8,4. а. По заданным малым 2-то,ечиому и 5-тх)чечному БПФ-алгоритмам Винограда

i о о о о о II I 1-1 о 11-1 10 1

I 1-1-1 0-1

[1 I 1-1 1 о

-1.25 .559 J.95I J.15 -J.363J

О О -Ij

постооить большой 10-точечный БПФ-алгоритм Винограда. 6 Сколько вещественных умножений содержит этот алгоритм? , Скмько вещественных /множений будет содержать алгоритм, в котором ;точечный точечный алгоритмы сочетаются по методу Гуда - Томаса? г Ппелположим что этот 10-точечный БПФ-алгоритм используется по метвду КулТьюки для построения ЮОО-точечного БПФ-алгоритма Гколько вещественных умножений будет содержать такой алгоритм? Как он соотн< тся с 1024-точечным БПФ-алгоритмом Кули - Тьюки по осно-

Г предположим, что вместо выписанного ранее 2-точечиого алгоритма используется следующий алгоритм:

8.8.

Что получится, проигрыш или выигрыш? .5. Дли вычисления преобразований Фурье длин 72, 315 и 5040 можно восполь-.зоваться большим БПФ-алгоритмом Винограда. Найти число необходимых сложений и число необходимых умножений в таких алгоритмах. ,6. Построить алгоритм вычисления двумерного (256Х 256)-точечного преобразования Фурье, сочетая БПФ-алгоритм Кулн - Тьюки с перестановочным алгоритмом Нуссбаумера-Квенделла. Сколько умножений я сложений содержит алгоритм? .7. Описать построение !040-точечного БПФ-алгоритма, основанного на трехмерной циклической свертке. Сколько умножений необходимо? Имеется много способов построения двумерного {63ХбЗ)-БПФ-алгорнтма. Найти число умножений, необходимых н каждой из следующих процедур.

а. Гнездовой метод сочетания 63-точечного одномерного БПФ-алгоритма с самим собой. (Какие здесь име1бтся возможности выбора?)

б. Гнездовой метод сочетания двумерного (7Х7)-БПФ-алгоритма с двумерным (ЭХ9)-БПФ-алгоритмом.

в. Алгоритм разложения Нуссбаумера - Квенделла, сводящий задачу к четырехмерному (7Х7Х9Х9)-БПФ-алгоритму.

.9, Для каких значений п перестановочный алгоритм Нуссбаумера - Квенделла вычисления двумерного преобразования Фурье не приносит преимуществ по сравнению с гнездовым методом сочетания одномерных алгоритмов? Изменится ли вывод в случае трехмерных преобразований ( ели число точек простое)?

двумерное (р X р)-прео6разование Фурье может быть вычислено ] как и ранее.

В общей сложности алгоритм содержит р + р одномерных р-точечных преобразований Фурье и р + I одномерных р-точеч-ных преобразований Фурье. За исключением одного р-точечного ; преобразования все преобразования Фурье являются выколотыми.

Число точек по осям равно степени двух. Хотя конструкция для случая, когда число точек По осям двумерного преобразования рвв-. на степени двух, по существу совпадает с описанной выше, OHal все-таки отличается настолько, что заслуживает отдельного рассмотрения. Так как все нечетные меньшие чем 2 * целые числа взаимно просты с 2 , то к компонентам с этими индексами опять i применима теорема 8.7.1. Компоненты Vk. k для нечетных к и fe = О, л - I вычисляются применением л-точечного полиномиального преобразования по модулю (х + \) и п одномерных п-точечных преобразований Фурье при л = 2 . В данном случае полиномиальное преобразование может быть-организовано в виде , БПФ-алгоритма Кули-Тьюки по основанию 2. Тогда число сложений будет пропорционально л logj л. Все преобразования Фурье будут выколотыми с равными нулю входными компонен- i тами с четными индексами.

Мы описали вычисление одной половины компонент Kf, i для которой к нечетно и ft = О, П - 1. Теперь поменяем ролями к и к к вычислим оставшиеся невычисленными компоненты Vk.f с нечетными* и четными ft. Для этого нам понадобится еще одно полиномиальное преобразование и еще л/2 одномерных преобразований Фурье.

Наконец, остается вычислить компоненты Vk-. оба индекса которых четны. Но они образуют (2 - X 2 )-точечное преобразование Фурье, вычисление которого можно организовать по той же схеме, что и вычисление (2 х2 )-точечного преобразования. Фурье.

Задачи

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

8.2. Для рассмотренных в разд. 8.1 БПФ-алгоритмов Кули - Тьюки по основанию 2 и 4 определить число необходимых сложений.

8.3. Пусть Л (п) и Л1 (л) обозначают число сложений и число умножений в БПФ-алгоритме Винограда длины п.

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

[М (л) - пУА (п) > 1/И (п) - п]/А (п ),

б. Провести аналогичный анализ отдельно для числа предсложений и чнсла постсложений.

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

8. П. а. Доказать, что многочлен Рейдера от двух переменных g(x,y) равен произведению многочлена от л: на многочлен от у.

б. Сформулировать и доказать для двумерных преобразований Фурье аналог теоремы 4.6.2.

8.12. Построить (5х5)-БПФ-алгоритм Нуссбаумера-Квенделла.

8.13. Отталкиваясь от 4-точечного БПФ-алгоритма и двумерного (ЗХЗ)-БПФ-алгоритма, описанного в данной главе, построить двумерный (12ХЗ)-БПФ-алгоритм.

Замечання

