Алгоритм Гуда — Томаса (Glikjnmb Ir;g — Mkbgvg)

Перейти к навигации Перейти к поиску

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

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

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

[править | править код]

Для произвольного натурального числа дискретным преобразованием Фурье комплексного вектора , где , называется комплексный вектор , где , компоненты которого задаются формулой

где .

Пусть , где и взаимно просты. Пусть также и — новые входные индексы, задающиеся соотношениями[2]

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

и Аналогично, пусть и — новые выходные индексы, задающиеся соотношениями

Тогда

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

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

то есть произошёл переход от одномерного преобразования длины к двумерному преобразованию размера . При этом число умножений и число сложений стало равно примерно [3].

Примечания

[править | править код]

Литература

[править | править код]
  • Блейхут, Р.. Быстрые алгоритмы цифровой обработки сигналов. — М.: Мир, 1989. — 448 с.