Код BCH

Код исправления ошибок

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

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

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

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

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

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

Пусть α — примитивный элемент GF ( q ^m ) . Для любого положительного целого числа i пусть m _i ( x ) будет минимальным многочленом с коэффициентами из GF( q ) от α ⁱ . Полином генератора кода BCH определяется как наименьшее общее кратное g ( x ) = lcm( m ₁ ( x ),…, m _{d - 1} ( x )) . Видно, что g ( x ) является многочленом с коэффициентами из GF( q ) и делит x ⁿ - 1 . Следовательно, полиномиальный код , определенный g ( x ), является циклическим кодом.

Пример

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

${\displaystyle m_{i}\left(\alpha ^{i}\right){\bmod {\left(z^{4}+z+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.}$

Как и раньше, пусть – примитивный корень степени из единицы и пусть – минимальный полином для всех . Генераторный полином кода BCH определяется как наименьшее общее кратное ${\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)).}$

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

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

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

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

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

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

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

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

Кодирование

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

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

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

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

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

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

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

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

Декодирование

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

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

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

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

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

${\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. Алгоритм Берлекэмпа – Мэсси
3. Алгоритм Евклида Сугиямы

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

Алгоритм Петерсона — это второй шаг обобщенной процедуры декодирования 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 t синдромов s _c , …, s _{c +2 t −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 }$

Нулями Λ( x ) являются α ^{- i ₁} , …, α ^{- i _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] Исправление нечитаемых символов также можно легко включить в алгоритм.

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

Как мы уже определили для формулы Форни, пусть ${\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 ⁴ ) с и . (Это используется в 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 ]. ${\displaystyle d=7}$ ${\displaystyle g(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+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 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 ] , что приводит к решению. Результирующий полином локатора ошибок имеет нули в точках и Показатели степени соответствуют местам ошибок. В этом примере нет необходимости вычислять значения ошибок, поскольку единственное возможное значение — 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 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 с добавлением на основе побитового исключающего ИЛИ.) ${\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}.}$ ${\displaystyle \alpha }$

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

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

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

${\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}.}$ ${\displaystyle \lambda _{0}\neq 1.}$ ${\displaystyle \Lambda .}$ ${\displaystyle \alpha ^{2},}$ ${\displaystyle \alpha ^{10}}$ ${\displaystyle \alpha ^{2}}$ ${\displaystyle \Lambda }$ ${\displaystyle \left(x-\alpha ^{2}\right)}$

Позволять

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

Найдем значения ошибок по формуле

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

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

На самом деле, это не должно вызывать удивления. ${\displaystyle 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].

Снова замените нечитаемые символы нулями, создавая полином, отражающий их позиции. Вычислите синдромы и создайте полином синдрома. ${\displaystyle \Gamma (x)=\left(\alpha ^{8}x-1\right)\left(\alpha ^{11}x-1\right).}$ ${\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}.}$

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

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

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

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

${\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. Хоквенгем, 1959 г.
3. Бозе и Рэй-Чаудхури 1960
4. «Система кодирования посадочного модуля Фобоса: программное обеспечение и анализ» (PDF) . Архивировано (PDF) из оригинала 9 октября 2022 г. Проверено 25 февраля 2012 г.
5. Марелли, Алессия; Микелони, Рино (2018). «Коды BCH для твердотельных накопителей». Внутри твердотельных накопителей (SSDS) . Серия Springer в области передовой микроэлектроники. Том. 37. С. 369–406. дои : 10.1007/978-981-13-0599-3_11. ISBN 978-981-13-0598-6. Проверено 23 сентября 2023 г.
6. http://pqc-hqc.org/doc/hqc-specification_2020-05-29.pdf ^{[ пустой URL-адрес PDF ]}
7. Гилл н.д., с. 3
8. Лидл и Пилц 1999, стр. 229
9. Горенштейн, Петерсон и Цирлер, 1960 г.
10. Гилл н.д., с. 47
11. Ясуо Сугияма, Масао Касахара, Сигейчи Хирасава и Тошихико Намекава. Метод решения ключевого уравнения для декодирования кодов Гоппы. Информация и контроль, 27:87–99, 1975.

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

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

• Хокенгем, А. (сентябрь 1959 г.), «Коды корректоров ошибок», Chiffres (на французском языке), Париж, 2 : 147–156.
• Бозе, Колорадо ; Рэй-Чаудхури, Д.К. (март 1960 г.), «О классе двоичных групповых кодов с исправлением ошибок» (PDF) , Information and Control , 3 (1): 68–79, doi : 10.1016/s0019-9958(60)90287- 4, ISSN  0890-5401, заархивировано (PDF) из оригинала 09 октября 2022 г.

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

• Гилл, Джон (nd), Примечания EE387 № 7, Раздаточный материал № 28 (PDF) , Стэнфордский университет, стр. 42–45, заархивировано (PDF) из оригинала 09 октября 2022 г. , получено 21 апреля 2010 г.^{[ мертвая ссылка ]} Конспекты курса, очевидно, переделываются на 2012 год: http://www.stanford.edu/class/ee387/. Архивировано 5 июня 2013 г. на Wayback Machine.
• Горенштейн, Дэниел ; Петерсон, В. Уэсли ; Цирлер, Нил (1960), «Коды Бозе-Чаудхури с коррекцией двух ошибок квазисовершенны», Information and Control , 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-е изд.), Джон Уайли
• Лин, С.; Костелло, Д. (2004), Кодирование контроля ошибок: основы и приложения , Энглвуд Клиффс, Нью-Джерси: Прентис-Холл
• МакВильямс, Ф.Дж.; Слоан, NJA (1977), Теория кодов, исправляющих ошибки , Нью-Йорк, Нью-Йорк: Издательство North-Holland Publishing Company.
• Рудра, Атри, CSE 545, Коды с исправлением ошибок: комбинаторика, алгоритмы и приложения, Университет Буффало, заархивировано из оригинала 2 июля 2010 г. , получено 21 апреля 2010 г.