Код BCH

В теории кодирования , то БЧЕ коды или коды Боуз-Чоудхури-Хоквенгем образуют класс циклических кодов с исправлением ошибок , которые построены с использованием полиномов над конечным полем (также называется поле Галуа ). Коды BCH были изобретены в 1959 году французским математиком Алексисом Хоккенгемом и независимо в 1960 году Раджем Бозом и Д.К. Рэем-Чаудхури . ^[1]^[2]^[3] Название Bose – Chaudhuri – Hocquenghem (и аббревиатура BCH) происходит от инициалов фамилий изобретателей (ошибочно в случае Рэя-Чаудхури).

Одной из ключевых особенностей кодов BCH является то, что во время разработки кода существует точный контроль над количеством ошибок символов, исправляемых кодом. В частности, можно разработать двоичные коды BCH, которые могут исправить несколько битовых ошибок. Еще одно преимущество кодов BCH заключается в простоте их декодирования, а именно с помощью алгебраического метода, известного как синдромное декодирование . Это упрощает конструкцию декодера для этих кодов с использованием небольшого маломощного электронного оборудования.

БЧХ коды используются в таких приложениях, как спутниковая связь, ^[4] компактные дисковые проигрыватели, DVD - диски , жесткие диски , твердотельные накопители , ^[5] квантово-стойкие криптографические ^[6] , и двумерные штрих - коды .

Определение и иллюстрация [ править ]

Примитивные узкосмысленные коды BCH [ править ]

Для простого числа $q$ и степени простого $q m$ с натуральными числами $m$ и $d,$ таких что $d \leq q m - 1$ , примитивный узкосмысловой код BCH над конечным полем (или полем Галуа) $GF (q)$ с длиной кода $n = q m - 1$ и расстояние не менее $d$ строится следующим способом.

Пусть $α$ быть примитивный элемент из $GF (кв м)$ . Для любого натурального числа $i$ пусть $m i (x)$ будет минимальным многочленом с коэффициентами из $GF (q)$ при $α i$ . Порождающий полином кода БЧХ определяется как наименьшее общее кратное $г (х) = LCM (м 1 (х), ..., м d - 1 (х))$ . Видно, что $g (x)$ - многочлен с коэффициентами из $GF (q),$ делящий $x n - 1$ . Следовательно, полиномиальный код, определяемый $g (x),$ является циклическим кодом.

Пример [ править ]

Пусть $q = 2$ и $m = 4$ (следовательно, $n = 15$ ). Мы рассмотрим разные значения $d$ . Для $GF (16) = GF (2 4)$ на основе многочлена $x 4 + x + 1$ с первообразным корнем $α = x +0$ существуют минимальные многочлены $m i (x)$ с коэффициентами в $GF (2),$ удовлетворяющие

{\ displaystyle m_ {i} \ left (\ alpha ^ {i} \ right) {\ bmod {\ left (x ^ {4} + x + 1 \ right)}} = 0.}

Минимальные многочлены четырнадцати степеней $α$ равны

{\begin{aligned}m_{1}(x)&=m_{2}(x)=m_{4}(x)=m_{8}(x)=x^{4}+x+1,\\m_{3}(x)&=m_{6}(x)=m_{9}(x)=m_{12}(x)=x^{4}+x^{3}+x^{2}+x+1,\\m_{5}(x)&=m_{10}(x)=x^{2}+x+1,\\m_{7}(x)&=m_{11}(x)=m_{13}(x)=m_{14}(x)=x^{4}+x^{3}+1.\end{aligned}}

Код BCH с порождающим полиномом $d=2,3$

g(x)={\rm {lcm}}(m_{1}(x),m_{2}(x))=m_{1}(x)=x^{4}+x+1.\,

Он имеет минимальное расстояние Хэмминга не менее 3 и исправляет до одной ошибки. Поскольку порождающий полином имеет степень 4, этот код имеет 11 бит данных и 4 бита контрольной суммы.

Код BCH с порождающим полиномом $d=4,5$

{\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x))=m_{1}(x)m_{3}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)=x^{8}+x^{7}+x^{6}+x^{4}+1.\end{aligned}}

Он имеет минимальное расстояние Хэмминга не менее 5 и исправляет до двух ошибок. Поскольку порождающий полином имеет степень 8, этот код имеет 7 бит данных и 8 битов контрольной суммы.

Код BCH с порождающим полиномом $d=6,7$

{\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x),m_{5}(x),m_{6}(x))=m_{1}(x)m_{3}(x)m_{5}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1.\end{aligned}}

Он имеет минимальное расстояние Хэмминга не менее 7 и исправляет до трех ошибок. Поскольку порождающий полином имеет степень 10, этот код имеет 5 битов данных и 10 битов контрольной суммы. (Этот конкретный генераторный полином имеет реальное применение в шаблонах формата QR-кода .)

Код BCH с и выше имеет порождающий полином $d=8$

{\begin{aligned}g(x)&={\rm {lcm}}(m_{1}(x),m_{2}(x),...,m_{14}(x))=m_{1}(x)m_{3}(x)m_{5}(x)m_{7}(x)\\&=\left(x^{4}+x+1\right)\left(x^{4}+x^{3}+x^{2}+x+1\right)\left(x^{2}+x+1\right)\left(x^{4}+x^{3}+1\right)=x^{14}+x^{13}+x^{12}+\cdots +x^{2}+x+1.\end{aligned}}

Этот код имеет минимальное расстояние Хэмминга 15 и исправляет 7 ошибок. Он имеет 1 бит данных и 14 битов контрольной суммы. Фактически, в этом коде всего два кодовых слова: 000000000000000 и 111111111111111.

Общие коды BCH [ править ]

Общие коды BCH отличаются от примитивных кодов BCH с узким смыслом в двух отношениях.

Во-первых, можно ослабить требование быть примитивным элементом . Расслабляя это требование, длина кода изменяется от до в порядке элемента $\alpha$ $\mathrm {GF} (q^{m})$ $q^{m}-1$ $\mathrm {ord} (\alpha ),$ $\alpha .$

Во-вторых, последовательные корни порождающего полинома могут запускаться вместо $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$ $\alpha ,\ldots ,\alpha ^{d-1}.$

Определение. Зафиксируем конечное поле, где - степень простого числа. Выберите положительные целые числа так , чтобы и был мультипликативным порядком по модулю $GF(q),$ $q$ $m,n,d,c$ $2\leq d\leq n,$ ${\rm {gcd}}(n,q)=1,$ $m$ $q$ $n.$

