Код BCH

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

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

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

• 1 Определение и иллюстрация
  • 1.1 Примитивные узкосмысловые коды BCH
    • 1.1. 1 Пример
  • 1.2 Общие коды BCH
  • 1.3 Особые случаи
• 2 Свойства
• 3 Кодирование
  • 3.1 Несистематическое кодирование: сообщение как фактор
  • 3.2 Систематическое кодирование: сообщение как префикс
• 4 Декодирование
  • 4.1 Вычисление синдромов
  • 4.2 Вычисление полинома местоположения ошибки
    • 4.2.1 Алгоритм Петерсона – Горенштейна – Цирлера
  • 4.3 Фактор полинома локатора ошибок
  • 4.4 Вычисление значений ошибок
    • 4.4.1 Алгоритм Форни
    • 4.4.2 Объяснение вычисления алгоритма Форни
  • 4.5 Декодирование на основе расширенного алгоритма Евклида
    • 4.5.1 Объяснение процесса декодирования
  • 4.6 Исправление ошибок
  • 4.7 Примеры расшифровки
    • 4.7.1 Декодирование двоичного кода без нечитаемых символов
    • 4.7.2 Декодирование с нечитаемыми символами
    • 4.7.3 Декодирование с нечитаемыми символами с небольшим количеством ошибок
• 5 Цитаты
• 6 Ссылки
  • 6.1 Первичные источники
  • 6.2 Вторичные источники
• 7 Дополнительная литература

Примитивные узкосмысловые коды 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 1 (x),…, m d - 1 (x)). Можно видеть, что g (x) - многочлен с коэффициентами из GF (q) и делит x - 1. Следовательно, полиномиальный код, определяемый g (x), является циклическим кодом.

Пример

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

$mi\; (\alpha \; i)\; mod\; (x\; 4\; +\; x\; +\; 1)\; =\; 0.\; \{\backslash \; displaystyle\; m\_\; \{i\}\; \backslash \; left\; (\backslash \; alpha\; ^\; \{i\}\; \backslash \; right)\; \{\backslash \; bmod\; \{\backslash \; left\; (x\; ^\; \{4\; \}\; +\; x\; +\; 1\; \backslash \; right)\}\}\; =\; 0.\}$

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

$m\; 1\; (x)\; =\; m\; 2\; (x)\; =\; m\; 4\; (x)\; =\; m\; 8\; (х)\; =\; х\; 4\; +\; х\; +\; 1,\; м\; 3\; (х)\; =\; м\; 6\; (х)\; =\; м\; 9\; (х)\; =\; м\; 12\; (х)\; =\; х\; 4\; +\; х\; 3\; +\; х\; 2\; +\; х\; +\; 1,\; м\; 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.\; \{\; \backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; m\_\; \{1\}\; (x)\; =\; m\_\; \{2\}\; (x)\; =\; m\_\; \{4\}\; (x)\; =\; m\_\; \{8\}\; (x)\; =\; x\; ^\; \{4\}\; +\; x\; +\; 1,\; \backslash \backslash \; m\_\; \{3\}\; (x)\; =\; m\_\; \{6\}\; (x)\; =\; m\_\; \{9\}\; (x)\; =\; m\_\; \{12\}\; (x)\; =\; x\; ^\; \{4\}\; +\; x\; ^\; \{3\}\; +\; x\; ^\; \{2\}\; +\; x\; +\; 1,\; \backslash \backslash \; m\_\; \{5\}\; (x)\; =\; m\_\; \{10\}\; (x)\; =\; x\; ^\; \{2\}\; +\; x\; +\; 1,\; \backslash \backslash \; m\_\; \{7\}\; (x)\; =\; m\_\; \{\; 11\}\; (x)\; =\; m\_\; \{13\}\; (x)\; =\; m\_\; \{14\}\; (x)\; =\; x\; ^\; \{4\}\; +\; x\; ^\; \{3\}\; +1.\; \backslash \; End\; \{align\}\}\}$

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

$g\; (x)\; =\; lcm\; (m\; 1\; (x),\; m\; 2\; (x))\; =\; m\; 1\; (х)\; =\; х\; 4\; +\; x\; +\; 1.\; \{\backslash \; displaystyle\; g\; (x)\; =\; \{\backslash \; rm\; \{lcm\}\}\; (m\_\; \{1\}\; (x),\; m\_\; \{2\}\; (x))\; =\; m\_\; \{1\}\; (x)\; =\; x\; ^\; \{4\; \}\; +\; x\; +\; 1.\; \backslash ,\}$

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

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

$g\; (x)\; =\; lcm\; (m\; 1\; (x),\; м\; 2\; (х),\; м\; 3\; (х),\; м\; 4\; (х))\; =\; м\; 1\; (х)\; м\; 3\; (х)\; =\; (х\; 4\; +\; х\; +\; 1)\; (х\; 4\; +\; х\; 3\; +\; х\; 2\; +\; x\; +\; 1)\; =\; x\; 8\; +\; x\; 7\; +\; x\; 6\; +\; x\; 4\; +\; 1.\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; g\; (x)\; =\; \{\backslash \; rm\; \{lcm\}\}\; (m\_\; \{1\}\; (x),\; m\_\; \{2\}\; (x),\; m\_\; \{3\}\; (x),\; m\_\; \{4\}\; (x))\; =\; m\_\; \{1\}\; (x)\; m\_\; \{3\}\; (x)\; \backslash \backslash \; =\; \backslash \; left\; (x\; ^\; \{4\; \}\; +\; x\; +\; 1\; \backslash \; right)\; \backslash \; left\; (x\; ^\; \{4\}\; +\; x\; ^\; \{3\}\; +\; x\; ^\; \{2\}\; +\; x\; +\; 1\; \backslash \; right)\; =\; x\; ^\; \{8\}\; +\; x\; ^\; \{7\}\; +\; x\; ^\; \{6\}\; +\; x\; ^\; \{4\}\; +1.\; \backslash \; End\; \{align\}\}\}$

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

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

$g\; (x)\; =\; 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)\; =\; (\; x\; 4\; +\; x\; +\; 1)\; (x\; 4\; +\; x\; 3\; +\; x\; 2\; +\; x\; +\; 1)\; (x\; 2\; +\; x\; +\; 1)\; =\; x\; 10\; +\; x\; 8\; +\; x\; 5\; +\; x\; 4\; +\; x\; 2\; +\; x\; +\; 1.\; \{\; \backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; g\; (x)\; =\; \{\backslash \; 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)\; \backslash \backslash \; =\; \backslash \; left\; (x\; ^\; \{4\}\; +\; x\; +\; 1\; \backslash \; right)\; \backslash \; left\; (x\; ^\; \{4\}\; +\; x\; ^\; \{3\}\; +\; x\; ^\; \{2\}\; +\; x\; +\; 1\; \backslash \; right)\; \backslash \; left\; (x\; ^\; \{2\}\; +\; x\; +\; 1\; \backslash \; right)\; =\; x\; ^\; \{10\}\; +\; x\; ^\; \{8\}\; +\; x\; ^\; \{5\}\; +\; x\; ^\; \{4\}\; +\; x\; ^\; \{2\}\; +\; x\; +\; 1.\; \backslash \; end\; \{align\}\}\}$

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

Код BCH с $d\; =\; 8\; \{\backslash \; displaystyle\; d\; =\; 8\; \}$и выше имеет порождающий многочлен

$g\; (x)\; =\; lcm\; (m\; 1\; (x),\; m\; 2\; (x),...,\; m\; 14\; (x))\; =\; m\; 1\; (x)\; m\; 3\; (x)\; m\; 5\; (x)\; m\; 7\; (x)\; =\; (x\; 4\; +\; x\; +\; 1)\; (x\; 4\; +\; x\; 3\; +\; x\; 2\; +\; x\; +\; 1)\; (x\; 2\; +\; x\; +\; 1)\; (x\; 4\; +\; Икс\; 3\; +\; 1)\; =\; Икс\; 14\; +\; Икс\; 13\; +\; Икс\; 12\; +\; \cdots \; +\; Икс\; 2\; +\; Икс\; +\; 1.\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{Выровнено\}\; g\; (x)\; =\; \{\backslash \; rm\; \{lcm\}\}\; (m\_\; \{1\; \}\; (x),\; m\_\; \{2\}\; (x),...,\; m\_\; \{14\}\; (x))\; =\; m\_\; \{1\}\; (x)\; m\_\; \{3\}\; (x)\; m\_\; \{5\}\; (x)\; m\_\; \{7\; \}\; (x)\; \backslash \backslash \; =\; \backslash \; left\; (x\; ^\; \{4\}\; +\; x\; +\; 1\; \backslash \; right)\; \backslash \; left\; (x\; ^\; \{4\}\; +\; x\; ^\; \{3\}\; +\; x\; ^\; \{2\}\; +\; x\; +\; 1\; \backslash \; right)\; \backslash \; left\; (x\; ^\; \{2\}\; +\; x\; +\; 1\; \backslash \; right)\; \backslash \; left\; (x\; ^\; \{4\}\; +\; x\; ^\; \{3\}\; +1\; \backslash \; right)\; =\; x\; ^\; \{14\}\; +\; x\; ^\; \{13\}\; +\; x\; ^\; \{\; 12\}\; +\; \backslash \; cdots\; +\; x\; ^\; \{2\}\; +\; x\; +\; 1.\; \backslash \; End\; \{align\}\}\}$

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

