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

Local-optimality guarantees for optimal decoding based on paths

Nissim Halabi, Guy Even

Published Aug 1, 2012• 0 citations
Publisher

Abstract

This paper presents a unified analysis framework that captures recent advances in the study of local-optimality characterizations for codes on graphs. These local-optimality characterizations are based on combinatorial structures embedded in the Tanner graph of the code. Local-optimality implies both maximum-likelihood (ML) optimality and linear-programming (LP) decoding optimality. Also, an iterative message-passing decoding algorithm is guaranteed to find the unique locally-optimal codeword, if one exists. We demonstrate this proof technique by considering a definition of local optimality that is based on the simplest combinatorial structures in Tanner graphs, namely, paths of length h. We apply the technique of local optimality to a family of Tanner codes. Inverse polynomial bounds in the code length are proved on the word error probability of LP-decoding for this family of Tanner codes.

DOI
10.1109/istc.2012.6325228

Related papers

Local-Optimality Guarantees Based on Paths for Optimal Decoding

Guy Even, Nissim Halabi

This paper presents a unified analysis framework that captures recent advances in the study of local-optimality characterizations for codes on graphs. These local-optimality characterizations are based on combinatorial structures embedded in the Tanner graph of the code. Local optimality implies both unique maximum likelihood optimality and unique linear programming (LP) decoding optimality. Also, an iterative message-passing decoding algorithm is guaranteed to find the unique locally optimal codeword if one exists. We demonstrate an instance of this proof technique by considering a definition of local optimality that is based on the simplest combinatorial structures in Tanner graphs, namely, paths of length $h$. We apply the technique of local optimality to binary Tanner codes (including any low-density parity-check code, and in particular any irregular repeat-accumulate code with both even and odd repetition factors). Inverse polynomial bounds in the code length are proved on the word error probability of LP decoding for binary Tanner codes. When the local codes are restricted to single parity-check codes, these bounds also hold for decoding by a certain iterative message-passing decoding algorithm.

arXiv:1203.1854•SIAM Journal on Discrete Mathematics•Jan 1, 2013•1 citation

Linear-programming decoding of Tanner codes with local-optimality certificates

Nissim Halabi, Guy Even

Given a channel observation y and a codeword x, we are interested in a one-sided error test that answers the questions: is x optimal with respect to y? is it unique? A positive answer for such a test is called a certificate for the optimality of a codeword. We present new certificates that are based on combinatorial characterization for local-optimality of a codeword in irregular Tanner codes. The certificate is based on weighted normalized trees in computation trees of the Tanner graph. These trees 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 (i.e., skinny trees). We prove that local-optimality in this new characterization implies ML-optimality and LP-optimality, and show that a certificate can be computed efficiently. 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.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2012•3 citations

On Decoding Irregular Tanner Codes With Local-Optimality Guarantees

Nissim Halabi, Guy Even

We consider decoding of binary linear Tanner codes using message-passing iterative decoding and linear-programming (LP) decoding in memoryless binary-input output-symmetric (MBIOS) channels. We present new certificates that are based on a combinatorial characterization for the local optimality of a codeword in irregular Tanner codes with respect to any MBIOS channel. This characterization is a generalization of (Arora , Proc. ACM Symp. Theory of Computing, 2009) and (Vontobel, Proc. Inf. Theory and Appl. Workshop, 2010) and is based on a conical combination of normalized weighted subtrees in the computation trees of the Tanner graph. These subtrees may have any finite height h (even equal or greater than half of the girth of the Tanner graph). In addition, the degrees of local-code nodes in these subtrees are not restricted to two (i.e., these subtrees are not restricted to skinny trees). We prove that local optimality in this new characterization implies maximum-likelihood (ML) optimality and LP optimality, and show that a certificate can be computed efficiently. We also present a new message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS decoding is a belief-propagation (BP) type algorithm that applies to any irregular binary Tanner code with single parity-check local codes (e.g., low-density and high-density parity-check codes). We prove that if a locally optimal codeword with respect to height parameter h exists (whereby notably h is not limited by the girth of the Tanner graph), then NWMS decoding finds this codeword in h iterations. The decoding guarantee of the NWMS decoding algorithm applies whenever there exists a locally optimal codeword. Because local optimality of a codeword implies that it is the unique ML codeword, the decoding guarantee also provides an ML certificate for this codeword. 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 to decode the transmitted codeword decays doubly exponentially in the girth of the Tanner graph.

