Pseudocodeword Performance Analysis for

Roxana Smarandache, Alí Emre Pusane, Pascal O. Vontobel, Daniel J. Costello

Published Jan 1, 2009• 0 citations

Abstract

Message-passing iterative decoders for low-density parity-check (LDPC) block codes are known to be subject to de- coding failures due to so-called pseudocodewords. These failures can cause the large signal-to-noise ratio (SNR) performance of message-passing iterative decoding to be worse than that predicted by the maximum-likelihood (ML) decoding union bound. In this paper, we address the pseudocodeword problem from the convolutional code perspective. In particular, we compare the performance of LDPC convolutional codes with that of their wrapped quasi-cyclic block versions and we show that the minimum pseudoweight of an LDPC convolutional code is at least as large as the minimum pseudoweight of an underlying quasi-cyclic code. This result, which parallels a well-known rela- tionship between the minimum Hamming weight of convolutional codes and the minimum Hamming weight of their quasi-cyclic counterparts, is due to the fact that every pseudocodeword in the convolutional code induces a pseudocodeword in the block code with pseudoweight no larger than that of the convolutional code's pseudocodeword. This difference in the weight spectra leads to improved performance at low-to-moderate SNRs for the convolutional code, a conclusion supported by simulation results. Index Terms—Convolutional codes, linear programming de- coding, low-density parity-check (LDPC) codes, message-passing iterative decoding, pseudocodewords, pseudoweights, quasi-cyclic codes.

Related papers

Pseudocodeword Performance Analysis for LDPC Convolutional Codes

Roxana Smarandache, A. E. Pusane, Pascal O. Vontobel +1 more

Message-passing iterative decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudocodewords. These failures can cause the large signal-to-noise ratio (SNR) performance of message-passing iterative decoding to be worse than that predicted by the maximum-likelihood (ML) decoding union bound.

arXiv:cs/0609148IEEE Transactions on Information TheoryMay 19, 200930 citations

Pseudo-Codewords in LDPC Convolutional Codes

Roxana Smarandache, Alí Emre Pusane, Pascal O. Vontobel +1 more

Iterative message-passing decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudo-codewords. These failures can cause the large signal-to-noise ratio performance of message-passing decoding to be worse than that predicted by the maximum-likelihood decoding union bound. In this paper we study the pseudo-codeword problem for the class of LDPC convolutional codes decoded continuously using an iterative, sliding window, message-passing decoder. In particular, for an LDPC convolutional code derived by unwrapping a quasi-cyclic LDPC block code, we show that the free pseudo-weight of the convolutional code is at least as large as the minimum pseudo-weight of the underlying quasi-cyclic code. This result parallels the well-known relationship between the free Hamming distance of convolutional codes and the minimum Hamming distance of their quasi-cyclic counterparts. Finally, simulation results are included that show improved performance for unwrapped LDPC convolutional codes compared to their underlying quasi-cyclic codes

IEEE International Symposium on Information Theory (ISIT)Jul 1, 200616 citations

Analysis of LDPC convolutional codes derived from LDPC block codes

Alí Emre Pusane

LDPC convolutional codes have been shown to be capable of achieving the same capacity-approaching performance as LDPC block codes with iterative message passing decoding. In this dissertation, we present several methods of deriving families of time-varying and time-invariant LDPC convolutional codes from LDPC block codes. We demonstrate that the derived LDPC convolutional codes significantly outperform the underlying LDPC block codes, and we investigate the reasons for these 'convolutional gains'. It is well known that cycles in the Tanner graph representation of a sparse code affect the iterative decoding algorithm, with short cycles generally pushing its performance further away from optimum. Hence it is common practice to design codes that do not contain short cycles, so as to obtain independent messages in at least the initial iterations of the decoding process. We show that the derived LDPC convolutional codes have better graph-cycle properties than their block code counterparts. In particular, we show that the unwrapping process that is used to derive LDPC convolutional codes from LDPC block codes can 'break' some cycles of the underlying LDPC block code, but cannot create any shorter cycles. We prove that any cycle in an LDPC convolutional code always maps to a cycle of the same or smaller length in the underlying LDPC block code. Minimum distance is an important code design parameter when the channel quality is high, since codewords that are minimum distance apart are the most likely to cause errors with ML or near-ML decoding. In this case, the minimum distance determines the so-called error floor behavior in the performance curve corresponding to high channel signal-to-noise ratios. Thus studying the minimum distance properties of a code family gives insight into its error floor behavior. We use asymptotic methods to calculate a lower bound on the free distance of several ensembles of asymptotically good LDPC convolutional codes derived from protograph-based LDPC block codes. Further, we show that the free distance to constraint length ratio of the LDPC convolutional codes exceeds the minimum distance to block length ratio of the corresponding LDPC block codes. Message-passing iterative decoders for LDPC block codes are known to be subject to decoding failures due to so-called pseudo-codewords. These failures can cause the large signal-to-noise ratio performance of message-passing iterative decoding to be worse than that predicted by the maximum-likelihood decoding union bound. We address the pseudo-codeword problem from the convolutional code perspective. In particular, we show that the minimum pseudo-weight of an LDPC convolutional code is at least as large as the minimum pseudo-weight of an underlying LDPC block code. This result, which parallels a well-known relationship between the minimum Hamming weight of convolutional codes and the minimum Hamming weight of their quasi-cyclic counterparts, is due to the fact that every pseudo-codeword in the LDPC convolutional code induces a pseudo-codeword in the LDPC block code with pseudo-weight no larger than that of the convolutional pseudo-codeword. More generally, we demonstrate a difference in the weight spectra of LDPC block and convolutional codes that leads to improved performance at low-to-moderate signal-to-noise ratios for the convolutional codes, a conclusion supported by simulation results.

