VT codes show easier list decoding for insertions than deletions
On the Average List Size of VT Codes under Two Insertions or Two Deletions
Information Theory
Summary
When fixing errors in data, some errors are insertions (extra bits added) and some are deletions (bits missing). The paper studies a special kind of code called VT codes to see how many possible original messages come up when there are two errors, either insertions or deletions. The authors find that for two insertions, the average number of possible messages is about half as many as for two deletions. This means it's generally easier to narrow down the original message when errors are insertions rather than deletions.
What this means in practice
- •For communication engineers: Assess error-correcting code performance under insertion and deletion errors for designing more reliable data transmission systems.
- •For storage system developers: Improve data recovery processes by understanding how insertion errors can be corrected more efficiently than deletion errors in storage media.
A theory result. No direct application yet.
Authors
Anisha Banerjee, Roni Con, Antonia Wachter-Zeh, Eitan Yaakobi
Abstract
Levenshtein's classical theorem shows that any code that can uniquely decode from \(t\) deletions can also uniquely decode from \(t\) insertions. This symmetry, however, does not generally hold in the list-decoding regime. Several prior results on the capacity and radii of list-decoding from insertions and deletions suggest that insertions are easier to handle than deletions. In an effort to better understand this asymmetry between insertions and deletions under list-decoding, we study an analogous version of McEliece's \emph{average list size problem}. More precisely, given a binary code \(\mathcal{C}\) of length \(n\) that uniquely corrects \(t'\) insertions (or deletions), we are interested in the average number of codewords returned by a \(t\)-insertion (or deletion) list decoder, where \(t' < t\). Focusing on the case of \(t'=1\) and \(t=2\), we find that under two insertions, this quantity is at most \((n+12)/4\) for any VT code of length \(n\), whereas under two deletions it is at least \(n/2 - 10\) when averaged over all length-\(n\) VT codes. The nearly factor-of-two gap between these upper and lower bounds serves to confirm the relative ease of list-decoding of insertions compared to deletions from an average-case perspective.