Back to Search
Start Over
EFFICIENT LINEAR AND AFFINE CODES FOR CORRECTING INSERTIONS/DELETIONS.
- Source :
-
SIAM Journal on Discrete Mathematics . 2023, Vol. 37 Issue 2, p748-778. 31p. - Publication Year :
- 2023
-
Abstract
- This paper studies linear and affine error-correcting codes for correcting synchronization errors such as insertions and deletions. We call such codes linear/affine insdel codes. Linear codes that can correct even a single deletion are limited to having an information rate at most 1/2 (achieved by the trivial two fold repetition code). Previously, it was (erroneously) reported that more generally no nontrivial linear codes correcting k deletions exist, i.e., that the (k + 1)-fold repetition codes and its rate of 1/(k + 1) are basically optimal for any k. We disprove this and show the existence of binary linear codes of length n and rate just below 1/2 capable of correcting \Omega(n) insertions and deletions. This identifies rate 1/2 as a sharp threshold for recovery from deletions for linear codes and reopens the quest for a better understanding of the capabilities of linear codes for correcting insertions/deletions. We prove novel outer bounds and existential inner bounds for the rate vs. (edit) distance trade-off of linear insdel codes. We complement our existential results with an efficient synchronization-string-based transformation that converts any asymptotically good linear code for Hamming errors into an asymptotically good linear code for insdel errors. Last, we show that the 2 -rate limitation does not hold for affine codes by giving an explicit affine code of rate 1 - e epsilon which can efficiently correct a constant fraction of insdel errors. [ABSTRACT FROM AUTHOR]
- Subjects :
- *LINEAR codes
*ERROR-correcting codes
*BINARY codes
*HAMMING codes
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 37
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 169719879
- Full Text :
- https://doi.org/10.1137/21M142798X