Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2412.04148 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918138484883456 |
|---|---|
| author | Hirobe, Tomoya Kasai, Kenta |
| author_facet | Hirobe, Tomoya Kasai, Kenta |
| contents | This paper investigates the construction and analysis of permutation codes under the Chebyshev distance. Direct product group permutation (DPGP) codes, independently introduced by Kløve et al. and Tamo et al., represent the best-known class of permutation codes in terms of both size and minimum distance, while also allowing for algebraic and efficient encoding and decoding. In contrast, this study focuses on recursively extended permutation (REP) codes, proposed by Kløve et al. as a recursive alternative. We analyze the properties of REP codes and prove that, despite their distinct construction principles, optimal REP codes achieve exactly the same size and minimum distance as the best DPGP codes under the Chebyshev metric. This surprising equivalence uncovers a deep connection between two structurally dissimilar code families and establishes REP codes as a structurally flexible yet equally powerful alternative to DPGP codes. In addition, we present efficient encoding and decoding algorithms for REP codes, including a sequential encoder with $O(n \log n)$ complexity and a bounded-distance decoder with $O(n \log^2 n)$ complexity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_04148 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Recursively Extended Permutation Codes under Chebyshev Distance Hirobe, Tomoya Kasai, Kenta Information Theory This paper investigates the construction and analysis of permutation codes under the Chebyshev distance. Direct product group permutation (DPGP) codes, independently introduced by Kløve et al. and Tamo et al., represent the best-known class of permutation codes in terms of both size and minimum distance, while also allowing for algebraic and efficient encoding and decoding. In contrast, this study focuses on recursively extended permutation (REP) codes, proposed by Kløve et al. as a recursive alternative. We analyze the properties of REP codes and prove that, despite their distinct construction principles, optimal REP codes achieve exactly the same size and minimum distance as the best DPGP codes under the Chebyshev metric. This surprising equivalence uncovers a deep connection between two structurally dissimilar code families and establishes REP codes as a structurally flexible yet equally powerful alternative to DPGP codes. In addition, we present efficient encoding and decoding algorithms for REP codes, including a sequential encoder with $O(n \log n)$ complexity and a bounded-distance decoder with $O(n \log^2 n)$ complexity. |
| title | Recursively Extended Permutation Codes under Chebyshev Distance |
| topic | Information Theory |
| url | https://arxiv.org/abs/2412.04148 |