Rank error-correcting code

Rank codes
Named after	Ernst M. Gabidulin
Classification
Hierarchy	Linear block code Rank code
Block length	n = q − 1
Message length	k
Distance	n − k + 1
Alphabet size	q = pm  (p prime)
Notation	[n, k, n − k + 1]q-code
Algorithms
Berlekamp–Massey Euclidean over Frobenius poynomials
Properties
Maximum-distance separable code

In coding theory, Rank codes are non-binary linear error-correcting codes invented by Ernst M. Gabidulin. 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 detect any errors of rank ⌊n-k/2⌋. As an erasure code, it can correct up to n-k known erasures.

Rank code is an algebraic linear code over the finite field $GF(q^{N})$ similar to Reed-Solomon code. Instead of using Hamming metric, the code is defined over rank metric.

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.

 disstance is a rank of the distance используется новая ранговая метрика (ранговое расстояние), которое задаётся как ранг разности векторов над полем $GF(q)$.

Ранговый код позволяет исправлять ошибки в передаваемой информационной матрице, если ранг ошибки не выше заданного.

Определения

Пусть задано $X^{n}$ — n-мерное векторное пространство над полем Галуа $GF\left({q^{N}}\right)$, где $q$ — степень простого числа, а $u_{1},u_{2},\dots ,u_{N}$ — некоторый фиксированный базис этого поля, если его рассматривать как векторное пространство над полем $GF\left({q}\right)$.

Любой элемент $x_{i}\in GF\left({q^{N}}\right)$ можно однозначно представить как $x_{i}=a_{1i}u_{1}+a_{2i}u_{2}+\dots +a_{Ni}u_{N}$. Если обозначить совокупность всех $\left({N\times n}\right)$ матриц с элементами из $GF\left({q}\right)$ как $A_{N}^{n}$, то для любого вектора ${\vec {x}}=\left({x_{1},x_{2},\dots ,x_{n}}\right)$ можно задать биекцию $A:X^{n}\to A_{N}^{n}$ с помощью следующего правила:

$A\left({\vec {x}}\right)=\left\|{\begin{array}{*{20}c}{a_{11}}&{a_{12}}&{...}&{a_{1n}}\\{a_{21}}&{a_{22}}&{...}&{a_{2n}}\\{...}&{...}&{...}&{...}\\{a_{N1}}&{a_{N2}}&{...}&{a_{Nn}}\\\end{array}}\right\|$

Рангом вектора ${\vec {x}}$ над полем $GF\left({q}\right)$ будем называть ранг соответствующей матрицы $A\left({\vec {x}}\right)$ и обозначать как $r\left({{\vec {x}};q}\right)$. Данный ранг (точнее, отображение ${\vec {x}}\to r\left({{\vec {x}};q}\right)$) задаёт норму на $X^{n}$. Данная норма задаёт на $X^{n}$ ранговую метрику:

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

Тогда произвольное множество {x₁, x₂, ..., x_M} векторов из Xⁿ назовём кодом (с кодовым расстоянием $d=\min d\left({x_{i},x_{j}}\right)$, а подпространство Xⁿ размерности k — линейным или (n, k)-кодом.

Использование

На основе ранговых кодов были предложены некоторые новые криптосистемы (ГПТ). Также было показано, что ранговые коды можно использовать при сетевом кодировании, которое использует возможность кода исправлять ошибки с рангом не выше заданного.

Литература

• Габидулин Э.М. (1985). "Теория кодов с максимальным ранговым расстоянием" (in Russian). 21 (1) (Пробл. передачи информ ed.): 3–16. {{cite journal}}: Cite journal requires |journal= (help)CS1 maint: date and year (link)
• E.M. Gabidulin, N.I. Pilipchuk (June 29-July 4, 2003). "A new method of erasure correction by rank codes" (Proceedings of the 2003 IEEE International Symposium on Information Theory ed.). Yokohama, Japan: 423. ISBN 0-7803-7728-1. {{cite journal}}: Check date values in: |year= and |date= (help); Cite journal requires |journal= (help)CS1 maint: date and year (link) CS1 maint: multiple names: authors list (link) CS1 maint: year (link)
• Габидулин Э.М., Пилипчук Н.И. (2004). "Симметричные ранговые коды" (in Russian). 40 (2) (Пробл. передачи информ ed.): 3–18. {{cite journal}}: Cite journal requires |journal= (help)CS1 maint: date and year (link) CS1 maint: multiple names: authors list (link)
• Alexander Kshevetskiy, Ernst M. Gabidulin (4-9 Sept. 2005). "The new construction of rank codes" (Proceedings of IEEE International Symposium on Information Theory (ISIT) 2005 ed.). Adelaide, Australia: 2105–2108. ISBN 0-7803-9151-9. {{cite journal}}: Check date values in: |year= and |date= (help); Cite journal requires |journal= (help)CS1 maint: date and year (link) CS1 maint: multiple names: authors list (link) CS1 maint: year (link)

См. также

• Network coding