Eigenvalue bounds on the pseudocodeword weight of expander codes
Christine A. Kelley Deepak Sridhara
Advances in Mathematics of Communications 2007, 1(3): 287-306 doi: 10.3934/amc.2007.1.287
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
Channel decomposition for multilevel codes over multilevel and partial erasure channels
Carolyn Mayer Kathryn Haymaker Christine A. Kelley
Advances in Mathematics of Communications 2018, 12(1): 151-168 doi: 10.3934/amc.2018010

We introduce the Multilevel Erasure Channel (MEC) for binary extension field alphabets. The channel model is motivated by applications such as non-volatile multilevel read storage channels. Like the recently proposed $q$-ary partial erasure channel (QPEC), the MEC is designed to capture partial erasures. The partial erasures addressed by the MEC are determined by erasures at the bit level of the $q$-ary symbol representation. In this paper we derive the channel capacity of the MECand give a multistage decoding scheme on the MEC using binary codes. We also present a low complexity multistage $p$-ary decoding strategy for codes on the QPEC when $q = p^k$.We show that for appropriately chosen component codes, capacity on the MEC and QPEC may be achieved.

keywords: Partial erasure channels multilevel codes multistage decoding storage channels
Zig-zag and replacement product graphs and LDPC codes
Christine A. Kelley Deepak Sridhara Joachim Rosenthal
Advances in Mathematics of Communications 2008, 2(4): 347-372 doi: 10.3934/amc.2008.2.347
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]