Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 23
Текст из файла (страница 23)
Алгаритн Рейдера †Бренне можно строить, исходя иа ураэ- ненай для алгоритма с прореживаннем по времене, но мы пре:<. почитаем <нталкиваться от уравнений для алгоритма с прорежи- ваннем пе частоте: Л вЂ” < Уи = ~ (о<+ о<е <э) ер", <-з <г — О, ..., л(2 — 1, Уме< = д< (э<--о<ч.„д)и'ммь. <-э Определим рабочий вектор в равенствами О, 1=0, (о< — о<е„гэ)<(2)э<п(уи(,'и)), 1=1, ..., л(2 — 1, и положим й" Я Я Я ЯЯЯ Я Я Я ЯИРФЯ 8 2 о ю Я о <г — < А„= д, н'пн Д =О, ..., л<2 — 1 <=э Так как <2 < Аны А, 2; озал, (ом П <-е <э "ам<а,2< ып (2дцл) <-е Я Я <2 — < — (о< — о<э„гг) и'иэ", «= Умножение на зту комплексную константу требует всею двух вещественных умножений н двух вещественнмх сложений.
Таких умвожевий на шагах 3, 4, ... алгоритм содержит соответственно л(4, л(8,,... Их можно ревлизовз ь с помощью специажной процедуры умножения. При агом в зависимости от выбранной реализации комплексного уиножения характеристики алгоритма будут даваться равенствами Мд (л) =- л ( — 7 -1- 2 1ой, л) Ф 12, А„(л) =- 3н ( — ! -1- 1ой, л) -1- 4 !Ээ Га. 4. Бнс р 4 э З в д схр пюгс яр Сра *зэ ия Фурь* 42 Агг рнги Ку — т ю со мээ к> эшяп !29 О 1= О а! 1("ь> л "!)/12ПС Р !СН 1= 1, ..., Ы2 — 1 !г-! 44 = ~ ! г! а = О, ..., Ыэ — ! ! э гг ! Уа 24 (,4-эгэ„гг)еп' а-О, ..., а)2 — ! ! — -э Уыл>--Агт! — '«-!.("4 — "с) 4=0, ...,,!2 — 1 Ряс. 4.В.
БПФ р в Р зд Гэ — ГО „„94 то велнчнны У,»ы н А„свнэаны равеяствамн Уыш = Аг-и Аг+(! о У >4). Твкнм образом, умноженне на комплексные константы ю' уха. лось заменить на умножения на мнимые константы (2! ып (2п()л) ! ', что уменьшает вьипслнтельную сложность. Необх димо,! одпюго, проследить, чтобы не произошло переполнение по длнйе слова потому, что когда л велико, а 1 мало, новые константы становятся весьма большнмн. Внратде форма ззгоритма показана на рнс. 4.6.
У>бждое из двух (л)2)сючечных дискретных преобразованнй Фурве можно в свою очередь разбить точно таким же образом. На каждом шаге алгоритма требуется (л>2) — 2 умножений комплексных чисел на мнимые, для чего в итоге используется и — 4 вещественных умножений. (Мы предпочлн избежать умножения на 1)2 прн г, равном л)4.) Нз каждом шаге алгоритма всего имеется 2п номплексных нлн 4л вещественных сложений.
Характеристики алгарнтма Рейлера †Бренне описываются рекуррентвымн уравненнямн Ма (л) = л — 4 )- 2М„(л!2), А„(л) = эл Р 2Аа (л)2) прн начальных условиях Ма (4) .= О, А„(4) = 16. Здесь не учтены имеющиеся не двух самых внутренних шагах умноження на (~!) и Щ). Вместе с другнмн формами БПФ.алгоритма Кули — Тычки на рнс. 4.5 приведены характеристики БПФ елгорнтма Рейдера— Бреннера. Отмешм, что полностью аптнмнзированпые БПФ.
алгоритмы по основанию 2 для малых длин содержат меньше сложений. Эта позволяет предложить гибридный алгоритм: раз. бивать преобразование Фурье пс алгорнтму Рейдера †Бренне дс тех пар, пока не достнгнем длнны 16, а затем переходить на полностью оптнмнзнронанный алгорнтм. Использование на самом внутреннем этапе рассматриваемого в равд. 4.6 16.точечного БПФ алгоритма Вннограда позволяет еще больше улучшить ! ! ! ! ! -! — ! ! ! — ! ! -1 ! ! ! — ! Для каждого нз г!(4 рассматриваемых значений индекса й такое матричное уравнение определяет четыре компоненты пресбразо.
ванна. Этот метод позволяет л.точечное преобразование Фурье заменять '!стыр»мя (л)4).точечными преобразования Фурье н пе. которымн дополнительными вычислениямн. Из выпнсаннога уран. нонна следует. что для каждого д имеется юлько трн различных комплексных умножения и 12 комплексных сложений Самый внутренннй шаг — 4-точечное преобразование Фурье — вообще не содержит умножений. Число сложений можно еще уменьшить. Для зтога перепишем последнне уравнения для й -.= О, ..., л)4 — ! в виде о ! о ~ о — ! о о ! о о ! о ! 0 ! О 1 О ! О 1 Π— ! 0 О ! О результаты. Характеристики гибридного алгоритма списываются теьгн же рекуррептнымн уравнениями, но с начальнымн условиями Ма (16) 20 А (!6) = 148. Очень популярны также БПФ-алгарнтмы Кули — Тычки по основанню 4.
Онн могут быть нспользаваны в случаях, когда длина преобрааовэння л равна степени 4, н получаются ее разло. женпем в вале 4.4 -' нлн 4" †' 4. Мы рассмотрим БПФ.алгоритм Кули †Тыч по основанию 4 с прореживанпем по времени. Уравнения юой формы БПФ можно получить простой подста. новкой л' = 4 и л' = л)4 в приведенные на рис. 4 1 общне уран. некиа БПФ.ачгоритма Кучи †Тью. Прк Д вЂ . 6, ..., п)4 — 1 соответственно имеем 141 4 1а 64 256 1024 4036 0 36 288 1 728 9 216 46 060 16 гщ 1 128 5 824 29 Иб 144 384 0 20 ЫВ 1 392 7 166 40 642 16 148 976 5 41М Ж 686 138 928 .а з а Ые Г . 4. Б ы Рын щ рнт ы Ин «Нстно н пиюарннса нни Фуиа Разложив исходную (4 х 4) ызтрицу в произведение двух, мм полу.
чили 8 сложений вместо 12. Это дает окончательную Форму Б ПФ. алгоритма Кули — Тычки по основанию 4. Характеристики алто. ритма описываются равенствами ' М,(и) = (374) л ((ой, п — 1) = (3/8) л (1о8, и — 2), А; (и) = 2п )ой, л = л 1ой, и Лля числа комплекснмк умножений и сложений соответственна. Если для вычисления комплскснмх умножений используется алгоритм с тремя вещественнымн умножениями н тремя веще- ственными сложениями, то «араитеристики описываются равен- ствами Ма(п) = (978) и(1ой,л — 2), Аа (л) = (2578) п1ой,л — (9)4) п.
Можно получить и лучшие результаты, если нложить в яро- грамму способность выловить все умножения на' (~1) и на (~!) или на нечетные степени элемента (1(у'2) (1 — !), посиольку они не требую трех вещественных умножений, и убрать их иэ алго- ритма. Тогда характеристики будут даваться равенствами 9 43 16 Ма (и) = — л (ой, и — — л + —, В 12 3 25 43 16 Аа(л) = — л1ой,л — — и+в 8 !2 3 Характеристики БПФ-алгоритма Кули — Тычки подытожены на рис.
4.7. Оснюнсэ н гор Пса т а сити нино н снсыила с * БПФ к щек с БПФ Книна Число Чи но Ч Чнснс и з асстз ниии уинаиснна к Н 7 на снонанна Рнс. 4.7. кирин Н жююрих БПФ-ан рн ион о ссиа н на 4. 4.3. Лнг рн Гги — Т с 6 иою пр сносна нн Фугм 4.8. Алгоритм Гуда — Томаса быстрого преобразования Фурье Алгоритм Гуда--Томаси с использованием простых делителей представляет собон БПФ.алгоритм второго типа. Концептуально он несколько сложнее алгоритма Кули †Тыч, но в вычислительном отношении несколько праще. Показанный на рис.
4.8 алгоритм Гуда †Тома представлнет собой другой способ отображения линейной последовательности иэ л = л'и" нелых чисел в (и' х л')-таблицу, преобразующего одномерное преобразование Фурье з двумерное преобразование Фурье. Лежащая носнове отображения идея сильно отличается от идеи алгоритма Кули— Тычки.
Теперь числа и' и л" должны быть нзаимно простыми, а основой отображения линейной последовательности в таблицу слунсит кнтайскан теорема аб остатках. Обращаясь к рис. 4.9, чы видим, как переупорядочсны входные данные. В двумерную таблицу они выписываются, начиная с верхнего левого угла, вдоль раснгиренной лнаговалиа Пссиольку число строк тзб.
лицы вззимно просто с числом ее столбгюв, расширенная диаго. иаль последовательно проходит через все элементы таблицы. После выполнения над этой таблицей двумерного преобразования Фурье компоненты преобразования оказываются записанными в двумерной таблице по иному правину, чем были записаны компоненты преобразуемого вектора. Способ упорядочивания входной и выходной таблиц будет описан нные.
Рн 4 В. БПФ. р с Гуда — Таама. !43 ил гг 44т Гл 4. Бн тр лгогнтм ае г» о ар!обре! зн» Фтр 4 Э. Лл рета Гга — То са б тржо прбабр юне Фтг В этих новых индексных обозначениях формула — ! уь= ~ммо, ! з ф 35Щ ф ЙП43 ф.г г! 4 (92П!)И эйЯ4Ф(б (~! Р . 4Л.ПЭ г г м» м лг Ггл — ума Построевие БПф.алгоритма Гуда — Томаса основано на китайской теореме об остатках для целых чисел. Входные индексы задаются вычетами по правилу !' = ! (пюд и'), ! = ! (тод л').
Это правило представляет собой отображение индекса ! иа расши.- ренную диагональ двумерной таблицы, злеыенты которой вану. мерованы парами индексов (!', !"). Согласно китайской теореме об остатках, существуют танис целые числа Лг' и У", что выпол. няешя равенство ! = Гй)"л" -!- !"Лг'л' (тад и), где Л"л' -)- Лмл" = !.
Выходные индексы определяются несхалько иначе. Пусть й' = ЛГ й (!под «'), й" .= ЛГ'й (тод л'). Эти равенства ыожно переписать в знвнвалентном виде й' ИЛ" тод л') й тод л'), й' = ((Лл тод л") й !под л"). Выходные индексы й вычисляются по правилу й л"й' -!- л'й" (тод и). Для проверки этого равенства выпишем! й = л" (77'й -4- ()гп') + л' (р('й + !З,л') (пюд л'л') = = й (л'Л' -4- и'Р(') (и!од л) = й.
преобразуется к виду †! '-! Уж» „,. = Е 7; мп л- .тг-» г!,.4 е нюо Вмполним умножения в понаэателе степени. Поскольку поря. док элемента м равен л'л", та члены с этим показателем прона. дают. Тогда выписанное выше преобразование индексов для зле. ментов входной и выходной таблиц дает — "-! Ч' мн"! .! ! ! Ф» ! ! !.Э.п, э! э ' †! -! — 7 7, йпе'г' э о! 4-, пег-б где (! = м" гж!' и Т = мл'!"'!'. Элементы У и Т явлвются про. стыни корнями из епнинцы степеней л' и л, задающими л'-точеч. нос преобразование Фурье и л"-точечное преобразование Фурье соответственио. Чтобы увидеть это, достаточно заметить, что З = (и"")"ы . Так как и' е-!'"!"' и У*л* = ! по модулю л', то б = е-гж'"Т Аналогичное утверждение справедлива и лля элемента т.
Уравнение теперь записано в форме двумерного (л' х л'). точечного пресбразования Фурье. Число умнонгений и число сложений равно примерно п (л' Ф л'). Преобразование Фурье по строкам и по столбцам, если соответствующан размермость задается составным числом, можно в свою очередь упростить, применяя алгоритм БПФ. Такин образом, если длина л преоб. разавання разлагается в произведение простых множителей лп то описанная форма БПФ-алгоритма ~ребует примерно л ш л, умножений и столько же слежений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
