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

IEEE Communications Letters

Stability analysis of an improved min-sum decoder

Mahdi Ramezani, R. Yazdani, Masoud Ardakani

Published Aug 1, 2008• 0 citations
Publisher

Abstract

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.

DOI
10.1109/lcomm.2008.080597

Related papers

Degree Optimization and Stability Condition for the Min-Sum Decoder

Kapil Bhattad, Vishwambhar Rathi, Rudiger L. Urbanke

The min-sum (MS) algorithm is arguably the second most fundamental algorithm in the realm of message passing due to its optimality (for a tree code) with respect to theblockerrorprobability [1]. There also seems to be a fundamental relationship of MS decoding with the linear programming decoder [2]. Despite its importance, its fundamental properties have not nearly been studied as well as those of the sum-product (also known as BP) algorithm. We address two questions related to the MS rule. First, we characterize the stability condition under MS decoding. It turns out to be essentially the same condition as under BP decoding. Second, we perform a degree distribution optimization. Contrary to the case of BP decoding, under MS decoding the thresholds of the best degree distributions for standard irregular LDPC ensembles are significantly bounded away from the Shannon threshold. More precisely, on the AWGN channel, for the best codes that we find, the gap to capacity is 1 dB for a rate 0.3 code and it is 0.4 dB when the rate is 0.9 (the gap decreases monotonically as we increase the rate). We also used the optimization procedure to design codes for modified MS algorithm where the output of the check node is scaled by a constant 1/alpha. For alpha = 1.25, we observed that the gap to capacity was lesser for the modified MS algorithm when compared with the MS algorithm. However, it was still quite large, varying from 0.75 dB to 0.2 dB for rates between 0.3 and 0.9. We conclude by posing what we consider to be the most important open questions related to the MS algorithm.

arXiv:0705.1345•IEEE Information Theory Workshop (ITW)•Sep 1, 2007•6 citations

Modified Normalized Min-Sum decoding of LDPC codes

Rong Chen, Yiming Wang

In this paper, we present an improvement on the normalized min-sum (NMS) decoding algorithm for low density parity check codes. The modified NMS (M-NMS) algorithm introduces a more efficient adjustment for check node update computation. Taking the sub-minimum value among extrinsic information from the variable nodes into consideration, we make the correction factor varies with different iterations. Results show that, compared with standard min-sum (MS) and NMS decoding algorithms, the proposed method not only offers a better performance but also achieves a lower error floor in the high SNR region.

•Oct 1, 2008•3 citations

Simplified 2-Dimensional Scaled Min-Sum Algorithm for LDPC Decoder

Keol Cho, Wangheon Lee, Ki‐Seok Chung

Among various decoding algorithms of low-density parity-check (LDPC) codes, the minsum (MS) algorithm and its modified algorithms are widely adopted because of their computational simplicity compared to the sum-product (SP) algorithm with slight loss of decoding performance.In the MS algorithm, the magnitude of the output message from a check node (CN) processing unit is decided by either the smallest or the next smallest input message which are denoted as min1 and min2, respectively.It has been shown that multiplying a scaling factor to the output of CN message will improve the decoding performance.Further, Zhong et al. have shown that multiplying different scaling factors (called a 2-dimensional scaling) to min1 and min2 much increases the performance of the LDPC decoder.In this paper, the simplified 2-dimensional scaled (S2DS) MS algorithm is proposed.In the proposed algorithm, we figure out a pair of the most efficient scaling factors which multiplications can be replaced with combinations of addition and shift operations.Furthermore, one scaling operation is approximated by the difference between min1 and min2.The simulation results show that S2DS achieves the error correcting performance which is close to or outperforms the SP algorithm regardless of coding rates, and its computational complexity is the lowest comparing to modified versions of MS algorithms.

Journal of Electrical Engineering and Technology•May 1, 2017•5 citations

Difference to sum ratio factor based min-sum decoding for Low Density Parity Check Codes

Mohammad Rakibul Islam, Khandaker Sultan Mahmood, Md. Moshiur Rahman Farazi +3 more

Low Density Parity Check Codes (LDPC) give groundbreaking performance which is known to approach Shannon's limits for sufficiently large block length. Historically and recently, LDPC have been known to give superior performance than concatenated coding. In the following paper, a proposal to modify the standard Min-Sum (MS) algorithm for decoding LDPC codes is presented. This is done by introduction of a difference to sum ratio factor, κ in the check to bit node updating process. The algorithm is further extended by implementing hard decision of the Bit-Flipping (BF) algorithm over the soft decision of MS algorithm. Simulation results demonstrate that the proposed algorithms are effective in imparting a better performance in terms of a lower bit error rate (BER) at medium to high signal to noise ratio (SNR) when compared to the traditional MS algorithm while adding fair amount of complexity.

Computing, Communications and IoT Applications (ComComAp)•Jan 1, 2012•1 citation