Общие коды BCH

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$s\; (x)\; =\; p\; (x)\; g\; (x)\; =\; (x\; 20\; +\; x\; 18\; +\; x\; 17\; +\; x\; 15\; +\; х\; 14\; +\; х\; 13\; +\; х\; 11\; +\; х\; 10\; +\; х\; 9\; +\; х\; 8\; +\; х\; 6\; +\; х\; 5\; +\; х\; 4\; +\; х\; 3\; +\; х\; 2\; +\; 1)\; (х\; 10\; +\; х\; 9\; +\; х\; 8\; +\; х\; 6\; +\; х\; 5\; +\; x\; 3\; +\; 1)\; =\; 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\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; s\; (x)\; =\; p\; (x)\; g\; (x)\; \backslash \backslash \; =\; \backslash \; 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\; \backslash \; right)\; \backslash \; left\; (x\; ^\; \{10\}\; +\; x\; ^\; \{9\}\; +\; x\; ^\; \{8\}\; +\; x\; ^\; \{6\}\; +\; x\; ^\; \{5\}\; +\; x\; ^\; \{3\}\; +1\; \backslash \; right)\; \backslash \backslash \; =\; 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\; \backslash \; end\; \{выровнено\}\; \}\}$

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

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

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

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

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

$p\; (x)\; xn\; -\; k\; =\; q\; (x)\; g\; (x)\; +\; r\; (x)\; \{\backslash \; displaystyle\; p\; (x)\; x\; ^\; \{nk\}\; =\; q\; (x)\; g\; (x)\; +\; r\; (x)\}$

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

$s\; (x)\; знак\; равно\; Q\; (Икс)\; г\; (Икс)\; знак\; равно\; п\; (Икс)\; Икс\; -\; К\; -\; р\; (Икс)\; \{\backslash \; Displaystyle\; s\; (х)\; =\; д\; (х)\; г\; (х)\; =\; р\; (х)\; х\; ^\; \{nk\}\; -r\; (x)\}$

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

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

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

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

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

Вычислить синдромы

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

$sj\; =\; R\; (\alpha \; j)\; =\; C\; (\alpha \; j)\; +\; Е\; (\alpha \; j)\; \{\backslash \; Displaystyle\; s\_\; \{j\}\; =\; R\; \backslash \; left\; (\backslash \; alpha\; ^\; \{j\}\; \backslash \; right)\; =\; C\; \backslash \; left\; (\backslash \; alpha\; ^\; \{j\}\; \backslash \; right)\; +\; E\; \backslash \; left\; (\backslash \; alpha\; ^\; \{j\}\; \backslash \; right)\}$

для $j\; =\; c\; \{\backslash \; displaystyle\; j\; =\; c\}$до $c\; +\; d\; -\; 2.\; \{\backslash \; displaystyle\; c\; +\; d-2.\}$

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

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

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

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

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

$sc\; =\; e\; \alpha \; cisc\; +\; 1\; =\; e\; \alpha \; (c\; +\; 1)\; i\; =\; \alpha \; isc\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; s\_\; \{c\}\; =\; e\; \backslash ,\; \backslash \; alpha\; ^\; \{\; c\; \backslash ,\; i\}\; \backslash \backslash \; s\_\; \{c\; +\; 1\}\; =\; e\; \backslash ,\; \backslash \; alpha\; ^\; \{(c\; +\; 1)\; \backslash ,\; i\}\; =\; \backslash \; alpha\; ^\; \{i\}\; s\_\; \{c\}\; \backslash \; end\; \{align\}\}\}$

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

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

$E\; (x)\; =\; e\; 1\; xi\; 1\; +\; e\; 2\; xi\; 2\; +\; \cdots \; \{\backslash \; displaystyle\; E\; (x)\; =\; e\_\; \{1\}\; x\; ^\; \{i\_\; \{\; 1\}\}\; +\; e\_\; \{2\}\; x\; ^\; \{i\_\; \{2\}\}\; +\; \backslash \; cdots\; \backslash ,\}$

Не сразу понятно, как начать решение результирующих синдромов для неизвестных $ek\; \{\backslash \; displaystyle\; e\_\; \{k\; \}\}$и $ik.\; \{\backslash \; displaystyle\; i\_\; \{k\}.\}$

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

$\Lambda \; (Икс)\; знак\; равно\; \prod \; J\; знак\; равно\; 1\; T\; (Икс\; \alpha \; ij\; -\; 1)\; \{\backslash \; Displaystyle\; \backslash \; Lambda\; (x)\; =\; \backslash \; prod\; \_\; \{j\; =\; 1\}\; ^\; \{t\}\; \backslash \; left\; (x\; \backslash \; alpha\; ^\; \{i\_\; \{j\}\}\; -1\; \backslash \; right)\}$

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

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

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

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

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

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

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

   $S\; v\; \times \; v\; =\; [scsc\; +\; 1\; \dots \; Sc\; +\; v\; -\; 1\; sc\; +\; 1\; sc\; +\; 2\dots \; sc\; +\; v\; ⋮\; ⋮\; \ddots \; sc\; +\; v\; -\; 1\; sc\; +\; v\dots \; sc\; +\; 2\; v\; -\; 2].\; \{\backslash \; Displaystyle\; S\_\; \{v\; \backslash \; times\; v\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; s\_\; \{c\}\; s\_\; \{c\; +\; 1\}\; \backslash \; dots\; s\_\; \{c\; +\; v-1\}\; \backslash \backslash \; s\_\; \{c\; +\; 1\}\; s\_\; \{c\; +\; 2\}\; \backslash \; dots\; s\_\; \{c\; +\; v\}\; \backslash \backslash \backslash \; vdots\; \backslash \; vdots\; \backslash \; ddots\; \backslash \; vdots\; \backslash \backslash \; s\_\; \{c\; +\; v-1\}\; s\_\; \{c\; +\; v\}\; \backslash \; dots\; s\_\; \{c\; +\; 2v-2\; \}\; \backslash \; end\; \{bmatrix\}\}.\}$

