Polynomial Time Low-Density Parity-Check Codes With Rates Very Close to the Capacity of the q-ary Random Deletion Channel for Large q
Lists
Only you see this
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...