Таким образом, для вычисления s< i (х) нужно только два умножения. Остальная часть алгоритма остается без изменений и в окончательном виде алгоритм записывается равенством

10 0 0

1111 1-1 1-1

10-10 0-1 о 1

iP о о 1

Этот алгоритм содержит шесть умножении и it слилспии. Его можно использовать в методе перекрытия с суммированием для реализации симметричной 3-фильтр-секции, содержащей 1 5 умножений и 4.5 сложений на каждую точку на выходе.

Даваемый теоремой 9.2.1 принцип трансформаций позволяет преобразовать этот алгоритм в алгоритм симметричной (4, i)-фильтр-секции, содержащий 1.5 умножений и 4 сложения на каждую точку на выходе. Этот алгоритм дается равенством

rf, d, dl

d, d,

d, d: d,

d, d, d,

i 1 1 1 0 б

0 1-1 0-10 0 1 t-I 0 0 0 1-1 0 11

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

Фильтр с L отводами, описываемый многочленом (х), называется симметрическим фильтром, если многочлен g (х) равен своему взаимному многочлену, т. е. если g (х) = x-xg (х-) или, эквивалентно, если gt = gb-i-t- Фильтр с L отводами, описываемый многочленомg (х), называется кососимметрическим фильтром, если многочлен (х) равен своему взаимному многочлену со знаком минус, т. е. если g (х) = -x-g (х ), или, эквивалентно, . если gi = -gL-ii- Мьг начнем рассмотрение симметрических i фильтров. Для симметрического фильтра с L отводами имеется очевидный алгоритм, содержащий для вычисления каждого вы- \ ходного отсчета (L - 1) сложений и только L/2 умножений, если L четно, и (Z, + 1)/2 умножений, если L нечетно. В этом очевидном алгоритме перед умножением на общий множитель gj складываются точки с индексами i и L - i - 1. .

Алгоритм Винограда для свертки в случае симметрического фильтра строится точно так же, как и ранее. Построим алгоритм для вычисления выхода симметрического фильтра с тремя отводами, на вход которого подается 4-точечный вектор. Пусть

g (А = gjj; -1- gxx + go,

d (x) = 4 + d,x -f d,x + d

s (X) = g (x) d (x) (mod (x -x) (x-oo)).

Поскольку deg s (x) = 5, то приведение по такому модулю никак не сказывается на s (х). Простыми делителями модуля являются четыре многочлена первой степени, каждый из которых в алго- , ритме приводит к одному умножению. Имеется также простой \ делитель х + 1, который, как можно было бы ожидать, приводит к трем умножениям. Но, как мы увидим, в силу симметрии он ( вносит в алгоритм только два умножения. Пусть S (х) = g< ) (х) d< ) (х) (mod х -f 1),

d< i (х) = (d, - d,) X -f (do - d,)

gi°i (x) = g,X -f (go - go) = g,x.

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

ё (х) = go- + йх + ёгх + giX + go. и рассмотрим вычеты

gHx) = g{x) (modx+ 1), g ix) = g{x) (modx--x+ 1), e>(x) = g(x) (modx -x-t- 1), gH>(x) = g(x) (modx+l). Легко проверить, что эти вычеты равны g l(x) = 2g -g

(х) = (go + ft - gj) X + (g + g, - g,) = = {x+ I)(g -t-g,-g,), gO) {x) = (-g -t- gi + gj X - (-g + gi + g,) =

= (X- 1)(-g + gi +g,), g<) (x) = giX + g,x + g,X = X (giX + g,x + g,).

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

sW (х) = gci (X) dci (X) (mod ш (х)),

то мы можем запрятать этот дополнительный множитель, спря тав его в переопределенном остатке dC) (х). Пусть d<4 (х) = d (х) (mod х + I),

d(2i (х) = (х+ l)d (х) (modx + x-h 1), d i (х) = (х - 1) d (х) (mod х -X + 1), di (х) = xd(x) (mod х< -~ 1).

Тогда вычеты g(0 (х) переопределятся по правилам г< (X) = 2g -g g >(x) = g + g,-g

9.4. Симметрические и кососимметрические фильтры

g(3) (х) = -g + g, -Н g

gW (х) = giX -I- g,x -f- gi. Для вычисления каждого из остатков sd) (х), s) (х) и si) (х) потребуется два умножения, а остаток s<> (х) надо вычислять как линейную свертку с последующим приведением по модулю х* -- 1. Эта линейная свертка представляет собой прохождение 4-точечного вектора через симметрический фильтр с тремя отводами. Алгоритм такой фильтрации с шестью умножениями мы уже построили.

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

m (х) = X (X - 1) (X + 1) (х - оо) (х -н 1) (х= - X + 1) X

X (х -Ь X -Ь 1).

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

Предположим, что требуется пропустить через этот же фильтр 14-точечную последовательность. Тогда к использовавшемуся ранее многочлену m (х) добавим еще один множитель, х* + 1. Это добавит в алгоритм еще шесть умножений. Окончательный алгоритм будет содержать 16 умножений (1.14 умножений на один отсчет на выходе).

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

