Efficient Error Control Decoder Architectures for Noncoherent Random Linear Network Coding

Random linear network coding is an efficient technique for disseminating information in networks, but it is highly susceptible to errors. Kötter-Kschischang (KK) codes and Mahdavifar-Vardy (MV) codes are two important families of subspace codes that provide error control in noncoherent random linear network coding. List decoding has been used to decode MV codes beyond half distance. Existing hardware implementations of the rank metric decoder for KK codes suffer from limited throughput, long latency and high area complexity. The interpolation-based list decoding algorithm for MV codes still has high computational complexity, and its feasibility for hardware implementations has not been investigated. In this paper we propose efficient decoder architectures for both KK and MV codes and present their hardware implementations. Two serial architectures are proposed for KK and MV codes, respectively. An unfolded decoder architecture, which offers high throughput, is also proposed for KK codes. The synthesis results show that the proposed architectures for KK codes are much more efficient than rank metric decoder architectures, and demonstrate that the proposed decoder architecture for MV codes is affordable.     

Low Complexity Decoder Architecture for Low-Density Parity-Check Codes

In this paper, we propose a low complexity decoder architecture for low-density parity-check (LDPC) codes using a variable quantization scheme as well as an efficient highly-parallel decoding scheme. In the sum-product algorithm for decoding LDPC codes, the finite precision implementations have an important tradeoff between decoding performance and hardware complexity caused by two dominant area-consuming factors: one is the memory for updated messages storage and the other is the look-up table (LUT) for implementation of the nonlinear function Ψ(x). The proposed variable quantization schemes offer a large reduction in the hardware complexities for LUT and memory. Also, an efficient highly-parallel decoder architecture for quasi-cyclic (QC) LDPC codes can be implemented with the reduced hardware complexity by using the partially block overlapped decoding scheme and the minimized power consumption by reducing the total number of memory accesses for updated messages. For (3, 6) QC LDPC codes, our proposed schemes in implementing the highly-parallel decoder architecture offer a great reduction of implementation area by 33% for memory area and approximately by 28% for the check node unit and variable node unit computation units without significant performance degradation. Also, the memory accesses are reduced by 20%.     

Iterative Approximate Linear Programming Decoding of LDPC Codes With Linear Complexity

The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.      

A Low Complexity Decoding Algorithm for Extended Turbo Product Codes

In this letter, we propose a low complexity algorithm for extended turbo product codes by considering both the encoding and decoding aspects. For the encoding part, a new encoding scheme is presented for which the operations of looking up and fetching error patterns are no longer necessary, and thus the lookup table can be omitted. For the decoder, a new algorithm is proposed to extract the extrinsic information and reduce the redundancy. This new algorithm can reduce decoding complexity greatly and enhance the performance of the decoder. Simulation results are presented to show the effectiveness of the proposed scheme.     

FPGA implementation of low complexity LDPC iterative decoder

Low-density parity-check (LDPC) codes, proposed by Gallager, emerged as a class of codes which can yield very good performance on the additive white Gaussian noise channel as well as on the binary symmetric channel. LDPC codes have gained lots of importance due to their capacity achieving property and excellent performance in the noisy channel. Belief propagation (BP) algorithm and its approximations, most notably min-sum, are popular iterative decoding algorithms used for LDPC and turbo codes. The trade-off between the hardware complexity and the decoding throughput is a critical factor in the implementation of the practical decoder. This article presents introduction to LDPC codes and its various decoding algorithms followed by realisation of LDPC decoder by using simplified message passing algorithm and partially parallel decoder architecture. Simplified message passing algorithm has been proposed for trade-off between low decoding complexity and decoder performance. It greatly reduces the routing and check node complexity of the decoder. Partially parallel decoder architecture possesses high speed and reduced complexity. The improved design of the decoder possesses a maximum symbol throughput of 92.95 Mbps and a maximum of 18 decoding iterations. The article presents implementation of 9216 bits, rate-1/2, (3, 6) LDPC decoder on Xilinx XC3D3400A device from Spartan-3A DSP family.     

Iterative algebraic soft-decision list decoding of Reed-Solomon codes

