1. Основы алгоритмов бпф

Дискретное преобразование Фурье (ДПФ) X(k) конечной последовательности x(n), n = 0, 1, ..., N – 1

X(k) = , k = 0, 1, ..., N – 1; (1)

обратное ДПФ x(n) = ,(2)

где n = 0, 1, ..., N – 1; W_N = – периодическая последовательность с периодомN

, m = 0, 1, 2, ... .

Непосредственное вычисление ДПФ X(k) (12.1) при комплексных значениях x(n) требует (N–1)² комплексных умножений и N(N–1) сложений комплексных чисел. Для больших значений N (сотни, тысячи) прямое вычисление ДПФ (12.1) требует выполнения очень большого числа арифметических операций умножения и сложения, что затрудняет реализацию вычисления в реальном масштабе времени.

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

БПФ с прореживанием по времени требует перестановку отсчетов входной последовательности x(n), а БПФ с прореживанием по частоте – перестановку отсчетов выходной последовательности X(k).