Айфичер Э., Джервис Б. Цифровая обработка сигналов, практический подход (2-е изд., 2004) (1095888), страница 29
Текст из файла (страница 29)
Я Я о а й Я. й о З.б. Апюритм быстрою преобразования Фурье с децимацией во временной области 157 Теперь Хга (2) = хо + И' йгаха = хо + Из~ха = хо + ха = Хяа(0), Хю(2) = ха+ И ь74хв — ха+ хо = Хгя(0). Следовательно, уравнение (3.54) эквивалентно уравнениям Хы(2) = Хга(0) — Хгг(0) (3.55) Х„(3) = Х„(3) — Игй7яХяя(3) (3.56) Теперь Хм (3) хо + И аогаха = хо+ е ~ ~ ~ ха = хо+ е * 'ха — — хо — ха = Хм(1) Хю(3) = хг — хо = Хгг(1).
Следовательно, уравнение (3.5б) эквивалентно уравнению Хп(3) = Хяа(1) + е агоаГаггХяг(1) = Хяа(1) + е Я"7~Хая(1) = (3.57) = Хм(1) + аХая(1). Сведя эти результаты вместе, получим Хы(0) = Х„(0) + Хгг(О) = Хг,(0) + И'оХ„(0), Хы(2) = Хм(0) — Хяг(0) = Хяа(0) Ио Хгя(0), Хм(1) = Х,а(1) — аХ„(1) = Хм(1) + И'ЯХ„(1), Х„(3) = Хм (1) + аХгя(1) = Хга(1) + И'огХгя(1). (3.58, а) (3.58, б) (3.58, в) (3.58, г) Внимательно изучая эти уравнения, видим, как ДПФ-образы Хат(к) связаны с ДПФ- образами их последовательностей с четными и нечетными номерами, и что Хм(0) н Х„(2) задаются выражениями с одинаковыми членами, которые отличаются толью знаком.
То же справедливо и для Хы(1) и Хы(3), Уравнения, подобные этим, называют рекампозиционными, поскольку, взяв пары данных и формируя Хяа(х), Хяя(й), Хгг(1а) и Хяа(аа), можно найти Хаа(та) и Хая()а), а следовательно, и Хт(й). При этом количество необходимых операций комплексного сложения и умножения уменьшается, посжальку, во-первых, рекомпозицнонные уравнения записываются через рекуррентный коэффициент И~аг в некоторой степени, во-вторых, используются также соотношения типа Хм(2) = Хга(0) и Хяа(3) = Х„(1) и, в-трстьих, различие между парами используемых выражений состоит только в знаке.
Этот алгоритм известен под названием алгоритма Кули-Тычки. Глава 3. Дискретные преобразования 1ББ х«(о> = хи(о>+ н",хо(о> х«(о> х«рп лшо>- н4хыо> х„(о> а) х«(п = х«(п+ н5х«п) х«(п х«(э) х,(о - и4хып хин) и) х«(о> хи(о)+ н«хыо) х«(о> х«ш-хиш+ и)хоп> х«(л) х«(о) — и4х«(о) хо(о> х«(з) х«())-н'$х„(п х«п> Рис. ЗА. "Бабочки" БЛФ ~';~ффк(о)(~; "Бабочка" Уравнения (3.58) можно изобразить на диаграмме, взяв их попарно и воспользовавшись симметрией знаюв.
Итак, согласно уравнениям (3.58, а) и (3.58, б) результатом рекомпозиции будут Х))(0) и Х)>(0), получившиеся из входных Хм(0) и Хзз(0). Это показано на рис. 3.4, а. Входные данные находятся с левой стороны от креста, а выходные — с правой. На рис. 3.4, б показано, как с помощью диаграммы можно получить Хц(1) и Хп(3). При наложении рис.
3.4, а на рис. 3.4, б получается составная диаграмыа, на которой выходные ДПФ расположены в порядке возрастания )о (см. рис. 3.4, в). Структура, изображенная на рис. 3.4, а или б, называется "бабочкой", поскольку диаграмма похожа на стилизованное изображение этого насекомого.
Целиюм восьмиточечное БПФ можно изобразить так, как показано на рис. 3.5. ,,Л)~~Ф~мщЯзйн(; Сейчас будет полезно найти ДПФ последовательности (1, О, О, 1), ранее определенное в разделе 3.2 с помощью алгоритма БПФ с временной децимацией. Это четырех- точечное ДПФ с хо = 1, х, = О, хз = О, хз = 1 и Х>(й) = Х))(й) + ИгтХ„(й), й = О, 1, 2, 3.
Переупорядочеиная последовательность — хо, хз, х„хз. 3.5. Алюритм быстров преобразования Фурье с децимацией во временной области 159 д«о> (о> н> о> (с) (з) (б) лс (т) ю д«з) хи(п Лаа олн лвуятсчсчимя дне чстмвсяючсчныя дне аасмсеимсчюмдпе этап! (3 Н э мз *3> Эт > бе З) Р>ю. 3.5. "Бабочки" восьмнточечното ДПФ: ВИ'э — память, выделенная точаам, дающим вкющ в самую большую "бабочку" этапа 3; ВЯз — память, выделенная веряиим точкам "бабочки" этапа 3 с одннаювыми асеевыми аоэФФиниеитемн Теперь для выполнения ДПФ можно воспользоваться верхним левым углом рис. 3,5.
Точки хо, хс, хз, хе заменим точками хо, хз, х>, хз, и искомыми значениями ДПФ будут Х„(0), Х„(1), Х„(2), Хм(3). Следовательно, Хз> (О) хо + хз 1 Хзз(1) = хо — хз = 1, Хаз(О) = х> + хз = 1, Хгз(1) = х> — хз = — 1, Хм (0) = Хм(0) + Ита~Хзз(0) = 1+ 1 = 2, Хм(1) = Хм(1) + Ига Хзз(1) = 1+ е ' ~ ( — 1) = 1+ т, Хм(2) = Хм(0) — ИзХзз(0) = 1 — 1 = 0 Км(3) = Х)л(1) — И'в Хзз(1) = 1 — т.
Полученные значения идентичны величинам, которые были найдены в разделе 3.2, но с помощью алгоритма БПФ их получить намного проще. Это общий вывод, причем сокращение вычислений возрастает при увеличении числа исходных выборок. 1ВО глава 3. Дискретные преобразования Таблица 3.2. Переупорялочеиие последовательности путем обращения битов " ':3.6.2. Выполнение алгоритма Изучая рис. 3.5, видим, что для выполнения БПФ программа должна переупорядочить входные данные и выполнить вычисления по схеме "бабочка". Обсудим эти операции по очереди (см. также 124)). 3.5.2.1.
Переупоридочение входных данных Хотя на первый взгляд может показаться, что у программы нет четкого способа переупорядочения данных, он есть. Секрет в том, что нужно перейти в двоичную систему счисления. В первом столбце табл. 3.2 показан нужный порядок входных данных для "бабочки", изображенной на рис. 3.5. Предполагается, что каждое значение сохраняется в двоичной ячейке памяти. Адреса этих ячеек даны во втором столбце. В третьем столбце показаны эти же адреса, но с обратной последовательностью битов.
Если в соответствии с этими обратными адресами взять двоичные адреса исходной последовательности данных, начав с к(0) для 000, то получатся значения, которые записаны в четвертом столбце. Таким образом, видно, что адреса переупорядоченных данных— это записанные с обратной последовательностью битов адреса исходных данных. Следовательно, программа должна преобразовать номера заданных точек (от 0 до Х вЂ” 1) в двоичные, обратить последовательность битов в этих номерах и преобразовать их снова в десятичные номера, которые и будут адресами переупорядоченных данных. Переход в двоичную систему осуществляется многократным делением на два, при этом остатки дают цифры соответствующего двоичного числа в обратном порядке, которое и является искомым бинарным адресом переупорядоченной последовательности. Эти остатки можно найти, воспользовавшись функцией МОЮ, реализованной в языках высшего уровня, например, функция МОР (К, 2 ) выдаст остаток при делении десятичного числа К на 2.
Целая часть К/2 находится путем целочисленного деления. Остальные цифры вычисляются путем повторения этого процесса до тех пор, пока не будет выполнено 1об, Х операций деления. Это следует из того, что, поскольку данные должны состоять из 2 = У точек, для каждого адреса нужно т цифр, и он должен делиться на два т раз, где т = 1окэ Аг. Отметим, что 1-й бит нового адреса — это двоичный коэффициент числа 2 ' ', так что новый адрес (МАРОК) можно найти с помощью цикла 00 для определенного значения К (К=1доРК), которое приобретает значения от 1 = 0 З.б.
Атпоритм быстрою преобразования Фурье с децимацией во временной области 161 до / = т — 1 и вычисляет остатки (К)(МОК) от деления К 1АООК последовательных целых чисел на два. Соответствующий псевдокод приводится ниже. ОО РОК 1 О ТО т-1 КИМ(Ж: МОО(1АОРК,2) МАИЖ: МАООК+ВЫМОК*2"(и-1-1) 1И)ОК: 1АООК/2 ЕМО 00 Этот цикл 00 должен находиться внутри еше одного цикла 00, задача которого— извлечь исходные данные из комплексного массива ОАТА(К), К пробегает значения от 0 до )т' — 1, представляющие собой номер точки из набора данных (а также номер комплексного элемента массива н исходный адрес данных), и ввести переупорядоченные данные в массив МЕИОАТА(МАООК) . Данные в массиве МЕИОАТА теперь стоят в последовательности, подходящей для вычисления "бабочки". Полный псевдокод, таким образом, вьнлядит так; 00 ГОК К О ТО М-1 МАОРК: О 1АООКз К 00 КОК 1 О ТО и-1 КИМОК: МОО(1АИЖ,2) МАООК: МАООК+РЫМНИК*2*(В-1-1) 1АИЖ: 1АИЖ/2 ЕМР 00 МЕНОАТА(МАО(Ж): ОАТА(К) ЕМО 00 3.5.2.2.
Вычисление "бабочки" Вычисление состоит из трех этапов: а) вычисление весовых коэффициентов И/на = е-(з з/н)Ю. б) вычисление "бабочки" данного каскада (определение каскадов см. на рис. 3.5); в) вычисление всех каскадов "бабочки". Достаточно эффективная реализация вычислений по схеме "бабочка" включает вычисление весовых коэффициентов Ит1лт, необходимых на данном каскаде, с последующим вычислением для каждого нз них всех "бабочек" этого каскада, в которые входит данный коэффициент. После вычисления всех "бабочек" данного каскада процедура повторяется для всех каскадов. Итак, для каскада 2 на рис. 3.5 вычисляются Итз и две "бабочки", содержащие коэффициент И'е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
