Коды БЧХ. 
Дискретный анализ. 
Основы высшей алгебры

В этом разделе будем рассматривать коды, имеющие длину п = 2^к — 1. Описываемый ниже способ способ построения «хорошего» кода, исправляющего «мною» ошибок, придуман Боузом, Чоудхури и Хоквингемом. Поэтому коды, которые мы получим, называются БЧХ-кодами.

Рассмотрим такое уточнение описанной выше схемы. Возьмем какой-нибудь неприводимый многочлен и построим по нему иоле. Ненулевые элементы поля, как было показано выше, образуют циклическую группу по умножению. Выберем порождающий элемент этой группы а и рассмотрим степени а, а², …, а^2г, где г — число ошибок, которые нужно уметь исправлять. И теперь в разложении соответствующею многочлена х^п — 1 выберем такие неприводимые множители, чтобы каждая из указанных степеней была корнем одного из них. Оказывается, что эго гарантирует исправление г ошибок.

Пример 4.10. Возьмем ж¹⁵ — 1. Предположим, что нужен код, исправляющий три ошибки. Значит, нужно найти многочлены, корнями которых являются первые шесть степеней порождающего элемента а. Если многочлен имеет корень а, то по теореме 3.41 можно указать все его корни: а, а², а⁴, а⁸.

Аналогично, если у многочлена есть корень от, то у него будут корни cv, с*⁶, а¹², с*⁹. Наконец, если у многочлена есть корень.

ii 10.

а у то у него также есть корень, а .

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

Теперь проведем эти рассуждения в более общем виде. Начнем с простой части — построения кода, а затем уже будем доказывать, что он действительно исправляет ошибки.

Итак, полагаем п = 2^к — 1. Из разложения на множители многочлена х^п — 1.

выберем те сомножители, корни которых содержат степени.

Перемножая выбранные сомножители, получаем искомый многочлен ip у порождающий идеал, который и даст нам хороший код. Какова степень Если какой-то многочлен имеет корень а, значит, он также имеет корень а². И вообще, если многочлен имеет корень а³, то он имеет также и корень a^2s. Таким образом, нам потребуется не более г штук многочленов, потому что каждый из выбираемых многочленов имеет по крайней мере два корня. А степень неприводимого делителя х^п — 1 не больше к (напомним, что было выбрано п = 2^к — 1). Поэтому общая степень произведения всех выбранных многочленов нс больше г&, где к = log₂(n + 1), тк — rlog₂(n +1).

Итак, идеал, порожденный </?, будет иметь размерность п минус степень порождающего полинома, значит точек в этом идеале будет не меньше, чем.

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

Докажем, что расстояние между точками кода не меньше, чем 2r+ 1. Заметим, что все многочлены, входящие в наш код, кратны ip. Поэтому каждый кодовый многочлен имеет корни а, а², …, ог^г. Значит, нам достаточно доказать следующее утверждение.

Лемма 4.11. Если ip (a^s) = 0 при 1 ^ s ^ 2 г, то у ф не менее 2г + 1 ненулевого коэффициента.

Доказательство. Рассмотрим многочлен ф (х) = ао + аХ + Н——-— a_n-ixⁿ~^l, удовлетворяющий этому условию. Его коэф фициенты дают решение следующей системы линейных уравнений:

Если набор а = (ао,…, a_n-i) ^— решение этой системы, то, как негрудно видеть, между ||а|| столбцами матрицы системы (4.3) есть линейная зависимость. Поэтому для доказательства леммы 4.11 достаточно показать, что любые 2г столбцов этой матрицы линейно независимы.

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

Давайте выберем из матрицы системы (4.3) столбцы Д, Д, • • •, j2r • Получим квадратную матрицу.

Вынесем из всех элементов столбца t общий множитель a^Jt. Получим, что определитель нашей матрицы с точностью до ненулевого множителя a^J1+j2+'" ^{+ равен}

^(4.4)

^{Это хорошо известный определитель Вандермонда. Вычисляется он над конечным полем точно так же, как и над привычным R:}

^{В нашем случае определитель отличен от нуля: напомним, что мы взяли в качестве а порождающий элемент мультипликативной группы поля, поэтому все степени а вплоть до}

• ^?
• ^{(гг — 1)-й различны.}

^{Итак, мы доказали лемму 4.11. Значит, построенный нами код действительно исправляет г ошибок (расстояние между кодовыми словами не меньше 2 г + 1).}