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

International Symposium on Turbo Codes and Iterative Information Processing

Average min-sum decoding of LDPC codes

Nathan Axvig, Deanna Dreher, Katherine Morrison, Eric T. Psota, Lance C. Pérez, Judy L. Walker

Published Sep 1, 2008• 8 citations
Publisher

Abstract

Simulations have shown that the outputs of min-sum (MS) decoding generally behave in one of two ways: either the output vector eventually stabilizes at a codeword or it eventually cycles through a finite set of vectors that may include both codewords and non-codewords. The latter behavior has significantly contributed to the difficulty in studying the performance of this decoder. To overcome this problem, a new decoder, average min-sum (AMS), is proposed; this decoder outputs the average of the MS output vectors over a finite set of iterations. Simulations comparing MS, AMS, linear programming (LP) decoding, and maximum likelihood (ML) decoding are presented, illustrating the relative performances of each of these decoders. In general, MS and AMS have comparable word error rates; however, in the simulation of a code with large block length, AMS has a significantly lower bit error rate. Finally, AMS pseudocodewords are introduced and their relationship to graph cover and LP pseudocodewords is explored, with particular focus on the AMS pseudocodewords of regular LDPC codes and cycle codes.

DOI
10.1109/turbocoding.2008.4658725

Related papers

Towards universal cover decoding

Nathan Axvig, Deanna Dreher, Katherine Morrison +3 more

In this paper, the non-codeword errors was analyzed that occur during parallel, iterative decoding with the min-sum decoder. Recently, work has been done relating the min-sum decoder to the linear programming (LP) decoder via graph covers. The LP decoder recasts the problem of decoding as an optimization problem whose feasible set is a polytope defined by the parity-check matrix of a code. It was shown that LP decoding can be realized as a decoder operating on graph covers.

International Symposium on Information Theory and its Applications•Dec 1, 2008•2 citations

TS-LDPC analog decoding based on the Min-Sum algorithm

Alireza Rabbani Abolfazli, Yousef R. Shayan, Glenn E. R. Cowan

It has been shown that Min-Sum (MS) algorithms have low complexity in the implementation of analog VLSI decoders compared to the Sum-Product (SP) algorithm. Moreover, Turbo-structured LDPC (TS-LDPC) codes are known to have lower error floor than random LDPC codes. In this paper, Min-Sum and Min-Sum with correction factor algorithms are reviewed and adapted with TS-LDPC codes for future analog VLSI implementation. Simulation results show that the error performance of the Min-Sum algorithm is comparable with the Sum-Product algorithm for the same block length. This means that the lower error floor property of TS-LDPC codes is preserved when MS algorithms are used. Moreover, analog decoder implementation of TS-LDPC codes is studied. To test the suitability of the MS algorithm based TS-LDPC decoder some analog impairments such as mismatch, leakage and noise are considered in the decoding procedure of TS-LDPC codes. In each case, it is shown that the degradation of the error performance of TS-LDPC codes due to analog impairments is negligible. Therefore, it can be concluded that the analog decoder of the TS-LDPC code using MS algorithm is fairly robust against analog imperfections and may be considered in future implementation of analog VLSI decoder.

Biennial Symposium on Communications•May 1, 2012•2 citations

Optimized Min-Sum decoding algorithm for Low Density PC codes

Dewan Siam Shafiullah, Mohammad Rakibul Islam, Muhammad Mostafa Amir Faisal +1 more

Low Density Parity Check (LDPC) approaches Shannon -limit performance for binary field and long code lengths. However performance of binary LDPC code is degraded when the code word length is small. An optimized min-sum algorithm for LDPC code is proposed in this paper. In this algorithm unlike other decoding methods an optimization factor has been introduced in both check node and bit node of the Min-sum algorithm. The optimization factor is obtained before decoding program and the same factor is multiplied twice in one cycle. So the increased complexity is fairly low. Simulation results show that the proposed Optimized Min-Sum decoding algorithm performs very close to the Sum-Product decoding, while preserving the main features of the Min-Sum decoding, that is low complexity and independence with respect to noise variance estimation errors.

International Conference on Advanced Communication Technology•Jan 1, 2012•5 citations

Stability analysis of an improved min-sum decoder

Mahdi Ramezani, R. Yazdani, Masoud Ardakani

