Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095938), страница 102
Текст из файла (страница 102)
Результат этого сравнения, однако, зависит от используемого для вычислений оборудования. Если наше арифметическое .устройство затрачивает на умножение намного больше тактов, чем на сложение, то наибольшее значение имеет разность количества операций умножения. В этом случае процент уменьшения объема вычислений при двойном Х-точечном действительном БПФ по сравнению с двумя отдельными М-точечными комплексными БПФ вычисляется как разность количества умножений, деленная на количество умножений, необходимое для вычисления двух отдельных БПФ, или 1 Комплексное сложение (а+1Ь) + (с-ь)4) - (а+с) +ЯЬ+4) требует двух действительных сложений. Комплексное умножение (а+/Ь) (с+/4) = ас-Ь4+/(а6+Ьс) требует двух действительных сложений и четырех действительных умножений.
13.5. Э ективное вычисление БПФдействигельныхпоследовательностей 489 Ц4И 1оя2И вЂ” (2У !она+ И)]/(4И 1оя2И)1 ° 100% = = ~(2 ° !ода — 1)/(4 ° 1оя2М)] ° 100% . (13-32) Я(4И 1оя2И+ 6Х ' 1оязИ) — (2Х 108~И+ Ж+ ЗЖ ' 1оя2И+2И)]/ /(4М 1оя2И+ 6Х' 1оя2М)) ' 100% = = [(5 ° 1оя2М вЂ” 3)/( 10 ° 1оя2М)] ° 100 % . (13-33) кснсмия вычисления при использовании 60 46 46 % 42 40 зв 36 34 1о' 10 10 10 1 1о 10 Рис. 13.11.
Уменьшение количества операций при использовании алгоритма двойного И-точечного действительного БПФ по сравнению с двумя отдельными И-точечными комплексными БПФ. Верхняя кривая показывает зкономию по умножениям. Нижняя кривая показывает зкономию по сумме сложений и умножений Экономия количества операций, вычисленная только по умножениям, при использовании (13-32) показана в виде верхнего графика на рисунке 13.11. По количеству умножений при М>32 двойное И-точечное действительное БПФ оказывается более чем на 45 % экономичнее по сравнению с двумя отдельными М-точечными комплексными БПФ. В аппаратуре, в которой используются высокоскоростные специализированные умножители, умножения и сложения могут выполняться за практически одинаковое количество тактов. В этом случае операции сложения так же важны, как и операции умножения.
Следовательно, для правильного сравнения необходимо брать разность суммарного количества операций в (13-30) и (13-30') и суммарного количества операций в (13-31) и (13-31'). В этом случае относительное уменьшение количества операций вычисляется как разность общего количества операций, деленная на общее количество операций для двух отдельных Ж-точечных комплексных БПФ, или 490 Глава 13. Маленькие кит ости ци овей об вбогки сигналов Полный выигрыш в объеме вычислений (по сумме умножений и сложений) в соответствии с (13-33) приведен в виде нижнего графика на рисунке 13.11. Этим мы завершаем обсуждение использования одного М-точечного комплексного БПФ для преобразования двух независимых А1-точечных действительных последовательностей.
13.5.2. Вычисление 2Н-точечного действительного БПФ Подобно описанному выше алгоритму вычисления БПФ двух разных действительных последовательностей с помощью одного комплексного БПФ, существует метод вычисления БПФ 2М-точечной действительной последовательности с помощью одного Ж-точечного комплексного БПФ.
Этот алгоритм 2М-точечного действительного БПФ, вывод которого также описан в литературе, основан на разбиении действительной последовательности длиной в 2%отсчетов на две части [19, 201. Не просто на разбиении, а на разбиении, подобном разъединению двух частей замка-молнии — разделении четных и нечетных отсчетов. М входных отсчетов с четными индексами загружаются на место действительных частей комплексной Ж-точечной входной последовательности х(п). Аналогично, Хотсчетов с нечетными индексами загружаются на место мнимых частей последовательности х(п). Длц иллюстрации этого процесса предположим, что мы имеем входную действительную последовательность длиной в 2У отсчетов а(п) при 0 ( п < 2У вЂ” 1.
Мы хотим получить преобразование последовательности а(п), содержащее 2Жотсчетов Х„(т). Загружая четные и нечетные отсчеты а(п) соответствующим образом в Ф-точечную последовательность х(п), получаем х(0) = а(0) +1а(1), х(1) - а(2) +1а(3), х(2) = а(4) -~уа(5), х(У вЂ” 1) = а(2Ж вЂ” 2) + уа(2Ж вЂ” 1). (13-34) (13-35) (13-36) (13-37) Х„(т) = 1Х(т) — Х„(Ф вЂ” т)1/2, Х,+(т) = 1Х;(т) + Х;(Ж вЂ” т)1,~2, Х; (т) - 1Х;(т) — Х;(М вЂ” т))/2, (13-38) Значения, полученные с помощью (13-35) — (13-38), используются затем как коэффициенты в следующих выражениях для получения действительных и мнимых частей Х„(т): Подавая М комплексных значений вида (13-34) на Ж-точечное комплексное БПФ, мы получим результат Х(т) = Х„(т) + 1Х;(т), где т меняется от 0 до А' — 1.
Чтобы извлечь требуемое 2М-точечное БПФ действительной последовательности Х,(т) = Х, ~(т) +1Х, ь„, (т) из Х(т), зададим следУющие соотношениЯ Х„+(т) = 1Х„(т) + Х,(У вЂ” т)],'2, 13.5. ективное вычислениеБУУФдействительныхпослероввтельностей 491 Х„геа1( т) = Х„+(т) + соз(лт/лУ) Х;+(т) — э1п(лт/лУ) Х„-(т), (13-39) х(0) = 03535 + уОЗ535, х(1) = 0.6464 + у1.0607, х(2) = 03535 — у1.0607, х(3) = — 13535 — у03535.
(13-41) Рис. 13.12. Последовательность вычислений в алгоритме 2И-точечного действительного БПФ В данном примере М = 4, поэтому, вычислив 4-точечное БПФ комплексной последовательности (13-41),мы получаем Х;(т) + 10.0000 — у 0.5857 -1 1 4141 +1 3.4141 Х,(т) Х(т)- 0.0000 + 1.4142 -т= О -т=1 -т-2 т= 3 + 1.4141 — 1.4142 (13-42) Х„;, (т) = Х; (т) — зш(лт/лу) Х;+(т) — соз(лт/Х) ' Х, (т), (13-40) Вспомните теперь, что индекс исходной последовательности а(п) меняется в пределах от 0 до 2У вЂ” 1, а индекс результата ЛУ-точечного БПФ т меняется от 0 до лУ-1. Мы подаем на вход преобразования 2Ждействительных отсчетов и получаем на выходе лу комплексных отсчетов в частотной области, представляющих первую половину эквивалентного 2ЛУ-точечного БПФ, от Х„(0) до Х„(лУ- 1). Поскольку входная последовательность этого алгоритма а(п) действительна, отсчеты от Х„(Ж) до Х„(АУ вЂ” 1) являются комплексно-сопряженными отсчетам Х„(0)— Х„(йУ-1), и их вычислять не нужно, Для более полного понимания всего процесса на рисунке 13.12 показаны шаги алгоритма АУ-точечного действительного БПФ.
Чтобы продемонстрировать этот алгоритм на примере, подадим 8-точечную последовательность из (13-26) на вход алгоритма 2лУ-точечного действительного БПФ. Разбивая отсчеты (13-26) в соответствии с (13-34), мы получаем новую входную последовательность БПФ: Глава 13. Маленькие хит ости ци овей об аботки сигналов 492 Используя эти значения, мы получаем промежуточные коэффициенты согласно(13-35) — (13-38).
ВычислениепервогозначенияХ„+(0)снованапоминаетнам о том, что последовательность Х(т) периодична с периодом Х, так что Х(4) = Х(0), и Х„+(0) = 1хг(0) + Хг(0)]/2 = О. ПРодолжаЯ использовать. (13-35)— (13-38), получаем Х„+(0) = О, Х„+(1) =О, Х„+(2) = 1.4141, Х„+(3) = О, Х;+(0)= О, Х;+(1) = 1.4142, Х;+(2)- — 1 А 144, Х;+(3)- 1.4142, Х„(0) -О, Хг (1) = 1.4142, Хг (2)=0, Х, (9) = -1.4142, х,-(О) = о, Х; (1) - -1.9999, Х; (2)=0, Х; (3) = 1.9999.
(13-43) Используя промежуточные значения из (13-43) в (13-39) и (13-40), получаем Х фо) =(0)+сов(л О/4) ° (0) — яп(л О/4) ° (0) Х„;,„(0) = (0) — яп(л 'О/4) ° (0) — соз(л О/4) ° (О) Х„я(1) = (0) + соз(л' 1/4) ° (1.4142) — яп(л ° 1/4) ° (1.4 142) Х„~е„~(0) = (0) + (1) ° (О ) — (0) ° (0) = О, Х.; . (0) - (0) - (0) ° (0) - (1) ° (0) - О, Х„. (1) = (О) - (0.7071) ° (1.4142) — (0.7071) ° (1.4142) = О, Ха !тая(1) = ( — 1.9999) — (0.7071) ° (1.4142) — (0.7071) ' (1 4142) = — 9.9999, Х~ н,Я2) = (1.4 141) + (О) ° (- 1.4144) — (1) ° (0) - 1,4141, Хв; „(2) = (0) — (1) ° ( — 1 4144) — (0) ° (0) = 1 4144, Х„ги4(9) = (0) + ( — 0.7071) ° (1.4142) — (0.7071) ° ( — 1.4142) = О, Хв; „(9) = (1.9999) — (0.7071) ° (1.4142) — ( — 0,7071) ° ( — 1.4142) = О, (13-45) Хв;в,~Я = ( — 19999) — яп(л~ 1/4) ° (1.4142) — соз(ле 1/4) ° (1,4142) Х„гев1(2) = (1.4141) + соз(л'2/4) ° ( — 1.4144) — яп(ле2/4) ° (0) Ха гимв(2) - (0) — Яп(л'2/4) ° ( — 1.4144) — соз(л'2/4) ° (0) Х, р(3) = (0) + соз(л'3/4) ° (1.4142) — яп(леЗ/4) ° ( — 1,4142) Х„; „(3) =(1.9999) — яп(л 3/4) ° (1.4142) — соз(л 9/4) ° ( — 1.4142) (13-44) Вычисляя значения синусоидальных и косинусоидальных членов в (13-44), получаем 13.5.
Э ективное вычисление БПФ действительных последовательностей 493 И, наконец, получаем окончательный правильный результат Х (0) =Х,, (0)+1Х„; (0) =0 10=0~0; Хв(1) =Х„„~(1) +1Хв; „(1) = 0 — 13999 4 ~ — 90; Хв (2) = Х„,.~в!(2) +1Хв;~ (2) = 1.4141+11.4144 = 2 ~. 45; Хв(3) - Хл ть4(3) +1Хв вл (3) = 0 ~10 = 0 ~ 0 (13-46) После выполнения всех операций согласно (13-35) — (13-40), читатель может задуматься об эффективности алгоритма 27ч'-точечного действительного БПФ. Используя тот же подход, который мы применили в случае двойного М-точечного действительного БПФ, покажем, что алгоритм 2М-точечного действительного БПФ на самом деле обеспечивает некоторый выигрыш. Прежде всего, мы знаем, что отдельное 27ч'-точечное БПФ по основанию 2 содержит (2Х/2) ° [о822Х- Х(!о82Ж+ '1) бабочек и требует 2М-точечное комплексноеБПФ вЂ” 4У' (!оя У+1) действительныхумножений (13-47) 6М (!о82Х+1) действительных сложений (13-47') Если мы сложим количество действительных умножений и действительных сложений, необходимое для вычисления Гч'-точечного комплексного БПФ, плюс операции, необходимы для (13-35) — (13-38) плюс операции в (13-39) и (13-40), то получится, что полное 2Ж-точечное действительное БПФ требует 2К-точечное действительное БПФ - 2М ' !ойзЖ ч- 87ч' действительных умножений (13-48) ЗМ ' !ойзЖ+ 8!ч' действительных сложений (13-48') Итак, используя те же соображения, которые привели нас к (13-32), мы получаем относительное уменьшение количества умножений в алгоритме 2М-точечного действительного БПФ по отношению к 21ч'-точечному комплексному БПФ в виде [4У (!ода+ 1) — (2Ж !о82Ж+ 8Щ[4И (!о82У ч-1)! ° 100%- = [2Ж !ойзЖ+ 2Ж вЂ” Ж !ойзУ вЂ” 4Ж))/[2У ' !ойзМ+ 2Л) ° 100%- = [!ойзУ вЂ” 2]/[2 ° !ойзУ+ 2! ° 100% .
(13-49) Выигрыш согласно (13-49) (с учетом только умножений) показан как нижний график на рисунке 13.13. Относительно умножений алгоритм 2Ж-точечного действительного БПФ обеспечивает экономию больше 30 Ж при Ж ~ 128, или при обработке действительных последовательностей, длина которых не меньше 256.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
