Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 43
Текст из файла (страница 43)
Глава 8 БЫСТРЫЕ АЛГОРИТМЫ МНОГОМЕРНЫХ ПРЕОБРАЗОВАНИЙ В предыдущих глазах были рагсмотрены способы разбиения задачи вычисления прсобрзаовання Фурье па подзадачи и спо. сабы преобразовании алгоритмов свертки з алгоритмы вычлсле. пня преобразования Фурье. Закачу вычислении многомерного преобразования Фурье также можно разбить на подзадачи и использовать алгоритмы вычисления многомерных сверток Лля вы«нслення многомерных преобразований Фурье. В ленном случае зтн возможности лаже богаче, чем а одномерном случае Мы рассмотрим многие вз ннх Алгоритмы многомерных преобразований Фурье рассматриваются иа простейшем примере двумерных преобразоыний Фурье Методы и фориулы, полу генные хля двумерного преобразования Фчрье, переносятся на произвольный многомерный случай непа средственно Многомерные преобразования Фурье возникают естественно в тек зала~ах цифровой обработки сигналов, которые по существу многомерны.
Но ои» возпзиают и искусственным путем как способ вычисления одномерного преобразования Фурье В данной главе изучаются зги методы н тем саиым Лаются практические способы построения алгоритмов одномерного преобразования Фурье больших длин из рассмотренных в гл 4 малмх алгоритмов преобразовав»я Фурье. 8.!. Алгоритмы Кули — Тычки по малому основанию Дл» вычислеаия двумерного преобразования фурье можно использовать ВПФ.алгоритм Кули — Тычки, применяя его сна.
чала к каждой строке, а потом к каждому столбцу. Это обосновы. вается простой расстзнопиой сйобои в уравнениях, определяющих лвумерное преобразование фурье. Обозначим через т двумерную тзблнцУ с злементамн ан, г-, 4" = О, , л' — ), (" = О, и" — (, из поля А Двумериое преобразование Фур~е тзблншэ ч 9 азг нос иоэо ю дэа Одэо эр а Д у ерааа Л ос оаозаю мопре Д умер аа Оао «раа У„,: ~ 2' мг юггоьг, г-а Г ЗЭО Га Э.
Б Г ююз г ю Г Эмба Ш определяется как двумерная таблица У с элементами пз поля Р, вычисляемыми по формулам '-г Ум . =- ~ ~ мг'.р" о, ,, «-ю г"-э где м — первообразный корень степени л' из единипы в поле Р, а р — первообразиый корень степени я из единицы в поле Р', при п' п" обычна полагают ю = р. Ясно, что Гю-< Уэ. „. = ~ югм~ у„рг"ь ос, с~ = ,г"ь.
( У „, Гмоп Отсюла видна, что двумерное преобразование Фурье можно вы. числять, либо вычисляя снзчала однонерные преобрааавааия по столбцам и вслед эа этим одномериыс преобразованяя па строкан, либо сначала па строкам, а вслед за этим па столбпам. Любые из БПФ.алгоритмов прнгодиы и для строк и для столбцов, и даже не нужно, чтобы они совпадали. В нашем распоряжении имеется много хороших БПФ.алгорвтмов, н любой из них можно выбрать, чтобы уменьшить число необхолимых учножевий и число необхо.
днммх сложений. Прн большик объемах таблиц помимо числа сложений н умно. жений возникает задача управления данными (1024х!024).таб. лица нал полем вещественных чисел содержит более одного мил. лиона чисел, и вдвое больше над полем комплексных чисел. Пргь цессор может запоминать большую часть таблицы в глобальной памяти, выбирая только часть данных в локальную память. Обмен данными между глобальной н локальной памятью является не менее важным моментом, чем число умножений и число сложений. Мы рассмотрим простейшую модель меканизма обмена дан. ными, в которой данные в глобальную память записываются по строкам н считываются в локальную память по стропам Тогда процесс вычисления двумерного преобразования Фурье сводится к одномерному преобразованию Фурье каждой стрпк», транспо. ниронанию таблицы и повторному применению одночернога пре.
образования Фурье к каждой новой строке Если окон гательный результат должен быть записан в глобальной намети в виде истин. ных строк преобразования, то нужна еще раз выполнять гранспа. ниравание. Быстрые алгоритмы трвнспонирования будут рас. сматрены в гл. 1О. Для того, чтобы избежать операции транспонирования, по. смотрим более внимательно иа используечые в алгоритме Кули— Тычки правила разбиения н применим их и построению много. Р с.
ад. Н р» рор мна. мерных алгоритмов БПФ. В многомерных алгоритмах будем де. пать разбиения не по с~рокам н столбцам, а прямо разбивая двумерную таблицу. Различие этих способов разбненя» показана на рис й.! В частности, двумерное разбиение по основанию 2 раз. бивает (пил) таблицу на четыре Ип)2) х(п(2)гтабггипы, а лвумер. нос разбиение по основанию 4 разбивает (яхп).таблицу на шест.
надцать ((л)4)х(л)4)).таблиц. Последнее разбиение, в частноств, привлекательно не только тем, что преобразует данные к малым объемам, на также и тем, что позволяет уменьшить число необ. «одимых умножений и сложений. Рассмотрим задачу вычисления двумерного (пхлгточечного преобразования Фурье 232 Гл 3. Бмстз ааюр мн и ериах Прюав ежл лх 263 где а = л'л" Отметим, чю мы специально убралн штрихаванныс обозначения индексов, чтобы воспользоваться разбиением Кули— Тычки Теперь л' и л" †.размеры прнмоугольной таблицы Напомним приведенну!о на рис. 4.! формулу разбиения Кули— Тычки: У, „,.
2', лг» мг! 2' .)!"ла, г-е ; -е Применим эту формулу к двумерному преобразованию дважды— один раз н строчнмм индексам. а другой раз к столбцовым индексам. Тагла. меняя парядои суммирования, можно записать ".Г 1.= = 1 Е й"'бхг' ~ю" "' Е Х у"!"';. с с;~.
Теперь мы получили запись преобразования в виде двумерного (л" х и")-точечного преобразования для каждых !' и !О за катармм следует покочпонентное умножение, а за иим (л' хл')-точечное двумерное преобразование Фурье для кажлых й' и 1" )(ля пас~роения дзумернпго алгоритма БПФ с разбиением по времени по основанию 2 выберем л' — 2 и л" = и)2 Тогда уран. пения в матричном виде для й =- О, ..., л)2 — 1 и 1 — — О, л)2 — 1 даются равенствам г -! «г-! гл гпа а' и лм,,г Е Е г=е 1-о Е Е г=о г=о !г — ! 11 — \ Е Х 1=0 г-Е гг-! ! — ! "Х Е г=л 1-.л и гг, г г1 ' !.
11 га гй "М.г1«! !'л,щ 11 !Лг- П !т гг ! ! — 1 — 1 !а Мал "г!.!.! гг-1-! — 1 †! ! Зтот БПФ.алгоритм разбивает таблицу входных данных на четыре екс в. таблицы в соответствии с четнастью илн нечетносгью обо д о . Выходнаи таблица также разбивается на четыре таблицы, хотя и па другому правилу, определяемому принадлежностью строк и столбцов к первой или второй половине.
Вычисления теперь свелись к четырем двумерным ((и)2) х (л)2))-точечным преоб. разованиям Фурье н (3)4) л умножениям на степени элемента м. Мы здесь не учитываем (114) л' тривиальных умножений, которые формируются в один блок и легка из алгорнтлга выбрасываются Оставшаяся часть тривиальных умножений мала и вхсднт в пол. аое число (3)4) М )множений. Пусть л равно сгеневи двойки и М (лХи) обоаначает число умножений в поле Р, всобкалвмых для вычисления двумерного (и х л) точечного преобразования Фурье описанным алгоритмом Тогда мы получаем следующую рекурсию: М(и хи) — 4М( — х — )+ — „л*. 3 Решение этого реиуррентнога ураваенвя дается равенством М (» х л) —. — и' (1ой, я — С), 3 где константа С определнется числам умаожений в самом внутрен- нем шаге.
В частности, можно отталкиваться от (2 х 2).преобра- зование Фурье, ие содержащего умножений, так что М (2х 2) =- О, нли от (4Х4)-преобразовании Фурье, также не содержащего умножений, так что М (4х4) = О. Тогда М(л х л) —.— л'()ай,л- 1) 3 или Ы (л х л) =- — „л' (1ой, л — 2). Возможна и дальней!псе уменьшение числа умножений, но струк. тура алгоритма ари этом усложняется. Полученные формулы интересна сравнить с числом М (лхл) = нг )ай и умножений в пале Р, необходимым в аз!мерном алгорвтме, осно- ванном на использовании БПФ-алгоритма Кули — Тьюки по осно- ванию 2 по столбцам и па строкам. Некоторое уменьшение числа необходимых умножений як лается прия~ным свойством рассмгпренного двумерного алгоритма.
11о ивяного более важной является используемая в нем форма записи входных данных, так кек она уменьшает необходимое числа обменов данными между глобальной и локальной памятью процессора. Входная таблица считывается в локальную намять по две строки ад»овремешю Обьеи локальной ланята должен быть достаточен для запоминаяия двух строк. Вдолл каждой пары строк вычисля!атея все двумерные (2х 2)-греобразовання. Згот процесс для даянай таблнга« яовторяется !ай, и раз В каж- дой итерации процесс спаривания двух строк управляетсн алггь рнтыом адресного тасавання Кули †Тыч; формирование (2х 2).
таблиц в пределах двух спаренвых строк также управляется алга. ритмом адресного тасоеания Кули †Тыч. Так как входная таблица содержит и строк, н так как онв трансфармнруется всего )ой, а раз, та в общей слажносп! мы получием л!ай, л пе- реносов с~рок нз глобал~ной памяти в локальную и тзное же число обратных переносов. т;, т т т т — т т;, -т т -т т -т т 2.
-"ьн — -т — т рн 224 Гл а Бм трме а р и р» риараинм за Чтобы построить двумерный БПФ-алгоритм по основанию 4 положим л' =- 4 и и" —.- и(4. Это разобьет исходную двумерную таблицу на 1Б подтаблиц. Вычисления можно записать в виде следующего матричного ураанени»: 2.2. Г а, шгорзтш чр саз з я Здесь (1б х! Б)-магри на, иа которую выполняется умножение, представлена в виде крояекеропского произведения двух (4х4)- матриц с элементами Ш1 и ~11 1б/!б нз стоящих в правой часта равенствз членов умножаются на степени элемента м. Небальша» часть нз них представляет собой тривиальные умножения, но, чтобы структура оставалась простой и удобной для расчетов, мы нх выбрасывать не будем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