Как и раньше, пусть будет примитивный корень из единицы в и пусть будет минимальный многочлен над из для всех The порождающего полинома кода БЧХ определяется как наименьшее общее кратное $\alpha$ n {\displaystyle n} $GF(q^{m}),$ $m_{i}(x)$ $GF(q)$ $\alpha ^{i}$ $i.$ $g(x)={\rm {lcm}}(m_{c}(x),\ldots ,m_{c+d-2}(x)).$

Примечание: если, как в упрощенном определении, то это 1, а порядок по модулю равен Таким образом, упрощенное определение действительно является частным случаем общего. $n=q^{m}-1$ ${\rm {gcd}}(n,q)$ $q$ $n$ $m.$

Особые случаи [ править ]

Код BCH с называется кодом BCH с узким смыслом . $c=1$
Код BCH с называется примитивным . $n=q^{m}-1$

Генераторный полином BCH-кода имеет коэффициенты из В общем случае циклический код с порождающим полиномом называется BCH-кодом над BCH-кодом и порождающий полином с последовательными степенями в качестве корней является одним типом кода Рида-Соломона, где алфавит декодера (синдромов) совпадает с алфавитом канала (данных и порождающего полинома), все элементы . ^[7] Другой тип кода Рида-Соломона - это исходный код Рида-Соломона, который не является кодом BCH. $g(x)$ $\mathrm {GF} (q).$ $\mathrm {GF} (q^{p})$ $g(x)$ $\mathrm {GF} (q^{p}).$ $\mathrm {GF} (q^{m})$ $g(x)$ $\alpha$ $\mathrm {GF} (q^{m})$

Свойства [ править ]

Генераторный полином кода БЧХ имеет степень не выше . Более того, если и , порождающий полином имеет степень не выше . $(d-1)m$ $q=2$ $c=1$ $dm/2$

Доказательство

Каждый минимальный многочлен имеет степень не выше . Следовательно, наименьшее общее кратное из них имеет степень не выше . Тем более, если то для всех . Следовательно, является наименьшим общим кратным не более чем минимальных многочленов для нечетных индексов, каждый из которых имеет степень не выше . $m_{i}(x)$ $m$ $d-1$ $(d-1)m$ $q=2,$ $m_{i}(x)=m_{2i}(x)$ $i$ $g(x)$ $d/2$ $m_{i}(x)$ $i,$ $m$

Код BCH имеет по крайней мере минимальное расстояние Хэмминга . $d$

Доказательство

Предположим, что это кодовое слово с меньшим количеством ненулевых членов. Затем $p(x)$ $d$

p(x)=b_{1}x^{k_{1}}+\cdots +b_{d-1}x^{k_{d-1}},{\text{ where }}k_{1}<k_{2}<\cdots <k_{d-1}.

Напомним, что являются корнями отсюда . Это означает, что для каждого из них выполняются следующие уравнения : $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$ $g(x),$ $p(x)$ $b_{1},\ldots ,b_{d-1}$ $i\in \{c,\dotsc ,c+d-2\}$

p(\alpha ^{i})=b_{1}\alpha ^{ik_{1}}+b_{2}\alpha ^{ik_{2}}+\cdots +b_{d-1}\alpha ^{ik_{d-1}}=0.

В матричной форме имеем

{\begin{bmatrix}\alpha ^{ck_{1}}&\alpha ^{ck_{2}}&\cdots &\alpha ^{ck_{d-1}}\\\alpha ^{(c+1)k_{1}}&\alpha ^{(c+1)k_{2}}&\cdots &\alpha ^{(c+1)k_{d-1}}\\\vdots &\vdots &&\vdots \\\alpha ^{(c+d-2)k_{1}}&\alpha ^{(c+d-2)k_{2}}&\cdots &\alpha ^{(c+d-2)k_{d-1}}\\\end{bmatrix}}{\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{d-1}\end{bmatrix}}={\begin{bmatrix}0\\0\\\vdots \\0\end{bmatrix}}.

Определитель этой матрицы равен

\left(\prod _{i=1}^{d-1}\alpha ^{ck_{i}}\right)\det {\begin{pmatrix}1&1&\cdots &1\\\alpha ^{k_{1}}&\alpha ^{k_{2}}&\cdots &\alpha ^{k_{d-1}}\\\vdots &\vdots &&\vdots \\\alpha ^{(d-2)k_{1}}&\alpha ^{(d-2)k_{2}}&\cdots &\alpha ^{(d-2)k_{d-1}}\\\end{pmatrix}}=\left(\prod _{i=1}^{d-1}\alpha ^{ck_{i}}\right)\det(V).

Видно, что матрица является матрицей Вандермонда , и ее определитель равен $V$

\det(V)=\prod _{1\leq i<j\leq d-1}\left(\alpha ^{k_{j}}-\alpha ^{k_{i}}\right),

который не равен нулю. Отсюда следует, что отсюда $b_{1},\ldots ,b_{d-1}=0,$ $p(x)=0.$

Код BCH является циклическим.

Доказательство

Полином код длины циклично тогда и только тогда , когда его порождающий полином делит Поскольку минимальный многочлен с корнями достаточно проверить , что каждый из является корнем Это непосредственно вытекает из того факта , что есть, по определению, корень из единицы . $n$ $x^{n}-1.$ $g(x)$ $\alpha ^{c},\ldots ,\alpha ^{c+d-2},$ $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$ $x^{n}-1.$ $\alpha$ $n$

Кодировка [ править ]

Поскольку любой многочлен, который является кратным полиному генератора, является допустимым кодовым словом BCH, кодирование BCH - это просто процесс поиска некоторого полинома, в котором генератор является фактором.

Сам код BCH не определяет значения коэффициентов полинома; концептуально, единственной задачей алгоритма декодирования BCH является поиск действительного кодового слова с минимальным расстоянием Хэмминга до полученного кодового слова. Следовательно, код BCH может быть реализован либо как систематический код, либо нет, в зависимости от того, как разработчик решает встроить сообщение в закодированный полином.

Несистематическое кодирование: сообщение как фактор [ править ]

Самый простой способ найти многочлен, кратный генератору, - это вычислить произведение некоторого произвольного полинома и генератора. В этом случае произвольный многочлен можно выбрать, используя символы сообщения в качестве коэффициентов.

s(x)=p(x)g(x)

В качестве примера рассмотрим генераторный полином , выбранный для использования в двоичном коде BCH (31, 21), используемом POCSAG и другими. Чтобы закодировать 21-битное сообщение {101101110111101111101}, мы сначала представляем его как полином над : $g(x)=x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1$ $GF(2)$

