Rank-modulation code[1][2]

Description

Also known as a code in permutations. A family of codes that encode a finite set of size \(M\) into a set \(S_n\) of permutations of \([n]=(1,2,...,n)\). They can be derived from Lee-metric codes, Reed-Solomon codes [3], quadratic residue codes and most binary codes.

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\).

Rate

Rank modulation codes with code distance \(d=\Theta(n^{1+\epsilon})\) for \(\epsilon\in[0,1]\) achieve a rate of \(1-\epsilon\) [4].

Realizations

Electronic devices where charges can either increase in an individual cell or decrease in a block of adjacent cells, e.g., flash memories [5].

Parent

  • Group-based code — Group-based codes whose alphabet is based on the permutation group \(S_n\) are rank-modulation codes.

Cousins

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]
Anxiao Jiang, M. Schwartz, and J. Bruck, “Error-correcting codes for rank modulation”, 2008 IEEE International Symposium on Information Theory (2008). DOI
[3]
A. Mazumdar, A. Barg, and G. Zemor, “Constructions of rank modulation codes”, 2011 IEEE International Symposium on Information Theory Proceedings (2011). DOI
[4]
A. Barg and A. Mazumdar, “Codes in permutations and error correction for rank modulation”, 2010 IEEE International Symposium on Information Theory (2010). DOI
[5]
Anxiao Jiang et al., “Rank Modulation for Flash Memories”, IEEE Transactions on Information Theory 55, 2659 (2009). DOI
Page edit log

Zoo code information

Internal code ID: rank_modulation

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: rank_modulation

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

Cite as:

“Rank-modulation code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/rank_modulation

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/groups/rank_modulation.yml.