Alternative names: Permutation-based code.
Description
Encodes codewords into permutations of \(n\) objects. Permutation group elements can be mapped to inversion vectors [4] over a mixed alphabet.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], including LP bounds [6]. The mapping to inversion vectors is not distance preserving, but the \(\ell_1\) distance between inversion vectors is a lower bound on the Kendall tau distance [4].
Other distances include the Ulam distance [7].
Rate
Asymptotically good codes in the Ulam metric exist [8].Notes
Review of parallels between linear binary codes and permutation groups [9].Cousins
- Convolutional code— Convolutional codes in permutations have been constructed [10].
- Mixed code— Permutation group elements can be mapped to inversion vectors [4] over a mixed alphabet.
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]
- A. Barg and A. Mazumdar, “Codes in Permutations and Error Correction for Rank Modulation”, IEEE Transactions on Information Theory 56, 3158 (2010) arXiv:0908.4094 DOI
- [5]
- M. Kiyota, “An inequality for finite permutation groups”, Journal of Combinatorial Theory, Series A 27, 119 (1979) DOI
- [6]
- H. Tarnanen, “Upper Bounds on Permutation Codes via Linear Programming”, European Journal of Combinatorics 20, 101 (1999) DOI
- [7]
- V. I. LEVENSHTEIN, “On perfect codes in deletion and insertion metric”, Discrete Mathematics and Applications 2, (1992) DOI
- [8]
- E. Goldenberg, M. Habib, and K. C. S, “Explicit Good Codes Approaching Distance 1 in Ulam Metric”, (2024) arXiv:2401.17235
- [9]
- P. J. Cameron, “Permutation codes”, European Journal of Combinatorics 31, 482 (2010) DOI
- [10]
- 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