Criss-Cross Deletion Correcting Codes: Optimal Constructions With Efficient Decoders
IEEE Transactions on Information Theory · 2026-07 · 72 (7) · 4648-4660
DOI: 10.1109/tit.2026.3696242 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-07. Verfasst von Yubo Sun und 1 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref). Gefördert von: National Key Research and Development Program of China, National Natural Science Foundation of China, Beijing Scholars Program.
Abstract (Originalsprache)
This paper addresses fundamental challenges in two-dimensional error correction by constructing optimal codes for criss-cross deletions . We consider an $ n \times n $ array $\boldsymbol {X}$ over a $ q $ -ary alphabet $\Sigma _{q}:= \{0, 1, \ldots, q-1\}$ that is subject to a $(t_{r}, t_{c})$ -criss-cross deletion , which involves the simultaneous removal of $ t_{r} $ rows and $ t_{c} $ columns. A code $\mathcal {C} \subseteq \Sigma _{q}^{n \times n}$ is defined as a $(t_{r},t_{c})$ -criss-cross deletion correcting code if it can successfully correct these deletions. Our primary technical contributions are as follows: 1) Theoretical Bounds: We derive a sphere-packing type lower bound and a Gilbert-Varshamov type upper bound on the redundancy of optimal codes. Our results indicate that the optimal redundancy for a $(t_{r}, t_{c})$ -criss-cross deletion correcting code lies between $(t_{r} + t_{c})n\log q + (t_{r} + t_{c})\log n + O_{q,t_{r},t_{c}}(1)$ and $(t_{r} + t_{c})n\log q + 2(t_{r} + t_{c})\log n + O_{q,t_{r},t_{c}}(1)$ , where the logarithm is on base two, and $O_{q,t_{r},t_{c}}(1)$ is a constant that depends solely on $q$ , $t_{r}$ , and $t_{c}$ . 2) Optimal Constructions: For the case of $(1,1)$ -criss-cross deletions, we propose two families of constructions that achieve $2n\log q + 2\log n + O_{q}(1)$ bits of redundancy. This redundancy is optimal up to an additive constant term $O_{q}(1)$ , which depends solely on $q$ . One family is designed for non-binary alphabets, while the other addresses arbitrary alphabets. For the case of $(t_{r}, t_{c})$ -criss-cross deletions, we provide a strategy to derive optimal codes when both unidirectional deletions occur consecutively. 3) Efficient Decoders: We propose decoding algorithms with a time complexity of $O(n^{2})$ for our codes, which are optimal for two-dimensional scenarios.
Förderung
- National Key Research and Development Program of China
- National Natural Science Foundation of China
- Beijing Scholars Program
Zitieren
APA
Sun, Y., & Ge, G. (2026). Criss-Cross Deletion Correcting Codes: Optimal Constructions With Efficient Decoders. IEEE Transactions on Information Theory, 72(7), 4648-4660. https://doi.org/10.1109/tit.2026.3696242
Vancouver
Sun Y, Ge G. Criss-Cross Deletion Correcting Codes: Optimal Constructions With Efficient Decoders. IEEE Transactions on Information Theory. 2026;72(7):4648-4660. doi:10.1109/tit.2026.3696242
BibTeX
@article{Sun2026,
author = {Sun, Yubo and Ge, Gennian},
title = {Criss-Cross Deletion Correcting Codes: Optimal Constructions With Efficient Decoders},
journal = {IEEE Transactions on Information Theory},
year = {2026},
volume = {72},
number = {7},
pages = {4648--4660},
doi = {10.1109/tit.2026.3696242}
}
EUVIMED