Русская Википедия:Двоичный код Гоппы
Двоичный код Гоппы — код коррекции ошибок из класса общих Шаблон:Iw, описан Валерием Денисовичем Гоппой. В сравнении с другими вариантами, бинарная структура даёт несколько математических преимуществ, а также подходит для общего использования в вычислительной технике и телекоммуникациях. Двоичные коды Гоппы обладают интересными свойствами, полезными в криптосистемах, подобных McEliece[1].
Строение и свойства
Двоичный код Гоппы определяется как многочлен <math>g(x)</math> степени <math>t</math> над конечным полем <math>GF(2^m)</math> без конечного числа нулей, и последовательность <math>L</math> из <math>n</math> различных элементов <math>GF(2^m)</math>, которые не являются корнями или полиномами.
- <math>\forall i,j \in \{0,\ldots,n-1\}: L_i \in GF(2^m) \land (L_i = L_j \implies i=j) \land g(L_i) \neq 0</math>
Ключи принадлежат ядру функции, формируя подпространство <math>\{0,1\}^n</math>:
- <math>\Gamma(g,L)=\left\{ c \in \{0,1\}^n \left| \sum_{i=0}^{n-1} \frac{c_i}{x-L_i} \equiv 0 \mod g(x) \right. \right\}</math>
Код определён, как пара <math>(g,L)</math> с минимальной длиной <math>2t+1</math>, таким образом, он может исправить <math>t=\left\lfloor \frac{(2t+1)-1}{2} \right\rfloor</math> ошибок в слове длиной <math>n-mt</math>, используя ключи размером <math>n</math>. Он также обладает удобной Шаблон:Iw <math>H</math> в виде:
- <math>
H=VD=\begin{pmatrix} 1 & 1 & 1 & \cdots & 1\\ L_0^1 & L_1^1 & L_2^1 & \cdots & L_{n-1}^1\\ L_0^2 & L_1^2 & L_2^2 & \cdots & L_{n-1}^2\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ L_0^{t-1} & L_1^{t-1} & L_2^{t-1} & \cdots & L_{n-1}^{t-1} \end{pmatrix} \begin{pmatrix} \frac{1}{g(L_0)} & & & & \\
& \frac{1}{g(L_1)} & & & \\
& & \frac{1}{g(L_2)} & & \\
& & & \ddots & \\
& & & & \frac{1}{g(L_{n-1})}
\end{pmatrix} </math>
Эта форма матрицы контроля чётности состоит из определителя Вандермонда <math>V</math> и диагональной матрицы <math>D</math>, имеет форму, схожую с проверочными матрицами Шаблон:Iw. Таким образом, в этой форме могут использоваться альтернативные декодеры. Они обычно обеспечивают только ограниченную возможность исправления ошибок (чаще всего <math>t/2</math>).
Для практических целей матрица проверки на чётность кода Гоппы обычно преобразуется в более удобную для использования компьютером двоичную форму с помощью конструкции трассировки, которая преобразует <math>t</math>-на-<math>n</math> матрицу над <math>GF(2^m)</math> в двоичную матрицу <math>mt</math>-на-<math>n</math>, разделив полиномиальные коэффициенты <math>GF(2^m)</math> на <math>m</math> последовательных рядов.
Декодирование
Обычно декодирование двоичного кода Гоппы производится алгоритмом Паттерсона, который способен эффективно исправлять ошибки (он исправляет все <math>t</math> обнаруженные ошибкиШаблон:Уточнить), и который также достаточно прост в реализации.
Алгоритм Паттерсона преобразует синдром в вектор ошибок. Предполагается, что синдром двоичного слова <math>c=(c_0,\dots,c_{n-1})</math> примет вид:
- <math>s(x) \equiv \sum_{i=0}^{n-1} \frac{c_i}{x - L_i} \mod g(x)</math>
Альтернативная форма матрицы контроля чётности основана на формуле для <math>s(x)</math> и может быть использована для создания такого синдрома с простым произведением матриц.
Далее алгоритм производит расчёт <math>v(x) \equiv \sqrt{s(x)^{-1}-x} \mod g(x)</math>. Это не удается, когда <math>s(x) \equiv 0</math>, но это тот случай, когда входное слово является ключом, поэтому исправление ошибок не требуется.
Использованием расширенного алгоритма Евклида <math>v(x)</math> сводится к многочленам <math>a(x)</math> и <math>b(x)</math>, так, что <math>a(x) \equiv b(x)\cdot v(x) \mod g(x)</math>, при этом <math>\deg(a)\leqslant\lfloor t/2 \rfloor</math> и <math>\deg(b)\leqslant\lfloor (t-1)/2 \rfloor</math>.
Наконец, многочлен, определяющий расположение ошибок, вычисляется как <math>\sigma(x) = a(x)^2 + x\cdot b(x)^2</math>. При этом в двоичном случае для исправления ошибок достаточно их найти, так как существует только одно отличное значение.
Если исходный ключ был декодирован и <math>e=(e_0,e_1,\dots,e_{n-1})</math> — двоичный вектор ошибок, то:
- <math>\sigma(x) = \prod_{i=0}^{n-1} e_i(x-L_i) </math>.
Разложение на множители или оценка всех корней <math>\sigma(x)</math> дает достаточно информации, чтобы восстановить вектор ошибок и исправить их.
Свойства и использование
Двоичные коды Гоппы обладают специфическим свойством — они исправляют все <math>\deg(g)</math> ошибок, в то время как троичные и прочие коды исправляют только <math>\deg(g)/2</math>. Асимптотически такая способность к исправлению ошибок соответствует известной границе Гилберта — Варшамова.
Благодаря способности исправления ошибок, с учётом высокой скорости кодирования и сложной формы матрицы проверки на чётность (которую обычно трудно отличить от случайной двоичной матрицы того же ранга) двоичные коды Гоппы используются в нескольких постквантовых криптосистемах, в частности, в криптосистеме McEliece и криптосистеме Нидеррейтера.
Примечания
Литература
