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

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

Если на некотором поле относительно операции умножения существует элемент ${\displaystyle \omega }$ порядка ${\displaystyle n}$ (т.е. равным корню ${\displaystyle n}$ порядка от единицы. В поле комплексных чисел обычно используется ${\displaystyle e^{-{\frac {2\pi i}{n}}}}$), тогда для него определено дискретное преобразование Фурье вида

${\displaystyle X(k)=\sum \limits _{j=0}^{n-1}\omega ^{kj}x(j)}$.

Если теперь ввести замену вида ${\displaystyle \beta =\omega ^{-{\frac {1}{2}}}}$, то от дискретного преобразования Фурье можно перейти к свёртке сигнала ${\displaystyle x}$ следующим образом^[1]:

${\displaystyle X(k)=\sum \limits _{j=0}^{n-1}\omega ^{kj}x(j)=\sum \limits _{j=0}^{n-1}\beta ^{-2kj}x(j)=\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)=\beta ^{-j^{2}}x(j)}$, ${\displaystyle b(j)=\beta ^{j^{2}}}$ можно переписать эту формулу в более компактном виде:

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

Здесь символ ${\displaystyle *}$ означает свёртку. В поле комплексных чисел при ${\displaystyle \omega =e^{-{\frac {2\pi i}{n}}}}$ обратный элемент ${\displaystyle b^{-1}}$ можно заменить комплексно-сопряжённым ${\displaystyle b^{*}}$, получив выражение

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

Величину ${\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)}$ и их преобразование Фурье также можно вычислить заранее и записать в память для последующего многократного использования.