Алгоритм Блуштайна

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

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

${\displaystyle 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.}$

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

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

Здесь верхний индекс ${\displaystyle ^{*}}$ означает комплексное сопряжение, а символ ${\displaystyle *}$ — свёртку.

Величины ${\displaystyle b(j)}$ иногда называются чирпом (англ. chirp), откуда происходит второе название алгоритма.

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

Например, с помощью теоремы о свёртке можно заменить вычисление свёртки на вычисление двух дискретных преобразований Фурье, каждое из которых можно вычислить быстрым алгоритмом, к примеру, методом Кули-Тьюки и, таким образом, обеспечить выполнение алгоритма Блюстайна с вычислительной сложностью ${\displaystyle O(n\log n)}$. Величины ${\displaystyle b(j)}$ и их преобразование Фурье также можно вычислить заранее и записать в память для последующего многократного использования.