БПФ с прореживанием по частоте

Рассмотрим еще один алгоритм БПФ, который называется алгоритм с прореживанием по частоте. Пусть снова имеем входной дискретный сигнал x (n), состоящий из N отсчетов, причем N равно степени двойки. Разобьём это сигнал на два N/2-отсчетных сигнала x₁(n) и x₂(n) так, что x₁(n) состоит из первых N/2 отсчетов x (n), а x₂(n) — из остальных N/2 отсчетов x (n), т. е.

(1.20).

При таком разбиении N-точечное ДПФ сигнала x (n) можно записать как.

(1.21).

Поскольку, то получим.

(1.22).

Запишем выражения отдельно для четных и нечетных отсчетов ДПФ.

(1.23).

Из выражения (1.23) видно, что N-точечное ДПФ можно получить как сумму двух N/2-точечных ДПФ N/2-отсчетных сигналов: сигнала и сигнала .

Аналогично предыдущему алгоритму, описанную процедуру можно применить повторно и представить каждое из N/2-точечных ДПФ в виде комбинации двух N/4-точечных ДПФ и т. д. На рис. 11.6 представлен пример 8-точечного БПФ, реализованного по этому алгоритму.

Базовая операция этого алгоритма описывается выражением.

(1.24).

Сравнение двух описанных алгоритмов позволяет выявить два очевидных различия между ними. Во-первых, при прореживании по времени порядок следования входных отсчетов двоично-инверсный, а выходных — прямой. При прореживании по частоте — наоборот. Однако это отличие кажущееся, поскольку в обоих алгоритмах порядок следования входных отсчетов можно сделать прямым. Тогда порядок следования выходных отсчетов будет двоично-инверсным. И наоборот.

Второе отличие заключается в несколько ином выполнении базовой операции. При прореживании по частоте комплексное умножение выполняется после сложения-вычитания.

В обоих алгоритмах для вычисления N-точечного ДПФ требуется около операций комплексного умножения. Вычисления по обоим алгоритмам могут быть произведены с замещением. В обоих случаях должно быть предусмотрено выполнение двоичной инверсии.