3. Алгоритм бпф с прореживанием по частоте

Алгоритм вычисления ДПФ (12.1) с прореживанием по частоте отличается тем, что входная последовательность х(n), n = 0, ..., N – 1, разбивается на две последовательности посередине – одна последовательность для n = 0 ... N /2 – 1, а другая – для n = N 2 ... N – 1 и эта процедура продолжается для каждой новой последовательности до тех пор, пока не получается искомая выходная одноэлементная последовательность X(k); при этом величины X(k) уже оказываются в выходном массиве в «прореженном» порядке и их приведение к естественному порядку связано с инверсией двоичного представления индексов k в вычисленных значениях X(k).

ДПФ (12.1) запишем в виде

X(k) = =+ =

= + .(13)

Учитывая, что = = (–1)^k, получаем

X(k) = . (14)

Подставив вместо k в (12.14) значение 2k и (2k 1), получим выражения для четных и нечетных отсчетов ДПФ:

X(2k) = ; (15)

X(2k + 1) = , (16)

где теперь для значений 0  n  N/2 – l:

(17)(18)

Рис. 3. Направленный граф «бабочка»

Вычисление N-точечного ДПФ X(k) сводится к вычислению двух N/2-точечных ДПФ при четных и нечетных значениях k для функций x₀(n) и x₁(n) и выполнению базовой операции «бабочка» – рис. 12.3. Операция «бабочка» здесь отличается от аналогичной для алгоритма БПФ с прореживанием по времени (рис. 12.1) тем, что комплексное умножение выполняется после операции сложения-вычитания

Аналогичную процедуру можно теперь применить к x₀(n) и x₁(n) и перейти от N/2-точечных ДПФ к N/4-точечным ДПФ и, таким образом, свести вычисление X(2k) и X(2k + 1) через X(4k), X(4k + 2), X(4k + 1), X(4k +3). Продолжив этот процесс, перейдем в конечном итоге к 2-точечным ДПФ с последующим прямым вычислением всех выходных отсчетов X(k). Полный алгоритм БПФ с прореживанием по частоте и его программная реализация аналогичны рассмотренным выше для метода БПФ с прореживанием по времени.

Рис. 4. Направленный граф восьмиточечного БПФ

с замещением и прореживанием по частоте

В обоих алгоритмах БПФ – и с прореживанием по времени, и с прореживанием по частоте – требуется примерно Nlоg₂N операций (комплексных умножений) и оба алгоритма могут быть реализованы по способу с замещением, используя только один массив ячеек памяти. В обоих алгоритмах должна быть предусмотрена процедура двоичной инверсии – на входе (при прореживании по времени) или на выходе (при прореживании по частоте).

Рис. 4. Направленный граф 32-точечного БПФ

с замещением и прореживанием по частоте