Redundancy-Optimal Constructions of $(1,1)$-Criss-Cross Deletion Correcting Codes with Efficient Encoding/Decoding Algorithms
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914329515786240 |
|---|---|
| author | Liu, Wenhao Jiang, Zhengyi Huang, Zhongyi Hou, Hanxu |
| author_facet | Liu, Wenhao Jiang, Zhengyi Huang, Zhongyi Hou, Hanxu |
| contents | Two-dimensional error-correcting codes, where codewords are represented as $n \times n$ arrays over a $q$-ary alphabet, find important applications in areas such as QR codes, DNA-based storage, and racetrack memories. Among the possible error patterns, $(t_r,t_c)$-criss-cross deletions-where $t_r$ rows and $t_c$ columns are simultaneously deleted-are of particular significance. In this paper, we focus on $q$-ary $(1,1)$-criss-cross deletion correcting codes. We present a novel code construction and develop complete encoding, decoding, and data recovery algorithms for parameters $n \ge 11$ and $q \ge 3$. The complexity of the proposed encoding, decoding, and data recovery algorithms is $\mathcal{O}(n^2)$. Furthermore, we show that for $n \ge 11$ and $q = Ω(n)$ (i.e., there exists a constant $c>0$ such that $q \ge cn$), both the code redundancy and the encoder redundancy of the constructed codes are $2n + 2\log_q n + \mathcal{O}(1)$, which attain the lower bound ($2n + 2\log_q n - 3$) within an $\mathcal{O}(1)$ gap. To the best of our knowledge, this is the first construction that can achieve the optimal redundancy with only an $\mathcal{O}(1)$ gap, while simultaneously featuring explicit encoding and decoding algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_13548 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Redundancy-Optimal Constructions of $(1,1)$-Criss-Cross Deletion Correcting Codes with Efficient Encoding/Decoding Algorithms Liu, Wenhao Jiang, Zhengyi Huang, Zhongyi Hou, Hanxu Information Theory Two-dimensional error-correcting codes, where codewords are represented as $n \times n$ arrays over a $q$-ary alphabet, find important applications in areas such as QR codes, DNA-based storage, and racetrack memories. Among the possible error patterns, $(t_r,t_c)$-criss-cross deletions-where $t_r$ rows and $t_c$ columns are simultaneously deleted-are of particular significance. In this paper, we focus on $q$-ary $(1,1)$-criss-cross deletion correcting codes. We present a novel code construction and develop complete encoding, decoding, and data recovery algorithms for parameters $n \ge 11$ and $q \ge 3$. The complexity of the proposed encoding, decoding, and data recovery algorithms is $\mathcal{O}(n^2)$. Furthermore, we show that for $n \ge 11$ and $q = Ω(n)$ (i.e., there exists a constant $c>0$ such that $q \ge cn$), both the code redundancy and the encoder redundancy of the constructed codes are $2n + 2\log_q n + \mathcal{O}(1)$, which attain the lower bound ($2n + 2\log_q n - 3$) within an $\mathcal{O}(1)$ gap. To the best of our knowledge, this is the first construction that can achieve the optimal redundancy with only an $\mathcal{O}(1)$ gap, while simultaneously featuring explicit encoding and decoding algorithms. |
| title | Redundancy-Optimal Constructions of $(1,1)$-Criss-Cross Deletion Correcting Codes with Efficient Encoding/Decoding Algorithms |
| topic | Information Theory |
| url | https://arxiv.org/abs/2602.13548 |