Богнер, Константинидис - Введение в цифровую фильтрацию (1044115), страница 17
Текст из файла (страница 17)
Рассмотренный метод преобразования носит название «прореживание по времени», поскольку входная временная последовательность разбивается на две подпоследовательности. Другой, совершенно отличный метод основан на разбиении искомой последовательности. Его называют методом прореживания по частоте. Здесь исходные данные стоят в естественном порядке, а конечные — в двоично-инверсном. Интересно отметить, что для выполнения вычислений не обязательно, чтобы Л1 было кратно 2. В модифицированном виде алгоритм можно использовать и для других У.
Однако эффективность алгоритма уменьшается, особенно когда сомножители, на которые раскладывается Л', велики. В самом деле, если У вЂ” простое число, алгоритм быстрого преобразования не рабогает, и необходимо использовать простую схему вычисления ДПФ, показанную на фиг. 7.9. Оценим теперь эффективность алгоритма быстрого преобразования Фурье, а затем выведем и используем систему рекуррентных уравнений, описывающих БПФ.
гллвл 7 Для больших значений У БПФ значительно сокращает время вычислений. Например, если ". Н сли 0=1024 БПФ оказывается ариблизительно в 100 раз быстрее обычного Д ДПФ. 7.7. Система рекуррентных уравнений, опис в щ ы аю их БПФ Обозначим индексами последовательные массивы А(и) направф . Т А (и) будет крайним левым массивом графа а иг. 7.13, а А„+,(и) — крайним правым; А;(и) — произво ный массив с 1, меняющимся от 1 до г+, где ательных шагов со взвешиванием входн д ых анных. Например, в те для столбца А,+~ операция взвешивания имеет в д и А,+,(и) — — А,(и)+А, и+ К А.+~ + — ~ — 2 А,(и) — А, и+ 2 В общем случае, чтобы выразить А;+,(и) через;( ), А (и) необходимо учитывать следующее. При движении справа налево по направг аф на фиг. 7.13 разнесение между парами, участвуюб ет меньшаться щими во взвешивании при каждой итерации, удет у в 2 раза. В результате этого: а) число уравнений будет удваиваться; б) диапазон изменения независимой переменной должен уменьшаться вдвое; в) аргумент весовой функции должен удваиваться.
С ччетом первого из этих условий пара, участвующая во взвешивании массива А;, имеет вид А,- (и) и А, (и+ 2'-'). Труднее всего выразить условия «а» и «б». Их можно удовлетить если вор и=(т — 1)+(1 — 1) 2'. Здесь 1 — число пар функциональных уравнений, 1=1, 2,..., 2'-', ф и т — диапазон изменения независимой переменной и, причем т=1,2,...,2''. 3 м что независимо от величины 1 переменная и принимает значения от нуля до И при условии, что 1 н т принимают все свои . О ако порядок следования значений и зависит от 1. я нкция Наконец, условие «в» удовлетворяется, если весовая фу имеет вид У"' . Эт функцию можно упростить, если выразить и ту фу ГЛАВА 7 й24 ;при 2, 2,..., 2'-', 2 ... 2'-'.
1=1, т=1, ~=1, через т и 1 (все целые) и учесть, что Юп — '>А' =1. В ез льтате Р У ..получим Я7< — 'Р' ~. Теперь можно записать окончательные рекуррентные уравнения: .А, [(т — 1) [- (1 — 1) 2'] = — [А, [(т — 1) + (1 — 1) 2'] + +А, [(т — 1)+(1 — 1) 2'+2'-1]Ф "*' '], (7.22) ,А„, [(т — 1)+(1 — 1) 2'+ 2'-'] = — [А,. [(т — 1)+ (1 — 1) 2']— — А; [(т — 1) + (Š— 1) 2'+ 2'-1] Ф " " '] ъ 7.8. Программирование алгоритма После того как мы получили рекуррентные уравнения, описы.Вающие БПФ программирование выполняется очень просто. За-метим, что вычисления включают три цикла длинои ~, и ветственно.
Самый длительныи среди них ц икл по 1, поскольку диапазон изменения и т и 1 зависит от 1. На ф . На фиг. 7.14 показана ° блок-схема вычислений, соответствующая рекуррентным уравнем (7.22). Р ководствуясь ей, легко написать программу или подпрограмму на ФОРТРАНе для вычисления ..ф приведен текст подпрограммы ЕАЗА, представляющей самое простое воплощение алгоритма БПФ. Как следует из комментариев, несколько первых операторов выполняют двоичную инверсию. Остальные касаются выполнения БПФ с прореживанием по времени.
Дальнейшее увеличение эффективности вычислении достигается путем расчета,синусных и косинусных весовых функций рекуррентным методом, как это делается в одном из вариантов подпромы ЕАЗА приведенном на фиг. 7.15б..Экономия расчетного йд амм асврем н мени происходит за счет отказа от стайдартных прогр р чета СОЯ и 31И, требующих больших затрат времени. Рекуррен- нтную формулу легко получить разложением в тригонометрический ;р яд (Й+ 1) -х членов сов [ (Й+ 1) О] и в[п [ (Й+ 1) О], где О= ., 1=1, 2,...,г.
ф (2г-ю) Со асио определению, подпрограмма ЕАЗА выполняет вычис.ления, соответствующие формуле (7.16). Для вычисления Д гл Фиг. 7.14. Блок-схема вычислений по алгоритму БПФ с прореживанием по времени. ГЛАВА 7 120 МЕТОДЬ[ ПРГОБРЛЗОВАИИЛ ФУРЬЕ 127 ЗОВйООТ[ИЕ ЕАЗТ(джей) 1мте6ей и РЕАС А (2 ф 1) Р1 а 3 1415926 И с 2 ° ей С!Н1 = и - ! 61М2 = и/2 [иРсдсе ЗмиРРье ОР Эдтд Вес1НЗ 1 00 3 1 = 1,Ь[ид [Р и.се,1) со тО ! А1 = А(дф т) А2 = А [2ю1) А(дф1) = Я(дед) А(2ю1) = А(2ют) д(1~1) а А1 А(2ф[/ з А2 1 С = С1М2 2 [Т (с. СЕ.,) ) 60 ТО З ( = с/2 60 то 2 3 1 = Х + ЗМ()ТРОЕ СОМРЕЕтЕ ТРАМЗРОРМ ВТ ПЕС[МАТ!ОИ 1И Т 1ИЕ ВЕС[ИЗ [)О 4 1 = 1~и (.1М1 = 2~~([ 1) Ь[И2 = 2 ° (и - [) ЭО 4 $ а 1,С1М2 00 4 Н 1гс1М1 $ [МЗ а (М 1) е (С 1) *2е[.!М! + 1 В1 = А(др~днЗ) В2 = А(2юо[МЗ) 61 = А(!фью [МЗ 4 (.1М!) С2 = А(2~С!ИЗ + С[Н1) ДРС а 2 ° В ° Р[ еР(.ОАТ((м' 1) е~ ДМ2) /РСОАТ(Й) А1 = С дас05[АРС) + С2е5[М(дйс) А2 =-С1 ° 51и(АРС) + С2*СОЗ(АРС) А(1 61МЗ) а В! Ф А1 д(2,61МЗ) а В2 + А2 А(1,С[ИЗ + С[М1) = Вд Дд А(2фС1МЗ ~ 01М1) = В2 А2 4 Соит[ИОЕ ЕИО Фиг.
7.15а. Программа на ФОРТРАНе реализацйи основного алгоритма ДПФ, заданного соотношением (7.16). соответствии с фор[)В)7лами (7.17) и (7.18) дополнительно к ЕАБд вызывается подпрограмма ЬСА1 Е (фиг. 7.16). Наконец, для выполнения ОДПФ в соответствии с формулами (7.19) и (7.20) перед исполнением ЕАЗА вызывается подпрограмма ЬОКТ [,ф зовйООтдие еА5т(А~)т) 1мтесей и йЕАС А(2е 1) Р1 а 3, 1415926 и з 2 ° ° и Сдмд а И с 1М2 з и/2 1иРСАСЕ ВИОРЕЛ(.Е ОР ВАТА ВЕС!ИЗ 1 з ОО З Х ° 1.(.
[Мд дс (1 ° СЕ !) СО ТО 1 Д[ а д(1 ~1) д2 т А(21) А(1ю1) = Я(де 1) А(2~.Ю) = А(2 1) А(1.1) а дд А [2~ 1) Я2 С з С1М2 [Р((..СЕ.1) Са тО З а ( а С/2 СО то 2 а 3 + Змо~1~е сомРсете тйдиЗРОйм ВТ ОЕС1ИАТ10И [И Т1МЕ ВЕС) и$ 00 4ХЗ 1>й С[Н1 2 ° ° (1 1) С 1Н2 = 2 ° ° [и А.) АРС а 2,6еР[ ° Е[И2гС~ВДТ[И) СЗ * [.Е 51 = В,В СЗТЕР ~ СОЗ(АРС) 55тЕР с 3!и[дйс) 00 4 и в 1 1..1м1 00 5 С з 1,с[и2 С[ИЗ [М - 1) + (С - 1)*2 Ь[Н1 + ! в1 * А(16~!МЗ) В2 * А(2 С[ИЗ) С1 З А(1~(.1МЗ ~ СДИ1) С2 = д(2 С!МЗ СДМ)) А1 з С1 ° СЗ + С2~5[ А2 с Сда51 + С2аСЗ Д[1 С[ИЗ) ° Вд .А! Я(2уС[МЗ) а В2 + А2 А(1~(.1МЗ + (.[Н1) = в[ А1 А (2 ~ С1НЗ + С[ид) = В2 .А2 Соит[ИОЕ С5 1 = СЗ ° СЗТЕР - 51 ° ЗЗТЕР 511 в 51 ° СЗТЕР + СЗ ° ЗЗТЕР СЗ = С51 51 = 511 Соит[ИОЕ ЕИ0 Фж.
7.15б. Улучшенная программа ДПФ с рекуррентным вычислением весовых коэффициентов. глАвА т 128 МГТОДЫ ПРЕОВ1'АЗОВАНИЯ ФУРЬЕ 129 : З))ВИОот1НЕ Воа).ЕЕХе)11 Р1МЕиз]Ом Х12, 1] 1ИТЕОЕй )С й н 2 ° ° и ВО 1 1 ч 1,М Х11 1) = Х11 1] гЕ1Оат1И) х 12 ~) ч х 12, 1] /Г~ОАТ 1л) 1 СОН11ЙОЕ ЯЕТОйй Е х)О Фиг. 7.16. Подпрограмма для умножения ~а 1/У результатов вычисления по программе ЕАЗА.
ЬОВИоот 1МЕ 5ОИ1 1хфн) )итссея и яЕАь Х12,1) н ч 2чея ~.1)11 = и/2 ОО 1 ) = г,с)ех1 х1 = х11, 1) х2 = х12,1) Ь1иг * Н ! + 2 х 11 1) е х 11 Ь1нг) х12,1) е хсг,ь)иг) х 11 $.1иг) а Х1 х 12, ь1)чг) = хг 1 Свит 1нЦЕ иет0яй емо Фиг. 7.17. Подпрограмма для выполнения двоичной инверсии при вычислении ОДПФ с помощью программы ДПФ ЕАо'т'. 7.9. Вычисление ДПФ действительных последовательностей В предыдущих разделах этой главы было рассмотрено ДПФ и его вычисление с помощью БПФ. ДПФ и БПФ служат для получения спектра Х(п) последовательности х(й), которая в общем случае является комплексной.
Однако в большинстве инженерных задач используются действительные функции с 1гп [х(7г)1=0 ' Спектр таких функций обладает свойством комплексно-сопряженной симметрии: Х(п)=Х*(И вЂ” п), и=1, 2, Следовательно, прр непосре)т т=енном использовании БПФ для оценки спектра У-точечной последовательности половина из 2Л1 требуемых ячеек памяти оказывается избыточной. Кроме того, тра- тится лишнее время на вычисление половины спектра, соответствующей отрицательным частотам.
Рассмотрим два более эффективных метода обработки действительных данных, которые не имеют указанных недостатков. Оба метода пспользу)от фундаментальное свойство симметрии, позволя)ощее представить 1)обу)о асимметричную функцию в виде суммы и гной и не ц'гной симметричных относительно некоторой осп функций. Это свойство для удобства последующих выкладок сформулируем в следующем виде: Х (и) = Х„„(п), Х„(п) п=О, 1, где т е 1 Х ~~~ Х(и)+Х(А' — и) чегн и) четн 1х и)— Х (и) — Х 1'Т вЂ” и) Лнече,„( ) = — Хнеч„н(А' — ) 2 . В обеих формулах и=1, 2, ..., Л'/2 — 1. Кроме того, Х„„н (0) =Х (0), Хчетн = Х Хн,„„н (0) =О, ( Л'') Хнсчетн ~Я Первый из двух рассматриваемых методов позволяет вычислять половину спектра, соответствующую положительным частотам, для двух Л1-точечных действительных последовательностей одинаковой длины одновременно., используя одно Лг-точечное БПФ (точки комплексные).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
