List Decoding of Insertions and Deletions

Antonia Wachter-Zeh

TL;DR

This paper establishes the first theoretical "Johnson-like" upper bound for list decoding in the Levenshtein metric, proving that we can recover information even when the number of insertions and deletions exceeds half the code's minimum distance. Additionally, it provides the first explicit polynomial-time algorithm for list decoding the classic Varshamov-Tenengolts (VT) codes, which are a staple in synchronization error correction.

What Problem Does This Paper Address?

In traditional coding theory, we usually deal with substitutions (Hamming distance)—where a '0' turns into a '1'. However, in emerging fields like DNA data storage and high-speed network synchronization, the primary errors are insertions and deletions (ins/del). These are much harder to handle because they shift the entire sequence, causing a loss of synchronization.

The "gold standard" for error correction is often unique decoding, which can only correct up to $d/2$ errors (where $d$ is the minimum distance of the code). List decoding is a more powerful paradigm: instead of returning one codeword, the decoder returns a short list of all possible codewords within a certain radius. While list decoding is well-understood for Hamming distance, its application to the Levenshtein metric (which counts ins/del) remained largely unexplored. This paper fills that gap by providing both the theoretical limits (bounds) and a practical way to reach them (algorithms).

Methods

The author employs three primary approaches:

  1. Combinatorial Bound Derivation: To find the "Johnson-like" upper bound, the author adapts techniques used in Hamming space (by Bassalygo and Roth) to the Levenshtein metric. This is non-trivial because, unlike Hamming spheres, the size of a "deletion ball" depends on the specific sequence, not just the radius.
  2. Lower Bound Analysis: By using the pigeonhole principle and the properties of supersequences, the author proves that for certain codes (like VT codes), the list size must grow exponentially if the number of deletions is large.
  3. Algorithmic Design: The paper introduces a list decoding algorithm for VT codes. The core idea is to reduce the problem of correcting multiple errors into a series of single-error corrections. For a received word with $\tau$ errors, the algorithm generates all possible sub/supersequences that could have resulted from a single error and applies a known efficient single-error VT decoder to each.

Datasets

As a theoretical contribution to coding theory, this paper does not use empirical datasets or machine learning benchmarks. Instead, it evaluates the performance of Varshamov-Tenengolts (VT) codes, which are a specific class of binary codes designed to correct single deletions. The "evaluation" consists of mathematical proofs and complexity analysis.

Key Insights and Ideas

  • The Johnson Radius for Ins/Del: The paper proves that polynomial-time list decoding is theoretically possible beyond the $d/2$ limit for the Levenshtein metric. The derived bound depends on the code length, the alphabet size, and the length of the received word.
  • Asymmetry of Errors: Interestingly, the Johnson-like bound for deletions is "larger" than the one for insertions. This suggests that, mathematically speaking, it is slightly easier to list-decode deletions than insertions.
  • Alphabet Size Matters: Similar to the Hamming metric, the size of the alphabet ($q$) significantly impacts the decoding radius. The improvement over unique decoding is most pronounced for small alphabets (like binary, $q=2$).
  • VT Code Limitations: While VT codes are excellent for unique decoding of a single error, the author shows that their list size grows exponentially with the number of deletions $\delta$. However, if the number of errors is a small constant, they remain highly efficient.

Key Results

  • Main Theorem: The author provides a concrete formula (Theorem 1) for the maximum list size $\ell$. If the decoding radius $\tau$ is below a specific "Johnson-like" radius $\tau_L(q)$, the list size is guaranteed to be small (polynomial in the code length $n$).
  • VT List Decoder: The proposed algorithm for VT codes can correct a constant number of insertions/deletions $\tau$ in $O(n^{\tau-1})$ time. For the specific case of two errors ($\tau=2$), the complexity is $O(n^2)$, making it very practical.
  • Visualizing the Gain: Figure 1 in the paper illustrates the "decoding radius" gain. It shows a notable improvement over the unique decoding radius, especially when the number of insertions and deletions are balanced ($\Delta = 0$).

Limitations and Future Work

The primary limitation is that the proposed VT list decoding algorithm is only "efficient" (polynomial time) when the number of errors $\tau$ is a constant. If the number of errors scales linearly with the code length $n$ (e.g., 10% of bits are deleted), the algorithm's complexity becomes exponential.

The author suggests that future research should focus on:

  • Finding specific code constructions that allow for polynomial-time list decoding even when the number of deletions grows linearly with $n$.
  • Tightening the lower bounds for general codes in the Levenshtein metric, as the current lower bound is specific to VT codes.

Summary updated

Abstract

List decoding of insertions and deletions in the Levenshtein metric is considered. The Levenshtein distance between two sequences is the minimum number of insertions and deletions needed to turn one of the sequences into the other. In this paper, a Johnson-like upper bound on the maximum list size when list decoding in the Levenshtein metric is derived. This bound depends only on the length and minimum Levenshtein distance of the code, the length of the received word, and the alphabet size. It shows that polynomial-time list decoding beyond half the Levenshtein distance is possible for many parameters. Further, we also prove a lower bound on list decoding of deletions with the well-known binary Varshamov-Tenengolts codes, which shows that the maximum list size grows exponentially with the number of deletions. Finally, an efficient list decoding algorithm for two insertions/deletions with VT codes is given. This decoder can be modified to a polynomial-time list decoder of any constant number of insertions/deletions.
BibTeX
@article{wachterzeh2018list,
  author = {Antonia Wachter-Zeh},
  title = {{List Decoding of Insertions and Deletions}},
  journal = {IEEE Trans. Information Theory},
  year = {2018},
  url = {https://openreview.net/forum?id=0gHgc8M_Fw},
}

Loading related content...

Figure