Двоичный код Гоппы — код коррекции ошибок из класса общих , описанный Валерием Денисовичем Гоппой. В сравнении с другими вариантами, бинарная структура даёт несколько математических преимуществ, а также подходит для общего использования в вычислительной технике и телекоммуникациях. Двоичные коды Гоппы обладают интересными свойствами, полезными в криптосистемах, подобных McEliece.
Строение и свойства Двоичный код Гоппы определяется как многочлен степени над конечным полем без конечного числа нулей, и последовательность из различных элементов , которые не являются корнями или полиномами.
Ключи принадлежат ядру функции, формируя подпространство :
Код определён, как пара с минимальной длиной , таким образом, он может исправить ошибок в слове длиной , используя ключи размером . Он также обладает удобной матрицей контроля чётности в виде:
Эта форма матрицы контроля чётности состоит из определителя Вандермонда и диагональной матрицы , имеет форму, схожую с проверочными матрицами . Таким образом, в этой форме могут использоваться альтернативные декодеры. Они обычно обеспечивают только ограниченную возможность исправления ошибок (чаще всего ).
Для практических целей матрица проверки на чётность кода Гоппы обычно преобразуется в более удобную для использования компьютером двоичную форму с помощью конструкции трассировки, которая преобразует -на- матрицу над в двоичную матрицу -на-, разделив полиномиальные коэффициенты на последовательных рядов.
Декодирование Обычно декодирование двоичного кода Гоппы производится алгоритмом Паттерсона, который способен эффективно исправлять ошибки (он исправляет все обнаруженные ошибки), и который также достаточно прост в реализации.
Алгоритм Паттерсона преобразует синдром в вектор ошибок. Предполагается, что синдром двоичного слова примет вид:
Альтернативная форма матрицы контроля чётности основана на формуле для и может быть использована для создания такого синдрома с простым произведением матриц.
Далее алгоритм производит расчёт . Это не удается, когда , но это тот случай, когда входное слово является ключом, поэтому исправление ошибок не требуется.
Использованием расширенного алгоритма Евклида сводится к многочленам и , так, что , при этом и .
Наконец, многочлен, определяющий расположение ошибок, вычисляется как . При этом в двоичном случае для исправления ошибок достаточно их найти, так как существует только одно отличное значение.
Если исходный ключ был декодирован и — двоичный вектор ошибок, то:
.
Разложение на множители или оценка всех корней дает достаточно информации, чтобы восстановить вектор ошибок и исправить их.
Свойства и использование Двоичные коды Гоппы обладают специфическим свойством — они исправляют все ошибок, в то время как троичные и прочие коды исправляют только . Асимптотически такая способность к исправлению ошибок соответствует известной границе Гилберта — Варшамова.
Благодаря способности исправления ошибок, с учётом высокой скорости кодирования и сложной формы матрицы проверки на чётность (которую обычно трудно отличить от случайной двоичной матрицы того же ранга) двоичные коды Гоппы используются в нескольких постквантовых криптосистемах, в частности, в криптосистеме McEliece и криптосистеме Нидеррейтера.
Примечания
Литература
Предыдущая версия
Категория:Теория кодирования