Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов (2-е изд., 1990) (1245704), страница 24
Текст из файла (страница 24)
2 11.314 !1*314 з -елее -а.еее ~.еее -е.еее 5 Е.ЕЗВ 4Ф.ЕЕЕ К<» Р1<» 2.99Ф -Е.ФФФ а.еее елеь Ф.ФФФ 1 ° 159 Е,ЕЕЕ !.Зьл 6. ФФФ 1. 57Ф бае акн н<воз Ркзгльтатов ие Рнтнт 9» 629 Ратнт 91," ! м<» Аг<» н<» Рп»- ьте Рятнт Ф!. ьое Ран 1=! то н 659 !ели! ег,Ив!но "аи" <1-1< 669 Ратнт аг,овтно "999999.аее !м<»лд<».нп<лн<» ьге нкхт 1 ьаь СЬОБЯ 9! 699 Ра1ит "РАБОТА ьн<онченА" 29Ф еив Основными этапами обработки являются: ввод исходных данных (строки 50 — 240), двоично-инверсная перестановка исходной последовательности (строки 250 — 350), собственно алгоритм БПФ (строки 360 — 510), расчет амплитуд и фаз анализируемого сигнала по результатам БПФ (строки 520 — 590) и вывод результатов (строки 600 — 690). Пользователю выводятся в виде таблицы значения номера компоненты (гармоники) БПФ, вещественная и мнимая ее составляющие [А1(1) и А2(1)), амплитуда и фаза соответствующей гармоники (К(1) и Р1(1)1 Пример 5.2. Реализапия БПФ вещественного сигнала х(н)= 2; А,х <=о хсоз(2кл<о<ч.е<!), содержащего три составляющие прн значениях параметрож Ао=2, ио=<ро=О А<=1, <о<=0125, <р,=07854, А,=З, из=03!25 <рз=!*57.
1 А1<» А2<» а<» 91<» е зз.еее е.еее з.еее е.ееа -о.еее -Ф.еее Ф.аее а.гбо 2 5.657 5.657 !.еее Ф.гщ з -е.еее -Ф.еее е.еее е.ре! 4 -Ф.еее -е.еее Ф.еее»29! 5 е.е!9 гьлее з.аее !.5жг Ь -Е.ЕЕЕ Е.ЕЕЕ Е.ЕЕЕ -1Л55 -е.еее е.еее е.еее -а.евь Ф -е.еее е.еее е.еее е.еее -е.еее -Ф.еее Ф.ееа Ф.же ге -е.еее -а.еее е.еее 1.!93 ы е.еге -24.999 з.ееа -1лга Рз -Ф.аее Ф.еее е.еее -!.291 1З -Е.ЕЕЕ Е.ЕЕЕ Е.ЕЕЕ -1.297 !4 5.657 -5.657 !.еее -9.755 15 -е.еее Ф.еее е.еее -9.492 В качестве исходных данных последовательно вводятся значения: А<=1 2=3; А(0)=2; и(0)=0; и!(0)=0; А(1)=1; и(1)=0,125; <г1(1)=07854; А(2)= го(2)=0,3!25; ж1(2)=1,57; !9=1; Пример 5.3, Реализация БПФ комплексного сигнала (5.12), содержаще три составляющие (2=3), прн значениях параметров Аь ж, и ч<, таких же, к ь -а.еее г -Ф.ФФФ а -Ф.еее 9 -Ф.ееа !е -елее ы -Ф.еее 12 -Ф.еее щ е.еее 14 ~.ЕЕЕ -е.еее е.еее Ф.еее е.еее е.еее е.еее е.еее Ф.еее елее е.еее Ф.ееа елее Ф.ееа -е.аее Ф.жое е.еее е.еее е.еее е.еее Ф.еее Ф.ааа -1 ° 354 -1.
169 "1 ° 146 Л. 655 -1.1Е7 -Ф.а<6 Е. 454 9.591 -Ф.твг -Е.Е35 5.4. АЛГОРИТМ БПФ С ПРОРЕЖИВАНИЕМ ПО ЧАСТОТЕ Рассмат иваемый р мый ниже алгоритм вычисления ДПФ (5.1) отличается тем, что входная последовательность хглТт, л= ..., Аг-!, пазбивается иа две последовательности посередине (т. е. х(л ),л —,... одиа последовательность для К=О...)т'2 — 1, — и эта процедура продолжается для каждой новой носледователыюсти до тех иор, пока не иолуч ет одноэлементная последовательность Х(7<) а ся искомая выходная же ть „при этом величины Х(/с) и ив уж оказываются в выходном массиве в «про «рорежеином» порядке и их п е став р едение к естественному порядку связа» о с инверсиеи двоичного р д ления индексов (с в вычисленных значениях Х()с).
Итак, запишем ДПФ (5.1) в виде и-1 К<2 — ! и†! Х(/с)= ~. х(п) И'кы= тг„х(п) И'кх+ ~ х(п) И'А'= К2— кгг- < и=п о=я<2 «=о и=о =',Г х(л) ИУ1+ ~ х(л+ А(72) и;""!'!1. (5.! 3) Учитывая, что И'„"""=е 'к ' = 7"'=( — 1 ", =е =( — 1), получаем Х(/с)= ,'! [К(п) + ( — 1)!х(и+М/2)) И'„"". и — -о вы ажен Подставив вместо (с в (5.!4) значение 2/с (2/с Г, р ж ния для четных и нечетных отсчетов ДПФ: или ! + Б получим К/2 — 1 Х(2/с) = ,'г„хо(л) И'к~г' о=о кгг- ! Х(2/с+1) = ',! х,(н) Игкйг, (5.16) где теперь для значений 0<и<<9(2 — 1: хо (и) = х(п) + х(л+ Лг(2); х, (л) = х(л) — х (и+ <912). (5. 14) (5.17) (5.18) 131 в примсое 5.2.
Вво и .р .. д сходных данных аналогичен пример 5.2, за и го! о, что значение 79 = 0, 7 ., за искщочснием !! Следовательно, вычисление Л!-точечного ДПФ Х(!с) сводится к вычислению двух Л!/2-точечных ДПФ при ! четных и нечетных значениях !г для функций хо(п) и х, (п) и выполнению Ь базовой операции «бабочка» (рис. 5.3); отличие операции «бабочка» здесь Рис. 5.3 заключается в том, что комплексное умножение выполняется после операции сложения-вычитания.
Ту же процедуру можно теперь применить к хо(п) и х,(п) и перейти от Л/(2-точечных ДПФ к Л!(4-точечным ДПФ и, таким образом, свести вычисление Х(2!с) и Х(2/!+1) через Х(4(г), Х(4!1+2), Х(4!с+1), Х(4!!+3). Продолжив этот процесс, перейдем в конечном итоге к 2-точечным ДПФ с последующим прямым вычислением всех выходных отсчетов Х(к). Полный алгоритм БПФ с прореживанием но частоте и его программная реализаци аналогичны рассмотренным выше для метода БПФ с прорежива пнем по времени.
Необходимо отметить, что в обоих алгоритмах БПФ— с прореживанием по времени, и с прореживанием по частоте требуется примерно Л!"1одх Л! операций (комплексных умножений и оба алгоритма могут быть реализованы по способу с замеще вием, используя только один массив ячеек памяти, В обо алгоритмах должна быть предусмотрена процедура двоично инверсии — на входе (при прореживании по времени) или н выходе (при прореживании по частоте). 5.5. ПРИМЕНЕНИЕ МЕТОДА БПФ ДЛЯ ВЫЧИСЛЕНИЯ ОБРАТНОГО ДПФ (ОДПФ) По определению (5.2) ОДПФ х (пТ) Л!-точечной последовател ности Х(к), К=О, 1, ..., Л! — 1, выражается соотношением К вЂ ! х(пт)=- ~ Х()!)И'к "", (5.1 ~ а=о причем в общем случае и х(пТ), и Х(к) — комплексныс, Пус х (пТ) и Х'(!г)- — последовательности, комплексно сопряженн соответсгвенно с х(пТ) и Х(!1).
Согласно (5.!9) можно записа К-! к-! х (пТ) ~ — ,'! Х(!!) И'к"") = — 2 Х (!с) И'„"". (5.2 ~ !=о ~ и=о Но выражение суммы в правой часги (5.20) есть прямое ДП последовательности Х (/г), lс = О, ..., Л! — 1, и, следовательно, э сумма может быть вычислена при помощи рассмотренн алгоритмов и программ БПФ. !32 р с ечивается вычисление последовательности Таким обоазом обе п Л!х (пТ) и для определения х(пТ) остается взять комплексно сопряженное с Л!х (пТ) выражение и разделить его на Л'. ! к — ! х(пТ)= — ( 2 Х ()с) И'к' К=о / (5.21) (5.24) 133 5.6.
ПРИМЕНЕНИЕ БПФ ДЛЯ ВЫЧИСЛЕНИЯ РЕАКЦИИ ЦФ р ц у(пТ) ЦФ с импульснои характеристикой Вычисление еакции !п'"' — а входное воздеиствие х(пТ), п=О, 1, ... ..., М вЂ” 1, может быть выполнено на основе алгоритма свертки к — ! у(пТ)= ~" )!(и!Т)х(пТ вЂ” тТ) ~=о — (5.22) Применение алгоритмов БПФ позволяет выполнить эффективное вычисление выходной последовательности у(пТ) ЦФ. С этой целью следует определить ДПФ г!'(!с) и Х(/г в Л!+ точках для последовательностей 1!(КТ) и х(пТ), затем определить ДПФ 1'(!г)= гТ(lс) Х(!с) выходной последовательности у(пТ).
Вычисление у(пТ) по ОДПФ У(к) выполняется, например, по алгоритму (5.21). Для вычисления ДПФ и ОДПФ используются алгоритмы БПФ. Отметим, что если длина М но х(пТ) велика, то на последовательности вычисления и х п велика, то реализация упомянутого выше алгоритм у( Т) связана со значительной временной заде жкой а этой за е ж (для накопления всех М выборок х(пТ".
С е п )). целью уменьшения на от езки х задержки можно входную последовательност . ( Т' б р к х!(КТ) каждыи длиной 2. и обрабатывать каждый нз них независимо от других. Предсгавим Р-! х(пТ)= ~ х,(пТ); М=Р1., 0(п(РТ.— 1. (5.23) =о Т огда можно (5 22) записать в виде к — ! е-! у(пТ)= 2 ~~ х,(пТ вЂ” тТ)Ь(п!Т)= ,'! у,(пТ), в=о !=о ~=о где часгная свертка К вЂ” ! у;(пТ)= ~ Цп!Т)х,(пТ вЂ” тТ). а=о — (5.25) Таким об све ток и ми разом можно начинать расчет методами БПФ частных Р формировать у(пТ) путем соответствующего суммирования элементов частных сверток [2].
5.7. ДРУГИЕ БЫСТРЫЕ АЛГОРИТМЪ| ВЪ|ЧИСЛЕНИЯ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЪЕ дрпичнаинМрснаи переса!анрепа хгр) -хтр) хЦт)- амтв дрпичнаинрарснан иеротанариа хтр)-хтр) хр)-хти хт!)- хсх) К оме ассмотренных выше классических алгоритм ов БПФ, известных как алгоритмы Кули — Тычки по основанию 2, 2, известно множество других. Некоторые из ннх позволяют существенно повыс ить эффективность вычисления дискретного преобразования Фурье. Так, алгоритмы Винограда при равном числе с ложений требуют примерно в 5 раз меныпе умножений, чем алгоритмы Кулй — Тычки. н ип азбиения В основе всех известных алгоритмов лежит принцип раз иения исходного ДПФ па совокупность малоточечных. Различие за-, ключается в способах вычисления малоточечных алгоритмов и последунпцего объединения частичных результатов.
ри этом размер преобразования пе обязательно равен степени двух, т. е. становится возможным БПФ произвольной длины, что очень важно для ряда практических задач. Так, в технике связи при цифровом преобразовании многоканальных сигналов размер БПФ определяется числом объединяемых каналов, Кратко рассмотрим только некоторые, наиболее важные алгоритмы, на , на основе которых впоследствии возникло множество 1 обобщенный различных эффекгивных модификации.
Это: ) о о алгоритм ули— К вЂ” Тычки с произвольным основанием с множиа — Виног- ' тслями поворота; 2) алгоритм простых множителеи Гуда — иног-' рада; 3) алгоритм Винограда. =А! )У Д п остоты изложения везде будем полагать Аг= ! г„ Для р !е ниже )т" — лина преобразования. Очевидно, приводимь положения легко могут быть перенесены на более общ " у ий сл чай когда )5)=11 Агг, )г>2. Обобщенный алгоритм Кули — Тычки с произвольным ос- нованием с множителями поворота. Итак, пусть Ж= Ж! Агг, где М )5) — ожительпые целые.
Покажем, что в этом случае н , -пол вычи слепне исхотного гУ-точечного ДПФ можно свест и лению Аг! )ч'з-точечных и Ага Лгг-точечных Д н у ножениям на множители поворота Игл!. Для этого в выражении л — ! Х()с)= г х(п) И',та, )с=О, 1, ..., А) — 1, (5.26 ' и=о ° 2 где И'л=е 'л, необходимо сделагь подстановку: )с=)сг+)сг)1)г, )с! =О, "., А)г — 1; )с!=О, .", А)! — 1; (5.27 ( 5.28 п=п! !34 хгут)- ттт) рт)-х7рт) хп)- хтр) хд)- хп) хт))-хтр хтет)-хрт) хст)- хтаг7 Рис, 5.4 Тогда ДПФ (5.26) преобразуется к виду л,— 1 ° л — ! 2 Х()сг+)с!Ага)= ~ ~ ,'! х(п, +пг)5)г) И'»'"' Ит„,'"' Итл'"'. (5.29) «,=о ~ и,=о Таким образом, полученный алгоритм включает в себя две основные ступени: на первой ступени переставленные в соответствии с (5.28) входные выборки подвергаются Жг-точечному преобразованию Фурье. На второй ступени производится вычисление Жг-точечных ДПФ.
Между первой и второй ступенями осуществляется операция пс)ворота ну~ем умножения на поворачивающие множители И'л' ', Полученная последовательность на выходе ДПФ должна быть переставлена в соответствии с (5.27). Пример 54. Пусть )!Г=б, тггг=3, )чг=2. Положим )с=)гг-ь)сг 2; и=лги +л, 3; л!)гг=О, 1, 2; лг)!!=О, 1. Тогда Х()г)=Х()гг+)сг2)= ~ ~ ( ~ х(лг!3лг) Ют' ' Ии' ' И г' '. Соответствующий сигнальный граф алгоритма изображен на рис, 5.4. Рассмотренный подход может быть положен в основу синтеза алгоритмов БПФ Кули Тычки с произвольным постоянным основанием. Наибольшую популярность получили алгоритмы с основаниями 4 и 8, позволяющие повысить эффективность вычисления ДПФ по сравнению с классическими алгоритмами по основанию 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
