4. АЛГОРИТМ БПФ С ПРОРЕЖИВАНИЕМ ПО ЧАСТОТЕ

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

Итак, запишем ДПФ (1.1) в виде:

(4.1)

Учитывая, что = получаем

. (4.2)

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

; (4.3)

, (4.4)

где теперь для значений:

Х₀ (п)=х(п) +x(n+N/2); (4.5)

Х₁(п)=х(п) -х(n+N/2). (4.6)

Рисунок 5 - Выполнение базовой операции «бабочка»

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

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

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