Теорема 9.4.1. Пусть четное число t не меньше четного п и пусть г (х) обозначает остаток от деления симметрического многочлена g (х) степени t на симметрический многочлен т (х) степени п над основным полем G. Тогда г (х) можно записать в виде

г{х) = f (х) г (х) (mod m (х)),

где г (х) представляет собой симметрический многочлен степени п - 2 и f (х) - некоторый многочлен над основным полем О {не зависящий, следовательно, от коэффициентов многочлена g (х)).

Доказательство. Без потери общности можно полагать, что многочлен m (х) приведен. Так как т (х) является симметрическим

И Блейхут Р.

g W =

влечет за собой равенство

(x-i)gw = -xi-(4.- i)g- (4-),

или равенство

g (X) = x-g (x-i).

Таким образом, фильтр, описываемый многочленом g (х)\ эквивалентен фильтру с многочленом g (х), за которым следуе

(пли которому предшествует) фильтр с двумя отводами, описываемый многочленом (х-I).

Теперь предположим, что многочлен g (х) задает кососимметрический фильтр с нечетным числом L отводов. Тогда 1 и -1 являются корнями многочлена g (х), так как центральный коэффициент равен нулю и

g(±l) = (S gi + gL-i-,)±( S gi + gi-i-i)=0-

\<чет. / Vt нечет /

Следовательно, можно определить симметричный фильтр с L - 2 отводами, задавая его многочленом

g (X) = g (x)/(x - 1). Таким образом, фильтр, описываемый многочленом g (х), эквивалентен фильтру, зaдaвaeмofy многочленом g (х), которому ]1редшествует (или за которым следует) фильтр с многочленом 1. □

Фильтры, задаваемые многочленами х - 1 или х - 1, приводят к некоторым дополнительным сложениям на входе или выходе. Следовательно, изменяя соответствующим образом матрицу предсложений или матрицу постсложений, мы преобразуем алгоритм для симметрического фильтра в алгоритм для кососимме-трического фильтра. Как всегда, если этот алгоритм используется в методе перекрытия с суммированием, то его следует брать в форме алгоритма для линейной свертки. Напротив, если в конструкции используется метод перекрытия с накоплением, то следует воспользоваться даваемым теоремой 9.2.1 принципом трансформаций для преобразования алгоритма в алгоритм секционной фильтрации.

Как оказалось, тот же метод, который позволяет свести за-.чачу для кососимметрических фильтров к задаче для симметрических фильтров, позволяет при нечетном числе L отводов свести задачу для симметрического фильтра с L + I отводами к задаче для симметрического фильтра с L отводами.

Теорема 9.4.3. Если L нечетно, то алгоритм для сим.четри-ческого фильтра с L +1 отводами получается из алгорит.ча для сим.четрического фильтра с L отводами без дополнительных умножений.

Доказательство. Пусть (L -i- 1)-точечный фильтр задается симметрическим многочленом g (х) нечетной степени L. Тогда g (-1) = О, так что (х i- 1) де.тат многочлен g (х). Следовательно, g (х) = (х -I- 1) g (х), где§ (х) - симметрический многочлен степени L - 1. Таким образом, фи.тьтр, задаваемый многочленом g (х), может быть реализован в виде каскада фильтров, за.тавае-мых многочленами х -f 1 и g (х), без дополнительных умножений. □ И*

многочленом степени л, то т (х) = x m (х ). Если п = t, положим т {х) = т (х); в противном случае, пусть

т {х) = т (х) + х~ т (х).

Этот многочлен является симметрическим степени t, так как

х [т + х-+-т {х->)] = х- т (х) + т (х).

Определим многочлен g (х) равенством

В (х) = g(x)~ g m (х).

Многочлен xg (х) при делении на m (х) дает тот же остаток, чт1, и многочлен g (х). но многочлен g (х) является симметрическим и его степень равна четному Числу, которое по меньшей мере на два меньше степени многочлена g (х). Если степень многочлен g (х) не меньше п, то этот процесс можно повторить до тех nopJ пока не получим многочлен г (х) степени п - 2. Тогда остаток от деления многочлена x<- +2)/V (х) на m (х) равен остатку деления g (х) на т (х). Для завершения доказательства положим fix) = [х<- +2)/2 1. □

Теперь мы перейдем к алгоритмам для кососимметрических фильтров. С этой задачей мы справимся значительно скорее! указав, как алгоритмы для симметрических фильтров можн( превратить в алгоритмы для кососимметрических фильтров.

Теорема 9.4.2. Пусть кососимметрический фильтр содержйп L отводов; тогда, если L четно, то эта задача фильтрации можеп быть решена по алгоритму для симметрического фильтра с L - \ отводами, а если L нечетно, то эта задача может быть решен по алгоритму для симметрического фильтра с L - 2 отводами!

Доказательство. Предположим, что многочлен g (х) описЫ! вает кососимметрический фильтр с четным числом L отводов.

Тогда g (1) = О, так как gi = -gL-i.i для i = О.....{L/2) -

Следовательно, (х - 1) делит многочлен g (х). Определим фильт

g {X) = g (х)/{х ~ I).

Ясно, что многочлен g (х) задает симметрический фильтр с L - i отводами. Симметричность фильтра вытекает из того, что равенствс