Ранговый код

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

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

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

ОпределенияПравить

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

Любой элемент $x_i\in <!--\; \in \; -->GF\left(q^N\right)$$x_{i}\in GF\left({q^{N}}\right)$  можно однозначно представить как $x_i=a_{1i}{u}_1+a_{2i}{u}_2+\cdots <!--\; \cdots \; -->+a_{Ni}{u}_N$$x_{i}=a_{{1i}}u_{1}+a_{{2i}}u_{2}+\dots +a_{{Ni}}u_{N}$ . Если обозначить совокупность всех $\left(N\times <!--\; \times \; -->n\right)$$\left({N\times n}\right)$  матриц с элементами из $GF\left(q\right)$$GF\left({q}\right)$  как $A_N^n$$A_{N}^{n}$ , то для любого вектора $\stackrel{\to <!--\; \to \; -->}{x}=\left(x_1,x_2,\dots <!--\; \dots \; -->,x_n\right)$${\vec x}=\left({x_{1},x_{2},\dots ,x_{n}}\right)$  можно задать биекцию $A:X^n\to <!--\; \to \; -->A_N^n$$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\|$ 

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

$d\left(\stackrel{\to <!--\; \to \; -->}{x};\stackrel{\to <!--\; \to \; -->}{y}\right)=r\left(\stackrel{\to <!--\; \to \; -->}{x}-<!--\; -\; -->\stackrel{\to <!--\; \to \; -->}{y};q\right)$$d\left({{\vec x};{\vec y}}\right)=r\left({{\vec x}-{\vec y};q}\right)$ 

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

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

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

ЛитератураПравить

• Габидулин Э. М. Теория кодов с максимальным ранговым расстоянием // Пробл. передачи информ. — 1985. — Т. 21, вып. 1. — С. 3—16.
• Gabidulin E. M., Pilipchuk N. I. A new method of erasure correction by rank codes (англ.) // IEEE International Symposium on Information Theory, 2003. Proceedings — IEEE, 2003. — P. 423. — ISBN 978-0-7803-7728-8 — doi:10.1109/ISIT.2003.1228440
• Габидулин Э. М., Пилипчук Н. И. Симметричные ранговые коды // Пробл. передачи информ. — 2004. — Т. 40, вып. 2. — С. 3–18. — doi:10.1023/B:PRIT.0000043925.67309.C6
• Kshevetskiy A. S., Gabidulin E. M. The new construction of rank codes (англ.) // Information Theory, 2005. ISIT 2005. Proceedings. International Symposium on — IEEE, 2005. — P. 2105—2108. — ISBN 978-0-7803-9151-2 — ISSN 2157-8095 — doi:10.1109/ISIT.2005.1523717

СсылкиПравить

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