Конспект лекций по цос

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-точечного БПФ
с замещением и прореживанием по частоте

4. ПРИМЕНЕНИЕ МЕТОДА БПФ ДЛЯ ВЫЧИСЛЕНИЯ ОДПФ

По определению (12.2) ОДПФ x(n) N-точечной последовательности X(k), k = 0, 1, …, N – 1, выражается соотношением
x(n) = , (19)
причем в общем случае и x(n), и x(k) — комплексные функции. Пусть x(n) и X(k) — последовательности, комплексно сопряженные соответственно с x(n) и X(k). Согласно (12.19) можно записать
x^*(n) = , (20)
Выражение суммы в правой части (12.20) есть прямое ДПФ последовательности X^*(k), k = 0, ...., N – 1 и, следовательно, эта сумма может быть вычислена при помощи рассмотренных алгоритмов и программ БПФ.
Таким образом, обеспечивается вычисление последовательности Nx^*(n) и для определения x(n) остается взять комплексно сопряженное с Nx^*(n) выражение и разделить его на N:
(21)

12.5. ПРИМЕНЕНИЕ БПФ ДЛЯ ВЫЧИСЛЕНИЯ РЕАКЦИИ ЦИФРОВОГО ФИЛЬТРА

Вычисление реакции y(n) ЦФ с импульсной характеристикой
h(n), n = 0, 1, ..., N – 1,
на входное воздействие x(n), n = 0, 1, ..., М – 1, может быть выполнено, на основе алгоритма свертки
y(n) = (22)
при n = 0, 1, …, N + M – 2.
Применение алгоритмов БПФ позволяет выполнить эффективное вычисление выходной последовательности y(n) ЦФ. С этой целью следует определить ДПФ H(k) и X(k) в N + M – 1 точках для последовательностей h(n) и x(n), затем определить ДПФ Y(k) = H(k)X(k) выходной последовательности y(n). Вычисление y(n) по ОДПФ Y(k) выполняется, например, но алгоритму (12.21). Для вычисления ДПФ и ОДПФ используются алгоритмы БПФ. Отметим, что при большой длине M последовательности x(n) реализация упомянутого выше алгоритма вычисления y(n) связана со значительной временной задержкой – для накопления всех М выборок x(n). Для уменьшения этой задержки входную последовательность x(n) можно разбить на отрезки x_i(n)