p(x)=x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1

Затем вычислите (также по окончании ): $GF(2)$

{\begin{aligned}s(x)&=p(x)g(x)\\&=\left(x^{20}+x^{18}+x^{17}+x^{15}+x^{14}+x^{13}+x^{11}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+1\right)\left(x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{3}+1\right)\\&=x^{30}+x^{29}+x^{26}+x^{25}+x^{24}+x^{22}+x^{19}+x^{17}+x^{16}+x^{15}+x^{14}+x^{12}+x^{10}+x^{9}+x^{8}+x^{6}+x^{5}+x^{4}+x^{2}+1\end{aligned}}

Таким образом, переданное кодовое слово - {1100111010010111101011101110101}.

Приемник может использовать эти биты в качестве коэффициентов и после исправления ошибок, чтобы гарантировать правильное кодовое слово, может повторно вычислить $s(x)$ $p(x)=s(x)/g(x)$

Систематическая кодировка: сообщение как префикс [ править ]

Систематический код - это код, в котором сообщение дословно отображается где-то внутри кодового слова. Следовательно, систематическое кодирование BCH включает в себя сначала встраивание полинома сообщения в полином кодового слова, а затем настройку коэффициентов оставшихся (не связанных с сообщением) членов, чтобы гарантировать, что он делится на . $s(x)$ $g(x)$

Этот метод кодирования использует тот факт, что вычитание остатка от делимого дает результат, кратный делителю. Следовательно, если мы возьмем наш полином сообщения, как и раньше, и умножим его на (чтобы «сдвинуть» сообщение с пути остатка), мы можем затем использовать евклидово деление многочленов, чтобы получить: $p(x)$ $x^{n-k}$

p(x)x^{n-k}=q(x)g(x)+r(x)

Здесь мы видим, что это действительное кодовое слово. Поскольку всегда степень меньше (которая является степенью ), мы можем безопасно вычесть ее, не изменяя ни один из коэффициентов сообщения, поэтому у нас есть as $q(x)g(x)$ $r(x)$ $n-k$ $g(x)$ $p(x)x^{n-k}$ $s(x)$

s(x)=q(x)g(x)=p(x)x^{n-k}-r(x)

Сверх (то есть с двоичными кодами BCH) этот процесс неотличим от добавления циклического контроля избыточности , и если систематический двоичный код BCH используется только для целей обнаружения ошибок, мы видим, что коды BCH являются просто обобщением математики циклических проверки избыточности . $GF(2)$

Преимущество систематического кодирования состоит в том, что получатель может восстановить исходное сообщение, отбросив все, что находится после первых коэффициентов, после выполнения исправления ошибок. $k$

Расшифровка [ править ]

Существует множество алгоритмов декодирования кодов BCH. Наиболее распространенные из них следуют этой общей схеме:

Вычислить синдромы s _j для полученного вектора
Определите количество ошибок t и полином локатора ошибок Λ (x) из синдромов
Вычислите корни полинома местоположения ошибок, чтобы найти местоположения ошибок X _i.
Вычислить значения ошибки Y _i в этих местах ошибки.
Исправьте ошибки

Во время некоторых из этих шагов алгоритм декодирования может определить, что полученный вектор содержит слишком много ошибок и не может быть исправлен. Например, если подходящее значение t не найдено, коррекция не будет выполнена. В усеченном (не примитивном) коде местоположение ошибки может быть вне допустимого диапазона. Если полученный вектор содержит больше ошибок, чем код может исправить, декодер может неосознанно выдать явно действительное сообщение, отличное от того, которое было отправлено.

Рассчитайте синдромы [ править ]

Полученный вектор представляет собой сумму правильного кодового слова и неизвестного вектора ошибок. Значения синдромов формируются путем рассмотрения как полинома и его оценки. Таким образом, синдромы равны ^[8] $R$ $C$ $E.$ $R$ $\alpha ^{c},\ldots ,\alpha ^{c+d-2}.$

s_{j}=R\left(\alpha ^{j}\right)=C\left(\alpha ^{j}\right)+E\left(\alpha ^{j}\right)

для к $j=c$ $c+d-2.$

Так как нули из которых являются кратными, изучение значений синдрома таким образом изолирует вектор ошибки, чтобы можно было приступить к его поиску. $\alpha ^{j}$ $g(x),$ $C(x)$ $C\left(\alpha ^{j}\right)=0.$

Если ошибки нет, для всех. Если синдромы все равны нулю, то декодирование выполнено. $s_{j}=0$ $j.$

Вычислить многочлен местоположения ошибки [ править ]

Если есть ненулевые синдромы, значит, есть ошибки. Декодер должен выяснить, сколько ошибок и где они находятся.

Если есть единственная ошибка, запишите это как где - расположение ошибки и ее величина. Тогда первые два синдрома $E(x)=e\,x^{i},$ $i$ $e$

{\begin{aligned}s_{c}&=e\,\alpha ^{c\,i}\\s_{c+1}&=e\,\alpha ^{(c+1)\,i}=\alpha ^{i}s_{c}\end{aligned}}

таким образом, вместе они позволяют нам вычислить и предоставить некоторую информацию о (полностью определяя ее в случае кодов Рида – Соломона). $e$ $i$

Если есть две или более ошибок,

E(x)=e_{1}x^{i_{1}}+e_{2}x^{i_{2}}+\cdots \,

Не сразу очевидно, как начать решать возникающие синдромы для неизвестных и $e_{k}$ $i_{k}.$

Первым шагом является поиск, совместимый с вычисленными синдромами и с минимально возможным многочленом локатора: $t,$

\Lambda (x)=\prod _{j=1}^{t}\left(x\alpha ^{i_{j}}-1\right)

Два популярных алгоритма для этой задачи:

Алгоритм Петерсона – Горенштейна – Цирлера
Алгоритм Берлекампа – Месси

Алгоритм Петерсона – Горенштейна – Цирлера [ править ]

Алгоритм Петерсона - это шаг 2 обобщенной процедуры декодирования BCH. Алгоритм Петерсона используется для вычисления коэффициентов полинома локатора ошибок полинома. $\lambda _{1},\lambda _{2},\dots ,\lambda _{v}$

\Lambda (x)=1+\lambda _{1}x+\lambda _{2}x^{2}+\cdots +\lambda _{v}x^{v}.

Теперь о процедуре алгоритма Петерсона – Горенштейна – Цирлера. ^[9] Ожидайте, что у нас будет не менее 2 t синдромов s _c ,…, s _{c +2 t −1} . Пусть v = t .

