Ранговый код

Ранговый код — алгебраический линейный код над полем $GF(q^{N})$, в общем случае — метод кодирования информации с целью защиты от помех. В настоящее время предложено использование данного кода для использования в случайном сетевом кодировании.

В отличие от других алгебраических кодов, использующих метрику Хемминга, используется новая ранговая метрика (ранговое расстояние), которое задаётся как ранг разности векторов над полем $GF(q)$.

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

Определения

Пусть задано $X^{n}$ — $n$-мерное векторное пространство над полем Галуа $GF\left({q^{N}}\right)$, где $q$ — простое число, $N$ — степень простого числа, а $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. — Т. 21, вып. 1. — С. 3—16.
• Gabidulin E. M., Pilipchuk N. I. A new method of erasure correction by rank codes (англ.) // IEEE International Symposium on Information Theory, 2003. Proceedings — IEEE, 2003. — P. 423. — ISBN 978-0-7803-7728-8 — doi:10.1109/ISIT.2003.1228440
• Габидулин Э. М., Пилипчук Н. И. Симметричные ранговые коды // Теория информации и теория кодирования — 2004. — Т. 40, вып. 2. — С. 3–18. — doi:10.1023/B:PRIT.0000043925.67309.C6
• Kshevetskiy A. S., Gabidulin E. M. The new construction of rank codes (англ.) // Information Theory, 2005. ISIT 2005. Proceedings. International Symposium on — IEEE, 2005. — P. 2105—2108. — ISBN 978-0-7803-9151-2 — ISSN 2157-8095 — doi:10.1109/ISIT.2005.1523717

Ссылки

• Реализация кодера и декодера рангового кода на языке MATLAB.