Binary codes correct multiple edits efficiently with low redundancy
Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert-Varshamov Bound
Information Theory
Summary
It's hard to fix messages that get changed by mistakes like missing or extra bits. This paper shows how to create special codes that can correct a fixed number of these errors while keeping extra information small. The authors developed methods to build, send, and fix these codes quickly using algorithms. Their approach matches the best theoretical guarantees without trying every possible message.
What this means in practice
- •For data storage engineers: Implement codes that reliably recover data corrupted by insertions, deletions, or substitutions while minimizing extra space.
- •For communication system developers: Design encoding and decoding processes that efficiently correct multiple types of errors in transmitted binary data streams.
Authors
Ryan Gabrys, Shubhransh Singhvi, Eitan Yaakobi
Abstract
We construct binary codes that attain the classical Gilbert-Varshamov redundancy guarantee for a fixed number of edit errors, with deterministic polynomial-time construction, encoding, and decoding. For every fixed integer $t\ge 1$ and all sufficiently large block lengths $n$, our codes correct any combination of at most $t$ insertions, deletions, and substitutions in total, with redundancy at most $2t\log_2 n+O_t(1)$. All algorithms run in polynomial time in $n$ for fixed $t$, and decoding recovers the original information message. This realizes the classical counting guarantee algorithmically without enumerating the exponentially large space of binary words.