Computer Science – Information Theory
Scientific paper
2011-07-13
Computer Science
Information Theory
Submitted to IEEE Transactions on Information Theory
Scientific paper
We deal with decoding of Tanner codes using message-passing iterative decoding and linear programming (LP) decoding in memoryless binary-input output-symmetric (MBIOS) channels. We present a new combinatorial characterization for local-optimality of a codeword in irregular Tanner codes with respect to any MBIOS channel. This characterization is a generalization of [Arora, Daskalakis, Steurer; 2009] and [Vontobel; 2010] and is based on a conical combination of subtrees in the computation trees. The main novelty is that the subtrees may have any finite height $h$ (even greater than the girth of the Tanner graph). In addition, the degrees of local-code nodes are not restricted to two. We prove that local-optimality in this new characterization implies Maximum-Likelihood (ML) optimality and LP-optimality. Given a codeword and the channel output, we also show how to efficiently recognize if the codeword is locally optimal. We present a novel message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS algorithm is a BP-type algorithm that applies to any Tanner code with single parity-check local codes (e.g., LDPC codes). We prove that if a locally optimal codeword for depth $h$ exists, then the NWMS algorithm finds it in $h$ iterations. Hence, the NWMS algorithm has an ML-certificate for any bounded number of iterations. Furthermore, since the depth $h$ is not bounded, the guarantee for successful decoding by NWMS holds even if the number of iterations $h$ exceeds the girth of the Tanner graph. Finally, we apply the new local-optimality characterization to regular Tanner codes, and prove lower bounds on the noise thresholds of LP-decoding in MBIOS channels. When the noise is below these lower bounds, the probability that LP-decoding fails decays doubly exponentially in the girth of the Tanner graph.
Even Guy
Halabi Nissim
No associations
LandOfFree
On Decoding Irregular Tanner Codes with Local-Optimality Guaranties 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 On Decoding Irregular Tanner Codes with Local-Optimality Guaranties, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Decoding Irregular Tanner Codes with Local-Optimality Guaranties will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-224475