Ранговый код

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

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

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

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

Любой элемент ${\displaystyle x_{i}\in GF\left({q^{N}}\right)}$ можно однозначно представить как ${\displaystyle x_{i}=a_{1i}u_{1}+a_{2i}u_{2}+\dots +a_{Ni}u_{N}}$. Если обозначить совокупность всех ${\displaystyle \left({N\times n}\right)}$ матриц с элементами из ${\displaystyle GF\left({q}\right)}$ как ${\displaystyle A_{N}^{n}}$, то для любого вектора ${\displaystyle {\vec {x}}=\left({x_{1},x_{2},\dots ,x_{n}}\right)}$ можно задать биекцию ${\displaystyle A:X^{n}\to A_{N}^{n}}$ с помощью следующего правила:

${\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\|}$

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

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

Тогда произвольное множество {x₁, x₂, ..., x_M} векторов из Xⁿ назовём кодом (с кодовым расстоянием ${\displaystyle 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.