Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 24
Текст из файла (страница 24)
Для вычисленип преобразования Фурье можно пользоваться как БПф.алгоритмом Кули — Тычки, так н БПф.алгоритмом Гуда — Томаса. Можно даже строить алгоритмы, содержащие БПФ-алгоритм Кули — Тычки и БПФ-алгоритм Гуда — Томаса одновременно. Например, используя БПФ-алгоритм Гуда †Точаса, можно ЗЗ-точечное преобразование фурье разбить на 7-точечное н 9-точечное; используя далее БПФ-алгоритм Кули— Тычки, 9гтчечное преобразование можно разбить на два 3-точечных преобразования. Вычисления при этом преобразуются в форму, аналогичную трехмерному (Зхйх7) преобразованию 4ж Ллчр ч Г Рк 44 Нт Гз. 4.
П тР 4 аз«Роша «Р оо РР 5Р ФГР И5 5 5 5 5 Р .4ПО.Н шрм с а ю р 4»44ПЮч»р армен Фрр Фурье. На рис. 4.10 показано несколько способов разбиения '. 1000 точечного преобразования Фурье на преобразования меньшего объема. Каждый из способов содержит 2.точечный модуль три раза н б-тачечнмй модуль грн раза. Но все процедуры существенно различны, так как малые модули нсоользуются в разной последовательности, Число умножений н сложений, чувствительность алгоритма к погрешностям вычислений и легкость реалнза. цнн алгоритлгз различны. 4.4. Алгоритм Герцеля Значение одной компоненты преобразования Фурье можно вычислить по правилу Горнера, дающему один нз способов вычисления многачлеиа о(х) = р ,з †' + о„,х"-4 + + о х -1- », а некоторой говне 0.
Правило Гарнера, записанное н виде «(0) =(...((Р„40+э„з)0+э )0+... ' оДБ+ре требует л — 1 сложеяий п и — 1 учножений э поле элемента 0. Если все различные степени элемента Б выРаслеиы заранее, то правило Горнера не дает ннкаиих преимуществ по «равнению с прямым вычислением. Преимущества правила Горнера состонт в том, что оно не требует предварительного вычисления и залами. нанна этих степеней. Если 0 = мь, то правило Горнера вычисляет й-ю компоненту преобразования Фурье посредством я — 1 комплексных умноже.
ний и и — 1 комплексных сложений. Более эффективным для этого вычислении является алгоритм Гернеля. Алгоритм Герцеля представляет собой процедуру вычисления дпскрецгого прсобрааоаання Фурье. Он позволяет уменыиить число необходимых умножений, ио па очень малый множитель. Он не принадлежит к алгоритмам БПФ, так каи его сложность по прежнему пропорциональна нй Алгоритм Гсрцеля полезен н тех случаях, когда требуется вычислить малое число компонент преобразования Фурье, — «ак правило, не более чем 1ой, л нэ л компонент. Так как БПФ алгоритыы вычисляют все ком. понепты преобрззовання, то в этих случапх приходится выбрасы.
вать ненужные компоненты. Для вычисления одной компоненты преобразования Фурье — 4 Уь = ~ м'"ог рассмотрим многачлен р (х) == (х — мр) (х — м-'). 4=4 Он представляет собой многочлен наименыпей степени с веще. огненными коэффициентами, дла которого элемент и-4 является корнем. Зго минимальный многочлеп элемента Ф' над полем вещественных чисел, н он ранен р(х) =х' — 2ом( — й) х-(-1, з Пусть р(х) = ~ о,х' 4-4 к запишем э (х) = О (х) 0 (х) + г (*). Многочлен.частное 44 (х) и многочлен-остаток г (х) могут быть найдены с помощью алгоритма деления многочлеиов.
Тогда вели. чина У» может быть вычислена по остатку согласно равенству Уь = о(м ) =-г(мь), таи каи по построению величина р (м") равна нулю. Большая часть работы приходится иа деление мнагочлеиов. Если коэффициенты многочлена о(х) являются иомплексным», то для его деления на многочлен р (х) требуется 2 (л — 2) вещественных умножений; если же коэффициенты многочлена р(х) являются вещественными, то требуется л — 2 вещественных умножений.
Аналогично, не. обходимое числа сложений а иомплексном случае равно 4 (л — 2), а а вещественном 2 (и — 2). 147 3» Б д а Л = 2 ю» — 4. 2 » д»» ммг» гь ж д« *. Р с. 4.14. Бдо».сд»в»»»юрмм Гари — 4 444 Г», Г Б Рп З Д» КРИН Г ПЗ»МЗ »ОМ» СУЗ 1»)осмс З ре д р а дю»а» Так как степень многачлеиа г (х) равна едннипе, то д»я вычисления г(м') требуегся только адно комплексное умаоженис и одно зомпленсиое сложение.
Таким образом, при комплексном входе для вычисления одной выходной «омпонеиты алгоритму Герпеля требуется 2л — 1 вмцествепных умножений и 4п — ! вещественных сложений. Блом-схема 'алгоритма Герделя показана на рис. 4 П. Эта схема имеет форму авторегресснонного фильтра. Это является следствием тпга, что схема деления многочленов имеет форму авторегрессноаного фильтра. После ввода многочлснз о (х) пень на рис. 4. П будет содержать остаток г (х) от деления многочлена о (х) на многочлсн р (х).
Частное 42(х) интереса не представляет и поэтому отбрасывается. 4.З. Б»с ««р сзз»юэ в» Оугы с южные З 4.5. Вычисление преобризовання Фурье с помощью свертнн Одним из мффехтивнык способов вычис.тения дискретнога «ре. образования Фурье У» = Е'ММО, -» являетси сведение я вычислению свертки. Это может показаться странным, тдя хая мы уже знаем, что хорошим методом вычисления свертки нвляется использование БПФ и теоремы о свертке.
И иа самом леле, возможно поэтому,многие годы рассматриваемые в данном рыделе методы привлекали мало внимания Сейчас, однако, стало понятна, что иногда выгодна вычислять преобразо. ванне Фурье сведением х еычнетению свергни, а иногда, иаобо. от, выгоднее вычислять свертку через преобразование Фурье. та еще удввительнее, иногда выгодно вычислить свертку через преобразование Фурье, реализуя пра этом преобразовав»в Фурье через алгорнты вычисления свертки, хотя и нз длине, отличной от исходной. Два различных способа перехода от преобразования Фурье к свертке дают чирп.алюритм Блюстейна и алгоритм Ревдера для простых чисел (см.
рис. 4.12). Алгоритм Блхстейна переводит и-точечное преобразование Фурье в и-точечную свертку н 2л дополнительных умножений. Алгоритм Рейдера переводит а. точечное преобразоваине Фурье в (а — 1).точечную свертку, но только для простых чисеч л. Алгоритм Блюстейна менее полезен, но проще в описании, тах что мы начнем с него. Он описывается равенством 1', = 2 — ' Е !)44-"'(!) — оог), где 2 равно ивалратиому корню из м. В этом варианте преобра. зоваиня Фурье производятся следующие вычисления: ' Е Бп-"м(Р-и ) = Е 2юо = Е мм 4-4 4-» 4=» Чирп.алюритм содержит л поточечных умножений ог на 2-", пнялическую свергну с Бо в КИО.фильтре с л отводами н следую щие за этим л потачечных умножений на 2-»'.
Поэтому полное число операций по.прежнему имеет порядок л', так что чнрпалгоритм асимптотичесии не эффективнее прямого вычисления преобразования Фурье. Однако в некоторых приложениях он доиусиает более простую апнарэтурную реализапню. Кроме того, 349 у» = Е ммо~ г-з й=б, ...,и — 1, у,=~~о г=е 1 до л — 1 равенство множества задает пеможно аа. 14в Г 4 н р зв а Р зр 'ат """ оуз прямое аычисленве свертки можмо заменить рассмотренными в гл.
Э алгоритмами быстрой свертки. Алгоритм Блюстейна содержит 2л умножений и свертку ллины л. Более предпочтителен следующий алгоритм — алто. ритм Рейдера, — так пан он не содержит 2н дополнительных умножений. Алгоритм Рейдера садернгнт толька векпторые опе. рации но переиндексации входных данных и аиклическую сверг. к)ц длина которой теперь уже равна л — 1.
Алгоритм Рейдера можно использовать для вычислении пре. образования Фурье в любом поле Г, если только длвна преобразо. ванна л является простым числом. Так нак л — простое число, ю можно воспользоваться структурой поля СГ (л) Лля переиадексацни компонент нхаднога вектора. Поле СЕ (и) не следует путать с пачем Р, в котором вычисляется преобразование Фурье. Выберем примитивный элемент к простого поля СР (л). Тогда каждое не лревосходящсе л пелое число можно однозвашо запн.
сать в виде степени злеьтентв и. Преобразование Фурье можно переписать, заменив индеисы г и й соответствующими степенями элемента и. Йндехсы )в Д принимают н пулевые значе. вия; зтн компоненты входного н выходного венгеров удобнее рассматривать отдельно. Тогда У,=о,+ ~м"оь й=1, ..., п=1. г-1 Пусть г (г) обозначает единственное для каждого 1 от целое число, такое что в поле СР(п) выполняетсн 'и) = г. Функция г (1) является отображением )1,2, ..., л — 1) на мможество (1, 2, ..., и — 1); она рестановну на множестве )1. 2, ..., л — 1).
Тогда 1'„ писать в следующем виде: ! ч и ~ ч- (ь~ ю! Так как г (1) задает перестановку, то можно положить 1 — г РБ и ) = л — 1 — г (г) и выбрать / н качестве индекса суммнроеа. вия; это дает ! У ~=от+ Дю м"' в" — '-1 г=! 150 Гз. 4. Б тр о р м э р пюго пр ара Фуры нли -о У'=ю-Г Е~ы 'оп о где У; = У„, п сг =- о„, 1 — соответственно переставлепные компоненты последовательностей входных н выкодных данных.
Теперь мы оолучяля уравнение для вычисления циклической свертки последовательностей (ог) н (м"1). Таким образам, иере. ставляя яндедсы входных н выходных данных, мы записали пре. образование Фурье в виде сверткн. Однако для того вида, а кото. ром этн формулы выписаны, необходимое числа операций для вычнслення свертки опять имеет порялок п'. В следующем раэ. деле мы скомбинкруем алгорнтм Рейдера для простой длины с алгоритмом Винограда для свертки н получим малый ВПФ. алгоритм Винограда.
Построим, нспользуя алгоритм Рейдера, двоичное пятвточеч. нос преобразование Фурье, для которого У, = ~ м'"оь й = О,... 4, 1-О где Ф = с-1'"14. Сначала перепнщем преобразование в анде о У,= х)о. Π— 1 У, = о, -1- Е и "о~ = 1'о + Е (Ф'о — 1) оо й = 1...., 4, н будем заниматься только членамя д,'(мы — 1) оо Элемент 2 в осле СЕ (5) является примнтнвным, к, следовательно, в атом поле выполняются равенства 2' = 1, 2' = 2, 2' — — 4, 2' = 3, 2о=!, 2'=3, 2'=4, 2'=-2. Таням образом, о Уо--Уо = 3, (мо' 1 — 1) ор 1=о В этой сумме летно узнается 4-точечная пнклнчесная свертна. Выделнм постоянные члены и апределнм фильтр Рейдера, задавая его мяогочленом й (к) кэд полем комплексных чисел, где й (х) =: (м' — Ц» Ф (м' — 1) к' -1- (ы' — 1) к -1- (м — !) (с коэффициентами 51 = оР' — 1).
Вход и выход фильтра опксы. ваются многочленамн, коэффнцяентм которых раппы оерестав- 45 В чоси и рмвр*э ы Фур ом м р ы 1 1 оо У У, У, У, !' 1 1 1 м мо 1 1 ! м' м м мо м' м' оо мо и' о Отсела получаем у, —.- о, ф о, -1. с, .1. о, ф о, н ~''Р' ' ' 'Г1 ПРавило перестановки алгорятма Рейдера прнвадкт это равенство к эквивалентному равенству в котором легко распознать матрнчную форму ззписн цнкляче. ской свертки ленным компонентам векторов т н Ч.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
