Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 97
Текст из файла (страница 97)
И в аппаратурной, и в программной реализации необходимо реализовать ее как можно эффективнее. Если используемая аппаратура может выполнять три сложения быстрее, чем одно умножение, мы можем ускорить комплексное умножение 116]. Умножение двух комплексных чисел а +7Ь и с +7а дает комплексное произведение вида Я+77-(а+7Ь)(с+7в') = (13-14) = (ас — Ы) +7(Ьс + ас4) Мы видим, что (13-14) требует четыре умножения и два сложения. (Мы предполагаем, что с точки зрения времени выполнения вычитание эквивалентно сложению.) Вместо использования (13-14) мы можем вычислить следующие промежуточные значения Ат=а(с+4, А2 = г((а + Ь), Ьз - с(Ь вЂ” а). (13-15) Прямоугольное Хэннинга Хам минга Блзкмана Точное Блзкмана 3-членное Блэкмана-Харриса 7938/18608 9240/18608 1430/18608 13.5. хтивное вычисление БПФдействительныхпоследовательностей 483 Затем мы выполняем следующие операции для получения окончательных значений Н и й к=вт-вг (13-16) 1 ~ 1 + ( 3 Мы предлагаем читателю подставить й из (13-15) в (13-16) и убедиться в том, что выражения в (13-16) эквивалентны (13-14).
Промежуточные значения в (13-15) требуют три сложения и три умножения, а результаты в (13-16) требуют еще два сложения. Таким образом, мы обменяли одно умножение в (13-14) на три сложения в (13-15) и (13-16). Если нашей аппаратуре для выполнения трех сложений требуется меньше тактов, чем для одного умножения, мы можем получить общий выигрыш в скорости обработки при использовании (13-15) и (13-16) вместо (13-14) для выполнения комплексного умножения. 13.5. Эффективное вычисление БПФ действительных последовательностей Осознав свойство линейности и четную/нечетную симметрии быстрого преобразования Фурье (БПФ), ранние его исследователи быстро пришли к выводу о том, что две разные действительные последовательности могут быть преобразованы с помощью одного комплексного БПФ.
Они также разработали метод использования одного Х-точечного комплексного БПФ для преобразования действительной последовательности длиной в 21ч'отсчетов. Посмотрим, как работают эти методы. 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 элементов Х„(тв) независимы и должны быть вычислены.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