Sep 15, 20221 citation

Minimum Pseudoweight and Minimum Pseudocodewords of LDPC Codes

Shu‐Tao Xia, Fang‐Wei Fu

In this correspondence, we study the minimum pseudoweight and minimum pseudocodewords of low-density parity-check (LDPC) codes under linear programming (LP) decoding. First, we show that the lower bound of Kelley, Sridhara, Xu, and Rosenthal on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth greater than is tight if and only if this pseudocodeword is a real multiple of a codeword. Then, the lower bound of Kashyap and Vardy on the stopping distance of an LDPC code is proved to be also a lower bound on the pseudoweight of a nonzero pseudocodeword of an LDPC code whose Tanner graph has girth , and this lower bound is tight if and only if this pseudocodeword is a real multiple of a codeword. Using these results we further obtain that for some LDPC codes, there are no other minimum pseudocodewords except the real multiples of minimum weight codewords. This means that the LP decoding for these LDPC codes is asymptotically optimal in the sense that the ratio of the probabilities of decoding errors of LP decoding and maximum-likelihood decoding approaches as the signal-to-noise ratio (SNR) tends to infinity. Finally, some LDPC codes are listed to illustrate these results.

arXiv:cs/0606051IEEE Transactions on Information TheoryJan 1, 200825 citations

Design and Analysis of LDPC Convolutional Codes

Arvind Sridharan

Low-density parity-check (LDPC) block codes invented by Gallager in 1962 achieve exceptional error performance on a wide variety of communication channels. LDPC convolutional codes are the convolutional counterparts of LDPC block codes. This dissertation describes techniques for the design of LDPC convolutional codes, and analyzes their distance properties and iterative decoding convergence thresholds. The construction of time invariant LDPC convolutional codes by unwrapping the Tanner graph of algebraically constructed quasi-cyclic LDPC codes is described. The convolutional codes outperform the quasi-cyclic codes from which they are derived. The design of parity-check matrices for time invariant LDPC convolutional codes by the polynomial extension of a base matrix is proposed. An upper bound on free distance, proving that time invariant LDPC codes are not asymptotically good, is obtained. The Tanner graph is used to describe a pipelined message passing based iterative decoder for LDPC convolutional codes that outputs decoding results continuously. The performance of LDPC block and convolutional codes are compared for fixed decoding parameters like computational complexity, processor complexity, and decoding delay. In each case, the LDPC convolutional code performance is at least as good as that of LDPC block codes. An analog circuit to implement pipelined decoding of LDPC convolutional codes is proposed. The distance properties of a permutation matrix based (time varying) ensemble of (J,K) regular LDPC convolutional codes is investigated. It is proved that these codes (for J > 2) have free distance increasing linearly with constraint length, i.e., they are asymptotically good. Further, the asymptotic free distance to constraint length ratio for the convolutional codes is several times larger than the minimum distance to block length ratio for corresponding LDPC block codes. Iterative decoding of terminated LDPC convolutional codes, based on the ensemble mentioned above, is analyzed, assuming transmission over a binary erasure channel. The structured irregularity of the codes leads to significantly better convergence thresholds compared to corresponding LDPC block codes. At the calculated thresholds, both the bit and block error probability can be made arbitrarily small. The results obtained suggest that the thresholds approach capacity with increasing J.

Sep 15, 202230 citations

Pseudocodewords, Expander Graphs, and the Algebraic Construction of Low-density Parity-check Codes

Christine A. Kelley

In 1948, Claude Shannon provided a sound mathematical foundation for communication, and proved the existence of good codes. Low-density parity-check (LDPC) codes are a family of error-correcting codes that achieve reliable performance (i.e., arbitrarily low probability of decoding error) near the Shannon-limit when decoded iteratively via very efficient graph-based message-passing decoders, the complexity of which grows only linearly in the block-length. Despite their tremendous success, LDPC codes lack a strong theoretical foundation and few explicit constructions of them are known that outperform their random counterparts. The first part of this thesis investigates how the structure of a graph representing an LDPC code affects the decoding performance. In particular, lower bounds on the minimum pseudocodeword weight, a key parameter in predicting iterative decoding performance, are obtained which link the performance of the code to the structural properties of its graph. One bound is a tree bound and is extended to generalized and p-ary LDPC codes. To this end, a suitable definition of pseudocodeword weight is derived for the p-ary symmetric channel. Moreover, the relationship between pseudocodeword weight distributions and different graph representations is examined. Bounds on the minimum pseudocodeword weight are also presented for several classes of expander codes based on the eigenvalues of the adjacency matrix of the Tanner graph. The second part of this thesis constructs LDPC codes having desirable properties. The first construction is combinatorial and uses permutations and mutually orthogonal Latin squares. One type results in the well-known projective-geometrybased LDPC codes. Another type yields a new family of codes having comparable parameters and pseudocodeword weights suitable for iterative decoding. The resulting performance of these codes is superior in comparison with that of comparable random LDPC codes, a feature attributed to the lack of low-weight bad pseudocodewords. For the second construction, unbalanced expander graphs are obtained by modifying the original zig-zag graph product to take bi-regular expander graphs as components, with suitable constraints on the degrees. Graphs resulting from the zig-zag and replacement product graphs are then used in the design of generalized LDPC codes having compact representation and pseudocodeword weights lower-bounded by the eigenvalue bounds.

Sep 15, 20220 citations