10.6. Примеры

Сначала мы продолжим рассмотрение примера 7.68, в котором исследовался двоичный БЧХ-код с исправлением 3 ошибок и кодовой длиной 31. когда по те задается миогочтенами от а степени где Степенные симметрические функции от локаторов ошибок имели вид ысно алюригму 7.4, находим, что Тогда

Используя формулу

получим, что

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

Если предположить, что произошло не более четырех ошибок, то общее решение примет вид (Залетим, что для двоичного кода имеет четную, нечетную степень и если или то должен иметь степень Согласно уравнению 10.57,

Для рассматриваемого примера это дает

или

Решения этого квадратного уравнения имеют вид или

Если

Если

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

Следовательно, многочлен должен иметь в четыре различных корня. С помощью процедуры Ченя находим, что

Второй возможный многочлен локаторов ошибок также имеет четыре корня в :

Итак, оказалось, что любая попытка исправить 4 ошибки с помощью двоичного БЧХ-кода с исправлением 3 ошибок и блоковой длиной 31 приводит к двузначности результата, так как каждый смежный класс, имеющий вес 4, содержит 2 лидера. Это свойство является следствием того, что рассматриваемый код получается выбрасыванием одного символа из кода Рида — Маллера. Коды такого типа изучаются в разд. 15.3.

В качестве второго примера рассмотрим двоичный БЧХ-код с блоковой длиной 31 и исправлением 5 ошибок. Предположим, что Так как

Согласно алгоритму 7.64,

С помощью обычных вычислений находим, что

Здесь

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

Если произошло не более шести ошибок, то, согласно уравнению (10.57),

Полагая получим квадратное уравнение относительно

Как будет показано в разд. 11.1, это уравнение имеет в два решения: либо либо

Если то и Так как в этом случае то мы должны отвергнуть гипотезу

Полагая получим, что Процедура Ченя показывает, что этот многочлен допустим и имеет место разложение

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

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

Исправление даже одной дополнительной ошибки требует решения алгебраического уравнения в некотором расширении конечного поля. В большинстве случаев использование процедуры Ченя для отыскания корней, лежащих в подполе, приводит к существенному увеличению необходимого общего времени декодирования. К счастью, процедуры Ченя можно избежать. Существуют лучшие методы решения алгебраических уравнений малой степени над расширениями конечных полей. Эти методы будут исследоваться в главе 11.

Задача

(см. скан)