Explicit codes correct mixed insertions deletions and substitutions

Explicit Edit Codes via Multicoloring

Information TheoryDiscrete MathematicsData Structures and Algorithms

Summary

Fixing mistakes in sequences of symbols, like typos or dropped parts, is a classic challenge. The authors build special codes that can explicitly correct mixed errors of insertions, deletions, and substitutions with as little extra information as theoretically possible. They create these codes by assigning multiple ‘colors’ to parts of messages and carefully encoding these so errors can be detected and fixed efficiently. Their method comes with algorithms that can encode and decode messages with some computational cost but guarantees the lowest known overhead.

What this means in practice

  • For data storage engineers: Create storage codes resilient to mixed insertion, deletion, and substitution faults with minimal redundancy overhead.
  • For communication system designers: Design communication protocols that efficiently correct a fixed number of mixed edit errors with guaranteed low redundancy.

Authors

Huiling Xie, Zitan Chen

Abstract

For any fixed integers $q\ge2$ and $t\ge1$, we construct explicit $q$-ary codes of length $n$ that correct any combination of at most $t$ insertions, deletions, and substitutions, with redundancy at most $2t\log_q n+O_{q,t}(\log\log n)$ $q$-ary symbols. This matches the leading redundancy term of Levenshtein's classical existential bound. Building on the standard graph-coloring approach, we use a prime-based multicoloring of the edit-confusion graph to assign multiple colors to each $q$-ary word of length $m<n$. Appending a short, edit-protected representation of an assigned color to the length-$m$ word yields a length-$n$ codeword. The choice among the assigned colors carries additional message information, thereby reducing the redundancy. The construction admits deterministic encoding and decoding in $\widetilde O_{q,t}(n^{6t+2})$ and $\widetilde O_{q,t}(n^{7t+2})$ time, respectively.