Ранговый код

Ранговый код — алгебраический линейный код над полем $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. — В. 1. — Т. 21. — С. 3-16.
• E.M. Gabidulin, N.I. Pilipchuk A new method of erasure correction by rank codes (англ.) // Proceedings of the 2003 IEEE International Symposium on Information Theory. — Yokohama, Japan, June 29-July 4, 2003. — С. 423. — ISBN 0-7803-7728-1.
• Габидулин Э.М., Пилипчук Н.И. Симметричные ранговые коды (рус.) // Пробл. передачи информ. — 2004. — В. 2. — Т. 40. — С. 3–18.
• Alexander Kshevetskiy, Ernst M. Gabidulin The new construction of rank codes (англ.) // Proceedings of IEEE International Symposium on Information Theory (ISIT) 2005. — Adelaide, Australia, 4-9 Sept. 2005. — С. 2105-2108. — ISBN 0-7803-9151-9.

См. также

• Сетевое кодирование