arXiv:1107.2677•IEEE Transactions on Information Theory•Oct 10, 2013•8 citations

Code representation and performance of graph -based decoding

Junsheng Han

Key to the success of modern error correcting codes is the effectiveness of message-passing iterative decoding (MPID). Unlike maximum-likelihood (ML) decoding, the performance of MPID depends not only on the code, but on how the code is represented. In particular, the performance of MPID is potentially improved by using a redundant representation. We focus on Tanner graphs and study combinatorial structures therein that help explain the performance disparity among different representations of the same code. Emphasis is placed on the complexity- performance tradeoff, as more and more check nodes are allowed in the graph. Our discussion applies to MPID as well as linear programming decoding (LPD), which we collectively refer to as graph-based decoding. On an erasure channel, it is well-known that the performance of MPID or LPD is determined by stopping sets. Following Schwartz and Vardy, we define the stopping redundancy as the smallest number of check nodes in a Tanner graph such that smallest size of a non-empty stopping set is equal to the minimum Hamming distance of the code. Roughly speaking, stopping redundancy measures the complexity requirement (in number of check nodes) for MPID of a redundant graph representation to achieve performance comparable to ML decoding (up to a constant factor for small channel erasure probability). General upper bounds on stopping redundancy are obtained. One of our main contribution is a new upper bound based on probabilistic analysis, which is shown to be by far the strongest. From this bound, it can be shown, for example, that for a fixed minimum distance, the stopping redundancy grows just linearly with the redundancy (codimension). Specific results on the stopping redundancy of Golay and Reed-Muller codes are also obtained. We show that the stopping redundancy of maximum distance separable (MDS) codes is bounded in between a Turan number and a single-exclusion (SE) number --- a purely combinatorial quantity that we introduce. By studying upper bounds on the SE number, new results on the stopping redundancy of MDS codes are obtained. Schwartz and Vardy conjecture that the stopping redundancy of an MDS code should only depend on its length and minimum distance. Our results provide partial confirmation, both exact and asymptotic, to this conjecture. Stopping redundancy can be large for some codes. We observe that significantly fewer checks are needed if a small number of small stopping sets are allowed. These small stopping sets can then be dealt with by ̀g̀uessing'' during the iterative decoding process. Correspondingly, the guess-g stopping redundancy is defined and it is shown that the savings in number of required check nodes are potentially significant. Another theoretically interesting question is when MPID of a Tanner graph achieves the same word error rate an ML decoder. This prompts us to define and study ML redundancy. Applicability and possible extensions of the current work to a non-erasure channel are discussed. A framework based on pseudo-codewords is considered and shown to be relevant. However, it is also observed that the polytope characterization of pseudo-codewords is not complete enough to be an accurate indicator of MPID performance. Finally, in a separate piece of work, the probability of undetected error (PUE) for over-extended Reed-Solomon codes is studied through the weight distribution bounds of the code. The resulting PUE expressions are shown to be tight in a well-defined sense

•Jan 1, 2008•0 citations

Local Optimality Certificates for LP Decoding of Tanner Codes

Nissim Halabi, Guy Even

We present a new combinatorial characterization for local optimality of a codeword in an irregular Tanner code. The main novelty in this characterization is that it is based on a linear combination of subtrees in the computation trees. These subtrees may have any degree in the local code nodes and may have any height (even greater than the girth). We expect this new characterization to lead to improvements in bounds for successful decoding. We prove that local optimality in this new characterization implies ML-optimality and LP-optimality, as one would expect. Finally, we show that is possible to compute efficiently a certificate for the local optimality of a codeword given an LLR vector.

arXiv:1104.4646•Apr 24, 2011•0 citations

Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes

Pascal O. Vontobel, R. Koetter

The goal of the present paper is the derivation of a framework for the finite-length analysis of message-passing iterative decoding of low-density parity-check codes. To this end we introduce the concept of graph-cover decoding. Whereas in maximum-likelihood decoding all codewords in a code are competing to be the best explanation of the received vector, under graph-cover decoding all codewords in all finite covers of a Tanner graph representation of the code are competing to be the best explanation. We are interested in graph-cover decoding because it is a theoretical tool that can be used to show connections between linear programming decoding and message-passing iterative decoding. Namely, on the one hand it turns out that graph-cover decoding is essentially equivalent to linear programming decoding. On the other hand, because iterative, locally operating decoding algorithms like message-passing iterative decoding cannot distinguish the underlying Tanner graph from any covering graph, graph-cover decoding can serve as a model to explain the behavior of message-passing iterative decoding. Understanding the behavior of graph-cover decoding is tantamount to understanding the so-called fundamental polytope. Therefore, we give some characterizations of this polytope and explain its relation to earlier concepts that were introduced to understand the behavior of message-passing iterative decoding for finite-length codes.

