1.3.4.    Свойства алгоритма БПФ с основанием 2 и прореживанием по времени

Анализ графа (см. рис. 1.17) и процедуры последовательного сокращения вдвое размеров преобразований показывает, что на каждом этапе БПФ (т. е. при каждом сокращении размеров ДПФ) необходимо выполнить  комплексных умножений. Поскольку общее количество этапов равно , то число комплексных умножений, необходимое для нахождения -точечного ДПФ, приблизительно равно .

Слово «приблизительно» использовано по той причине, что умножения на и  в действительности сводятся просто к сложениям и вычитаниям комплексных чисел. Так, например, первый этап БПФ (см. рис. 1.17) содержит только сложения и вычитания комплексных чисел. Даже на втором этапе используются только сложения и вычитания комплексных чисел. Фактически, как следует из направленного графа (см. рис. 1.17), вместо ожидаемых 12 (т. е. 4×log28) достаточно выполнить всего

два нетривиальных умножения. Однако для больших значений N фактическое число нетривиальных умножений хорошо аппроксимируется выражением .

Описанный алгоритм был назван алгоритмом с прореживанием по времени, поскольку на каждом этапе входная (т. е. временная) последовательность разделяется на две обрабатываемые последовательности меньшей длины, т. е. входная последовательность прореживается на каждом этапе. Другая форма алгоритма БПФ (с прореживанием по частоте) будет описана далее, а сейчас целесообразно обсудить некоторые общие свойства алгоритмов БПФ.

Базовая операция алгоритма с прореживанием по времени (так называемая «бабочка») состоит в том, что два входных числа А и В объединяются для получения двух выходных чисел X и Y следующим образом:

Подпись:  
Рис. 1.18. Базовая операция алгоритма БПФ с прореживанием 
по времени

.                               (1.37)

На рис. 1.18 изображен направленный граф базовой операции (1.37). Внимательное рассмотрение направленного графа (см. рис. 1.17) показывает, что каждый из этапов содержит  базовых операций. В случае, когда множитель  – нетривиальный, для каждой базовой операции необходимо выполнить только одно умножение, поскольку величину  можно вычислить и запомнить.

Подпись:  
Рис. 1.19. Типичное разложение для алгоритмов БПФ 
с основанием 2

Таким образом, структура базовых операций такова, что для выполнения БПФ -точечной последовательности, размещенной в памяти, достаточно иметь лишь одну дополнительную ячейку памяти. Нетрудно заметить, что базовая операция «бабочки» 2-точечного ДПФ формирует основу для всего вычисления. Вычисление осуществляется в трех каскадах. После того, как заканчивается вычисление первого каскада, нет необходимости сохранять какие-либо предыдущие результаты. Результаты вычисления первого каскада могут быть сохранены в тех же самых регистрах или ячейках памяти, которые первоначально хранили исходные отсчеты из временной области x(n). Точно так

же, когда закончатся вычисление второго каскада, результаты вычисления первого каскада могут быть удалены. Таким же образом осуществляется вычисление последнего каскада, при этом в памяти заменяется промежуточный результат вычисления предыдущего каскада. Алгоритм, в котором для размещения входной и выходной последовательностей используются одни и те же ячейки памяти, называется алгоритмом БПФ с замещением.

На рис. 1.19 алгоритм БПФ с основанием 2 иллюстрируется несколь
ко иначе. Все ДПФ являются двухточечными и не требуют операций умножения. Однако при объединении двух -точечных ДПФ в одно -точечное ДПФ приходится выполнять около  умножений. Из примера (см. рис. 1.17) видно, что -точечное БПФ состоит из  этапов, причем все операции умножения используются только при объединении результатов ДПФ. Поскольку эти умножения используются во всех алгоритмах БПФ, соответствующие множители получили специальное название поворачивающих множителей (иногда их называют фазовыми множителями или множителями вращения).

Еще одной особенностью алгоритма с прореживанием по времени (как, впрочем, и большинства других алгоритмов БПФ) является необходимость такой перестановки элементов входной последовательности, чтобы выходная последовательность  имела естественный (прямой) порядок расположения, т.е. . В примере (см. рис. 1.17) для этого требовался следующий порядок размещения входной последовательности:

x(0), x(4), x(2), x(6), x(1), x(5), x(3) и x(7).

Характер перестановки элементов входной последовательности может быть описан сравнительно просто с использованием алгоритма реверсирования битов. Алгоритм реверсирования битов, используемый для реализации прореживания по времени, представлен в табл. 1.3. Десятичный индекс n преобразуется в его двоичный эквивалент. Затем двоичные разряды располагаются в обратном порядке и преобразуются обратно в десятичное число. Реверсирование битов часто выполняют аппаратурой ЦОС в генераторе адреса данных (Data Address Generator – DAG), упрощая таким образом программное обеспечение, сокращая количество дополнительных операций и ускоряя вычисления.

Таблица 1.3 Пример бит-реверсивного прореживания для N = 8

Порядок записи номера отсчета

Номера точек

Десятичное число

0

1

2

3

4

5

6

7

Двоичный эквивалент

000

001

010

011

100

101

110

111

Двоичный эквивалент с реверсированием

000

001

010

011

100

101

110

111

Десятичный эквивалент

000

001

010

011

100

101

110

111

Отметим еще одну особенность алгоритма БПФ, заключающуюся в том, что на всех этапах преобразования используются коэффициенты . Существует несколько способов получения этих коэффициентов. Простейший способ – составление таблицы, к которой можно обращаться в процессе счета. Единственный недостаток этого способа состоит в том, что для хранения этих коэффициентов необходима дополнительная память примерно из N ячеек, так что при больших значениях N имеющийся объем памяти ЭВМ может оказаться недостаточным.

Второй способ заключается в непосредственном вычислении коэффициентов  с использованием каждый раз стандартных подпрограмм расчета синуса и косинуса. Этот способ связан с большими затратами времени, поскольку вычисление синуса и косинуса, как правило, достаточно продолжительно.