Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095938), страница 101
Текст из файла (страница 101)
Посмотрим, как работают эти методы. 13.5.1. Вычисление БПФ двух й-точечных действительныхпоследоввтельностей Стандартные алгоритмы БПФ разработаны для комплексных входных последовательностей; т. е. предполагается, что входная последовательность х(п) содержит действительную и мнимую часть, или х(0) = х„(0) + 1х;(О), х(1) = х,(1) +1х;(1), х(2) = х,(2) + 1х;(2), х(М вЂ” 1) = хт(7ч' — 1) + ух;(Ж вЂ” 1) . (13-17) В типовых схемах обработки сигналов чаще всего анализируются действительные последовательности.
Самый распространенный пример — ' вычисление БПФ последовательности, полученной с выхода АЦП, который выдает целые действительные отсчеты, соответствующие некоторому непрерывному сигналу. В этом случае мнимые части всех отсчетов последовательности х(я) равны 48а Глава 13. Маленькие хи ости ци свой об аботки сигналов х(0) = а(0)-~уЬ(0), х(1) - а(1)чуЬ(1), х(2) = а(2) + уЬ(2), (13-18) х(йу — 1) = а(йу — 1) +уЬ(ду — 1) Подставляя х(п) из (13-18) в формулу стандартного ДПФ, еу — у Х(т) = ~~> х(п) е у2ллт/М -о (13-19) мы получим результат Х(т), при этом т пробегает все целые значения от 0 до ЬУ вЂ” 1. (Мы, естественно, предполагаем, что ДПФ реализуется в виде БПФ.) Обо- значая верхним индексом " комплексно-сопряженное число, мы можем извлечь два искомых ДПФ Х„(т) и Хь(т) из Х(т), используя следующие выражения: Х„(т) - 1Х"(ЬУ вЂ” т) + Х(т)!/2, (13-20) и Хь(т) =АХ" (йУ вЂ” т) — Х(т) 1/2 .
(13-21) Чтобы сделать выражения для Х„(т) и Хь(т) более понятными и более удобными для реализации, представим (13-20) и (13-21) в виде действительной и мнимой частей. Используя запись Х(т) в алгебраической форме, Х(т) = Х,(т) чуХ(т), мы можем переписать (13-20) в виде Х,(т) = (Хг(Х вЂ” т) + Х,(т) +ЯХ;(т) — Х;(ЛУ вЂ” т)1)/2, (13-22) гдет = 1,2 З,...,ЬУ-1.ЧтовыскажетеобХ (т),когдат =07Да здесьмысталкиваемся с непреодолимой трудностью, если попробуем реализовать (13-20) прямо.
Подставив т = 0 в (13-40), мы быстро осознаем, что первый член числителя Х"(ЬУ-0) - Х"(Щ отсутствует, т. к. в результатах ЬУ-точечного БПФ отсчетаХ(ЬУ) нет! Мы решаем эту проблему, вспомнив, что последовательность Х(т) периодична с периодом ЬУ, так что Х(ЬУ) - Х(0)'.
Это показано в разделе 3.8 при обсуждении утечки спектра в ДПФ. нулю. Следовательно, часть операций, выполняемых на первом этапе БПФ, оказывается бесполезной. Первые исследователи БПФ осознали неэффективность выполнения такого преобразования, изучили проблему и разработали метод, ко- ' торые позволяет с помощью одного ЬУ-точечного комплексного БПФ вычислять преобразования двух независимых действительных последовательностей, содержащих по ЬУотсчетов. Мы называем предложенный метод алгоритмом двойного ЬУ-точечного действительного БПФ. Вывод этого метода не представляет сложности и изложен в литературе 117 - 191.
Две ЬУ-точечные действительные входные последовательности а(п) и Ь(п) имеют преобразования Фурье Х„(т) и Хь(т). Если мы возьмем а(п) в качестве действительной части входной последовательности БПФ, а Ь(п) в качестве мнимой части входной последовательности БПФ, то 13.5. Э ектиеное вычисление БУ7Фдейсгвигельныхпоследовательностей 485 Когда т - О, формула (13-20) превращается в Х„(0) = [Х„(0) — уХ;(0) + Х„(0) + уХ;(0) [/2 = Х,(0) . (13-23) Далее, упрощая (13-21), получаем Хь(т) = у[Х„(У вЂ” т) — уХ(АУ вЂ” т) — Х„(т) — уХ,(т)[/2- = (Х;())У вЂ” т) + Х;(т) +ЯХ(Х вЂ” т) — Х(т)1)/2, (13-24) где т - 1, 2, 3, ..., ЬУ-1.
Прибегая к тем же рассуждениям, что и при выводе (13-23), получаем Хь(0) в (13-24) в виде Ху,(0) = (Х;(О) + Х;(0) +7[Х,(0) — Х„(0)[)/2 = Х;(О) (13-25) Аналогично, 8-точечная последовательность из примера 2 в разделе 3.6, обо- значенная как Ь(п), имеет вид Ь(0) = 1.0607, Ь(1) = 0.3535, Ь(2) = -1.0607, Ь(3) = -1.3535, Ь(4) = -0.3535, Ь(5) = 0.3535, Ь(6) = 0.3535, Ь(7) = 0.6464. (13-27) Объединяя (13-26) и (13-27) в одну комплексную последовательность х(п), мы получаем Ь(п) +у 1.0607 +у 0.3535 -У 1.0607 а(п) 0.3535 + 0.3535 + 0.6464 х(п)= Эти рассуждения выявили один момент, который новичкам следует запомнить. В литературе формулы (13-20) и (13-21) часто подаются без обсуждения пробле- мы, связанной с т = О. Так что каждый раз, разбирая математические выкладки или столкнувшись с некоторыми уравнениями, сохраняйте здоровую долю скепсиса.
Проверьте уравнения на примере — вы увидите, справедливы ли они. (В конце концов, и автор книги, и наборщик в типографии тоже человек и иногда делает ошибки. В Огайо известна старая присказка: «Доверяй всем, но прячь свои кар- ты.») Следуя этому, совету, давайте докажем, что описанное двойное АУ-точечное действительное БПФ действительно работает, подставив в (13-22) — (13-25) 8-точечные последовательности из примеров вычисления ДПФ в главе 3.
Взяв 8-точечную последовательность из примера 1 в разделе 3.1, и обозначив ее как а(п), имеем а(0) = 0.3535, а(1) - 0.3535, а(2) - 0.6464, а(3) = 1.0607, а(4) = 0.3535, а(5) = -1.0607, а(6) - — 1.3535, а(7) = -0.3535 . (13-26) Глава 13. Маленькие «и ости ци овей об аботки сигналов 486 + 1.0607 + 0.3535 — 1.0607 — 1.3535 — 0.3535 -1 1.3535 -1 0.3535 +10.3535 +10.3535 +1 0.6464. (13-28) Теперь, вычисляя 8-точечное БПФ комплексной последовательности (13-28), мы имеем: Х(т)= (13-28) Итак, согласно (13-23), Х„(0) = Х,(0) = О.
Для получения остальных отсчетов Х„(т) мы должны подставить отсчеты Х(т) и Х(М вЂ” т) в (13-22)'. В результате получаем: Х,(1) - [Х„(7) - Х,(1) + 1[Х,(1) - Х,(7)[)/2 = - [2.8289 — 2.8283 -ь 1( — 1.1717 — Б.8282) )/2 = = (Π— )'7.9999)/2 =. Π— 14.0 = 4 4. — 90', Ха(2) - [Х„(Б) -ь Х„(2) + )[Х1(2) — Х;(Б)[)/2- = [0.0+ 2.8282+ 1(2.8282 — 0.0)[/2 = - (2 8282 +128282)/2 = 1.4 14 +11 414 = 2 х' 45, Х (З) = [Х„(9) + Хг(З) +1[Х;(З) — Х;(З)))/2- = [О.О - О.О +,1(О.Π— О.О)[/2 = О 4.
О', Х,(4) = [Х„(4) + Х„(4) +ЯХ;(4) — Х;(4)])/2 = = [0.0+ 0.0 +у(0.0 — 0.0))/2 = 0 4. 0', 1 Помните, что для комплексной входной последовательности отсчеты ДПФ не обладают сопряженной симметрией; т, е, мы не можем предположить, что г(т) - Е"(М-ж), когда и действительная, и мнимая части входных отсчетов отличны от нуля. Х,(т) 0.0000 — 2.8283 + 2.8282 + 0.0000 + 0.0000 + 0.0000 + 0.0000 + 2.8283 Х(т) +10.0000 -1 1.1717 +12.8282 +1 0.0000 +10.0000 +10.0000 +10.0000 +16.8282 -т= О ° -т=1 ° -т=2 ° -т=3 -т=4 ° -т=5 -т= 6 - т = 7.
13.5. Э ективное вычисление БПФ действительных последовательностей 487 Х„(5) - (Х,(3) + Х„(5) + 1[Х;(5) — Х;(3)])/2 = - [0.0 + 0.0 + 1(0.0 — 0.0)]/2 = 0 ~ 0', Х (б) = [Х„(2) + Х„(б) +ЯХ;(6) — Х;(2)])/2 = - [2,8282 + 0.0 + у(0.0 — 2.8282)]/2 = = (2.8282 — 12.8282)/2 = 1.4 14 + 11.4 14 = 2 4. —. 45', х,(7) = (х(1) + х(7) + 1[х,(7) - х(1)])/г = = [- 2.8282 + г аа+1(6/аа — 1.1717)]/г = = (0.0 + 17.9999)/2 = 0 + 14.0 = 4 ~ 90 .
Следовательно, (13-22) действительно позволяет извлечь Х„(т) из Х(т). Можно видеть, что нет необходимости выполнять вычисления по (13-22), когда т больше 4 (или )ч/2), потому что последовательность Х (и) всегда сопряженно-симметрична. Поскольку Х (7) = Х (1) ', Х (6) = Х„(2)" и т.д., только первые 1ч/2 элементов Х„(тв) независимы и должны быть вычислены.
Итак, продолжим наши вычисления и используем (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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
