New deletion codes reduce data loss with fewer extra bits
Polynomially larger deletion codes by linear hashing of substring counts
Information Theory
Summary
Data sometimes gets messed up when some parts are lost or deleted, like missing words in a text message. This paper shows a better way to fix two or more deletions in binary data by using fewer extra bits than before, improving how efficiently errors can be corrected. The authors create these codes by cleverly counting patterns inside the data and grouping similar pieces using a kind of hashing, then sorting out confusing cases so they can still tell everything apart.
What this means in practice
- •For communication system engineers: Design communication protocols that detect and fix two or more deletions in transmitted binary data with fewer extra bits, improving bandwidth efficiency.
- •For storage system designers: Create error-correcting schemes for storage devices that better handle data loss due to deletions by using codes with reduced redundancy.
A theory result. No direct application yet.
Authors
Eyal En Gad
Abstract
We show that binary codes of length $n$ correcting two deletions exist with redundancy $3\log_2n+O(\log_2\log_2n)$. The previous best upper bound had leading coefficient $4$, unchanged since 1965, while the best known lower bound has coefficient $2$. More generally, codes correcting $t\ge2$ deletions exist with redundancy $(2t-1)\log_2n+O_t(\log_2\log_2n)$, improving the coefficient $2t$. We extract a code from one label class of a random linear hash of substring counts, with about $n$ times fewer labels than a direct construction. Confusable words that still share a label are separated by a two-colouring after discarding the words in components with odd cycles, and these are few because an odd cycle forces the edits along it to overlap.