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

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

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

$X(k)=\underset{j=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{\mathrm{\omega <!--\; \omega \; -->}}^{kj}x(j)$$X(k)=\sum \limits _{j=0}^{n-1}\omega ^{kj}x(j)$.

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

$X(k)=\underset{j=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{\mathrm{\omega <!--\; \omega \; -->}}^{kj}x(j)=\underset{j=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{\mathrm{\beta <!--\; \beta \; -->}}^{-<!--\; -\; -->2kj}x(j)={\mathrm{\beta <!--\; \beta \; -->}}^{-<!--\; -\; -->k^2}\underset{j=0}{\overset{n-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}{\mathrm{\beta <!--\; \beta \; -->}}^{(j-<!--\; -\; -->k{)}^2}({\mathrm{\beta <!--\; \beta \; -->}}^{-<!--\; -\; -->j^2}x(j)),k=0,\dots <!--\; \dots \; -->,n-<!--\; -\; -->1$$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$.

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

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

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

$X(k)=b^{\ast <!--\; \ast \; -->}(k)\left(a\ast <!--\; \ast \; -->b\right),k=0,\dots <!--\; \dots \; -->,n-<!--\; -\; -->1$$X(k)=b^{*}(k)\left(a*b\right),\;k=0,\ldots ,n-1$

Величину $b(j)$$b(j)$ здесь называют чирпом (англ. chirp).

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

Например, с помощью теоремы о свёртке^[en] можно заменить вычисление свёртки на вычисление двух дискретных преобразований Фурье, каждое из которых можно вычислить быстрым алгоритмом, к примеру, методом Кули — Тьюки и, таким образом, обеспечить выполнение алгоритма Блюстайна с вычислительной сложностью $O(n\log <!--\; \; -->n)$$O(n\log n)$. Величины $b(j)$$b(j)$ и их преобразование Фурье также можно вычислить заранее и записать в память для последующего многократного использования.

ЛитератураПравить

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