Name
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 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1137/120886674 | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | Field | DocType |
coding theory,Tanner codes,local optimality,maximum likelihood,linear programming decoding,error probability,iterative message-passing decoding,repeat-accumulate codes | Discrete mathematics,Combinatorics,Concatenated error correction code,Sequential decoding,Coding theory,Code word,Linear code,Tanner graph,Decoding methods,List decoding,Mathematics | Journal |
Volume | Issue | ISSN |
27 | 4 | 0895-4801 |
Citations | PageRank | References |
0 | 0.34 | 10 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guy Even | 1 | 1194 | 136.90 |
| Nissim Halabi | 2 | 8 | 3.58 |