List Decoding of Insertions and Deletions

Antonia Wachter-Zeh

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 with the well-known binary Varshamov-Tenengolts (VT) 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.

Introduction

Traditional error correction primarily focuses on substitution errors, measured by the Hamming distance. However, in applications like DNA data storage and network synchronization, synchronization errors—insertions and deletions (ins/del)—are more prevalent. These errors are challenging because they shift the sequence, causing a loss of alignment. While unique decoding can correct up to half the minimum distance ($d/2$), list decoding offers a more powerful alternative by returning a short list of potential codewords. This work establishes the first theoretical "Johnson-like" upper bound for list decoding in the Levenshtein metric and provides an explicit polynomial-time algorithm for list decoding Varshamov-Tenengolts (VT) codes.

Combinatorial Bounds in the Levenshtein Metric

The paper derives a Johnson-like upper bound for the Levenshtein metric by adapting techniques from Hamming space. This derivation is complex because the size of a "deletion ball" in Levenshtein space depends on the specific sequence, unlike the uniform spheres in Hamming space.

Key theoretical insights include:

  • Johnson Radius for Ins/Del: Polynomial-time list decoding is theoretically possible beyond the $d/2$ limit.
  • Error Asymmetry: The bound for deletions is mathematically "larger" than for insertions, suggesting deletions are slightly easier to list-decode.
  • Alphabet Size: The gain over unique decoding is most significant for small alphabets, such as binary ($q=2$).

Algorithmic Design for VT Codes

Varshamov-Tenengolts (VT) codes are a standard for correcting single deletions. This paper extends their utility by introducing a list decoding algorithm capable of handling multiple insertions and deletions.

The core strategy involves reducing multiple-error correction to a series of single-error corrections. For a received word with $\tau$ errors, the algorithm generates candidate sub/supersequences and applies an efficient single-error VT decoder to each.

Algorithm 2 for list decoding VT codes under insertions and deletions.

For a constant number of errors $\tau$, the algorithm runs in $O(n^{\tau-1})$ time. Specifically, for two errors ($\tau=2$), the complexity is $O(n^2)$, making it highly practical for low-error scenarios.

Results and Performance

The theoretical bounds prove that if the decoding radius $\tau$ remains below the "Johnson-like" radius $\tau_L(q)$, the list size $\ell$ is guaranteed to be polynomial in the code length $n$.

Comparison of the list decoding radius with the unique decoding radius for various parameters.

As shown in Figure 1, there is a notable improvement over the unique decoding radius, particularly when insertions and deletions are balanced ($\Delta = 0$). However, analysis also reveals a limitation: for VT codes, the list size grows exponentially if the number of deletions $\delta$ is large, though they remain efficient for a small constant number of errors.

Conclusion

This research provides both the theoretical limits and practical algorithms for list decoding in the Levenshtein metric. While the current VT list decoder is efficient for constant error counts, future work should explore code constructions that maintain polynomial-time decoding when the number of deletions scales linearly with the code length.

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 with the well-known binary Varshamov-Tenengolts (VT) 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},
}
Figure