Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets
Abstract
We construct systematic q-ary codes correcting two deletions with three redundant symbols over polynomial-size alphabets. For every information length n≥2, our first construction has length n+3 over an alphabet of size q=2s<232n7 for some integer s, with polynomial-time encoding and decoding. A cardinality bound of Liu and Xing implies that three redundant symbols are necessary, so the construction is optimal in this measure. We also establish the existence of systematic codes with the same redundancy over alphabets of size O(n4), leaving efficient encoding and decoding at that alphabet scale open. For a single burst of at most two adjacent deletions, we give a polynomial-time systematic construction with three redundant symbols over a power-of-two alphabet of size q<(n+2)4. A converse bound for adjacent deletions shows that three redundant symbols are again optimal for n≥2.
Related
- Order-Optimal Systematic Permutation Codes for Correcting t Deletions
- The probabilistic bound for perfect hashing is sharp only for binary alphabets
- A Layered Simplex Architecture for Large Alphabets
- Unique ergodicity, and not, for primitive substitutions on compact alphabets containing isolated points
- New upper and lower bounds on covering codes K_q(n,R) for alphabets of size 5 <= q <= 21
BibTeX
@misc{valery2026systematic,
title = {{Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets}},
author = {Valery and Grishin and Aryeh Lev Zabokritskiy},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.38259},
eprint = {2609.38259},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38259},
}
RIS
TY - UNPB
TI - Systematic Codes Correcting Two Deletions with Three Redundant Symbols over Large Alphabets
AU - Valery
AU - Grishin
AU - Aryeh Lev Zabokritskiy
PY - 2026
DA - 2026/10/21
PB - arXiv
DO - 10.48550/arxiv.2609.38259
UR - https://arxiv.org/abs/2609.38259
AB - We construct systematic q-ary codes correcting two deletions with three redundant symbols over polynomial-size alphabets. For every information length n≥2, our first construction has length n+3 over an alphabet of size q=2^s<2^32n^7 for some integer s, with polynomial-time encoding and decoding. A cardinality bound of Liu and Xing implies that three redundant symbols are necessary, so the construction is optimal in this measure. We also establish the existence of systematic codes with the same redundancy over alphabets of size O(n^4), leaving efficient encoding and decoding at that alphabet scale open. For a single burst of at most two adjacent deletions, we give a polynomial-time systematic construction with three redundant symbols over a power-of-two alphabet of size q<(n+2)^4. A converse bound for adjacent deletions shows that three redundant symbols are again optimal for n≥2.
ER -