A scalable LDPC decoder ASIC architecture with bit-serial message exchange

We present a scalable bit-serial architecture for ASIC realizations of low-density parity check (LDPC) decoders. Supporting the architecture's potential, we describe a decoder implementation for a (256,128) regular-(3,6) LDPC code that has a decoded information throughput of 250 Mbps, a core area of 6.96 mm² in 180-nm 6-metal CMOS, and an energy efficiency of 7.56 nJ per uncoded bit at low signal-to-noise ratios. The decoder is fully block-parallel, with all bits of each 256-bit codeword being processed by 256 variable nodes and 128 parity check nodes that together form an 8-stage iteration pipeline. Extrinsic messages are exchanged bit-serially between the variable and parity check nodes to significantly reduce the interleaver wiring. Parity check node processing is also bit-serial. The silicon implementation performs 32 iterations of the min-sum decoding algorithm on two staggered codewords in the same pipeline. The results of a supplementary layout study show that the reduced wiring congestion makes the decoder readily scaleable up to the longer kilobit-size LDPC codewords that appear in important emerging communication standards.     

A class of irregular LDPC codes with low error floor and low encoding complexity

In this letter, we propose a class of irregular structured low-density parity-check (LDPC) codes with low error floor and low encoding complexity by designing the parity check matrix in a triangular plus dual-diagonal form. The proposed irregular codes clearly lower the error floor and dramatically improve the performance in the waterfall region of error-rate curves. Being characterized by linear encoding complexity, the encoders of the proposed codes attain throughputs over 10 Gbit/s.     

非规则LDPC码的不等错误保护性能研究

提出了一种具有不等错误保护性能的非规则低密度校验(LDPC,low-density parity-check)码信道编码方案, 构造了重量递增校验(weight-increasing parity-check)矩阵,系统编码时,重要信息比特映射到LDPC码的“精华”比特上。AWGN和Rayliegh衰落信道的仿真结果表明,与随机构造的非规则LDPC码相比,WICP-LDPC码具有好的UEP性能。     

基于矩阵分块的LDPC码快速编码结构研究

低密度奇偶校验(LDPC)码由于具有接近香农限的性能和高速并行的译码结构而成为研究热点。然而,当码长很长时,编译码器的硬件实现变得很困难。文章从编译码实际实现的角度出发,提出一种基于分块的LDPC码下三角形校验矩阵结构,降低了编译码复杂度,不仅可以实现线性时间编码,同时还可以实现部分并行译码。仿真结果表明,具有这种结构的LDPC码和随机构造的LDPC码相比具有同样好的纠错性能。     

Results on the Improved Decoding Algorithm for Low-Density Parity-Check Codes Over the Binary Erasure Channel

In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates     

Design of low-density parity-check codes for modulation and detection

A coding and modulation technique is studied where the coded bits of an irregular low-density parity-check (LDPC) code are passed directly to a modulator. At the receiver, the variable nodes of the LDPC decoder graph are connected to detector nodes, and iterative decoding is accomplished by viewing the variable and detector nodes as one decoder. The code is optimized by performing a curve fitting on extrinsic information transfer charts. Design examples are given for additive white Gaussian noise channels, as well as multiple-input, multiple-output (MIMO) fading channels where the receiver, but not the transmitter, knows the channel. For the MIMO channels, the technique operates within 1.25 dB of capacity for various antenna configurations, and thereby outperforms a scheme employing a parallel concatenated (turbo) code by wide margins when there are more transmit than receive antennas.     

LDPC Codes Over Rings for PSK Modulation

This paper describes the design and analysis of low-density parity-check (LDPC) codes over rings and shows how these codes, when mapped onto appropriate signal constellations, can be used to effect bandwidth-efficient modulation. Specifically, LDPC codes are constructed over the integer rings$BBZ_m$and$BBG_m^2$and mapped onto phase-shift keying (PSK)-type signal sets to yield geometrically uniform signal space codes. This paper identifies and addresses the design issues that affect code performance. Examples of codes over$BBZ_8$and$BBG_64$mapped onto$8$-ary and$64$-ary signal sets at a spectral efficiency of 1.5 and 2.0 bits per second per hertz (b/s/Hz) illustrate the approach; simulation of these codes over the additive white Gaussian noise (AWGN) channel demonstrates that this approach is a good alternative to bandwidth-efficient techniques based on binary LDPC codes—e.g., bit-interleaved coded modulation.     

CRC-assisted error correction in a convolutionally coded system

