Чирп-алгоритм

Чирп-алгоритм (алгоритм Блюстейна) — алгоритм вычисления быстрого преобразования Фурье, заключающийся в сведении вычисления дискретного преобразования Фурье к вычислению свёртки.

Для $n\in \mathbb{N}$, $\omega =e^{-\frac{2\pi i}{n}}$, $\beta ={\omega }^{-\frac{1}{2}}$ формула алгоритма выводится из формулы для дискретного преобразования Фурье сигнала $x$ к сигналу $X$ следующим образомШаблон:Sfn:

$X(k)=\sum _{j=0}^{n-1}x(j){\omega }^{kj}=\sum _{j=0}^{n-1}x(j){\beta }^{-2kj}={\beta }^{-k^2}\sum _{j=0}^{n-1}{\beta }^{(j-k{)}^2}({\beta }^{-j^2}x(j)),k=0,\dots ,n-1$.

С использованием обозначений $a(j)=x(j){\beta }^{-j^2}$, $b(j)={\beta }^{j^2}$ можно переписать эту формулу в более компактном виде:

$X(k)=b^{*}(k)(a*b),k=0,\dots ,n-1$.

Здесь верхний индекс ${*}^{}$ означает комплексное сопряжение, а символ $*$ — свёртку. Величины $b(j)$ называются чирпом (Шаблон:Lang-en).

Алгоритм содержит $n$-точечную свёртку, вычисление которой требует $O(n^2)$ операций, и $2n$ дополнительных умножений, то есть полное число операций имеет порядок $O(n^2)$, поэтому алгоритм Блюстайна асимптотически не эффективнее прямого вычисления преобразования Фурье. Однако в некоторых приложениях он допускает более простую аппаратурную реализацию. Более того, прямое вычисление свёртки можно заменить быстрыми алгоритмамиШаблон:Sfn.

Литература

• Шаблон:Книга