Код BCH - BCH code

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

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

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

Определение и иллюстрация

Примитивные узкосмысловые коды BCH

Учитывая простое число q и основная сила q^м с положительными целыми числами м и d такой, что d ≤ q^м − 1, примитивный узкосмысловой код BCH над конечное поле (или поле Галуа) GF (q) с длиной кода п = q^м − 1 и расстояние по меньшей мере d строится следующим способом.

Позволять α быть примитивный элемент из GF (q^м).Для любого положительного целого числа я, позволять м_я(Икс) быть минимальный многочлен с коэффициентами в GF (q) из α^я. порождающий полином кода BCH определяется как наименьший общий множитель грамм(Икс) = lcm (м₁(Икс),…,м_{d − 1}(Икс))Видно, что грамм(Икс) - многочлен с коэффициентами в GF (q) и разделяет Икс^п − 1Таким образом, полиномиальный код, определяемый грамм(Икс) - циклический код.

Пример

Позволять q = 2 и м = 4 (следовательно п = 15). Мы рассмотрим разные значения d. За GF (16) = GF (2⁴) на основе полинома Икс⁴ + Икс + 1 с первобытным корнем α = Икс+0 есть минимальные многочлены м_я(Икс) с коэффициентами в GF (2) удовлетворение

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

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

${\displaystyle {\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 с ${\displaystyle d=2,3}$ имеет порождающий полином

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

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

Код BCH с ${\displaystyle d=4,5}$ имеет порождающий полином

${\displaystyle {\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 с ${\displaystyle d=6,7}$ имеет порождающий полином

${\displaystyle {\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 с ${\displaystyle d=8}$ и выше имеет порождающий полином

${\displaystyle {\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 с узким смыслом в двух отношениях.

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

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

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

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

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

Особые случаи

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

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

Характеристики

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

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

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

Код BCH имеет минимальное расстояние Хэмминга не менее ${\displaystyle d}$.

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

Предположим, что ${\displaystyle p(x)}$ это кодовое слово с меньшим, чем ${\displaystyle d}$ ненулевые условия. потом ${\displaystyle 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}.}$ Напомним, что ${\displaystyle \alpha ^{c},\ldots ,\alpha ^{c+d-2}}$ корни ${\displaystyle g(x),}$ следовательно из ${\displaystyle p(x)}$. Отсюда следует, что ${\displaystyle b_{1},\ldots ,b_{d-1}}$ удовлетворяют следующим уравнениям, для каждого ${\displaystyle i\in \{c,\dotsc ,c+d-2\}}$: ${\displaystyle p(\alpha ^{i})=b_{1}\alpha ^{ik_{1}}+b_{2}\alpha ^{ik_{2}}+\cdots +b_{d-1}\alpha ^{ik_{d-1}}=0.}$ В матричной форме имеем ${\displaystyle {\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}}.}$ Определитель этой матрицы равен ${\displaystyle \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).}$ Матрица ${\displaystyle V}$ рассматривается как Матрица Вандермонда, а его определитель ${\displaystyle \det(V)=\prod _{1\leq i<j\leq d-1}\left(\alpha ^{k_{j}}-\alpha ^{k_{i}}\right),}$ который не равен нулю. Отсюда следует, что ${\displaystyle b_{1},\ldots ,b_{d-1}=0,}$ следовательно ${\displaystyle p(x)=0.}$

Код BCH циклический.

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

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

Кодирование

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

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

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

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

${\displaystyle s(x)=p(x)g(x)}$

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

${\displaystyle 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}$

Затем вычислите (также более ${\displaystyle GF(2)}$):

${\displaystyle {\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}.

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

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

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

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

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

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

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

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

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

Расшифровка

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

1. Рассчитайте синдромы s_j для полученного вектора
2. Определите количество ошибок т и полином локатора ошибок Λ (х) от синдромов
3. Вычислите корни полинома местоположения ошибки, чтобы найти местоположения ошибки Икс_я
4. Рассчитайте значения ошибок Y_я в тех местах ошибки
5. Исправьте ошибки

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

Рассчитайте синдромы

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

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

за ${\displaystyle j=c}$ к ${\displaystyle c+d-2.}$

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

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

Вычислить полином местоположения ошибки

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

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

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

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

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

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

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

Первый шаг - поиск, совместимый с компьютерными синдромами и с минимально возможными ${\displaystyle t,}$ полином локатора:

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

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

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

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

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

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

Теперь о процедуре алгоритма Петерсона – Горенштейна – Цирлера.^[9] Ожидайте, что у нас будет как минимум 2т синдромы s_c, …, s_c+2т−1. Позволять v = т.

1. Начните с создания ${\displaystyle S_{v\times v}}$ матрица с элементами, которые являются значениями синдромов

   ${\displaystyle 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}}.}$

2. Создать ${\displaystyle c_{v\times 1}}$ вектор с элементами
   ${\displaystyle C_{v\times 1}={\begin{bmatrix}s_{c+v}\\s_{c+v+1}\\\vdots \\s_{c+2v-1}\end{bmatrix}}.}$
3. Позволять ${\displaystyle \Lambda }$ обозначают неизвестные коэффициенты полинома, которые задаются
   ${\displaystyle \Lambda _{v\times 1}={\begin{bmatrix}\lambda _{v}\\\lambda _{v-1}\\\vdots \\\lambda _{1}\end{bmatrix}}.}$
4. Сформируем матричное уравнение
   ${\displaystyle S_{v\times v}\Lambda _{v\times 1}=-C_{v\times 1\,}.}$
5. Если определитель матрицы ${\displaystyle S_{v\times v}}$ отлична от нуля, то мы действительно можем найти обратную матрицу и найти значения неизвестных ${\displaystyle \Lambda }$ значения.
6. Если ${\displaystyle \det \left(S_{v\times v}\right)=0,}$ затем следуйте

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

   продолжить с начала декодирования Петерсона, сделав меньшие ${\displaystyle S_{v\times v}}$
7. После того, как у вас есть значения ${\displaystyle \Lambda }$, у вас есть многочлен локатора ошибок.
8. Прекратите процедуру Петерсона.

Факторный полином локатора ошибок

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

Нули Λ (Икс) находятся α^−я₁, …, α^−я_v.

Рассчитать значения ошибок

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

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

${\displaystyle {\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}}}$

Алгоритм Форни

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

Позволять

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

${\displaystyle 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]

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

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

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

куда

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

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

${\displaystyle 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, поэтому выражение упрощается до:

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

Объяснение расчета алгоритма Форни

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

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

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

${\displaystyle {\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}}}$

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

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

Благодаря ${\displaystyle v\leqslant d-1}$ у нас есть

${\displaystyle \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).}$

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

${\displaystyle \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).}$

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

В качестве формальная производная

${\displaystyle \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),}$

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