Начните с создания матрицы с элементами, которые являются значениями синдрома $S_{v\times v}$
$S_{v\times v}={\begin{bmatrix}s_{c}&s_{c+1}&\dots &s_{c+v-1}\\s_{c+1}&s_{c+2}&\dots &s_{c+v}\\\vdots &\vdots &\ddots &\vdots \\s_{c+v-1}&s_{c+v}&\dots &s_{c+2v-2}\end{bmatrix}}.$
Создайте вектор с элементами $c_{v\times 1}$
$C_{v\times 1}={\begin{bmatrix}s_{c+v}\\s_{c+v+1}\\\vdots \\s_{c+2v-1}\end{bmatrix}}.$
Обозначим через неизвестные коэффициенты полинома, которые задаются формулой $\Lambda$
$\Lambda _{v\times 1}={\begin{bmatrix}\lambda _{v}\\\lambda _{v-1}\\\vdots \\\lambda _{1}\end{bmatrix}}.$
Сформируем матричное уравнение
$S_{v\times v}\Lambda _{v\times 1}=-C_{v\times 1\,}.$
Если определитель матрицы отличен от нуля, то мы действительно можем найти обратную матрицу и найти значения неизвестных значений. $S_{v\times v}$ $\Lambda$

Если тогда следовать

\det \left(S_{v\times v}\right)=0,

 если  $v=0$  потом объявить пустой многочлен локатора ошибок остановить процедуру Петерсона. конец набор  $v\leftarrow v-1$

продолжаем с самого начала декодирования Петерсона, делая меньшие

S_{v\times v}

После того, как у вас есть значения , у вас будет многочлен локатора ошибок. $\Lambda$
Прекратите процедуру Петерсона.

Факторный многочлен локатора ошибок [ править ]

Теперь, когда у вас есть многочлен, его корни могут быть найдены в форме путем перебора, например, с использованием алгоритма поиска Chien . Экспоненциальные степени примитивного элемента дадут позиции, где возникают ошибки в полученном слове; отсюда и название полином «локатора ошибок». $\Lambda (x)$ $\Lambda (x)=\left(\alpha ^{i_{1}}x-1\right)\left(\alpha ^{i_{2}}x-1\right)\cdots \left(\alpha ^{i_{v}}x-1\right)$ $\alpha$

Нули Λ ( x ) равны α ^{- i ₁} ,…, α ^{- i _v} .

Вычислить значения ошибок [ править ]

После того, как места ошибок известны, следующим шагом будет определение значений ошибок в этих местах. Затем значения ошибок используются для исправления полученных значений в этих местах для восстановления исходного кодового слова.

В случае двоичного BCH (со всеми читаемыми символами) это тривиально; просто переверните биты принятого слова в этих позициях, и мы получим исправленное кодовое слово. В более общем случае веса ошибок могут быть определены путем решения линейной системы $e_{j}$

{\begin{aligned}s_{c}&=e_{1}\alpha ^{c\,i_{1}}+e_{2}\alpha ^{c\,i_{2}}+\cdots \\s_{c+1}&=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \\&{}\ \vdots \end{aligned}}

Алгоритм Форни [ править ]

Однако есть более эффективный метод, известный как алгоритм Форни .

Позволять

S(x)=s_{c}+s_{c+1}x+s_{c+2}x^{2}+\cdots +s_{c+d-2}x^{d-2}.

v\leqslant d-1,\lambda _{0}\neq 0\qquad \Lambda (x)=\sum _{i=0}^{v}\lambda _{i}x^{i}=\lambda _{0}\prod _{k=0}^{v}\left(\alpha ^{-i_{k}}x-1\right).

И полином вычислителя ошибок ^[10]

\Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}

Ну наконец то:

\Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},

где

i\cdot x:=\sum _{k=1}^{i}x.

Если бы синдромы можно было объяснить словом ошибки, которое может быть ненулевым только на позициях , то значения ошибок равны $i_{k}$

e_{k}=-{\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right) \over \alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}.

Для кодов BCH с узким смыслом c = 1, поэтому выражение упрощается до:

e_{k}=-{\Omega \left(\alpha ^{-i_{k}}\right) \over \Lambda '\left(\alpha ^{-i_{k}}\right)}.

Объяснение вычисления алгоритма Форни [ править ]

Он основан на интерполяции Лагранжа и методах производящих функций .

Рассмотрим и для простоты предположим для и для Тогда $S(x)\Lambda (x),$ $\lambda _{k}=0$ $k>v,$ $s_{k}=0$ $k>c+d-2.$

S(x)\Lambda (x)=\sum _{j=0}^{\infty }\sum _{i=0}^{j}s_{j-i+1}\lambda _{i}x^{j}.

{\begin{aligned}S(x)\Lambda (x)&=S(x)\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{i=0}^{d-2}\sum _{j=1}^{v}e_{j}\alpha ^{(c+i)\cdot i_{j}}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\sum _{i=0}^{d-2}\left(\alpha ^{i_{j}}\right)^{i}x^{i}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\left\{\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\right\}\left\{\lambda _{0}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\right\}\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}{\frac {\left(x\alpha ^{i_{j}}\right)^{d-1}-1}{x\alpha ^{i_{j}}-1}}\prod _{\ell =1}^{v}\left(\alpha ^{i_{\ell }}x-1\right)\\&=\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\left(\left(x\alpha ^{i_{j}}\right)^{d-1}-1\right)\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right)\end{aligned}}

Мы хотим вычислить неизвестные, и мы могли бы упростить контекст, удалив термины. Это приводит к полиному оценщика ошибок $e_{j},$ $\left(x\alpha ^{i_{j}}\right)^{d-1}$

\Omega (x)\equiv S(x)\Lambda (x){\bmod {x^{d-1}}}.

Благодаря нам $v\leqslant d-1$

\Omega (x)=-\lambda _{0}\sum _{j=1}^{v}e_{j}\alpha ^{ci_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right).

Благодаря (уловке с интерполяцией Лагранжа) сумма вырождается только в одно слагаемое для $\Lambda$ $x=\alpha ^{-i_{k}}$

\Omega \left(\alpha ^{-i_{k}}\right)=-\lambda _{0}e_{k}\alpha ^{c\cdot i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).

Чтобы получить, нужно просто избавиться от продукта. Мы могли бы вычислить продукт непосредственно из уже вычисленных корней из , но мы могли бы использовать более простую форму. $e_{k}$ $\alpha ^{-i_{j}}$ $\Lambda ,$

