TY - GEN
T1 - Searching for low weight pseudo-codewords
AU - Chertkov, Michael
AU - Stepanov, Mikhail
PY - 2007
Y1 - 2007
N2 - Belief Propagation (BP) and Linear Programming (LP) decodings of Low Density Parity Check (LDPC) codes are discussed. We summarize results of instanton/pseudo-codeword approach developed for analysis of the error-floor domain of the codes. Instantons are special, code and decoding specific, configurations of the channel noise contributing most to the Frame-Error-Rate (FER). Instantons are decoded into pseudo-codewords. Instanton/pseudo-codeword with the lowest weight describes the largest Signal-to-Noise-Ratio (SNR) asymptotic of FER, while the whole spectra of the low weight instantons is descriptive of the FER vs SNR profile in the extended error-floor domain. First, we describe a general optimization method that allows to find the instantons for any coding/decoding. Second, we introduce LP-specific pseudo-codeword search algorithm that allows efficient calculations of the pseudo-codeword spectra. Finally, we discuss results of combined BP/LP error-floor exploration experiments for two model codes.
AB - Belief Propagation (BP) and Linear Programming (LP) decodings of Low Density Parity Check (LDPC) codes are discussed. We summarize results of instanton/pseudo-codeword approach developed for analysis of the error-floor domain of the codes. Instantons are special, code and decoding specific, configurations of the channel noise contributing most to the Frame-Error-Rate (FER). Instantons are decoded into pseudo-codewords. Instanton/pseudo-codeword with the lowest weight describes the largest Signal-to-Noise-Ratio (SNR) asymptotic of FER, while the whole spectra of the low weight instantons is descriptive of the FER vs SNR profile in the extended error-floor domain. First, we describe a general optimization method that allows to find the instantons for any coding/decoding. Second, we introduce LP-specific pseudo-codeword search algorithm that allows efficient calculations of the pseudo-codeword spectra. Finally, we discuss results of combined BP/LP error-floor exploration experiments for two model codes.
UR - http://www.scopus.com/inward/record.url?scp=48049090892&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=48049090892&partnerID=8YFLogxK
U2 - 10.1109/ITA.2007.4357567
DO - 10.1109/ITA.2007.4357567
M3 - Conference contribution
AN - SCOPUS:48049090892
SN - 9780615153148
T3 - 2007 Information Theory and Applications Workshop, Conference Proceedings, ITA
SP - 94
EP - 100
BT - 2007 Information Theory and Applications Workshop, Conference Proceedings, ITA
T2 - 2007 Information Theory and Applications Workshop, ITA
Y2 - 29 January 2007 through 2 February 2007
ER -