Ранжируйте код исправления ошибок - Rank error-correcting code - Wikipedia

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

А код ранга является алгебраическим линейным кодом над конечным полем ${ Displaystyle GF (д ^ {N})}$ похожий на Код Рида – Соломона.

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

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

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

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

${ 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 влево ({д ^ {N}} вправо)}$ - ранг соответствующей матрицы ${ Displaystyle А влево ({ vec {х}} вправо)}$ над полем ${ displaystyle GF left ({q} right)}$ обозначается ${ displaystyle r left ({{ vec {x}}; q} right)}$.

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

${ displaystyle d left ({{ vec {x}}; { vec {y}}} right) = r left ({{ vec {x}} - { vec {y}}; q }верно)}$

Код ранга

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

Формирующая матрица

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

Определим силу Фробениуса ${ Displaystyle [я]}$ элемента ${ Displaystyle х в GF (д ^ {N})}$ в качестве

${ Displaystyle х ^ {[я]} = х ^ {q ^ {я mod N}}. ,}$

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

${ 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} ^ {[km]} & g_ {2} ^ {[km]} & dots & g_ {n} ^ {[км]} end {array}} right |,}$

куда ${ Displaystyle НОД (м, N) = 1}$.

Приложения

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

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

Смотрите также

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

Примечания

Рекомендации

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

внешняя ссылка

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