Двоичные БЧХ–коды

 

Кратких сведений по структуре и свойствам конечных полей достаточно для ознакомления с одним из основных достижений теории кодирования. БЧХ[1]–коды дают один из немногих примеров возможности построения кодов с заранее предсказуемыми корректирующими свойствами. В настоящем параграфе рассматриваются примитивные БЧХ–коды, представляющие собой только подкласс (хотя и наиболее важный) обширного семейства БЧХ–кодов. Указанные коды характеризуются длиной и строятся на основе расширенного поля . Обобщение теории БЧХ–кодов на случай –ичного алфавита осуществляется достаточно легко, однако они не находят адекватного применения на практике. Основная идея построения БЧХ–кодов определяется следующей теоремой.

Теорема 8.5.1. (БЧХ теорема). Пусть порождающий полином имеет в расширенном поле корни , где – примитивный элемент поля . Тогда циклический код с порождающим полиномом обладает минимальным расстоянием , не меньшим .

Доказательство данной теоремы основывается на свойстве определителя специфической матрицы, формулируемом следующей леммой.

Лемма 8.5.1. Квадратичная матрица вида (матрица Вандермонда)

имеет отличный от нуля определитель, если и только если все элементы различны.

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

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

Далее вычтем из каждой –й строки –ю, умноженную на , а затем вынесем из каждого –го столбца общий множитель вида , в результате чего получим

.

Тогда, с учетом индукции по , имеем

,

откуда непосредственно следует, что если при всех .

Доказательство: В рамках доказательства теоремы о БЧХ–кодов предположим, что существует кодовое слово, вес которого меньше . Делимость соответствующего этому слову полинома на порождающий влечет за собой, что корнями полинома являются , т.е.

,

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

,

где матрица – корневая проверочная матрица.

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

,

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

На основании теоремы 8.5.1 опишем общий алгоритм построения БЧХ–кодов. Для значения , обеспечивающего необходимую длину кода , из таблиц выбирается примитивный полином степени и строится расширенное поле , как это было сделано в примерах 8.2.5–8.2.6. Затем в построенном поле выбирается последовательность степеней примитивного элемента .

Если выбран в качестве корня порождающего полинома , то, согласно теореме 8.4.1, корнями будут и все сопряженные с по степени два элементы , которые вместе с тем являются и корнями соответствующего минимального многочлена, так что имеет в качестве сомножителя полином вида

,

где – длина 2–сопряженной последовательности (цикла) с элементом , которая вследствие примитивности равна . Следующим элементом, претендующим на роль корня , является , который уже учтен в сомножителе , поскольку сопряжен с по степени 2.

Если , то следующим корнем порождающего полинома будет , а также все 2–сопряженные с ним элементы , которые являются корнями минимального для полинома

,

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

Гарантией того, что построенный по описанному алгоритму многочлен действительно порождает циклический код, служит тот факт, что он делит бином , где (см. теорему 7.2.2). Действительно, полином представляет собой произведение некоторых биномов вида с различными ненулевыми элементами , тогда как, согласно теореме 8.4.3, многочлен есть произведение подобных биномов со всеми ненулевыми элементами поля.

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

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

Пример 8.5.1. Построим порождающий полином БЧХ–кода длины , исправляющий любую однократную ошибку. Расширенное поле , необходимое для нахождения , построено в примере 8.2.5. Требование исправления кодом любых однократных ошибок влечет за собой, что , а значит, корнями порождающего многочлена должны быть элементы и .

Минимальный многочлен, отвечающий элементу , имеет вид

,

где

, ,

,

поэтому . Элемент , являющийся корнем , уже учтен в , так что .

Поскольку , то число информационных символов , содержащихся в каждом слове, будет , и значит, результатом построения является циклическая версия (7,4) кода Хэмминга, исправляющего любую однократную ошибку.

Если изменить условия примера, потребовав, например, построить циклический код, исправляющий ошибки кратности до 2–х включительно ( и ), то в число обязательных корней порождающего полинома войдут . Поскольку элементы входят в один и тот же цикл 2–сопряженных корней и являются корнями одного и того же минимального полинома , то остается найти только минимальный полином для и сопряженных с ним и . Тогда , а , так что итогом будет тривиальный (7,1) код с повторением, передающий в каждом слове только один информационный символ.

В настоящее время разработчику телекоммуникационной системы нет необходимости осуществлять весь объем работы по отысканию БЧХ–кода, поскольку подобные исследования уже выполнены много лет назад, результатом чего явились детальные таблицы, содержащие готовые к использованию порождающие полиномы БЧХ–кодов. Вместе с тем любой, кто занимается канальным кодированием, должен уметь быстро определять параметры БЧХ–кодов. Так, например, может быть получена слабая нижняя граница числа информационных символов в каждом слове БЧХ–кода, если учесть, что каждая четная степень примитивного элемента входит в состав последовательности 2–сопряженных с элементом меньшей степени и, следовательно, уже охватывается некоторым минимальным полиномом. Тогда общее число последовательностей из сопряженных по степени 2 элементов, которые должны входить в число корней минимальных полиномов, не больше, чем , а поскольку длина любой последовательности не превосходит , то БЧХ–код характеризуется следующими параметрами

.

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

Пример 8.5.2. Сколько информационных символов содержит БЧХ–код, исправляющий любую однократную ошибку? Для того чтобы ответить на данный вопрос отметим, что , а значит, элементы и являются корнями порождающего полинома . Однако, поскольку они принадлежат одному и тому же циклу сопряженных элементов , длины , то , причем . Следовательно, , т.е. любой БЧХ–код, исправляющий однократные ошибки, есть просто циклическая версия кода Хэмминга.

Пример 8.5.3. Определить точное число информационных символов в БЧХ–коде длины , исправляющем любую ошибку кратности до 5. Для данного кода корнями порождающего полинома служат элементы . Последовательность из 2–сопряженных с элементов содержит , поскольку , охватывая, как это видно, четыре обязательных корня порождающего полинома . Цикл из 2-сопряженных с элементом включает , тем самым, охватывая корни , доводя их общее число до 6. Для в цикл из 2–сопряженных элементов входят

,

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

.

Таким образом, порождающий полином является произведением 4–х минимальных многочленов, степень каждого из которых равна 5, так что , откуда . В заключении отметим, что фактическое значение числа информационных символов значительно больше предсказываемого нижней границей: .