Алгоритм фильтрации, пример на основе БПФ

реферат

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

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

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

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

(7.5)

n1.=0,...., N1-1; п2=0,..., N2-1;

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

(k1N2 +k2)=X((s1k2N1 + s2k1N2)mod N), (7.6)

k1 =0,..., N1 -1; k2 =0,..., N2 -1,

где запись п mod N означает «остаток от деления п на N», а s1 и s2 определяются из следующих уравнений в соответствии с китайской теоремой об остатках о восстановлении целого числа по его вычетам: s1N1 = 1mod N2, s1<N2, s2N2 == 1modN1, s2 <N1. Тогда алгоритм N=N1N2 - точечного ДПФ представляется в виде

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

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

Делись добром ;)