Как формальная производная

\Lambda '(x)=\lambda _{0}\sum _{j=1}^{v}\alpha ^{i_{j}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{j\}}\left(\alpha ^{i_{\ell }}x-1\right),

мы снова получаем только одно слагаемое в

\Lambda '\left(\alpha ^{-i_{k}}\right)=\lambda _{0}\alpha ^{i_{k}}\prod _{\ell \in \{1,\cdots ,v\}\setminus \{k\}}\left(\alpha ^{i_{\ell }}\alpha ^{-i_{k}}-1\right).

Итак, наконец

e_{k}=-{\frac {\alpha ^{i_{k}}\Omega \left(\alpha ^{-i_{k}}\right)}{\alpha ^{c\cdot i_{k}}\Lambda '\left(\alpha ^{-i_{k}}\right)}}.

Эта формула полезна при вычислении формальной производной формы $\Lambda$

\Lambda (x)=\sum _{i=1}^{v}\lambda _{i}x^{i}

уступая:

\Lambda '(x)=\sum _{i=1}^{v}i\cdot \lambda _{i}x^{i-1},

где

i\cdot x:=\sum _{k=1}^{i}x.

Декодирование на основе расширенного алгоритма Евклида [ править ]

Альтернативный процесс поиска полинома Λ и полинома локатора ошибок основан на адаптации расширенного алгоритма Евклида Ясуо Сугияма . ^[11] Исправление нечитаемых символов также может быть легко включено в алгоритм.

Пусть будут позиции нечитаемых символов. Создается многочлен, локализующий эти позиции. Установите значения в нечитаемых позициях на 0 и вычислите синдромы. $k_{1},...,k_{k}$ $\Gamma (x)=\prod _{i=1}^{k}\left(x\alpha ^{k_{i}}-1\right).$

Как мы уже определили для формулы Форни, пусть $S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}.$

Давайте запустим расширенный алгоритм Евклида для определения наименьшего общего делителя многочленов и цель состоит не в том, чтобы найти наименьший общий делитель, а найти многочлен степени не выше и многочлены такие, что низкая степень гарантий, которые удовлетворяли бы расширенным (по ) определяющим условиям для $S(x)\Gamma (x)$ $x^{d-1}.$ $r(x)$ $\lfloor (d+k-3)/2\rfloor$ $a(x),b(x)$ $r(x)=a(x)S(x)\Gamma (x)+b(x)x^{d-1}.$ $r(x)$ $a(x)$ $\Gamma$ $\Lambda .$

Определение и использование вместо в формуле Фурни даст нам значения ошибок. $\Xi (x)=a(x)\Gamma (x)$ $\Xi$ $\Lambda (x)$

Основным преимуществом алгоритма является то, что он тем временем вычисляет требуемые в формуле Форни. $\Omega (x)=S(x)\Xi (x){\bmod {x}}^{d-1}=r(x)$

Объяснение процесса декодирования [ править ]

Цель состоит в том, чтобы найти кодовое слово, которое минимально отличается от принятого слова на читаемых позициях. Выражая полученное слово как сумму ближайшего кодового слова и слова ошибки, мы пытаемся найти слово ошибки с минимальным количеством ненулевых символов на читаемых позициях. Syndrom ограничивает слово ошибки по условию $s_{i}$

s_{i}=\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}.

Мы могли бы написать эти условия отдельно или создать многочлен

S(x)=\sum _{i=0}^{d-2}s_{c+i}x^{i}

и сравнить коэффициенты при степенях к $0$ $d-2.$

S(x){\stackrel {\{0,\cdots ,\,d-2\}}{=}}E(x)=\sum _{i=0}^{d-2}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}\alpha ^{cj}x^{i}.

Предположим, что на позиции есть нечитаемая буква, мы можем заменить набор синдромов набором синдромов, определяемых уравнением. Предположим, что для слова ошибки все ограничения исходным набором синдромов выполняются, чем $k_{1},$ $\{s_{c},\cdots ,s_{c+d-2}\}$ $\{t_{c},\cdots ,t_{c+d-3}\}$ $t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}.$ $\{s_{c},\cdots ,s_{c+d-2}\}$

t_{i}=\alpha ^{k_{1}}s_{i}-s_{i+1}=\alpha ^{k_{1}}\sum _{j=0}^{n-1}e_{j}\alpha ^{ij}-\sum _{j=0}^{n-1}e_{j}\alpha ^{j}\alpha ^{ij}=\sum _{j=0}^{n-1}e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)\alpha ^{ij}.

Новый набор синдромов ограничивает вектор ошибок

f_{j}=e_{j}\left(\alpha ^{k_{1}}-\alpha ^{j}\right)

так же , как оригинальный набор синдромов ограничил вектор ошибки , за исключением координат , где мы имеем равен нуль, если для цели фиксирующих позиций ошибок мы смогли изменить набор синдромов аналогичным образом , чтобы отразить все нечитаемые символы. Это сокращает набор синдромов на $e_{j}.$ $k_{1},$ $f_{k_{1}}=0,$ $f_{j}$ $e_{j}=0.$ $k.$

В полиномиальной формулировке замена набора синдромов на набор синдромов приводит к $\{s_{c},\cdots ,s_{c+d-2}\}$ $\{t_{c},\cdots ,t_{c+d-3}\}$

T(x)=\sum _{i=0}^{d-3}t_{c+i}x^{i}=\alpha ^{k_{1}}\sum _{i=0}^{d-3}s_{c+i}x^{i}-\sum _{i=1}^{d-2}s_{c+i}x^{i-1}.

Следовательно,

xT(x){\stackrel {\{1,\cdots ,\,d-2\}}{=}}\left(x\alpha ^{k_{1}}-1\right)S(x).

После замены на потребовалось бы уравнение для коэффициентов при степенях $S(x)$ $S(x)\Gamma (x)$ $k,\cdots ,d-2.$

Можно рассмотреть поиск ошибочных позиций с точки зрения устранения влияния заданных позиций так же, как и для нечитаемых символов. Если мы нашли такие позиции, устранение их влияния приводит к получению набора синдромов, состоящего из всех нулей, то существует вектор ошибок с ошибками только по этим координатам. Если обозначить полином, исключающий влияние этих координат, получим $v$ $\Lambda (x)$

S(x)\Gamma (x)\Lambda (x){\stackrel {\{k+v,\cdots ,d-2\}}{=}}0.

