Ранговый код

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

В отличие от других алгебраических кодов, использующих метрику Хемминга, используется новая ранговая метрика (ранговое расстояние), которое задаётся как ранг разности векторов над полем [math]\displaystyle{ GF(q) }[/math].

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

Определения

Пусть задано [math]\displaystyle{ X^n }[/math] — [math]\displaystyle{ n }[/math]-мерное векторное пространство над полем Галуа [math]\displaystyle{ GF\left( {q^N } \right) }[/math], где [math]\displaystyle{ q }[/math] — простое число, [math]\displaystyle{ N }[/math] — степень простого числа, а [math]\displaystyle{ u_1, u_2, \dots, u_N }[/math] — некоторый фиксированный базис этого поля, если его рассматривать как векторное пространство над полем [math]\displaystyle{ GF\left( {q} \right) }[/math].

Любой элемент [math]\displaystyle{ x_i \in GF\left( {q^N } \right) }[/math] можно однозначно представить как [math]\displaystyle{ x_i = a_{1i}u_1 + a_{2i}u_2 + \dots + a_{Ni}u_N }[/math]. Если обозначить совокупность всех [math]\displaystyle{ \left( {N \times n} \right) }[/math] матриц с элементами из [math]\displaystyle{ GF\left( {q} \right) }[/math] как [math]\displaystyle{ A_N^n }[/math], то для любого вектора [math]\displaystyle{ \vec x = \left( {x_1, x_2, \dots, x_n } \right) }[/math] можно задать биекцию [math]\displaystyle{ A:X^n \to A_N^n }[/math] с помощью следующего правила:

[math]\displaystyle{ 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\| }[/math]

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

[math]\displaystyle{ d\left( {\vec x;\vec y} \right) = r\left( {\vec x - \vec y;q} \right) }[/math]

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

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

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

Литература

Ссылки

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