Gabidulin code[1][2]

Description

Also called a vector rank-metric code. 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} \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 [3].

Parents

  • Linear \(q\)-ary code
  • 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. [4]). The reverse is not always true since Gabidulin codes are not always \(GF(q^N)\)-linear (see Rm. 16 in Ref. [4]).

Cousin

Zoo code information

Internal code ID: gabidulin

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: gabidulin

Cite as:
“Gabidulin code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/gabidulin
BibTeX:
@incollection{eczoo_gabidulin, title={Gabidulin code}, booktitle={The Error Correction Zoo}, year={2022}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/gabidulin} }
Permanent link:
https://errorcorrectionzoo.org/c/gabidulin

References

[1]
E. M. Gabidulin, Theory of Codes with Maximum Rank Distance, Problemy Peredachi Informacii, Volume 21, Issue 1, 3–16 (1985)
[2]
R. M. Roth, “Maximum-rank array codes and their application to crisscross error correction”, IEEE Transactions on Information Theory 37, 328 (1991). DOI
[3]
D. Silva and F. R. Kschischang, “Fast encoding and decoding of Gabidulin codes”, 2009 IEEE International Symposium on Information Theory (2009). DOI; 0901.2483
[4]
Alberto Ravagnani, “Rank-metric codes and their duality theory”. 1410.1333

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/q-ary_digits/gabidulin.yml.