Rank error-correcting code

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})}${\displaystyle GF(q^{N})} similar to Reed–Solomon code.

The rank of the vector over ${\displaystyle GF(q^{N})}${\displaystyle GF(q^{N})} is the maximum number of linearly independent components over ${\displaystyle GF(q)}${\displaystyle GF(q)}. The rank distance between two vectors over ${\displaystyle GF(q^{N})}${\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.

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

Every element ${\displaystyle x_{i}\in GF\left({q^{N}}\right)}${\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}}${\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)}${\displaystyle {\vec {x}}=\left({x_{1},x_{2},\dots ,x_{n}}\right)} over ${\displaystyle GF\left({q^{N}}\right)}${\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\|}${\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}}}${\displaystyle {\vec {x}}} over the field ${\displaystyle GF\left({q^{N}}\right)}${\displaystyle GF\left({q^{N}}\right)} is a rank of the corresponding matrix ${\displaystyle A\left({\vec {x}}\right)}${\displaystyle A\left({\vec {x}}\right)} over the field ${\displaystyle GF\left({q}\right)}${\displaystyle GF\left({q}\right)} denoted by ${\displaystyle r\left({{\vec {x}};q}\right)}${\displaystyle r\left({{\vec {x}};q}\right)}.

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

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

A set ${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}}${\displaystyle \{x_{1},x_{2},\dots ,x_{n}\}} of vectors from ${\displaystyle X^{n}}${\displaystyle X^{n}} is called a code with code distance ${\displaystyle d=\min d\left(x_{i},x_{j}\right)}${\displaystyle d=\min d\left(x_{i},x_{j}\right)}. If the set also forms a k-dimensional subspace of ${\displaystyle X^{n}}${\displaystyle X^{n}}, then it is called a linear (n, k)-code with distance ${\displaystyle d}${\displaystyle d}. Such a linear rank metric code always satisfies the Singleton bound ${\displaystyle d\leq n-k+1}${\displaystyle d\leq n-k+1} with equality.

There are several known constructions of rank codes, which are maximum rank distance (or MRD) codes with d = n − k + 1. The easiest one to construct is known as the (generalized) Gabidulin code, it was discovered first by Delsarte (who called it a Singleton system) and later by Gabidulin ^[2] (and Kshevetskiy ^[3] ).

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

${\displaystyle x^{[i]}=x^{q^{i\mod N}}.,円}${\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}${\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)}${\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}^{[(k-1)m]}&g_{2}^{[(k-1)m]}&\dots &g_{n}^{[(k-1)m]}\end{array}}\right\|,}${\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}^{[(k-1)m]}&g_{2}^{[(k-1)m]}&\dots &g_{n}^{[(k-1)m]}\end{array}}\right\|,}

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

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

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

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

• 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 September 2005). "The new construction of rank codes". Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. pp. 2105–2108. doi:10.1109/ISIT.2005.1523717. ISBN 978-0-7803-9151-2. S2CID 11679865.
• Gabidulin, Ernst M.; Pilipchuk, Nina I. (June 29 – July 4, 2003). "A new method of erasure correction by rank codes". IEEE International Symposium on Information Theory, 2003. Proceedings. p. 423. doi:10.1109/ISIT.2003.1228440. ISBN 978-0-7803-7728-8. S2CID 122552232.

• MATLAB implementation of a Rank–metric codec

• Error detection and correction
• Coding theory

• Articles with short description
• Short description matches Wikidata