Ранговый код
Ранговый код — алгебраический линейный код над полем [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{ \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]
Тогда произвольное множество {x1, x2, ..., xM} векторов из Xn назовём кодом (с кодовым расстоянием [math]\displaystyle{ d = \min d\left( {x_i ,x_j } \right) }[/math], а подпространство Xn размерности k — линейным или (n, k)-кодом.
Использование
На основе ранговых кодов были предложены некоторые новые криптосистемы (ГПТ). Также было показано, что ранговые коды можно использовать при сетевом кодировании, которое использует возможность кода исправлять ошибки с рангом не выше заданного.