IEEE Transactions on Circuits and Systems I Regular Papers

Flexible LDPC Decoder Design for Multigigabit-per-Second Applications

Chuan Zhang, Zhongfeng Wang, Jin Sha, Li Li, Jun Lin

Published Mar 24, 2009• 51 citations

Abstract

Low-density parity-check (LDPC) codes are one of the most promising error-correcting codes approaching Shannon capacity and have been adopted in many applications. However, the efficient implementation of high-throughput LDPC decoders adaptable for various channel conditions still remains challenging. In this paper, a low-complexity reconfigurable VLSI architecture for high-speed LDPC decoders is presented. Shift-LDPC codes are incorporated within the design and have shown not only comparable decoding performance to computer-generated random codes but also high hardware efficiency in high-speed applications. The single-minimum Min-Sum decoding scheme and the nonuniform quantization scheme are explored to reduce the complexity of computing core and the memory requirement. The well-known Benes network is employed to construct the configurable permutation network to support multiple shift-LDPC codes with various code parameters. The ASIC implementation results of an (8192, 7168) (4, 32)-regular shift-LDPC decoder demonstrate a maximum decoding throughput of 3.6 Gbits/s at 16 iterations, which outperforms the state-of-the-art design for high-speed flexible LDPC decoders by many times with even less hardware.

DOI: 10.1109/tcsi.2009.2018915

Related papers

Efficient decoder design for high-throughput LDPC decoding

Zhiqiang Cui, Zhongfeng Wang, Xinmiao Zhang +1 more

In this paper, a matrix permutation scheme is proposed to convert a generic QC-LDPC code to a shift-structured LDPC code. Thus, efficient VLSI architectures can be developed to achieve very high decoding throughput with low hardware complexity. Furthermore, novel implementation schemes for min-sum algorithm based column-layered decoding are presented. The proposed approaches provide very efficient ways for high-speed decoder design of generic QC-LDPC codes.

IEEE Asia Pacific Conference on Circuits and Systems (APCCAS)Nov 1, 200824 citations

A Network-Efficient Nonbinary QC-LDPC Decoder Architecture

Chuan Zhang, Keshab K. Parhi

Nonbinary low-density parity-check (LDPC) codes are of great interest due to their better performance cover binary ones when the code length is moderate. However, the cost of decoder implementation for these LDPC codes is still very high. In this paper, a low-complexity VLSI architecture for nonbinary LDPC decoders is presented. By exploiting the intrinsic shifting and symmetry properties of nonbinary quasi-cyclic LDPC (QC-LDPC) codes, significant reduction of memory size and routing complexity can be achieved. These unique features lead to two network-efficient decoder architectures for Class-I and Class-II nonbinary QC-LDPC codes, respectively. Comparison results with the state-of-the-art designs show that for the code example of the 64-ary (1260, 630) rate-0.5 Class-I code, the proposed scheme can save up to 70.6% hardware required by switch network, which demonstrates the efficiency of the proposed technique. The proposed design for the 32-ary (992, 496) rate-0.5 Class-II code can achieve a 93.8% switch network complexity reduction compared with conventional approaches. Furthermore, with the help of a generator for possible solution sequences, both forward and backward steps can be eliminated to offer processing convenience of check node unit (CNU) blocks. Results show the proposed 32-ary (992, 496) rate-0.5 Class-II decoder can achieve 4.47 Mb/s decoding throughput at a clock speed of 150 MHz.

IEEE Transactions on Circuits and Systems I Regular PapersJan 17, 201212 citations

Low-Complexity High-Speed Decoder Design for Quasi-Cyclic LDPC Codes

Zhongfeng Wang, Zhiqiang Cui

This paper studies low-complexity high-speed decoder architectures for quasi-cyclic low density parity check (QC-LDPC) codes. Algorithmic transformation and architectural level optimization are incorporated to reduce the critical path. Enhanced partially parallel decoding architectures are proposed to linearly increase the throughput of conventional partially parallel decoders through introducing a small percentage of extra hardware. Based on the proposed architectures, a (8176, 7154) Euclidian geometry-based QC-LDPC code decoder is implemented on Xilinx field programmable gate array (FPGA) Virtex-II 6000, where an efficient nonuniform quantization scheme is employed to reduce the size of memories storing soft messages. FPGA implementation results show that the proposed decoder can achieve a maximum (source data) decoding throughput of 172 Mb/s at 15 iterations

IEEE Transactions on Very Large Scale Integration (VLSI) SystemsJan 1, 2007155 citations

Design and implementation of decoders for error correction in high-speed communication systems.

Joan Marc Català Pérez

