Eigenvalue bounds on the pseudocodeword weight of expander codes
Christine A. Kelley Deepak Sridhara
Four different ways of obtaining low-density parity-check codes from expander graphs are considered. For each case, lower bounds on the minimum stopping set size and the minimum pseudocodeword weight of expander (LDPC) codes are derived. These bounds are compared with the known eigenvalue-based lower bounds on the minimum distance of expander codes. Furthermore, Tanner's parity-oriented eigenvalue lower bound on the minimum distance is generalized to yield a new lower bound on the minimum pseudocodeword weight. These bounds are useful in predicting the performance of LDPC codes under graph-based iterative decoding and linear programming decoding.
keywords: pseudocodeword weight pseudocodewords iterative decoding. LDPC codes Expander graphs
Zig-zag and replacement product graphs and LDPC codes
Christine A. Kelley Deepak Sridhara Joachim Rosenthal
It is known that the expansion property of a graph influences the performance of the corresponding code when decoded using iterative algorithms. Certain graph products may be used to obtain larger expander graphs from smaller ones. In particular, the zig-zag product and replacement product may be used to construct infinite families of constant degree expander graphs. This paper investigates the use of zig-zag and replacement product graphs for the construction of codes on graphs. A modification of the zig-zag product is also introduced, which can operate on two unbalanced biregular bipartite graphs, and a proof of the expansion property of this modified zig-zag product is presented.
keywords: expander graphs Codes on graphs replacement product of a graph LDPC codes zig-zag product

Year of publication

Related Authors

Related Keywords

[Back to Top]