Навигация
Алгоритм простых множителей
36424
знака
11
таблиц
11
изображений
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].
7.3 Алгоритм Винограда
Дальнейшей экономии вычислений в случае разложения N на взаимно простые множители можно достичь, если ступенчатый характер объединения частичных мало точечных преобразований заменить вложенным. В этом и заключается идея алгоритма Винограда. Идею вложения мало точечных алгоритмов легче всего понять на примере.
Пример 5. Рассмотрим случай 6-точечного ДПФ, т. е. N=6. Пусть N1=2, N2=3. Приведем сначала алгоритмы мало точечных (2- и 3-точечных) ДПФ, синтезированные оптимальным образом по методу Винограда.
Алгоритм 2-точечного ДПФ
имеет вид
(7.8)
где si-сложения, mi-умножения; Аi и ai - выходные и входные числа.
Алгоритм 3-точечного ДПФ
Имеет вид
, 
, 
, 
, 
(7.9)
, 
, 
Преобразуем исходную 6-точечную последовательность в двумерную точечную в соответствии с (7.5) и (7.6). Тогда матрицу 6-точечного ДПФ можно представить в виде прямого произведения 2- и 3-точечных ДПФ и преобразование можно записать в виде:
, (7.10)
, 
, 
, 
,
Где
Применим к матричному преобразованию (7.10) алгоритм 2-точечного БПФ (7.8). В результате найдем векторы
и 
:
Для вычисления векторов 
и 
используем алгоритм 3-точечного БПФ (7.9).
Таким образом, мы как бы «вложили» алгоритм 3-точечного БПФ в структуру 2-точечного, который оперирует 3-точечными векторами. Характерной особенностью «вложенных» алгоритмов является то, что требуемое число умножений для N-точечного алгоритма равно произведению числа умножений, требуемых для каждого из частичных алгоритмов. Этот факт легко проверяется на приведенном выше алгоритме.
В заключение отметим, что принцип «вложения» малоточечных алгоритмов применяется также для вычисления N-точечных циклических сверток, когда N разлагается на взаимно простые множители, если имеются достаточно эффективные алгоритмы малоточечных сверток. Вложенные алгоритмы циклических сверток получили название по имени авторов алгоритмов Агарвала-Кули [3]. По сравнению с традиционными алгоритмами вычисления свертки с использованием БПФ алгоритмы Агарвала-Кули позволяют сэкономить число умножений почти на порядок.
Другими классами еще более экономных алгоритмов ДПФ и свертки являются алгоритмы, основанные на теоретико-числовых и полиномиальных преобразованиях, с которыми можно познакомиться в [3].
Похожие работы
... учесть введением в блок-схему дополнительного .источника шума [11]. Расстояние между отсчетами должно удовлетворять теореме Найквиста для двумерных колебаний [1]. Устройства для дискретизации и квантования изображений основаны на технике микроденситометрии. В подобных системах на пленку проектируется луч света с интенсивностью I1. Интенсивность I2 света, прошедшего сквозь пленку (или отраженного ...
... Интересным примером применения спецпроцессора СПФ СМ явилась обработка радиолокационных сигналов зондирования поверхности планеты Венера, которое проводилось со спутника. Глава 3. Применение цифровой обработки сигналов. 3.1 Шумоподавление для звука Звуковой сигнал, записываемый в реальных акустических условиях, часто содержит нежелательные шумы, которые могут порождаться окружающей средой ...
... , расположенной напротив одного из ушей, к точке, расположенной перед человеком. Дилэй применяется, прежде всего, в том случае, когда запись голоса или акустического музыкального инструмента, выполненную с помощью единственного микрофона, встраивают в стереофоническую композицию. Этот эффект служит основой технологии создания стереозаписей. Подробные рекомендации по применению задержки в этих ...
... построения оптических систем и сетей связи В результате изучения данной дисциплины студент должен: знать: принципы построения инфокоммуникационных сетей (ПК-1); основные характеристики первичных сигналов связи (ПК-3); принципы построения проводных и радиосистем передачи с частотным и временным разделением каналов (ПК-1); основные характеристики каналов и трактов (ПК-3); принципы построения ...
0 комментариев