Improved Sliced Message Passing Architecture for High Throughput Decoding of LDPC Codes

This paper presents an architecture for high-throughput decoding of high-rate Low-Density Parity-Check (LDPC) codes. The proposed architecture is a modification of the sliced message passing (SMP) decoding architecture which overlaps the check-node and variable-node update stages, achieving a good tradeoff between area and throughput, and also, high hardware utilization efficiency (HUE). The proposed modification does not affect the performance of the SMP algorithm and yields an area reduction of 33%. As an example, SMP architecture and the proposed modification was synthesized in a 90 nm CMOS process for the 2048-bit LDPC code of the IEEE802.3an standard with 16 iterations achieving a throughput of 5.9 Gbps with 15.3 mm² and 6.2 Gbps with 10.2 mm², respectively.     

Modified Shuffled Based Architecture for High-Throughput Decoding of LDPC Codes

Low Density Parity-Check (LDPC) codes achieve the best performance when they are decoded with the sum-product (SP) algorithm. This is a two-phase iterative algorithm where two types of messages are interchanged and updated in each iteration. The group-shuffled or layered decoding schemes applied to the SP algorithm speed up its convergence by modifying its schedule, so they yield a reduction in the number of iterations required to achieve a given performance. However, the two-phase processing is still maintained. In this paper a modification of the group-shuffled scheme suitable for high-rate LDPC codes is proposed. The modification allows the overlapping of the two-phase computation, achieving a convergence speed up close to that of the group-shuffled scheme with higher throughput. Besides, high throughput architectures are presented for the modified algorithm. As an example, the proposed architecture has been implemented for the 2048-bit LDPC code of the IEEE 802.3an standard and it was synthesized in a 90 nm CMOS process achieving a throughput of 22.40 Gbps at 14 iterations with a clock frequency of 306 MHz and a total area of 10.5 mm². Furthermore, the decoder performs within 0.5 dB of the floating-point 100 iterations sum-product algorithm at a PER of 10⁻⁵.     

An LDPC Decoder Chip Based on Self-Routing Network for IEEE 802.16e Applications

An LDPC decoder chip fully compliant to IEEE 802.16e applications is presented. Since the parity check matrix can be decomposed into sub-matrices which are either a zero-matrix or a cyclic shifted matrix, a phase-overlapping message passing scheme is applied to update messages immediately, leading to enhance decoding throughput. With only one shifter-based permutation structure, a self-routing switch network is proposed to merge 19 different sub-matrix sizes as defined in IEEE 802.16e and enable parallel message to be routed without congestion. Fabricated in the 90 nm 1P9M CMOS process, this chip achieves 105 Mb/s at 20 iterations while decoding the rate-5/6 2304-bit code at 150 MHz operation frequency. To meet the maximum data rate in IEEE 802.16e, this chip operates at 109 MHz frequency and dissipates 186 mW at 1.0 V supply.     

High-throughput layered decoder implementation for quasi-cyclic LDPC codes

This paper presents a high-throughput decoder design for the Quasi-Cyclic (QC) Low-Density Parity-Check (LDPC) codes. Two new techniques are proposed, including parallel layered decoding architecture (PLDA) and critical path splitting. PLDA enables parallel processing for all layers by establishing dedicated message passing paths among them. The decoder avoids crossbar-based large interconnect network. Critical path splitting technique is based on articulate adjustment of the starting point of each layer to maximize the time intervals between adjacent layers, such that the critical path delay can be split into pipeline stages. Furthermore, min-sum and loosely coupled algorithms are employed for area efficiency. As a case study, a rate-1/2 2304-bit irregular LDPC decoder is implemented using ASIC design in 90nm CMOS process. The decoder can achieve the maximum decoding throughput of 2.2Gbps at 10 iterations. The operating frequency is 950MHz after synthesis and the chip area is 2.9mm².     

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.     

基于FPGA的不可分层LDPC码译码器

针对不可分层LDPC码无法采用分层译码算法的问题,设计了一种新型的LDPC码分层译码器。与传统分层译码器的结构不同,新结构在各层间进行并行更新,各层内进行串行更新。通过保证在不同分层的同一变量节点不同时进行更新,达到分层译码算法分层递进更新的目标。选用Altera公司的CycloneⅢ系列EP3C120器件,实现码率3/4,码长8 192的(3,12)规则不可分层QC-LDPC码译码器的布局布线,在最大迭代次数为5次时,最高时钟频率可以达到45.44 MHz,吞吐量可以达到47.6 Mbps。     

IEEE802.16e标准LDPC译码器设计与实现