It has been shown that under min-sum (MS) decoding, scaling the messages at the output of check nodes can improve the performance of regular low-density parity-check (LDPC) codes. However, for irregular codes designed for the sum-product decoder, linear scaling can hinder the performance. The problem of code design for MS and linear scaling min-sum (LSMS) decoders have been recently investigated. It is shown that the gap to the capacity for LSMS codes is better than MS codes, but compared to sum-product codes the gap is still considerable. In this letter, a modified MS decoding is proposed and studied. We use the stability analysis of density evolution to show that the proposed method allows for a larger fraction of edges connected to degree-2 variable nodes than LSMS codes. Finally, by designing codes based on the modified method, we show that compared to MS and LSMS codes, a smaller gap to the capacity can indeed be achieved while the complexity of decoding remains essentially the same.

IEEE Communications Letters•Aug 1, 2008•0 citations

Optimized Min-Sum Decoding Algorithm for Low Density Parity Check Codes

Mohammad Rakibul Islam, Dewan Siam Shafiullah, Muhammad Mostafa +2 more

Abstract ― Low Density Parity Check (LDPC) code approaches Shannon–limit performance for binary field and long code lengths. However, performance of binary LDPC code is degraded when the code word length is small. An optimized min-sum algorithm for LDPC code is proposed in this paper. In this algorithm unlike other decoding methods, an optimization factor has been introduced in both check node and bit node of the Min-sum algorithm. The optimization factor is obtained before decoding program, and the same factor is multiplied twice in one cycle. So the increased complexity is fairly low. Simulation results show that the proposed Optimized Min-Sum decoding algorithm performs very close to the Sum-Product decoding while preserving the main features of the Min-Sum decoding, that is low complexity and independence with respect to noise variance estimation errors.

•Oct 31, 2015•2 citations

Sign-Preserving Min-Sum Decoders

Franklin Cochachin, Emmanuel Boutillon, David Declercq

This paper proposes a new finite precision iterative decoder for low-density parity-check (LDPC) codes. The proposed decoder, named Sign-Preserving Min-Sum (SP-MS), significantly improves the decoding performance compared to the classical Offset Min-Sum (OMS) decoder when messages are quantized on$q=2$, 3, or 4 bits. The particularity of the SP-MS decoder is that messages cannot take the 0 value, and can fully benefit from the$q$bits of precision. The optimization of the SP-MS decoder is investigated in the asymptotic limit of the code length using density evolution (DE). Our study shows that 3-bit SP-MS decoders can achieve the same error-correcting performance as 5-bit OMS decoders, and 2-bit SP-MS decoders outperform 3-bit OMS decoders. The finite-length simulations confirm the conclusions of the DE analysis for several LDPC codes. Our SP-MS decoder shows a signal-to-noise ratio (SNR) gain up to 0.43 dB, with a memory/wire reduction of up to 40%, compared to the OMS decoder. Moreover, the SP-MS decoder converges faster and uses fewer iterations than the OMS decoder, with an improvement of up to 83.3% of the average decoding throughput. On an FPGA, the SP-MS decoder reduces resource utilization by up to 56% compared to the OMS decoder.

