EUVIMEDEUVIMED entdecken
Crossref

Criss-Cross Deletion Correcting Codes: Optimal Constructions With Efficient Decoders

Yubo Sun, Gennian Ge

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →