Главная > Разное > Теория и применение цифровой обработки сигналов
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

6.16. Алгоритм Блюстейна

Алгоритм БПФ позволяет существенно уменьшить время вычисления -точечного ДПФ лишь при условии, что число N имеет много сомножителей. Однако существуют и другие эффективные алгоритмы расчета ДПФ последовательностей, также требующие выполнения порядка N log N операций.

К ним относится и алгоритм Блюстейна, применимый при любых N и основанный на цифровой фильтрации, эквивалентной вычислению ДПФ.

Рассмотрим цифровой фильтр с импульсной характеристикой вида

Фильтр с такой импульсной характеристикой обычно навивают ЛЧМ-фильтром из-за его сходства с аналоговым фильтром, согласованным с ЛЧМ-сигналом. При подаче на его вход -точечной последовательности [отсчеты отличны от нуля только на интервале ] выходная последовательность на интервале будет равна

Введя в эту формулу новую переменную , получим

откуда

Из формулы (6.57) следует, что выходная последовательность равна взвешенным (весовые коэффициенты равны ) отсчетам ДПФ -точечной последовательности вида . Следовательно, чтобы получить -точечное ДПФ последовательности , необходимо в соответствии с (6.57) подать на вход фильтра последовательность , а отсчеты выходной последовательности с номерами умножить на весовые коэффициенты эти операции, необходимые для вычисления -точечного ДПФ последовательности , представлены на фиг. 6.25.

Фиг. 6.25. Вычисление -точечного БПФ с помощью линейной фильтрации.

Для некоторых значений N (а именно если N равно квадрату целого числа) количество операций, используемых в цифровом фильтре, может быть пропорционально .

Основной смысл алгоритма Блюстейна состоит в том, что с его помощью показана возможность получения ДПФ последовательности посредством ее линейной фильтрации ЛЧМ-фильтром.

<< Предыдущий параграф Следующий параграф >>
Оглавление