In communication systems employing a serially concatenated cyclic redundancy check (CRC) code along with a convolutional code (CC), erroneous packets after CC decoding are usually discarded. The list Viterbi algorithm (LVA) and the iterative Viterbi algorithm (IVA) are two existing approaches capable of recovering erroneously decoded packets. We here employ a soft decoding algorithm for CC decoding, and introduce several schemes to identify error patterns using the posterior information from the CC soft decoding module. The resultant iterative decoding-detecting (IDD) algorithm improves error performance by iteratively updating the extrinsic information based on the CRC parity check matrix. Assuming errors only happen in unreliable bits characterized by small absolute values of the log-likelihood ratio (LLR), we also develop a partial IDD (P-IDD) alternative which exhibits comparable performance to IDD by updating only a subset of unreliable bits. We further derive a soft-decision syndrome decoding (SDSD) algorithm, which identifies error patterns from a set of binary linear equations derived from CRC syndrome equations. Being noniterative, SDSD is able to estimate error patterns directly from the decoder output. The packet error rate (PER) performance of SDSD is analyzed following the union bound approach on pairwise errors. Simulations indicate that both IDD and IVA are better tailored for single parity check (PC) codes than for CRC codes. SDSD outperforms both IDD and LVA with weak CC and strong CRC. Applicable to AWGN and flat fading channels, our algorithms can also be extended to turbo coded systems.     

Doubly Generalized LDPC Codes over the AWGN Channel

In this paper, the design of doubly generalized low-density parity-check (DGLDPC) codes is proposed. This approach generalizes the structure of LDPC codes at both check and variable nodes. The performance of DGLDPC codes over the AWGN channel is analyzed using EXIT charts. Combined with differential evolution optimization, this analysis provides thresholds for DGLDPC codes that are better than that of LDPC and GLDPC codes with the same maximum variable degree. These theoretical thresholds are verified via simulations. Furthermore DGLDPC codes exhibit a lower error floor compared with their LDPC and GLDPC counterparts.     

Efficient Multi-rate Encoder of QC-LDPC Codes Based on FPGA for WIMAX Standard

An efficient multi-rate encoder for IEEE 802.16e LDPC codes which outperforms current single rate encoders with acceptable hardware consumption and effi-cient memory consumption is proposed. This design uti-lizes the common dual-diagonal structure in parity matri-ces to avoid the inverse matrix operation which requires extensive computations. Parallel Matrix-vector multipli-cation (MVM) units, bidirectional operation and storage compression are applied to this multi-rate encoder to in-crease the encoding speed and significantly reduce the quantity of memory bits required. The proposed encoding architecture also contributes to the design of multi-rate encoders whose parity matrices are dual-diagonally struc-tured and have an Approximately lower triangular (ALT) form, such as in IEEE 802.11n and IEEE 802.22. Simu-lation results verified that the proposed encoder can effi-ciently work for all code rates specified in WIMAX stan-dard. With a maximum clock frequency of 117 MHz, the encoder achieves 3 to 10 times higher throughput than prior works. The proposed encoder is capable to switch among six rates by adjusting the input parameter and it achieves the throughput up to 1Gbps.     

A Flexible LDPC/Turbo Decoder Architecture

Low-density parity-check (LDPC) codes and convolutional Turbo codes are two of the most powerful error correcting codes that are widely used in modern communication systems. In a multi-mode baseband receiver, both LDPC and Turbo decoders may be required. However, the different decoding approaches for LDPC and Turbo codes usually lead to different hardware architectures. In this paper we propose a unified message passing algorithm for LDPC and Turbo codes and introduce a flexible soft-input soft-output (SISO) module to handle LDPC/Turbo decoding. We employ the trellis-based maximum a posteriori (MAP) algorithm as a bridge between LDPC and Turbo codes decoding. We view the LDPC code as a concatenation of n super-codes where each super-code has a simpler trellis structure so that the MAP algorithm can be easily applied to it. We propose a flexible functional unit (FFU) for MAP processing of LDPC and Turbo codes with a low hardware overhead (about 15% area and timing overhead). Based on the FFU, we propose an area-efficient flexible SISO decoder architecture to support LDPC/Turbo codes decoding. Multiple such SISO modules can be embedded into a parallel decoder for higher decoding throughput. As a case study, a flexible LDPC/Turbo decoder has been synthesized on a TSMC 90 nm CMOS technology with a core area of 3.2 mm². The decoder can support IEEE 802.16e LDPC codes, IEEE 802.11n LDPC codes, and 3GPP LTE Turbo codes. Running at 500 MHz clock frequency, the decoder can sustain up to 600 Mbps LDPC decoding or 450 Mbps Turbo decoding.     

Reliability-based coded modulation with low-density parity-check codes

In this letter, we consider the interleaver design in bit-interleaved coded modulation (BICM) with low-density parity-check (LDPC) codes. The design paradigm is to provide more coding protection through iterative decoding to bits that are less protected by modulation (and are thus less reliable at the output of the demodulator). The design is carried out by an ad hoc search algorithm over the column permutations of the parity-check matrix. Our simulations show that the proposed reliability-based coded modulation scheme can improve the error-rate performance of conventional BICM schemes based on regular LDPC codes by a few tenths of a decibel, with no added complexity.     

