Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 48
Текст из файла (страница 48)
Пересгановочный алгоритм Нуссбаумера — Квенделла представляет собой алгоритм многомерного быстрого преобразования Фурье. Он строится сведением многомерного преобразования к вычислению некоторого количества одномерных преобразований фурье, что и отличает его от рассмогреяных в раэд. 8.6 алгоритмов разложения, в котормх многомерное преобразование Фурье свалится к вычислению нескольиих многомерных сверток. БПФ-алгоритм Нуссбаумера — Квенделла имеет лучшие харзнтернсгики, но применим только тогда, когда мноюмерное прюбразование имеет Одинаковую длину по всем измерениям или когда все ллнны имеют общий множитель, так что ножно применить китайскую теорему об остатках.
В настоящем разделе рассматривается БПФ- алюритм Нуссбаумера — Квенлелла; характеристики этого алгоритма для двумернопг случая приведены на рис. 8.18, а дл» трек- мерного случая — на рис. 8.19. Алгоритм Нуссбаумера — Квенделла является алюритмом вычисления мноюмерного преобразования Фурье в случае, когда число тачек во всех намерениях равно одному и тому же числу л, которое либо просто, либо равно степени простого числа.
Конструкции различны для трех случаев: л — простое число; п равно степени нечетного простого числа; л равно степени двойки, л = = 2". Гнеэдовод метод позволяет из этик алгоритмов строить бочьшие многомерные преобразования точно таким же образом, как зго делается в случае одномерного преобразования фурье, Например, для построения (63к63)-преобразования Фурье сначала оно отображается в четырехмерное ((ук9) к (7х9))-преобразование, «оторое затем рассматривается как К7х7) к (9НО))- преобразование, для вмчисления «оторого используется гнездовой метод сочетания (7х 7)-алгоритма с (9 к 9)-алгоритмом. Это приводит к 49-кратному применению двумерного (9х9)-~реобразовання Фурье к 49 полтаблицам ланнмх, за которым следует 81-нратное применение двумерного (7ку)-преобразования фурье к 81 подтаблицам данных. Все алгоритмы могут быть приеедеим а оган.
дартную форму в виде матрицы предсложений при условии, что наждая нз (7к7)-подтаблиц сформирована как 49-компонентный вектор н кажлая нэ (9х 9)-подтаблнц сформирована как 81-компонентный вектор. (Все описанные манипуляция с вхож!од (63К63)- таблицей относятся только к индексам. Он» не солержат арифметических вычисленнб и не требуют ннкакоб физической перестановки данных.) Далее, так же на к н для одномерного случая, можво использовать теорему о кронекеровском произведении матриц ддя приведения вычислений к стандартному виду. выделяя все пред- 48 ух Рэс.
618 Хээ 9 «э БНФ.эгюэ Нт б 7 рэ — К з л . 3 О 24 27 26 162 64 0 384 166 1% ! 686 457 456 6 767 %2 224 4 %2 9% 962 10 383 4992 3808 51 960 Р .8.19.Хэээ р» р. р» БПФ. р %Нгсбг à — Кы- сложения перед всеми умножениями н все умножения перед всеми постсложениями Такай гнеэловай метод построения алюритма вычисления (л'л" х л'л")-преобразования Фурье содержит М (л'л" х л'и") = М (л' х л*) М (л" к л") умножений.
Чнсло тривиальных умножений описывается равен. ством такого же типа, число сложений в алюритме равно А (и'л" х л'л') = (л') А (л' х л') ! М (л" х л") А (о' х л') Вывод этих формул полностью совпадает с рассужденияыи, про. ведеными в случае одномерного преобразования Фурье. Характеристики гнездовых БПФ-алгоритмов Нуссбаумера — Квеиделла приведены на рис. 8.20. 10ь эт 2К2 Зхз 4х4 5хб тхт зк з 9Х9 1бк 16 2к 2х 2 Зхзхз 4х4хЯ 5хбх5 7х 7Х 7 знака 9Х ОХ 9 16Х!бх 16 4 9 16 31 % 64 Ю5 394 о 8 0 30 64 24 104 216 8 Зб 64 22! 635 408 7% 2264 0 0 89 0 1 20 1.31 0.375 1.28 0 84 9.00 О.
96 0.00 1 24 ! ЗЗ 0.4! 1 32 О. 93 2 4 8. 84 12 96 6.37 9% 8% ЗО 60 бс 13 5 19.7 24 14 2 12 9 290 Гл. В. Б Гме ююр ю м«р зрюбрзз Е Т Р, 8.20. Хау «т рнстнке ор х г юдо нх БПШ гпнш, Изучаемые в настоящем разделе алгоритмы строятся сведением двумерного (р х р)-преобразования Фурье и вычислению (о + !) одномерных р-точечных преобразований фурье для случая, когда число р простое. Для иллюстрации структуры, с которой мы будем работать, рассмотрим пример двумерного (ЗхЗ)-преобразования Фурье. Если записать входную и выходную (ЗхЗ)-таблицы по столбцам в виде векторов с 9 иомпонентами, то рассматриваемое (3 х 3)-преобраВование запишется в виде г где разделение на подматрипы сделано для того, чтобы выявить структуру кранекеровского нроиэведення. Кратка зто равенство записывается в виде У = %ч, где ч и У обозначают выписанные выше «хадной и выходной векторы соответственно, а элементы матрицы % равны степеням элемента Ф.
Нашей целью являшся по- !О 12 12 15 15 21 21 ЗО 30 35 35 46 48 63 Я 80 80 120 120 168 168 240 240 420 420 504 504 840 840 1008 !008 2520 2520 144 273 555 1 116 2 015 2 73Б 6 825 9 424 17 Шб 37 440 84 816 290 160 436 809 1 160 640 2 074 ВОО 13 Б4ОЮО 126 278 584 1 112 2 014 З ШВ 6 824 9 336 17 816 37 400 М 728 290 144 436?80 1 160 690 2 074 7!2 13 540 ?Ш 1 !62 2 ВЮ 7 499 13 356 30 240 29 592 102 460 123 784 276 696 Б58 584 13444М 5 765 760 В !76 792 24 738 ЯО 40 133 656 298 48! 660 0 89 !.24 1.32 1 24 1,64 1.
!5 1. 72 КББ 1 24 132 1. 47 1,65 1 ?2 1. 64 2. 04 2.13 8 ОО 12 84 16 96 14 84 24 90 Ш,84 25 Щ 19 34 19 21 23 33 23 34 32. Ш 32.19 35.06 39. 50 4?ЯО 8.7, пер зна а *з н ну О у г — к еззюлз строение разложенн» % = СВА, где А и С представляют собой соответственно матрицы предсложений и постслажений, а матрица В задает набор одномерных преобразований Фурье Б данном примере матрица В имеет внл где не ап е незаполвенным блокам соответствуют нулевые (3 х 3)-матрицы. Разложение % = СВА замечательно похоже на запись малого БПФ.алгоритма Вииагрзла Сейчас, олнако, мы находимся на е щенко ином уровне: стоящая в центре разложения блочно.
диагональная матрица представляет собой пакет одномерных преобразований Фурье, а не пакет умножений. Коль скоро такое разложение уже получено, двумерное (3 х 3)-преобразование Фурье вычисляется последовательным выполнением предсложений, зздавземых матрицей А, четырехкратным обращением к З.точечному одномерному БПФ и выполнением постсложеинй, задаваемык матрицей С. Ка» мм увидим позже, для некоторых одномернмх преобразований Фурье надо вычислять не все члены; этз обсуждаемая юзльше процедура названа емкоэотымн БПФ-алгоритмами и позволяет еше немного умеиыпить вычислителю!ую нагрузку. Одномерное преобразование Фурье можно трактовать как процесс вычисления значений миогачлеиа о (х) а точках юэ: У, = о (ю'), й =- О, ..., и — 1, где о(х) = ~ о,хд г-з Бта же трактовиа иримеинма и к двумерному преобразованию Фурье, причем более плодотворным оиазалось использование та.
като описани» талька вдоль одного из измерений двумерного преобразования. Запишем (л х п)-таблицу в виде вектора длины л, компонентамн которого являются многочлены — 1 о!. (х)=- ~ ог.!.х', !'=О,..., л — 1. ! е язя Гл. З. Н с р р тьр * рюарьюзь Е Определим одномерное преобразование Фурье вектора многочле. нов равенствамн — ! 1'» (х) =- Е»г юог. (х), й' .= О,..., л — 1. г"=с Тогда двумерное преобразование Фурье эапншется в анде й' = О, ..., л — 1, Уьс ь = Л ь' !Уь (х)! = Уь' (ю ) й =.О,...,л — 1. В этом определения осн явумерного преобраэовання Фурье не- равноправны и играют разную роль.
Теперь у нас уже все готово длн тога, чтобы, используя некоторую разумную технику перестановок, начать переход ат преобразования Фурье к палнномнальному вреобразованию. Пусть г обозначает некоторое положительное целое число, взаимна простое с л. Пусть й* = ((йг)), для некаторога й нз множества (О, ..., л — 1). Это задает неявный способ перебора всех зна- чений индекс» й', так как в снлу взаимной простота г я л, когда й пробегает все значения ат О до л — 1, число й" также пробегает все значения от О ло л — 1.
Тогда, тек как порядом элемента» равен л, »ь = »"Л н двв предыдущне равенства можно для любога г, вза- имно простого с л, нерепксать в виде — 1 Уиь,п (к) = ~', »смою (х), г.=ь й' = О, ..., и — 1, Уь.пь.я=В. ь (У!гьюг(х)1 Если й' само взаимна просто с л, то можно палажнть г равным й' н тогда второе равенство прнвнмает внд й = О, ..., л — 1. "(ун"'и( ))' нод( ' ) =1 Каждая компонента выходной таблицы, первый нндекс которой взаимно прост с л, может быть запнсана таким образом. Эевершнв на этом вводную меть, переходим к построению полиномиальвого преобразовання. Следуюгцзя теорема представляет собой скачок прямо к окончательному резулыату.
Читая эту теорему, необходима иметь в виду, что все те й', которые относятся и одному н тому же круговому многочлену, требуют одних н тех же вмчнсленнй, что один и тот же индекс й' используется н в качестве выходного индекса, н для формирования перестановки, н что деление на й' определено, так как й' н л взаимно просты. Теорема 8.7.1, Пусть й' — фиы роеоккы целое чыло, юаимяо лрыты с л. Пусть О (х) обоэчачыт кругыой миоючлен, корнем ег Перс н Е лгр Нуюгке Кме «о порога яеляе яе яется отменю»"'.
Тоедо зачисление компонент е виде ° длн й*= О, ..., л — 1 может бить реокиэ иько е е е гкедуюи(их трех юагы: (1) ьмч с ить поликомиольлы лреобр еокие — 1 у,(х)= й; «п(х)хн" (юобЯ(к)), й=б г -о (2) емсислить л лреобраэоеачий Фуры — й: НОд(й, я)= 1, й О (8) сделозю керестояоеку йЧ НОД(й', л).=1 Ую ю=у' пююн й- О Докоэаглельслюо, Рассмотрим равенства « — ! Уьаь.н (к) = ~ »нмЪп (х), с=о 1'ю п„ь и = Я„ю (1/!оюп (х)1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
