Codes improve correction of insertions and deletions in data transmission
Constant-List Insertion--Deletion Codes:New Bounds and an Improvement of Levenshtein's Lower Bound
Information Theory
Summary
Some communication errors happen when extra bits are added or some are missing, which makes fixing messages tricky. The authors look at codes that can handle a fixed number of possible corrections even as messages get longer. They found better ways to measure how much data can be safely sent while fixing such errors, especially for binary codes. Their methods improve on old estimates and help understand how to balance deleting and inserting errors with a fixed limit on possible outputs. This could make communication over noisy channels more reliable.
What this means in practice
- •For data communication engineers: Design coding schemes that better correct message insertions and deletions with limited decoding ambiguity.
- •For storage system developers: Improve error correction in data storage where bit insertions and deletions cause corruption.
Authors
Han Mao Kiah, Hengjia Wei, Ruixiao Zeng
Abstract
We study codes correcting adversarial insertions and deletions with list size $L$ fixed independently of the block length. We derive new achievable-rate bounds for binary codes and upper bounds over every fixed alphabet of size $q\ge2$, retaining explicit dependence on $L$. We establish a combinatorial reduction that trades $L$ units of insertion budget for one unit of deletion budget in the decoding guarantee, without changing the code or increasing the list size. Consequently, asymptotic bounds for mixed errors with insertion fraction $γ$ and deletion fraction $δ$ follow from insertion-only lower bounds at $γ+Lδ$ and deletion-only upper bounds at $δ+γ/L$. For binary unique decoding, we strictly improve Levenshtein's classical asymptotic rate lower bound for every deletion fraction $0<δ<1/2$ for which the classical rate expression is nonnegative. At $δ=0.1$, the lower bound increases from approximately $0.162009$ to $0.180431$, a relative increase of about $11.37\%$. Our framework also yields insertion and deletion lower bounds for every fixed list size. The existence proofs combine the Lovász local lemma with sampling from words having a specified number of runs, where a run is a maximal block of equal symbols. Generating functions provide refined bounds on the probability that $L+1$ sampled words share an allowed received word. We also derive a Levenshtein-type upper bound by run counting and, separately, a higher-order Elias bound using intersections and unions of the position sets used to embed $L+1$ codewords in a common supersequence. The latter recovers Yasunaga's asymptotic unique-decoding bound at $L=1$ and strictly improves the Haeupler--Shahrasbi--Sudan insertion bound for every fixed $L$ and $0<γ<q-1$. Numerical comparisons quantify the gains and remaining gaps.