Алгоритм Кули — Тьюки

Алгоритм Ку́ли — Тью́ки — наиболее часто используемый алгоритм вычисления быстрого преобразования Фурье. Алгоритм позволяет выразить дискретное преобразование Фурье длины, равной произвольному составному числу $N$, через определённое количество преобразований меньшей длины с помощью рекурсии, понижая таким образом сложность вычислений до $O(N\log N)$ для гладких $N$. Назван в честь Шаблон:Нп3 и Дж. Тьюки.

Основной алгоритм

Схема общего алгоритма Кули — Тьюки

Для произвольного натурального числа $N$ дискретным преобразованием Фурье комплексного вектора $x(j)$, где $j=0,\dots ,N-1$, называется комплексный вектор $X(k)$, где $k=0,\dots ,N-1$, компоненты которого задаются формулой

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

где $\omega =e^{-\frac{2\pi i}{N}}$.

Для построения алгоритма делается предположение, что $N=N_1{N}_2$ для некоторых натуральных $N_1$ и $N_2$ и производится следующая замена индексовШаблон:Sfn:

$\begin{array}{cccc}& j=j_1+N_1{j}_2,& j_1=0,\dots ,N_1-1,& j_2=0,\dots ,N_2-1,\\ & k=k_2+N_2{k}_1,& k_1=0,\dots ,N_1-1,& k_2=0,\dots ,N_2-1,\end{array}$

в результате которой получается

$X(k_2+N_2{k}_1)=\sum _{j_1=0}^{N_1-1}\sum _{j_2=0}^{N_2-1}x(j_1+N_1{j}_2){\omega }^{(j_1+N_1{j}_2)(k_2+N_2{k}_1)}.$

Далее векторы входных и выходных данных преобразуются в двумерные массивы $x^{\prime }$ и $X^{\prime }$, задающиеся равенствами

$\begin{array}{cccc}& x^{\prime }(j_1,j_2)=x(j_1+N_1{j}_2),& j_1=0,\dots ,N_1-1,& j_2=0,\dots ,N_2-1,\\ & X^{\prime }(k_1,k_2)=X(k_2+N_2{k}_1),& k_1=0,\dots ,N_1-1,& k_2=0,\dots ,N_2-1.\end{array}$

Стоит заметить, что компоненты $X$ упорядочены не так, как компоненты $x$.

Далее пусть ${\omega }^{N_1}=\gamma$ и ${\omega }^{N_2}=\beta$. Очевидно, что ${\omega }^{N_1{N}_2{j}_2{k}_1}=1$. Тогда в терминах двумерных переменных формула преобразуется к видуШаблон:Sfn

$X^{\prime }(k_1,k_2)=\sum _{j_1=0}^{N_1-1}{\beta }^{j_1{k}_1}({\omega }^{j_1{k}_2}\sum _{j_2=0}^{N_2-1}{x}^{\prime }(j_1,j_2){\gamma }^{j_2{k}_2}).$

Таким образом, вычисление преобразования длины $N=N_1{N}_2$ сводится к выполнению следующих действий:

1. Вычисление $N_1$ преобразований длины $N_2$.
2. Умножение на комплексные «поворачивающие» множители.
3. Вычисление $N_2$ преобразований длины $N_1$.

При этом вместо $N^2$ комплексных сложений и $N^2$ комплексных умножений исходной формулы итоговая схема содержит не более $N(N_1+N_2-2)$ комплексных сложений и $N(N_1+N_2+1)$ комплексных умноженийШаблон:Sfn.

Каждое из преобразований длины $N_1$ или $N_2$ можно вычислять с помощью различных быстрых алгоритмов, в частности, снова по вышеприведённой схеме. В этом случае преобразование длины $N=\prod _{i=1}^n{N}_i$ может быть представлено в форме, требующей выполнения $N\sum _{i=1}^n{N}_i$ комплексных умноженийШаблон:Sfn.

Алгоритм по основанию два

Во многих приложениях длина преобразования равна степени двойки: $N=2^m$. Тогда в вышеприведённой схеме возможны варианты $N_1=2$ или $N_2=2$. В этом случае говорят об алгоритме Кули — Тьюки по основанию дваШаблон:Sfn (Шаблон:Lang-en).

Если $N_1=2$, то говорят об алгоритме Кули — Тьюки с прореживанием по времениШаблон:Sfn. В этом случае уравнения преобразуются к виду

