Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095938), страница 30
Текст из файла (страница 30)
(4-23) и=О и=О Обратите внимание на сходство выражений (4-23) и (4-20). Эта возможность деления й»/2-точечного ДПФ на два )((/4-точечных ДПФ и сообщает алгоритму БПФ способность существенно уменьшать количество необходимых умножений при реализации ДПФ. (Мы это вскоре продемонстрируем на примере.) Выполняя те же шаги, которые мы выполняли для получения А(т), можно показать, что В(т) в (4-21) имеет вид (Х/4) — 1 (М/4) — 1 В(т) = ~» х(4п+1)(Иг)О~4у)+(%~~2~~Я х(4п+3)(Иги»4)™. (4-24) и-0 и-0 При )(( = 8 (4-23) и (4-24) реализуются так, как показано на рисунке 4.3. Здесь отчетливо видна структура сигнального графа, содержащая хорошо известные бабочки, и мы видим дальнейшую перетасовку входных данных.
Поворачивающий множитель (Иг~,»2) в (4-23) и (4-24) в нашем примере с й( = 8 изменяется от (%4) до (И4)~, потому что индекс т для А(т) и В(т) изменяется от 0 до 3. Для любого Л(-точечного ДПФ мы можем разбить каждое из Ж/2-точечных ДПФ на два Ж/4-точечных ДПФ с целью дальнейшего уменьшения количества умножений на синусы и косинусы. В конце концов мы дойдем до ряда 2-точечных ДПФ, после чего дальнейшее сокращение количества операций уже невозможно.
Именно по этой причине количество точек БПФ может быть равно только целой степени двойки, а этот алгоритм БПФ называется БПФ по основанию 2. Двигаясь в том же направлении, сделаем еще один шаг вперед и закончим с рассматриваемым й» = 8-точечным ДПФ. Двухточечные ДПФ на рисунке 4.3 нельзя разделить на более мелкие части — мы дошли до конца в процессе уменьшения длины последовательности и пришли к бабочке одного 2-точечного ДПФ, показанной на рисунке 4А.
Из определения И')чследует, что (И»л») = е 1 " = 1, и Π— '2иО/14 4.4. Раз аботкаалго итма БПФпооснованию2 ()(7)у) 7 = е ) ~ 7 = е 7" = 1. Следовательно, блоки 2-точечного ДПФ на рисун№2 — /2х)у/2У -тн ке 4.3 можно заменить бабочкой, показанной на рисунке 4.4, получив, таким образом, полную реализацию 8-точечного БПФ, показанную на рисунке 4.5. х(о) х(0) х(н х(4) х(г) х(2) — ~ х(з) х(5) — ~ Х(4) х(() — (ы- Х(5) х(5) — ю Х(5) «(з) ° Х(7) хп) — ~. Рис. 4.3.
Быстрая реализация 8-точечного ДПФ в виде двух 4-точечных ДПФ и четырех 2-точечных ДПФ Итак, мы прошли через изрядное количество алгебраических манипуляций. Чтобы проверить правильность нашего вывода алгоритма БПФ, мы можем взять 8-точечную последовательности из примера 1 в главе 3 и обработать ее в соответствии с алгоритмом 8-точечного БПФ, представленным на рисунке 4.5. Последовательность данных, представляющая сигнал х(п) = гйп(2л 1000птх) + 055(п(2л2000пГ, + + 3л774), имеет вид: (4-25) х(0) = 0.3535, х(г) = 0.6465, х(4) = 0.3535, х(6) = -1.3535, х(1) = 0.3535, х(3) = 1.0607, х(5) = -1.0607, х(7) = -0.3535. 150 Глава 4. Быст ое п еобразование Фурье х(к) х(((+И/2) ~— Рмс.
4.4. Бабочка для одного 2-точечно~ о 44 х(0) х(о) х(4) х(п х(2) х(г) х(6) х(з) х(4) х(1) х(5) х(5) х(5) х(з) х(т) х(7) в(з) Рис. 4.5. Полная реализация алгоритма БПФ с прореживанием во времени для 8-точечного ДПФ Начнем перемалывать эти данные, наложив входные значения из (4-25) на рисунок 4.5, в результате чего получим значения, показанные в левой части рисунка 4.6. Выходные значения второго каскада БПФ равны 4.4. Раз аботка алто итма БПФпооснованию2 А(0) = 0.707 + (%4 )~( — 0.707) = 0.707 + (1 +)0)( — 0.707) = 0 +10, А(1) = 00 ч- ()(г4 )'(1999) = О О + (Π— У 1)(1999) = 0 — 11999, А(2) = 0707 + ( %4 ) 2( — 0707) = 0707 + (-1 +)0)( — 0707) = 1414 +10, А(3) = 00+ (Иг4) (1999) = 00+ (О+)'1)(1999) = О+)1999, В(0) = 0707 + (%4)~(0707) = — 0707+ (1 +10)(0707) = 0 +)О, В(1) = 1414 + (Й4)(1414) = 1414 + (Π— )1)(1414) = 1414 — )1414, В(2) = -0707 ~ (((,)'(0707) = -О 707+ (-1 +10)(0707) =- -1414+)О, В(9) = 1414+ (к( ) (1.414) = 1.414+ (О+)'1)(1.414) = 1.414 +)1.414.
д(о) х(0) х(а) х(4) х«) х(2) Х(2) х(е) х(з) х(1) Х(4) х(5) Х(5) х(з) х(е) х(т) х(т) 1 -О Зеае 1 414 в(з) 3-й каскад 2-й каскад 1-й каскад Рис. 4.6. 8-точечное БПФ последовательности примера 1 из раздела 3.1 Глааа4. Быст оеп еоб азованиеФ ье Вычисляя результат третьего каскада БПФ, получаем окончательный ответ Х(0) = А(0) + (%в ) В(0) = 0 + уО + (1 + 10)( О + уО) = 0 + уО + 0 -~ уО = 0 2 0; Х(1) = А(1) + (%в) В(1) = 0 — у1999+ (О 707 — 10 707)(1414 — 11414) = = 0 — у1.999 + 0 —,у'1.999 = 0 — у4 = 4 2. -90' Х(2) = А(2) + (% ) В(2) = 1414 + уО + (Π— 11)( — 1414 +10) = = 1414+ 10+ О+ у14242 = 1414+11414 =2 г' 45; Х(3) =А(3) + (%в) В(3) 0+11999+ ( О 707 )0 707)(1414+)1414) = = 0 + у'1.999 + 0 - у1.999 = 0 ~ 0; Х(4) = А(0) + (%в ) В(0) = 0 +.уО + ( 1 +.уО)(0».уО) = =0+10+0+УО=О~О, Х(5) =А(1) + (%в)~В(1) = 0 11999+ (-0.707+10.707)(1.414 — )1 414) = = 0 — у'1.999 + 0 +11.999 = 0 2.
0; Х(б) =А(2) + (%в) В(2) = 1414+10+ (0+11)( 1414+10) = = 1.414+10+ 0 — 11414 = 1.414 — 11.414 = 2 2. — 45' Х(7) = А(3) + (%в ) В(3) = 0 + 11 999 + (О 707 +уО 707)(1 414»11 4 14) = = 0 е у1.999 в» 0 + у1.999 = О + у4 = 4 г' 90'. Итак, к счастью, БПФ дает правильный результат, и это позволяет нам снова напомнить читателю, что БПФ не является аппроксимацией ДПФ, а представляет собой ДПФ с уменьшенным количеством арифметический операций. В приведенном вьппе примере вы могли видеть, что вычисление 8-точечного БПФ требует меньших затрат, чем 8-точечное ДПФ из первого примера в разделе 3.1.
Некоторые авторы предпочитают объяснять это уменьшение количества арифметических операций избыточностью поворачивающих множителей . Они показывают это с помощью звездной диаграммы, приведенной на рисунке 4.7, которая демонстрирует эквивалентность некоторых поворачивающих множителей в 8-точечном ДПФ. 4.5. БИТ-реверсивная перестановка входных и выходных данных БПФ Рассмотрим некоторые особые свойства БПФ, которые имеют большое значение для разработчиков программ и аппаратурных процессоров БПФ. Заметим, что рисунок 4.5 назван «Полная реализация БПФ с прореживанием по времени для 8-точечного ДПФ». Слова с прореживанием по времени относятся к способу разбиения входной последовательности отсчетов на четные и нечетные, который мы использовали при выводе соотношений (4-20), (4-23) и (4-24).
Такое прореживание приводит к перемешиванию входных отсчетов на рисунке 4.5. Принцип перемешивания можно понять с помощью таблицы 4.1. Это перемешивание называют бит-реверсивным, потому что порядок следования отсчетов в перемешанной последовательности можно получить путем изменения порядка следования битов в двоичном представлении индексов отсчетов в неперемешанной последовательности на обратный. Это звучит несколько запутанно, но на самом деле все просто — таблица 4.1 иллюстрирует реверс битов для рассматриваемого примера 8-точечного БПФ. Обратите внимание на то, что индексы в левом столбце таблицы 4.1 расположены в нормальном порядке, а в правом столбце индексы приведены в перемешанном порядке, который совпадает с окончательным порядком следования прореженных входных отсчетов на рисунке 4.5.
Мы перевернули биты двоичного представления нормальных индексов, поменяв их порядок следования на обратный. Старший бит стал младшим, а младший стал старшим, следующий за старшим бит стал следующим за младшим, и т, д. в 3 4 4 2 ит = иl о о в 2 ! В 4 Рис. 4.7. Избыточность поворачивающих множителей для 8-точечного БПФ Таблица 4.1. Бит-реверсивная перестановка входных отсчетов 8-точечного БПФ Двоичное Перестановка Бит-реверсивный представление битов порядок индекса л индекса и индекса и Нормальный порядок индексов и 000 000 001 100 010 010 О!1 110 001 100 101 101 110 011 1 Многие же будут первые последними, н последние первыми. 1Марк 10;ЗЦ 4.5.
БИТ- еае сианаяперестановкааходныхиаыходныхданныхБПФ 1БЗ 164 Глааа4, Бысгроеп еоб азоааниеФ ье 4.6. Структуры бабочек БПФ по основанию 2 Исследуем подробнее сигнальный граф бабочки БПФ с прореживанием по времени. Чтобы упростить сигнальный граф, заменим на рисунке 4.5 поворачивающие множители их эквивалентными значениями, обозначенными как (И'~г)~, где У = 8. Мы можем показывать только показатели степени т множителей (Игн)~, чтобы получить структуру БПФ, показанную на рисунке 4.8.
Например, ( И'4) на рисунке 4.5 равен ( И'а) и на рисунке 4.8 показан как 2, ( И'4) на рисун2 ке 4.5 равен ( И'а) и на рисунке 4.8 показан как 4 и т. д. Значения 1 и — 1 в первом каскаде рисунка 4.5 на рисунке 4.8 заменены на 0 и 4 соответственно. За исключением обозначения поворачивающих множителей, рисунок 4.8 идентичен рисунку 4.5. Мы можем перетасовать на рисунке 4.5 сигнальные узлы и получить 8-точечное БПФ с прореживанием по времени, показанное на рисунке 4.9.
Заметьте, что входные данные на рисунке 4.9 расположены в нормальном порядке, а биты индексов выходных отсчетов переставлены в обратном порядке. В этом случае необходимо выполнять операцию реверсии порядка битов над выходными отсчетами БПФ, чтобы представить частотные отсчеты в нормальном порядке. На рисунке 4.10 показана структура сигнального графа БПФ, которая не требует перестановки вообще, но элегантное переплетение линий обычной бабочки превратилось в запутанную, хоть и эффективную, конфигурацию. Не так давно большая часть времени при аппаратурной реализации БПФ тратилась на выполнение умножений, а процесс бит-реверсивной перестановки, необходимый для доступа к данным в памяти, не составлял значительной части в общем объеме вычислений. Теперь, когда аппаратурные умножители-аккумуляторы в интегральном исполнении могут умножать два числа за один такт синхросигнала, мультиплексирование и адресация данных БПФ приобретают больше значение. Это стимулировало разработку ряда эффективных алгоритмов бит-реверсивной перестановки 112-151 Существует другой способ получения алгоритма БПФ, который приводит к похожим структурам бабочек, но с другими поворачивающими множителями.
Эта разновидность алгоритмов БПФ известна как БПФ с прореживанием по частоте. Если алгоритм БПФ с прореживанием по времени основан на разделении входных данных на четные и нечетные отсчеты, алгоритм БПФ с прореживанием по частоте основан на раздельном вычислении четных и нечетных отсчетов в частотной области. Вывод алгоритма с прореживанием по частоте достаточно прост и включен во многие статьи и учебники, поэтому здесь мы не будем заниматься этим [4, 5, 15, 161.
Но мы приводим структуры бабочек с прореживанием по частоте на рисунках 4.11 — 4.13 (аналогичные структурам, показанным на рисунках 4.8 — 4.10). Для каждой структуры БПФ с прореживанием по времени существует эквивалентная структура с прореживанием по частоте. Важно отметить, что количество умножений при реализации алгоритма БЙФ с прореживанием по частоте совпадает с количеством умножений при реализации БПФ с прореживанием по времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
