Binary Linear-Time Erasure Decoding for Non-Binary LDPC codes

Preprint English OPEN
Savin, Valentin (2009)
  • Subject: Computer Science - Information Theory
    arxiv: Computer Science::Information Theory

In this paper, we first introduce the extended binary representation of non-binary codes, which corresponds to a covering graph of the bipartite graph associated with the non-binary code. Then we show that non-binary codewords correspond to binary codewords of the extended representation that further satisfy some simplex-constraint: that is, bits lying over the same symbol-node of the non-binary graph must form a codeword of a simplex code. Applied to the binary erasure channel, this description leads to a binary erasure decoding algorithm of non-binary LDPC codes, whose complexity depends linearly on the cardinality of the alphabet. We also give insights into the structure of stopping sets for non-binary LDPC codes, and discuss several aspects related to upper-layer FEC applications.
  • References (13)
    13 references, page 1 of 2

    [1] R. G. Gallager, Low Density Parity Check Codes, Ph.D. thesis, MIT, Cambridge, Mass., September 1960.

    [2] T.J. Richardson, M.A. Shokrollahi, and R.L. Urbanke, “Design of capacity-approaching irregular low-density parity-check codes,” IEEE Transactions on Information Theory, vol. 47, pp. 619-637, 2001.

    [3] M.G. Luby, M. Mitzenmacher, M.A. Shokrollahi, and D.A. Spielman, “Efficient erasure correcting codes,” IEEE Transactions on Information Theory, vol. 47, no. 2, pp. 569-584, 2001.

    [4] R. M. Tanner, “A recursive approach to low complexity codes,” IEEE Transactions on Information Theory, vol. 27, no. 5, pp. 533-547, 1981.

    [5] E. Paolini, M. Fossorier, and M. Chiani, “Analysis of Generalized LDPC Codes with Random Component Codes for the Binary Erasure Channel,” Int. Symp. on Information Theory and its Applications (ISITA), 2006.

    [6] N. Miladinovic and M. Fossorier, “Generalized LDPC codes and generalized stopping sets,” IEEE Transactions on Communications, vol. 56(2), pp. 201-212, 2008.

    [7] M. Luby, “LT codes,” Proc. ACM Symp. Found. Comp. Sci., 2002.

    [8] A. Shokrollahi, “Raptor codes,” IEEE Transactions on Information Theory, vol. 52-6, pp. 2551-2567, 2006.

    [9] V. Rathi and R. Urbanke, “Density Evolution, Thresholds and the Stability Condition for Non-binary LDPC Codes,” IEE Proceedings Communications, vol. 152, no. 6, 2005.

    [10] V. Rathi, “Conditional Entropy of Non-Binary LDPC Codes over the BEC,” IEEE Int. Symp. on Information Theory (ISIT), 2008.

  • Metrics
    No metrics available
Share - Bookmark