Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 98
Текст из файла (страница 98)
Итак, продолжим наши вычисления и используем (13-24) и (13-25) для извлечения ХЬ(т) из результатов БПФ. Согласно (13-25), Хв(0) =Х,(0) = О. Подставляя отсчеты спектра в (13-24) для получения следующих четырех отсчетов ХЬ(т), получаем Хь(1) = (Х,(7) + Х;(1) +Ах,(7) — Х,(1)])/2 = = [6.8г82 — 1. 1717+1(2.8283+ г.а8З)]/2- - (5.656 + 15.656)/2 = 2.828 + 12.828 = 4 ~ 45, х,(г) - (х,(6) + х,(2) +ях„(6) - х(2)])/г = = [о.о - 2.8282+ 1(о.о — 2.8282)]/г = = (2.8282 — 12.8282)/2 = 1.414 — 1'1 414 = 2 ~ — 45, Хь(3) (Х'(5) + Х'(3) +ЯХ (5) Х (3)Д/2 = = [0.0 + 0.0 + 1(0.0 — 0.0)]/2 = 0 к.
0', Хь(4) = (Х;(4) + Х;(4) + ЯХ,(4) — Х,(4) Д/2 = = [0.0 + 0.0 +ЯО.Π— 0.0)]/2 = 0 ~ 0'. Возникает вопрос: «Увеличивается или уменьшается общее количество операций с учетом дополнительной обработки в соответствии с (13-22) и (13-24) после БПФ, и насколько, при использовании алгоритма двойного Ж-точечного действительного БПФ7» Мы можем оценить эффективность этого алгоритма, рассмотрев количество необходимых арифметических операций по отношению к двум отдельным М-точечным БПФ по основанию 2.
Сначала мы должны оценить количество арифметических операций для двух отдельных Ю-точечных комплексных БПФ. Глава 13. Маленькиекит остици овойоб аботкисигналоа Из раздела 4.2 мы знаем, что стандартное У-точечное комплексное БПФ по основанию 2 требует выполнения (Х/2)1ой2Хбабочек. Если мы используем оптимизированную структуру бабочки, каждая бабочка требует одного комплексного умножения и двух комплексных сложений, Каждое комплексное умножение состоит из двух действительных сложений и четырех действительных умножений, а одно комплексное сложение содержит два действительных сложения'. Следовательно, одна бабочка БПФ содержит четыре действительных умножения и шесть действительных сложений.
Это значит, что №точечное комплексное БПФ требует (4Ж/2)1ой2Х действительных умножений и (бМ/2)1ой2Х действительных сложений, Наконец, мы можем сказать, что два отдельных Ж-точечных комплексных БПФ по основанию 2 требуют Два К-точечных комплексных БПФ - 4№!ой~Ждействительных умножений и (13-30) б№! ой2Ь1 действительных сложений. (13-30') Далее нам необходимо определить объем вычислений для двойного У-точечного действительного БПФ. Если мы сложим количество действительных операций сложения и умножения, необходимых для реализации У-точечного комплексного БПФ, и количество соответствующих операций, необходимых для вычислений по (13-22) и (13-24) для получения Х„(т) и ХЬ(гл) соответственно, то получим следующую картину: Двойное К-точечное действительное БПФ - 2№ !оп~У ч Ждействительных умножений и (13-31) 3№1ой2Ж+ 2Ждействительных сложений. (13-31') В (13-31) и (13-31') предполагается, что мы вычисляем только первые У/2 независимых отсчетов Хо(ти) и ХЬ(т).
Член У в (13-31) учитывает Х/2 операций деления на 2 в (13-22) и М/2 делений на 2 в (13-24). Итак, теперь мы можем установить, какова эффективность алгоритма двойного М-точечного действительного БПФ по сравнению с двумя отдельными комплексными М-точечными БПФ по основанию 2. Результат этого сравнения, однако, зависит от используемого для вычислений оборудования. Если наше арифметическое .устройство затрачивает на умножение намного больше тактов, чем на сложение, то наибольшее значение имеет разность количества операций умножения.
В этом случае процент уменьшения объема вычислений при двойном Х-точечном действительном БПФ по сравнению с двумя отдельными М-точечными комплексными БПФ вычисляется как разность количества умножений, деленная на количество умножений, необходимое для вычисления двух отдельных БПФ, или 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
