Back to Search
Start Over
An Improved Bound on the Fraction of Correctable Deletions.
- Source :
-
IEEE Transactions on Information Theory . Jan2017, Vol. 63 Issue 1, p93-103. 11p. - Publication Year :
- 2017
-
Abstract
- We consider codes over fixed alphabets against worst case symbol deletions. For any fixed k \ge 2 , we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst case deletion fraction approaching 1-(2/(k+\sqrt k)) . In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/(\sqrt 2 +1)=\sqrt 2-1 \approx 0.414 . Previously, even non-constructively, the largest deletion fraction known to be correctable with positive rate was 1-\Theta (1/\sqrt k) , and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for $k$ -ary codes as 1-\Theta (1/k)$ , since 1-1/k$ is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between and 1/2 for the limit of worst case deletions correctable by binary codes remains a tantalizing open question. [ABSTRACT FROM PUBLISHER]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 63
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 120414448
- Full Text :
- https://doi.org/10.1109/TIT.2016.2621044