Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

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

Xiaofei Huang

Published Jan 1, 2006• 8 citations
OpenAlex

Abstract

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.

Related papers

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/0609090•IEEE Information Theory Workshop (ITW)•Oct 1, 2006•5 citations

Single-Step Adaptive Offset Min-Sum Algorithm for Decoding LDPC Codes

Xiaoju Lin, Gansuren Baasantseren, Hae-Kee Lee +1 more

Low-density parity-check (LDPC) codes with belief-propagation (BP) algorithm achieve a remarkable performance close to the Shannon limit at reasonable decoding complexity. Conventionally, each iteration in decoding process contains two steps, the horizontal step and the vertical step. In this paper, an efficient implementation of the adaptive offset min-sum (AOMS) algorithm for decoding LDPC codes using the single-step method is proposed. Furthermore, the performances of the AOMS algorithm compared with belief-propagation (BP) algorithm are investigated. The algorithms using the single-step method reduce the implementation complexity, speed up the decoding process and have better efficiency in terms of memory requirements.

The Transactions of The Korean Institute of Electrical Engineers•Jan 1, 2010•0 citations

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, 2006•12 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 archive•Jul 1, 2009•1 citation

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

Xiaofei Huang, Suquan Ding, Zhixing Yang +1 more

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

arXiv:cs/0609089•IEEE Information Theory Workshop (ITW)•Oct 1, 2006•7 citations

A Relaxed Min-Sum LDPC Decoder With Simplified Check Nodes

Saied Hemati, François Leduc-Primeau, Warren J. Gross

This letter presents a heuristic technique for simplifying the parity-check node operation in a relaxed min-sum iterative decoder. The proposed decoder eliminates the second-minimum computation in check nodes, which allows broadcasting the same output to all neighboring variable nodes to alleviate routing problem in VLSI implementations of low-density parity check (LDPC) decoders. The second-minimum, when required, is emulated by adding an offset to the first-minimum. The proposed relaxed decoder also uses a relaxation factor equal to 0.5 to simplify variable nodes. Simulation results for two LDPC codes show the proposed decoding algorithm with only 4-bit quantization closely matches the performance of floating-point normalized/offset min-sum and sum-product decoders in the waterfall region.

IEEE Communications Letters•Jan 12, 2016•25 citations
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.
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
Low-density parity-check (LDPC) codes with belief-propagation (BP) algorithm achieve a remarkable performance close to the Shannon limit at reasonable decoding complexity. Conventionally, each iteration in decoding process contains two steps, the horizontal step and the vertical step. In this paper, an efficient implementation of the adaptive offset min-sum (AOMS) algorithm for decoding LDPC codes using the single-step method is proposed. Furthermore, the performances of the AOMS algorithm compared with belief-propagation (BP) algorithm are investigated. The algorithms using the single-step method reduce the implementation complexity, speed up the decoding process and have better efficiency in terms of memory requirements.
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.
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
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
This letter presents a heuristic technique for simplifying the parity-check node operation in a relaxed min-sum iterative decoder. The proposed decoder eliminates the second-minimum computation in check nodes, which allows broadcasting the same output to all neighboring variable nodes to alleviate routing problem in VLSI implementations of low-density parity check (LDPC) decoders. The second-minimum, when required, is emulated by adding an offset to the first-minimum. The proposed relaxed decoder also uses a relaxation factor equal to 0.5 to simplify variable nodes. Simulation results for two LDPC codes show the proposed decoding algorithm with only 4-bit quantization closely matches the performance of floating-point normalized/offset min-sum and sum-product decoders in the waterfall region.