${\displaystyle \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).}$

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

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

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

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

уступая:

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

куда

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}.}$

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

${\displaystyle 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}.}$

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

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

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

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

${\displaystyle 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}.}$

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

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

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

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

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

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

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

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

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

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

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

Примеры расшифровки

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

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

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

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

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

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

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

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

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

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

вычислить

${\displaystyle 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}.}$

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

${\displaystyle {\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}}}$

We have reached polynomial of degree at most 3, and as

${\displaystyle {\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}},}$

мы получили

${\displaystyle {\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}}.}$

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

${\displaystyle 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}.}$

Позволять ${\displaystyle \Lambda (x)=\alpha ^{3}+\alpha ^{-5}x+\alpha ^{6}x^{2}.}$ Don't worry that ${\displaystyle \lambda _{0}\neq 1.}$ Find by brute force a root of ${\displaystyle \Lambda .}$ The roots are ${\displaystyle \alpha ^{2},}$ и ${\displaystyle \alpha ^{10}}$ (after finding for example ${\displaystyle \alpha ^{2}}$ we can divide ${\displaystyle \Lambda }$ by corresponding monom ${\displaystyle \left(x-\alpha ^{2}\right)}$ and the root of resulting monom could be found easily).

Позволять

${\displaystyle {\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}}}$

Let us look for error values using formula

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

куда ${\displaystyle \alpha ^{-i_{j}}}$ корни ${\displaystyle \Xi (x).}$ ${\displaystyle \Xi '(x)=\alpha ^{2}x^{2}.}$ We get

${\displaystyle {\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}}}$

Fact, that ${\displaystyle e_{3}=e_{4}=1,}$ should not be surprising.

Corrected code is therefore [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Decoding with unreadable characters with a small number of errors

Let us show the algorithm behaviour for the case with small number of errors. Let the received word is [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].

Again, replace the unreadable characters by zeros while creating the polynomial reflecting their positions ${\displaystyle \Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).}$Compute the syndromes ${\displaystyle s_{1}=\alpha ^{4},s_{2}=\alpha ^{-7},s_{3}=\alpha ^{1},s_{4}=\alpha ^{1},s_{5}=\alpha ^{0},}$ и ${\displaystyle s_{6}=\alpha ^{2}.}$Create syndrome polynomial

${\displaystyle {\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}}}$

Let us run the extended Euclidean algorithm:

${\displaystyle {\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}}}$

We have reached polynomial of degree at most 3, and as

${\displaystyle {\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}},}$

мы получили

${\displaystyle {\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}}.}$

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

${\displaystyle 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.}$

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

Позволять

${\displaystyle {\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}}}$

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

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

Мы получили

${\displaystyle {\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}}}$

Дело в том, что ${\displaystyle e_{3}=1}$ не должно быть ничего удивительного.

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

Цитаты

1. Рид и Чен 1999, п. 189
2. Hocquenghem 1959
3. Боз и Рэй-Чаудхури, 1960
4. «Система кодирования Phobos Lander: программное обеспечение и анализ» (PDF). Получено 25 февраля 2012.
5. «Описание продукта Sandforce SF-2500/2600». Получено 25 февраля 2012.
6. http://pqc-hqc.org/doc/hqc-specification_2020-05-29.pdf
7. Гилл н.д., п. 3
8. Lidl & Pilz 1999, п. 229
9. Горенштейн, Петерсон и Цирлер 1960
10. Гилл н.д., п. 47
11. Ясуо Сугияма, Масао Касахара, Сигейчи Хирасава и Тошихико Намекава. Метод решения ключевого уравнения для декодирования кодов Гоппа. Информация и контроль, 27: 87–99, 1975.

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

Основные источники

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

Вторичные источники

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

дальнейшее чтение

• Блахут, Ричард Э. (2003), Алгебраические коды для передачи данных (2-е изд.), Издательство Кембриджского университета, ISBN  0-521-55374-1
• Гилберт, В. Дж .; Николсон, В. К. (2004), Современная алгебра с приложениями (2-е изд.), Джон Вили
• Lin, S .; Костелло, Д. (2004), Кодирование с контролем ошибок: основы и приложения, Englewood Cliffs, NJ: Prentice-Hall
• MacWilliams, F.J .; Слоан, Н. Дж. А. (1977), Теория кодов, исправляющих ошибки, Нью-Йорк, Нью-Йорк: Издательская компания Северной Голландии.
• Рудра, Атри, CSE 545, Коды с исправлением ошибок: комбинаторика, алгоритмы и приложения, Университет Буффало, архив из оригинал на 2010-07-02, получено 21 апреля, 2010