Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 47
Текст из файла (страница 47)
Мы не можем сделать это в достаточно общем виде, поскольку иет ника. кой общей теории минимизации числа сложений и, что еше важнее, поскольку это не позволяет построить алгоритм, хороню распадающийся на мелкие подпрограммы так, как рассматриваемый ал. горитм. Тем не менее кое-что можно сделать. 6-точечные циклические свертки можно скомбинировать с некоторыми препсложениими и постсложеннями так, чтобы сформировать 7-точечные преобрззоваиия Фурье. Эю не меняет числа необходимых умножений. Вмчислення в так организованном алгоритме будут состоять нз некошрык предсложений, одного 7.точечного преобразо.
ванна Фурье, одной 6-точечной циклической свертки, одной дву. мерной (бх 6).свертки и некоторых постсложений. Полное число сложений умевьшашся следующим образозс Предсложення 7-точечное БПФ 6-точечнан цинлическая свертка Циклическая (6 х 6)-свертка Постсложеиия Эта, конечно, небольшое улучшение. В качестве второго примера рассмотрим двумерное (5 х 13)- преобразование Фурье.
Как показана на рис. 8.14, разобъем его иа 4-точечную циклическую свертку, 12-точечную циклическую свертку и двумерную циклическую (4 х 12).свертку. Для вычисления двумерной циклической(4 Х 12).свертки преобразуем ее в трех. мерную циклическую (4х4хЗ)-свертку и воспользуемся гнездовым алгоритмом, сочетающим алгоритм циклической (4х4) свертки с алгоритмом 3-точечной циклической свертки; этот алто. ритм содержит 88 вещественных умножений и 608 вещественнмх сложений. Присоединяя 4-точечную циклическую свертку и 12- точечную циклическую свертку (20 вещественных умножений и 100 вещественных сложений) и учитывая одно связанное с компонен- Зб Д. Р" Р э о) о) 4 а ц«я цш ен а» «раке э э За4 Г .
б В рм ээшр оагэн р * р бр о эв)Е 72 Р с. а 14 Р зб ев э (бХ!З). Рюбраээввннв Фтр тай У,а тРнвнальное Умножение, полУчаем (Б х 1З)-БПФ-алгоРитьг, содержащн)г П4 вещественных уь)ноженнй н 939 вещественных сложений. (Б х 13)-БГ(фалгоритм с несколько лучшими характеристиками получается, если ппдпрограмму 13-точечнага БПФ с 26 негривяальнымн вещественнымн умноженнямн н 94 вещественными сложениями использовать вместо 12-тпчечной цнклнчесной свертки; тогда чнсдо вещественных умноженнй равно П4, а число необходимых вещественных сложений равно 917. Описанный метод пригоден н в том случае, когда числа точек па осям равны степеням простых чисел. Разбненяя множеств нн.
кексов на подмножества даются теперь более сложными прааиламн. Нвпрнмер, рассмотркм задачу вычисления двумерного (7х9)- преобразования Фурье Так как число 9 не является простым, та для построения алгоритма аужен более общнй, чем рассмотренный выше, метод. Напомним, что обобщая в гл.
4 алгоритм Рейдера яа случай вычисления 9-точечкой свертки, мы выбросили все не взаимно простые с 9 ннлексы н свели задачу к вычислению Б-точечной циклической свертки и двух 2.точечных пинлн )ескях сверток. Постуна» гак же и — — 9 теперь, мы 'получаем двумерную пкнлнческую (Бхб)-свергну н две лвумерные циклические (2хб).свертка. Такнм образом, как показано на рнс. 8 13, двумерный (7х9). БПФ-алгоритм строится нэ лвумерной циклнческой (бхб)- свертки, двух двумерных циклнчесннх (бх2)-сверток, 9.точечного БПФ-алгарнтма н 6-тога «мд 1 че )ной цнклнческай сверткн. В общей слажвостн такой Рэс а.)з, Р эбвенвэ (гха). р брн алгоритм требует 62 -1. 2 х э в вв Фуры.
х)Б -1- 10+ 8 = 102 умноже- р) 41б, рюб»щ двум р» Э (бХб)- р ннй, поэта число можно уменьшить, если более тщательна струк. турнровать алгоритм Мы не учли того факта, чтоб-то )ечная сверг. ка, получающаяся пря преобразования 9.точечного преобразова. ння Фурье по алгоритму Рейдера, прнводнт к нескольким умноженнвч на нуль Этн умнаження, описываемые теоремой 4.6.2, можно ве учитывать. (бхб)-свертка возникает из двумерного аналога обобщенного алгоритма Рейдера.
Дт» двумерного (ГХ9)-преобразования Фурье многочлен Рейдера ат двух переменных рбвен э Г у (х, у) = ~ (м' — 1) х) ~ ~ К (Р~ — 1) у'~, 1! ) ) гле н — первообразный корень степени шесть нз едннкцы, а Р .— первоабразпый корень степени девять из единнлы. Для построения алгорнтма пнплической (Бхб)-свертки запи- шем х' — 1 = (х' -1- х -1- 1) (х — 1) (х -1- 1) (х' — к -1- 1), у' — 1 = (у* + у -Р 1) (у — И Ь -1- и Ь' — у+ 1), а вычислим вычеты мнагочлена у (х, у) по модулям, равным этим делателям Как показана на ркс. 8.16, зтн вычяслення можно разбить на 16 фрагментов. Согласно теореме 4.Б.2, фрагменты, связанные с малулямн (у — 1) к (у + 1), прнваднт к равным нулю вы )егам, я, следоватачьно, могут быть выброшены. В квадратах на рнс.
8.16 указаны числа умноженнй, кеобходкмых прн нычисленян каждого фрагменте, прячем в скобках пряведеча число ум. ножений, необходимое в случае, когда вычет не равен нулю. Ог. сюда видно, что для аычнслення циклической (Бхб)-свертки требуетсн тольно 36 умножений, так что полное чксло умножений в алгоритме (7х9)-точечного БПФ равно 86. 286 Гл. 8. Б р 4 «лг рк к и ер мх эз брзэсзз иа 8.8. Улучшенный алгоритм Винограда быстрого преобравовання Фурье Коль скоро задача вычисления одномерного преобразования Фурье с помощью алгоритма Гула †Тома сведена к задаче вычисления мнаюыерногс преобразования Фурье, то дальше можно ее решать сведением к многомерной свертке.
Такай путь вычяслевия одномерного преобразоваии» Фурье очень похож на большой БПФ.алгоритм Винограда, но с одним отличием. Напомним, что бальнюй ЬПФ-алгоритм Винограда «омбннирует два али больше малых БПФ-алгоритмов, ио не меняет их структуру. Однако каждый нз малых алгоритмов страатся на основании быстрого алгоритма свертки, тан что можно ожидать, что в большой задаче содержится многомерная свертка. Большой БПФ-алгоритм Винограда не пытается извлечь измнагомерной свертки никакой пользы и он в конечном счете вычисляет ее, сочетая гнездовым способом два одномерных алгоритма. Если многомерная свертка достаточно валика, то характеристики можно улучшить, применяя для вычисления этой свертки более сильные алгоритмы.
Характеристики л'л"-точечнога улучюеннаго БПФ-алгоритма Винограда лучше, чем характеристики большого я'лцточечногс БПФ-алгоритма Викагрэда, если р(л') и Ф (с") имеют абший делитель, равный по меньшей мере четырем. Характеристики для некоторых таких алгоритмов приведены на рис. 8.17. В основе улучшенного алгоритма лежит сочетание трех идей; сведение о»номерного преобразования Фурье к мноюмерному с помощью алгоритма Гуда †Тома, многомерный аналог алгоритма Рейдера и использование аолнномиальвого преобразования для вычисления многомерной свертки Рейдера. Первая из этих идей относится талька к индексации данных. Сочетание второй идеи с третьей уже рассиатривалось в предыдущем разделе при пс«тросики алгоритмов разложения. Для построения улучшенного алгоритма надо модифицировать один из двумерных ал.
гаритмав, используя перестановку сгалбца» матрицы предсложений и перестановку строк матрицы пастслсженнй. Рассмотрим сначала 15-тачечное преобразование Фурье. Ега можно трансформировать в двумерное(3 х 5)-точечное преобразоэание Фурье. Используя далее алгоритм Рейдера вдаль каждой оси, выделим двумерную циклическую (2х 4)-свертку, записываемую в анде з(х, у) =8(х, у)б(х, у) (шоб х' — 1) (пюб у* — 1).
Эта свертка так коротка, что наилучшим способом ее вычисления являетсв гнездовое сочетание одномерных алгоритмов свертки. Для л = 15 улучшенный БПФ-алгоритм не лучше большога БПФ- 87, нчрмть ч я л рт ну б у г — кэ згл б. 87 8 76 !! 74 ! 1,36 !4 Ю !7.!Я ! !3 !.24 1щ !.37 ! 74 ! 75 163 134 4Н 7!2 917 1Ббо !б' !8 17 2! 27 26 35 54 53 ш ю % 65 ' !!4 !И д! !59 158 Р 8 !7. Х ра мрэсгчх» улу меч с б раг ююр»шэ рмсрэзсз Фуэ 8.7. Перествновочный алгоритм Нуссбаумера — Квенделла В прелыдущей главе, записав многомерную свертку в виде снертни многачленов, мы смогли воспальзаватьс» поли номнальным представлением расширений полей для построения алгоритмов многомерных свертон.
Теперь мы воспользуемся полиномнальным представлением расширений волей для того, чтобы построить алгоритмы вычисления многомерных преобразований Фурье. Одним из применений многомерных преобразований Фурье является, конечно, вычисление многомерных сверток, так что фактически мы построим другой способ вычисления мноюмерных сверток.
Еще раз иам удбется построить «арошие алгоритмы лля одного класса задач, с»еда этот класс к Лругаму классу задач, лля каторога решение уже имеется. Такой подход может показаться чрезвычайна искусственным, так как сначала мы ввели полиномиальное преобрааование как одну из фарм записи преобразования Фурье, а затем отказались от этой точки зрения. Теперь мы алгоритма Винограда, а иа самом деле даже хуже, так как содержит больше сложений Теперь рассмглрим 53.точечное преобразование Фурье. Большой БПФ.алюритм Винограда содержит в этом счучае 98 нетриввальных вещественных умножений и 704 вещественнык сложений Рассмотрим улучшенный БПФ.аагоритм, начинающийся сведением 63-точечного преобразования Фурье н двумерному (7х9)-преобра.
зованию Фурье, для вычисления которого используется показан. ная на рис. 8.15 структура. Такой алгоритм содержит 85 петри. ввальных вещественных умножений и 712 вещественных сло. женил. 2% Гл.б Б Э р ннэг раз эробр «З 289 87 поз*с е зка ыюр ! нтск 7 рэ — кыэыээ опять переворачиваем исю постановку задачи и используем полнномнальное преобразование для вычисления преобразования Фурье, хотя н не того самого, которое первоначально привела иас к определению полнномиального преобразования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
