# Rank error-correcting code

Rank codes
Classification
Hierarchy Linear block code
Rank code
Parameters
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 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 $GF(q^N)$ similar to Reed–Solomon code.

The rank of the vector over $GF(q^N)$ is the maximum number of linearly independent components over $GF(q)$. The rank distance between two vectors over $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 $X^n$n-dimensional vector space over the finite field $GF\left( {q^N } \right)$, where $q$ is a prime number, $N$ is a power and $\left(u_1, u_2, \dots, u_N\right)$ with $u_i \in GF(q)$ is a base of the vector space over the field $GF\left( {q} \right)$.

Every element $x_i \in GF\left( {q^N } \right)$ can be represented as $x_i = a_{1i}u_1 + a_{2i}u_2 + \dots + a_{Ni}u_N$. Hence, every vector $\vec x = \left( {x_1, x_2, \dots, x_n } \right)$ over $GF\left( {q^N } \right)$ can be written as matrix:

$\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 $\vec x$ over the field $GF\left( {q^N} \right)$ is a rank of the corresponding matrix $A\left( {\vec x} \right)$ over the field $GF\left( {q} \right)$ denoted by $r\left( {\vec x; q} \right)$.

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

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

## Rank code

A set $\{x_1, x_2, \dots, x_n\}$ of vectors from $X^n$ is called a code with code distance $d = \min d\left( x_i ,x_j \right)$ and a k-dimensional subspace of $X^n$ – a linear (n, k)-code with distance $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 $[i]$ of the element $x \in GF(q^N)$ as

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

Then, every vector $\vec g = (g_1, g_2, \dots, g_n), ~ g_i \in GF(q^N), ~ n \leq N$, linearly independent over $GF(q)$, defines a generating matrix of the MRD (n, k, d = n − k + 1)-code.

$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^{[2 m]} & g_2^{[2 m]} & \dots & g_n^{[2 m]} \\ \dots & \dots & \dots & \dots \\ g_1^{[k m]} & g_2^{[k m]} & \dots & g_n^{[k m]} \end{array}} \right\|,$

where $\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 suitable for network coding.