7.2 Алгоритм простых множителей

В случае, когда N представимо произведением взаимно простых множителей, имеется возможность избавиться от поворачивающих множителей в разложении (7.4). Тем самым можно достигнуть еще большей экономии числа операций.

Чтобы избавиться от множителей поворота, нужно произвести перестановку входной и выходной последовательностей, отличную от (7.2) и (7.3). Такой перестановкой может быть следующая:

для входной последовательности

(7.5)

n₁.=0,...., N₁-1; п₂=0,..., N₂-1;

для выходной последовательности

(k₁N₂ +k₂)=X((s₁k₂N₁ + s₂k₁N₂)mod N), (7.6)

k₁ =0,..., N₁ -1; k₂ =0,..., N₂ -1,

где запись п mod N означает «остаток от деления п на N», а s₁ и s₂ определяются из следующих уравнений в соответствии с китайской теоремой об остатках о восстановлении целого числа по его вычетам: s₁N₁ = 1mod N₂, s₁<N₂, s₂N₂ == 1modN₁, s₂ <N₁. Тогда алгоритм N=N₁N₂ - точечного ДПФ представляется в виде

Таким образом, алгоритм простых множителей (АПМ) является способом представления одномерного ДПФ в виде многомерного, причем размерность зависит от числа взаимно простых сомножителей N. Алгоритм простых множителей имеет ступенчатую форму объединения мало точечных преобразований. В данном случае на первой ступени производится N₁N₂-точечных ДПФ, а на второй ступени - N₂ N₁-точечных ДПФ.

Впервые АПМ был предложен Гудом [3]. В том случае, когда используемые мало точечные алгоритмы синтезированы оптимальным образом по методу Винограда, получается алгоритм Гуда - Винограда [3]. Оптимальные мало точечные алгоритмы БПФ синтезируются путем сведения мало точечного ДПФ к совокупности циклических сверток. Для последних Виноградом [2] доказана теорема о существовании алгоритма вычисления с минимальным количеством умножений и был предложен метод синтеза, основанный на последовательном вычислении полиномиальных вычетов по неприводимым полиномам в поле рациональных чисел в соответствии с полиномиальным вариантом китайской теоремы об остатках [3].