6.16. Алгоритм Блюстейна
Алгоритм БПФ позволяет существенно уменьшить время вычисления 
-точечного ДПФ лишь при условии, что число N имеет много сомножителей. Однако существуют и другие эффективные алгоритмы расчета ДПФ последовательностей, также требующие выполнения порядка N log N операций.
К ним относится и алгоритм Блюстейна, применимый при любых N и основанный на цифровой фильтрации, эквивалентной вычислению ДПФ.
Рассмотрим цифровой фильтр с импульсной характеристикой 
вида
Фильтр с такой импульсной характеристикой обычно навивают ЛЧМ-фильтром из-за его сходства с аналоговым фильтром, согласованным с ЛЧМ-сигналом. При подаче на его вход 
-точечной последовательности 
[отсчеты 
отличны от нуля только на интервале 
] выходная последовательность 
на интервале 
будет равна
Введя в эту формулу новую переменную 
, получим
откуда
Из формулы (6.57) следует, что выходная последовательность 
равна взвешенным (весовые коэффициенты равны 
) отсчетам ДПФ 
-точечной последовательности вида 
. Следовательно, чтобы получить 
-точечное ДПФ последовательности 
, необходимо в соответствии с (6.57) подать на вход фильтра последовательность 
, а отсчеты выходной последовательности 
с номерами 
умножить на весовые коэффициенты 
эти операции, необходимые для вычисления 
-точечного ДПФ последовательности 
, представлены на фиг. 6.25.
Фиг. 6.25. Вычисление 
-точечного БПФ с помощью линейной фильтрации.
Для некоторых значений N (а именно если N равно квадрату целого числа) количество операций, используемых в цифровом фильтре, может быть пропорционально 
.
Основной смысл алгоритма Блюстейна состоит в том, что с его помощью показана возможность получения ДПФ последовательности посредством ее линейной фильтрации ЛЧМ-фильтром.