В алгоритме Евклида мы пытаемся исправить максимум ошибок (на читаемых позициях), потому что с большим количеством ошибок может быть больше кодовых слов на том же расстоянии от полученного слова. Следовательно, поскольку мы ищем, уравнение должно выполняться для коэффициентов, близких к степеням, начиная с ${\tfrac {1}{2}}(d-1-k)$ $\Lambda (x)$

k+\left\lfloor {\frac {1}{2}}(d-1-k)\right\rfloor .

В формуле Форни можно было бы умножить на скаляр, получив тот же результат. $\Lambda (x)$

Может случиться так, что алгоритм Евклида найдет степень выше, чем имеющая число различных корней, равное его степени, где формула Фурни сможет исправить ошибки во всех своих корнях, в любом случае исправление такого количества ошибок может быть рискованным (особенно без каких-либо других ограничения на полученное слово). Обычно после получения более высокой степени мы решаем не исправлять ошибки. Исправление может потерпеть неудачу, если имеет корни с большей кратностью или количество корней меньше его степени. Отказ также может быть обнаружен по формуле Форни, возвращающей ошибку за пределами переданного алфавита. $\Lambda (x)$ ${\tfrac {1}{2}}(d-1-k)$ $\Lambda (x)$ $\Lambda (x)$

Исправьте ошибки [ править ]

Используя значения ошибок и местоположение ошибки, исправьте ошибки и сформируйте скорректированный кодовый вектор путем вычитания значений ошибок в местах ошибки.

Примеры расшифровки [ править ]

Расшифровка двоичного кода без нечитаемых символов [ править ]

Рассмотрим код BCH в GF (2 ⁴ ) с и . (Это используется в QR - кодах .) Пусть сообщение , которое будет передано составляет [1 1 0 1 1], или в полиномиальной нотации, Символы «контрольная сумма» рассчитывается путем деления путем и взятия остатка, в результате чего или [1 0 0 0 0 1 0 1 0 0]. Они добавляются к сообщению, поэтому переданное кодовое слово - [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0]. $d=7$ $g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1$ $M(x)=x^{4}+x^{3}+x+1.$ $x^{10}M(x)$ $g(x)$ $x^{9}+x^{4}+x^{2}$

Теперь представьте, что при передаче есть две битовые ошибки, поэтому полученное кодовое слово равно [1 0 0 1 1 1 0 0 0 1 1 0 1 0 0]. В полиномиальных обозначениях:

R(x)=C(x)+x^{13}+x^{5}=x^{14}+x^{11}+x^{10}+x^{9}+x^{5}+x^{4}+x^{2}

Чтобы исправить ошибки, сначала рассчитайте синдромы. Взяв, что у нас есть и Далее, примените процедуру Петерсона, уменьшив строку следующей расширенной матрицы. $\alpha =0010,$ $s_{1}=R(\alpha ^{1})=1011,$ $s_{2}=1001,$ $s_{3}=1011,$ $s_{4}=1101,$ $s_{5}=0001,$ $s_{6}=1001.$

\left[S_{3\times 3}|C_{3\times 1}\right]={\begin{bmatrix}s_{1}&s_{2}&s_{3}&s_{4}\\s_{2}&s_{3}&s_{4}&s_{5}\\s_{3}&s_{4}&s_{5}&s_{6}\end{bmatrix}}={\begin{bmatrix}1011&1001&1011&1101\\1001&1011&1101&0001\\1011&1101&0001&1001\end{bmatrix}}\Rightarrow {\begin{bmatrix}0001&0000&1000&0111\\0000&0001&1011&0001\\0000&0000&0000&0000\end{bmatrix}}

Из-за нулевой строки $S 3 \times 3$ является сингулярным, что неудивительно, поскольку в кодовое слово были внесены только две ошибки. Однако левый верхний угол матрицы идентичен $[S 2 \times 2 | C 2 \times 1]$ , что приводит к решению . Результирующий полином локатора ошибок имеет нули в и Показатели степени соответствуют местоположениям ошибок. В этом примере нет необходимости вычислять значения ошибок, так как единственное возможное значение - 1. $\lambda _{2}=1000,$ $\lambda _{1}=1011.$ $\Lambda (x)=1000x^{2}+1011x+0001,$ $0100=\alpha ^{-13}$ $0111=\alpha ^{-5}.$ $\alpha$

Расшифровка с нечитаемыми символами [ править ]

Предположим тот же сценарий, но полученное слово содержит два нечитаемых символа [1 0 0? 1 1? 0 0 1 1 0 1 0 0]. Мы заменяем нечитаемые символы нулями при создании полинома, отражающего их положение. Мы вычисляем синдромы и (Используя логарифмическую нотацию, которая не зависит от изоморфизмов GF (2 ⁴ ). Для проверки вычислений мы можем использовать то же представление для сложения, которое использовалось в предыдущем пример. Шестнадцатеричное описание степеней : последовательно 1,2,4,8,3,6, C, B, 5, A, 7, E, F, D, 9 с добавлением на основе побитового xor.) $\Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).$ $s_{1}=\alpha ^{-7},s_{2}=\alpha ^{1},s_{3}=\alpha ^{4},s_{4}=\alpha ^{2},s_{5}=\alpha ^{5},$ $s_{6}=\alpha ^{-7}.$ $\alpha$

Сделаем синдромный многочлен

S(x)=\alpha ^{-7}+\alpha ^{1}x+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{5}x^{4}+\alpha ^{-7}x^{5},

вычислить

S(x)\Gamma (x)=\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}.

Запустите расширенный алгоритм Евклида:

{\begin{aligned}&{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+\alpha ^{7}x^{6}+\alpha ^{-3}x^{7}\\x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}+2\alpha ^{7}x^{6}+2\alpha ^{-3}x^{7}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}+\alpha ^{-3}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{-5}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\left(\alpha ^{-7}+\alpha ^{3}\right)x+\left(\alpha ^{3}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-5}+\alpha ^{-6}\right)x^{3}+\left(\alpha ^{3}+\alpha ^{1}\right)x^{4}+2\alpha ^{-6}x^{5}+2x^{6}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\left(1+\alpha ^{-4}\right)+\left(\alpha ^{1}+\alpha ^{2}\right)x+\alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{4}x+\alpha ^{-1}x^{2}+\alpha ^{6}x^{3}+\alpha ^{-1}x^{4}+\alpha ^{5}x^{5}\\\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}&\alpha ^{7}+\alpha ^{-3}x\\\alpha ^{4}+\alpha ^{-5}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{-5}+\alpha ^{-4}x&1\\1&0\end{pmatrix}}\\&\qquad {\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\left(\alpha ^{7}+\alpha ^{-7}\right)+\left(2\alpha ^{-7}+\alpha ^{4}\right)x+\left(\alpha ^{-5}+\alpha ^{-6}+\alpha ^{-1}\right)x^{2}+\left(\alpha ^{-7}+\alpha ^{-4}+\alpha ^{6}\right)x^{3}+\left(\alpha ^{4}+\alpha ^{-6}+\alpha ^{-1}\right)x^{4}+2\alpha ^{5}x^{5}\end{pmatrix}}\\[6pt]={}&{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}{\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix}}.\end{aligned}}

