Computer Science – Information Theory
Scientific paper
2006-01-27
Computer Science
Information Theory
5 pages, 6 figures
Scientific paper
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 \cite{03FWK}. In order to quantify LP decoding, and thus to describe performance of the error-correction scheme at moderate and large Signal-to-Noise-Ratios (SNR), it is important to study the relaxed polytope to understand better its vertexes, so-called pseudo-codewords, especially those which are neighbors of the zero codeword. In this manuscript we propose a technique to heuristically create a list of these neighbors and their distances. Our pseudo-codeword-search algorithm starts by randomly choosing the initial configuration of the noise. The configuration is modified through a discrete number of steps. Each step consists of two sub-steps. Firstly, one applies an LP decoder to the noise-configuration deriving a pseudo-codeword. Secondly, one finds configuration of the noise equidistant from the pseudo codeword and the zero codeword. The resulting noise configuration is used as an entry for the next step. The iterations converge rapidly to a pseudo-codeword neighboring the zero codeword. Repeated many times, this procedure is characterized by the distribution function (frequency spectrum) of the pseudo-codeword effective distance. The effective distance of the coding scheme is approximated by the shortest distance pseudo-codeword in the spectrum. The efficiency of the procedure is demonstrated on examples of the Tanner $[155,64,20]$ code and Margulis $p=7$ and $p=11$ codes (672 and 2640 bits long respectively) operating over an Additive-White-Gaussian-Noise (AWGN) channel.
Chertkov Michael
Stepanov Mikhail G.
No associations
LandOfFree
An Efficient Pseudo-Codeword Search Algorithm for Linear Programming Decoding of LDPC Codes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An Efficient Pseudo-Codeword Search Algorithm for Linear Programming Decoding of LDPC Codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient Pseudo-Codeword Search Algorithm for Linear Programming Decoding of LDPC Codes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-505972