IEEE Transactions on Communications•Jul 26, 2021•2 citations
Simulations have shown that the outputs of min-sum (MS) decoding generally behave in one of two ways: either the output vector eventually stabilizes at a codeword or it eventually cycles through a finite set of vectors that may include both codewords and non-codewords. The latter behavior has significantly contributed to the difficulty in studying the performance of this decoder. To overcome this problem, a new decoder, average min-sum (AMS), is proposed; this decoder outputs the average of the MS output vectors over a finite set of iterations. Simulations comparing MS, AMS, linear programming (LP) decoding, and maximum likelihood (ML) decoding are presented, illustrating the relative performances of each of these decoders. In general, MS and AMS have comparable word error rates; however, in the simulation of a code with large block length, AMS has a significantly lower bit error rate. Finally, AMS pseudocodewords are introduced and their relationship to graph cover and LP pseudocodewords is explored, with particular focus on the AMS pseudocodewords of regular LDPC codes and cycle codes.
It has been shown that Min-Sum (MS) algorithms have low complexity in the implementation of analog VLSI decoders compared to the Sum-Product (SP) algorithm. Moreover, Turbo-structured LDPC (TS-LDPC) codes are known to have lower error floor than random LDPC codes. In this paper, Min-Sum and Min-Sum with correction factor algorithms are reviewed and adapted with TS-LDPC codes for future analog VLSI implementation. Simulation results show that the error performance of the Min-Sum algorithm is comparable with the Sum-Product algorithm for the same block length. This means that the lower error floor property of TS-LDPC codes is preserved when MS algorithms are used. Moreover, analog decoder implementation of TS-LDPC codes is studied. To test the suitability of the MS algorithm based TS-LDPC decoder some analog impairments such as mismatch, leakage and noise are considered in the decoding procedure of TS-LDPC codes. In each case, it is shown that the degradation of the error performance of TS-LDPC codes due to analog impairments is negligible. Therefore, it can be concluded that the analog decoder of the TS-LDPC code using MS algorithm is fairly robust against analog imperfections and may be considered in future implementation of analog VLSI decoder.
Low Density Parity Check (LDPC) approaches Shannon -limit performance for binary field and long code lengths. However performance of binary LDPC code is degraded when the code word length is small. An optimized min-sum algorithm for LDPC code is proposed in this paper. In this algorithm unlike other decoding methods an optimization factor has been introduced in both check node and bit node of the Min-sum algorithm. The optimization factor is obtained before decoding program and the same factor is multiplied twice in one cycle. So the increased complexity is fairly low. Simulation results show that the proposed Optimized Min-Sum decoding algorithm performs very close to the Sum-Product decoding, while preserving the main features of the Min-Sum decoding, that is low complexity and independence with respect to noise variance estimation errors.
It has been shown that under min-sum (MS) decoding, scaling the messages at the output of check nodes can improve the performance of regular low-density parity-check (LDPC) codes. However, for irregular codes designed for the sum-product decoder, linear scaling can hinder the performance. The problem of code design for MS and linear scaling min-sum (LSMS) decoders have been recently investigated. It is shown that the gap to the capacity for LSMS codes is better than MS codes, but compared to sum-product codes the gap is still considerable. In this letter, a modified MS decoding is proposed and studied. We use the stability analysis of density evolution to show that the proposed method allows for a larger fraction of edges connected to degree-2 variable nodes than LSMS codes. Finally, by designing codes based on the modified method, we show that compared to MS and LSMS codes, a smaller gap to the capacity can indeed be achieved while the complexity of decoding remains essentially the same.
Abstract ― Low Density Parity Check (LDPC) code approaches Shannon–limit performance for binary field and long code lengths. However, performance of binary LDPC code is degraded when the code word length is small. An optimized min-sum algorithm for LDPC code is proposed in this paper. In this algorithm unlike other decoding methods, an optimization factor has been introduced in both check node and bit node of the Min-sum algorithm. The optimization factor is obtained before decoding program, and the same factor is multiplied twice in one cycle. So the increased complexity is fairly low. Simulation results show that the proposed Optimized Min-Sum decoding algorithm performs very close to the Sum-Product decoding while preserving the main features of the Min-Sum decoding, that is low complexity and independence with respect to noise variance estimation errors.
This paper proposes a new finite precision iterative decoder for low-density parity-check (LDPC) codes. The proposed decoder, named Sign-Preserving Min-Sum (SP-MS), significantly improves the decoding performance compared to the classical Offset Min-Sum (OMS) decoder when messages are quantized onq=2q=2q=2, 3, or 4 bits. The particularity of the SP-MS decoder is that messages cannot take the 0 value, and can fully benefit from theqqqbits of precision. The optimization of the SP-MS decoder is investigated in the asymptotic limit of the code length using density evolution (DE). Our study shows that 3-bit SP-MS decoders can achieve the same error-correcting performance as 5-bit OMS decoders, and 2-bit SP-MS decoders outperform 3-bit OMS decoders. The finite-length simulations confirm the conclusions of the DE analysis for several LDPC codes. Our SP-MS decoder shows a signal-to-noise ratio (SNR) gain up to 0.43 dB, with a memory/wire reduction of up to 40%, compared to the OMS decoder. Moreover, the SP-MS decoder converges faster and uses fewer iterations than the OMS decoder, with an improvement of up to 83.3% of the average decoding throughput. On an FPGA, the SP-MS decoder reduces resource utilization by up to 56% compared to the OMS decoder.