Мы достигли полинома степени не выше 3, и при

{\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&\alpha ^{4}+\alpha ^{-5}x\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},

мы получили

{\begin{pmatrix}-\left(\alpha ^{4}+\alpha ^{-5}x\right)&\alpha ^{-3}+\alpha ^{5}x+\alpha ^{7}x^{2}\\\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}&-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{-3}+\alpha ^{-2}x+\alpha ^{0}x^{2}+\alpha ^{-2}x^{3}+\alpha ^{-6}x^{4}\\\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}\end{pmatrix}}.

Следовательно,

S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}\right)-\left(\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}\right)x^{6}=\alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}.

Пусть не волнуйтесь , что Find грубой силой корня корней и (после того, как найти, например , мы можем разделить на соответствующем monom и корень полученного monom можно найти легко). $\Lambda (x)=\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}.$ $\lambda _{0}\neq 1.$ $\Lambda .$ $\alpha ^{2},$ $\alpha ^{10}$ $\alpha ^{2}$ $\Lambda$ $\left(x-\alpha ^{2}\right)$

Позволять

{\begin{aligned}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{4}x^{2}+\alpha ^{2}x^{3}+\alpha ^{-5}x^{4}\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{-4}+\alpha ^{4}x+\alpha ^{2}x^{2}+\alpha ^{-5}x^{3}{\bmod {x^{6}}}\end{aligned}}

Будем искать значения ошибок по формуле

e_{j}=-{\frac {\Omega \left(\alpha ^{-i_{j}}\right)}{\Xi '\left(\alpha ^{-i_{j}}\right)}},

где корни Мы получаем $\alpha ^{-i_{j}}$ $\Xi (x).$ $\Xi '(x)=\alpha ^{2}x^{2}.$

{\begin{aligned}e_{1}&=-{\frac {\Omega (\alpha ^{4})}{\Xi '(\alpha ^{4})}}={\frac {\alpha ^{-4}+\alpha ^{-7}+\alpha ^{-5}+\alpha ^{7}}{\alpha ^{-5}}}={\frac {\alpha ^{-5}}{\alpha ^{-5}}}=1\\e_{2}&=-{\frac {\Omega (\alpha ^{7})}{\Xi '(\alpha ^{7})}}={\frac {\alpha ^{-4}+\alpha ^{-4}+\alpha ^{1}+\alpha ^{1}}{\alpha ^{1}}}=0\\e_{3}&=-{\frac {\Omega (\alpha ^{10})}{\Xi '(\alpha ^{10})}}={\frac {\alpha ^{-4}+\alpha ^{-1}+\alpha ^{7}+\alpha ^{-5}}{\alpha ^{7}}}={\frac {\alpha ^{7}}{\alpha ^{7}}}=1\\e_{4}&=-{\frac {\Omega (\alpha ^{2})}{\Xi '(\alpha ^{2})}}={\frac {\alpha ^{-4}+\alpha ^{6}+\alpha ^{6}+\alpha ^{1}}{\alpha ^{6}}}={\frac {\alpha ^{6}}{\alpha ^{6}}}=1\end{aligned}}

На самом деле, это не должно вызывать удивления. $e_{3}=e_{4}=1,$

Таким образом, исправленный код будет [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Расшифровка нечитаемых символов с небольшим количеством ошибок [ править ]

Покажем поведение алгоритма для случая с небольшим количеством ошибок. Пусть полученное слово [1 0 0? 1 1? 0 0 0 1 0 1 0 0].

Опять же, замените нечитаемые символы нулями при создании полинома, отражающего их положение. Вычислите синдромы и создайте полином синдрома. $\Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).$ $s_{1}=\alpha ^{4},s_{2}=\alpha ^{-7},s_{3}=\alpha ^{1},s_{4}=\alpha ^{1},s_{5}=\alpha ^{0},$ $s_{6}=\alpha ^{2}.$

{\begin{aligned}S(x)&=\alpha ^{4}+\alpha ^{-7}x+\alpha ^{1}x^{2}+\alpha ^{1}x^{3}+\alpha ^{0}x^{4}+\alpha ^{2}x^{5},\\S(x)\Gamma (x)&=\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}.\end{aligned}}

Запустим расширенный алгоритм Евклида:

{\begin{aligned}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}&={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+\alpha ^{-1}x^{6}+\alpha ^{6}x^{7}\\x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}x^{6}\\\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}+2\alpha ^{-1}x^{6}+2\alpha ^{6}x^{7}\end{pmatrix}}\\&={\begin{pmatrix}\alpha ^{-1}+\alpha ^{6}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{3}+\alpha ^{1}x&1\\1&0\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\left(\alpha ^{-5}+\alpha ^{5}\right)x+2\alpha ^{-7}x^{2}+2\alpha ^{6}x^{3}+2\alpha ^{4}x^{4}+2\alpha ^{2}x^{5}+2x^{6}\end{pmatrix}}\\&={\begin{pmatrix}\left(1+\alpha ^{2}\right)+\left(\alpha ^{0}+\alpha ^{-6}\right)x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}{\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}\end{aligned}}

Мы достигли полинома степени не выше 3, и при

{\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&1\end{pmatrix}}={\begin{pmatrix}1&0\\0&1\end{pmatrix}},

мы получили

{\begin{pmatrix}-1&\alpha ^{-1}+\alpha ^{6}x\\\alpha ^{3}+\alpha ^{1}x&-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)\end{pmatrix}}{\begin{pmatrix}S(x)\Gamma (x)\\x^{6}\end{pmatrix}}={\begin{pmatrix}\alpha ^{4}+\alpha ^{7}x+\alpha ^{5}x^{2}+\alpha ^{3}x^{3}+\alpha ^{1}x^{4}+\alpha ^{-1}x^{5}\\\alpha ^{7}+\alpha ^{0}x\end{pmatrix}}.

Следовательно,