This thesis is focused on the design and implementation of binary low-density parity-check (LDPC) code decoders for high-speed modern communication systems. The basic of LDPC codes and the performance and bottlenecks, in terms of complexity and hardware efficiency, of the main soft-decision and hard-decision decoding algorithms (such as Min-Sum, Optimized 2-bit Min-Sum and Reliability-based iterative Majority-Logic) are analyzed. The complexity and performance of those algorithms are improved to allow efficient hardware architectures.\n\nA new decoding algorithm called One-Minimum Min-Sum is proposed. It reduces considerably the complexity of the check node update equations of the Min-Sum algorithm. The second minimum is estimated from the first minimum value by a means of a linear approximation that allows a dynamic adjustment. The Optimized 2-bit Min-Sum algorithm is modified to initialize it with the complete LLR values and to introduce the extrinsic information in the messages sent from the variable nodes. Its variable node equation is reformulated to reduce its complexity. Both algorithms were tested for the (2048,1723) RS-based LDPC code and (16129,15372) LDPC code using an FPGA-based hardware emulator. They exhibit BER performance very close to Min-Sum algorithm and do not introduce early error-floor. \n\nIn order to show the hardware advantages of the proposed algorithms, hardware decoders were implemented in a 90 nm CMOS process and FPGA devices based on two types of architectures: full-parallel and partial-parallel one with horizontal layered schedule. The results show that the decoders are more area-time efficient than other published decoders and that the low-complexity of the Modified Optimized 2-bit Min-Sum allows the implementation of 10 Gbps decoders in current FPGA devices. \n\nFinally, a new hard-decision decoding algorithm, the Historical-Extrinsic Reliability-Based Iterative Decoder, is presented. This algorithm introduces the new idea of considering hard-decision votes as soft-decision to compute the extrinsic information of previous iterations. It is suitable for high-rate codes and improves the BER performance of the previous RBI-MLGD algorithms, with similar complexity.

Jul 7, 20170 citations

Reduced-complexity column-layered decoding and implementation for LDPC codes

Z. Cui, Zhirui Wang Zhirui Wang, Xiaofang Zhang

Layered decoding is well appreciated in low-density parity-check (LDPC) decoder implementation since it can achieve effectively high decoding throughput with low computation complexity. This work, for the first time, addresses low-complexity column-layered decoding schemes and very-large-scale integration (VLSI) architectures for multi-Gb/s applications. At first, the min-sum algorithm is incorporated into the column-layered decoding. Then algorithmic transformations and judicious approximations are explored to minimise the overall computation complexity. Compared to the original column-layered decoding, the new approach can reduce the computation complexity in check node processing for high-rate LDPC codes by up to 90% while maintaining the fast convergence speed of layered decoding. Furthermore, a relaxed pipelining scheme is presented to enable very high clock speed for VLSI implementation. Equipped with these new techniques, an efficient decoder architecture for quasi-cyclic LDPC codes is developed and implemented with 0.13 µm VLSI implementation technology. It is shown that a decoding throughput of nearly 4 Gb/s at a maximum of 10 iterations can be achieved for a (4096, 3584) LDPC code. Hence, this work has facilitated practical applications of column-layered decoding and particularly made it very attractive in high-speed, high-rate LDPC decoder implementation.

arXiv:1204.2577IET CommunicationsOct 14, 201140 citations

Parallel algorithms and architectures for LDPC Decoding

Gabriel Falcão

Low-Density Parity-Check (LDPC) codes have recaptured the attention of the scientific community a few years after Turbo codes were invented in the early nineties. Originally proposed in the 1960s at MIT by R. Gallager, LDPC codes represent powerful error correcting codes that allow working very close to the Shannon limit and achieve excellent Bit Error Rate (BER) due to computationally intensive algorithms on the decoder side of the system. Advances in microelectronics introduced small process technologies that allowed developing complex designs incorporating a high number of transistors in Very Large Scale Integration (VLSI) systems. Recently, these processes have been used to develop architectures able of performing LDPC decoding in real-time and delivering considerably high throughputs. Mainly for these reasons and naturally because the patent has expired, they have been adopted by modern communication standards which triggered their popularity, showing how actual they are. Due to the increase of transistor density in VLSI systems, and also to the fact that recently processing speed has risen faster than bandwidth, power and memory walls have created a new paradigm in computer architectures: rather than just increasing the frequency of operation supported by smaller process designs, the introduction of multiple cores on a single chip has become the new trend to provide augmented computational power. This thesis proposes new approaches for these computationally intensive algorithms, by performing parallel LDPC decoding based on ubiquitous multi-core architectures and achieves efficient throughputs that compare well with dedicated VLSI systems. We extensively address the challenges faced in the investigation and development of these programmable solutions, with focus mainly given on flexibility and scalability of the proposed algorithms, throughput and BER performance, and general efficiency of the programmable solutions here presented, that also achieve results more than an order of magnitude superior to those obtained with conventional CPUs. Furthermore, the investigation herein described follows a methodology that analyzes in detail the computational complexity of these decoding algorithms in order to propose strategies to accelerate their processingwhich, if conveniently transposed to other areas of computer science, can demonstrate that in this new multi-core era we may be in the presence of valid alternatives to non-reprogrammable dedicated VLSI hardware that requires non-recurring engineering.

Dec 6, 20108 citations