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

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
arXivHTMLPDF

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

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•7 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 Applications•Dec 1, 2008•2 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 Conference•Jan 1, 2005•6 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

A Novel Approach for Efficient LDPC Decoding

B. LasyaSri, B. Ashok Raj, Lavadya Nirmala Devi

Recently, LDPC codes have been proved to be capable of closely approaching the channel capacity and hence they are strongly promoted in many international standards. Though decoding is simpler compared to Turbo code decoding, efficient decoding techniques for LDPC codes are in demand to make it further simpler. The theoretical performance of LDPC codes appears simple and close to Shannon’s capacity of channel, but the practical implementation is still challenging due to tasks like numerical inaccuracy, limited memory resources, etc. We investigate methods to reduce the complexity and make decoding simple while still keeping the loss in performance negligible. The aim of this paper is to reduce the complexity by simplification of the component decoders. For this, we analyze the min-sum algorithm and derive a theoretical framework. With this framework, we are able to modify the algorithm in order to achieve good performance for regular as well as irregular LDPC codes.

International journal of advance research, ideas and innovations in technology•May 15, 2017•0 citations

A Modified Min Sum Decoding Algorithm based on Approximation Enhancement for LDPC Codes

Nam Il Kim, Seung-Que Lee, Jin-Up Kim

Min-sum algorithm(MSA) and its modification are used in LDPC decoder implementations because of its error performance and low computation complexity. In this paper a modified min-sum LDPC decoding algorithm through approximation enhancement using the smallest three minimum values is presented. The proposed algorithm improves error performance and reduces decoder iterations. From the simulation results for 5G NR LDPC codes, we show that the proposed algorithm can achieve about 1.6dB improvement of FER compared to the min-sum decoding algorithm and provide about 10% reduction of the average iteration numbers compare to NMSA with optimum normalization factor.

International Conference on Information and Communication Technology Convergence (ICTC)•Oct 21, 2020•6 citations
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
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
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.
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.
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
Recently, LDPC codes have been proved to be capable of closely approaching the channel capacity and hence they are strongly promoted in many international standards. Though decoding is simpler compared to Turbo code decoding, efficient decoding techniques for LDPC codes are in demand to make it further simpler. The theoretical performance of LDPC codes appears simple and close to Shannon’s capacity of channel, but the practical implementation is still challenging due to tasks like numerical inaccuracy, limited memory resources, etc. We investigate methods to reduce the complexity and make decoding simple while still keeping the loss in performance negligible. The aim of this paper is to reduce the complexity by simplification of the component decoders. For this, we analyze the min-sum algorithm and derive a theoretical framework. With this framework, we are able to modify the algorithm in order to achieve good performance for regular as well as irregular LDPC codes.
Min-sum algorithm(MSA) and its modification are used in LDPC decoder implementations because of its error performance and low computation complexity. In this paper a modified min-sum LDPC decoding algorithm through approximation enhancement using the smallest three minimum values is presented. The proposed algorithm improves error performance and reduces decoder iterations. From the simulation results for 5G NR LDPC codes, we show that the proposed algorithm can achieve about 1.6dB improvement of FER compared to the min-sum decoding algorithm and provide about 10% reduction of the average iteration numbers compare to NMSA with optimum normalization factor.