Polynomial time decodable codes for the binary deletion channel

Abstract

In the random deletion channel, each bit is deleted independently with probability $p$. For the random deletion channel, the existence of codes of rate $(1-p)/9$, and thus bounded away from $0$ for any $p<1$, has been known. We give an explicit construction with polynomial time encoding and deletion correction algorithms with rate $c_0(1-p)$ for an absolute constant $c_0>0$.

arXiv admin note: substantial text overlap with arXiv:1612.06335. The published version of this paper incorrectly states the alphabet size in Theorem 3.4. This version states the result correctly