Alternative names: Permutation-based code.
Description
Encodes codewords into permutations of \(n\) objects.Protection
Protects against errors in the Kendall tau distance on the space of permutations. The Kendall distance between permutations \(\sigma\) and \(\pi\) is defined as the minimum number of adjacent transpositions required to change \(\sigma\) into \(\pi\). Various bounds have been developed [4,5].
Other distances include the Ulam distance [6].
Rate
Asymptotically good codes in the Ulam metric exist [7].Notes
Review of parallels between linear binary codes and permutation groups [8].Cousin
- Convolutional code— Convolutional codes in permutations have been constructed [9].
Member of code lists
Primary Hierarchy
Parents
Codes in permutations are group-alphabet codes for the symmetric group \(G=S_n\).
Code in permutations
Children
References
- [1]
- D. Slepian, “Permutation modulation”, Proceedings of the IEEE 53, 228 (1965) DOI
- [2]
- H. Chadwick and L. Kurz, “Rank permutation group codes based on Kendall’s correlation statistic”, IEEE Transactions on Information Theory 15, 306 (1969) DOI
- [3]
- I. F. Blake, G. Cohen, and M. Deza, “Coding with permutations”, Information and Control 43, 1 (1979) DOI
- [4]
- M. Kiyota, “An inequality for finite permutation groups”, Journal of Combinatorial Theory, Series A 27, 119 (1979) DOI
- [5]
- H. Tarnanen, “Upper Bounds on Permutation Codes via Linear Programming”, European Journal of Combinatorics 20, 101 (1999) DOI
- [6]
- V. I. LEVENSHTEIN, “On perfect codes in deletion and insertion metric”, Discrete Mathematics and Applications 2, (1992) DOI
- [7]
- E. Goldenberg, M. Habib, and K. C. S, “Explicit Good Codes Approaching Distance 1 in Ulam Metric”, (2024) arXiv:2401.17235
- [8]
- P. J. Cameron, “Permutation codes”, European Journal of Combinatorics 31, 482 (2010) DOI
- [9]
- H. C. Ferreira, A. J. H. Vinck, T. G. Swart, and I. deBeer, “Permutation Trellis Codes”, IEEE Transactions on Communications 53, 1782 (2005) DOI
Page edit log
- Jiaxin Huang (2022-04-08) — most recent
Cite as:
“Code in permutations”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/binary_permutation