Order-Optimal Systematic Permutation Codes for Correcting t Deletions
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 ≥ 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 + Ot(1) bits and 4tlog n + Ot(1) bits, respectively. Both code families are uniformly constructible, encodable, and decodable in nO(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.
Related
- Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets
- Substring Edit Correcting Codes and Optimal Single Burst-Deletion Correcting Codes
- Balanced weightings and permutation matchings applied to the monoid of order-preserving mappings
- SWAP: A Scalable, Warm-Startable, Anytime Permutation Solver for Optimal Transport
- On first-order limiting probabilities for small permutation classes
BibTeX
@misc{wu2026orderoptimal,
title = {{Order-Optimal Systematic Permutation Codes for Correcting t Deletions}},
author = {Bolin Wu and Quan D. Bui and Kai Niu and Van Khu Vu and Shuche Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37578},
eprint = {2609.37578},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37578},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Order-Optimal Systematic Permutation Codes for Correcting t Deletions
AU - Bolin Wu
AU - Quan D. Bui
AU - Kai Niu
AU - Van Khu Vu
AU - Shuche Wang
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37578
UR - https://arxiv.org/abs/2609.37578
AB - 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 ≥ 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 4tlog 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.
ER -