Гоноровский И.С. Радиотехнические цепи и сигналы (4-е издание, 1986) (1095423), страница 87
Текст из файла (страница 87)
Так, при А7 = 2га = 1024 требуется 1О' умножений и сложений, При использовании алгоритма свертки (12.73) требуется приблизительно столько же арифметических операций. Это обстоятельство долгое время препятствовало применению цифровой техники к обработке сложных сигналов. Существенный сдвиг в этой области произошел благодаря открытию нового алгоритма, известного под названием «быстрое преобразование Фурьег (БПФ). В связи с широким внедрением БПФ в цифровую обработку алгоритм свертки применяется в основном при фильтрации малобазовых сигналов. 12.14. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ (12.77) !о !7 1 2 8 4 Х Ю 7 8 8 10 11 1218 14 1бл зх!7т -з 3 б 1 2 8 4 Х б 7 ЗдЮ-а 2!с+6 ч) О 1 2 8 4 Х 8 7 7т Рис.
12,36, Раабиеине последовательности (а(4)), 4=0, 1, ..., !!1 — 1, на две последова- тельности: четных н нечетных отсчетов Суть этого алгоритма заключается в многократном членении заданной последовательности временных отсчетов на более короткие последовательности. Поясним достигаемый при этом выигрыш на примере одного первого разбиения. Пусть задана последовательность отсчетов (з (!г)), й = 6, 1,..., Ж вЂ” 1, причем число А7 является степеньюдвойки, т.
е, )У = 2', где 1 †цел число. Разобьем эту последовательность на две подпоследовательности, как показано на рис. 12.36. Для первой из них, составленной из четно пронумерованных отсчетов з (2я) =- з! (й) (рис. 12.36, б), выражение, аналогичное (!2.14), должно быть записано в форме — ! — 1 !ч — г г г '~Р~ з(я) (Рф'= т' з(2я) Ф'ф'л= ~~~' з!(й) %'нгы, п .О, 1, ..., — — 1.
а-о а.=. о а=о (12.76) ЗДесь и в Дальнейшем исгюльзУетсЯ обозначение %'и =е — !гл1н, ДлЯ второй (нечетной) подпоследовательности, составленной из отсчетов з (2й +1)= =зц (я) (рис. 12.36. в), ДПФ можно записать в форме !т — ! г !с з(й) 27» = ч~! з(24 +1! В'~~мч ц" = ~' зц(й) ))7!га+!! "= ы .Й,й !т а=-! а.= о «=а !г — — ! г В'"„~ ац(я) ))7га", и= О, 1, ..., — — 1. а=о С учетом равенств 3 РЗ вп (рв = (е тт"/п)х=е = (ал!/2, (рм = тал()2 (12.78) правые части выражений (12.76), (12.77) можно привести к виду — — ! з!(/т) (рф,и Вт(п) (Рйх а> б г о б 8 ит /г то /а ! л чч 3д, Гп) б/ — -! 3/л/ 2 х ч" зц(~) (1?й =('л'Вц(п)' Э Рис. (2.3?.
Спектры /1ПФ последовательностей четных отсчетов (а), нечетных отсчетов (б) и исходной последователь. кости (а) 8 (п) = $! (и) + (ръчл, Вц (п). В диапазоне и = Л!/2, Л!/2+ 1,..., Л! — ! можно, основываясь на периодичности $! (и) и бц (и) (с периодом Л/2), исходить из равенств 8т(п) =8! (п — Л!/2), Вц(п) =8п(п — Л//2). (12.79) Кроме того, необходимо учитывать перемену знака перед фазовым мно- жителем при п /ч/2: (рп (рчч/в+ п — и/т (рчч/т (Рп- и/х (у/и- и/т л л л л! ' и ел !ч , кольку (ри/т =е ' и л' В результате приходим к следующему выражению для ДПФ всей последовательности: 5(п)= " ' - ' (12.80) Ь!(п)+ ()?",~8ц(п), О <п(Л//2 — 1, 8! (п — Л'/2) — (3'и и/т Вц (и — Л//2), Л//2 < и < Л! — 1. 38? !3* В этих выраженияхБ! (п) ибц(п) б г л б 8 тб гг то тб представляют собой ДПФ соответственно четной и нечетной подпоследовательностей. Заменой !утаи~' на В'фх учитывается, что шаг дискретизации в (з! (/т)) и (зц (/т)) вдвое больше, чем в исходной последовательности (з (й)).
.2п л -! ~~п фазовый множитель ((?и = е " перед второй суммой учитывает задержку последовательности (зц (/!)) на один интервал относительно последовательности (з, (й)) (см. рис. 12.36). На рис. 12.37, а и б представлен примерный вид спектров $! (п) и Вц (п). В соответствии с числом временных отсчетов Л!/2 число спектральных коэффициентов также равно Л /2 (п = 0,1,, /ч/2 — 1). Штриховыми линиями на рисунках показано периодическое продолжение спектра на участок /ч/2 : < и< Л/ — 1. Резулыирующее ДПФ $ (и) исходной последовательности (з (й)) можно выразить через 8! (п) и Вц (и).
В диапазоне и =0,1, ..., №2 — 1 имеет место очевидное соотношение 3 (г/) з бр 36) 3(/) х л+и"„"д Згб- ) 3,, (и) Зх (г) (Ф ) ЗФ З(ту ) т Д Игло а) 3 (и) Зап" Зт(о)еИг" 3; (о), О~о< — -( л' "г З,Щ'-) Зри"Зг(" 2) Иг(т-а)3(» а) Ф г ~л4л-г 3,( ~) 3 (л'-г) Рис. !2.38. Базовые операции, используемые в алгоритме БПФ Спектр 8 (и) содержит й/ спектральных отсчетов на интервале одного периода (на оси л), как это представлено на рис. 12.37, в.
Заметим, что Бг (л — /!//2) и Вц (п — А//2) совпадают с соответствующими значениями 81 (и) и Вп (а). Выяснив структуру спектров $~ (и) и Зп (а), подсчитаем число операций умножения, требующихся для получения Аг спектральных коэффициентов при использовании алгоритма (12.80). Для вычисления функций $~ (а) и Вц (а) требуется (А//2)в умножений отсчетов з (й) на комплексные коэффициенты )Ря. Кроме того, требуется Аг умножений 8п (и) на коэффициент )!Ум. Всего требуется 2 (Аг/2)а+ Аг умножений, т, е. почти вдвое меньше, чем при использовании алгоритма (12.73). Разбиением каждой подпоследовательиости можно осуществить дальнейшее уменьшение объема вычислений. Разбиение следует продолжать вплоть до получения простейших, двухэлементных последовательностей. Определив ДПФ указанных простеиших пар отсчетов, можно найти ДПФ четырехэлементных, восьмиэлемеитных и т.д.
последовательностей. При объединении ДПФ двух подпоследовательностей можно руководствоваться алгоритмом (12.80), подставляя в него соответствующие значения Аг и а. В основе алгоритма (12.80) лежит операция сложение-вычитание с умножением одного из слагаемых на коэффициент Ю'мг. Указанную операцию, являющуюся базовой для БПФ, можно представить в виде графа, изображенного на рис.
!2.38, а (так называемая бабочка). При обозначениях (12,80) базовая операция принимает вид, показанный на рис. 12.38, б. Основанный на этой базовой операции сигнальный граф объединения двух ДПФ представлен на рнс. !2.38, в. Проиллюстрируем описанный способ построения полного графа БПФ от двухточечных до А/-точечных ДПФ на примере Аг = 8. После первого разбиения последовательности (з (й)) получаются две четырехэлементные последовательности (г~) н (зц), показанные в левой части рис. !2.39, В первой из них четными считаются з, (О) = з (О) и 3, (2) = = 3 (4), а нечетными 3, (!) = з (2) и з, (3) = з~ (б).
Поэтому последовательность (зг) распадается иа две пары: а (О), а (1) и Ь (О), Ь (!) !т. е. з (О), 3 (4) и 3 (2), з (6)). Аналогично последовательность (зц) распадается иа две пары: с (О), с (!) и г/ (О), г( (1). Зд(Ф Зд бу 3,(г) з (3) 3 (Ы Зд(1) зд(г) И' Зз(З) Рис. 12.39. Сигнальный граф БПФ нри Л1=8 Определим ДПФ двухэлементных последовательностей. Для пары а (0), а (1) ! А(п) = ~ а()г) %'иаи,, п=О, 1, ь=о откуда А(0) =а(0)+а(1) )ь')г)4 =а(0)+а(1), А (1) = а(0)+а(1) Ж'й)а = а (0) + а (1) 1174 а (0) — а (1). Как видим, для вычисления А (О) и А (1) не требуется умножений. Нужно лишь образовать сумму а (0) + а (!) и разность а (0) — а (!), т. е.
з (0) + з (4) и з (0) — з (4). На рис. 12.39 для операции сложение-вычитание использована символика, совпадающая с операцией «бабочкаа при )аг$ = 1: верхний вывод соответствует сумме, а нижний — разности. Аналогичным образом на рис. 12.39 обозначены ДПФ остальных пар; Ь (0), Ь (!), с (0), с (1), и г( (0), г( (1).
Следующий шаг объединение ДПФ А (п) и В (и). Число спектральных коэффициентов в суммарном ДПФ равно 4: и = О, 1, 2 и 3. По аналогии с (12.80) можем написать Учитывая, что 117л, = )Уг~п, переписываем последнее выражение в форме Аналогичные выражения нетрудно составить для ДПФ 8п (и), объединякщего ДПФ С (п) и )) (и). 'см. Базовые операции для $~ (п) и $п (п) одинаковы (см. рис. 12.39). Для определения ДПФ всей последовательности из восьми отсчетов нужно воспользоваться выражением (12.80) и графом, представленным на рис.
12.38, в при Ь) = 8. 389 з(а>-зд (В) и())- ()) "- „' Л(3) з(2)-зд(1) «ла(1)-з(4) ° л(1) З(а) Зд(2) ~Ъ Ьй З(2) а~ а-З©~ З(б) Зд(З) а — Ь(1) З Ы ~З(1 з(1)-и (0) — с(0) з(1 С(О) з(З)-зз(1) изб-з(с) ~ С(1) и (3) -зиШ -~ ~ г)(О)-з(З) в(г)) з(7)-зз(З) — г)(7)-з(7) «-))(1) А(и)-!-)Р",В(п) и =0 1 А (п — 2) — Ю'<,л — М В (п — 2), п = 2, 3. 8 А (п) + )агин В (и), и = О, 1, Бг(п) = А(п — 2) — 1Р~'" — '> В(п — 2), п= 2, 3. Итак, 8~(0)= А(0)+)агавВ(0), 8)(!) =А(1)+ Ю™ В(1), 8, !2) = А (О) — )У", В (О), 8 (3) =А (О) — ))7,' В (1). 3 ()) З(1) 3(2) 3(З) З(4) зе) ЗФ 3()) Базовые операции, соответствующие приведенным соотношениям, показаны в правой части графа на рис.
12. 39. Выяснив структуру сигнального графа БПФ, подсчитаем суммарное число операций умножения. При достаточно больших значениях ))) на каждом этапе вычислений (при каждом разбиении последовательности на две более короткие) требуется порядка У умножений. При числе разбиений 1ойьУ общее число операций равно примерно Ж 1одь У (приблнженность связана с тем, что умножение на )Р'Й, К/~, 117А!'~ и )Рй ) сводится просто к сложениям и вычитаниям комплексных чисел). Итак, при использовании алгоритма БПФ для вычисления ДПФ М-точечной последовательности требуется примерно У 1опьЛ) операций умноже- 390 вее! 0 'с с с с с с еевг Еье> еве ° Еевв ЕВОЬ ове> Ееее 6669 Ев!О 64 6617 661> Во>4 6615 Вв!4 ее!т ее>6 66>9 6626 6621 9622 Е»2> 6624 6625 Вегь о627 6926 В629 ВЕЗЕ Ве>1 Ео>2 Вв» В6>4 ьез! Е9>Ь ЕО>7 евзв Во>9 6646 6641 Е642 ооь> ЕЕ4< 6945 оеьь 3!)ВЙООТ(ЙЕ ЕЕТ(йн1Кв)н> ° »«» ° «» ° ° ° ° « ° »«« ° »* ° ° ° »»» ° » ° *« ° ° « ° »«» ° »»« ° « » ПРОГРАННА ВНПОЛНЕННЯ вл» х.конплексныя ньсснв поеовеьзтеных отсчетов йй число пРеОЕРА>теных Отсчетов~ РАвное Челоя степени Авоякн~ не пРевыньеыее 5>г ) «9 АЛЯ ПРЯНОГО ПРЕОВРАЗОВАННЯ )н«! Оля оояьтного пгеоеяьзовьння * ° ° ° ° ° ° ° ° ° ° »*9»» ° »» ° » ° » ° ° ° » ° » ° * СОНРЕЕХ Х(5)2>4й!Т )т 9 !Й«нн )Й«>я/г )ес)яаеп!6> со ТР 26 )т«(т+1 со то 16 С 0 Н Т 1 Й 0 Е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
