Русская Википедия:Ранговый код

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

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

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

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

Определения

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

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

<math>

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

<math>d\left( {\vec x;\vec y} \right) = r\left( {\vec x - \vec y;q} \right)</math>

Тогда произвольное множество {x1, x2, ..., xM} векторов из Xn назовём кодом (с кодовым расстоянием <math>d = \min d\left( {x_i ,x_j } \right)</math>, а подпространство Xn размерности k — линейным или (n, k)-кодом.

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

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

Литература

Ссылки