Чирп-алгоритм (алгоритм Блюстейна) — алгоритм вычисления быстрого преобразования Фурье, заключающийся в сведении вычисления дискретного преобразования Фурье к вычислению свёртки.
Для , , формула алгоритма выводится из формулы для дискретного преобразования Фурье сигнала к сигналу следующим образом: .
С использованием обозначений , можно переписать эту формулу в более компактном виде: .
Здесь верхний индекс означает комплексное сопряжение, а символ — свёртку. Величины называются чирпом ().
Алгоритм содержит -точечную свёртку, вычисление которой требует операций, и дополнительных умножений, то есть полное число операций имеет порядок , поэтому алгоритм Блюстайна асимптотически не эффективнее прямого вычисления преобразования Фурье. Однако в некоторых приложениях он допускает более простую аппаратурную реализацию. Более того, прямое вычисление свёртки можно заменить быстрыми алгоритмами.
Примечания
Литература
Категория:Преобразование Фурье Категория:Алгоритмы