Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.07607 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912663438622720 |
|---|---|
| author | Sun, Yubo Ge, Gennian |
| author_facet | Sun, Yubo Ge, Gennian |
| contents | This paper addresses fundamental challenges in two-dimensional error correction by constructing optimal codes for \emph{criss-cross deletions}. We consider an $ n \times n $ array $\boldsymbol{X}$ over a $ q $-ary alphabet $Σ_q := \{0, 1, \ldots, q-1\}$ that is subject to a \emph{$(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 Σ_q^{n \times n}$ is defined as a \emph{$(t_r,t_c)$-criss-cross deletion correcting code} if it can successfully correct these deletions.
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$. 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. We propose decoding algorithms with a time complexity of $O(n^2)$ for our codes, which are optimal for two-dimensional scenarios. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_07607 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Criss-Cross Deletion Correcting Codes: Optimal Constructions with Efficient Decoders Sun, Yubo Ge, Gennian Information Theory This paper addresses fundamental challenges in two-dimensional error correction by constructing optimal codes for \emph{criss-cross deletions}. We consider an $ n \times n $ array $\boldsymbol{X}$ over a $ q $-ary alphabet $Σ_q := \{0, 1, \ldots, q-1\}$ that is subject to a \emph{$(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 Σ_q^{n \times n}$ is defined as a \emph{$(t_r,t_c)$-criss-cross deletion correcting code} if it can successfully correct these deletions. 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$. 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. We propose decoding algorithms with a time complexity of $O(n^2)$ for our codes, which are optimal for two-dimensional scenarios. |
| title | Criss-Cross Deletion Correcting Codes: Optimal Constructions with Efficient Decoders |
| topic | Information Theory |
| url | https://arxiv.org/abs/2506.07607 |