Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes
| dc.creator | Vontobel, Pascal O. | |
| dc.creator | Koetter, Ralf | |
| dc.date | 2005-12-20 | |
| dc.date.accessioned | 2026-07-07T08:15:49Z | |
| dc.date.available | 2026-07-07T08:15:49Z | |
| dc.description | 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. | |
| dc.description | Submitted to IEEE Transactions on Information Theory, December 2005 | |
| dc.identifier | https://arxiv.org/abs/cs/0512078 | |
| dc.identifier | http://arxiv.org/abs/cs/0512078 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/133575 | |
| dc.subject | Information Theory | |
| dc.title | Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes | |
| dc.type | text |