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