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.     

RS码与LDPC码的联合迭代译码

针对RS码与LDPC码的串行级联结构,提出了一种基于自适应置信传播(ABP)的联合迭代译码方法.译码时,LDPC码置信传播译码器输出的软信息作为RS码ABP译码器的输入;经过一定迭代译码后,RS码译码器输出的软信息又作为LDPC译码器的输入.软输入软输出的RS译码器与LDPC译码器之间经过多次信息传递,译码性能有很大提高.码长中等的LDPC码采用这种级联方案,可以有效克服短环的影响,消除错误平层.仿真结果显示:AWGN信道下这种基于ABP的RS码与LDPC码的联合迭代译码方案可以获得约0.8 dB的增益.     

Memory-efficient sum-product decoding of LDPC codes

Low-density parity-check (LDPC) codes perform very close to capacity for long lengths on several channels. However, the amount of memory (fixed-point numbers that need to be stored) required for implementing the message-passing algorithm increases linearly as the number of edges in the graph increases. In this letter, we propose a decoding algorithm for decoding LDPC codes that reduces the memory requirement at the decoder. The proposed decoding algorithm can be analyzed using density evolution; further, we show how to design good LDPC codes using this. Results show that this algorithm provides almost the same performance as the conventional sum-product decoding of LDPC codes.     

LDPC-based iterative joint source-channel decoding for JPEG2000.

A framework is proposed for iterative joint source-channel decoding of JPEG2000 codestreams. At the encoder, JPEG2000 is used to perform source coding with certain error-resilience (ER) modes, and LDPC codes are used to perform channel coding. During decoding, the source decoder uses the ER modes to identify corrupt sections of the codestream and provides this information to the channel decoder. Decoding is carried out jointly in an iterative fashion. Experimental results indicate that the proposed method requires fewer iterations and improves overall system performance.     

Comments on successive relaxation for decoding of LDPC codes

The application of successive relaxation (SR) to the fixed-point problem associated with the iterative decoding of low-density parity-check (LDPC) codes was proposed by Hemati et al.. The simulation results presented by Hemati et al. for the SR version of belief propagation (BP) in the likelihood ratio (LR) domain and that of min-sum (MS) in the log-likelihood ratio (LLR) domain are based on the assumption of all-zero codeword transmission. This assumption however results in erroneous error rates when SR is applied in the LR domain. Here, we correct the simulation results reported by Hemati et al. for SR-BP in the LR domain. Furthermore, we investigate the performance of SR-BP and SR-MS in the LLR and LR domains, respectively. The results for a binary input additive white Gaussian noise (BIAWGN) channel show that for both BP and MS, the application of SR in the two domains of LR and LLR results in different error correcting performance. In particular, for the tested codes, it is shown that among the four algorithms, SR-MS-LLR has the best performance. It outperforms standard MS and BP by up to about 0.6 dB and 0.3 dB, respectively, offering an attractive solution in terms of performance/complexity tradeoff.     

Fast-Converging and Low-Power LDPC Decoding: Algorithm,Architecture, and VLSI Implementation

Low-latency and energy-efficient multi-Gbps LDPC decoding requires fast-converging iterative schedules. Hardware decoder architectures based on such schedules can achieve high throughput at low clock speeds, resulting in reduced power consumption and relaxed timing closure requirements for physical VLSI design. In this work, a fast column message-passing (FCMP) schedule for decoding LDPC codes is presented and investigated. FCMP converges in half the number of iterations compared to existing serial decoding schedules, has a significantly lower computational complexity than residual-belief-propagation (RBP)-based schedules, and consumes less power compared to state-of-the-art schedules. An FCMP decoder architecture supporting IEEE 802.11ad (WiGig) LDPC codes is presented. The decoder is fully pipelined to decode two frames with no idle cycles. The architecture is synthesized using the TSMC 40 nm and 65 nm CMOS technology nodes, and operates at a clock-frequency of 200 MHz. The decoder achieves a throughput of 8.4 Gbps, and it consumes 72 mW of power when synthesized using the 40 nm technology node. This results in an energy efficiency of 8.6 pJ/bit, which is the best-reported energy-efficiency in the literature for a WiGig LDPC decoder.

     

基于LDPC乘积码的BICM-ID方案性能分析

提出一种采用LDPC乘积码和BICM-ID相结合的编码调制技术.该方案编码采用LDPC乘积码,译码可以采取三个迭代过程:在解调器和译码器之间迭代,LDPC乘积码的分量码之间迭代,以及分量码内部迭代.因此采取合理的迭代译码策略,可以提高的译码效率.仿真结果显示,该方案在AWGN信道和Rayleigh信道条件下,与数字电视地面多媒体广播DTMB采用的编码调制方案相比具有更好的误比特性能.     