Algorithm Design of Quantized Min-Sum Decoder for Low-density Parity-Check (LDPC) Codes Based on Density Evolution

Xinmei Wang

Design of quantized Min-Sum decoder for low-density parity-check (LDPC) codes is very important for the application of LDPC codes.Based on the theory of density evolution,the paper proposes an algorithm to optimize the uniform or ununiform quantized Min-Sum decoder for regular or irregular LDPC codes.Compared with the continuous Sum-Product decoder,the proposed quantized decoder can reduce computational cost with little performance degradation, involving only integer addition calculations.

•Jan 1, 2005•0 citations

An improved normalized min-sum algorithm for LDPC codes

Jinlei Chen, Yan Zhang, Ruiyi Sun

An improved normalized min-sum (IN-MS) algorithm is proposed for decoding low-density parity-check (LDPC) codes. In this algorithm, two normalized factors are used in check node computing, one for the minimum data and another for the second minimum data, and this algorithm achieves a better approximation to the BP algorithm. Simulation results show that the decoding performance of IN-MS algorithm is better than that of the normalized min-sum (NMS) algorithm.

IEEE/ACIS International Conference on Computer and Information Science (ICIS)•Jun 1, 2013•9 citations
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.
The min-sum (MS) algorithm is arguably the second most fundamental algorithm in the realm of message passing due to its optimality (for a tree code) with respect to theblockerrorprobability [1]. There also seems to be a fundamental relationship of MS decoding with the linear programming decoder [2]. Despite its importance, its fundamental properties have not nearly been studied as well as those of the sum-product (also known as BP) algorithm. We address two questions related to the MS rule. First, we characterize the stability condition under MS decoding. It turns out to be essentially the same condition as under BP decoding. Second, we perform a degree distribution optimization. Contrary to the case of BP decoding, under MS decoding the thresholds of the best degree distributions for standard irregular LDPC ensembles are significantly bounded away from the Shannon threshold. More precisely, on the AWGN channel, for the best codes that we find, the gap to capacity is 1 dB for a rate 0.3 code and it is 0.4 dB when the rate is 0.9 (the gap decreases monotonically as we increase the rate). We also used the optimization procedure to design codes for modified MS algorithm where the output of the check node is scaled by a constant 1/alpha. For alpha = 1.25, we observed that the gap to capacity was lesser for the modified MS algorithm when compared with the MS algorithm. However, it was still quite large, varying from 0.75 dB to 0.2 dB for rates between 0.3 and 0.9. We conclude by posing what we consider to be the most important open questions related to the MS algorithm.
In this paper, we present an improvement on the normalized min-sum (NMS) decoding algorithm for low density parity check codes. The modified NMS (M-NMS) algorithm introduces a more efficient adjustment for check node update computation. Taking the sub-minimum value among extrinsic information from the variable nodes into consideration, we make the correction factor varies with different iterations. Results show that, compared with standard min-sum (MS) and NMS decoding algorithms, the proposed method not only offers a better performance but also achieves a lower error floor in the high SNR region.
Among various decoding algorithms of low-density parity-check (LDPC) codes, the minsum (MS) algorithm and its modified algorithms are widely adopted because of their computational simplicity compared to the sum-product (SP) algorithm with slight loss of decoding performance.In the MS algorithm, the magnitude of the output message from a check node (CN) processing unit is decided by either the smallest or the next smallest input message which are denoted as min1 and min2, respectively.It has been shown that multiplying a scaling factor to the output of CN message will improve the decoding performance.Further, Zhong et al. have shown that multiplying different scaling factors (called a 2-dimensional scaling) to min1 and min2 much increases the performance of the LDPC decoder.In this paper, the simplified 2-dimensional scaled (S2DS) MS algorithm is proposed.In the proposed algorithm, we figure out a pair of the most efficient scaling factors which multiplications can be replaced with combinations of addition and shift operations.Furthermore, one scaling operation is approximated by the difference between min1 and min2.The simulation results show that S2DS achieves the error correcting performance which is close to or outperforms the SP algorithm regardless of coding rates, and its computational complexity is the lowest comparing to modified versions of MS algorithms.
Low Density Parity Check Codes (LDPC) give groundbreaking performance which is known to approach Shannon's limits for sufficiently large block length. Historically and recently, LDPC have been known to give superior performance than concatenated coding. In the following paper, a proposal to modify the standard Min-Sum (MS) algorithm for decoding LDPC codes is presented. This is done by introduction of a difference to sum ratio factor, κ in the check to bit node updating process. The algorithm is further extended by implementing hard decision of the Bit-Flipping (BF) algorithm over the soft decision of MS algorithm. Simulation results demonstrate that the proposed algorithms are effective in imparting a better performance in terms of a lower bit error rate (BER) at medium to high signal to noise ratio (SNR) when compared to the traditional MS algorithm while adding fair amount of complexity.