Asilomar Conference on Signals, Systems and Computers (ACSSC)

Decoding of Quasi-cyclic LDPC Codes Using an On-the-Fly Computation

Kiran Gunnam, Gwan Choi, Weihuang Wang, Euncheol Kim, Mark B. Yeary

Published Jan 1, 2006• 26 citations

Abstract

The implementation complexity of the decoder for low-density parity-check codes (LDPC) is dictated by memory and interconnect requirements. We propose new LDPC decoder architectures that reduce the need of message passing memory by 80% (for standard message passing)-55%(for layered decoding) and the router requirements by more than 50%. These novel architectures are based on scheduling of computation that results in "on the fly computation" of variable node and check node reliability messages. These architectures are targeted for quasi- cyclic LDPC codes such as array LDPC codes (regular QC-LDPC) and block LDPC codes (irregular QC-LDPC). FPGA and ASIC implementation results show substantial gains when compared to the existing work in the literature.

DOI: 10.1109/acssc.2006.354944

Related papers

A High Throughput H-QC LDPC Decoder

Yi-Hsing Chien, Mong‐Kai Ku

In this paper, design of a high throughput low-density parity-check (LDPC) decoder using overlapped message passing scheduling algorithm is presented. Regular hierarchical quasi-cyclic (H-QC) LDPC code is used in this design to provide good coding performance at long code length. The two-level regular H-QC LDPC code matrix structure is exploited to parallelize the row and column decoding operations. Our scheduling algorithm re-arranges these operations across iteration boundaries to avoid memory access conflicts. The memory requirement is reduced by half compared to pipelined decoders without scheduling. A (12288, 6144) LDPC decoder implemented in FPGA achieves 298 Mbps throughput performance.

IEEE International Symposium on Circuits and Systems proceedingsMay 1, 200712 citations

An Efficient General-Purpose Quasi-Cyclic LDPC Decoder Architecture

Shunliang Mei

This paper presents an efficient general-purpose QC-LDPC decoder architecture by combining hardware with software.The proposed architecture can be applied to regular and irregular QC-LDPC codes of various rates,lengths and parity-check matrix structures,and supports min-sum approximation decoding algorithms and realizes different message passing scheduling strategies.Some complicated message update is implemented by a hardware accelerator,thus the decoding throughput is improved.According to the quasi-cyclic structure of the parity-check matrix,the messages are stored and processed by blocks in decoding.Parallel message processing can also be realized with a small increase in implementation complexity.

Computer Engineering and ScienceJan 1, 20080 citations

A Fast-Convergence Decoding Method and Memory-Efficient VLSI Decoder Architecture for Irregular LDPC Codes in the IEEE 802.16e Standards

Yeong-Luh Ueng, Chung-Chao Cheng

In this paper, we propose a modified iterative decoding algorithm to decode a special class of quasi-cyclic low- density parity-check (QC-LDPC) codes such as QC-LDPC codes used in the IEEE 802.16e standards. The proposed decoding is implemented by serially decoding block codes with identical parity-check matrix H1derived from the parity-check matrix H of the QC-LDPC codes. The dimensions of H1are much smaller than those of H. Extrinsic values can be passed among these block codes since the code bits of these block codes are overlapped. Hence, the proposed decoding can reduce the number of iterations required by up to forty percent without error performance loss as compared to the conventional message- passing decoding algorithm. A partially-parallel very large-scale integration (VLSI) architecture is proposed to implement such a decoding algorithm. The proposed VLSI decoder can fully take advantage of the proposed decoding to increase its throughput. In addition, the proposed decoder only needs to store check-to- variable messages and hence is memory efficient.

IEEE Vehicular Technology ConferenceSep 1, 200715 citations

Efficient Highly-Parallel Decoder Architecture for Quasi-Cyclic Low-Density Parity-Check Codes

Daesun Oh, Keshab K. Parhi

In this paper, the authors propose an efficient highly-parallel decoder architecture using partially overlapped decoding scheme for quasi-cyclic (QC) low-density parity-check (LDPC) codes, which leads to reduction in hardware complexity and power consumption. Generally, due to the regularly structured parity-check matrix H of QC LDPC codes, the message updating computations in the check node unit (CNU) and the variable node unit (VNU) can be efficiently overlapped, which increases the decoding throughput by maximizing the hardware utilization efficiency (HUE). However, the partially overlapped decoding scheme cannot be used to design a highly-parallel decoding architecture for high-throughput applications. For (3, 5)-regular QC LDPC codes, our proposed method could reduce the hardware complexity by approximately 33% for the CNU and 20% for the VNU in the highly-parallel decoder architecture without any performance degradation. In addition, the power consumption can be minimized by reducing the total number of memory accesses for updated messages.

IEEE International Symposium on Circuits and Systems proceedingsMay 1, 200714 citations

Low-complexity architectures for reliability-based message-passing non-binary LDPC decoding

Xinmiao Zhang, Fang Cai

When the code is not long, non-binary low-density parity- check (NB-LDPC) codes can achieve better error-correcting performance than binary LDPC codes at the cost of higher decoding complexity. The recently developed iterative reliability-based majority-logic NB- LDPC decoding can achieve better performance-complexity tradeoffs than previous algorithms. Many existing NB-LDPC code construction schemes lead to quasi-cyclic or cyclic codes. In this paper, efficient low- complexity NB-LDPC decoder architectures are developed for these two types of codes based on the newly proposed iterative hard reliability-based majority-logic decoding (IHRB-MLGD). Particularly, novel schemes are designed to keep a small proportion of messages in order to reduce the memory requirement without causing noticeable performance loss. Moreover, a shift-message structure is proposed by using memories concatenated with variable node units to enable efficient partial-parallel decoding for cyclic NB-LDPC codes. Compared to previous decoders based on the Min-max algorithm, the proposed IHRB-MLGD decoder architectures can achieve tens of times higher efficiency for codes with similar length and rate with moderate coding gain loss.

IEEE International Symposium on Circuits and Systems proceedingsMay 1, 20118 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