Код BCH

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

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

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

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

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

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

Пусть α — примитивный элемент группы GF( q ^м ) . Для любого положительного целого числа 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), удовлетворяющими

$m_{i}\left(\alpha ^{i}\right){\bmod {\left(z^{4}+z+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 бита контрольной суммы. Он также обозначается как: (15, 11) код BCH.

Код 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 бит контрольной суммы. Он также обозначается как: (15, 7) код BCH.

Код 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 бит контрольной суммы. Он также обозначается как: (15, 5) код BCH. (Этот конкретный полином-генератор имеет реальное применение в «информации о формате» 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 бит контрольной суммы. Он также обозначается как: (15, 1) код BCH. На самом деле в этом коде всего два кодовых слова: 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.$

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

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

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

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

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

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

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

показывать Доказательство
Each minimal polynomial $m_{i}(x)$ has degree at most $m$. Therefore, the least common multiple of $d-1$ of them has degree at most $(d-1)m$. Moreover, if $q=2,$ then $m_{i}(x)=m_{2i}(x)$ for all $i$. Therefore, $g(x)$ is the least common multiple of at most $d/2$ minimal polynomials $m_{i}(x)$ for odd indices $i,$ each of degree at most $m$.

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

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

Suppose that $p(x)$ is a code word with fewer than $d$ non-zero terms. Then $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}.$ Recall that $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$ are roots of $g(x),$ hence of $p(x)$. This implies that $b_{1},\ldots ,b_{d-1}$ satisfy the following equations, for each $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.$ In matrix form, we have ${\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}}.$ The determinant of this matrix equals $\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).$ The matrix $V$ is seen to be a Vandermonde matrix, and its determinant is $\det(V)=\prod _{1\leq i<j\leq d-1}\left(\alpha ^{k_{j}}-\alpha ^{k_{i}}\right),$ which is non-zero. It therefore follows that $b_{1},\ldots ,b_{d-1}=0,$ hence $p(x)=0.$

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

показывать Доказательство
A polynomial code of length $n$ is cyclic if and only if its generator polynomial divides $x^{n}-1.$ Since $g(x)$ is the minimal polynomial with roots $\alpha ^{c},\ldots ,\alpha ^{c+d-2},$ it suffices to check that each of $\alpha ^{c},\ldots ,\alpha ^{c+d-2}$ is a root of $x^{n}-1.$ This follows immediately from the fact that $\alpha$ is, by definition, an $n$th root of unity.

Кодирование

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

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

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

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

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

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

Здесь мы видим это $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)$

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

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

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

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

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

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

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

Полученный вектор $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)$

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

1. Алгоритм Петерсона – Горенштейна – Цирлера
2. Алгоритм Берлекэмпа – Мэсси
3. Алгоритм Евклида Сугиямы

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

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

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

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

1. Начните с создания $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}}.$

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

          if $v=0$
          then
                declare an empty error locator polynomial
                stop Peterson procedure.
          end
          set $v\leftarrow v-1$
   

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

Полином локатора факторной ошибки

Теперь, когда у вас есть $\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 ) являются α ^{− и ₁} , ..., а ^{- я _в} .

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

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

В случае двоичного 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).$

И полином оценки ошибок

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

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

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

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

Как мы уже определили для формулы Форни, пусть $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)$ требуется в формуле Форни.

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

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

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

Декодирование с нечитаемыми символами

Предположим тот же сценарий, но полученное слово имеет два нечитаемых символа [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0]. Заменяем нечитаемые символы нулями, создавая полином, отражающий их позиции. $\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}.$ (Используя логарифмическую запись, независимую от GF(2 ⁴ ) изоморфизмы. Для проверки вычислений мы можем использовать то же представление для сложения, что и в предыдущем примере. Шестнадцатеричное описание полномочий $\alpha$ являются последовательно 1,2,4,8,3,6,C,B,5,A,7,E,F,D,9 с добавлением на основе побитового исключающего ИЛИ.)

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

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

Позволять $\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.$

Позволять $\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].

Ссылки

Первоисточники

• Хокенгем, А. (сентябрь 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) из оригинала 9 октября 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, Коды с исправлением ошибок: комбинаторика, алгоритмы и приложения , Университет в Буффало, заархивировано из оригинала 18 декабря 2012 г.