Alternative names: Permutation-based code.
Description
Encodes codewords into permutations of \(n\) objects. Permutation group elements can be mapped to inversion vectors [6] 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 [6,7], including LP bounds [8,9]. 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 [6].
Other distances include the Ulam distance [10].
Linear programming bounds for permutation codes have been derived [9].
Rate
Asymptotically good codes in the Ulam metric exist [11].Notes
Review of parallels between linear binary codes and permutation groups [12].Cousins
- Convolutional code— Convolutional codes in permutations have been constructed [13].
- Mixed code— Permutation group elements can be mapped to inversion vectors [6] 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\).
The permutation group can be viewed as a finite symmetric space \(G/H\) with \(G = S_n \times S_n\) and \(H=S_n\) [8,9][14; Table 3].
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]
- M. Deza and S. A. Vanstone, “Bounds for permutation arrays”, Journal of Statistical Planning and Inference 2, 197 (1978) DOI
- [4]
- P. Frankl and M. Deza, “On the maximum number of permutations with given maximal or minimal distance”, Journal of Combinatorial Theory, Series A 22, 352 (1977) DOI
- [5]
- I. F. Blake, G. Cohen, and M. Deza, “Coding with permutations”, Information and Control 43, 1 (1979) DOI
- [6]
- 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
- [7]
- M. Kiyota, “An inequality for finite permutation groups”, Journal of Combinatorial Theory, Series A 27, 119 (1979) DOI
- [8]
- H. Tarnanen, “Upper Bounds on Permutation Codes via Linear Programming”, European Journal of Combinatorics 20, 101 (1999) DOI
- [9]
- P. J. Dukes, F. Ihringer, and N. Lindzey, “On the Algebraic Combinatorics of Injections and its Applications to Injection Codes”, (2019) arXiv:1912.04500
- [10]
- V. I. LEVENSHTEIN, “On perfect codes in deletion and insertion metric”, Discrete Mathematics and Applications 2, (1992) DOI
- [11]
- E. Goldenberg, M. Habib, and K. C. S, “Explicit Good Codes Approaching Distance 1 in Ulam Metric”, (2024) arXiv:2401.17235
- [12]
- P. J. Cameron, “Permutation codes”, European Journal of Combinatorics 31, 482 (2010) DOI
- [13]
- H. C. Ferreira, A. J. H. Vinck, T. G. Swart, and I. deBeer, “Permutation Trellis Codes”, IEEE Transactions on Communications 53, 1782 (2005) DOI
- [14]
- C. Bachoc, D. C. Gijswijt, A. Schrijver, and F. Vallentin, “Invariant Semidefinite Programs”, International Series in Operations Research & Management Science 219 (2011) arXiv:1007.2905 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