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

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

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

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

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

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

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

Пусть $n=n_{1}n_{2}$, где $n_{1}$ и $n_{2}$ взаимно просты. Пусть также $j_{1}$ и $j_{2}$ — новые входные индексы, задающиеся соотношениями

$j_{1}=j\ ({\mbox{mod}}\ n_{1}),\ j_{2}=j\ ({\mbox{mod}}\ n_{2}).$

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

$j=j_{1}N_{2}n_{2}+j_{2}N_{1}n_{1}\ ({\mbox{mod}}\ n)$

и $N_{1}n_{1}+N_{2}n_{2}=1.$ Аналогично, пусть $k_{1}$ и $k_{2}$ — новые выходные индексы, задающиеся соотношениями

$k_{1}=N_{2}k\ ({\mbox{mod}}\ n_{1}),\ k_{2}=N_{1}k\ ({\mbox{mod}}\ n_{2}).$

Тогда

$k=n_{2}k_{1}+n_{1}k_{2}\ ({\mbox{mod}}\ n).$

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

$x'(j_{1},j_{2})=x(j_{1}N_{2}n_{2}+j_{2}N_{1}n_{1}),$

$X'(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'(k_{1},k_{2})=\sum \limits _{j_{1}=0}^{n_{1}-1}\sum \limits _{j_{2}=0}^{n_{2}-1}\beta ^{j_{1}k_{1}}\gamma ^{j_{2}k_{2}}x'(j_{1},j_{2}),$

то есть произошёл переход от одномерного преобразования длины $n$ к двумерному преобразованию размера $(n_{1}\times n_{2})$. При этом число умножений и число сложений стало равно примерно $n(n_{1}+n_{2})$.

Литература

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