Computer Science – Information Theory
Scientific paper
2007-05-09
Computer Science
Information Theory
submitted to ITW 07
Scientific paper
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 the {\em block error} probability \cite{Wiberg}. There also seems to be a fundamental relationship of MS decoding with the linear programming decoder \cite{Koetter}. 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 1dB for a rate 0.3 code and it is 0.4dB 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.
Bhattad Kapil
Rathi Vishwambhar
Urbanke Ruediger
No associations
LandOfFree
Degree Optimization and Stability Condition for the Min-Sum Decoder does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Degree Optimization and Stability Condition for the Min-Sum Decoder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Degree Optimization and Stability Condition for the Min-Sum Decoder will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-646321