2. Сгенерировать вектор $cv\; \times \; 1\; \{\backslash \; displaystyle\; c\_\; \{v\; \backslash \; times\; 1\}\}$с элементами
   $C\; v\; \times \; 1\; =\; [сбн\; +\; vsc\; +\; v\; +\; 1\; ⋮\; sc\; +\; 2\; v\; -\; 1].\; \{\backslash \; Displaystyle\; C\_\; \{v\; \backslash \; times\; 1\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; s\_\; \{c\; +\; v\}\; \backslash \backslash \; s\_\; \{c\; +\; v\; +\; 1\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \; s\_\; \{c\; +\; 2v-1\}\; \backslash \; end\; \{\; bmatrix\}\}.\}$
3. Пусть $\Lambda \; \{\backslash \; displaystyle\; \backslash \; Lambda\}$обозначает неизвестные полиномиальные коэффициенты, которые задаются как
   $\Lambda \; v\; \times \; 1\; =\; [\lambda \; v\; \lambda \; v\; -\; 1\; ⋮\; \lambda \; 1].\; \{\backslash \; displaystyle\; \backslash \; Lambda\; \_\; \{v\; \backslash \; times\; 1\}\; =\; \{\backslash \; begin\; \{bmatrix\}\; \backslash \; lambda\; \_\; \{v\}\; \backslash \backslash \backslash \; lambda\; \_\; \{v-1\}\; \backslash \backslash \backslash \; vdots\; \backslash \backslash \backslash \; lambda\; \_\; \{1\}\; \backslash \; end\; \{\; bmatrix\}\}.\}$
4. Сформируйте матричное уравнение
   $S\; v\; \times \; v\; \Lambda \; v\; \times \; 1\; =\; -\; C\; v\; \times \; 1.\; \{\backslash \; displaystyle\; S\_\; \{v\; \backslash \; times\; v\}\; \backslash \; Lambda\; \_\; \{v\; \backslash \; times\; 1\}\; =\; -\; C\_\; \{v\; \backslash \; times\; 1\; \backslash ,\}.\}$
5. Если определитель матрицы $S\; v\; \times \; v\; \{\backslash \; displaystyle\; S\_\; \{v\; \backslash \; times\; v\}\}$не равно нулю, тогда мы можем фактически найти обратную матрицу и найти значения неизвестного $\Lambda \; \{\backslash \; displaystyle\; \backslash \; Lambda\}$значений.
6. Если $det\; (S\; v\; \times \; v)\; =\; 0,\; \{\backslash \; displaystyle\; \backslash \; det\; \backslash \; left\; (S\_\; \{v\; \backslash \; times\; v\}\; \backslash \; right)\; =\; 0,\}$затем выполните

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

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

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

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

Нули Λ (x) - это α,…, α.

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

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

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

$sc\; =\; e\; 1\; \alpha \; ci\; 1\; +\; e\; 2\; \alpha \; ci\; 2\; +\; \cdots \; сбн\; +\; 1\; знак\; равно\; е\; 1\; \alpha \; (с\; +\; 1)\; я\; 1\; +\; е\; 2\; \alpha \; (с\; +\; 1)\; я\; 2\; +\; \cdots \; ⋮\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; s\_\; \{c\}\; =\; e\_\; \{1\}\; \backslash \; alpha\; ^\; \{c\; \backslash ,\; i\_\; \{1\}\}\; +\; e\_\; \{2\}\; \backslash \; alpha\; ^\; \{c\; \backslash ,\; i\_\; \{2\}\}\; +\; \backslash \; cdots\; \backslash \backslash \; s\_\; \{c\; +\; 1\}\; =\; e\_\; \{1\}\; \backslash \; alpha\; ^\; \{\; (c\; +\; 1)\; \backslash ,\; i\_\; \{1\}\}\; +\; e\_\; \{2\}\; \backslash \; alpha\; ^\; \{(c\; +\; 1)\; \backslash ,\; i\_\; \{2\}\}\; +\; \backslash \; cdots\; \backslash \backslash \; \{\}\; \backslash \; \backslash \; vdots\; \backslash \; end\; \{выровнено\}\}\; \}$

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

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

Пусть

$S\; (x)\; =\; sc\; +\; sc\; +\; 1\; x\; +\; sc\; +\; 2\; х\; 2\; +\; \cdots \; +\; сбн\; +\; г\; -\; 2\; х\; г\; -\; 2.\; \{\backslash \; Displaystyle\; S\; (x)\; =\; s\_\; \{c\}\; +\; s\_\; \{c\; +\; 1\}\; x\; +\; s\_\; \{c\; +\; 2\}\; x\; ^\; \{2\}\; +\; \backslash \; cdots\; +\; s\_\; \{c\; +\; d-2\}\; x\; ^\; \{d-2\; \}.\}$

$v\; ⩽\; d\; -\; 1,\; \lambda \; 0\; \ne \; 0\; \Lambda \; (x)\; =\; \sum \; i\; =\; 0\; v\; \lambda \; ixi\; =\; \lambda \; 0\; \prod \; k\; =\; 0\; v\; (\alpha \; -\; ikx\; -\; 1).\; \{\backslash \; displaystyle\; v\; \backslash \; leqslant\; d-1,\; \backslash \; lambda\; \_\; \{0\}\; \backslash \; neq\; 0\; \backslash \; qquad\; \backslash \; Lambda\; (x)\; =\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{v\}\; \backslash \; lambda\; \_\; \{i\}\; x\; ^\; \{i\}\; =\; \backslash \; lambda\; \_\; \{0\}\; \backslash \; prod\; \_\; \{k\; =\; 0\}\; ^\; \{v\}\; \backslash \; left\; (\backslash \; alpha\; ^\; \{-\; i\_\; \{k\}\}\; x-1\; \backslash \; right).\}$

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

$Ом\; (Икс)\; \equiv \; S\; (Икс)\; \Lambda \; (Икс)\; mod\; xd\; -\; 1\; \{\backslash \; Displaystyle\; \backslash \; Omega\; (x)\; \backslash \; Equiv\; S\; (x)\; \backslash \; Lambda\; (x)\; \{\backslash \; bmod\; \{x\; ^\; \{d-1\}\}\}\; \}$

Наконец:

