Rank error-correcting code

Rank codes
Classification
Hierarchy	Linear block code Rank code
Parameters
Block length	n
Message length	k
Distance	n − k + 1
Alphabet size	Q = q^N  (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 $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 power of a prime, $N$ is an integer 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 useful for error and erasure correction in network coding.

See also

• Linear code
• Reed–Solomon error correction
• Berlekamp–Massey algorithm
• Network coding

Notes

1. Codes for which each input symbol is from a set of size greater than 2.
2. http://link.springer.com/article/10.1007%2Fs00145-007-9003-9)

References

• Gabidulin, Ernst M. (1985), "Theory of codes with maximum rank distance", Problems of Information Transmission 21 (1): 1–12
• Kshevetskiy, Alexander; Gabidulin, Ernst M. (4–9 Sept. 2005), "The new construction of rank codes", Proceedings of IEEE International Symposium on Information Theory (ISIT) 2005: 2105–2108, ISBN 0-7803-9151-9 Check date values in: |date= (help)
• Gabidulin, Ernst M.; Pilipchuk, Nina I. (June 29 – July 4, 2003), "A new method of erasure correction by rank codes", Proceedings of the 2003 IEEE International Symposium on Information Theory: 423, ISBN 0-7803-7728-1

External links

• MATLAB implementation of a Rank–metric codec