Быстрое преобразование Фурье

В соответствии с формулой прямого ДПФ для определения N значений X[k] требуется выполнить примерно N2 умножений и N2 сложений. С ростом N… Рассмотрим алгоритмы БПФ с основанием 2, которые применяются к… Основная идея БПФ состоит в следующем. Последовательность x[n] разбивают на две последовательности x1[n] и x2[n]…

Так как , то

. Здесь выражения в фигурных скобках представляют прямые ДПФ от последовательностей x1[n] и x2[n], половинной длины

Важной особенностью рассматриваемых алгоритмов БПФ является необходимость перестановки входных или выходных значений. Элементы входной последовательности для алгоритма с прореживанием по времени должны быть расположены в памяти в бит–инверсном порядке. Бит–инверсный порядок задается путем «зеркального» отображения двоичных разрядов входной последовательности (табл.1.3).

Бит-инверсный порядок Таблица 1.3.

N	Двоичный номер	бит инверсия	бит-инверсный номер

На всех этапах выполнения БПФ используются коэффициенты WNk, k=0,1,…N-1. Обычно указанные значения вычисляют до выполнения БПФ и хранят в таблице, к которой можно обращаться в процессе счета.

Количество этапов в процессе вычисления БПФ равно log2N, количество “бабочек” на каждом этапе - N/2. Так как в процессе БПФ используются комплексные числа, то каждая «бабочка» БПФ сопровождается четырьмя операциями умножения и четырьмя операциями сложения. Поэтому количество парных операций умножение-сложение равно 2N log2N. При больших N применение алгоритма БПФ существенно сокращает количество операций по сравнению с ДПФ.

Линейные дискретные системы и цифровые фильтры

Важную роль в цифровой обработке сигналов играют линейные дискретные системы. Такие системы преобразуют входную последовательность x[n] в выходную… а) сумматора последовательностей (рис. 1.27,а). ; (01)

Рис. 1.29. Структурная схема рекурсивного цифрового фильтра

Если в уравнении (11) все коэффициенты a[k]=0, то

. (12)

Фильтр, функционирующий на основе уравнения (12), называется нерекурсивным фильтром (НРФ) и имеет конечную длительность импульсной характеристики. Такие фильтры также называют фильтрами с конечной импульсной характеристикой (КИХ-фильтрами). Фильтры, реализующие (11), характеризуются бесконечной импульсной характеристикой и называются БИХ-фильтрами. Из (12) и (07) следует, что для НРФ b[k]=h[k], т.е. коэффициенты КИХ-фильтра совпадают с отсчетами его импульсной характеристики.