Asymptotically Optimal Codes Correcting One Substring Edit
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866908455557660672 |
|---|---|
| author | Li, Yuting Tang, Yuanyuan Lou, Hao Gabrys, Ryan Farnoud, Farzad |
| author_facet | Li, Yuting Tang, Yuanyuan Lou, Hao Gabrys, Ryan Farnoud, Farzad |
| contents | The substring edit error is the operation of replacing a substring $u$ of $x$ with another string $v$, where the lengths of $u$ and $v$ are bounded by a given constant $k$. It encompasses localized insertions, deletions, and substitutions within a window. Codes correcting one substring edit have redundancy at least $\log n+k$. In this paper, we construct codes correcting one substring edit with redundancy $\log n+O(\log \log n)$, which is asymptotically optimal. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13808 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Asymptotically Optimal Codes Correcting One Substring Edit Li, Yuting Tang, Yuanyuan Lou, Hao Gabrys, Ryan Farnoud, Farzad Information Theory G.2.1 The substring edit error is the operation of replacing a substring $u$ of $x$ with another string $v$, where the lengths of $u$ and $v$ are bounded by a given constant $k$. It encompasses localized insertions, deletions, and substitutions within a window. Codes correcting one substring edit have redundancy at least $\log n+k$. In this paper, we construct codes correcting one substring edit with redundancy $\log n+O(\log \log n)$, which is asymptotically optimal. |
| title | Asymptotically Optimal Codes Correcting One Substring Edit |
| topic | Information Theory G.2.1 |
| url | https://arxiv.org/abs/2507.13808 |