LDPC码自在上个世纪90年代被重新发现以来,以其接近香农极限的差错控制性能,以及译码复杂度低、吞吐率高的优点引起了人们的关注,成为继Turbo码之后信道编码界的又一研究热点。利用FPGA设计并实现了一种基于IEEE802.16e标准的LDPC码译码器。该译码器采用偏移最小和（Offset Min-Sum）算法,其偏移因子β取值为0.125,具有接近置信传播（Belief Propagation）算法浮点的性能。译码器在结构上采用了部分并行结构,可以灵活支持标准中定义的所有码率和码长的LDPC码的译码。此外,该译码器还支持对连续输入的数据块进行处理,并具有动态停止迭代功能。硬件综合结果表明,该译码器工作频率为150MHz时,固定15次迭代,最低可达到95Mb/s的译码吞吐率,完全满足802.16e标准的要求。     

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.     

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.     

Optimal Overlapped Message Passing Decoding of Quasi-Cyclic LDPC Codes

Efficient hardware implementation of low-density parity-check (LDPC) codes is of great interest since LDPC codes are being considered for a wide range of applications. Recently, overlapped message passing (OMP) decoding has been proposed to improve the throughput and hardware utilization efficiency (HUE) of decoder architectures for LDPC codes. In this paper, we first study the scheduling for the OMP decoding of LDPC codes, and show that maximizing the throughput gain amounts to minimizing the intra- and inter-iteration waiting times. We then focus on the OMP decoding of quasi-cyclic (QC) LDPC codes. We propose a partly parallel OMP decoder architecture and implement it using FPGA. For any QC LDPC code, our OMP decoder achieves the maximum throughput gain and HUE due to overlapping, hence has higher throughput and HUE than previously proposed OMP decoders while maintaining the same hardware requirements. We also show that the maximum throughput gain and HUE achieved by our OMP decoder are ultimately determined by the given code. Thus, we propose a coset-based construction method, which results in QC LDPC codes that allow our optimal OMP decoder to achieve higher throughput and HUE.     

适于分层译码算法的LDPC码构造方法

The layered decoding algorithm has been widely used in the implementation of Low Density Parity Check (LDPC) decoders, due to its high convergence speed. However, the pipeline operation of the layered decoder may introduce memory access conflicts, which heavily deteriorates the decoder throughput. To essentially deal with the issue of memory access conflicts, we propose a construction algorithm of LDPC codes, to which a constraint condition is added in the Progressive Edge-Growth (PEG) algorithm. The constraint condition can guarantee that for our constructed LDPC codes, the sets of all the variable nodes connected to the consecutive layers do not share any common variable node, which can avoid the memory access conflicts. Simulation results show that the performance of our constructed LDPC codes is close to the several other LDPC codes adopted in wireless standards. Moreover, compared with the decoder for IEEE 802. 16e LDPC codes, the throughput of our LDPC decoder has large improvement, while the chip resource consumption is unchanged. Thus, our constructed LD-PC codes can be adopted in the high-speed transmission.     

Decoder Design for RS-Based LDPC Codes

This brief studies very large-scale integration (VLSI) decoder architectures for RS-based low-density parity-check (LDPC) codes, which are a special class of LDPC codes based on Reed-Solomon codes. The considered code ensemble is well known for its excellent error-correcting performance and has been selected as the forward error correction coding scheme for 10GBase-T systems. By exploiting the shift-structured properties hidden in the algebraically generated parity-check matrices, novel decoder architectures are developed with significant advantages of high level of parallel decoding, efficient usage of memory, and low complexity of interconnection. To demonstrate the effectiveness of the proposed techniques, we completed a high-speed decoder design for a (2048, 1723) regular RS-LDPC code, which achieves 10-Gb/s throughput with only 820 000 gates. Furthermore, to support all possible RS-LDPC codes, two special cases in code construction are considered, and the corresponding extensions of the decoder architecture are investigated.     

A self-testing 2-/spl mu/m CMOS chip set for FFT applications

A chip set for high-speed radix-2 fast Fourier transform (FFT) applications up to 512 points is described. The chip set comprises a (16+16)/spl times/(12+12)-bit complex number multiplier, and a 16-bit butterfly chip for data reordering, twiddle factor generation, and butterfly arithmetic. The chips have been implemented using a standard cell design methodology on a 2-/spl mu/m bulk CMOS process. Three chips implement a complex FFT butterfly with a throughput of 10 MHz, and are cascadable up to 512 points. The chips feature an offline self-testing capability.     

Novel modified min-sum decoding algorithm for low-density parity-check codes

