Back to Search
Start Over
Optimally Resilient Codes for List-Decoding From Insertions and Deletions.
- Source :
-
IEEE Transactions on Information Theory . Dec2021, Vol. 67 Issue 12, p7837-7856. 20p. - Publication Year :
- 2021
-
Abstract
- We give a complete answer to the following basic question: “What is the maximal fraction of deletions or insertions tolerable by $q$ -ary list-decodable codes with non-vanishing information rate?” This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best-known result was that a $\gamma \leq 0.707$ fraction of insertions is tolerable by some binary code family. For any desired $\varepsilon > 0$ , we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of $\gamma $ fraction of insertions and $\delta $ fraction of deletions as long as $\gamma + 2\delta \leq 1 - \varepsilon $. On the other hand, for any $\gamma, \delta $ with $\gamma + 2\delta = 1$ list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions. We further generalize our result to codes over any finite alphabet of size $q$. Surprisingly, our work reveals that the feasibility region for $q>2$ is not the natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a $(q-1)$ -piece-wise linear boundary whose $q$ corner-points lie on a quadratic curve. The main technical work in our results is proving the existence of code families of sufficiently large size with good list-decoding properties for any combination of $\delta,\gamma $ within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh and Ma, 2014]. Finally, we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate. [ABSTRACT FROM AUTHOR]
- Subjects :
- *BINARY codes
*GENERALIZATION
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 67
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 153731631
- Full Text :
- https://doi.org/10.1109/TIT.2021.3120910