Name
Title | ||
|---|---|---|
Explicit and Efficient Constructions of Coding Schemes for the Binary Deletion Channel |
Abstract | ||
|---|---|---|
In the binary deletion channel with parameter p (BDC
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub>
) every bit is deleted independently with probability p. [1] proved a lower bound of (1-p)/9 on the capacity of the BDC
<sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub>
, 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. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1109/ISIT44484.2020.9173977 | 2020 IEEE International Symposium on Information Theory (ISIT) |
Keywords | DocType | ISSN |
explicit family,binary deletion channel,BDC,decoding algorithms,polynomial time encoding | Conference | 2157-8095 |
ISBN | Citations | PageRank |
978-1-7281-6433-5 | 1 | 0.35 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Roni Con | 1 | 2 | 1.38 |
| Amir Shpilka | 2 | 1095 | 64.27 |