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

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

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

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

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

$X(k)=b^{*}(k)\left(a*b\right),\;k=0,\ldots ,n-1$.

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

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

Литература

• Блейхут Р.. Быстрые алгоритмы цифровой обработки сигналов (рус.). — М.: Мир, 1989. — 448 с.