Rank-metric code[1]
Description
Each codeword is a matrix over \(GF(q)\), with codewords forming a \(GF(q)\)-linear subspace, and with the metric being the rank of the difference of matrices. The distance \(d\) is the minimum rank of all nonzero matrices in the code. Rank-metric codes on \(n\times m\) matrices are denoted as \([n\times m,k,d]_q\).
The number of codewords satisfies \(k \leq \max(n, m) M\), where \(M\) is the maximum rank of all matrices in the code. Codes that achieve this bound with equality are called Delsarte optimal anticodes.
Protection
Protects against errors with rank \(\leq \lfloor \frac{d-1}2 \rfloor\).
The complexity of decoding rank-metric codes is unknown but expected to be harder than that of binary linear codes [2].
Decoding
Polynomial-reconstruction Berlekamp-Welch based decoder [3].Berlekamp-Massey based decoder [4].Realizations
Identity-Based Encryption [5].Digital watermarking [6].Network coding and streaming media broadcasting [7].Notes
See Ref. [8] for a discussion of MacWilliams identities and the relationship between rank metric and Gabidulin codes.See Ref. [9][10; Sec. 5] for more details.Cousins
- Subspace code— Subspace and rank-metric codes are closely related [11].
- Quantum Gabidulin code— Quantum Gabidulin code and (classical) rank-metric code distances are based on ranks of the matrix representations of their corresponding errors.
Member of code lists
Primary Hierarchy
References
- [1]
- P. Delsarte, “Bilinear forms over a finite field, with applications to coding theory”, Journal of Combinatorial Theory, Series A 25, 226 (1978) DOI
- [2]
- G. Philippe and Z. Gilles, “On the hardness of the decoding and the minimum distance problems for rank codes”, (2014) arXiv:1404.3482
- [3]
- P. Loidreau, “A Welch–Berlekamp Like Algorithm for Decoding Gabidulin Codes”, Lecture Notes in Computer Science 36 (2006) DOI
- [4]
- G. Richter and S. Plass, “Fast decoding of rank-codes with rank errors and column erasures”, International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings. 398 DOI
- [5]
- P. Gaborit, A. Hauteville, D. H. Phan, and J.-P. Tillich, “Identity-Based Encryption from Codes with Rank Metric”, Lecture Notes in Computer Science 194 (2017) DOI
- [6]
- P. Lefèvre, P. Carré, and P. Gaborit, “Application of rank metric codes in digital image watermarking”, Signal Processing: Image Communication 74, 119 (2019) DOI
- [7]
- D. Silva and F. R. Kschischang, “Rank-Metric Codes for Priority Encoding Transmission with Network Coding”, 2007 10th Canadian Workshop on Information Theory (CWIT) 81 (2007) DOI
- [8]
- A. Ravagnani, “Rank-metric codes and their duality theory”, (2015) arXiv:1410.1333
- [9]
- I. F. Blake, Essays on Coding Theory (Cambridge University Press, 2024) DOI
- [10]
- M. Blaum, P. G. Farrell, H. C. A. van Tilborg, 1998. Array codes. Handbook of coding theory, 2 (Part 2), pp. 1855-1909.
- [11]
- D. Silva, F. R. Kschischang, and R. Koetter, “A Rank-Metric Approach to Error Control in Random Network Coding”, IEEE Transactions on Information Theory 54, 3951 (2008) DOI
- [12]
- U. Martínez-Peñas, “Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring”, (2018) arXiv:1710.03109
Page edit log
- Mazin Karjikar (2023-01-16) — most recent
- Victor V. Albert (2023-01-16)
- Mazin Karjikar (2022-12-30)
- Victor V. Albert (2022-05-25)
- Thomas Wrona (2022-05-18)
Cite as:
“Rank-metric code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/rank_metric