Linear code bounds limit corrections for insertion and deletion errors
A Generalized Half-Singleton Bound for List Decoding of Insertion/Deletion Errors
Information Theory
Summary
Correcting mistakes where parts of data get added or removed is tricky. The paper finds limits on how much such errors a certain kind of code (linear codes) can fix when you allow multiple guesses. It also shows a way to make codes that fix exactly one such error while being as efficient as possible. These ideas apply to codes built over alphabets with three or more symbols.
What this means in practice
- •For network protocol engineers: Design communication protocols that handle insertion and deletion errors more effectively by understanding the limits of linear code error correction.
- •For storage system architects: Develop storage error correction schemes that correct one insdel error with optimal code rates in systems using non-binary alphabets.
A theory result. No direct application yet.
Authors
Neehar Verma, Camilla Hollanti, Razane Tajeddine
Abstract
We derive an upper bound on the rate of a linear code capable of list decoding from insertion and deletion errors. Subsequently, we show that a linear code can list decode from at most $n - \frac{L}{L+1}k + 1$ insdel errors with fixed list size $L$, and that this bound is strict when the code does not contain the all-ones vector. We also provide a simple construction of codes achieving the optimal rate for any given list size capable of correcting a single insdel error. All the results hold for linear codes over finite fields of size $q \geq 3$.