2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | A.3.3 | ||
| Paper Title | Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel | ||
| Authors | Roni Con, Amir Shpilka, Tel Aviv University, Israel | ||
| Session | A.3: Combinatorics and Information Theory | ||
| Presentation | Lecture | ||
| Track | Algebraic and Combinatorial Coding Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | In the binary deletion channel with parameter $p$ (BDC$_p$) every bit is deleted independently with probability $p$. [1] proved a lower bound of $(1-p)/9$ on the capacity of the BDC$_p$, yet currently no explicit construction achieves this rate. In this work we give an explicit family of codes of rate $(1-p)/16$, for every $p$. This improves upon the work of Guruswami and Li [2] that gave a construction of rate $(1-p)/120$. The codes in our family have polynomial time encoding and decoding algorithms. \textit{A full version of this paper is accessible at:} \url{https://arxiv.org/abs/1909.10177} | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
