Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 29
Текст из файла (страница 29)
При М = 8 (4-20) и (4-20') реализуются так, как показано на рисунке 4.2. Х(0) х(0) Х(1) х(2) Х(2) х(4) Х(3) х(6) Х(4) х(1) Х(5) х(3) Х(6) х(5) Х(7) х(7) Рис. 4.2. Реализация БПФ для 8-точечного ДПФ с использованием двух 4-точеч- ных ДПФ Если мы запишем (4-20) н (4-20') в более простой форме (4-21) Х(т) =А(т) ч-(йт~)"В(т), Глава4. Быст оеп еоб азоааниеф ье 148 Х(т+й»/2) = А(т) — (И"м) В(т), (4-21') мы можем пойти дальше и разбить два 4-точечных ДПФ на четыре 2-точечных ДПФ. Посмотрим, как можно разделить верхнее 4-точечное ДПФ на рисунке 4.2, четыре выхода которого равны А(т) в (4-21) и (4-21').
Мы можем разделить четные и нечетные входные отсчеты верхнего 4-точечного ДПФ: (М,'2) — 1 )и»и и=О (М,'4) — 1 (М/4)-1 =,» х(4п)(Иьу2) " +~, х(4п+ 2)(И)»у2)( " ) . (4-22) и-0 и-0 Поскольку (И~,О,2) " = (И',,~4)", мы можем выразить А(т) через два Л»/4-точечных ДПФ как (У/4)-1 (М/4)- 1 А(т) = Я х(4п)(И'~4)"~+(И~12)~,Я х(4п+2)(%~~4)'~.
(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 и т. д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
