arXiv:cs/0609089 · IEEE Information Theory Workshop (ITW)

Fast Min-Sum Algorithms for Decoding of LDPC over GF(q)

Xiaofei Huang, Suquan Ding, Zhixing Yang, Youshou Wu

Published Oct 1, 2006• 7 citations

Abstract

In this paper, we present a fast min-sum algorithm for decoding LDPC codes over GF(q). Our algorithm is different from the one presented by David Declercq and Marc Fossorier (2005) only at the way of speeding up the horizontal scan in the min-sum algorithm. The Declercq and Fossorier's algorithm speeds up the computation by reducing the number of configurations, while our algorithm uses the dynamic programming instead. Compared with the configuration reduction algorithm, the dynamic programming one is simpler at the design stage because it has less parameters to tune. Furthermore, it does not have the performance degradation problem caused by the configuration reduction because it searches the whole configuration space efficiently through dynamic programming. Both algorithms have the same level of complexity and use simple operations which are suitable for hardware implementations

DOI: 10.1109/itw2.2006.323764

Related papers

Fast Min-Sum Algorithms for Decoding of LDPC over GF(q

Xiaofei Huang, Suquan Ding, Zhixing Yang +1 more

Abstract — In this paper, we present a fast min-sum algorithm for decoding LDPC codes over GF(q). Our algorithm is different from the one presented by David Declercq and Marc Fossorier in [1] only at the way of speeding up the horizontal scan in the min-sum algorithm. The Declercq and Fossorier’s algorithm speeds up the computation by reducing the number of configurations, while our algorithm uses the dynamic programming instead. Compared with the configuration reduction algorithm, the dynamic programming one is simpler at the design stage because it has less parameters to tune. Furthermore, it does not have the performance degradation problem caused by the configuration reduction because it searches the whole configuration space efficiently through dynamic programming. Both algorithms have the same level of complexity and use simple operations which are suitable for hardware implementations. I.

Jan 1, 200612 citations

Single-Scan Min-Sum Algorithms for Fast Decoding of LDPC Codes

Xiaofei Huang

Many implementations for decoding LDPC codes are based on the (normalized/offset) min-sum algorithm due to its satisfactory performance and simplicity in operations. Usually, each iteration of the min-sum algorithm contains two scans, the horizontal scan and the vertical scan. This paper presents a single-scan version of the min-sum algorithm to speed up the decoding process. It can also reduce memory usage or wiring because it only needs the addressing from check nodes to variable nodes while the original min-sum algorithm requires that addressing plus the addressing from variable nodes to check nodes. To cut down memory usage or wiring further, another version of the single-scan min-sum algorithm is presented where the messages of the algorithm are represented by single bit values instead of using fixed point ones. The software implementation has shown that the single-scan min-sum algorithm is more than twice as fast as the original min-sum algorithm

arXiv:cs/0609090IEEE Information Theory Workshop (ITW)Oct 1, 20065 citations

Modified min-sum algorithm with threshold filtering for nonbinary LDPC codes over GF(q)

Yue Liu, Jun Ning, Jinhong Yuan

In this paper, we propose a scheme to reduce the computation complexity of min-sum (MS) algorithm for decoding of nonbinary low-density parity-check (LDPC) codes over GF(q). Previously, MS algorithm reduced the decoding complexity by lowering the size of the configuration set for each variable node through a sorting. In the proposed scheme, we modify the MS algorithm by minimizing the size of the configuration set for each variable node through a filtering. In the filtering, the reduction of the set size can be controlled by a preset threshold. This way we can reduce the complexity more efficiently. Simulation results show, compared to the previous EMS algorithm, the complexity of proposed scheme is reduced with a negligible degradation in the code performance.

International Symposium on Information Theory and its ApplicationsDec 1, 20082 citations

Single-Scan Min-Sum Algorithms for Fast Decoding of LDPC Codes

Xiaofei Huang

Abstract — Many implementations for decoding LDPC codes are based on the (normalized/offset) min-sum algorithm due to its satisfactory performance and simplicity in operations. Usually, each iteration of the min-sum algorithm contains two scans, the horizontal scan and the vertical scan. This paper presents a single-scan version of the min-sum algorithm to speed up the decoding process. It can also reduce memory usage or wiring because it only needs the addressing from check nodes to variable nodes while the original min-sum algorithm requires that addressing plus the addressing from variable nodes to check nodes. To cut down memory usage or wiring further, another version of the single-scan min-sum algorithm is presented where the messages of the algorithm are represented by single bit values instead of using fixed point ones. The software implementation has shown that the single-scan min-sum algorithm is more than twice as fast as the original min-sum algorithm. I.

Jan 1, 20068 citations

New algorithm for LDPC decoding over GF(q)

Christian Spagnol

This paper present a novel decoding scheme for low density parity check codes (LDPC) over GF(q). The scheme is a variation of the sum-product algorithm. The novel algorithm has a low complexity and reduces the number of look up table accesses necessary. Moreover, the algorithm does not compute division or multiplication, making it suitable for hardware implementation. The new algorithm has been compared with existing algorithms showing that both the BER performance and the speed of convergence are identical.

Irish Signals and Systems ConferenceJan 1, 20057 citations

Fast convergence algorithm for decoding of low density parity check codes

Jin Xie, Liuguo Yin, Ning Ge +1 more

Abstract: In this paper, a fast-convergence algorithm is proposed for the decoding of low-density parity-check (LDPC) codes. By putting more weight on the message update from check node to variable node in current iteration, the proposed method speeds up the decoding significantly. Simulation results show that compared with the standard layered min-sum decoding algorithm, the proposed scheme may reduce about 1/6 iteration numbers for LDPC codes used in DVB-S2, with hardware complexity overhead less than 2%. Key–Words: LDPC code, fast convergence decoding algorithm, layered decoding, min-sum algorithm, hardware implementation 1

WSEAS TRANSACTIONS on COMMUNICATIONS archiveJul 1, 20091 citation