образом. Одним из возможных подходов является построение гистограммы. Например, для уравнения (2) при каждом значении Ai построим гистограмму величины (А,*"" - Л1а~ЬР)~ х X а~Я,. Любая составляющая гистограммы, принимающая значение -Ь 1, соответствует возможной конфигурации из f + 1 ошибок.

Декодер можно модифицировать далее так, чтобы он исправлял t + V ошибок. Хотя уравнения при этом удлиняются, такой подход представляется практически вполне возможным для t + 3 и f + 4 в зависимости от длины кода.

Теперь рассмотрим двоичные коды. Они отличаются от кодов Рида-Соломона тем, что для них декодер может быть упрощен в силу теоремы 7.6.1, но одновременно усложняется за счет того, что многие из находимых конфигураций ошибок веса v не являются двоичными и поэтому должны быть отброшены.

Предположим, что у нас имеется двоичный код БЧХ с конструктивным расстоянием 2+1, и мы хотим исправлять все однозначно декодируемые конфигурации веса t-\- \. Единственными величинами, которые может измерять декодер, являются 2t компонент синдрома S, Szt- Во всех остальных частотах стоят либо произвольные значения, либо значения, определяемые условиями сопряженности. Итеративный алгоритм в двоичном случае дает

Л+) (X) = Л (х) - At+ixB (х). Во временной области он переписывается в виде

и предполагается, что конфигурация ошибок веса t или менее не была найдена алгоритмом.

Построим гистограмму величины akf/bc* по всем ненулевым элементам поля GF (q). Каждая равная +1 компонента этой гистограммы соответствует кандидату на роль конфигурации ошибок. Зная локаторы ошибок, вычислим эту конфигурацию. Если она двоична и единственна, то декодирование завершено успешно.

Рассмотрим далее двоичный код, у которого проверочные частоты не являются последовательными. Например, проверочными частотами двоичного циклического (63, 28, 15)-кода являются Cl, Cg, Cg, С,, Cg, Qi и €.21. Как можно проверить на ЭВМ, минимальное расстояние кода равно 15. По сравнению с (63, 24, 15)-кодом БЧХ этот код обладает тем преимуществом, что обеспечивает большую скорость, но зато для кода БЧХ известен алгоритм декодирования. Однако ценой незначительного-усложнения частотный декодер для кода БЧХ удается преобра-

зовать в декодер для (63, 28, 15)-кода. Используя описанную выше процедуру, можно найти все конфигурации ошибок веса не более 7, которые согласуются с 12 последовательными прове-рочными частотами, а затем вычислить S21 для каждой из них. Только одна из них будет соответствовать измеренному значению Sgi-

9.7. ДЕКОДИРОВАНИЕ АЛЬТЕРНАНТНЫХ КОДОВ

Альтернантные коды являются ограничением на подполе простейшей модификации кодов Рида-Соломона. Минимальное расстояние d* альернантного кода не меньше конструктивного расстояния d исходного кода Рида-Соломона. Любая процедура декодирования кода Рида-Соломона может быть использована для декодирования альтернантных кодов. Необходимо лишь модифицировать синдром либо с помощью обратного преобразования шаблона, либо путем умножения на него во временной области, либо путем вычисления свертки в частотной области; никаких других изменений не требуется.

Таким образом, для декодирования альтернантных кодов в пределах конструктивного расстояния можно применять любой временной или частотный декодер для кодов БЧХ. Привлекательность альтернантных кодов, однако, состоит в том, что их минимальное расстояние много больше их конструктивного расстояния. В то же время использование альтернантных кодов с БЧХ-де-кодером дает мало преимуществ по сравнению с использованием кодов БЧХ с БЧХ-декодером. Конечно, есть резон в том, чтобы использовать альтернантные коды с БЧХ-декодером при исправлении ошибок в пределах конструктивного расстояния и обнаружении ошибок вплоть до минимального расстояния. Можно также применить описанные в § 9.6 методы декодирования за конструктивным расстоянием, хотя и в ограниченных пределах.

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

Профильтрованный спектр принятого слова дается равенством

/г-1 /е=0

Для кода Гоппы спектр в свою очередь вычисляется из Т по формуле

п-1 7t

А;=0 fc=0

9.7. ДЕКОДИРОВАНИЕ АЛЬТЕРНАНТНЫХ КОДОВ 315

где степень многочлена Гоппы G (х) равна 2t и G (х) Н (х) = = 1 (mod х"- - 1). Поскольку

£ Нщ и))Сн = 0. i = n- 2.+ 1, ..., rt,

/е=0

ТО компоненты синдрома даются равенствами

/е=0

По этим компонентам синдрома вычислим многочлен локаторов ошибок и продолжим его рекуррентно для получения всех компонент Sj, j = I, п. Спектр вектора ошибок находится из равенств

Ej = 5] GfeS((/ fe „+20) / = 0> • • •> « - 1-

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

За исключением шага, связанного с шаблоном, декодирование альтернантных кодов происходит точно так же, как декодирование кодов Рида-Соломона. Так же, как и коды Рида-Соломона, альтернантные коды можно декодировать за пределами конструктивного расстояния. В пределах минимального расстояния кодовое слово единственно. Декодер для кода Рида-Соломона, применяемый для декодирования альтернантных кодов, может указать и другие слова, но они будут содержать компоненты, не принадлежащие полю символов кода, и такие слова должны быть отброшены.

При декодировании кодов Гоппы в узком смысле такого отбрасывания ложных кодовых слов можно заранее избежать, если добавлять только компоненты синдрома, согласующиеся с ограничениями сопряженности гу = Ej- Две дополнительные ком-