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

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^O(1/epsi2)/q, and the computational complexity for encoding and decoding is n^O(1/epsi2)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