LDPC-based channel coding of correlated sources with iterative joint decoding

This letter considers low-density parity-check (LDPC) coding of correlated binary sources and a novel iterative joint channel decoding without communication of any side information. We demonstrate that depending on the extent of the source correlation, additional coding gains can be obtained. Two stages of iterative decoding are employed. During global iterations, updated estimates of the source correlation are obtained and passed on to the sum-product decoder that performs local iterations with a predefined stopping criterion and/or a maximum number of local decoding iterations. Simulation results indicate that very few global iterations (2-5) are sufficient to reap significant benefits from implicit knowledge of source correlation. Finally, we provide analytical performance bounds for our iterative joint decoder and comparisons with sample simulation results.     

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.     

低复杂度的连续相位调制与LDPC联合迭代译码算法

连续相位调制与低密度奇偶校验(LDPC)码编译码技术在提高频谱利用率的同时能够有效降低发射功率,然而这会增加通信系统的复杂度。为此,提出了一种低复杂度的联合迭代译码算法解决此问题。该算法以符号/比特的可靠度作为内外译码器之间的迭代信息。仿真结果表明,新的联合迭代译码算法的性能与概率域下的算法几乎没有差异,在总迭代次数相同的情况下,采用低复杂度联合迭代的性能相比于未采用联合迭代的性能有约0.75 dB的增益。     

Low-density parity check codes and iterative decoding for long-haul optical communication systems

A forward-error correction (FEC) scheme based on low-density parity check (LDPC) codes and iterative decoding using belief propagation in code graphs is presented in this paper. We show that LDPC codes provide a significant system performance improvement with respect to the state-of-the-art FEC schemes employed in optical communications systems. We present a class of structured codes based on mutually orthogonal Latin rectangles. Such codes have high rates and can lend themselves to very low-complexity encoder/decoder implementations. The system performance is further improved by a code design that eliminates short cycles in a graph employed in iterative decoding.     

On general linear block code decoding using the sum-product iterative decoder

The sum-product iterative decoder, conventionally used for low-density parity-check (LDPC) codes, hold promise as a decoder for general linear block code decoding. However, the promise is only partly fulfilled because, as we show experimentally, the decoder performance degrades rapidly as a function of parity check matrix weight. Even in the case of decoder failure, however, we demonstrate that there is information present in the decoder output probabilities that can still help with the decoding problem.     

CORDIC instructions for LDPC decoding on SDR platforms

Wireless protocols strive to increase spectral efficiency and achieve high data throughput. Low-density parity-check (LDPC) codes are advanced forward error correction (FEC) codes that use iterative decoding techniques to achieve close to the Shannon capacity. Due to their superior performance, state-of-art wireless protocols, such as WiMAX and LTE Advanced, are adopting LDPC codes. LDPC codes come with the high cost of drastically increased computational effort for decoding. Among the proposed decoding algorithms, the belief propagation (BP) algorithm leads to a good approximation of an optimal decoder; however, it uses compute-intensive hyperbolic trigonometric functions. To reduce the computational complexity, typical LDPC decoder implementations use simplified algorithms, such as the min-sum algorithm, at the expense of reduced signal processing performance. Efficient and accurate methods to compute hyperbolic trigonometric functions can facilitate the use of the BP algorithm in real-time LDPC decoder implementations. This paper investigates hyperbolic COordinate Rotation DIgital Computer (CORDIC) instruction set architecture (ISA) extensions for software-defined radio (SDR) processors to compute the hyperbolic trigonometric functions for LDPC decoding efficiently. The CORDIC ISA extensions are evaluated on the low-power multi-threaded Sandbridge Sandblaster? SB3000 platform. The computational performance, numerical accuracy, hardware estimates, power consumption estimates, and memory requirements with the CORDIC ISA extensions are compared to a baseline implementation without these extensions on the SB3000.     

A 0.18-$muhbox m$CMOS Analog Min-Sum Iterative Decoder for a (32,8) Low-Density Parity-Check (LDPC) Code

Current-mode circuits are presented for implementing analog min-sum (MS) iterative decoders. These decoders are used to efficiently decode the best known error correcting codes such as low-density parity-check (LDPC) codes and turbo codes. The proposed circuits are devised based on current mirrors, and thus, in any fabrication technology that accurate current mirrors can be designed, analog MS decoders can be implemented. The functionality of the proposed circuits is verified by implementing an analog MS decoder for a (32,8) LDPC code in a 0.18-mum CMOS technology. This decoder is the first reported analog MS decoder. For low signal to noise ratios where the circuit imperfections are dominated by the noise of the channel, the measured error correcting performance of this chip in steady-state condition surpasses that of the conventional floating-point discrete-time synchronous MS decoder. When data throughput is 6 Mb/s, loss in the coding gain compared to the conventional MS decoder at BER of 10^-3 is about 0.3 dB and power consumption is about 5 mW. This is the first time that an analog decoder has been successfully tested for an LDPC code, though a short one     

