жений иа каждые пять выходных точек (1,6 умножений и 6 сложений на одну точку на выходе).

Теперь рассмотрим такую же задачу для секции прореживающего фильтра с пятью отводами и тремя выходными отсчетами. Алгоритм для такой секции можно записать равенством

в этом алгоритме с помощью трех дополнительных сложений сочетаются алгоритмы 3-фильтр-секции и (3, 2)-фильтр-секции, так что в общей сложности этот алгоритм прореживающей фильтрации содержит девять умножений и 26 сложений.

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

Алгоритм записан в виде вычисления 3-точечной линейной свертки 2-точечной линейной свертки и трех дополнительных сложении сочетающих результаты этих сверток. Таким образом, paccMq тренный алгоритм прореживающей фильтрации содержит восем умножений и 26 сложений на каждые пять точек на выходе. Есл этот алгоритм использовать в методе перекрытия с суммиров нием, то для сочетания секций, каждая из которых содержит пят входных точек, потребуется еще четыре дополнительных сложи ния. Такой алгоритм будет содержать восемь умножений и 30 слЙ

За.ченим теперь {е , е, е, е, на (Sj, s s Sj, Sj) и fi, /2, /3, /4) на (dg, d di, 4, da). Тогда

gj g, 0 0

0 81 Sj 0 0

0 So Si 8, 0

,0 0 Sl 8, 0

