## 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

- Reed-Solomon (RS) code — RS codes can be used to design rank modulation codes [3].
- Binary permutation-based code — Binary permutation-based codes also encode messages into permutations but protect against errors with the Hamming distance.

## 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

- Victor V. Albert (2022-04-12) — most recent
- Jiaxin Huang (2022-04-08)

## Zoo code information

## Cite as:

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