In this paper, we present an iterative soft-decision decoding algorithm for Reed-Solomon (RS) codes offering both complexity and performance advantages over previously known decoding algorithms. Our algorithm is a list decoding algorithm which combines two powerful soft-decision decoding techniques which were previously regarded in the literature as competitive, namely, the Koetter-Vardy algebraic soft-decision decoding algorithm and belief-propagation based on adaptive parity-check matrices, recently proposed by Jiang and Narayanan. Building on the Jiang-Narayanan algorithm, we present a belief-propagation-based algorithm with a significant reduction in computational complexity. We introduce the concept of using a belief-propagation-based decoder to enhance the soft-input information prior to decoding with an algebraic soft-decision decoder. Our algorithm can also be viewed as an interpolation multiplicity assignment scheme for algebraic soft-decision decoding of RS codes.     

Guessing Facets: Polytope Structure and Improved LP Decoder

We investigate the structure of the polytope underlying the linear programming (LP) decoder introduced by Feldman, Karger, and Wainwright. We first show that for expander codes, every fractional pseudocodeword always has at least a constant fraction of nonintegral bits. We then prove that for expander codes, the active set of any fractional pseudocodeword is smaller by a constant fraction than that of any codeword. We further exploit these geometrical properties to devise an improved decoding algorithm with the same order of complexity as LP decoding that provably performs better. The method is very simple: it first applies ordinary LP decoding, and when it fails, it proceeds by guessing facets of the polytope, and then resolving the linear program on these facets. While the LP decoder succeeds only if the ML codeword has the highest likelihood over all pseudocodewords, we prove that the proposed algorithm, when applied to suitable expander codes, succeeds unless there exists a certain number of pseudocodewords, all adjacent to the ML codeword on the LP decoding polytope, and with higher likelihood than the ML codeword. We then describe an extended algorithm, still with polynomial complexity, that succeeds as long as there are at most polynomially many pseudocodewords above the ML codeword.     

完美空时分组码及其高性能解码算法

根据完美空时分组码（STBC）的结构特点提出了等效的垂直-贝尔实验室空时（V-BLAST）模型，在对该模型进行最小均方误差-判决反馈均衡（MMS-DFE）预处理之后，提出一种有边界约束的Fano解码器。该解码器可达到几乎最大似然（ML）性能，在很大的信噪比区域范围内其复杂度比目前典型的解码器低，而且该解码器可用于发射天线数大于接收天线数的系统。直接在复数域计算和处理，该解码器适用于任何星座形式。该解码器可用于任何能等效成V-BLAST模型的空时系统。仿真结果表明了该解码器的有效性。     

Soft-Output BEAST Decoding With Application to Product Codes

A Bidirectional Efficient Algorithm for Searching code Trees (BEAST) is proposed for efficient soft-output decoding of block codes and concatenated block codes. BEAST operates on trees corresponding to the minimal trellis of a block code and finds a list of the most probable codewords. The complexity of the BEAST search is significantly lower than the complexity of trellis-based algorithms, such as the Viterbi algorithm and its list generalizations. The outputs of BEAST, a list of best codewords and their metrics, are used to obtain approximate a posteriori probabilities (APPs) of the transmitted symbols, yielding a soft-input soft-output (SISO) symbol decoder referred to as the BEAST-APP decoder. This decoder is employed as a component decoder in iterative schemes for decoding of product and incomplete product codes. Its performance and convergence behavior are investigated using extrinsic information transfer (EXIT) charts and compared to existing decoding schemes. It is shown that the BEAST-APP decoder achieves performances close to the Bahl–Cocke–Jelinek–Raviv (BCJR) decoder with a substantially lower computational complexity.      

Configurable Multi-Rate Decoder Architecture for QC-LDPC Codes Based Broadband Broadcasting System

In this paper we present a Base-matrix based decoder architecture for multi-rate QC-LDPC codes proposed in broadband broadcasting system. We use the Modified Min-Sum Algorithm (MMSA) as the decoding algorithm in this architecture, which lowers the complexity of the LDPC decoder while keeping almost the same performance or even better. Based on this algorithm, we designed a novel check node processing unit to reduce the complexity of the decoder and facilitate the multiplex of the processing units. The decoder designed with hardware constraints is not only scalable in throughput, but also easily configurable to support different QC-LDPC codes flexible in code rate and code length.     

The hardness of decoding linear codes with preprocessing

