TY - JOUR
T1 - An efficient pseudocodeword search algorithm for linear programming decoding of LDPC codes
AU - Chertkov, Michael
AU - Stepanov, Mikhail G.
N1 - Funding Information:
Manuscript received January 27, 2006; revised May 19, 2007. The work at LANL was carried out under the auspices of the National Nuclear Security Administration of the U.S. Department of Energy at Los Alamos National Laboratory under Contract DE-AC52-06NA25396, and, specifically, the LDRD Exploratory Research Grant on Novel Physics Inspired Approach to Error Correction.
PY - 2008/4
Y1 - 2008/4
N2 - In linear programming (LP) decoding of a low-density parity-check (LDPC) code one minimizes a linear functional, with coefficients related to log-likelihood ratios, over a relaxation of the polytope spanned by the codewords. In order to quantify LP decoding it is important to study vertexes of the relaxed polytope, so-called pseudocodewords. We propose a technique to heuristically create a list of pseudocodewords close to the zero codeword and their distances. Our pseudocodeword-search algorithm starts by randomly choosing configuration of the noise. The configuration is modified through a discrete number of steps. Each step consists of two substeps: one applies an LP decoder to the noise-configuration deriving a pseudocodeword, and then finds configuration of the noise equidistant from the pseudocodeword and the zero codeword. The resulting noise configuration is used as an entry for the next step. The iterations converge rapidly to a pseudocodeword neighboring the zero codeword. Repeated many times, this procedure is characterized by the distribution function of the pseudocodeword effective distance. The efficiency of the procedure is demonstrated on examples of the Tanner code and Margulis codes operating over an additive white Gaussian noise (AWGN) channel.
AB - In linear programming (LP) decoding of a low-density parity-check (LDPC) code one minimizes a linear functional, with coefficients related to log-likelihood ratios, over a relaxation of the polytope spanned by the codewords. In order to quantify LP decoding it is important to study vertexes of the relaxed polytope, so-called pseudocodewords. We propose a technique to heuristically create a list of pseudocodewords close to the zero codeword and their distances. Our pseudocodeword-search algorithm starts by randomly choosing configuration of the noise. The configuration is modified through a discrete number of steps. Each step consists of two substeps: one applies an LP decoder to the noise-configuration deriving a pseudocodeword, and then finds configuration of the noise equidistant from the pseudocodeword and the zero codeword. The resulting noise configuration is used as an entry for the next step. The iterations converge rapidly to a pseudocodeword neighboring the zero codeword. Repeated many times, this procedure is characterized by the distribution function of the pseudocodeword effective distance. The efficiency of the procedure is demonstrated on examples of the Tanner code and Margulis codes operating over an additive white Gaussian noise (AWGN) channel.
KW - Error-floor
KW - Linear programming decoding
KW - Low-density parity-check (LDPC) codes
UR - http://www.scopus.com/inward/record.url?scp=41949108879&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=41949108879&partnerID=8YFLogxK
U2 - 10.1109/TIT.2008.917682
DO - 10.1109/TIT.2008.917682
M3 - Article
AN - SCOPUS:41949108879
SN - 0018-9448
VL - 54
SP - 1514
EP - 1520
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 4
ER -