Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 49
Текст из файла (страница 49)
Так нак х — »" делит круговой многочлен Ц (к), та второе нз Г'"' авенств не нарушится, если первое вычислять по модулю О (х). о позволяет переписать равенства следуюшнм образом; — ! Уцм и (к) =. ю' иг. (х)»ь"' (пюб О (х)), г.-е (а,),=-Й„„А 1)ньен(.тИ= Но теперь, согласна второму равенству, элемент »ь' сразннм с х. Поэтому замена ю" на л в первом равенстве не нрнведет к изменению окончательного результата Это нозвалпет еше рзз перепнсать исходные равенства з виде — ! У;мь.п (х) —..
~', о,. (х) к" (шоб Я (х)), г=ь Уьс пм'и = Й ь' !Упььч (хВ '— ч' »" 'К'. Нь 'и Теперь для завершения доказателытва теоремы сютается уток. нить абозначевия н перенисать равенства в окончательном вндед П Эту теореыу надо прнменнть к трем разлнчным случаям, саатветстзуюшим равенству числа точек па каждой размерности хву. мерного преобразования простому числу, степени нечетного про.
блад (3 ч- З) 2»с д Эв 2 л м ду ю 2 'т *н нр брв э пел мщу (3!2) 2 р обр * ° Од о д умер пр брэо пюр мер 2 'х2 "' н «.р* 224 Г». З Бс р * влшритн юг м ри ребр ю а Про»бр во и До ппюль м пр браво нв Фурь с ння Про Р и чиж рюбрвво- р-1- ) прюбр ювв- Р'-1-и' — б».1- 4 нисло р вани во дулю на' длвнм Р (» -' ))/ .'- П сн щ рига ю прюурве . р'.).
р р брю - 2»'-1- Р' — б»'-1. прост в ние о нулю овина" д.внм р' + р».1- б ч с р („»' ))/(„» 1) Р- че пр обрю . р .1- ) р бравен»- в чме паулю вма л и Р („»' 1)/( » 1) зв«модулю (л» вЂ” ))!( — П Рм. З2). Пщ р*грв и, юыуемм БПФ- ритм л Нуюбпу еров К пелла. стого числа и степени двух. Рассмотрим последовательно все три случая; результаты анализа подытожены на рис. 8.21.
г/исло г точек б каждом памир»мои проема. При простом числе точек теоремой можно воспользоваться для того, чтобы свести вы. численне двумерною (р х р)-преобразования Фурье к р , 1 различным одномерным преобразованиям Фурье. В более общем случае метод позволяет свести дг-мерное, р-точечное по каждому из. мерению преобразование Фурье к (ри — !)/(р — 1) рвэличнмм одномерным р-точечным преобразованиям Фурье. Это можно срзв.
вить с прямым методом вычисления д)-мерного р.точечною па иаждому измерению преобразования фурье, содержащим Д»ри — ' раз. личных олномерных р-точечных преобразований Фурье. Для простых р имеет место разложение х» — 1 =(к — 1) (к — '+ и» вЂ” '+... +э+ 1). * Э рч Ну блу р — Кюдлщ римму Рис З22. П рм в ов в А юри Нус б умре — К нл Каждое ненулевое й" является «орн р ру ем вта ого к гавота многа. члена. Согласно теореме 8.7.1, для вычисления компонент — 1 н Й' = 1,,, Р надо вычислить одно полип об азаваний номиальное преобразование и р одномернык прео р Ф . Ч бы завершить вычисление, надо найти еще «ом.
урье длины р. то Б «и эз бзаэ эн Фур га = 1, 2 3 4 5 7 8 16 2 3 4 б 9 8 П 18 о 2 0 5 8 2 10 16 2 6 8 17 36 26 44 74 2 2 5 В 4 В 16 4 2 !5 34 ю 28 32 а»т„й г1 1 11 а ! и( () ' )(о) 296 Гл.8.5 р багор и раз 9 бээ а Норм» БПФ Б р д 8 х БПФ Бинмгаа Д Чэгм у зй' Ч мб уи эй' Ебм " Га' С О Зиай Шщее " ГЮ О Еаай' шиа них ' л а бэ га Рзс. 8.23. Х Р* .'р сгч» з псрм» зм БПФ ю панеиты Уз, ° с й, рааиыы кулю.
Но сии получаются сразу «ак результат еще одного преобразования Фурье: — г — 1 Уа.э = ~~ Фгм 2; осм, й'=-О,..., р — !. 1' '7 Таким образом, всего получаем р + ! одномерных преобразоааинй Фурье длины р. На рис.8.22 приведена блои-схема алгоритма для простого р. На последнем шаге осуществляется обратная перестановка компонент, для чего испольэушся обращение по модулю р. Есть епге одно упрощение У большинства преобразований Фурье неиогорые коэффициенты отсутствуют, так что соответсгауюгцие «реобразаваяия можно упростить с помощью выкапывания — выбрасывая те входные компоненты, которые заведомо равны нулю, и ге выходные иомпонеиты, вычислять которые иет иа.
добиости. Как видно аз блок-схемы иа рис. 8.22, а основном шаге алгоритма, связанном с вычислеиием р.точечиых преобразований Фурье векторов длины р — ), коэффициент старшего парилка всегда рааса аулю и нужны только р — ! выходных компонент, а младший каэффициемт можно отбросить. Такие яыиолотые БПФ-алгоритмы и их вычислительные характеристики представлеиы иа рис. 8.28. 87, П,топшм» й жбээ™ Нуыщг"'Г' мммш 297 В качестве примера БПФ-алгоритма Нуссбаумера — Квеиделла посгроим пример (ЗХ3)-БПФ-алгоритма.
Первый фрагмеит еыписыпвегся проще всего. Теперь заметим, что круговой мяогавлен равен !4 (х) = х' + х -(- 4- ! =- ( ' — !))(х — !] и о, (х) = о,,х' -! и, х + о ь; (х) = пь,х* -. 'с,ак -)- о, „ «,(х) = пьвх' Ф пьэх + па, Вычисление полииомиальаого преобразования по модулю х' -)- -)- х -(- ! приводит к миогочленам первой степени Хотя приведе- ние по модулю 4)(х) можно и отложить, мы сразу заменим исход- ные многочлеиы их вычетами по модулю !)(х)! (х) =- (о, — оэа)хб (», — оэ,) о (х) ..—.
(оьт — ота) х .)- (о а — бы), о, (Н вЂ” — (оь, — с,э) х .1 (ощ, — с„). Пааииомаальное преобразование равно Бга равенство можно переписать в аиде Следующий шаг состоит в вычислении результатов выколотых БПФ-алгоритмов. Вместо полного преобразования Фурье вида »ж г. к а. 8»сж шг ре и„га заэ г;2 й с а !с е) (гщ Д раГаа ~1 2 „г',,) — ! ,гь У. мгча, г =с г"-т 2 =О,...,(Р— 1, 1=0, „р — 1. '(р,1 ~~ асс )а а о а соа| а з (г;, й;г;, а о, '(г;,, ы Х г'=О,... Р— ! г=й, Р— ! н пусть Уь ~ = Уел,. Тогда Т; миа У угар, г'=г =т а' = О, ..., р* — 1, ! = О, ..., р — 1. 2 й а нужны толька ныкалатме преобразование Фурье при й = О, 1, 2 Саед»а»я их вместе, получаем Теперь нала выполнить обратную перестанов зку компонемтг Наконец, саб прая аместе все фрагменты, получаем окончательную форму алгоритма, показанную на рнс, 8.24.
Число тачек ла ас ла осям расла сам»гни»растога нечем»ага ~исаа. Для описания техники построения алгоритма достаточно рассмо. треть случай, когда число точек по каждой аси двумерного преабрв. зове»»я равна квадрату нечетного простого числа. По суп!естзу техника остается той же, что и з первом случае, несколько усложняясь за счет того, что сначала надо отобрать индексы, иде ф .
ру щне подлекгащне отдельной обработке компоненты. В этом отношении очень полезной оказывается многочленна» символика. р р, так как единственными делителями р' янляются 1, р н р', то, согласна теорече 5.5.3, многачлеи х"' — 1 разлагается по правилу х ' — 1 =-(х — !)(х'-' + ле†' + ... + х -(- 1)(х' " " + -»4-...
+" !) =Е,(.) Е,() фм() на круговые ынагачлеяы. Индексы й разбиваются иа три подмножества, соответствующие трен множествам соприжеиных элементов, на которые корни из единицы, м", разделяются круговымн понент, »н е многочленами. Воспользуемс» теоремой 8.7.1 для об б ра отки ком, »ндексы котарык входят в множество сопряженных эле. З т П рост З ааг рати Нус а у рз — Каюк и е ментов, соответствующее многочлеиу г)р. (х). Это потребует выполне. иия одного палиномиального преобразования р* членов по модулю Ом (х) и р' выколотмх рита. чечиых преобразований Фурье.
Для завершения этога фрагмента вмчислеиий надо найти компоненпа Уа, ь- с индекс»- чн й", кратаыми р. Зтн компоненты задаются равенствами Внутреннюю сумму можно трансформировать в р-точечнос преобразование Фурье Обозначим через у = мг корень степени р нз е»»иицы; пусть ор. ° = да о . ° .нр г=а Теперь поменяем порядок сумма. рова»»я н опять применим теорему 8.7.1. Для этого нам потребуется еще олно полинамиальное преобразование р членов на модулю йр (к) и еще р выколотых рмточечных преобразований Фурье. Остающееся при этом зо! Рзл с.ма]а ! о а Р 2 Р ПР д н ююумясдлуммйю р»н Задача Эбе Г .
В. Бн рп л! Рптнн пню юран р бр й двумерное (р х р)-преобразованне Фурье можш быть вычислена кан к ранее. В общей слажностн алгоритм содержит ра + р одномерных рюточечных преобразований Фурье н р -1- 1 одномерных р-точеч. ных преобразований Фурье. За исключением одного р-точечного преобразования зсе преобраэовання Фурье яаляются выколотммя.
' Число точек по осям рдело сшепеяп дврл. Хотя нонструкцня длн случая, когда числа то гек по осям двумерного преобразования ранна степенн двух, по сущестау совпадает с апнсанной выше, онат все-такн отличается настолько, что заслуживает отдельного рассмотрения.
Так как все нечетнме меньшие чем 2 целые числа взаимно яростм с 2, та к компонентам с этими индексами опять применима теоремз 8.7.1 Компоненты Ра с. лля нечетных й' п й" =- О, ..., я — 1 вычисляются применением п-точечнога палнномяального преобразования па модулю (л"и + !] и я одномерных п.точечных преобразований Фурье арн п = 2 . В данном случае полнномкэльнае преобразанание может быть.органнэоэаао в анде ВПФ-алгорнтма Кули †Тыч па основанию 2. Тогда числа сложений будет пропорционально и 1об, я. Все преобразования фурье будут выколотыми с равныма нулю входными нампонен-, тами с четнымн индексами.
Мы опнсали вычисление одной половины компонент длн которой й' печетно н й" = О, ..., я — 1. Теперь поменяем ролямн й' н й' я вычнслнм оставшиеся невычнсленнммн компоненты Ра, а. с нечетными й" к четнымн й'. Для этого нам понадобится еще одно полиномнальное преобразонвнне н еще п)2 одномерных преобразований Фурье. Наконец, остается зычно.чнть компоненты Р» а., оба индекса которых четны. На оня образуют (2 †' х 2 ')-точечное преобрнзованне Фурье, вычисление которого можно организовать по той же схеме, что н нычнсленне (2 х 2 )-точечного преобразования Фурье. ал ор и рс брасоююя Фурье о Рж и с б л .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
