Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 44
Текст из файла (страница 44)
Тогда числа умножений описывается рекурреитиым соотиашевием М(л х л)=(БМ( 4 х )+ — пз, решением иоторага является М (л х л) — — и'(1ай л — С), 14 где ноистанта С имеет такой же смысл, как и для алгоритм» по ос- нованию 2. Если выбрать внутреннюю свертку так, что М (4 х 4)=О, то М (я х л) =- — л' (1ой л — 2), 32 н мы видим, что в добавление к хорошей сгруитурированности алгоритм по основанию 4 эффективен в смысле числа необходимых умножений. Для того, чтобы воспользоваться двумерным разбиением по основанию 4, локальная память должна быть столь большой, чтобы чажио было одновременна записать четыре строки матрицы вкадных данных.
В общей сложности таблица входных данных будет переноситься 1ай, н раз, так что всего потребуется — п1ай, и переносов строк из глобальной памяти в локальную и наоборот. 8.2. Гнездовые алгоритмы преобразования Теперь мы рассмотрим другой метод, известный под названием гнездового, в котором многомерные БПФ-алгоритмы строятся сочетанием одномерных БПФ-алгоритмов, квк в БПФ-алгоритме Винограда. Напомним, чта следствием возможности изменения порядка суммирования -т ".-т рь г.= Хз мп"'( ~ рт""ат с1.= т т т.-з — т ' — т т"з 2 с,гз а, т -е явлнется та, по двумерное преобразование Фурье можно вычислять как наследоввтельность одномерных преобразований Фурье 2бб Гэ.
З Бштр г р»пма мима р м ар сбрю а сначала па строкам, з затем по столбцам, нли сначала по столбцам, а затем цо строкам. Для вычисления одномерных преобразований Фурье можно польюваться любой удобной «омбннацней алгарвю мав вычисления, применяя ях к страхам и столбцам, входящим в двумерное преобразовапае. Мы будем работать с малымн ВПФ- алгоратмамн Винограда, отыскнвая эффективные способы нх сочетания. Пусть М (л') н А (л') обозначают соответственно числа умноженкй и сложения некоторого имеющегося в нашем распоряжения одномерного алгоритма л -то гечнаго преобразования Фурье. Для вынолнения и" тапнх одномерных преобразований нужно л М (л') умножений и и"А (л') сложений.
Аналогично, чтобы выполнять л' паеобразованвй длины л", веобходнмо л'М (л") умноженнб н л А (л") сложеяяй. Такнм образом, исвользуя последовательна одномерные преобразования, получаем, что вычислительная сложность двумерного преобразования Фурье равна М (л' х л") = л'М (л') -)- л'М (л ), А (л' х л") .= л"А (л') -)- л'А (л'). Какое нэ измерений тзблнцы выбрано первым, не играет ралн. Поскольку в такой процедуре обработка осуществляется последовательна, та сложность булет той же самой. К лучшей процедуре вычислений пряаоднт сочетание алгорнтмов по гнездовому меюду Винограда Так как для двумерного преобразованин Фурье несушествеваа, что именно, строки нлк столбцы, обрабатываются в первую очередь, то, возможно, существует н путь нх совместного вычисления. Именно это н делает гвездоваб метал Винограда. Он так связывает вычяслення па строкам н по столбцам, что полное число необходимых умножений уменьшается.
Такнм образом, мы будем пользоваться одномернымн алгоритмами преобразования Фурье, на сочетав нх более зффектнвпым образом. Для описания метода воспользуемся кроне. «еровснам пронзведеняем матриц. Пусть %' н )У" обозначают соответственно матрнпы преобразования Фурье длин л' я л", так что У' =- ВГ'ч', У" = »У"ч" н ' — ! м — ! У» = б» 8»»аК У;. = ~ ума", »=О »=» Двумерное (л' х л")-преобразаванне Фурье двумерного сигнала а, !. получается применением матрицы ьуг к каждому столбцу (столбец содержит л' компонент) и последующим применением матрицы цг" к каждой строке.
Зто двумерное вмчисленке можно преобразовать в одномерное так, как показано на рнс. 8.2. Вмпн»пем двумерные таблицы т и У в виде одномерных таблиц, счнтмвая их в стеки по столбцам, н сохраним эа ннмя те же абаз- З 2 Гамаа Р ааюбгм », м .. ю -! м и а ! м ! "л !. -! зм я Рэ«. З.2.
Опар ае двумер оя таблиа оа р ум. аачення, так что входной н выходной одномерные векторы содер- жат л'лс компонент н имеют внд у !У т, Ъ где чп н уп обозначают соответственно столбцы нсхояных дву- мерных таблнц: м Если пад ч и У понимать тан построенные одномерные л'п .точечные векторы, то двумерное преобразование Фурье записывается 26В эА' Вны я юВ юча с пал% эр д Мвся я юус же мн) мй) . 'Уэ %'О О..
О%' О О О%' яяр мз 2 мй! ' ' ' му му, ( му,. М(л') я Ю а э р" г С' Вод гл ч я' сээ лаз чдй ') яю ая Шос я 2ЗЭ Гкз Б р зл рн я р х рмрю юй в виде «ронекеровского произведены». Сначала запишем вычисле- ния в виде где %' — определенная выше (л' х л')-мат)тица, Π— нулевая (л' Х л')-матрица и ) — единичнап (л' х л ).матрица. В этом произведении матриц легко узнать кронекероаское произведение матриц, так что в сокращенной записи имеем Ч вЂ” — %% где % = %" х-%' представляет собой (и'л' х Мл").матрицу.
В БПФ-алгоритмах Винограда длин л' и я' соответственно «а- триды%' и %" разлагаются в виде %' = С'В'А' и %' = С"В"А", где А', А', С' и С' представляют собой матрицы, состоящие только из нулей н еднннп, а матрицы В' н В" являются диагональными. Бсе умножения в алгоритмах Винограда исчерпываются умноже- ниями на матрнцм В' и В" соответственно. Пусть % = %" х %'; применяя дважды теорему 2.5.5., получаем % = (С"В"А") х (С'В'А') = (С" х С')(В" х В')(А" х А') = =- СВА, где кронекеровское произведение С =- С' х С' и А = А' х А' приводит апнть к матрицам, состоящим только из нулей н единиц, а кранекеравское произведение В -- В' х В' представляет собой диагональную матрицу. Таким образом, мы построили алгоритм двумерного л'лцэзчечного преобразования Фурье в той же форме, что и БПФ-алгоритм Винограда Это и дает способ построения двумерных БПФ-алгоритмов из одномерных алгоритмов.
Хороший способ организации вычисления двумеряого преобра. зования Фурье диктуется формулой У .- (С х С') (В х В') (А" х А') т, н иллюстрируется рнс. Б 3 Здесь предполагается, что данные записаны в виде двумерной таблицы Для умножения на (А' х х А')сначала наждый столбец входной двумерной таблицы умножается на матрицу А', а затем каждая строка полученной матрицы умножается яа АС Первая из этих операций не содержит умножений и преобразует входную (л'хл")-таблицу в таблицу рвз- Р .
3 3. Г а юз я '«ясина аэу ря г р эрю Фур мера (М (л') х л")); вторая операция также содержит только сложения я и преобразует данные в таблицу размера (М (л ) х М(л')). Далее происходит умножение каждого столбца на матрицу В' и затем умножение каждой строки на матрицу ВС Эта процедура содержит 2М (л') М (л') умножений. Другой способ реализации этого шага вычислений гостоит в предварительном вмчнслении и запоминании (М (л') х М (л'))-матриугы В = В" х ВС Тогда на этом «гаге потребуется тольио М (л') М (и ) умножений, но память для констант вычисления растет.
Наконец, вычисленная на втароч шаге (М (я') х М (л"))-матрица преобразуется в (л' х л")- матрацу умножением сначала каждого столбца на С', з затем каждой строки на С . Посчедний гпаг содержит только сложения. Полное число умножений в алгоритме разно М (л' х л'*) = М (л') М (л").
Формула для полного числа гложеннй выводится несколько сложнее, так как зависит от распределения числа сложений в составлиющих алгоритмах между нредсложениями и постсложениями, Чтобы упростить зту формулу и ее вывод(и даже уменьшить число необходиммх сложеннй), предположим, что можно менять порядок зт1 зз я Р в Раь т70 Гэ.
а. Вмстрне тюрэш мэ гояерэнэ эрюарэюэзн Я Ф й$) йхц — хдяйй пи*ййййй'Ц$8 8.3. Алгоритмы Винограда быстрого вычисления ирсобразованмя Фурье большой длины Г нюдовые методы построения двумерных БПФ-алгоритмов можно использовать, наоборот, для построения алгоритмов вычисления одномерного преобразования Фурье. В настоящем разделе мы возвращаемся к задаче вычисления одномерного преобразования Фурье и строим БПФ-алгоритм Винограда для больших длин преобразования (большой БПФ-алгоритм Винограда). Большой БПФ-алгоритм Винограда представляет собой метод эффективного вычисления дискретного преобразования Фурье, если ллина л преобразования распадается в яранэеедение взавмяо 2 ппаияпйяйййяй применения матриц С' и С'.
(Изменение порядка суммирования оправдано общим тождеством ~)Сгь ~~Сгз"Угш = ~Стог Х х дгСг ь Угг.) Тогда А (л' х л") = л'А (л') + М (л') А (л'). Теперь мы уже имеем деа способа вмчисления двумерного преобразования Фурье. Первый из них содержит М (л' Х л") = л'М (и') -1- л'М (л") умножений, на строится на основе люсюго одномерного БПФ- алгоритма, а второй содержит М (л' х л") == М (л') М (л") умножений, но в конструкции использукцся только БПФ-алгоритмы Винограда вдоль иаждого из измерений Например, реализация (1008х 1008)-преобразования Фурье для комплексного входа в первом случае требует 4 х 1008Х 1782 вешественнык умножений (см. Раэд.
8.3), а ва втором случае 2х х 1782' вещественммх умножегшй.(В случае вещественного входа во втором случае требуетсп вдвое мепыце веществеинык умножений, а в первом случае только 374 от уиаэаииого числа, так как после применения БПФ-алгоритма по строкам данные становятся комплексными.) В б торой способ, очевидно, лучше, ио для его реализаднн треуется создание временного массива памяти для запоиниания комплексных данных объема 2х 1782х 1782 (который в начале может содержать 2х1008 х1008 входных данных); дли первого спшоба необходима только временная одномерная память для запоминания 3584 слов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
