# Rank error-correcting code

Rank codes
Classification
Hierarchy Linear block code
Rank code
Block length n
Message length k
Distance nk + 1
Alphabet size Q = qN  (q prime)
Notation [n, k, d]-code
Algorithms
Decoding Berlekamp–Massey
Euclidean
with Frobenius poynomials

In coding theory, rank codes (also called Gabidulin codes) are non-binary[1] linear error-correcting codes over not Hamming but rank metric. They described a systematic way of building codes that could detect and correct multiple random rank errors. By adding redundancy with coding k-symbol word to a n-symbol word, a rank code can correct any errors of rank up to t = ⌊ (d − 1) / 2 ⌋, where d is a code distance. As an erasure code, it can correct up to d − 1 known erasures.

A rank code is an algebraic linear code over the finite field ${\displaystyle GF(q^{N})}$ similar to Reed–Solomon code.

The rank of the vector over ${\displaystyle GF(q^{N})}$ is the maximum number of linearly independent components over ${\displaystyle GF(q)}$. The rank distance between two vectors over ${\displaystyle GF(q^{N})}$ is the rank of the difference of these vectors.

The rank code corrects all errors with rank of the error vector not greater than t.

## Rank metric

Let ${\displaystyle X^{n}}$n-dimensional vector space over the finite field ${\displaystyle GF\left({q^{N}}\right)}$, where ${\displaystyle q}$ is a power of a prime, ${\displaystyle N}$ is an integer and ${\displaystyle \left(u_{1},u_{2},\dots ,u_{N}\right)}$ with ${\displaystyle u_{i}\in GF(q)}$ is a base of the vector space over the field ${\displaystyle GF\left({q}\right)}$.

Every element ${\displaystyle x_{i}\in GF\left({q^{N}}\right)}$ can be represented as ${\displaystyle x_{i}=a_{1i}u_{1}+a_{2i}u_{2}+\dots +a_{Ni}u_{N}}$. Hence, every vector ${\displaystyle {\vec {x}}=\left({x_{1},x_{2},\dots ,x_{n}}\right)}$ over ${\displaystyle GF\left({q^{N}}\right)}$ can be written as matrix:

${\displaystyle {\vec {x}}=\left\|{\begin{array}{*{20}c}a_{1,1}&a_{1,2}&\ldots &a_{1,n}\\a_{2,1}&a_{2,2}&\ldots &a_{2,n}\\\ldots &\ldots &\ldots &\ldots \\a_{N,1}&a_{N,2}&\ldots &a_{N,n}\end{array}}\right\|}$

Rank of the vector ${\displaystyle {\vec {x}}}$ over the field ${\displaystyle GF\left({q^{N}}\right)}$ is a rank of the corresponding matrix ${\displaystyle A\left({\vec {x}}\right)}$ over the field ${\displaystyle GF\left({q}\right)}$ denoted by ${\displaystyle r\left({{\vec {x}};q}\right)}$.

The set of all vectors ${\displaystyle {\vec {x}}}$ is a space ${\displaystyle X^{n}=A_{N}^{n}}$. The map ${\displaystyle {\vec {x}}\to r\left({\vec {x}};q\right)}$) defines a norm over ${\displaystyle X^{n}}$ and a rank metric:

${\displaystyle d\left({{\vec {x}};{\vec {y}}}\right)=r\left({{\vec {x}}-{\vec {y}};q}\right)}$

## Rank code

A set ${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}$ of vectors from ${\displaystyle X^{n}}$ is called a code with code distance ${\displaystyle d=\min d\left(x_{i},x_{j}\right)}$ and a k-dimensional subspace of ${\displaystyle X^{n}}$ – a linear (n, k)-code with distance ${\displaystyle d\leq n-k+1}$.

## Generating matrix

There is known the only construction of rank code, which is a maximum rank distance MRD-code with d = n − k + 1.

Let's define a Frobenius power ${\displaystyle [i]}$ of the element ${\displaystyle x\in GF(q^{N})}$ as

${\displaystyle x^{[i]}=x^{q^{i\mod N}}.\,}$

Then, every vector ${\displaystyle {\vec {g}}=(g_{1},g_{2},\dots ,g_{n}),~g_{i}\in GF(q^{N}),~n\leq N}$, linearly independent over ${\displaystyle GF(q)}$, defines a generating matrix of the MRD (n, k, d = n − k + 1)-code.

${\displaystyle G=\left\|{\begin{array}{*{20}c}g_{1}&g_{2}&\dots &g_{n}\\g_{1}^{[m]}&g_{2}^{[m]}&\dots &g_{n}^{[m]}\\g_{1}^{[2m]}&g_{2}^{[2m]}&\dots &g_{n}^{[2m]}\\\dots &\dots &\dots &\dots \\g_{1}^{[km]}&g_{2}^{[km]}&\dots &g_{n}^{[km]}\end{array}}\right\|,}$

where ${\displaystyle \gcd(m,N)=1}$.

## Applications

There are several proposals for public-key cryptosystems based on rank codes. However, most of them have been proven insecure (see e.g. Journal of Cryptology, April 2008[2]).

Rank codes are also useful for error and erasure correction in network coding.