WikiSort.ru - Не сортированное

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

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

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

Определения

Пусть задано ${\displaystyle X^{n}}$  — 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.
  <a href='https://wikidata.org/wiki/Track:Q21766851'></a><a href='https://wikidata.org/wiki/Track:Q4130888'></a><a href='https://wikidata.org/wiki/Track:Q21766854'></a>
• 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
  <a href='https://wikidata.org/wiki/Track:Q4130888'></a><a href='https://wikidata.org/wiki/Track:Q27473237'></a><a href='https://wikidata.org/wiki/Track:Q27473251'></a><a href='https://wikidata.org/wiki/Track:Q27473259'></a>
• Габидулин Э. М., Пилипчук Н. И. Симметричные ранговые коды // Пробл. передачи информ. — 2004. — Т. 40, вып. 2. — С. 3–18. — doi:10.1023/B:PRIT.0000043925.67309.C6
  <a href='https://wikidata.org/wiki/Track:Q21766851'></a><a href='https://wikidata.org/wiki/Track:Q27473237'></a><a href='https://wikidata.org/wiki/Track:Q27473284'></a><a href='https://wikidata.org/wiki/Track:Q4130888'></a>
• 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
  <a href='https://wikidata.org/wiki/Track:Q27473358'></a><a href='https://wikidata.org/wiki/Track:Q26887242'></a><a href='https://wikidata.org/wiki/Track:Q4130888'></a><a href='https://wikidata.org/wiki/Track:Q27473350'></a>

Ссылки

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