Efficient encoding of quasi-cyclic low-density parity-check codes

Quasi-cyclic (QC) low-density parity-check (LDPC) codes form an important subclass of LDPC codes. These codes have encoding advantage over other types of LDPC codes. This paper addresses the issue of efficient encoding of QC-LDPC codes. Two methods are presented to find the generator matrices of QC-LDPC codes in systematic-circulant (SC) form from their parity-check matrices, given in circulant form. Based on the SC form of the generator matrix of a QC-LDPC code, various types of encoding circuits using simple shift registers are devised. It is shown that the encoding complexity of a QC-LDPC code is linearly proportional to the number of parity bits of the code for serial encoding, and to the length of the code for high-speed parallel encoding.     

Augmented Belief Propagation Decoding of Low-Density Parity Check Codes

We propose an augmented belief propagation (BP) decoder for low-density parity check (LDPC) codes which can be utilized on memoryless or intersymbol interference channels. The proposed method is a heuristic algorithm that eliminates a large number of pseudocodewords that can cause nonconvergence in the BP decoder. The augmented decoder is a multistage iterative decoder, where, at each stage, the original channel messages on select symbol nodes are replaced by saturated messages. The key element of the proposed method is the symbol selection process, which is based on the appropriately defined subgraphs of the code graph and/or the reliability of the information received from the channel. We demonstrate by examples that this decoder can be implemented to achieve substantial gains (compared to the standard locally-operating BP decoder) for short LDPC codes decoded on both memoryless and intersymbol interference Gaussian channels. Using the Margulis code example, we also show that the augmented decoder reduces the error floors. Finally, we discuss types of BP decoding errors and relate them to the augmented BP decoder.     

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.     

Implementation of a Flexible LDPC Decoder

Low-density parity-check codes (LDPC) are among the most powerful error correcting tools today available. For this reason they became very popular in several applications such as the digital satellite broadcasting system (DVB-S2), wireless local area network (IEEE 802.11n) and metropolitan area network (802.16e). Whereas several code-specific decoders have been proposed in the literature, the implementation of a high performance yet flexible LDPC decoder still is a challenging topic. This work presents a novel formulation of the decoding algorithm that strongly simplifies internal communication requirements and enables the development of decoders supporting generally defined LDPC codes. The resulting architecture is tailored to decode both IEEE 802.11n and IEEE 802.16e LDPC codes, as well as any other code of comparable complexity. The implementation cost deriving from the full flexibility offered by the proposed approach is also evaluated.     

Bootstrap decoding of low-density parity-check codes

An initial bootstrap step for the decoding of low-density parity-check (LDPC) codes is proposed. Decoding is initiated by first erasing a number of less reliable bits. New values and reliabilities are then assigned to erasure bits by passing messages from nonerasure bits through the reliable check equations. The bootstrap step is applied to the weighted bit-flipping algorithm to decode a number of LDPC codes. Large improvements in both performance and complexity are observed.     

Quasi-cyclic LDPC codes using overlapping matrices and their layered decoders

Quasi-cyclic (QC) low-density parity-check (LDPC) codes have the parity-check matrices consisting of circulant matrices. Since QC LDPC codes whose parity-check matrices consist of only circulant permutation matrices are difficult to support layered decoding and, at the same time, have a good degree distribution with respect to error correcting performance, adopting multi-weight circulant matrices to parity-check matrices is useful but it has not been much researched. In this paper, we propose a new code structure for QC LDPC codes with multi-weight circulant matrices by introducing overlapping matrices. This structure enables a system to operate on dual mode in an efficient manner, that is, a standard QC LDPC code is used when the channel is relatively good and an enhanced QC LDPC code adopting an overlapping matrix is used otherwise. We also propose a new dual mode parallel decoder which supports the layered decoding both for the standard QC LDPC codes and the enhanced QC LDPC codes. Simulation results show that QC LDPC codes with the proposed structure have considerably improved error correcting performance and decoding throughput.     

针对 IRA-LDPC 码类的半随机半代数结构设计

提出用半随机半代数结构的设计方法来构造IRA-LDPC码的信息位所对应的奇偶校验矩阵H d。与现有结构化LDPC码相比,所给出的H d矩阵的结构化紧凑表示阵列的独特优势在于：可使H d矩阵中每个1元素的位置坐标均能用数学表达式计算得到,不仅极大地降低了随机奇偶校验矩阵对存储资源的消耗,而且还为LDPC编解码器的低复杂度硬件实现提供了可能性。与现有工业标准中的LDPC码相比,所提出的IRA-LDPC码在误码率与信噪比的仿真性能方面也占有优势。     

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

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