Простейший из алгоритмов вычисления двумерного преобразования Фурье сводится к последовательному выполнению одномерных преобразований по обеим осям двумерной таблицы. Поэтому все быстрые алгоритмы вычисления одномерных преобразований в готовом виде были перенесены на двумерный случай. Существенно двумерные алгоритмывозникли позже. Двумерное разбиение типа Хули - Тьюки было предложено Райвордом (I] (1977) и обобщено в работе Гарриса, Макклеллана, Чэна и Шусслера [2] (1977). Мерсере и Спик 13] (1981) описали изящную унификацию различных двумерных БПФ-алгоритмов Кули - Тьюки.

С целью создания более эффективной упаковки алгоритмов Виноград 14] (1976) предложил гнездовой метод соединения своих малых одномерных алгоритмов. Двумерные алгоритмы его интересовали как некоторое искусственное средство построения алгоритмов одномерных преобразований Фурье, но эта же техника применима и к возникающим естественным путем двумерным преобразованиям Фурье. Дальнейшее развитие гнездовой метод Винограда получил в работах Колбы и Паркса 151 (1977) и Сильверменэ 161 (1977). Методы построения последовательности БПФ-алгоритмов, промежуточных по отношению к БПФ-алгоритмам Гуда - Томаса и БПФ-алгоритму Винограда, были рассмотрены Джонсоном и Баррасом [7] (1983). Использовать полиномиальное преобразование Нуссбаумера для вычисления преобразований Фурье предложили Нусс-баумер и Квенделл [8] (1979). Другую структуру алгоритма вычисления двумерного преобразования, основанную на связанных с циклическими структурами расширений полей Галуа перестановках, описали Ауслендер. Фейг и Виноград [10] (1983). Характеристики этого алгоритма близки к характеристикам БПФ-алгоритма Нуссбаумера - Квенделла.

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

Наиболее важным устройством в обработке дискретных сигналов является КИО-фильтр. На фильтр поступает в.ходной поток отсчетов цифровых данных, и на выходе фильтра формируется выходной поток отсчетов данных. Длины этих потоков данных очень велики; возможно, каждую секунду через фильтр проходят миллионы отсчетов. Быстрые алгоритмы фильтрации всегда разбивают поток входящих данных на пакеты, содержащие, возможно, сотни отсчетов. Единовременно обрабатывается только один пакет; результат обработки помещается в выходной буфер, данные из которого считываются с необходимой скоростью.

9.1. Вычисление свертки секционированием

В гл. 3 было построено много алгоритмов вычисления циклической свертки. Их можно использовать как непосредственно, так и в качестве модулей для построения хороших алгоритмов преобразования Фурье подобно тому, как это сделано в гл. 4. БПФ-алгоритмы, в свою очередь, могут быть использованы для построения эффективных алгоритмов вычисления свертки, особенно когда длина велика. В основе такого вычисления лежит теорема о свертке, согласно которой циклической свертке во временной области

i = 0,

. п-\,

в частотной области соответствует произведение S, = GjD fc = 0.....n-1.

АРХИТЕКТУРА ФИЛЬТРОВ И ПРЕОБРАЗОВАНИЙ

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

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

Выберем удобную для построения преобразования Фурье длину /г, такую, чтобы выполнялось условие п > 2л, и удлиним векторы g, d и S так, чтобы компоненты с индексами i = О, л - ) принимали предписываемые им циклической сверткой длины п значения, несмотря на то, что вычисления производятся на удобной для преобразования Фурье длине л. Например, определим

= 0.....n-l,

= 0.....л - 1,

= 0.....л-1,

= л, л - л - 1, = л - л, . .., л - 1,

где теперь двойные скобки обозначают вычисление по модулю л.

Тогда sl = Si для ( = 0.....л - 1. Остальные значения sl

не представляют интереса и могут быть отброшены.

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

iMbi сначала опишем метод, известный под названием метода перекрытия с накоплением. Предположим, что у нас имеется устройство вычисления циклической свертки длины л, и что нам нужно умножить многочлен g (х), степень А которого меньше л, на мно-

гочлен d (х), степень В которого больше л. Обычно В очень велико и можно полагать его равным бесконечности. По многочлену d (х) построим множество многочленов {d (х), d > (х), ...) степеней л - 1 или меньше, полагая их коэффициенты равными

Многочленов должно быть достаточно для исчерпания всех коэффициентов многочлена d (х). Заметим, что так построенные многочлены перекрывают друг друга. Для каждого ( определим s(ii (X) = g (х) d<> (х) (mod х - 1).

Тогда, так как s (х) = g (х) d (х), то за исключением первых А коэффициентов, коэффициенты многочлена s (х) находятся среди коэффициентов многочленов s i (х). А именно,

и так далее. Таким образом мы получаем на выходе фильтра бесконечную последовательность данных. Первые А младших коэффициентов многочлена s (х) теряются. Во многих приложениях линейной свертки такая потеря в начале фильтрации является несущественной. Если же на выходе нужны все коэффициенты, то надо просто заменить многочлен d (х) на многочлен х-* d (х). При этом будут вычислены все коэффициенты свертки, но индексы их будут сдвинуты на величину Л.

Каждая из рассмотренных циклических сверток за исключением последней вычисляет л - Л коэффициентов искомой линейной свертки и А бесполезных коэффициентов, которые просто отбрасываются. Поскольку степень последнего входного сегмента d (х) может быть меньше л - 1, то последняя свертка может содержать больше, чем п - А, значимых коэффициентов.

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