Ранговый код

Ранговый код — алгебраический линейный код над полем $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$, то для любого вектора $\overrightarrow{x}=\left(x_1,x_2,\dots ,x_n\right)$ можно задать биекцию $A:X^n\to A_N^n$ с помощью следующего правила:

$A\left(\overrightarrow{x}\right)=\Vert \begin{array}{cccc}{a}_{11}& a_{12}& \mathrm{...}& a_{1n}\\ a_{21}& a_{22}& \mathrm{...}& a_{2n}\\ \mathrm{...}& \mathrm{...}& \mathrm{...}& \mathrm{...}\\ a_{N1}& a_{N2}& \mathrm{...}& a_{Nn}\end{array}\Vert$

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

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

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

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

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

Литература

• Шаблон:Source
• Шаблон:Source
• Шаблон:Source
• Шаблон:Source

Ссылки

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