Алгоритм Гуда — Томаса — алгоритм вычисления быстрого преобразования Фурье, применяющийся к последовательностям, длина которых равна произведению двух взаимно простых чисел.
Алгоритм Гуда — Томаса не следует путать с алгоритмом Кули — Тьюки, где делители длины преобразования не обязаны быть взаимно простыми. Алгоритм Гуда — Томаса ограничен этим условием, а также задействует более сложную схему переиндексации, чем алгоритм Кули — Тьюки, но при этом не требует промежуточного умножения на комплексные множители и потому несколько проще с точки зрения вычислений.
Построение алгоритма Для произвольного натурального числа дискретным преобразованием Фурье комплексного вектора , где , называется комплексный вектор , где , компоненты которого задаются формулой
где .
Пусть , где и взаимно просты. Пусть также и — новые входные индексы, задающиеся соотношениями
Отсюда по китайской теореме об остатках и соотношению Безу следует, что существуют такие целые числа и , что
и Аналогично, пусть и — новые выходные индексы, задающиеся соотношениями
Тогда
С использованием обозначений
исходная формула принимает вид
то есть произошёл переход от одномерного преобразования длины к двумерному преобразованию размера . При этом число умножений и число сложений стало равно примерно .
Примечания
Литература
Категория:Преобразование Фурье Категория:Алгоритмы