[Jump to code hierarchy]

Gabidulin code [1–3]

Alternative Names: Vector rank-metric code, Delsarte-Gabidulin code.

Description

A linear code over \(\mathbb{F}_{q^N}\) that corrects errors over rank metric instead of the traditional Hamming distance. Every element \(\mathbb{F}_{q^N}\) can be written as an \(N\)-dimensional vector with coefficients in \(\mathbb{F}_q\), and the rank of a set of elements is rank of the matrix formed by their coefficients.

Given \(X^n=span\{x_i\}\), an \(n\)-dimensional vector space over \(\mathbb{F}_{q^N}\) (where \(q\) is a power of a prime number), the rank metric \(d(x, y)\) is defined via the rank norm, \(\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\). For \(n=N\) and rate \(R\), some received words have exponentially many Gabidulin codewords within relative rank distance \(1-\sqrt{R}\) [4]. Some families of Gabidulin codes cannot be list decoded efficiently at any radius beyond the unique-decoding radius [5].

Decoding

Fast decoder based on a transform-domain approach [6].Subcodes of Gabidulin codes whose evaluation points span a subfield can be list decoded up to the Singleton bound, with the subcode chosen by a Monte Carlo construction [7] or explicitly [8].

Realizations

Public-key cryptosystems [9,10].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 [11].

Cousins

  • Maximum-rank distance (MRD) code— Gabidulin codes over \(\mathbb{F}_{q^N}\) with maximum rank-distance, when expressed as matrices over \(\mathbb{F}_q\), are MRD codes.
  • Linear \(q\)-ary code— Gabidulin codes over \(\mathbb{F}_{q^N}\), when expressed as vectors over \(\mathbb{F}_{q^N}\), are linear \(q\)-ary codes.
  • Subspace code— Gabidulin codes can be used to construct asymptotically good subspace codes [12,13].
  • Linearized RS code— Choosing one conjugacy class with \(\sigma\neq\operatorname{Id}\) and \(\delta=0\) recovers Gabidulin codes, and the sum-rank metric reduces to the rank metric [14; Ex. 37]. Over \(\mathbb{F}_{q^m}\) viewed over \(\mathbb{F}_q\), linearized RS codes can have length up to \((q-1)m\), whereas Gabidulin codes over the same extension have maximum length \(m\) [14; Sec. 4.2].
  • Quantum Gabidulin code— A quantum Gabidulin code is defined using two Gabidulin codes with associated parameters \(r,s\), respectively, such that \(r+s = n\) [15].

Primary Hierarchy

Parents
Gabidulin codes over \(\mathbb{F}_{q^N}\), when expressed as matrices over \(\mathbb{F}_q\), are rank-metric codes (see Def. 14 in Ref. [16]). The reverse is not always true, i.e., not every rank-metric code is Gabidulin [16; Rm. 16].
Gabidulin code

References

  1. [1]

    E. M. Gabidulin, “Theory of Codes with Maximum Rank Distance”, Problemy Peredachi Informatsii 21(1), 3–16 (1985)

  2. [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. [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. [4]

    A. Wachter-Zeh, “Bounds on List Decoding of Rank-Metric Codes”, IEEE Transactions on Information Theory 59, 7268 (2013) arXiv:1301.4643 DOI

  5. [5]

    N. Raviv and A. Wachter-Zeh, “Some Gabidulin Codes cannot be List Decoded Efficiently at any Radius”, (2016) arXiv:1501.04272

  6. [6]

    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

  7. [7]

    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 843 (2013) DOI

  8. [8]

    V. Guruswami and C. Wang, “Explicit rank-metric codes list-decodable with optimal redundancy”, (2013) arXiv:1311.7084

  9. [9]

    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

  10. [10]

    T. Lau and C. Tan, “A New Technique in Rank Metric Code-Based Encryption”, Cryptography 2, 32 (2018) DOI

  11. [11]

    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

  12. [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. [13]

    R. Koetter and F. Kschischang, “Coding for Errors and Erasures in Random Network Coding”, (2008) arXiv:cs/0703061

  14. [14]

    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

  15. [15]

    N. Delfosse and G. Zémor, “Correction of circuit faults in a stacked quantum memory using rank-metric codes”, (2024) arXiv:2411.09173

  16. [16]

    A. Ravagnani, “Rank-metric codes and their duality theory”, (2015) arXiv:1410.1333

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: gabidulin

Cite as:
“Gabidulin code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/gabidulin, arXiv:2606.11484
BibTeX:
@incollection{eczoo_gabidulin,
title={Gabidulin code},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/gabidulin}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/gabidulin

Cite as:

“Gabidulin code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/gabidulin, arXiv:2606.11484

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/matrices/sum-rank-metric/rank-metric/gabidulin.yml.