Erasure correction by low-density codes

V. V. Zyablov, P. S. Rybin

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

We generalize the method for computing the number of errors correctable by a low-density parity-check (LDPC) code in a binary symmetric channel, which was proposed by V.V. Zyablov and M.S. Pinsker in 1975. This method is for the first time applied for computing the fraction of guaranteed correctable erasures for an LDPC code with a given constituent code used in an erasure channel. Unlike previously known combinatorial methods for computing the fraction of correctable erasures, this method is based on the theory of generating functions, which allows us to obtain more precise results and unify the computation method for various constituent codes of a regular LDPC code. We also show that there exist an LDPC code with a given constituent code which, when decoded with a low-complexity iterative algorithm, is capable of correcting any erasure pattern with a number of erasures that grows linearly with the code length. The number of decoding iterations, required to correct the erasures, is a logarithmic function of the code length. We make comparative analysis of various numerical results obtained by various computation methods for certain parameters of an LDPC code with a constituent single-parity-check or Hamming code.

Original languageEnglish
Pages (from-to)204-220
Number of pages17
JournalProblems of information transmission
Volume45
Issue number3
DOIs
Publication statusPublished - 2009
Externally publishedYes

Fingerprint

Dive into the research topics of 'Erasure correction by low-density codes'. Together they form a unique fingerprint.

Cite this