S(x)\Gamma (x)\left(\alpha ^{3}+\alpha ^{1}x\right)-\left(\alpha ^{-7}+\alpha ^{7}x+\alpha ^{7}x^{2}\right)x^{6}=\alpha ^{7}+\alpha ^{0}x.

Пусть не волнуйтесь , что Корень IS $\Lambda (x)=\alpha ^{3}+\alpha ^{1}x.$ $\lambda _{0}\neq 1.$ $\Lambda (x)$ $\alpha ^{3-1}.$

Позволять

{\begin{aligned}\Xi (x)&=\Gamma (x)\Lambda (x)=\alpha ^{3}+\alpha ^{-7}x+\alpha ^{-4}x^{2}+\alpha ^{5}x^{3},\\\Omega (x)&=S(x)\Xi (x)\equiv \alpha ^{7}+\alpha ^{0}x{\bmod {x^{6}}}\end{aligned}}

Будем искать значения ошибок по формуле где - корни многочлена $e_{j}=-\Omega \left(\alpha ^{-i_{j}}\right)/\Xi '\left(\alpha ^{-i_{j}}\right),$ $\alpha ^{-i_{j}}$ $\Xi (x).$

\Xi '(x)=\alpha ^{-7}+\alpha ^{5}x^{2}.

Мы получили

{\begin{aligned}e_{1}&=-{\frac {\Omega \left(\alpha ^{4}\right)}{\Xi '\left(\alpha ^{4}\right)}}={\frac {\alpha ^{7}+\alpha ^{4}}{\alpha ^{-7}+\alpha ^{-2}}}={\frac {\alpha ^{3}}{\alpha ^{3}}}=1\\e_{2}&=-{\frac {\Omega \left(\alpha ^{7}\right)}{\Xi '\left(\alpha ^{7}\right)}}={\frac {\alpha ^{7}+\alpha ^{7}}{\alpha ^{-7}+\alpha ^{4}}}=0\\e_{3}&=-{\frac {\Omega \left(\alpha ^{2}\right)}{\Xi '\left(\alpha ^{2}\right)}}={\frac {\alpha ^{7}+\alpha ^{2}}{\alpha ^{-7}+\alpha ^{-6}}}={\frac {\alpha ^{-3}}{\alpha ^{-3}}}=1\end{aligned}}

В этом нет ничего удивительного. $e_{3}=1$

Таким образом, исправленный код будет [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Цитаты [ править ]

^ Рид и Чен 1999 , стр. 189
^ Hocquenghem 1959
↑ Боз и Рэй-Чаудхури, 1960
^ "Система кодирования Phobos Lander: программное обеспечение и анализ" (PDF) . Проверено 25 февраля 2012 года .
^ «Описание продукта Sandforce SF-2500/2600» . Проверено 25 февраля 2012 года .
^ http://pqc-hqc.org/doc/hqc-specification_2020-05-29.pdf
^ Гилл nd , стр. 3
^ Lidl & Pilz 1999 , стр. 229
^ Горенштейн, Peterson & Zierler 1960
^ Гилл nd , стр. 47
^ Ясуо Сугияма, Масао Kasahara, Shigeichi Хирасава и Toshihiko Namekawa. Метод решения ключевого уравнения для декодирования кодов Гоппа. Информация и контроль, 27: 87–99, 1975.

Ссылки [ править ]

Первоисточники [ править ]

Hocquenghem, A. (сентябрь 1959 г.), "Codes correcteurs d'erreurs", Chiffres (на французском языке), Париж, 2 : 147–156.
Bose, RC ; Рэй-Чаудхури, Д.К. (март 1960 г.), «Об одном классе двоичных групповых кодов с исправлением ошибок» (PDF) , Информация и управление , 3 (1): 68–79, DOI : 10.1016 / s0019-9958 (60) 90287- 4 , ISSN 0890-5401

Вторичные источники [ править ]

Джилл, Джон (nd), EE387 Notes # 7, раздаточный материал # 28 (PDF) , Стэнфордский университет, стр. 42–45 , получено 21 апреля 2010 г.^{[ мертвая ссылка ]} Заметки к курсу на 2012 год явно переделываются: http://www.stanford.edu/class/ee387/
Горенштейн, Даниэль ; Петерсон, У. Уэсли ; Цирлер, Нил (1960), «Коды Бозе-Чаудхури с исправлением двух ошибок являются квази-совершенными», Информация и управление , 3 (3): 291–294, DOI : 10.1016 / s0019-9958 (60) 90877-9
Лидл, Рудольф; Пильц, Гюнтер (1999), Прикладная абстрактная алгебра (2-е изд.), Джон Вили
Рид, Ирвинг С .; Чен, Сюэминь (1999), Кодирование с контролем ошибок для сетей передачи данных , Бостон, Массачусетс: Kluwer Academic Publishers , ISBN 0-7923-8528-4

Дальнейшее чтение [ править ]

Блахут, Ричард Э. (2003), Алгебраические коды для передачи данных (2-е изд.), Cambridge University Press , ISBN 0-521-55374-1
Гилберт, WJ; Николсон, WK (2004), Современная алгебра с приложениями (2-е изд.), Джон Вили
Lin, S .; Костелло, Д. (2004), Кодирование с контролем ошибок: основы и приложения , Englewood Cliffs, NJ: Prentice-Hall
MacWilliams, FJ; Слоан, штат Нью-Джерси (1977), Теория кодов с исправлением ошибок , Нью-Йорк, Нью-Йорк: издательство North-Holland Publishing Company
Рудра, Атри, CSE 545, Коды исправления ошибок: комбинаторика, алгоритмы и приложения , Университет в Буффало, заархивировано из оригинала 02.07.2010 , получено 21 апреля 2010 г.

[1] Рид и Чен 1999 , стр. 189

[2] Hocquenghem 1959

[3] Боз и Рэй-Чаудхури, 1960

[4] "Система кодирования Phobos Lander: программное обеспечение и анализ" (PDF) . Проверено 25 февраля 2012 года .

[5] «Описание продукта Sandforce SF-2500/2600» . Проверено 25 февраля 2012 года .

[6] ttp://pqc-hqc.org/doc/hqc-specification_2020-05-29.pdf

[7] Гилл nd , стр. 3

[8] Lidl & Pilz 1999 , стр. 229

[9] Горенштейн, Peterson & Zierler 1960

[Gill-Forney-10] Гилл nd , стр. 47

[11] Ясуо Сугияма, Масао Kasahara, Shigeichi Хирасава и Toshihiko Namekawa. Метод решения ключевого уравнения для декодирования кодов Гоппа. Информация и контроль, 27: 87–99, 1975.

[1]