Несмотря на то, что алгоритмы БПФ хорошо известны и широко используются, при первом ознакомлении с ними они по ряду причин достаточно трудны для понимания. К тому же в современной научно-технической литературе встречается несколько различных подходов к описанию алгоритмов БПФ. В данном разделе мы познакомимся с теорией алгоритмов БПФ по основанию 2. Термин «по основанию 2» говорит о том, что число входных отсчетов N кратно степени числа 2, то есть . Среди этих алгоритмов различают два основных типа:
· алгоритм БПФ с прореживанием по времени (decimation-in-time – DIT);
· алгоритм БПФ с прореживанием по частоте (decimation-in-frequency – ьDIF).
Дискретное преобразование Фурье конечной последовательности было определено нами ранее и описывается выражением (1.24). Основная идея БПФ состоит в том, чтобы разбить исходную N-точечную последовательность на две более короткие последовательности, ДПФ которых могут быть скомбинированы таким образом, чтобы получилось ДПФ исходной N-точечной последовательности. Так, например, если N четное, а исходная N-точечная последовательность разбита на две (N/2)-точечные последовательности, то для вычисления искомого N-точечного ДПФ потребуется порядка комплексных умножений, т.е. вдвое меньше по сравнению с прямым вычислением. Здесь множитель (N/2)2 дает число умножений, необходимое для прямого вычисления (N/2)-точечного ДПФ, а множитель 2 соответствует двум ДПФ, которые должны быть вычислены.
Эту операцию можно повторить, вычисляя вместо (N/2)-точечного ДПФ два (N/4)-точечных ДПФ (предполагая, что N/2 четное) и сокращая тем самым объем вычислений еще в два раза. Выигрыш в два раза является приближенным, поскольку не учитывается, каким образом из ДПФ меньшего размера образуется искомое N-точечное ДПФ.
Проиллюстрируем описанную методику для N-точечной последовательности , считая, что N равно степени 2. Введем две (N/2)-точечные последовательности и из четных и нечетных членов соответственно, т. е.
(1.28)
В этом случае N-точечное ДПФ последовательности можно записать следующим образом:
(1.29)
С учетом периодичности и симметричности поворачивающих множителей следует:
. (1.30)
Перепишем выражение (1.29) в следующем виде:
. (1.31)
Полученные суммы представляют собой прямые ДПФ исходных последовательностей и , тогда выражение (1.31) приводится к виду:
. (1.32)
Из формулы (1.32) следует, что N-точечное ДПФ X(k) может быть разложено на два (N/2)-точечных ДПФ, результаты которых объединяются согласно выражению (1.32). Если бы (N/2)-точечные ДПФ вычислялись обычным способом, то для вычисления N-точечного ДПФ потребовалось бы, очевидно, (N2/2+N) комплексных умножений. При больших ‘>N(когда N2/2>>N) это позволяет сократить время вычисления на 50%.
Поскольку X(k) определено при , а X1(k) и X2(k) определены при , необходимо доопределить формулу (1.32) для . Это определение является прямым следствием периодичности ДПФ и симметричности
поворачивающих множителей. Принимая во внимание симметрию поворачивающих множителей
,
получим следующее выражение для доопределения коэффициентов ДПФ:
. (1.33)
На рис. 1.18 с помощью направленного графа представлена последовательность операций при выполнении восьмиточечного ДПФ с использованием двух четырехточечных преобразований.
Входную последовательность сначала разбивают на две последовательности и из четных и нечетных членов , после чего рассчитывают их преобразования и . Затем в соответствии с формулой (1.33) получают . Незачерченные кружки в правой части (рис. 1.15) обозначают операцию сложения (вычитания), причем верхний выход соответствует сумме, а нижний – разности. Стрелка (®) обозначает операцию умножения входного числа (a) на значение множителя, указанного над стрелкой. В общем случае переменные являются комплексными числами. Заметим, что кружок можно интерпретировать
как двухточечное ДПФ. Узлы обозначают регистры, содержащие входные и выходные массивы отдельных ДПФ. Все эти обозначения согласуются с правилами изображения направленных графов в теории линейных систем.
Рассмотренная схема вычислений может быть использована для расчета (N/2)-точечных ДПФ в соответствии с формулой (1.33). Каждая из последовательностей и разбивается на две последовательности, состоящие из четных и нечетных членов. Аналогично (N/2)-точечные ДПФ могут быть записаны как комбинации двух (N/4)-точечных ДПФ, т.е.
(1.34)
где , и – (N/4)-точечные ДПФ соответственно четных и нечетных членов .
На рис. 1.16 показан результирующий направленный граф, в котором четырехточечные ДПФ (см. рис. 1.15) рассчитываются согласно формуле (1.34).
Процесс уменьшения размера ДПФ от до , где равно степени 2, может быть продолжен до тех пор, пока не останутся только двухточечные ДПФ. Двухточечное ДПФ , может быть рассчитано без использования умножений по формулам
(1.35)
или
(1.36)
Здесь – преобразуемая двухточечная последовательность. Поскольку , для вычислений по формулам (1.36) действительно не нужны операции умножения. Таким образом, восьмиточечное ДПФ (см. рис. 1.15 и 1.16) в итоге сводится к алгоритму, описываемому направленным графом (рис. 1.17).