$\Lambda \; \prime \; (x)\; =\; \sum \; i\; =\; 1\; vi\; \cdot \; \lambda \; ixi\; -\; 1,\; \{\backslash \; displaystyle\; \backslash \; Lambda\; \text{'}(x)\; =\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{v\}\; i\; \backslash \; cdot\; \backslash \; lambda\; \_\; \{i\}\; x\; ^\; \{i-1\},\}$

где

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

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

$ek\; =\; -\; \alpha \; ik\; \Omega \; (\alpha \; -\; ik)\; \alpha \; c\; \cdot \; ik\; \Lambda \; \prime \; (\alpha \; -\; ik).\; \{\backslash \; displaystyle\; e\_\; \{k\}\; =\; -\; \{\backslash \; alpha\; ^\; \{i\_\; \{k\}\}\; \backslash \; Omega\; \backslash \; left\; (\backslash \; alpha\; ^\; \{-\; i\_\; \{k\}\}\; \backslash \; right)\; \backslash \; over\; \backslash \; alpha\; ^\; \{c\; \backslash \; cdot\; i\_\; \{k\}\; \}\; \backslash \; Lambda\; \text{'}\backslash \; left\; (\backslash \; alpha\; ^\; \{-\; i\_\; \{k\}\}\; \backslash \; right)\}.\}$

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

$ek\; =\; -\; \Omega \; (\alpha \; -\; ik)\; \Lambda \; \prime \; (\alpha \; -\; ik).\; \{\backslash \; displaystyle\; e\_\; \{k\}\; =\; -\; \{\backslash \; Omega\; \backslash \; left\; (\backslash \; alpha\; ^\; \{-\; i\_\; \{k\}\}\; \backslash \; right)\; \backslash \; over\; \backslash \; Lambda\; \text{'}\backslash \; left\; (\backslash \; alpha\; ^\; \{-\; i\_\; \{k\}\}\; \backslash \; right)\}.\}$

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

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

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

$S\; (x)\; \Lambda \; (x)\; =\; \sum \; j\; =\; 0\; \infty \; i\; =\; 0\; jsj\; -\; i\; +\; 1.\; \{\backslash \; Displaystyle\; S\; (x)\; \backslash \; Lambda\; (x)\; =\; \backslash \; sum\; \_\; \{j\; =\; 0\}\; ^\; \{\backslash \; infty\}\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{j\}\; s\_\; \{j-i\; +\; 1\}\; \backslash \; lambda\; \_\; \{\; i\}\; x\; ^\; \{j\}.\}$

$S (x) Λ (x) = S (x) {λ 0 ∏ ℓ = 1 v (α i ℓ x - 1)} = {∑ i = 0 d - 2 ∑ j = 1 vej α (c + i) ⋅ ijxi} {λ 0 ∏ ℓ = 1 v (α i ℓ x - 1)} = {∑ j = 1 vej α cij ∑ i = 0 d - 2 (α ij) ixi} {λ 0 ∏ ℓ = 1 v (α i ℓ x - 1)} = {∑ j = 1 vej α cij (x α ij) d - 1 - 1 x α ij - 1} {λ 0 ∏ ℓ = 1 v (α i ℓ x - 1)} = λ 0 ∑ j = 1 vej α cij (x α ij) d - 1 - 1 x α ij - 1 ∏ ℓ = 1 v (α i ℓ x - 1) = λ 0 ∑ j = 1 vej α cij ( ( x α ij) d − 1 − 1) ∏ ℓ ∈ { 1, ⋯, v } ∖ { j } ( α i ℓ x − 1) {\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(\a lpha ^{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}}}$

We want to compute unknowns $e\; j,\; \{\backslash displaystyle\; e\_\{j\},\}$and we could simplify the context by removing the $(\; x\; \alpha \; i\; j)\; d\; -\; 1\; \{\backslash displaystyle\; \backslash left(x\backslash alpha\; ^\{i\_\{j\}\}\backslash right)^\{d-1\}\}$terms. This leads to the error evaluator polynomial

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

Thanks to $v\; ⩽\; d\; -\; 1\; \{\backslash displaystyle\; v\backslash leqslant\; d-1\}$we have

$\Omega \; (\; x)\; =\; -\; \lambda \; 0\; \sum \; j\; =\; 1\; v\; e\; j\; \alpha \; c\; i\; j\; \prod \; \ell \; \in \; \{\; 1,\; \cdots ,\; v\; \}\; \setminus \; \{\; j\; \}\; (\; \alpha \; i\; \ell \; x\; -\; 1).\; \{\backslash displaystyle\; \backslash Omega\; (x)=-\backslash lambda\; \_\{0\}\backslash sum\; \_\{j=1\}^\{v\}e\_\{j\}\backslash alpha\; ^\{ci\_\{j\}\}\backslash prod\; \_\{\backslash ell\; \backslash in\; \backslash \{1,\backslash cdots,v\backslash \}\backslash setminus\; \backslash \{j\backslash \}\}\backslash left(\backslash alpha\; ^\{i\_\{\backslash ell\; \}\}x-1\backslash right).\}$

Thanks to $\Lambda \; \{\backslash displaystyle\; \backslash Lambda\; \}$(the Lagrange interpolation trick) the sum degenerates to only one summand for $x\; =\; \alpha \; -\; i\; k\; \{\backslash displaystyle\; x=\backslash alpha\; ^\{-i\_\{k\}\}\}$

$\Omega \; (\; \alpha \; -\; i\; k)\; =\; -\; \lambda \; 0\; e\; k\; \alpha \; c\; \cdot \; i\; k\; \prod \; \ell \; \in \; \{\; 1,\; \cdots ,\; v\; \}\; \setminus \; \{\; k\; \}\; (\; \alpha \; i\; \ell \; \alpha \; -\; i\; k\; -\; 1).\; \{\backslash displaystyle\; \backslash Omega\; \backslash left(\backslash alpha\; ^\{-i\_\{k\}\}\backslash right)=-\backslash lambda\; \_\{0\}e\_\{k\}\backslash alpha\; ^\{c\backslash cdot\; i\_\{k\}\}\backslash prod\; \_\{\backslash ell\; \backslash in\; \backslash \{1,\backslash cdots,v\backslash \}\backslash setminus\; \backslash \{k\backslash \}\}\backslash left(\backslash alpha\; ^\{i\_\{\backslash ell\; \}\}\backslash alpha\; ^\{-i\_\{k\}\}-1\backslash right).\}$

To get $e\; k\; \{\backslash displaystyle\; e\_\{k\}\}$we just should get rid of the product. We could compute the product directly from already computed roots $\alpha \; -\; i\; j\; \{\backslash displaystyle\; \backslash alpha\; ^\{-i\_\{j\}\}\}$of $\Lambda ,\; \{\backslash displaystyle\; \backslash Lambda,\}$but we could use simpler form.

As formal derivative

$\Lambda \; \prime \; (\; x)\; =\; \lambda \; 0\; \sum \; j\; =\; 1\; v\; \alpha \; i\; j\; \prod \; \ell \; \in \; \{\; 1,\; \cdots ,\; v\; \}\; \setminus \; \{\; j\; \}\; (\; \alpha \; i\; \ell \; x\; -\; 1),\; \{\backslash displaystyle\; \backslash Lambda\; \text{'}(x)=\backslash lambda\; \_\{0\}\backslash sum\; \_\{j=1\}^\{v\}\backslash alpha\; ^\{i\_\{j\}\}\backslash prod\; \_\{\backslash ell\; \backslash in\; \backslash \{1,\backslash cdots,v\backslash \}\backslash setminus\; \backslash \{j\backslash \}\}\backslash left(\backslash alpha\; ^\{i\_\{\backslash ell\; \}\}x-1\backslash right),\}$

we get again only one summand in

$\Lambda \; \prime \; (\; \alpha \; -\; i\; k)\; =\; \lambda \; 0\; \alpha \; i\; k\; \prod \; \ell \; \in \; \{\; 1,\; \cdots ,\; v\; \}\; \setminus \; \{\; k\; \}\; (\; \alpha \; i\; \ell \; \alpha \; -\; i\; k\; -\; 1).\; \{\backslash displaystyle\; \backslash Lambda\; \text{'}\backslash left(\backslash alpha\; ^\{-i\_\{k\}\}\backslash right)=\backslash lambda\; \_\{0\}\backslash alpha\; ^\{i\_\{k\}\}\backslash prod\; \_\{\backslash ell\; \backslash in\; \backslash \{1,\backslash cdots,v\backslash \}\backslash setminus\; \backslash \{k\backslash \}\}\backslash left(\backslash alpha\; ^\{i\_\{\backslash ell\; \}\}\backslash alpha\; ^\{-i\_\{k\}\}-1\backslash right).\}$

So finally

$e\; k\; =\; -\; \alpha \; i\; k\; \Omega \; (\; \alpha \; -\; i\; k)\; \alpha \; c\; \cdot \; i\; k\; \Lambda \; \prime \; (\; \alpha \; -\; i\; k).\; \{\backslash displaystyle\; e\_\{k\}=-\{\backslash frac\; \{\backslash alpha\; ^\{i\_\{k\}\}\backslash Omega\; \backslash left(\backslash alpha\; ^\{-i\_\{k\}\}\backslash right)\}\{\backslash alpha\; ^\{c\backslash cdot\; i\_\{k\}\}\backslash Lambda\; \text{'}\backslash left(\backslash alpha\; ^\{-i\_\{k\}\}\backslash right)\}\}.\}$

This formula is advantageous when one computes the formal derivative of $\Lambda \; \{\backslash displaystyle\; \backslash Lambda\; \}$form

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

yielding:

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

where

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

Decoding based on extended Euclidean algorithm

An alternate process of finding both the polynomial Λ and the error locator polynomial is based on Yasuo Sugiyama's adaptation of the Extended Euclidean algorithm. Correction of unreadable characters could be incorporated to the algorithm easily as well.

Let $k\; 1,...,\; k\; k\; \{\backslash displaystyle\; k\_\{1\},...,k\_\{k\}\}$be positions of unreadable characters. One creates polynomial localising these positions $\Gamma \; (\; x)\; =\; \prod \; i\; =\; 1\; k\; (\; x\; \alpha \; k\; i\; -\; 1).\; \{\backslash displaystyle\; \backslash Gamma\; (x)=\backslash prod\; \_\{i=1\}^\{k\}\backslash left(x\backslash alpha\; ^\{k\_\{i\}\}-1\backslash right).\}$Set values on unreadable positions to 0 and compute the syndromes.

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

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

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

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

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

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

$s\; i\; =\; \sum \; j\; =\; 0\; n\; -\; 1\; e\; j\; \alpha \; i\; j.\; \{\backslash \; displaystyle\; s\_\; \{i\}\; =\; \backslash \; sum\; \_\; \{j\; =\; 0\}\; ^\; \{n-1\}\; e\_\; \{j\}\; \backslash \; alpha\; ^\; \{ij\}.\}$

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

$S\; (x)\; знак\; равно\; \sum \; я\; знак\; равно\; 0\; d\; -\; 2\; сбн\; +\; ixi\; \{\backslash \; displaystyle\; S\; (x)\; =\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{d-2\}\; s\_\; \{c\; +\; i\}\; x\; ^\; \{i\}\}$

и сравните коэффициенты около степеней $0\; \{\backslash \; displaystyle\; 0\}$с $d\; -\; 2.\; \{\backslash \; Displaystyle\; d-2.\}$

$S\; (x)\; =\; \{0,\; \cdots ,\; d\; -\; 2\}\; E\; (x)\; =\; \sum \; i\; =\; 0\; d\; -\; 2\; \sum \; j\; =\; 0\; n\; -\; 1\; ej\; \alpha \; ij\; \alpha \; cjxi.\; \{\backslash \; Displaystyle\; S\; (Икс)\; \{\backslash \; stackrel\; \{\backslash \; \{0,\; \backslash \; cdots,\; \backslash ,\; d-2\; \backslash \}\}\; \{=\}\}\; E\; (x)\; =\; \backslash \; sum\; \_\; \{i\; =\; 0\}\; ^\; \{d-2\}\; \backslash \; sum\; \_\; \{j\; =\; 0\}\; ^\; \{n-1\}\; e\_\; \{j\}\; \backslash \; alpha\; ^\; \{ij\}\; \backslash \; alpha\; ^\; \{cj\}\; x\; ^\; \{i\}.\}$

Предположим, на позиции $k\; есть\; нечитаемая\; буква\; 1,\; \{\backslash \; displaystyle\; k\_\; \{1\},\}$мы могли бы заменить набор синдромов $\{sc,\; \cdots ,\; sc\; +\; d\; -\; 2\}\; \{\backslash \; displaystyle\; \backslash \; \{s\_\; \{c\},\; \backslash \; cdots,\; s\_\; \{c\; +\; d-2\}\; \backslash \}\}$по набору синдромов $\{tc,\; \cdots ,\; tc\; +\; d\; -\; 3\}\; \{\backslash \; displaystyle\; \backslash \; \{t\_\; \{c\},\; \backslash \; cdots,\; t\_\; \{\; c\; +\; d-3\}\; \backslash \}\}$определяется уравнением $ti\; =\; \alpha \; k\; 1\; si\; -\; si\; +\; 1.\; \{\backslash \; displaystyle\; t\_\; \{i\}\; =\; \backslash \; alpha\; ^\; \{k\_\; \{1\}\}\; s\_\; \{i\}\; -s\_\; \{i\; +\; 1\}.\}$Предположим для слова ошибки все ограничения из исходного набора $\{\; sc,\; \cdots ,\; sc\; +\; d\; -\; 2\}\; \{\backslash \; displaystyle\; \backslash \; \{s\_\; \{c\},\; \backslash \; cdots,\; s\_\; \{c\; +\; d-2\}\; \backslash \}\}$удерживает синдромов, чем

$ti\; =\; \alpha \; k\; 1\; si\; -\; si\; +\; 1\; =\; \alpha \; k\; 1\; \sum \; j\; =\; 0\; n\; -\; 1\; ej\; \alpha \; ij\; -\; \sum \; j\; =\; 0\; n\; -\; 1\; ej\; \alpha \; j\; \alpha \; ij\; =\; \sum \; j\; =\; 0\; n\; -\; 1\; ej\; (\alpha \; k\; 1\; -\; \alpha \; j)\; \alpha \; ij.\; \{\backslash \; displaystyle\; t\_\; \{i\}\; =\; \backslash \; alpha\; ^\; \{k\_\; \{1\}\}\; s\_\; \{i\}\; -s\_\; \{i\; +\; 1\}\; =\; \backslash \; alpha\; ^\; \{k\_\; \{1\}\}\; \backslash \; sum\; \_\; \{j\; =\; 0\}\; ^\; \{n-\; 1\}\; e\_\; \{j\}\; \backslash \; alpha\; ^\; \{ij\}\; -\; \backslash \; sum\; \_\; \{j\; =\; 0\}\; ^\; \{n-1\}\; e\_\; \{j\}\; \backslash \; alpha\; ^\; \{j\}\; \backslash \; alpha\; ^\; \{ij\}\; =\; \backslash \; sum\; \_\; \{j\; =\; 0\}\; ^\; \{n-1\}\; e\_\; \{j\}\; \backslash \; left\; (\backslash \; alpha\; ^\; \{k\_\; \{1\}\}\; -\; \backslash \; alpha\; ^\; \{j\}\; \backslash \; right)\; \backslash \; alpha\; ^\; \{ij\}.\}$

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

$fj\; =\; ej\; (\alpha \; k\; 1\; -\; \alpha \; j)\; \{\backslash \; displaystyle\; f\_\; \{j\}\; =\; e\_\; \{j\}\; \backslash \; left\; (\backslash \; alpha\; ^\; \{k\_\; \{1\}\}\; -\; \backslash \; alpha\; ^\; \{j\}\; \backslash \; right)\; \}$

точно так же, как исходный набор синдромов ограничивал вектор ошибок $ej.\; \{\backslash \; displaystyle\; e\_\; \{j\}.\}$За исключением координаты $k\; 1,\; \{\backslash \; displaystyle\; k\_\; \{1\},\}$, где $fk\; 1\; =\; 0,\; \{\backslash \; displaystyle\; f\_\; \{k\_\; \{1\}\}\; =\; 0,\}$an $fj\; \{\backslash \; displaystyle\; f\_\; \{j\}\}$равно нулю, если $ej\; =\; 0.\; \{\backslash \; displaystyle\; e\_\; \{j\}\; =\; 0.\}$Для определения местоположения ошибок мы могли бы изменить набор синдромов аналогичным образом, чтобы отразить все нечитаемые символы. Это сокращает набор синдромов на $k.\; \{\backslash \; displaystyle\; k.\}$

В полиномиальной формулировке замена синдромов задает $\{sc,\; \cdots ,\; sc\; +\; d\; -\; 2\}\; \{\backslash \; displaystyle\; \backslash \; \{s\_\; \{c\},\; \backslash \; cdots,\; s\_\; \{c\; +\; d\; -2\}\; \backslash \}\}$по набору синдромов $\{tc,\; \cdots ,\; tc\; +\; d\; -\; 3\}\; \{\backslash \; displaystyle\; \backslash \; \{t\_\; \{c\},\; \backslash \; cdots,\; t\_\; \{c\; +\; d-3\}\; \backslash \}\}$приводит к

$T\; (x)\; =\; \sum \; i\; =\; 0\; d\; -\; 3\; tc\; +\; ixi\; =\; \alpha \; k\; 1\; \sum \; i\; =\; 0\; d\; -\; 3\; sc\; +\; ixi\; -\; \sum \; i\; =\; 1\; d\; -\; 2\; сбн\; +\; ixi\; -\; 1.\; \{\backslash \; Displaystyle\; Т\; (х)\; =\; \backslash \; сумма\; \_\; \{я\; =\; 0\}\; ^\; \{d-3\}\; t\_\; \{с\; +\; я\}\; х\; ^\; \{я\}\; =\; \backslash \; альфа\; ^\; \{к\_\; \{1\}\}\; \backslash \; сумма\; \_\; \{я\; =\; 0\; \}\; ^\; \{d-3\}\; s\_\; \{c\; +\; i\}\; x\; ^\; \{i\}\; -\; \backslash \; sum\; \_\; \{i\; =\; 1\}\; ^\; \{d-2\}\; s\_\; \{c\; +\; i\}\; x\; ^\; \{i-1\}.\}$

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

$x\; T\; (x)\; =\; \{1,\; \cdots ,\; d\; -\; 2\}\; (x\; \alpha \; k\; 1\; -\; 1)\; S\; (x).\; \{\backslash \; displaystyle\; xT\; (x)\; \{\backslash \; stackrel\; \{\backslash \; \{1,\; \backslash \; cdots,\; \backslash ,\; d-2\; \backslash \}\}\; \{=\}\}\; \backslash \; left\; (x\; \backslash \; alpha\; ^\; \{k\_\; \{1\}\}\; -\; 1\; \backslash \; right)\; S\; (\; x).\}$

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

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

$S\; (x)\; \Gamma \; (x)\; \Lambda \; (x)\; знак\; равно\; \{к\; +\; v,\; \cdots ,\; d\; -\; 2\}\; 0.\; \{\backslash \; displaystyle\; S\; (x)\; \backslash \; Gamma\; (x)\; \backslash \; Lambda\; (x)\; \{\backslash \; stackrel\; \{\backslash \; \{k\; +\; v,\; \backslash \; cdots,\; d-2\; \backslash \}\}\; \{=\}\}\; 0.\}$

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

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

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

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

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

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

Примеры декодирования

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

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

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

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

$[S\; 3\; \times \; 3\; |\; C\; 3\; \times \; 1]\; =\; [с\; 1\; с\; 2\; с\; 3\; с\; 4\; с\; 2\; с\; 3\; с\; 4\; с\; 5\; с\; 3\; с\; 4\; с\; 5\; с\; 6]\; =\; [1011\; 1001\; 1011\; 1101\; 1001\; 1011\; 1101\; 0001\; 1011\; 1101\; 0001\; 1001]\; \Rightarrow \; [0001\; 0000\; 1000\; 0111\; 0000\; 0001\; 1011\; 0001\; 0000\; 0000\; 0000\; 0000]\; \{\backslash \; displaystyle\; \backslash \; left\; [S\_\; \{3\; \backslash \; times\; 3\}\; |\; C\_\; \{3\; \backslash \; times\; 1\}\; \backslash \; right]\; =\; \{\backslash \; begin\; \{bmatrix\}\; s\_\; \{1\}\; s\_\; \{2\; \}\; s\_\; \{3\}\; s\_\; \{4\}\; \backslash \backslash \; s\_\; \{2\}\; s\_\; \{3\}\; s\_\; \{4\}\; s\_\; \{5\}\; \backslash \backslash \; s\_\; \{3\}\; s\_\; \{4\}\; s\_\; \{5\}\; s\_\; \{6\}\; \backslash \; end\; \{bmatrix\}\; \}\; =\; \{\backslash \; begin\; \{bmatrix\}\; 1011\; 1001\; 1011\; 1101\; \backslash \backslash \; 1001\; 1011\; 1101\; 0001\; \backslash \backslash \; 1011\; 1101\; 0001\; 1001\; \backslash \; end\; \{bmatrix\}\}\; \backslash \; Rightarrow\; \{\backslash \; begin\; \{bmatrix\}\; 0001\; 0000\; 1000\; 0111\; \backslash \backslash \; 0000\; 0001\; 0001\; 0001\; 0001\; 0001\; 0001\; 0001\; 0001\; 0001\; \backslash \backslash \; 000075\}\; к\; концу\; b\; строка,\; S\; 3\; \times \; 3\; является\; сингулярной,\; что\; неудивительно,\; поскольку\; только\; две\; ошибки\; были\; введены\; в\; кодовое\; слово.\; Однако\; верхний\; левый\; угол\; матрицы\; идентичен\; [S\; 2\; \times \; 2\; |\; C\; 2\; \times \; 1\; ],\; что\; дает\; решение$ \lambda \; 2\; =\; 1000,\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{2\}\; =\; 1000,\}$$$\lambda \; 1\; =\; 1011.\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{1\}\; =\; 1011.\}$Результирующий полином локатора ошибок равен $\Lambda \; (x)\; =\; 1000\; x\; 2\; +\; 1011\; x\; +\; 0001,\; \{\backslash \; displaystyle\; \backslash \; Lambda\; (x)\; =\; 1000x\; ^\; \{2\}\; +\; 1011x\; +\; 0001,\}$, у которого есть нули в $0100\; =\; \alpha \; -\; 13\; \{\backslash \; displaystyle\; 0100\; =\; \backslash \; alpha\; ^\; \{-\; 13\}\}$и $0111\; =\; \alpha \; -\; 5.\; \{\backslash \; displaystyle\; 0111\; =\; \backslash \; alpha\; ^\; \{-\; 5\}.\}$Показатели степени $\alpha \; \{\backslash \; displaystyle\; \backslash \; alpha\}$соответствуют местоположениям ошибок. В этом примере нет необходимости вычислять значения ошибок, поскольку единственное возможное значение - 1.

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

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

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

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

вычислить

$S\; (x)\; \Gamma \; (Икс)\; знак\; равно\; \alpha \; -\; 7\; +\; \alpha \; 4\; Икс\; +\; \alpha \; -\; 1\; Икс\; 2\; +\; \alpha \; 6\; Икс\; 3\; +\; \alpha \; -\; 1\; Икс\; 4\; +\; \alpha \; 5\; Икс\; 5\; +\; \alpha \; 7\; Икс\; 6\; +\; \alpha \; -\; 3\; Икс\; 7.\; \{\backslash \; Displaystyle\; S\; (x)\; \backslash \; Gamma\; (x)\; =\; \backslash \; alpha\; ^\; \{-\; 7\}\; +\; \backslash \; alpha\; ^\; \{4\}\; x\; +\; \backslash \; alpha\; ^\; \{-\; 1\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{6\}\; x\; ^\; \{\; 3\}\; +\; \backslash \; alpha\; ^\; \{-\; 1\}\; x\; ^\; \{4\}\; +\; \backslash \; alpha\; ^\; \{5\}\; x\; ^\; \{5\}\; +\; \backslash \; alpha\; ^\; \{7\}\; x\; ^\; \{6\}\; +\; \backslash \; alpha\; ^\; \{-\; 3\}\; x\; ^\; \{\; 7\}.\}$

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

$(S (x) Γ (x) x 6) = (α - 7 + α 4 x + α - 1 x 2 + α 6 x 3 + α - 1 x 4 + α 5 x 5 + α 7 x 6 + α - 3 x 7 x 6) = (α 7 + α - 3 x 1 1 0) (x 6 α - 7 + α 4 x + α - 1 x 2 + α 6 x 3 + α - 1 x 4 + α 5 x 5 + 2 α 7 x 6 + 2 α - 3 x 7) = (α 7 + α - 3 x 1 1 0) (α 4 + α - 5 x 1 1 0) (α - 7 + α 4 x + α - 1 x 2 + α 6 x 3 + α - 1 x 4 + α 5 x 5 α - 3 + (α - 7 + α 3) x + (α 3 + α - 1) x 2 + (α - 5 + α - 6) x 3 + (α 3 + α 1) x 4 + 2 α - 6 x 5 + 2 x 6) = ((1 + α - 4) + (α 1 + α 2) x + α 7 x 2 α 7 + α - 3 x α 4 + α - 5 x 1) (α - 7 + α 4 x + α - 1 x 2 + α 6 x 3 + α - 1 x 4 + α 5 x 5 α - 3 + α - 2 x + α 0 x 2 + α - 2 x 3 + α - 6 x 4) = (α - 3 + α 5 x + α 7 x 2 α 7 + α - 3 x α 4 + α - 5 x 1) (α - 5 + α - 4 x 1 1 0) (α - 3 + α - 2 x + α 0 x 2 + α - 2 х 3 + α - 6 х 4 (α 7 + α - 7) + (2 α - 7 + α 4) x + (α - 5 + α - 6 + α - 1) x 2 + (α - 7 + α - 4 + α 6) x 3 + ( α 4 + α - 6 + α - 1) x 4 + 2 α 5 x 5) = (α 7 x + α 5 x 2 + α 3 x 3 α - 3 + α 5 x + α 7 x 2 α 3 + α - 5 x + α 6 x 2 α 4 + α - 5 x) (α - 3 + α - 2 x + α 0 x 2 + α - 2 x 3 + α - 6 x 4 α - 4 + α 4 x + α 2 x 2 + α - 5 x 3). {\ Displaystyle {\ begin {align} {\ 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} \ конец {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 + \ альфа ^ {- 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 (\ альфа ^ {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} \ вправо) 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} \\\ альфа ^ {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 {align}}}$

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

$(-\; (\alpha \; 4\; +\; \alpha \; -\; 5\; x)\; \alpha \; -\; 3\; +\; \alpha \; 5\; x\; +\; \alpha \; 7\; x\; 2\; \alpha \; 3\; +\; \alpha \; -\; 5\; x\; +\; \alpha \; 6\; x\; 2\; -\; (\alpha \; 7\; x\; +\; \alpha \; 5\; x\; 2\; +\; \alpha \; 3\; x\; 3))\; (\alpha \; 7\; x\; +\; \alpha \; 5\; x\; 2\; +\; \alpha \; 3\; x\; 3\; \alpha \; -\; 3\; +\; \alpha \; 5).\; Икс\; +\; \alpha \; 7\; Икс\; 2\; \alpha \; 3\; +\; \alpha \; -\; 5\; Икс\; +\; \alpha \; 6\; Икс\; 2\; \alpha \; 4\; +\; \alpha \; -\; 5\; Икс)\; =\; (1\; 0\; 0\; 1),\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{pmatrix\}\; -\; \backslash \; left\; (\backslash \; alpha\; ^\; \{4\}\; +\; \backslash \; alpha\; ^\; \{-\; 5\}\; x\; \backslash \; right)\; \backslash \; alpha\; ^\; \{-\; 3\}\; +\; \backslash \; alpha\; ^\; \{5\}\; x\; +\; \backslash \; alpha\; ^\; \{7\}\; x\; ^\; \{2\}\; \backslash \backslash \backslash \; alpha\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{-\; 5\}\; x\; +\; \backslash \; alpha\; ^\; \{6\}\; x\; ^\; \{2\}\; -\; \backslash \; left\; (\backslash \; alpha\; ^\; \{7\}\; x\; +\; \backslash \; alpha\; ^\; \{5\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{3\}\; x\; ^\; \{3\}\; \backslash \; right)\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; \backslash \; alpha\; ^\; \{7\}\; x\; +\; \backslash \; alpha\; ^\; \{5\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{3\}\; x\; ^\; \{3\}\; \backslash \; alpha\; ^\; \{-\; 3\}\; +\; \backslash \; alpha\; ^\; \{5\}\; x\; +\; \backslash \; alpha\; ^\; \{7\}\; x\; ^\; \{2\}\; \backslash \backslash \backslash \; alpha\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{-\; 5\}\; x\; +\; \backslash \; alpha\; ^\; \{6\}\; х\; ^\; \{2\}\; \backslash \; а\; lpha\; ^\; \{4\}\; +\; \backslash \; alpha\; ^\; \{-\; 5\}\; x\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; 1\; 0\; \backslash \backslash \; 0\; 1\; \backslash \; end\; \{pmatrix\}\},\}$

получаем

$(-\; (\; \alpha \; 4\; +\; \alpha \; -\; 5\; x)\; \alpha \; -\; 3\; +\; \alpha \; 5\; x\; +\; \alpha \; 7\; x\; 2\; \alpha \; 3\; +\; \alpha \; -\; 5\; x\; +\; \alpha \; 6\; x\; 2\; -\; (\alpha \; 7\; x\; +\; \alpha \; 5\; x\; 2\; +\; \alpha \; 3\; x\; 3))\; (\; S\; (x)\; \Gamma \; (x)\; x\; 6)\; =\; (\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\; х\; 3).\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{pmatrix\}\; -\; \backslash \; left\; (\backslash \; alpha\; ^\; \{4\}\; +\; \backslash \; alpha\; ^\; \{-\; 5\}\; x\; \backslash \; right)\; \backslash \; alpha\; ^\; \{-\; 3\}\; +\; \backslash \; alpha\; ^\; \{5\}\; x\; +\; \backslash \; alpha\; ^\; \{7\}\; x\; ^\; \{2\}\; \backslash \backslash \backslash \; alpha\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{-\; 5\}\; x\; +\; \backslash \; alpha\; ^\; \{6\}\; x\; ^\; \{2\}\; -\; \backslash \; left\; (\backslash \; alpha\; ^\; \{7\}\; x\; +\; \backslash \; alpha\; ^\; \{5\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{3\}\; x\; ^\; \{3\}\; \backslash \; right)\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; S\; (x)\; \backslash \; Gamma\; (x)\; \backslash \backslash \; x\; ^\; \{\; 6\}\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; \backslash \; alpha\; ^\; \{-\; 3\}\; +\; \backslash \; alpha\; ^\; \{-\; 2\}\; x\; +\; \backslash \; alpha\; ^\; \{0\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{-\; 2\}\; x\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{-\; 6\}\; x\; ^\; \{4\}\; \backslash \backslash \backslash \; alpha\; ^\; \{-\; 4\}\; +\; \backslash \; alpha\; ^\; \{4\}\; x\; +\; \backslash \; alpha\; ^\; \{2\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{-5\}\; x\; ^\; \{3\}\; \backslash \; end\; \{pmatrix\}\}.\}$

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

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

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

Пусть

$\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 \; (Икс)\; \equiv \; \alpha \; -\; 4\; +\; \alpha \; 4\; Икс\; +\; \alpha \; 2\; Икс\; 2\; +\; \alpha \; -\; 5\; Икс\; 3\; по\; модулю\; Икс\; 6\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; Xi\; (x)\; =\; \backslash \; Gamma\; (x)\; \backslash \; Lambda\; (x)\; =\; \backslash \; alpha\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{4\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{2\}\; x\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{-\; 5\}\; x\; ^\; \{4\}\; \backslash \backslash \backslash \; Омега\; (x)\; =\; S\; (x)\; \backslash \; Xi\; (x)\; \backslash \; Equiv\; \backslash \; alpha\; ^\; \{-\; 4\}\; +\; \backslash \; alpha\; ^\; \{4\}\; x\; +\; \backslash \; alpha\; ^\; \{2\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{-\; 5\; \}\; x\; ^\; \{3\}\; \{\backslash \; bmod\; \{x\; ^\; \{6\}\}\}\; \backslash \; end\; \{align\}\}\}$

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

$ej\; =\; -\; \Omega \; (\alpha \; -\; ij)\; \Xi \; \prime \; (\; \alpha \; -\; ij),\; \{\backslash \; displaystyle\; e\_\; \{j\}\; =\; -\; \{\backslash \; frac\; \{\backslash \; Omega\; \backslash \; left\; (\backslash \; alpha\; ^\; \{-\; i\_\; \{j\}\}\; \backslash \; right)\}\; \{\backslash \; Xi\; \text{'}\backslash \; left\; (\backslash \; alpha\; ^\; \{-\; i\_\; \{j\}\}\; \backslash \; right)\}\},\}$

где $\alpha \; -\; ij\; \{\backslash \; displaystyle\; \backslash \; alpha\; ^\; \{-\; i\_\; \{j\}\}\}$- корни $\Xi \; (x).\; \{\backslash \; Displaystyle\; \backslash \; Xi\; (x).\}$$\Xi \; \prime \; (x)\; =\; \alpha \; 2\; x\; 2.\; \{\backslash \; displaystyle\; \backslash \; Xi\; \text{'}(x)\; =\; \backslash \; alpha\; ^\; \{2\}\; x\; ^\; \{2\}.\}$Мы получаем

$e 1 = - Ω (α 4) Ξ ′ (α 4) = α - 4 + α - 7 + α - 5 + α 7 α - 5 = α - 5 α - 5 = 1 e 2 = - Ω (α 7) Ξ ′ (α 7) = α - 4 + α - 4 + α 1 + α 1 α 1 = 0 e 3 = - Ω (α 10) Ξ ′ (α 10) = α - 4 + α - 1 + α 7 + α - 5 α 7 = α 7 α 7 = 1 e 4 Знак равно - Ω (α 2) Ξ ′ (α 2) = α - 4 + α 6 + α 6 + α 1 α 6 = α 6 α 6 = 1 {\ Displaystyle {\ begin {align} 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} + \ альфа ^ {6} + \ alpha ^ {1}} {\ alpha ^ {6}}} = {\ frac {\ alpha ^ {6}} {\ alpha ^ {6}}} = 1 \ end {align}}}$

Факт, что $e\; 3\; =\; e\; 4\; =\; 1,\; \{\backslash \; 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].

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

$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\; х\; 6\; +\; \alpha \; 6\; х\; 7.\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; S\; (x)\; =\; \backslash \; alpha\; ^\; \{4\}\; +\; \backslash \; alpha\; ^\; \{-\; 7\}\; x\; +\; \backslash \; alpha\; ^\; \{1\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{1\}\; x\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{0\}\; x\; ^\; \{4\}\; +\; \backslash \; alpha\; ^\; \{2\}\; x\; ^\; \{5\},\; \backslash \backslash \; S\; (x)\; \backslash \; Gamma\; (x)\; =\; \backslash \; alpha\; ^\; \{4\}\; +\; \backslash \; alpha\; ^\; \{7\}\; x\; +\; \backslash \; alpha\; ^\; \{5\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{3\}\; x\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{1\}\; x\; ^\; \{4\}\; +\; \backslash \; alpha\; ^\; \{-\; 1\}\; x\; ^\; \{5\}\; +\; \backslash \; alpha\; ^\; \{-\; 1\}\; x\; ^\; \{6\}\; +\; \backslash \; alpha\; ^\; \{6\}\; x\; ^\; \{7\}.\; \backslash \; End\; \{align\}\}\}$

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

$(S (x) Γ (x) x 6) = (α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α - 1 x 5 + α - 1 x 6 + α 6 x 7 x 6) = (α - 1 + α 6 x 1 1 0) (x 6 α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α - 1 x 5 + 2 α - 1 x 6 + 2 α 6 x 7) = (α - 1 + α 6 x 1 1 0) (α 3 + α 1 x 1 1 0) (α 4 + α 7 x + α 5 x 2 + α 3 x 3 + α 1 x 4 + α - 1 x 5 α 7 + (α - 5 + α 5) x + 2 α - 7 x 2 + 2 α 6 x 3 + 2 α 4 x 4 + 2 α 2 x 5 + 2 x 6) = ((1 + α 2) + (α 0 + α - 6) x + α 7 x 2 α - 1 + α 6 x α 3 + α 1 x 1) (α 4 + α 7 Икс + α 5 Икс 2 + α 3 Икс 3 + α 1 Икс 4 + α - 1 Икс 5 α 7 + α 0 Икс) {\ Displaystyle {\ begin {align} {\ begin {pmatrix} S (x) \ Gamma (x) \\ x ^ {6} \ end {pmatrix}} = {\ begin {p матрица} \ 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} \\\ альфа ^ {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} + \ альфа ^ {3} x ^ {3} + \ alpha ^ {1} x ^ {4} + \ alpha ^ {- 1} x ^ {5} \\\ alpha ^ {7} + \ alpha ^ {0} x \ end {pmatrix}} \ end {align}}}$

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

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

получаем

$(-\; 1\; \alpha \; -\; 1\; +\; \alpha \; 6\; x\; \alpha \; 3\; +\; \alpha \; 1\; x\; -\; (\alpha \; -\; 7\; +\; \alpha \; 7\; x\; +\; \alpha \; 7\; x\; 2))\; (S\; (x)\; \Gamma \; (x)\; x\; 6)\; =\; (\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).\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{pmatrix\}\; -1\; \backslash \; alpha\; ^\; \{-\; 1\}\; +\; \backslash \; alpha\; ^\; \{6\}\; x\; \backslash \backslash \backslash \; alpha\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{1\}\; x\; -\; \backslash \; left\; (\backslash \; alpha\; ^\; \{\; -7\}\; +\; \backslash \; alpha\; ^\; \{7\}\; x\; +\; \backslash \; alpha\; ^\; \{7\}\; x\; ^\; \{2\}\; \backslash \; right)\; \backslash \; end\; \{pmatrix\}\}\; \{\backslash \; begin\; \{pmatrix\}\; S\; (x)\; \backslash \; Gamma\; (x)\; \backslash \backslash \; x\; ^\; \{6\}\; \backslash \; end\; \{pmatrix\}\}\; =\; \{\backslash \; begin\; \{pmatrix\}\; \backslash \; alpha\; ^\; \{4\}\; +\; \backslash \; alpha\; ^\; \{7\}\; x\; +\; \backslash \; alpha\; ^\; \{5\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{3\}\; x\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{1\}\; x\; ^\; \{4\}\; +\; \backslash \; alpha\; ^\; \{-\; 1\}\; x\; ^\; \{5\}\; \backslash \backslash \backslash \; alpha\; ^\; \{7\}\; +\; \backslash \; alpha\; ^\; \{0\}\; x\; \backslash \; end\; \{pmatrix\}\}.\}$

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

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

Пусть $\Lambda \; (x)\; =\; \alpha \; 3\; +\; \alpha \; 1\; х.\; \{\backslash \; displaystyle\; \backslash \; Lambda\; (x)\; =\; \backslash \; alpha\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{1\}\; x.\}$Не беспокойтесь, что $\lambda \; 0\; \ne \; 1.\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{0\}\; \backslash \; neq\; 1.\}$Корень $\Lambda \; (x)\; \{\backslash \; displaystyle\; \backslash \; Lambda\; (x)\}$равен $\alpha \; 3\; -\; 1.\; \{\backslash \; displaystyle\; \backslash \; alpha\; ^\; \{3-1\}.\}$

Пусть

$\Xi \; (x)\; =\; \Gamma \; (x)\; \Lambda \; (x)\; =\; \alpha \; 3\; +\; \alpha \; -\; 7\; x\; +\; \alpha \; -\; 4\; x\; 2\; +\; \alpha \; 5\; Икс\; 3,\; Ом\; (Икс)\; знак\; равно\; S\; (Икс)\; \Xi \; (Икс)\; \equiv \; \alpha \; 7\; +\; \alpha \; 0\; Икс\; модуль\; Икс\; 6\; \{\backslash \; Displaystyle\; \{\backslash \; begin\; \{align\}\; \backslash \; Xi\; (x)\; =\; \backslash \; Gamma\; (x)\; \backslash \; Lambda\; (\; x)\; =\; \backslash \; alpha\; ^\; \{3\}\; +\; \backslash \; alpha\; ^\; \{-\; 7\}\; x\; +\; \backslash \; alpha\; ^\; \{-\; 4\}\; x\; ^\; \{2\}\; +\; \backslash \; alpha\; ^\; \{5\}\; x\; ^\; \{3\},\; \backslash \backslash \backslash \; Omega\; (x)\; =\; S\; (x)\; \backslash \; Xi\; (x)\; \backslash \; Equiv\; \backslash \; alpha\; ^\; \{7\}\; +\; \backslash \; alpha\; ^\; \{0\}\; x\; \{\backslash \; bmod\; \{x\; ^\; \{6\}\}\}\; \backslash \; end\; \{align\}\}\}$

Позвольте нам найдите значения ошибок с помощью формулы $ej\; =\; -\; \Omega \; (\alpha \; -\; ij)\; /\; \Xi \; \prime \; (\alpha \; -\; ij),\; \{\backslash \; displaystyle\; e\_\; \{j\}\; =\; -\; \backslash \; Omega\; \backslash \; left\; (\backslash \; alpha\; ^\; \{-\; i\_\; \{j\})\; \}\; \backslash \; right)\; /\; \backslash \; Xi\; \text{'}\backslash \; left\; (\backslash \; alpha\; ^\; \{-\; i\_\; \{j\}\}\; \backslash \; right),\}$где $\alpha \; -\; ij\; \{\backslash \; displaystyle\; \backslash \; alpha\; ^\; \{-\; i\_\; \{j\; \}\}\}$являются корнями многочлена $\Xi \; (x).\; \{\backslash \; Displaystyle\; \backslash \; Xi\; (x).\}$

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

Мы получаем

$e\; 1\; =\; -\; \Omega \; (\alpha \; 4)\; \Xi \; \prime \; (\alpha \; 4)\; =\; \alpha \; 7\; +\; \alpha \; 4\; \alpha \; -\; 7\; +\; \alpha \; -\; 2\; =\; \alpha \; 3\; \alpha \; 3\; =\; 1\; e\; 2\; =\; -\; \Omega \; (\alpha \; 7)\; \Xi \; \prime \; (\alpha \; 7)\; =\; \alpha \; 7\; +\; \alpha \; 7\; \alpha \; -\; 7\; +\; \alpha \; 4\; знак\; равно\; 0\; е\; 3\; знак\; равно\; -\; \Omega \; (\alpha \; 2)\; \Xi \; \prime \; (\alpha \; 2)\; =\; \alpha \; 7\; +\; \alpha \; 2\; \alpha \; -\; 7\; +\; \alpha \; -\; 6\; =\; \alpha \; -\; 3\; \alpha \; -\; 3\; =\; 1\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; e\_\; \{1\}\; =\; -\; \{\backslash \; frac\; \{\backslash \; Omega\; \backslash \; left\; (\backslash \; alpha\; ^\; \{4\}\; \backslash \; right)\}\; \{\backslash \; Xi\; \text{'}\backslash \; left\; (\backslash \; alpha\; ^\; \{4\}\; \backslash \; right)\}\}\; =\; \{\backslash \; frac\; \{\backslash \; alpha\; ^\; \{7\}\; +\; \backslash \; alpha\; ^\; \{4\}\}\; \{\backslash \; alpha\; ^\; \{-\; 7\}\; +\; \backslash \; alpha\; ^\; \{-\; 2\}\}\}\; =\; \{\backslash \; frac\; \{\backslash \; alpha\; ^\; \{3\}\}\; \{\backslash \; alpha\; ^\; \{3\}\}\; \}\; =\; 1\; \backslash \backslash \; e\_\; \{2\}\; =\; -\; \{\backslash \; frac\; \{\backslash \; Omega\; \backslash \; left\; (\backslash \; alpha\; ^\; \{7\}\; \backslash \; right)\}\; \{\backslash \; Xi\; \text{'}\backslash \; left\; (\backslash \; alpha\; ^\; \{7\}\; \backslash \; right)\}\}\; =\; \{\backslash \; frac\; \{\backslash \; alpha\; ^\; \{7\}\; +\; \backslash \; alpha\; ^\; \{7\}\}\; \{\backslash \; alpha\; ^\; \{-\; 7\}\; +\; \backslash \; alpha\; ^\; \{4\}\}\}\; =\; 0\; \backslash \backslash \; e\_\; \{3\}\; =\; -\; \{\backslash \; frac\; \{\; \backslash \; Omega\; \backslash \; left\; (\backslash \; alpha\; ^\; \{2\}\; \backslash \; right)\}\; \{\backslash \; Xi\; \text{'}\backslash \; left\; (\backslash \; alpha\; ^\; \{2\}\; \backslash \; right)\}\}\; =\; \{\backslash \; frac\; \{\backslash \; alpha\; ^\; \{7\}\; +\; \backslash \; alpha\; ^\; \{2\; \}\}\; \{\backslash \; alpha\; ^\; \{-\; 7\}\; +\; \backslash \; alpha\; ^\; \{-\; 6\}\}\}\; =\; \{\backslash \; frac\; \{\backslash \; alpha\; ^\; \{-\; 3\}\}\; \{\backslash \; alpha\; ^\; \{-\; 3\}\}\}\; =\; 1\; \backslash \; end\; \{выровнено\}\; \}\}$

Тот факт, что $e\; 3\; =\; 1\; \{\backslash \; displaystyle\; e\_\; \{3\}\; =\; 1\}$, не должен вызывать удивления.

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

Цитаты

Ссылки

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

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

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

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

Далее чтение

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