Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 30
Текст из файла (страница 30)
Значения 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).
Для каждой структуры БПФ с прореживанием по времени существует эквивалентная структура с прореживанием по частоте. Важно отметить, что количество умножений при реализации алгоритма БЙФ с прореживанием по частоте совпадает с количеством умножений при реализации БПФ с прореживанием по времени. 4.6. Ст к ы бабочекБПФпооснованию2 Существует гак много разных структур бабочек БПФ, описанных в литературе, что легко можно спутать бабочки с прорежи ванием по частоте и с прореживанием по времени. В зависимости от того, как подается материал, начинающий читатель может легко прийти к выводу, что БПФ с прореживанием по времени всегда требует бит-реверсивной перестановки входных отсчетов, а БПФ с прореживанием по частоте всегда выдает результат в бит-реверсивном порядке.
Как показывают приведенные структуры, это не так. Прореживание по времени или частоте определяется тем, какая последовательность — входная или выходная, подвергается разделению при выводе той или иной структуры бабочек БПФ из формулы ДПФ.
х(0) х(0) х«) х(4) х(г) х(2) х(з) х(6) Х(4) Х(5) х(5) х(з) Х(6) х(7) х(7) Рис. 4.8. 8-точечное БПФ с прореживанием по времени, входные отсчеты которо- го подвергнуты бит-реверсивной перестановке х(0) х(0) х(1) Х(4) х(2) х(г) к(з) х(6) х(4) х(ц х(5) Х(5) х(6) Х(3) «(7) х(7) Рис. 4.9. 8-точечное БПФ с прореживанием по времени с бит-реверсивным по- рядком выходных отсчетов Глава 4. Быст реп еоб аэованиеФ ье Х(0) х(0) х(1) х(ц х(2) Х(2) х(з) х(з) Х(4) х(4) Х(5) х(5) х(6) х(6) х(7] х(7) Рис. 4.10. 8-точечное БПФ с прореживанием по времени, входная и выходная последовательность которого расположены в нормальном порядке Х(0) х(0) х(1) х(4) х(г) х(г) х(6) х(з) х(4) х(1) Х(5) х(5) Х(5) х(3) хр) х(7) Рис.
4.11. 8-точечтное БПФ с прореживанием по частоте и бит-реверсивным порядком входных отсчетов Рассмотрим еще раз отдельную бабочку. Структуры БПФ на рисунках 4.8, 4.9, 4.11 и 4.12 являются прямым результатом вывода алгоритмов с прореживанием по времени и по частоте. Хотя сначала это не очевидно, но показатели степени поворачивающих множителей, приведенные на этих рисунках, распределены по определенной системе. Обратите внимание на то, что они всегда принимают обобщенные формы, показанные на рисунке 4.14 (а)'.
Для реализапии бабочки с прореживанием по времени, показанной на рисунке 4.14 (а), нам потребуется ! Помните, что для простоты в структурах бабочек, показанных на рисунках 4.8 — 4.13, приведены только показатели степени поворачивающих множителей, х и й+У/2, а не полные комплексные поворачивающие множители. 157 4.6.
С к ы бабочек БПФ по основанию 2 выполнить два комплексных умножения и два комплексных сложения. Конечно же, есть лучший способ реализапни. Рассмотрим бабочку с прореживанием по времени на рисунке 4.14 (а). Если обозначить верхний вход как х, а нижний — как у, верхний выход бабочки будет равен х'=х 1-(Й'ч) у, (4-26) а нижний выход бабочки будет равен у ' = х + ( И'~,) у у.
(4-27) х(о) х(о> х(1) Х(4) х(2) Х(2) х(З> х(6> х(4) х(1> х(5) Х(5) х(з) х(Б) х(7) х(7> Рис. 4.12. 8-точечное БПФ с прореживанием по частоте и бит-реверсивным порядком выходной последовательности х(о> х(о) х(1) х(1) х(2) х(2) х(з) х(з> Х(4) х(4) Х(5) х(5) Х(6) х(6) х(7) хр> Рис. 4.13.
8-точечное БПФ с прореживанием по частоте и нормальным порядком входных и выходных отсчетов Глава4. Быст оеп еоб азованиеФ ье 168 Прореживание по времени Прореживание по частоте х х" х' (а) У у х' х х" (Ь) У У У х' х ° х" У' У Рис. 4.14. Структуры бабочек с прореживанием по времени и частоте: (а) исходная форма; (Ь) упрощенная форма; (с) оптимизированная форма х' х х" у У (а) (Ь) Рис.
4.15. Другой способ изображения бабочки: (а) с прореживанием по времени; (Ь) с прореживанием по частоте К счастью, операции в (4-26) н (4-27) можно упростить, потому что два поворачивающих множителя связаны соотношением (И'ч) ~ = (И'и) (И'и) ~ =(Игн) (е 'х У ) =(И'д,) (-1) = — (И',~) . ' (4-28) Следовательно, мы можем заменить поворачивающие множители (И',) й~-и/2 на рисунке 4.14 (а) множителями — ( Иг~), что дает нам упрощенную форму бабо- к чек, показанную на рисунке 4.14 (Ь). Поняв, что поворачивающие множители на 4.б. Ст к ы бабочек БПФ по основанию 2 рисунке 4.14 (Ц отличаются только знаками, мы приходим к оптимизированной форме бабочек, показанной на рисунке 4.14 (с).
Заметьте, что такие оптимизированные бабочки требую два комплексных сложения, но всего одно комплексное умножение, что уменьшает общее количество операций'. В литературе вы будете часто встречать оптимизированные структуры бабочек, приведенные на рисунке 4.14 (с), вместо структур, показанных на рисунке 4.14 (а). Эти оптимизированные бабочки позволяют нам легко распознавать алгоритмы с прореживанием по времени и по частоте. Если мы видим оптимизированные бабочки, подобные приведенным на рисунке 4.14 (с), мы знаем, что это алгоритм с прореживанием по времени, если поворачивающий множитель стоит перед — 1, в противном случае, если поворачивающий множитель стоит после — 1, это алгоритм с прореживанием по частоте. Иногда мы будем встречать в литературе структуры БПФ, в которых используются обозначения, показанные на рисунке 4.15 [5, 171.
Эти бескрылые бабочки эквивалентны показанным на рисунке 4.14 (с). В этих сигнальных графах используется соглашение о том, что выход узла, обозначенного кружочком, помеченный плюсом, представляет собой сумму отсчетов, входящих в узел слева, а выход, помеченным минусом, представляет собой разность этих отсчетов. Таким образом, выходные отсчеты бабочек с прореживанием по времени, показанных на рисунках 4.14 (с) и 4.15 (а) вычисляются как х'=хе (И'и) у и у'=х — (И'и) у. (4-29) Выходы бабочек с прореживанием по частоте, показанных на рисунках 4.14 (с) и 4.15 (Ц равны х"=х+У и У"=()4н) (х — У) =()(гм) х — ()(~) У. (4-30) Так какая же структура лучше? Это зависит от приложения, аппаратурной реализации и соображений удобства.
Если для выполнения БПФ мы используем программу на компьютере общего назначения, выбор у нас обычно невелик. Большинство специалистов просто используют существующие подпрограммы БПФ, включенные в коммерческие пакеты программ. Их код может быть оптимизирован по скорости выполнения, но вы этого никогда не узнаете. Чтобы разобраться в том, как онн реализуют БПФ, может потребоваться изучение этого кода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
