Also known as Vector rank-metric code, Delsarte-Gabidulin code.
Description
A linear code over \(GF(q^N)\) that corrects errors over rank metric instead of the traditional Hamming distance. Every element \(GF(q^N)\) can be written as an \(N\)-dimensional vector with coefficients in \(GF(q)\), and the rank of a set of elements is rank of the matrix formed by their coefficients.
Given \(X^n=\text{span}\{x_i\}\), an \(n\)-dimensional vector space over \(GF(q^N)\) (where \(q\) is a power of a prime number), the rank metric \(d(x, y)\) is defined via the rank norm \(r(x, q) = \mathrm{rank}(A(x))\), where \begin{align} A(x) = \begin{pmatrix} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ a_{N1} & a_{N2} & \ldots & a_{Nn}~, \end{pmatrix} \tag*{(1)}\end{align} and \(x_i = a_{1i} u_1 + a_{2i} u_2 + \ldots + a_{Ni}u_N \) for some fixed basis \(\{u_i\}_{i=1}^N\).
Protection
Set of vectors \(\{x_1, x_2, \ldots, x_M\}\) determines a rank code with distance \(d=\min d(x_i, x_j)\). The code with distance \(d\) corrects all errors with rank of the error not greater than \(\lfloor (d-1)/2\rfloor\).
Decoding
Fast decoder based on a transform-domain approach [4].Algebraic list decoder that decodes up to the Singleton bound [5].
Realizations
Public-key cryptosystems [6,7].Digital watermarking. The Gabidulin code provides efficient correction against luminance tampering and image-slicing distortion due to the consistency of the rank against alterations such as column swapping [8].
Parent
- Rank-metric code — Gabidulin codes over \(GF(q^N)\), when expressed as matrices over \(GF(q)\), are rank-metric codes (see Def. 14 in Ref. [9]). The reverse is not always true since Gabidulin codes are not always \(GF(q^N)\)-linear [9; Rm. 16].
Cousins
- Maximum-rank distance (MRD) code — Gabidulin codes over \(GF(q^N)\) with maximum rank-distance, when expressed as matrices over \(GF(q)\), are MRD codes.
- Linear \(q\)-ary code — Gabidulin codes over \(GF(q^N)\), when expressed as vectors over \(GF(q^N)\), are linear \(q\)-ary codes.
- Linearized RS code — Gabidulin codes are particular cases of linearized RS codes because the sum-rank metric generalizes the rank metric [10].
- Generalized Srivastava code — Generalized Srivastava codes for \(m=1\) are equivalent to Gabidulin codes [11; pg. 359].
- Subspace code — Gabidulin codes can be used to construct asymptotically good subspace codes [12,13].
- Quantum Gabidulin code — A quantum Gabidulin code is defined using two Gabidulin codes with associated parameters \(r,s\), respectively, such that \(r+s = n\) [14].
References
- [1]
- E. M. Gabidulin, Theory of Codes with Maximum Rank Distance, Problemy Peredachi Informacii, Volume 21, Issue 1, 3–16 (1985)
- [2]
- P. Delsarte, “Bilinear forms over a finite field, with applications to coding theory”, Journal of Combinatorial Theory, Series A 25, 226 (1978) DOI
- [3]
- R. M. Roth, “Maximum-rank array codes and their application to crisscross error correction”, IEEE Transactions on Information Theory 37, 328 (1991) DOI
- [4]
- D. Silva and F. R. Kschischang, “Fast encoding and decoding of Gabidulin codes”, 2009 IEEE International Symposium on Information Theory 2858 (2009) arXiv:0901.2483 DOI
- [5]
- V. Guruswami and C. Xing, “List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound”, Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (2013) DOI
- [6]
- T. P. Berger and P. Loidreau, “How to Mask the Structure of Codes for a Cryptographic Use”, Designs, Codes and Cryptography 35, 63 (2005) DOI
- [7]
- T. Lau and C. Tan, “A New Technique in Rank Metric Code-Based Encryption”, Cryptography 2, 32 (2018) DOI
- [8]
- P. Lefevre, P. Carre, and P. Gaborit, “Watermarking and Rank Metric Codes”, 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) 2087 (2018) DOI
- [9]
- A. Ravagnani, “Rank-metric codes and their duality theory”, (2015) arXiv:1410.1333
- [10]
- 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
- [11]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [12]
- Huaxiong Wang, Chaoping Xing, and R. Safavi-Naini, “Linear authentication codes: bounds and constructions”, IEEE Transactions on Information Theory 49, 866 (2003) DOI
- [13]
- R. Koetter and F. R. Kschischang, “Coding for Errors and Erasures in Random Network Coding”, IEEE Transactions on Information Theory 54, 3579 (2008) DOI
- [14]
- N. Delfosse and G. Zémor, “Correction of circuit faults in a stacked quantum memory using rank-metric codes”, (2024) arXiv:2411.09173
Page edit log
- Micah Shaw (2022-08-09) — most recent
- Victor V. Albert (2022-05-25)
- Victor V. Albert (2021-12-16)
- Marianna Podzorova (2021-12-13)
Cite as:
“Gabidulin code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/gabidulin