Code in permutations[1,2] 

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

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, A. J. H. Vinck, T. G. Swart, and I. deBeer, “Permutation Trellis Codes”, IEEE Transactions on Communications 53, 1782 (2005) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: binary_permutation

Cite as:
“Code in permutations”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/binary_permutation
BibTeX:
@incollection{eczoo_binary_permutation, title={Code in permutations}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/binary_permutation} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/binary_permutation

Cite as:

“Code in permutations”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/binary_permutation

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/groups/permutation/binary_permutation.yml.