Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов (2-е изд., 1990) (1245704), страница 23
Текст из файла (страница 23)
(5.5) =о лло . 2л Учитываи, что И'пглл И'„!г=е'%г, полУчаем Х» (/с ) = х» - 10 (/с) + И и Х» - 1, 1 (/с )» (5.6) >ле Х„, о(/с) и Х» !л(к) — (Х/2)-точечные ДПФ соответственно последовательностей х„>,о(п) и х„,, (п): п>2 — 1 п>г -1 Х» — ! О(/с)= ~~ х» 1 О(п) К й>2, Х» — 1 1(/с)= 2' х» — 1 1(п) И Я>2' л=О л=о Так как Х,(/с) должно быть определено для Х точек (/с=О, 1, ..., Х вЂ” 1), а Х» ! о(/с) и Х„ь>(/с) определяются только для Х/2 ~очек (/с=О, 1, ..., Х/2 — 1), лоопределим (5.6) лля значений /с= =Х/2, Х/2+!, ..., Х вЂ” 1; учитывая, что Х, ! О(/с) и Х„,, (Й)— периодические функции с периодом Х/2, можно записать Х»(1~+ Х/2) =- Х»- >,о (/с+ Х/2) + И~~Р+ ~12> Х ! 1(lс+ Х/2) =х...(/) — КМх„,, (/), (5.7) 2»й так как В7'~=е ' и 2= — 1, Формулы (5.6) и (5.7) дают алгоритм вычисления Х-точечной ДПФ через (Х/2)-точечных ДПФ.
Этот алгоритм можно пред- ставить направленным графом, имеющим вид «бабочки > 125 к(л)-к„, гн„"к„, кев (л) л а к(4 7)-к„„-и„к„г кгг (л) а) б) Рнс. 5.1 (рис. 5.1,а), в котором выходные числа с и г7 получаются из входных чисел а и Ь по правилам г'=о+Ь)гй, ( (5.8) г7 = о — (у Игй.
~ В качестве примера граф на рис. 5.1,6 представляет операции (5.6) и (5.7). Аналогично можно теперь выразить (Лг/2)-точечны ДПФ Х„г о((г) и Х„,д((с) через ())((4)-точечные ДПФ: Х„г о ((с) = Хв- з,о ((г) + Р) й Х, з 1 (гг), л = О, 1, ..., о(/4 — 1, 1 Х„, о((г)=Хг а о(/г) — Игй"Хг а г((г), (г=Ж(4 ... Ж(2 — 1 ( Х гл((г)=Х„гл(/с) + И'й Х» з з((г), Ус=О, „(г((/4 — 1, Х„ь,(й)=Х...(й)-И'РХ,— .,(й), К=р((~4, ...,))((2-1,) где Хь во(/г) и Х„т,г((г)--соответственно (Ж/4)-точечные ДП четных х„т о(п) и нечетных х„,, (и) членов носледовательнос х, г о(п), а Х„зл((г) и Хг в з(ггс) — соответственно (Ж/4)-точечны ДПФ четных х„зд(п) и нечетных хг в з(п) членов последователь ности х„-г.г(п) Процесс уменьшения размера ДПФ от М до М(2, где М рави степени 2, продолжается до тех пор, пока на ч-м шаге (в=1082 где Аг — исходный размер ДПФ) не окажутся только 2-точечны ДПФ Ф()г), ге=0,1, для двухточечных последовательностей гр(п п=0,1, определяемые из соотношений Ф(0)=гр(0) + И йгр(1)=гр(0)+гр(1), Ф(1)= р(0) + И ннтв р(1)= р(О) — р(1).) Последние вычисляются без операции умножения.
Пример 5.1. Поюронм алгоритм БПФ с прорежнваннсм по времени й =8 = 2з, т = 3, т. е для послсдоватсльностн х(аг), и= О, 1, 2, 3, 4, 5, 6, 7. Разобье согласно (54) исходную последовательность х(ат)=.т,(л) на две послсловатсл ности: хже(н) н х,, (и),— состоягднс соответственно нз четных н нечетных член хз (л): хлс(н)=(х(0), х(2), х(4), х(6)), ( хаг(н)=(х(1), т(3), х(5), т(7)).) 126 к,(4) л а..7 х(е) х(аг) в(77) в(еТ) х(ГТ) ;(777 х(КТ) а'(77! к, (4) л 47 кз-к(л) к-а..у Кт (4) 4 4(ек Рнс.
5.2 теперь вновь разобьем последовательности (5.10) на последоватсльностн нз нечетных н четных членов последовательностей (5.10): з., с(н)=(х(0), х(4)), х,, (п)=(х(2), х(6)), хт т(л)=(х(1), х(5)), лаз (в)= (х(3), х(7)). (5.11) Послсдовательностн (5.1!) являются уже двухточечными. Теперь, используя алгоритм, представленный графом «бабочка» (см. рис. 5.1,а), строим алгоритм 8-точечного БПФ (рис, 5.2).
Вначале построим исходный массив. Как видно из (5.11), он состойт из элементов последовательности х(п)=х(пТ), п=0,1...7„ причем на входах первого графа «бабочка» первой ступени помещаются числа х (0) и х (4). На входах второго графа «бабочк໠— числа х(2) и х(6), на входах третьей «бабочки» вЂ” х(1) я х(5) и на входах четвертой «бабочки» вЂ” х(3) и х(7).
Таким образом, если предположить, что последовательность х(п) записывается в массив ячеек памяти, то удобно осуществить размещение х(п) в следующем порядке (рис. 5.2): х(0), х(4), х(2), х(6), х(1), х(5), х(3), х(7). Легко заметить, что элементы этой последовательности получаются нз исходной х(п) в соответствии с двоичной инверсией номеров, т.
е. число х(п) с номером в двоичном представлении п=(п„,, ..., по) запоминается в ячейке памяти с номером п=(па, ..., и„,). Так, число х(4) с номером в двоичном представлении 4(,Ф вЂ”вЂ” 10012! запоминается в ячейке с номером 001ыг — — 11,о>, а число х(3), где З„о! —— 011121, запоминается в ячейке с номером 110!э,—— бг,о> и т. д. Итак, можно считать, что начальная ступень преобразования Хо((г), (г=0,1...7, получается просто в результате прореживанин (в указанном смысле) 127 исходной временной последовательности х(нТ), Н=0,1...7, т.
е. Ха (7<) = х (н Т), где й = й — двоично-инверсное представлени номера н. На выходах АГ/2=4 «бабочек» нт= 1-й ступени образовываютс значения Хт(/<), являющиеся входными числами «бабочек» т=2- ступени, На выходах последней значения выходной последователь ности Хз((г) =Х(/<), >1=0... 7. Выходная последовательность Х((г) >1=0,1...7, получается в естественном порядке следования. Как показано в рассмотренном примере, все входные числ «бабочек» ХО (7<) на начальной ступени являются элементам задашюй последовательности х(н), >>=О.„У вЂ” 1, причем получа ются из х(н) в соответствии с двоичной инверсией номеров т.
е. число х (НТ) = х (н) с двоичным представлением номер л является входным числом Ха(/<) «бабочки» с номером (г равным инверсному двоичному представлению номера н. Заметим, что в рассмотренном алгоритме БПФ можп выполнить вычисления по способу с замещением. Если разместит входную последовательность ХО(/с) «бабочек» в массиве из ячеек памяти, то после вычисления выходов «бабочек» входны элементы становятся ненужными и в указанные ячейки памят могут быть записаны вычисленные выходные числа.
На след ютцей ступени вновь вычисленные значения выходов «бабочек записываются в ячейки массива вместо использованных входнь чисел, и в конце вычислений во входном массиве окажугс записанными значения Х(й) в естественном порядке, т. е, зпачепи ДПФ при 7<=0, 1, 2... Ат — 1. 53. ПРОГРАММА И ПРИМЕР РЕАЛИЗАЦИ АЛГОРИТМА БПФ С ПРОРЕЖИВАНИЕМ П ВРЕМЕНИ Ниже приводится программа вычисления БПФ с прорежив пнем по времени по способу с замещением и рассматривают примеры реализации этой программы. Программа 5.1 быстрое преобразование Фурье с основ пнем два н прорежпванием по времени. Программа осущесгвля алгоритм БПФ с основанием два и прореживапием по време комплексной или вещественной последовательности х(п) длин Ат отсчетов.
Вещественные составляющие отсчетов исходи последовательности записываются в массив /(1(<т'), а мнимые— массив А2(ттт). В программе для ознакомления с ее работ предусмотрено формирование входной последовательное~и, соо ветствующей отсчетам нолигармопического сигнала / — ! х(н)= ,'> А!(Соз(2кпн!+<р!)+75>п(2яп>г!+4)!)1 (5.1 т=о 128 (строки 80 — 240). При использовании программы для выполнения БПФ произвольной последовательности необходимо заменить строки 80 †.
240, организовав ввод исходной последовательности. !Ф йен ВИФ 26КЕН С ОСНОВАНИЕН 2 за йен и йнвпнвй>пан йа пгп<п(н »Ф ОРЕИ -а".Ф!. <ЕР>" 5Ф 1ИРОТ 'ВВЕДИТЕ ДЛИНТ ПОСЛЕДОВАТЕЛЬНОСТИ И 2"Н >И 66 н гтх<каа<и)/каа<г>».!) >6 ян А!(И>.62<и>,й<и>,с<и>.гт<н> ВФ 1ИРОт ка>пяестза РАРВВВН">.) 96 Втн м.>-и.яз-!>,я<э-!> !66 Рати! "вв>д Анин<!/в< А<к>,чйстати и<к>/мзи и!(к)- иа гай к=а та 3-! !26 Рити! "м )к»"= >интчл мк> !за Рйтнт -и<:к»=:пвит и<к> !»Ф Рйтнт и!<1>к» -)<ТИРИ! и!<к> !56 нехт к 166 1«гат если Васл-ть ВеаестаеинАя,ааедите 1.
нь<че Ф" <19 !26 гай т ! та н !66 я=Ф>я=а !96 вв к-Ф ТО 3-! зм я =я+мк >»саа(2»з. ы>592»(1-! >«И<к>+я <к) > яа тг 19<>! тнен я=а+мк) В!и<2»з.!»!592»<т-!>Нт(к>нп(к» 226 нехт к 236 А!(1>=Я >АВ(!)=52 2»Ф кехт 1 256 йен пеРестйнан<А Вхаднай паследаВАтельнасти 2АФ И =Н/2<Я=и-ИЗ=! 226 вв 1=! та н! й>6 тг 1>=з тнеи яа 296 ВТ=М<З><М<Я М<!><М<!>=и ЗФФ 52=62<3)<62<3)=62<1)>Аз<1)=62 ЯФ К=Н2 326 !г к)=з тнен з»Ф ззФ з=з-к<к=к/2>Вата 326 з»Ф з=з к з56 нгхт ! 3»6 АЕН В П Ф 3/Ф гай ь=! та н ЗПФ Ы*з«Ь З96 Ьа ! !/2 »66 О>=!<аз 6 »16 И! Саа(3.1»!592/12><И2 -Ян<ЗПФ!592/С2> »26 гай 3=! та > 2 АЗФ Гай 1 3 ТО И ВТЕР К! МФ И=т Са »56 т! А!<и>»О>-»2<и)на>12=»2<1)>«О!»А)<1!)Н>2 »66 Аии> А!(1>-тийз(1!>=Аз<1>-тз АРФ А!<1> Ат(1>»т!<Аз(1>-62<1>»>2 »66 иехт т »96 Оз О!<О! янп-Оз»из<О Ознпн>зна 566 нехт 3 5!Ф >яхт к 52Ф йп( РАСЧЕТ АНВЛНТУД И ФАЗ 536гайт! тан ма йт»ай«< А! < и "2»А2(1 > "г> 556 1Г 1 1 ТНЕИ й(1> й5/И ЕКПЕ й(1> 2»й5/И 566 тг я<и=а АИВ /а<1»Ф т>ки гт(1>-!.5266 526 тг Аит> Ф АНВ Аз<тпа т>ки гт<1> -!.5266 5<в тг м <1><>6 тнеи гит> Агина<1>/А!<1)> яа нехт т 129 Зик.п ЗЗТЗ 1 А1<» Аг<» е зг.аае -е.еее -а.еее 4<.еее .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
