Metraipolis › archive › dc_89de6be02a10
Order-Optimal Systematic Permutation Codes for Correcting t Deletions — arXiv:2609.37578
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.37578
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T18:36:47.444Z
- SHA-256 of the archived text
fd50ed37fac099d636e565b5da5764ad8aacca35656c37399180c09fc29bcd9c- Stable URL of this page
https://metraipolis.com/documento/dc_89de6be02a10
How to cite
Order-Optimal Systematic Permutation Codes for Correcting t Deletions — arXiv:2609.37578 — arXiv (en), https://arxiv.org/abs/2609.37578 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_89de6be02a10 (Metraipolis archive dc_89de6be02a10, sha256 fd50ed37fac099d636e565b5da5764ad8aacca35656c37399180c09fc29bcd9c)
BibTeX
@misc{dc89de6be02a10,
title = {Order-Optimal Systematic Permutation Codes for Correcting t Deletions — arXiv:2609.37578},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.37578},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_89de6be02a10; sha256 fd50ed37fac099d636e565b5da5764ad8aacca35656c37399180c09fc29bcd9c},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.37578. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\lambda$-regular multipermutations, proving that the PID and SID channels coincide whenever the common multiplicity satisfies $\lambda > t$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-30 in math.IT).
Categorie arXiv: Information Theory (cs.IT).
Pagina del lavoro: https://arxiv.org/abs/2609.37578 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T18:02:53.472Z dalla pagina https://arxiv.org/catchup/math.IT/2026-09-30?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).