Начальные значения:

АШ = В(х) = 1

.,2f

Вычисление слеВующего выхоВа послейнего фильтра » Дг=.Ё AjS-j

Вычисление нового многочлена связей, йля которого = О

Пх)*М.х)-[\гхВ{х)

Нх) - Т(х)

L ~r-L Л(х)- Т(х)

;=0,..:,л-1

В(рс) ~хВ(х)

Cmon-исправление закончено

Рис. 9.8. Декодер для альтернантного кода.

поненты синдрома St+i и S2t+2, необходимые для исправления t -Ь 1 ошибок, неизвестны. Но

Е; = 1 GkSj-k~n+2t)),

следовательно

2i 2t

Ei=GoS2i+\ + 2j GkS2t+l-k)), E2 = GoS2t+2-\- Ii GftS((2;+2-fe)),

k=l k=l

И так как £2 = i, то

S2t+2 = Go

-21 2t -

Таким образом, в качестве неизвестного надо ввести только S2t+\-В общем случае неизвестными являются компоненты с нечетными индексами, а компоненты синдрома с четными индексами вычисляются. Необходима только половина новых компонент синдрома, а конфигурация ошибок всегда двоична. Если результирующий многочлен локаторов ошибок допустим, то декодирование закончено. К сожалению, для декодирования s ошибок за пределами конструктивного расстояния необходимо просмотреть q" возможностей для неизвестных компонент синдрома.

9.8. ВЫЧИСЛЕНИЕ ПРЕОБРАЗОВАНИЙ В КОНЕЧНЫХ ПОЛЯХ

Рассмотрим преобразование Фурье

где а - элемент порядка п в поле GF (q"). Для малых значений п его можно вычислять в том виде, в каком оно записано, но так как вычисление содержит г? умножений, то оно становится практически неприемлемым при больших длинах. Необходимы эффективные методы вычисления преобразования Фурье, и мы располагаем некоторыми такими методами. Одним из наиболее мощных методов, пригодных для многих значений длин, является переход от одномерного преобразования к многомерному преобразованию Фурье. Все такие методы известны под общим названием быстрого преобразования Фурье. Изучение этих методов мы отложим до гл. 11; в этом же параграфе мы рассмотрим другие методы вычисления преобразования Фурье, а именно chirp-алгоритм Блюстейна, алгоритм Рейдера для простых значений длин преобразования и алгоритм Герцеля.

Представленные на рис. 9.9 алгоритмы Блюстейна и Рейдера являются различными способами перехода от преобразования Фурье к свертке; первый из них переводит п-точечное преобразование Фурье в п-точечную свертку, а второй (который приме няется в случае, когда п - простое число) переводит п-точечное преобразование Фурье в (п - 1)-точечную свертку.

Во всех случаях, когда элемент а имеет квадратный корень, может использоваться chirp-алгоритм Блюстейна. Согласно теореме 4.6.15, каждый элемент поля Галуа имеет квадратный корень. Для полей характеристики 2 -j/a = «("+/2, так как

СЫгр-алгоритм Блюстейна:

Vj = S «"гг = Р" [Ргг]

chirp

chirp

Алгоритм Рейдера:

Длина п должна быть простым числом В качестве примитивного элемента поля GF (п) используется я.»

1, 2, 3, ..., п - 1 = n зх, ..., n"-(modn)

/г-1

Vj=1 aiVi, i = n-l-r (О], / (/)

fi-I n-l

Vo=I Vi, Vj = Uo Ь S aiVi =

/ = 0,

R- 1

ViVo + "lia-"-l)vk,

fc=i

/ = 0, . .., n - 1

Сумма

Без перестановки

Рис. 9.9. Переход от преобразования Фурье к свертке.