On the Maximum Size of Codes Under the Damerau-Levenshtein Metric
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_ | 1866911042384166912 |
|---|---|
| author | Ye, Zuo Ge, Gennian |
| author_facet | Ye, Zuo Ge, Gennian |
| contents | The Damerau-Levenshtein distance between two sequences is the minimum number of operations (deletions, insertions, substitutions, and adjacent transpositions) required to convert one sequence into another. Notwithstanding a long history of this metric, research on error-correcting codes under this distance has remained limited. Recently, motivated by applications in DNA-based storage systems, Gabrys \textit{et al} and Wang \texit{et al} reinvigorated interest in this metric. In their works, some codes correcting both deletions and adjacent transpositions were constructed. However, theoretical upper bounds on code sizes under this metric have not yet been established. This paper seeks to establish upper bounds for code sizes in the Damerau-Levenshtein metric. Our results show that the code correcting one deletion and asymmetric adjacent transpositions proposed by Wang \textit{et al} achieves optimal redundancy up to an additive constant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_04806 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Maximum Size of Codes Under the Damerau-Levenshtein Metric Ye, Zuo Ge, Gennian Information Theory The Damerau-Levenshtein distance between two sequences is the minimum number of operations (deletions, insertions, substitutions, and adjacent transpositions) required to convert one sequence into another. Notwithstanding a long history of this metric, research on error-correcting codes under this distance has remained limited. Recently, motivated by applications in DNA-based storage systems, Gabrys \textit{et al} and Wang \texit{et al} reinvigorated interest in this metric. In their works, some codes correcting both deletions and adjacent transpositions were constructed. However, theoretical upper bounds on code sizes under this metric have not yet been established. This paper seeks to establish upper bounds for code sizes in the Damerau-Levenshtein metric. Our results show that the code correcting one deletion and asymmetric adjacent transpositions proposed by Wang \textit{et al} achieves optimal redundancy up to an additive constant. |
| title | On the Maximum Size of Codes Under the Damerau-Levenshtein Metric |
| topic | Information Theory |
| url | https://arxiv.org/abs/2507.04806 |