Гольденберг Л.М., Матюшкин Б.Д., Поляк М.Н. Цифровая обработка сигналов (2-е изд., 1990) (1245704), страница 25
Текст из файла (страница 25)
Отметим, что алгоритмы с основанием 2 также могут быть получены с использованием рассмотренного подхода. Таким образом, рассмотренный метод синтеза является общим и позволяег синтезировать различные модификации алгоритма Кули — Тычки с произвольными постоянным н смешанным основаниями. Алгоритм простых множителей. В случае, когда Ж представимо произведением взаимно простых множителей, имеется возможность 135 избавиться от поворачивающих множителей в разложении (5.29). Тем самым можно достигнуть еще большей экономии числа операций. Чтобы избавиться от множителей поворота, нужно произвести перестановку входной и выходной последовательностей, отличную от (5.27) и (5.28). Такой перестановкой может быть следующая: для входной последовательности Я(пз Л/а+ па) = х((па Лгз + пз Лсз) тос) ЛС), (5.
30) пз =О, ..., Лгз — 1; п,=О, ..., Л(з — !; для выходной последовательности Х(/с з Лз+/сз) = Х((хз/сзЛ)г+ тз/сз Лгз) шос) Л), /сз =О, ..., Лгз — 1; /сз = О, ..., Лгз-1, (5.3 1) где запись п тос! Л/ означает «остаток от деления п на Л'», а з, и с, определяются из следующих уравнений в соответствии с китайской теоремой об остатках о восстановлении целого числа по его вычетам: узЛгз = 1 пзос( Л(з, з! < Лгз т,Лгз= — 1 тос! Лг„аз < Лгз.
Тогда алгоритм Лг=ЛгзЛгз-точечного ДПФ представляется в виде в,-! и -з 3 х)з,%~-з,1= х ( х *1,а,.!-,)в'„"")о„.". (5ззз .,=о х„=о Таким образом, алгоритм просгых множителей (АПМ) является способом представления одномерного ДПФ в виде многомерного, причем размерность зависит от числа взаимно простых сомножителей Лг, Алгоритм простых множителей имеет ступенчатую форму объединения малоточечных преобразований. В данном случае на первой ступени производится Лз, Лг;точечны ДПФ, а на второй ступени — -Л/з Лгз-точечных ДПФ. Впервые АПМ был предложен Гудом [1! ).
В том случае, когда используемые малоточечные алгоритмы синтезировань оптимальным образом по методу Винограда, получается алгоритм Гуда- Винограда [11]. Оп гимальные малоточечпые алгоритмь БПФ син!езируются путем сведения малоточечного ДПФ к совокупности циклических сверток. Для последних Виноградом [2 доказана теорема о существовании алгоритма вычисления с минимальным количеством умножений и был предложен мето синтеза, основанный ца последовательном вычислении полипоми альных вычетов по неприводимым полиномам в поле рациональ ных чисел в соответствии с полиномиальным вариантом китай ской зеоремы об остатках [11).
Алгоритм Винограда. Дальнейшей экономии вычислений в слу чае разложения Л( на взаимно простые множители можно достичь если ступенчатый характер объединения частичных малоточечны 136 преобразований заменить вложенным. В этом и заключается идея алгоритма Винограда. Идею вложения малоточечных алгоритмов легче всего понять на примере. имеет вид з! =по+ам зз — ао — ао аз о = И з з .
аз з = и'з з,. ~ о о. Ао=лзо. Аз=зло (5.33) ~де зз — сложения, ю,— умножения; А, и а; —. выходные и входные числа. Люоритм 3-гочечного ДПФ А з = Игзз К Игзз а нмсст вил з,=а,-а„ 2я пзз = соз — — 1 з„ 3 зз=з Ч-ао, хз =по,-а„ пзо= Из аз, о 2н азз =/з!и — хз, 3 (5,34) хо = взо 6 лз,, Ао = »зо.
хз=зоз-гпз, Аз=аз, .зо = з, — азз. Аз=хо Преобразуем исходную 6-точечную последовательность в двумерную 2 хЗ- зочсчную в соогвезсз вин с (5.30) и (5.3!), Тогла матрицу 6-точечного ДПФ можно представить в виде прямо~о произведения 2- и 3-точечных ДПФ и преобразование можно записать в види (535) Хо= Х(2), Хз = Х(З) . хо = х(2), Хз= х(3) где "'з н'з и'3 Из= "з "з зез ,о ,о .2,! жз и'з в'з 137 Пример 5,5.
Рассмотрим случай 6-точечного ДПФ, т. е, Лс=б. Пусть %, =2, пз = 3. Приведем сначала алгоритмы малоточечных (2- и 3-точечных) ДПФ, синтезиронанные оптимальным образом по методу Винограда. Ллгоритм 2-точечного ДПФ Применим к матричному преобразованию ~5.35) алгоритм 2-точечного БПФ (5.33). В результате найдем векторы Хо и Х,: .гг=хео+.х«1, Х=хко-х«1, Мо вг Н зги Н зп Мги1 И згг= )г~ззг, ,о .о Хо=мо, Х,=М,. Для вычисления векторов Мо и Мг используем алгоритм 3-точечного БПФ (5.34).
Таким образом, мы как бы «вложили» алгоритм 3-точечного БПФ в структуру 2-точечного, который оперирует 3-точечными векторами. Характерной особенностью «вложецных» алгоритмов является то, что требуемое число умножений для А/-точечного алгоритма равно произведению числа умножений, требуемых для каждого из частичных алгоритмов. Этот факт легко проверяется на приведенном выше алгоритме.
В заключение отметим, что принцип «вложения» малоточечных алгоритмов применяется также для вычисления А/-точечных циклических сверток, когда А/ разлагается на взаимно простые множители, если имеются достаточно эффективные алгоритмы малоточечных сверток.
Вложенные алгоритмы циклических сверток получили название по имени авторов алгоритмов Агарвала— Кули [11]. По сравнению с традиционными алгоритмами вычисления свертки с использованием БПФ алгоритмы Агарвала— Кули позволяют сэкономить число умножений почти на порядок. Другими классами еще более экономных алгоритмов ДПФ и свертки являются алгоритмы, основанные на теоретико-числовых и полиномиальных преобразованиях, с которыми можно познакомиться в [!1]. 5.8.
АНАЛИЗ ТОЧНОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ БПФ При реализации алгоритма БПФ, как и при реализации других алгоритмов ЦОС, возникают вычислительные ошибки, обусловленные (см. гл. 2) округлением (уссчснием) произведений, квантованием коэффициентов и, возможно, процедурой масштабирования чисел (с целью устранения переполнения сумматоров). При анализе ошибок будем принимать упомянутые в гл. 2 допущения об их характере, т. е. будем рассчитывать выходную ошибку БПФ как суперпозицию ошибок, вызванных каждым независимым источником ошибок. Методику оценки вычислительных ошибок БПФ рассмотрим на примере .
реализации БПФ по основанию 2 и с прореживанием по времени. Рассматриваемая методика может быть применена и для анализа ошибок других алгоритмов БПФ. Будем предполагать, что: обрабатываемые числа представляются с помощью Ь,+1 разрядов, а козффициснпл — с помощью Ь,+1 разрядов с учетом знака; для аппроксимации произведений используется операция округления; масштабирование промежуточных результатов производится на входе каждой операции 138 «бабочка» путем сдвига чисел на один разряд вправо (деление на два); входные ланныс нронормированы гаким образом, что ! х(пТ)1= ! х(п)! < 1, и полчиняются равномерному закону распределения, т. е.
имеют математическое ожидание, равное нулю, н дисперсию и„', равную 1/3. Следовательно, срсднеквадратическое значение (СКЗ) вхолной последовательности равно также 1,'3. В соответствии с теоремой Парссваля п 1 1«-1 Е (х(п)1'= — Е (Х(й)1' =о 1У г-о выходная посясдоватсльность Х(/г) БПФ булет иметь СКЗ гг//3, где гз/ размер преобразования, С целью уяснения методики анализа ошибок получим алгоритм БПФ в аналитическом виде. Для этого в выражение для /г/=2'-точечного ДПФ (5.1) и Х(Ь) = ~ х(п) е ", /г = О, ..., /У- 1, (5.36) -о нсобхолимо подставить двоичное разложение коэффициензов и н /г: п=п,2" '-~п,. 12" и ...
+и„) /1 /1 2 — 1+/г 2 -г( 1/1 по /гг = О, 1. (5.37) Хо(п,2' ' < п,2' ' + ... + и,) =к(п 2" ' -~ п,,2" ' + ... -1 и, ). На каждой из остальных о ступеней (пг=(. 2, ..., о) произволится преобразование тина «бабочка» выходной последовательности прслылушей ступени, Так, на ступени пг= 1 производится преобразование последовательности Хо (и о ....
гг„ ).' Хг(пг, ..., и,—,,/гг)= х/ Хо(п„..., и.—,, п„)е ь=о На сзупсни пг=2 преобразование послеловательности Х,(п,, ..., и„„/11) 1 11«г г«,1 Хг(пг ... п„-г, /гг, /11)= ~ Х1(п1 ... п 1, /11)с ,-о На пг-й ступени Х„(п „..., и„„, /г„... /З ) = 1 м Х 1(пг, „и„„ /г 1...,. Х1)с г" ' " .,-о [5.
38) Гак постепенно в двоичном представлении индекса последовательности Х с увеличением пг происхолнт замена коэффициентов и; на /1» Наконец, нри пг=о 1 г« х,(/г„..., й1)= 2. Х,-1(п1./1, 1, -,/11)с г' ' 139 В результате алгоритм БПФ можно прелставнзь. как ранее убелились, в виде о 1-1-ступенчатого процесса. На ступени г»=О производится двончно-инверсная перестановка входной нослеловательности т У Х! /п) -Х Хг /л) и у Х/и) у т / Х, /и) Хс'и) (5.39) гу =о «,=о «,=о,-о хс Рис. 5.5 Искомая вь!холная последовательность !4! Выхолная послеловательносгь послелней ступени является искомой: Х(Х) = Х(/с„2" ' 4 ...
+/с ) = Х„(/с„2' '+/с„2"" 2+ ... 4 й ). Представим индекс элемента т-й ступени в виде (л,, ..., и, „, /с„, ..., /с,) = 2" 'и, + 2" за 2 Ч,. + 2 л„+ 2" 1/с + ... +/с, = = 2"/+ д. Тогла число Х (2 /+д) можно рассматривать как д-й элемент /-го блока т-й С1УПЕНИ. Пример 5.6. Рассмотрим описанную процедуру синтеза алгоритма БПФ с прорсживанием по времени на примере !6-точечного ДПФ.
В этом случае О=4. ИНЛСКСЫ П И /С ПрспетаВИМ СЛЕЛуЮщИМ ОбраЗОМ: Л=п«2'+ЛЗ2'+»225-Л1, /с=/с«22«с/сз2 +/с!2+/с! Полставляя п и /с в выражение для !6-точечного ДПФ, получаем ! 1 ! 1 Х(К«/сз/сз/с!) с с с с з/спал!пал!)и г ! г 2.". !з, 2' ° .. ! а, ! Теперь распишем алгоритм по ступеням; т= 0 — инверсия вхолной послеловательносзи: Хо(п, 2'+пз 2 тлз 2«ла)=х(па 2 +пз 2 ч-л2.2+и,); т=! преобразование «бабочка» псзслслователыюсти Хо. Х,(п„п,, пз,/с,)= «2" Хо(п1, пз,пз, па)с '2"' '; ,=о т=2 преобразование «бабочка» последовательности Х,: 2 „ -! Дтла, 2+1,1 Хз(пс, лз,/сз,/с,)= 2.
Х!(пз, пз, пз:/сз)е ,-о т=З преобразование «бабочка» последовательности Х,: ! 2 -! —,,Н, 2'+! .2+!, ! Хз(п,, Хз, /сз, /с!)= ~ Хз(пз, пз./сз, /с!)е !п=4 — преобразование «бабочка» последовательности Х,: '12,«Я,.2'-! 2'+1,2«1,! Ха(/са /сз Бы /с!)= ~ Хз(пз, /сз, Хь /с!)е ,=о Х(/с)=Х(/са, /сз, «2, /с!)=Ха(/са /сз Хз /с!) !40 /у Ф-яниуяа яагяг!яиуиуяуияия Е яшиуяи яяуугягяия пряигугугиия Направленный граф полученного в примере !6-точечного БПФ с указанием нсзочнпков элементарных ошибок окру!пения произволений и масштабирования, а также путей их распространения изображен на рис. 5.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