The problem of maximum-likelihood decoding of linear block codes is known to be hard. The fact that the problem remains hard even if the code is known in advance, and can be preprocessed for as long as desired in order to device a decoding algorithm, is shown. The hardness is based on the fact that existence of a polynomial-time algorithm implies that the polynomial hierarchy collapses. Thus, some linear block codes probably do not have an efficient decoder. The proof is based on results in complexity theory that relate uniform and nonuniform complexity classes     

Soft trellis-based decoder for linear block codes

A systematic design of a trellis-based maximum-likelihood soft-decision decoder for linear block codes is presented. The essence of the decoder is to apply an efficient search algorithm for the error pattern on a reduced trellis representation of a certain coset. Rather than other efficient decoding algorithms, the proposed decoder is systematically designed for long codes, as well as for short codes. Computational gain of up to 6 is achieved for long high-rate codes over the well-known trellis decoder of Wolf (1978). Efficient decoders are also obtained for short and moderate length codes     

Low-Density Parity-Check Codes with 2-State Trellis Decoding

A class of low-density parity-check (LDPC) codes with a simple 2-state trellis structure is presented. For LDPC decoding, the conventional belief propagation (BP) algorithm consists of numerous sub-decoders of single-parity check codes and exchanges information between sub-decoders in an iterative manner. If the single-parity check codes can be constructed and grouped in a proper way, the decoder can be decomposed into few identical 2-state trellis decoders. Therefore, instead of numerous sub-decoders of single-parity check codes, an iterative decoding algorithm based on few sub-decoders over 2-state trellis is proposed. The proposed decoding algorithm improves the efficiency of message passing between sub-decoders and hence provides a fast convergent rate as compared to the standard BP algorithm. Simulation results show that the proposed scheme provides a better performance and a fast convergent rate as compared to those of standard BP algorithm. The result also shows that the proposed algorithm has a similar performance as that of asynchronous replica shuffled BP algorithm and has a slightly inferior performance than that of synchronous replica shuffled BP algorithm. However, complexity analysis shows that our proposed algorithm has complexity that is lower than that of the replica shuffled BP algorithm.     

High-throughput LDPC decoders

A high-throughput memory-efficient decoder architecture for low-density parity-check (LDPC) codes is proposed based on a novel turbo decoding algorithm. The architecture benefits from various optimizations performed at three levels of abstraction in system design-namely LDPC code design, decoding algorithm, and decoder architecture. First, the interconnect complexity problem of current decoder implementations is mitigated by designing architecture-aware LDPC codes having embedded structural regularity features that result in a regular and scalable message-transport network with reduced control overhead. Second, the memory overhead problem in current day decoders is reduced by more than 75% by employing a new turbo decoding algorithm for LDPC codes that removes the multiple checkto-bit message update bottleneck of the current algorithm. A new merged-schedule merge-passing algorithm is also proposed that reduces the memory overhead of the current algorithm for low to moderate-throughput decoders. Moreover, a parallel soft-input-soft-output (SISO) message update mechanism is proposed that implements the recursions of the Balh-Cocke-Jelinek-Raviv (BCJR) algorithm in terms of simple "max-quartet" operations that do not require lookup-tables and incur negligible loss in performance compared to the ideal case. Finally, an efficient programmable architecture coupled with a scalable and dynamic transport network for storing and routing messages is proposed, and a full-decoder architecture is presented. Simulations demonstrate that the proposed architecture attains a throughput of 1.92 Gb/s for a frame length of 2304 bits, and achieves savings of 89.13% and 69.83% in power consumption and silicon area over state-of-the-art, with a reduction of 60.5% in interconnect length.     

An efficient hybrid decoding algorithm for Reed-Solomon codes based on bit reliability

The paper presents a computationally efficient hybrid reliability-based decoding algorithm for Reed-Solomon (RS) codes. This hybrid decoding algorithm consists of two major components, a re-encoding process and a successive erasure-and-error decoding process for both bit and symbol levels. The re-encoding process is to generate a sequence of candidate codewords based on the information provided by the codeword decoded by an algebraic decoder and a set of test error patterns. Two criteria are used for testing in the decoding process to reduce the decoding computational complexity. The first criterion is devised to reduce the number of re-encoding operations by eliminating the unlikely error patterns. The second criterion is to test the optimality of a generated candidate codeword. Numerical results show that the proposed decoding algorithm can achieve either a near-optimum error performance or an asymptotically optimum error performance.     

Efficient VLSI Architecture for Soft-Decision Decoding of Reed–Solomon Codes

