Deletion-correcting codes for an adversarial nanopore channel
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_ | 1866918365564502016 |
|---|---|
| author | Xie, Huiling Chen, Zitan |
| author_facet | Xie, Huiling Chen, Zitan |
| contents | We study deletion-correcting codes for an adversarial nanopore channel in which at most $t$ deletions may occur. We propose an explicit construction of $q$-ary codes of length $n$ for this channel with $2t\log_q n+Θ(\log\log n)$ redundant symbols. We also show that the optimal redundancy is between $t\log_q n+Ω(1)$ and $2t\log_q n-\log_q\log_2 n+O(1)$, so our explicit construction matches the existential upper bound to first order. In contrast, for the classical adversarial $q$-ary deletion channel, the smallest redundancy achieved by known explicit constructions that correct up to $t$ deletions is $4t(1+ε)\log_q n+o(\log n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_21236 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Deletion-correcting codes for an adversarial nanopore channel Xie, Huiling Chen, Zitan Information Theory Discrete Mathematics Data Structures and Algorithms We study deletion-correcting codes for an adversarial nanopore channel in which at most $t$ deletions may occur. We propose an explicit construction of $q$-ary codes of length $n$ for this channel with $2t\log_q n+Θ(\log\log n)$ redundant symbols. We also show that the optimal redundancy is between $t\log_q n+Ω(1)$ and $2t\log_q n-\log_q\log_2 n+O(1)$, so our explicit construction matches the existential upper bound to first order. In contrast, for the classical adversarial $q$-ary deletion channel, the smallest redundancy achieved by known explicit constructions that correct up to $t$ deletions is $4t(1+ε)\log_q n+o(\log n)$. |
| title | Deletion-correcting codes for an adversarial nanopore channel |
| topic | Information Theory Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2601.21236 |