arXiv:cs/0512078•Dec 20, 2005•227 citations
This paper presents a unified analysis framework that captures recent advances in the study of local-optimality characterizations for codes on graphs. These local-optimality characterizations are based on combinatorial structures embedded in the Tanner graph of the code. Local-optimality implies both maximum-likelihood (ML) optimality and linear-programming (LP) decoding optimality. Also, an iterative message-passing decoding algorithm is guaranteed to find the unique locally-optimal codeword, if one exists. We demonstrate this proof technique by considering a definition of local optimality that is based on the simplest combinatorial structures in Tanner graphs, namely, paths of length h. We apply the technique of local optimality to a family of Tanner codes. Inverse polynomial bounds in the code length are proved on the word error probability of LP-decoding for this family of Tanner codes.
This paper presents a unified analysis framework that captures recent advances in the study of local-optimality characterizations for codes on graphs. These local-optimality characterizations are based on combinatorial structures embedded in the Tanner graph of the code. Local optimality implies both unique maximum likelihood optimality and unique linear programming (LP) decoding optimality. Also, an iterative message-passing decoding algorithm is guaranteed to find the unique locally optimal codeword if one exists. We demonstrate an instance of this proof technique by considering a definition of local optimality that is based on the simplest combinatorial structures in Tanner graphs, namely, paths of length hhh. We apply the technique of local optimality to binary Tanner codes (including any low-density parity-check code, and in particular any irregular repeat-accumulate code with both even and odd repetition factors). Inverse polynomial bounds in the code length are proved on the word error probability of LP decoding for binary Tanner codes. When the local codes are restricted to single parity-check codes, these bounds also hold for decoding by a certain iterative message-passing decoding algorithm.
Given a channel observation y and a codeword x, we are interested in a one-sided error test that answers the questions: is x optimal with respect to y? is it unique? A positive answer for such a test is called a certificate for the optimality of a codeword. We present new certificates that are based on combinatorial characterization for local-optimality of a codeword in irregular Tanner codes. The certificate is based on weighted normalized trees in computation trees of the Tanner graph. These trees 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 (i.e., skinny trees). We prove that local-optimality in this new characterization implies ML-optimality and LP-optimality, and show that a certificate can be computed efficiently. 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.
We consider decoding of binary linear Tanner codes using message-passing iterative decoding and linear-programming (LP) decoding in memoryless binary-input output-symmetric (MBIOS) channels. We present new certificates that are based on a combinatorial characterization for the local optimality of a codeword in irregular Tanner codes with respect to any MBIOS channel. This characterization is a generalization of (Arora , Proc. ACM Symp. Theory of Computing, 2009) and (Vontobel, Proc. Inf. Theory and Appl. Workshop, 2010) and is based on a conical combination of normalized weighted subtrees in the computation trees of the Tanner graph. These subtrees may have any finite height h (even equal or greater than half of the girth of the Tanner graph). In addition, the degrees of local-code nodes in these subtrees are not restricted to two (i.e., these subtrees are not restricted to skinny trees). We prove that local optimality in this new characterization implies maximum-likelihood (ML) optimality and LP optimality, and show that a certificate can be computed efficiently. We also present a new message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS decoding is a belief-propagation (BP) type algorithm that applies to any irregular binary Tanner code with single parity-check local codes (e.g., low-density and high-density parity-check codes). We prove that if a locally optimal codeword with respect to height parameter h exists (whereby notably h is not limited by the girth of the Tanner graph), then NWMS decoding finds this codeword in h iterations. The decoding guarantee of the NWMS decoding algorithm applies whenever there exists a locally optimal codeword. Because local optimality of a codeword implies that it is the unique ML codeword, the decoding guarantee also provides an ML certificate for this codeword. 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 to decode the transmitted codeword decays doubly exponentially in the girth of the Tanner graph.
Key to the success of modern error correcting codes is the effectiveness of message-passing iterative decoding (MPID). Unlike maximum-likelihood (ML) decoding, the performance of MPID depends not only on the code, but on how the code is represented. In particular, the performance of MPID is potentially improved by using a redundant representation. We focus on Tanner graphs and study combinatorial structures therein that help explain the performance disparity among different representations of the same code. Emphasis is placed on the complexity- performance tradeoff, as more and more check nodes are allowed in the graph. Our discussion applies to MPID as well as linear programming decoding (LPD), which we collectively refer to as graph-based decoding. On an erasure channel, it is well-known that the performance of MPID or LPD is determined by stopping sets. Following Schwartz and Vardy, we define the stopping redundancy as the smallest number of check nodes in a Tanner graph such that smallest size of a non-empty stopping set is equal to the minimum Hamming distance of the code. Roughly speaking, stopping redundancy measures the complexity requirement (in number of check nodes) for MPID of a redundant graph representation to achieve performance comparable to ML decoding (up to a constant factor for small channel erasure probability). General upper bounds on stopping redundancy are obtained. One of our main contribution is a new upper bound based on probabilistic analysis, which is shown to be by far the strongest. From this bound, it can be shown, for example, that for a fixed minimum distance, the stopping redundancy grows just linearly with the redundancy (codimension). Specific results on the stopping redundancy of Golay and Reed-Muller codes are also obtained. We show that the stopping redundancy of maximum distance separable (MDS) codes is bounded in between a Turan number and a single-exclusion (SE) number --- a purely combinatorial quantity that we introduce. By studying upper bounds on the SE number, new results on the stopping redundancy of MDS codes are obtained. Schwartz and Vardy conjecture that the stopping redundancy of an MDS code should only depend on its length and minimum distance. Our results provide partial confirmation, both exact and asymptotic, to this conjecture. Stopping redundancy can be large for some codes. We observe that significantly fewer checks are needed if a small number of small stopping sets are allowed. These small stopping sets can then be dealt with by ̀g̀uessing'' during the iterative decoding process. Correspondingly, the guess-g stopping redundancy is defined and it is shown that the savings in number of required check nodes are potentially significant. Another theoretically interesting question is when MPID of a Tanner graph achieves the same word error rate an ML decoder. This prompts us to define and study ML redundancy. Applicability and possible extensions of the current work to a non-erasure channel are discussed. A framework based on pseudo-codewords is considered and shown to be relevant. However, it is also observed that the polytope characterization of pseudo-codewords is not complete enough to be an accurate indicator of MPID performance. Finally, in a separate piece of work, the probability of undetected error (PUE) for over-extended Reed-Solomon codes is studied through the weight distribution bounds of the code. The resulting PUE expressions are shown to be tight in a well-defined sense
We present a new combinatorial characterization for local optimality of a codeword in an irregular Tanner code. The main novelty in this characterization is that it is based on a linear combination of subtrees in the computation trees. These subtrees may have any degree in the local code nodes and may have any height (even greater than the girth). We expect this new characterization to lead to improvements in bounds for successful decoding. We prove that local optimality in this new characterization implies ML-optimality and LP-optimality, as one would expect. Finally, we show that is possible to compute efficiently a certificate for the local optimality of a codeword given an LLR vector.
The goal of the present paper is the derivation of a framework for the finite-length analysis of message-passing iterative decoding of low-density parity-check codes. To this end we introduce the concept of graph-cover decoding. Whereas in maximum-likelihood decoding all codewords in a code are competing to be the best explanation of the received vector, under graph-cover decoding all codewords in all finite covers of a Tanner graph representation of the code are competing to be the best explanation. We are interested in graph-cover decoding because it is a theoretical tool that can be used to show connections between linear programming decoding and message-passing iterative decoding. Namely, on the one hand it turns out that graph-cover decoding is essentially equivalent to linear programming decoding. On the other hand, because iterative, locally operating decoding algorithms like message-passing iterative decoding cannot distinguish the underlying Tanner graph from any covering graph, graph-cover decoding can serve as a model to explain the behavior of message-passing iterative decoding. Understanding the behavior of graph-cover decoding is tantamount to understanding the so-called fundamental polytope. Therefore, we give some characterizations of this polytope and explain its relation to earlier concepts that were introduced to understand the behavior of message-passing iterative decoding for finite-length codes.