Using linear programming to Decode Binary linear codes

A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d/sub frac/ of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to /spl lceil/d/sub frac//2/spl rceil/-1 errors and that there are codes with d/sub frac/=/spl Omega/(n/sup 1-/spl epsi//). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.     

An analysis of the block error probability performance of iterative decoding

Asymptotic iterative decoding performance is analyzed for several classes of iteratively decodable codes when the block length of the codes N and the number of iterations I go to infinity. Three classes of codes are considered. These are Gallager's regular low-density parity-check (LDPC) codes, Tanner's generalized LDPC (GLDPC) codes, and the turbo codes due to Berrou et al. It is proved that there exist codes in these classes and iterative decoding algorithms for these codes for which not only the bit error probability P/sub b/, but also the block (frame) error probability P/sub B/, goes to zero as N and I go to infinity.     

Low-floor decoders for LDPC codes

One of the most significant impediments to the use of LDPC codes in many communication and storage systems is the error-rate floor phenomenon associated with their iterative decoders. The error floor has been attributed to certain subgraphs of an LDPC code?s Tanner graph induced by so-called trapping sets. We show in this paper that once we identify the trapping sets of an LDPC code of interest, a sum-product algorithm (SPA) decoder can be custom-designed to yield floors that are orders of magnitude lower than floors of the the conventional SPA decoder. We present three classes of such decoders: (1) a bi-mode decoder, (2) a bit-pinning decoder which utilizes one or more outer algebraic codes, and (3) three generalized-LDPC decoders. We demonstrate the effectiveness of these decoders for two codes, the rate-1/2 (2640,1320) Margulis code which is notorious for its floors and a rate-0.3 (640,192) quasi-cyclic code which has been devised for this study. Although the paper focuses on these two codes, the decoder design techniques presented are fully generalizable to any LDPC code.     

Estimation of Bit and Frame Error Rates of Finite-Length Low-Density Parity-Check Codes on Binary Symmetric Channels

A method for estimating the performance of low-density parity-check (LDPC) codes decoded by hard-decision iterative decoding algorithms on binary symmetric channels (BSCs) is proposed. Based on the enumeration of the smallest weight error patterns that cannot be all corrected by the decoder, this method estimates both the frame error rate (FER) and the bit error rate (BER) of a given LDPC code with very good precision for all crossover probabilities of practical interest. Through a number of examples, we show that the proposed method can be effectively applied to both regular and irregular LDPC codes and to a variety of hard-decision iterative decoding algorithms. Compared with the conventional Monte Carlo simulation, the proposed method has a much smaller computational complexity, particularly for lower error rates.     

High-Throughput Layered LDPC Decoding Architecture

This paper presents a high-throughput decoder architecture for generic quasi-cyclic low-density parity-check (QC-LDPC) codes. Various optimizations are employed to increase the clock speed. A row permutation scheme is proposed to significantly simplify the implementation of the shuffle network in LDPC decoder. An approximate layered decoding approach is explored to reduce the critical path of the layered LDPC decoder. The computation core is further optimized to reduce the computation delay. It is estimated that 4.7 Gb/s decoding throughput can be achieved at 15 iterations using the current technology.      

A fast LDPC encoder/decoder for small/medium codes

Although Low-Density Parity-Check (LDPC) codes perform admirably for large block sizes — being mostly resilient to low levels of channel SNR and errors in channel equalization — real time operation and low computational effort require small and medium sized codes, which tend to be affected by these two factors. For these small to medium codes, a method for designing efficient regular codes is presented and a new technique for reducing the dependency of correct channel equalization, without much change in the inner workings or architecture of existing LDPC decoders is proposed. This goal is achieved by an improved intrinsic Log-Likelihood Ratio (LLR) estimator in the LDPC decoder — the ILE-Decoder, which only uses LDPC decoder-side information gathered during standard LDPC decoding. This information is used to improve the channel parameters estimation, thus improving the reliability of the code correction, while reducing the number of required iterations for a successful decoding. Methods for fast encoding and decoding of LDPC codes are presented, highlighting the importance of assuring low encoding/decoding latency with maintaining high throughput. The assumptions and rules that govern the estimation process via subcarrier corrected-bit accounting are presented, and the Bayesian inference estimation process is detailed. This scheme is suitable for application to multicarrier communications, such as OFDM. Simulation results in a PLC-like environment that confirm the good performance of the proposed LDPC coder/decoder are presented.