Two-Insertion/Deletion/Substitution Correcting Codes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916100345692160 |
|---|---|
| author | Pi, Yuhang Zhang, Zhifang |
| author_facet | Pi, Yuhang Zhang, Zhifang |
| contents | In recent years, the emergence of DNA storage systems has led to a widespread focus on the research of codes correcting insertions, deletions, and classic substitutions. During the initial investigation, Levenshtein discovered the VT codes are precisely capable of correcting single insertion/deletion and then extended the VT construction to single-insertion/deletion/substitution ($1$-ins/del/sub) correcting codes. Inspired by this, we generalize the recent findings of $1$-del $1$-sub correcting codes with redundancy $6\log_{2}n+O(1)$ to more general $2$-ins/del/sub correcting codes without increasing the redundancy. Our key technique is to apply higher-order VT syndromes to distinct objects and accomplish a systematic classification of all error patterns. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_11231 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Two-Insertion/Deletion/Substitution Correcting Codes Pi, Yuhang Zhang, Zhifang Information Theory In recent years, the emergence of DNA storage systems has led to a widespread focus on the research of codes correcting insertions, deletions, and classic substitutions. During the initial investigation, Levenshtein discovered the VT codes are precisely capable of correcting single insertion/deletion and then extended the VT construction to single-insertion/deletion/substitution ($1$-ins/del/sub) correcting codes. Inspired by this, we generalize the recent findings of $1$-del $1$-sub correcting codes with redundancy $6\log_{2}n+O(1)$ to more general $2$-ins/del/sub correcting codes without increasing the redundancy. Our key technique is to apply higher-order VT syndromes to distinct objects and accomplish a systematic classification of all error patterns. |
| title | Two-Insertion/Deletion/Substitution Correcting Codes |
| topic | Information Theory |
| url | https://arxiv.org/abs/2401.11231 |