6.7. ДЕКОДЕР МЕГГИТТА ДЛЯ. КОДА ГОЛЕЯ
В тех случаях, когда данный код не позволяет непосредственно использовать декодер с вылавливанием ошибок, иногда удается так добавить несколько дополнительных цепей, чтобы аннулировать влияние некоторых мешающих применению декодера конфигураций ошибок. В общем случае для получения удовлетворительного решения требуется некоторая изобретательность. Мы опишем такой декодер для 
-кода Голея.
Длина вектора ошибок равна 23, а вес не превосходит 3. Длина синдромного регистра равна 11. Если данная конфигурация ошибок не вылавливается, то она не может быть циклически сдвинута так, чтобы все три ошибки появились в 11 младших разрядах. Можно убедиться (возможно, после нескольких прикидок), что в этом случае по одну сторону от одной из трех ошибочных позиций стоит по меньшей мере пять, а по другую сторону — по меньшей мере шесть нулей. Следовательно, каждая исправляемая конфигурация ошибок может быть с помощью циклических сдвигов приведена к одному из трех следующих видов (позиции нумеруются числами от 0 до 22):
1) все ошибки (не более трех) расположены в II старших разрядах;
2) одна ошибка занимает пятую позицию, а остальные расположены в 11 старших разрядах;
3) одна ошибка занимает шестую позицию, а остальные расположены в 11 старших разрядах.
Таким образом, в декодере надо заранее вычислить величины 
Тогда ошибка вылавливается, если вес 
не превышает 3 или если вес 
либо 
не превышает 2. В декодере можно либо исправлять все три ошибки, если эти условия выполнены, либо исправлять только две ошибки в младших 11 битах, дожидаясь удаления из регистра третьего ошибочного бита.
Разделив 
на порождающий многочлен
имеем
Следовательно, если ошибка содержится в пятой или шестой позициях, то синдром соответственно равен 
или 
. Наличие двух дополнительных ошибок в II старших разрядах приводит к тому, что в соответствующих позициях два из этих битов заменяются на противоположные.
Декодер отслеживает синдром, отличающийся от нулевого синдрома не более чем в трех позициях, а также синдром, отличающийся от выписанных двух синдромов не более чем в двух позициях.
ЗАДАЧИ
(см. скан)
(см. скан)
ЗАМЕЧАНИЯ
Многие идеи данной главы уже ясно просматриваются как идеи теории дискретных фильтров, но с заменой поля вещественных или комплексных чисел на поле Гвлуа. Это смутно ощущвлось еще в самом начале и становилось все более очевидным по мере развития предмета. Содержащие регистры сдвига устройства были сразу использованы большинством исследователей и ьошли в литературу без всяких фанфар. Использовавме регистров сдвига в кодерах и декодерах можно найти в работах Питерсона [1960] и Ченя [1964]. В виде учебного материала эти идеи появились уже в нииге Питерсона [1961]. Меггитт опубликоввл описание устройств своих декодеров в 1960 и 1961 гг. Не совсем ясно, кому принадлежит идея декодера с вылавливанием ошибок, но обычно ее приписывают Прейцджу.
Способы модификации декодера с вылавливанием ошибок, позволяющие корректировать исправляемые, но не вылавливаемые ошибки, рассматривал Касами [1964]. На методах Касами основан описанный в § 6.7 декодер для кода Голея. Использование отличных от циклических перестановок исследовала Мак-Вильямс [1964]. Другие ранние результаты приводятся в статьях Митчелла [1962] и Рудолфа и Митчелла [1964].