$\begin{array}{ccc}X(k)& =& \sum _{j=0}^{N/2-1}x(2j){\omega }^{2kj}+{\omega }^k\sum _{j=0}^{N/2-1}x(2j+1){\omega }^{2kj}\\ X(k+N/2)& =& \sum _{j=0}^{N/2-1}x(2j){\omega }^{2kj}-{\omega }^k\sum _{j=0}^{N/2-1}x(2j+1){\omega }^{2kj},k=0,\dots ,N/2-1.\end{array}$

Схема реализации операции «бабочки»

Если ввести обозначения $E(k)=\sum _{j=0}^{N/2-1}x(2j){\omega }^{2kj}$ и $O(k)=\sum _{j=0}^{N/2-1}x(2j+1){\omega }^{2kj}$, то уравнения можно переписать как

$\begin{array}{ccc}X(k)& =& E(k)+{\omega }^{k}O(k)\\ X(k+N/2)& =& E(k)-{\omega }^{k}O(k),k=0,\dots ,N/2-1.\end{array}$

Такая операция обычно называется «бабочкой».

Данная процедура может быть применена к входному вектору рекурсивно. На каждом шаге $N$-точечное преобразование разбивается на два $(N/2)$-точечных преобразования, которые, в свою очередь, разбиваются таким же образом до тех пор, пока длина преобразования не станет равна единице. Затем происходит обратный ход, на каждом шаге длины результатов преобразований удваиваются с помощью «бабочек». При такой реализации выполняется $(N/2){\log }_{2}N$ комплексных умножений и $N{\log }_{2}N$ комплексных сложений.

Этот процесс является примером применения методики «разделяй и властвуй». При этом во многих реализациях прямой рекурсии избегают и вместо неё дерево вычислений проходится в порядке поиска в ширину.

Если $N_2=2$, то говорят об алгоритме Кули — Тьюки с прореживанием по частотеШаблон:Sfn. В этом случае уравнения преобразуются к виду

$\begin{array}{ccc}X(2k)& =& \sum _{j=0}^{N/2-1}(x(j)+x(j+N/2)){\omega }^{2kj},\\ X(2k+1)& =& \sum _{j=0}^{N/2-1}(x(j)-x(j+N/2)){\omega }^{j(2k+1)},k=0,\dots ,N/2-1.\end{array}$

Алгоритм Рейдера — Бреннера

Пусть

$a(k)=\{\begin{array}{cc}0,& k=0,\\ \frac{x(k)-x(k+N/2)}{2i\sin (2\pi k/N)},& k=1,\dots ,N/2-1\end{array}$

и пусть

$A(k)=\sum _{j=0}^{N/2-1}a(j){\omega }^{2kj},k=0,\dots ,N/2-1.$

С использованием формул алгоритма с прореживанием по частоте нетрудно убедиться, что выполняется следующее соотношение:

$X(2k+1)=A(k)-A(k+1)+(x(0)-x(N/2)),k=0,\dots ,N/2-1.$

Такая модификация алгоритма по основанию два называется алгоритмом Рейдера — Бреннера. Она позволяет уменьшить вычислительную сложность за счёт более простых умножений на чисто мнимые константы $1/(2i\sin (2\pi k/N))$Шаблон:Sfn. Аналогичные формулы можно получить с использованием вещественных констант $1/(2\cos (2\pi k/N))$Шаблон:Sfn.

История

Алгоритм и его рекурсивная реализация были изобретены около 1805 года К. Гауссом при интерполировании траекторий астероидов Паллада и Юнона. Тогда открытие не получило широкого распространения и было опубликовано лишь после смерти учёного на новой латыни. Результат Гаусса несколько раз переоткрывался в различных формах в течение последующих 150 лет и стал популярным после публикации в 1965 году статьи Шаблон:Нп3 из IBM и Дж. Тьюки из Принстона, в которой алгоритм был в очередной раз переоткрыт, а также описывалась удобная реализация для ЭВМ.

Тот факт, что первооткрывателем алгоритма является Гаусс, был обнаружен лишь через несколько лет после публикации Кули и Тьюки. В своей статье они ссылались только на работу И. Дж. Гуда, в которой был описан алгоритм Гуда — Томаса.

Выражение преобразования Фурье длины $N$ через два преобразования длины $N/2$ иногда называют леммой Шаблон:Нп3 — Ланцоша, так как оно было получено этими двумя авторами в 1942 году.

Литература

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

См. также

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