Polynomial Time Low-Density Parity-Check Codes With Rates Very Close to the Capacity of the q-ary Random Deletion Channel for Large q

Michael MitzenmacherIEEE Trans. Information Theory 2006 · OpenReview

Abstract

We demonstrate polynomial-time deletion codes based on the verification-based decoding paradigm that come arbitrarily close to capacity. The random deletion channel takes n symbols from a q-ary alphabet, and each symbol is deleted independently with probability p. Taking advantage of recent improvements on the results of Luby and Mitzenmacher for verification-based decoding by Shokrollahi and Wang, we show how to design for any epsi>0 and sufficiently large n and q deletion codes with the following properties: the rate is (1-p)(1-epsi), the failure probability is n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1/epsi2)</sup> /q, and the computational complexity for encoding and decoding is n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1/epsi2)</sup> log q. We also extend these schemes to obtain the same results even if the undeleted symbols are also transposed arbitrarily, and if a sufficiently small number of random symbols are inserted
BibTeX
@article{mitzenmacher2006polynomial,
  author = {Michael Mitzenmacher},
  title = {{Polynomial Time Low-Density Parity-Check Codes With Rates Very Close to the Capacity of the q-ary Random Deletion Channel for Large q}},
  journal = {IEEE Trans. Information Theory},
  year = {2006},
  url = {https://openreview.net/forum?id=n9zgpUB2U0A},
}

Loading related content...

Figure