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

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

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

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

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

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

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

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

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

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

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

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

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

Тогда

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

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

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

${\displaystyle X'(k_{1},k_{2})=X(n_{2}k_{1}+n_{1}k_{2}),}$

${\displaystyle \beta =\omega ^{N_{2}\left(n_{2}\right)^{2}},}$

${\displaystyle \gamma =\omega ^{N_{1}\left(n_{1}\right)^{2}},}$

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

${\displaystyle 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}),}$

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

Примечания

1. Блейхут, 1989, с. 141.
2. Блейхут, 1989, с. 142.
3. Блейхут, 1989, с. 143.

Литература

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