7.6. ДЕКОДИРОВАНИЕ ДВОИЧНЫХ КОДОВ БЧХ

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

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

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

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

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

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

Теорема 7.6.1. Пусть в расширении поля задана произвольная последовательность удовлетворяющая условию для пусть также задан регистр сдвига с линейной обратной связью и выполняются равенства

Если следующий член последовательности задается равенством

то

Доказательство. Покажем, что при сделанных предположениях выражения для совпадают. С одной стороны,

С другой стороны,

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

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

Таким образом, по индукции получаем, что равно нулю для четных поэтому можно рассматривать только нечетные итерации, формально объединяя две последовательные итерации:

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