Also known as Code in permutations.
Description
A family of codes that encode a finite set of size \(M\) into a group \(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-alphabet code — Group-alphabet codes whose alphabet is based on the permutation group \(S_n\) are rank-modulation codes.
Cousins
- Gray code — The rank-modulation Gray code is an extension of the original binary Gray code to a code on the permutation group [5].
- 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. Zémor, “Constructions of Rank Modulation Codes”, (2011) arXiv:1110.2557
- [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-11-07) — most recent
- Victor V. Albert (2022-04-12)
- Jiaxin Huang (2022-04-08)
Cite as:
“Rank-modulation Gray code (RMGC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/rank_modulation