[0 0 g 81 8

d, 0 0 d.

0 rf 0 0

0 (/0 d

0 d, 0 rf, 0

d, 0 d, 0 d,

Мы получили уравнения для интерполирующего фильтра, поскольку нулю теперь равны входные точки. Таким образом, применение трансформационного принципа к прореживающей в отношении 2 : 1 5-фильтр-секции привело к интерполирующей в огношении 2 : 1 5-фильтр-секции. Алгоритм содержит восемь у.чножений.

9.5. Фильтры прореживания и итерполяции

Фильтром прореживания называется КИО-фильтр, которь вычисляет только каждый г-й выходной отсчет; часто г равно или 3. Все прочие выходные отсчеты нежелательны и п(< давляются, даже если они вычисляются. Можно надеяться существование более простых алгоритмов, не вычисляющих н нужные выходные точки. Фильтр интерполяции действует npq тивоположным образом: отсчеты на выходе такого фильтра фо± мируются с большей скоростью, чем на входе. Прореживающий и интерполирующий фильтры иногда называются фильтроЯ с подавлением и фильтром с восстановлением соответственно.

Конструкции прореживающего и интерполирующего КИС, фильтров аналогичны общим конструкциям КИО-фильтров. ОА нако, их специфические особенности можно использовать дл построения более эффективных алгоритмов. В первом случа более эффективные алгоритмы можно строить из-за выбрасывав мых выходных точек, а во втором - из-за выбрасываемых вxo ных точек.

Для фильтров прореживания алгоритмы линейной свертки алгоритмы секционной фильтрации не связаны между собо описываемым теоремой 9.2.1 трансформационным принциполС Трансформационный принцип преобразует алгоритм свертки дл прореживающего фильтра в алгоритм секционной фильтрация для интерполирующего фильтра.

Рассмотрим алгоритм линейной свертки для прореживающее в отношении 2 : 1 фильтра с пятью отводами, на вход котороп подается 5-точечный вектор. Необходимый выходной вект дается вычислением

326 Гл, 9. Архитектура фильтров и

Таким же образом, алгоритм прореживающей 5-фильтр-сек ции, записываемый равенством

9,6. Автокорреляция н взаимная корреляция

So g, 8: g, О О О

О О g, g, g, g, 0

0 0 0 0

может быть трансформирован к алгорит.\1у

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

Следующим рассмотрим (на примере) алгоритм симметричной прореживающей фильтрации. Построим алгоритм сим.четрическогс прореживающего в отношении 2 : 1 15-фильтра. Как и в предыду щем примере, разобьем задачу на симметрическую линейнук 8-точечную свертку и симметрическую линейную 7-точечнук* свертку. Согласно теореме 9.4.3 первая из них может быть вы числена с помощью алгоритма фильтрации 8-точечного вход в фильтре с 7 отводами.

Для вычисления обеих линейных симметрических свертоь воспользуемся разработанным в предыдущем параграфе методом! Степень многочлена

т (х) = X (х - 1) (X -г 1){х- оо) (х= + 1) (х= +

+ X + 1) (х - X + I) {x + l равна 14 и, следовательно, им можно воспользоваться для по строения алгоритма линейной фильтрации 8-точечного входи в фи.тьтре с 7 отводами. В разд. 9.4 было опреде.тено число умно жени и, связанных с использованием в качестве модуля каждогч из указанных симметрических многочленов. Это приводит к об

щему числу умножений в алгоритме, равному 16. Аналогично, выбрасывая один линейный мнржитель, получаем алгоритм фильтрации 7-точечного входа в фильтре с 7 отводами, содержащий 15 умножений. Следовательно, для решения рассматриваемой задачи можно построить алгоритм, содержащий 31 умножение.

9.6. Автокорреляция

и взаимная корреляция

Выражение вида

JV-I

/ i = S gi+jdft.

4=1)

i = О.....L+N-2.

называемое корреляцией, если g совпадает с d, и взаимной корреляцией, если g и d различны, очень тесно связано со сверткой. Его можно сделать похожим на свертку, если просто прочитать одну из последовательностей в обратном порядке. В принципе, любой из рассмотренных нами методов вычисления линейной свертки годится для вычисления корреляции. Тем не менее, имеется одно практически существенное различие. Длина КИО-фильтра обычно намного меньше, чем длина фильтруемой последовательности данных, а входящий в корреляцию фильтр g (х) на самом деле представляет собой другую последовательность данных, длина которой примерно равна длине последовательности, обозначаемой многочленом d (х); часто длина записи обеих последовательностей неопределена и весьма велика - возможно, несколько сотен отсчетов. Хорошие алгоритмы разбивают g и d на секции.

Мы начнем рассмотрение с вычисления автокорреляции

1 = 0.....п/2 - 1,

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

2 dk.{.[n/2dk+[n/2+tt

i = 0, i = 0,

n/2-I, 1-1,

векопягШ 0 бР - <= елась к вычисление

вектора П) для / = О.....L - 1, который мы будем находить

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

Тогда

(О I <ii+W2, i = О, ..., п/2 - 1, ~ i = n/2, п- 1,

= 0.....л-1.

= Д d*ff4+(, < = О.....п/2 - 1.

Пусть D ) и ОС) обозначают векторы, полученные преобразова. ниемФурье из векторов d<i и g ). Тогда согласно задаче 1.10. ре*ляции РР Фурье циклической кор-

= ( = 0.....п-I,

и половина из этих компонент дает искомые нами величины

= -Ls< , , = 0, л/2-1.

Таким образом, сначала мы вычисляем вектор S.= soi Gt , А = 0.....л-1,

а затем вычисляем его обратное преобразование Фурье s и пола; гаем Ti = (I/iV) s, для < = О, п/2 - 1.

Для завершения описания алгоритма покажем, как исключит некоторые вычисления. Вместо использования БПФ для вычисле ния воспользуемся формулой

Эта формула является прямым следствием свойства задержки дл преобразования Фурье; умножение в частотной области иа в соответствует временному сдвигу на Ь позиций. Если b = n/is то это соответствует умножению D на (-1). Во временн6

области происходит сдвиг ненулевых позиций вектора d<+i) в нулевые позиции вектора d*; во временной области сумма равна gC*, II, следовательно, в частотной области сумма равна GC). Таким образом, это вычисление можно записать в виде

S.= EDi [Dl4(~l)Oi+ ]-

Алгоритм завершается вычислением обратного преобразования Фурье.

Блок-схема вычислений в окончательном виде показана на рис. 9.6. Отметим, что каждый цикл содержит только один БПФ-алгоритм, хотя в начальной точке и в последней точке алгоритма добавляется еще по одному БПФ. Таким образом, хотя вычисление одной циклической свертки содержит три преобразования Фурье, мы построили алгоритм, который в среднем на цикл содержит только одно БПФ,

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

Аналогичный метод применим и к задаче вычисления взаимной корреляции. Обе последовательности данных разобьем на отрезки, комбинируя которые в частотной области, мы уменьшаем число необходимых обратных преобразований Фурье.

Теперь на одном очень подробном примере покажем, как можно использовать другие методы в рассматриваемом способе

вычисления корреляций. Запишем корреляцию = d+tgh в матричном виде.

,1 ll-J

где г намного больше п.

Мы опишем структуру алгоритма для частного случая л = 120 и г = 10 ООО. Основываясь на некотором опыте, примем произвольное решение разбить последовательность из 120 выходных точек на четыре пакета по 30 выходных точек в каждом, и организуем вычисления, опираясь на 60-точечный БПФ-алгоритм Винограда.