publication . Preprint . Conference object . 2009

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

Valentin Savin;
Open Access English
  • Published: 10 Oct 2009
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 t...
Persistent Identifiers
arXiv: Computer Science::Information Theory
ACM Computing Classification System: Data_CODINGANDINFORMATIONTHEORY
free text keywords: Computer Science - Information Theory, Tornado code, Discrete mathematics, Combinatorics, Linear code, Concatenated error correction code, Low-density parity-check code, Factor graph, Erasure code, Decoding methods, Binary erasure channel, Mathematics

[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. [OpenAIRE]

[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. [OpenAIRE]

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

[11] V. Savin, “Non binary LDPC codes over the binary erasure channel: density evolution analysis,” in IEEE Int. Symp. Applied Sciences on Biomedical and Communication Technologies (ISABEL), 2008.

[12] MPC Fossorier, “Quasicyclic low-density parity-check codes from circulant permutation matrices,” IEEE Transactions on Information Theory, vol. 50, no. 8, pp. 1788-1793, 2004. [OpenAIRE]

[13] C. Di, D. Proietti, IE Telatar, TJ Richardson, and RL Urbanke, “Finitelength analysis of low-density parity-check codes on the binary erasure channel,” IEEE Transactions on Information Theory, vol. 48, no. 6, pp. 1570-1579, 2002.

Any information missing or wrong?Report an Issue