The problem of improving the performance of min-sum decoding of low-density parity-check(LDPC)codes is considered in this paper.Based on rain-sum algorithm,a novel modified min-sum decoding algorithm for LDPC codes is proposed.The proposed algorithm modifies the variable node message in the iteration process by averaging the new message and previous message if their signs are different.Compared with the standard min-sum algorithm,the modification is achieved with only a small increase in complexity,but significantly improves decoding performance for both regular and irregular LDPC codes.Simulation results show that the performance of our modified decoding algorithm is very close to that of the standard sum-produet algorithm for moderate length LDPC codes.     

改进的离散字母表迭代译码算法研究

为了优化LDPC迭代译码性能和降低算法复杂度,提出了一种改进的基于Gallager A算法的2b离散字母表迭代译码算法。在每一轮迭代中,Tanner图上的校验节点与变量节点之间所传递的消息有1b表示符号值,另1b反映码字结构特性,其中变量节点更新规则是通过查表法来实现的。在二元对称信道下针对列重为3的规则LDPC码做了仿真实验,仿真结果表明该算法性能明显优于原算法,并且具有较低的复杂度。     

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.     

Performance analysis and code optimization of low densityparity-check codes on Rayleigh fading channels

A numerical method has been presented to determine the noise thresholds of low density parity-check (LDPC) codes that employ the message passing decoding algorithm on the additive white Gaussian noise (AWGN) channel. In this paper, we apply the technique to the uncorrelated flat Rayleigh fading channel. Using a nonlinear code optimization technique, we optimize irregular LDPC codes for such a channel. The thresholds of the optimized irregular LDPC codes are very close to the Shannon limit for this channel. For example, at rate one-half, the optimized irregular LDPC code has a threshold only 0.07 dB away from the capacity of the channel. Furthermore, we compare simulated performance of the optimized irregular LDPC codes and turbo codes on a land mobile channel, and the results indicate that at a block size of 3072, irregular LDPC codes can outperform turbo codes over a wide range of mobile speeds     

Power Reduction Techniques for LDPC Decoders

This paper investigates VLSI architectures for low-density parity-check (LDPC) decoders amenable to low- voltage and low-power operation. First, a highly-parallel decoder architecture with low routing overhead is described. Second, we propose an efficient method to detect early convergence of the iterative decoder and terminate the computations, thereby reducing dynamic power. We report on a bit-serial fully-parallel LDPC decoder fabricated in a 0.13-$mu{hbox{m}}$ CMOS process and show how the above techniques affect the power consumption. With early termination, the prototype is capable of decoding with 10.4 pJ/bit/iteration, while performing within 3 dB of the Shannon limit at a BER of 10$^{-5}$ and with 3.3 Gb/s total throughput. If operated from a 0.6 V supply, the energy consumption can be further reduced to 2.7 pJ/bit/iteration while maintaining a total throughput of 648 Mb/s, due to the highly-parallel architecture. To demonstrate the applicability of the proposed architecture for longer codes, we also report on a bit-serial fully-parallel decoder for the (2048, 1723) LDPC code in 10GBase-T standard synthesized with a 90-nm CMOS library.      

多元LDPC译码器设计

在多元低密度奇偶校验码(NB-LDPC)的扩展最小和译码算法（EMS）中,由于消息向量的递归计算和校验/变量节点信息之间的迭代交换,导致译码器存在较大延迟。针对此问题本文提出了一种新型译码器结构,它优化了校验节点更新单步运算单元,根据前向后向算法规则,以3路单步运算单元完成校验节点更新,硬件资源消耗略有增加,但所需时钟周期约降为一般结构的1/3;并采用全并行运算的变量节点信息更新单元,无需利用前向后向算法将更新过程分解为多个单步运算,消除了变量节点更新的递归计算,且具有低复杂度低延时等优点,并在现场可编程门阵列(FPGA)Xilinx Virtex-4 (XC4VLX200)平台上对一个GF(16)域上(480,360)的准循环多元LDPC码进行了综合仿真。仿真结果证明,设计的译码器在较小资源消耗条件下能成倍提高吞吐量。      

Transactions papers evaluation and design of irregular LDPC codes using ACE spectrum

The construction of finite-length irregular LDPC codes with low error floors is currently an attractive research problem. In particular, for the binary erasure channel (BEC), the problem is to find the elements of selected irregular LDPC code ensembles with the size of their minimum stopping set being maximized. Due to the lack of analytical solutions to this problem, a simple but powerful heuristic design algorithm, the approximate cycle extrinsic message degree (ACE) constrained design algorithm, has recently been proposed. Building upon the ACE metric associated with a cycle in a code graph, we introduce the ACE spectrum of LDPC codes as a useful tool for evaluation of codes from selected irregular LDPC code ensembles. Using the ACE spectrum, we generalize the ACE constrained design algorithm, making it more flexible and efficient. We justify the ACE spectrum approach through examples and simulation results.