Bounds on Codes Correcting Transpositions of Consecutive Symbols
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909980731375616 |
|---|---|
| author | Kovačević, Mladen Goyal, Keshav Kiah, Han Mao |
| author_facet | Kovačević, Mladen Goyal, Keshav Kiah, Han Mao |
| contents | The problem of correcting transpositions (or swaps) of consecutive symbols in $ q $-ary strings is studied. Lower bounds on asymptotically achievable rates of codes correcting $ t = τn $ transpositions are derived. The first bound is obtained by analyzing the average cardinality of ``transposition balls'' and evaluating the appropriate version of the generalized Gilbert--Varshamov bound, while the second bound follows from a construction of codes correcting an arbitrary number of transpositions (i.e., zero-error codes). Asymptotic bounds on the cardinality of optimal codes correcting $ t = \textrm{const} $ transpositions are also derived. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_06692 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Bounds on Codes Correcting Transpositions of Consecutive Symbols Kovačević, Mladen Goyal, Keshav Kiah, Han Mao Information Theory Discrete Mathematics 94B25, 94B50, 94B65, 68P30, 68R05 The problem of correcting transpositions (or swaps) of consecutive symbols in $ q $-ary strings is studied. Lower bounds on asymptotically achievable rates of codes correcting $ t = τn $ transpositions are derived. The first bound is obtained by analyzing the average cardinality of ``transposition balls'' and evaluating the appropriate version of the generalized Gilbert--Varshamov bound, while the second bound follows from a construction of codes correcting an arbitrary number of transpositions (i.e., zero-error codes). Asymptotic bounds on the cardinality of optimal codes correcting $ t = \textrm{const} $ transpositions are also derived. |
| title | Bounds on Codes Correcting Transpositions of Consecutive Symbols |
| topic | Information Theory Discrete Mathematics 94B25, 94B50, 94B65, 68P30, 68R05 |
| url | https://arxiv.org/abs/2509.06692 |