Near Optimal Code Construction for the Adversarial Torn Paper Channel With Edit Errors
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908776519434240 |
|---|---|
| author | Abu-Sini, Maria Heckel, Reinhard |
| author_facet | Abu-Sini, Maria Heckel, Reinhard |
| contents | Motivated by DNA storage systems and 3D fingerprinting, this work studies the adversarial torn paper channel with edit errors. This channel first applies at most $t_e$ edit errors (i.e., insertions, deletions, and substitutions) to the transmitted word and then breaks it into $t+1$ fragments at arbitrary positions. In this paper, we construct a near optimal error correcting code for this channel, which will be referred to as a $t$-breaks $t_e$-edit-errors resilient code. This code enables reconstructing the transmitted codeword from the $t+1$ noisy fragments. Moreover, we study list decoding of the torn paper channel by deriving bounds on the size of the list (of codewords) obtained from cutting a codeword of a $t$-breaks resilient code $t'$ times, where $t' > t$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_14088 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Near Optimal Code Construction for the Adversarial Torn Paper Channel With Edit Errors Abu-Sini, Maria Heckel, Reinhard Information Theory Motivated by DNA storage systems and 3D fingerprinting, this work studies the adversarial torn paper channel with edit errors. This channel first applies at most $t_e$ edit errors (i.e., insertions, deletions, and substitutions) to the transmitted word and then breaks it into $t+1$ fragments at arbitrary positions. In this paper, we construct a near optimal error correcting code for this channel, which will be referred to as a $t$-breaks $t_e$-edit-errors resilient code. This code enables reconstructing the transmitted codeword from the $t+1$ noisy fragments. Moreover, we study list decoding of the torn paper channel by deriving bounds on the size of the list (of codewords) obtained from cutting a codeword of a $t$-breaks resilient code $t'$ times, where $t' > t$. |
| title | Near Optimal Code Construction for the Adversarial Torn Paper Channel With Edit Errors |
| topic | Information Theory |
| url | https://arxiv.org/abs/2601.14088 |