Systematic permutation codes correct multiple deletions efficiently
Order-Optimal Systematic Permutation Codes for Correcting t Deletions
Information Theory
Summary
Deleting parts of a sequence can cause problems when trying to recover the original information. The authors developed a way to add special markers to sequences so that even if multiple parts get deleted, the original order can still be figured out. Their method uses fewer extra symbols than before and works efficiently for large sequences. It applies to different types of deletions and special sequence patterns.
What this means in practice
- •For communication protocol engineers: Design channels that recover original message order after multiple deletions using efficient redundancy in transmitted sequences.
- •For data storage system developers: Improve data resilience by embedding order-preserving redundancy to correct deletion errors in stored permutation-based data formats.
Authors
Bolin Wu, Quan D. Bui, Kai Niu, Van Khu Vu, Shuche Wang
Abstract
This paper investigates the construction of full-systematic permutation codes capable of correcting multiple deletions under two complementary models, namely symbol-invariant deletions (SIDs), where surviving symbol values are preserved, and permutation-invariant deletions (PIDs), where the surviving sequence is standardized to a permutation. For any fixed integer $t \ge 1$ and all sufficiently large message lengths $n$, our proposed encoders map any message permutation of length $n$ to a codeword by inserting distinct redundancy symbols while strictly preserving the sequence order of the original message symbols. The proposed constructions correct up to $t$ deletions using $7t-1$ redundancy markers for PIDs and $4t$ redundancy markers for SIDs, achieving redundancies of $(7t-1)\log n + O_t(1)$ bits and $4t\log n + O_t(1)$ bits, respectively. Both code families are uniformly constructible, encodable, and decodable in $n^{O(t)}$ time. The underlying framework stores an inner deletion-correcting syndrome in the relative positions of redundancy markers via an algebraic outer code based on integer moments and residual graph coloring. We further extend this framework to fixed-composition and strictly $λ$-regular multipermutations, proving that the PID and SID channels coincide whenever the common multiplicity satisfies $λ> t$.