Reed–Solomon (RS) codes have very broad applications in digital communication and storage systems. The recently developed algebraic soft-decision decoding (ASD) algorithms of RS codes can achieve substantial coding gain with polynomial complexity. Among the ASD algorithms with practical multiplicity assignment schemes, the bit-level generalized minimum distance (BGMD) decoding algorithm can achieve similar or higher coding gain with lower complexity. ASD algorithms consist of two major steps: the interpolation and the factorization. In this paper, novel architectures for both steps are proposed for the BGMD decoder. The interpolation architecture is based on the newly proposed Lee-O'Sullivan (LO) algorithm. By exploiting the characteristics of the LO algorithm and the multiplicity assignment scheme in the BGMD decoder, the proposed interpolation architecture for a (255, 239) RS code can achieve 25% higher efficiency in terms of speed/area ratio than prior efforts. Root computation over finite fields and polynomial updating are the two main steps of the factorization. A low-latency and prediction-free scheme is introduced in this paper for the root computation in the BGMD decoder. In addition, novel coefficient storage schemes and parallel processing architectures are developed to reduce the latency of the polynomial updating. The proposed factorization architecture is 126% more efficient than the previous direct root computation factorization architecture.      

Decoding of High Rate Convolutional Codes Using the Dual Trellis

This paper deals with a posteriori probability (APP) decoding of high-rate convolutional codes, using the dual code's trellis. After deriving the dual APP (DAPP) algorithm from the APP relation, its trellis-based implementation is addressed. The challenge involved in practical implementation of a DAPP decoder is then highlighted. Metric representation schemes similar to the log domain used for log-APP decoding are shown to be unattractive for DAPP decoding due to quantization requirements. After explaining the nature of the DAPP metrics, an arc hyperbolic tangent (AHT) scheme is proposed and its equivalent arithmetic operations derived. By using an efficient approximation, an addition is translated to an addition in the AHT domain. Efficient techniques for normalization and extrinsic log-likelihood ratio (LLR ) calculation are presented which reduce implementation complexity significantly. Simulation results with different high-rate codes are given to show that the AHT-DAPP decoder performs similarly to a log-APP decoder and at the same time performs better than a decoder for a punctured code. A fully fixed-point model of an AHT-DAPP decoder is shown to perform close to an optimum decoder. The decoding complexity of the log-APP and AHT-DAPP decoders are listed and compared for several rate-k/(k+1) codes. It is shown that an AHT-DAPP decoder starts to be less complex from a code rate of 7/8 . When compared against a max-log-APP decoder, the AHT-DAPP decoder is less complex at a code rate of 9/10 and above.     

New SISO decoding algorithms

A new maximum a posteriori (MAP)-equivalent soft-input soft-output (SISO) algorithm is derived together with its simplified versions. The proposed SISO algorithms provide a good compromise between complexity and performance. Our simplest SISO algorithm has lower complexity than the log-MAP, the max-log-MAP, and the soft-output Viterbi (1998) algorithm SISO algorithms, and it is an equivalent max-log-MAP algorithm. When this algorithm is used, turbo codes with block length as short as 150 bits will outperform convolutional codes when compared on the basis of equal decoder complexity.     

Low complexity NB-LDPC decoder based on shared comparator architecture for ECN/EVN

Non-binary low density parity check (NB-LDPC) codes are considered as preferred candidate in conditions where short/medium codeword length codes and better performance at low signal to noise ratios (SNR) are required. They have better burst error correcting performance, especially with high order Galois fields (GF). A shared comparator(SCOMP) architecture for elementary of check node (ECN)/elementary of variable node (EVN) to reduce decoder complexity is introduced because high complexity of check node (CN) and variable node (VN) prevent NB-LDPC decoder from widely applications. The decoder over GF(16) is based on the extended min-sum (EMS) algorithm. The decoder matrix is an irregular structure as it can provide better performance than regular ones. In order to provide higher throughput and increase the parallel processing efficiency,the clock which is 8 times of the system frequency is adopted in this paper to drive the CN/VN modules. The decoder complexity can be reduced by 28% from traditional decoder when shared comparator architecture is introduced. The result of synthesis software shows that the throughput can achieve 34 Mbit/s at 10 iterations. The proposed architecture can be conveniently extended to GF such as GF(64) or GF(256). Compared with previous works, the decoder proposed in this paper has better hardware efficiency for practical applications.