БЧХ код

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

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

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

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

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

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

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

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

Пример

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

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

Минимальные многочлены:

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

Код БЧХ имеет порождающий полином ${\displaystyle d=2,3}$

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

Он имеет минимальное расстояние Хэмминга не менее 3 и исправляет до одной ошибки. Поскольку полином генератора имеет степень 4, этот код имеет 11 бит данных и 4 бита контрольной суммы. Он также обозначается как: (15, 11) код БЧХ.

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

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

Он имеет минимальное расстояние Хэмминга не менее 5 и исправляет до двух ошибок. Поскольку полином генератора имеет степень 8, этот код имеет 7 бит данных и 8 бит контрольной суммы. Он также обозначается как: (15, 7) код БЧХ.

Код БЧХ имеет порождающий полином ${\displaystyle d=6,7}$

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

Он имеет минимальное расстояние Хэмминга не менее 7 и исправляет до трех ошибок. Поскольку полином генератора имеет степень 10, этот код имеет 5 бит данных и 10 бит контрольной суммы. Он также обозначается как: (15, 5) код BCH. (Этот конкретный полином генератора имеет реальное применение в «информации о формате» QR-кода .)

Код БЧХ с и выше имеет порождающий полином ${\displaystyle d=8}$

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

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

Общие коды BCH

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

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

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

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

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

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

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

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

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

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

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

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

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

Кодирование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Расшифровка

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

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

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

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

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

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

для того, чтобы ${\displaystyle j=c}$ ${\displaystyle c+d-2.}$

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

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

Рассчитайте полином местоположения ошибки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   ${\displaystyle S_{v\times v}={\begin{bmatrix}s_{c}&s_{c+1}&\dots &s_{c+v-1}\\s_{c+1}&s_{c+2}&\dots &s_{c+v}\\\vdots &\vdots &\ddots &\vdots \\s_{c+v-1}&s_{c+v}&\dots &s_{c+2v-2}\end{bmatrix}}.}$

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

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

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

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

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

Нули Λ( x ) — это α ^{− i ₁} , …, α ^{− i _v} .

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

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

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

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

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

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

Позволять

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

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

И полином оценки ошибки ^[9]

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

Окончательно:

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

где

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

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

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

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

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

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

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

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

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

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

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

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

Спасибо, что у нас есть ${\displaystyle v\leqslant d-1}$

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

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

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

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

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

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

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

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

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

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

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

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

выход:

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поэтому,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Давайте сделаем синдром полиномиальным

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

вычислить

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

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

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

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

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

мы получаем

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

Поэтому,

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

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

Позволять

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

мы получаем

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

Поэтому,

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

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

Позволять

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

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

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

Мы получаем

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

Это не должно вызывать удивления. ${\displaystyle e_{3}=1}$

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

Цитаты

1. Рид и Чен 1999, стр. 189
2. Хоквенгем 1959
3. Бозе и Рэй-Чоудхури 1960
4. "Phobos Lander Coding System: Software and Analysis" (PDF) . Архивировано (PDF) из оригинала 2022-10-09 . Получено 25 февраля 2012 .
5. Марелли, Алессия; Микелони, Рино (2018). «Коды BCH для твердотельных накопителей». Внутри твердотельных накопителей (SSDS) . Springer Series in Advanced Microelectronics. Том 37. С. 369–406. doi :10.1007/978-981-13-0599-3_11. ISBN 978-981-13-0598-6. Получено 23 сентября 2023 г. .
6. Gill nd, стр. 3
7. Lidl & Pilz 1999, стр. 229
8. Горенштейн, Петерсон и Цирлер, 1960 г.
9. Гилл nd, стр. 47
10. Ясуо Сугияма, Масао Касахара, Сигейчи Хирасава и Тошихико Намекава. Метод решения ключевого уравнения для декодирования кодов Гоппы. Информация и контроль, 27:87–99, 1975.

Ссылки

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

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

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

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

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

• Блахут, Ричард Э. (2003), Алгебраические коды для передачи данных (2-е изд.), Cambridge University Press , ISBN 0-521-55374-1
• Гилберт, У. Дж.; Николсон, У. К. (2004), Современная алгебра с приложениями (2-е изд.), Джон Уайли
• Лин, С.; Костелло, Д. (2004), Кодирование с контролем ошибок: основы и применение , Энглвуд Клиффс, Нью-Джерси: Prentice-Hall
• MacWilliams, FJ; Sloane, NJA (1977), Теория кодов, исправляющих ошибки , Нью-Йорк, штат Нью-Йорк: North-Holland Publishing Company
• Рудра, Атри, CSE 545, Коды исправления ошибок: комбинаторика, алгоритмы и приложения, Университет в Буффало, архивировано с оригинала 2012-12-18