Войти
алгоритм простых множителей (PFA), также называемый алгоритмом Гуда – Томаса (1958/1963), представляет собой алгоритм быстрого преобразования Фурье (БПФ), который повторно выражает дискретное преобразование Фурье (ДПФ) размера N = N 1N2как двумерное al N 1×N2DFT, но только для случая, когда N 1 и N 2 являются относительно простыми. Эти более мелкие преобразования размера N 1 и N 2 затем могут быть оценены путем применения PFA рекурсивно или с помощью какого-либо другого алгоритма БПФ.
PFA не следует путать с смешанным основанием обобщением популярного алгоритма Кули – Тьюки, который также разделяет ДПФ размером N = N 1N2в более мелкие преобразования размера N 1 и N 2. Последний алгоритм может использовать любые множители (не обязательно относительно простые), но его недостаток состоит в том, что он также требует дополнительных умножений на корни из единицы, называемых множителями, в дополнение к меньшим преобразованиям. С другой стороны, PFA имеет недостатки, заключающиеся в том, что он работает только для относительно простых факторов (например, он бесполезен для размеров степени двойки ) и что он требует более сложной переиндексации данных на основе по китайской теореме об остатках (CRT). Обратите внимание, однако, что PFA можно комбинировать со смешанным основанием Кули – Тьюки, при этом первый факторизует N на относительно простые компоненты, а второй обрабатывает повторяющиеся множители.
PFA также тесно связана с вложенной структурой, где последняя выполняет преобразование разложенного N 1 на N 2 с помощью более сложных методов двумерной свертки. Поэтому в некоторых более старых работах алгоритм Винограда также называется PFA FFT.
(Хотя PFA отличается от алгоритма Кули-Тьюки, работа Good 1958 года над PFA была названа источником вдохновения Кули и Тьюки в их статье 1965 года, и первоначально некоторая путаница в отношении того, были ли эти два алгоритма разными. Фактически, это была единственная предыдущая работа по БПФ, на которую они ссылались, поскольку они тогда не знали о более ранних исследованиях Гаусса и других.)
Напомним, что ДПФ определяется формулой:
PFA включает повторную индексацию входных данных и выходные массивы, которые при подстановке в формулу ДПФ преобразуют его в два вложенных ДПФ (двумерное ДПФ).
Предположим, что N = N 1N2, где N 1 и N 2 являются относительно простыми. В этом случае мы можем определить биективную переиндексацию входа n и выхода k следующим образом:
где N 1 обозначает модульную мультипликативную инверсию для N 1по модулю N2и наоборот для N 2 ; индексы k a и n a начинаются с 0,…, N a - 1 (для a = 1, 2). Эти инверсии существуют только для относительно простых N 1 и N 2, и это условие также требуется для того, чтобы первое отображение было биективным.
Это повторное индексирование n называется руритановским отображением (также отображением Гуда), в то время как такое повторное индексирование k называется отображением CRT. Последнее относится к тому факту, что k является решением китайской проблемы остатка k = k 1 mod N 1 и k = k 2 mod N 2.
(Вместо этого можно было бы использовать руритановское отображение для выхода k и отображение CRT для входа n или различные промежуточные варианты.)
Схемам для оценки этой переиндексации было посвящено большое количество исследований. эффективно, в идеале на месте, сводя к минимуму количество дорогостоящих операций по модулю (остатку) (Chan, 1991 и ссылки).
Вышеупомянутая переиндексация затем подставляется в формулу для ДПФ и, в частности, в произведение nk в экспоненте. Поскольку e = 1, этот показатель оценивается по модулю N: любой перекрестный член N 1N2= N в произведении nk может быть установлен равным нулю. (Аналогично, X k и x n неявно периодичны по N, поэтому их индексы оцениваются по модулю N.) Остальные члены дают:
Внутренняя и внешняя суммы - это просто ДПФ размера N 2 и N 1 соответственно.
(Здесь мы использовали тот факт, что N 1N1равно единице при вычислении по модулю N 2 в показателе внутренней суммы, и наоборот для показателя внешней суммы.)
