Русская Википедия:Алгоритм Гуда — Томаса

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

<math> X(k) = \sum\limits_{j=0}^{n-1} x(j) \omega^{kj}, \; k = 0, \ldots, n-1, </math>

где <math>\omega = e^{-\frac{2\pi i}{n}}</math>.

Пусть <math>n = n_1 n_2</math>, где <math>n_1</math> и <math>n_2</math> взаимно просты. Пусть также <math>j_1</math> и <math>j_2</math> — новые входные индексы, задающиеся соотношениямиШаблон:Sfn

<math>j_1 = j \ (\mbox{mod} \ n_1), \ j_2 = j \ (\mbox{mod} \ n_2).</math>

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

<math> j = j_1 N_2 n_2 + j_2 N_1 n_1 \ (\mbox{mod} \ n)</math>

и <math> N_1 n_1 + N_2 n_2 = 1.</math> Аналогично, пусть <math>k_1</math> и <math>k_2</math> — новые выходные индексы, задающиеся соотношениями

<math>k_1 = N_2 k \ (\mbox{mod} \ n_1), \ k_2 = N_1 k \ (\mbox{mod} \ n_2).</math>

Тогда

<math> k = n_2 k_1 + n_1 k_2 \ (\mbox{mod} \ n). </math>

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

<math> x'(j_1,j_2) = x(j_1 N_2 n_2 + j_2 N_1 n_1), </math>

<math> X'(k_1,k_2) = X(n_2 k_1 + n_1 k_2), </math>

<math> \beta = \omega^{N_2 \left( n_2 \right)^2}, </math>

<math> \gamma = \omega^{N_1 \left( n_1 \right)^2}, </math>

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

<math> 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), </math>

то есть произошёл переход от одномерного преобразования длины <math>n</math> к двумерному преобразованию размера <math>(n_1 \times n_2)</math>. При этом число умножений и число сложений стало равно примерно <math>n(n_1 + n_2)</math>Шаблон:Sfn.

Литература

• Шаблон:Книга