Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095938), страница 31
Текст из файла (страница 31)
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) Так какая же структура лучше? Это зависит от приложения, аппаратурной реализации и соображений удобства. Если для выполнения БПФ мы используем программу на компьютере общего назначения, выбор у нас обычно невелик. Большинство специалистов просто используют существующие подпрограммы БПФ, включенные в коммерческие пакеты программ. Их код может быть оптимизирован по скорости выполнения, но вы этого никогда не узнаете. Чтобы разобраться в том, как онн реализуют БПФ, может потребоваться изучение этого кода.
Если для нас важна скорость работы, первым делом нужно проверить, вычисляются ли синусы н косинусы каждый раз, когда требуется поворачивающий множитель. Обычно вычисление тригонометрических функций занимает множество машинных тактов. Скорость вычисления БПФ можно повысить, вычислив поворачивающие множители заранее и сохранив их таблицу в памяти. В этом случае вычисление поворачивающего множителя заменяется выборкой из таблицы. Если мы пишем собственную процедуру выполнения БПФ, мы можем реализовать алгоритм в целочисленной арифметике, которая на большинстве машин работает быстрее, но при этом мы должны принять меры против возможных переполнений на выходах бабочек н внимательно отнестись к масштабированию Мы говорим, что количество комплексных умножений при реализации БПФ равно (МУ2)!оязУ(см. (4-2)) именно потому, что Ж-точечное БПФ содержит (ХУ2)1оязХбабочек.
Глааа4. Быст оеп еоб аэованиеФ ье результатов'. При использовании целочисленной арифметики следует быть внимательным: некоторые К15С процессоры в действительности выполняют целочисленные операции медленнее, т. к. они оптимизированы для выполнения операций над числами с плавающей запятой. Если мы используем для вычислений векторный процессор, программы для этих процессоров всегда оптимизированы, т. к. их главная цель — высокая скорость вычислений.
Изготовители векторных процессоров обычно рекламируют свои изделия, указывая скорость выполнения на них 1024-точечного БПФ. Посмотрим теперь, какие возможности есть у нас при выборе структуры БПФ для реализации в виде специализированной аппаратуры.
Обсуждавшиеся ранее структуры бабочек БПФ обычно попадают в одну из двух категорий: алгоритмы БПФ с замещением и алгоритмы БПФ с удвоенной памятью. Алгоритм с замещением показан на рисунке 4.5. Выход бабочки запоминается в той же ячейке памяти, в которой хранились входные отсчеты. Память для хранения промежуточных результатов не нужна.
В этом случае для Х-точечного БПФ требуется только 2М ячеек памяти (коэффициент 2 учитывает то, что операция бабочки выполняется над комплексными числами, имеющими действительную и мнимую части). Камнем преткновения при реализации алгоритмов с замещением является довольно сложная адресация памяти. Структура БПФ с двойной памятью изображена на рисунке 4.10. В этом случае необходима промежуточная память, т. к. в структуре уже нет стандартной бабочки, и требуется дополнительно 4Х ячеек памяти. Но доступ к данным и адресация памяти в этих структурах намного проще, чем в случае алгоритма с замещением.
Высокоскоростные интегральные схемы с плавающей запятой, реализующие конвейерные структуры БПФ, более полно используют преимущества конвейерной архитектуры при использовании алгоритмов с двойной памятью [18]. Существует еще один класс структур БПФ, известный как алгоритмы с постоянной геометрией, которые делают адресацию памяти не только простой, но и одинаковой для всех каскадов БПФ. Эти структуры особенно интересны тем, кто проектирует специализированные аппаратурные процессоры БПФ [4, 19]. С точки зрения аппаратуры в общем случае алгоритмы с прореживанием по времени являются оптимальными для действительных входных последовательностей, а алгоритмы с прореживанием по частоте больше подходят для обработки комплексных входных последовательностей [8].
Когда входная последовательность БПФ симметрична во времени, для устранения ненужных операций используются специальные структуры БПФ. Эти специальные структуры, основанные на симметрии данных, описаны в литературе [20]. В случае двумерного Б П Ф, например, при обработке изображений, алгоритмы с прореживанием по частоте считаются оптимальными [21]. Ваше приложение может оказаться таким, что бит-реверсивная перестановка входной и выходной последовательности не важна.
Некоторые приложения позволяют манипулировать выходной последовательностью БПФ в бит-реверсивном порядке без восстановления нормального порядка отсчетов. Затем обратное преобразование, Переполнением называется то, что происходит, когда результат арифметической операции содержит слишком много бит или разрядов и не может быть представлен в предназначенных для его хранения регистрах Переполнение данных БПФ рассматривается в разделе 12 3. Библиог а ия 161 которое использует входную последовательность в бит-реверсивном порядке, даст результат во временной области в нормальном порядке.
В этой ситуации бит-реверсивная перестановка не нужна вообще. Примером подобного использования БПФ является перемножение двух преобразований Фурье в частотной области для получения свертки или корреляции во временной области'. Как можно видеть, выбор оптимального алгоритма и аппаратурной архитектуры Б Г1 Ф представляет собой достаточно сложную проблему, но, к счастью, литература может дать нам указания по ее решению [4, 22, 231. Библиография 1. Соо!еу, !. апб Ти1сеу, Г. «Ап А18опгЬш Гог сЬе МасЬГпе Са1си1аг1оп о1 Сошр1ех Роипег Бепея», Май. Сотриг., 'ч'о!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
