Also known as 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 [3,4].

## Notes

Review of parallels between linear binary codes and permutation groups [5].

## Parent

- Group-alphabet code — Codes in permutations are group-alphabet codes for the symmetric group \(G=S_n\).

## Child

## Cousin

- Convolutional code — Convolutional codes in permutations have been constructed [6].

## References

- [1]
- H. Chadwick and L. Kurz, “Rank permutation group codes based on Kendall’s correlation statistic”, IEEE Transactions on Information Theory 15, 306 (1969) DOI
- [2]
- I. F. Blake, G. Cohen, and M. Deza, “Coding with permutations”, Information and Control 43, 1 (1979) DOI
- [3]
- M. Kiyota, “An inequality for finite permutation groups”, Journal of Combinatorial Theory, Series A 27, 119 (1979) DOI
- [4]
- H. Tarnanen, “Upper Bounds on Permutation Codes via Linear Programming”, European Journal of Combinatorics 20, 101 (1999) DOI
- [5]
- P. J. Cameron, “Permutation codes”, European Journal of Combinatorics 31, 482 (2010) DOI
- [6]
- H. C. Ferreira et al., “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