Characterizations of pseudo-codewords of (low-density) parity-check codes |
| |
Authors: | Ralf Koetter Wen-Ching W. Li Pascal O. Vontobel Judy L. Walker |
| |
Affiliation: | a Institute for Communications Engineering, TU Munich, D-80333 Munich, Germany b Department of Mathematics, Pennsylvania State University, University Park, PA 16802-6401, USA c Hewlett-Packard Laboratories, Palo Alto, CA 94304, USA d Department of Mathematics, University of Nebraska, Lincoln, NE 68588-0130, USA |
| |
Abstract: | An important property of low-density parity-check codes is the existence of highly efficient algorithms for their decoding. Many of the most efficient, recent graph-based algorithms, e.g. message-passing iterative decoding and linear programming decoding, crucially depend on the efficient representation of a code in a graphical model. In order to understand the performance of these algorithms, we argue for the characterization of codes in terms of a so-called fundamental cone in Euclidean space. This cone depends upon a given parity-check matrix of a code, rather than on the code itself. We give a number of properties of this fundamental cone derived from its connection to unramified covers of the graphical models on which the decoding algorithms operate. For the class of cycle codes, these developments naturally lead to a characterization of the fundamental cone as the Newton polyhedron of the Hashimoto edge zeta function of the underlying graph. |
| |
Keywords: | primary, 94B secondary, 05C |
本文献已被 ScienceDirect 等数据库收录! |
|