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

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

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

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

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

Пусть будет n -мерным векторным пространством над конечным полем , где — степень простого числа, а — положительное целое число. Пусть , причем , будет базой как векторного пространства над полем .${\displaystyle X^{n}}$ ${\displaystyle GF\left({q^{N}}\right)}$${\displaystyle д}$${\displaystyle N}$${\displaystyle \left(u_{1},u_{2},\точки ,u_{N}\right)}$${\displaystyle u_{i}\in GF(q^{N})}$${\displaystyle GF\left({q^{N}}\right)}$${\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 {\vec {x}}=\left({x_{1},x_{2},\dots ,x_{n}}\right)}$${\displaystyle GF\left({q^{N}}\right)}$

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

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

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

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

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

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

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

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

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

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

где .${\displaystyle \НОД(м,N)=1}$

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

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

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

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

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