1. ОСНОВЫ АЛГОРИТМОВ БПФ

Дискретное преобразование Фурье (ДПФ) X(k) конечной последователъности х(пТ), п=О, 1,..., N-1 определяется согласно (1.1), (1.2):

(1.1)

(1.2)

причем является периодической последовательностью с периодом N, так как т=О, 1, 2… Непосредственное вычисление ДПФ (5.1) при комплексных значениях х(пТ) требует для каждого значения k (N - 1) умножений и (N - 1) сложений комплексных чисел или 4 (N -1) умножений и (2N - 2) сложений действительных чисел, а для всех N значений k=0, 1,…, N -1 требуется примерно N² умножений и N² сложений комплексных чисел. Таким образом, для больших значений N (порядка нескольких сотен или тысяч) прямое вычисление ДПФ (1.1) требует выполнения весьма большого числа арифметических операций умножения и сложения, что затрудняет реализацию вычисления в реальном масштабе времени процессов и спектров.

Быстрым преобразованием Фурье называют набор алгоритмов, реализация которых приводит к существенному уменьшению вычислительной сложности ДПФ (1.1). Исходная идея этих алгоритмов состоит в том, что N-точечная последовательность разбивается, на две более короткие, например на две (N/2)точечные последовательности, вычисляются ДПФ для этих более коротких последовательностей и из этих ДПФ конструируется ДПФ исходной последовательности. Для двух (N/2)-точечных последовательностей требуется примерно умножений комплексных чисел, т. е. число умножений (а также сложений) уменьшается примерно в 2 раза. Аналогично вместо вычисления ДПФ (Н/2)-точечной последовательности можно вычислить ДПФ для двух (Н/4)-точечных последовательностей и таким образом вновь уменьшить требуемое число умножений и сложений. Если N=2^v, v>O и целое, то процесс уменьшения размера ДПФ может быть продолжен до тех пор, пока не останутся только 2-точечные ДПФ. При этом общее число этапов вычисления ДПФ будет равно v=log₂ N, а число требуемых арифметических операций для вычисления N-точечной ДПФ будет порядка N_v, т.е. уменьшается примерно в N/log₂N раз. Так, при N=1000 для прямого вычисления ДПФ согласно (1.1) требуется примерно N² = 10⁶ операций комплексных умножений и сложений, а при использовании алгоритмов БПФ таких операций требуется всего порядка 10⁴, т. е. объем вычислений сокращается примерно на два порядка.

Рассмотрим два алгоритма БПФ: с прореживанием по времени (в которых требуется перестановка отсчетов входной последовательности х(пТ)) и с прореживанием по частоте (в которых требуется перестановка отсчетов выходной последовательности Х(k)).