Ранговый код, исправляющий ошибки

Ранговые коды
Классификация
Иерархия	Линейный блочный код Код ранга
Длина блока	н
Длина сообщения	к
Расстояние	п - к + 1
Размер алфавита	Q = q Н ( q простое число)
Обозначения	[ n , k , d ]-код
Алгоритмы
Берлекамп-Мэсси евклидов с полиномами Фробениуса

В теории кодирования ранговые коды (также называемые кодами Габидулина ) не являются двоичными. линейные коды, исправляющие ошибки, не над метрикой Хэмминга , а над ранговой метрикой. Они описали систематический способ создания кодов, которые могли бы обнаруживать и исправлять множественные случайные ошибки ранга . Добавляя избыточность с кодированием k -символьного слова к n- символьному слову, ранговый код может исправлять любые ошибки ранга до t = ⌊ ( d − 1)/2 ⌋, где d — кодовое расстояние. Как код стирания , он может исправить до d − 1 известных стираний.

Ранговый код — это алгебраический линейный код над конечным полем $GF(q^{N})$ аналогичный коду Рида-Соломона .

Ранг вектора выше $GF(q^{N})$ — максимальное количество линейно независимых компонентов по $GF(q)$. Ранговое расстояние между двумя векторами по $GF(q^{N})$ – ранг разности этих векторов.

Ранговый код исправляет все ошибки, ранг вектора ошибок которых не превышает t .

Показатель ранга

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

Каждый элемент $x_{i}\in GF\left({q^{N}}\right)$ может быть представлено как $x_{i}=a_{1i}u_{1}+a_{2i}u_{2}+\dots +a_{Ni}u_{N}$. Следовательно, каждый вектор ${\vec {x}}=\left({x_{1},x_{2},\dots ,x_{n}}\right)$ над $GF\left({q^{N}}\right)$ можно записать в виде матрицы:

${\vec {x}}=\left\|{\begin{array}{*{20}c}a_{1,1}&a_{1,2}&\ldots &a_{1,n}\\a_{2,1}&a_{2,2}&\ldots &a_{2,n}\\\ldots &\ldots &\ldots &\ldots \\a_{N,1}&a_{N,2}&\ldots &a_{N,n}\end{array}}\right\|$

Ранг вектора ${\vec {x}}$ над полем $GF\left({q^{N}}\right)$ — ранг соответствующей матрицы $A\left({\vec {x}}\right)$ над полем $GF\left({q}\right)$ обозначается $r\left({{\vec {x}};q}\right)$.

Набор всех векторов ${\vec {x}}$ это пространство $X^{n}=A_{N}^{n}$. Карта ${\vec {x}}\to r\left({\vec {x}};q\right)$) определяет норму над $X^{n}$ и показатель ранга :

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

Код ранга

Набор $\{x_{1},x_{2},\dots ,x_{n}\}$ векторов из $X^{n}$ называется кодом с кодовым расстоянием $d=\min d\left(x_{i},x_{j}\right)$. Если множество также образует k -мерное подпространство $X^{n}$, то он называется линейным ( n , k )-кодом с расстоянием $d$. Такой метрический код линейного ранга всегда удовлетворяет границе Синглтона $d\leq n-k+1$ с равенством.

Генерирующая матрица

Существует несколько известных конструкций ранговых кодов, которые представляют собой коды максимального рангового расстояния (или MRD) с d = n - k + 1. Самый простой в построении код известен как (обобщенный) код Габидулина. Он был открыт сначала Дельсартом (который назвал его синглтон-системой ), а затем Габидулином. (и Кшевецкий ).

Определим степень Фробениуса. $[i]$ элемента $x\in GF(q^{N})$ как

$x^{[i]}=x^{q^{i\mod N}}.\,$

Тогда каждый вектор ${\vec {g}}=(g_{1},g_{2},\dots ,g_{n}),~g_{i}\in GF(q^{N}),~n\leq N$, линейно независимый по $GF(q)$, определяет порождающую матрицу MRD ( n , k , d = n − k + 1)-кода.

$G=\left\|{\begin{array}{*{20}c}g_{1}&g_{2}&\dots &g_{n}\\g_{1}^{[m]}&g_{2}^{[m]}&\dots &g_{n}^{[m]}\\g_{1}^{[2m]}&g_{2}^{[2m]}&\dots &g_{n}^{[2m]}\\\dots &\dots &\dots &\dots \\g_{1}^{[(k-1)m]}&g_{2}^{[(k-1)m]}&\dots &g_{n}^{[(k-1)m]}\end{array}}\right\|,$

где $\gcd(m,N)=1$.

Приложения

Существует несколько предложений по криптосистемам с открытым ключом, основанным на ранговых кодах. Однако большинство из них оказались небезопасными (см., например, Journal of Cryptology, апрель 2008 г. ).

Ранговые коды также полезны для исправления ошибок и стирания при сетевом кодировании .

См. также

• Линейный код
• Исправление ошибок Рида – Соломона
• Алгоритм Берлекэмпа – Мэсси
• Сетевое кодирование

Ссылки

• Габидулин, Эрнст М. (1985), "Теория кодов с максимальным ранговым расстоянием" , Проблемы передачи информации , 21 (1): 1–12
• Кшевецкий, Александр; Габидулин, Эрнст М. (4–9 сентября 2005 г.). «Новая конструкция ранговых кодов». Слушания. Международный симпозиум по теории информации, 2005 г. ISIT 2005 г. стр. 2105–2108. дои : 10.1109/ISIT.2005.1523717 . ISBN  978-0-7803-9151-2 . S2CID   11679865 .
• Габидулин Эрнст М.; Пилипчук Нина Ивановна (29 июня – 4 июля 2003 г.). «Новый метод коррекции стираний по ранговым кодам». Международный симпозиум IEEE по теории информации, 2003. Труды . п. 423. дои : 10.1109/ISIT.2003.1228440 . ISBN  978-0-7803-7728-8 . S2CID   122552232 .

Внешние ссылки

• Реализация MATLAB рангового метрического кодека