Алгоритм Гуда — Томаса

Алгоритм Гуда — Томаса — алгоритм вычисления быстрого преобразования Фурье, применяющийся к последовательностям, длина которых равна произведению двух взаимно простых чисел.

Алгоритм Гуда — Томаса не следует путать с алгоритмом Кули — Тьюки, где делители длины преобразования не обязаны быть взаимно простыми. Алгоритм Гуда — Томаса ограничен этим условием, а также задействует более сложную схему переиндексации, чем алгоритм Кули — Тьюки, но при этом не требует промежуточного умножения на комплексные множители и потому несколько проще с точки зрения вычисленийШаблон:Sfn.

Построение алгоритма

Для произвольного натурального числа $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$ взаимно просты. Пусть также $j_1$ и $j_2$ — новые входные индексы, задающиеся соотношениямиШаблон:Sfn

$j_1=j(\text{mod}{n}_1),j_2=j(\text{mod}{n}_2).$

Отсюда по китайской теореме об остатках и соотношению Безу следует, что существуют такие целые числа $N_1$ и $N_2$, что

$j=j_1{N}_2{n}_2+j_2{N}_1{n}_1(\text{mod}n)$

и $N_1{n}_1+N_2{n}_2=1.$ Аналогично, пусть $k_1$ и $k_2$ — новые выходные индексы, задающиеся соотношениями

$k_1=N_{2}k(\text{mod}{n}_1),k_2=N_{1}k(\text{mod}{n}_2).$

Тогда

$k=n_2{k}_1+n_1{k}_2(\text{mod}n).$

С использованием обозначений

$x^{\prime }(j_1,j_2)=x(j_1{N}_2{n}_2+j_2{N}_1{n}_1),$

$X^{\prime }(k_1,k_2)=X(n_2{k}_1+n_1{k}_2),$

$\beta ={\omega }^{N_2{\left(n_2\right)}^2},$

$\gamma ={\omega }^{N_1{\left(n_1\right)}^2},$

исходная формула принимает вид

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

то есть произошёл переход от одномерного преобразования длины $n$ к двумерному преобразованию размера $(n_1\times n_2)$. При этом число умножений и число сложений стало равно примерно $n(n_1+n_2)$Шаблон:Sfn.

Литература

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