Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 99
Текст из файла (страница 99)
(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. Для аппаратуры, использующей высокоскоростные умножители, мы должны учитывать как умножения, так и сложения. Подходящее сравнение обеспечивается Глава 13. Маленькие хит ости ци овей об аботки с'игналов 494 разностью общего количества операций в (13-47) и (13-47') и общего количества операций в (13-48) и (13-48'). В этом случае относительная экономия вычисле- ний в процентах вычисляется как 14У ' (1о82У+1) + 6У ' (1о82У+1) — (2У ' 1о82У+ 8У+ ЗУ ' 1о82У+ 8У)]/ /(4У ' (1о82У+1) + 6У ' (1оя2У+1)] ° 100%- [10 ° (1оя2У+1) — 5 ° 1оя2У вЂ” 16]/110 ° (1о82У+1)] ° 100 % = = (5 ° 1о82У вЂ” 6]/(10 ° (1о82У+1)] ° 100% .
(13-50) Эконоиин вычионвний ори исссльзоввнии 2М % 20 го ио 1о' 1о' 1о' и Рис. 13.13. Экономия объема вычислений при использовании алгоритма 2У-точечного действительного БПФ по сравнению с отдельным 2И-точечным комплексным БПФ. Верхний график показывает экономию с учетом и сложений, и умножений. Нижний график показывает зкономию с учетом только умножений Экономия полного количества операций (умножений и сложений) согласно (13-50) в зависимости от У показана в виде верхнего графика на рисунке 13.13. 13.6. Вычисление обратного БПФ с помощью прямого БПФ 13.6.1.
Первый метод вычисления обратного БПФ Первый метод выполнения обратного БПФ реализуется в соответствии со схемой, показанной на рисунке 13.14. Часто в системах цифровой обработки сигналов требуется вычислять обратное БПФ. Это может создавать проблемы, если имеющаяся аппаратура или библиотечная процедура могут выполнять только прямое БПФ. К счастью, существуют два простых способа вычисления обратного БПФ, используя прямое БПФ. 13.6.
Вычисление об атного БПФ с помощью л ямого БПФ Чтобы понять, как она работает, рассмотрим выражения для прямого и обратного ДПФ: Н-1 Прямое ДПФ Х(т) = ~~~ х(и)е 12л"и/Н (13-51) л-0 Н-1 х(п) = (1/Ы),Г,Х(т)еРл™/Н. (13-52) Обратное ДПФ . х,(п) Х„ (т) Х, (т) х, (л) -1 -1 Рис. 13.14.
Последовательность обработки при использовании первого метода вычисления обратного БПФ Повторим: нашей целью является использование преобразования, описываемого выражением (13-51), для реализации (13-52). На первом шаге мы используем операцию комплексного сопряжения. Напомним, что эта операция (обозначаемая надстрочным индексом ') состоит в инверсии знака показателя степени комплексной экспоненты — если х = е)0, то х = е 10. Итак, на первом шаге мы заменяем обе части (13-52) комплексно-сопряженными величинами, а именно х"(и) = (1/ЖЯ Х(т)е12™/Н ~". и-0 (13-53) Одно из свойств комплексных чисел, обсуждаемое в приложении А, состоит в том, что сопряженное произведения равно произведению сопряженных: если с = аЬ, то с" - (аЬ)" - а "Ь". Используя это свойство, мы можем показать, что правая часть (13-53) имеет вид Н-1 х (и) = (1/Ы)~~ Х(т)+(е12 "'"/и)" = и-0 Н вЂ” 1 = (1/Ы) ~> Х(т)'е 12лл"'/Н. (13-54) и 0 Потерпите еше немного, мы почти у цели.
Обратите внимание на сходство выражения (13-54) и выражения для прямого ДПФ (13-51). Если мы выполним прямое ДПФ последовательности, сопряженной исходной последовательности Х(т) в (13-54), и разделим результат на М, мы получим последовательность, сопряженную нашей искомой последовательности х(и). Построив сопряжение для обеих частей (13-54), мы получаем более прямое выражение для х(п): Н-1 х(п) - (1/Ы)~~~> Х(т) е 12лли/Н] . (13-55) и-0 Глава 13. Маленькие хит ости и овей об богки сигналов 13.6.2. Второй метод вычисления обратного БПФ Х,,(м) х„ (а) х, (л) х, (в] Рис.
13.16. Обработка данных вторым методом вычисления обратного БПФ М вЂ” 1 х(п) = (1/М~~~> Х(т)032лат/М Обратное ДПФ~ и-О ))( — 1 = (1/М) г[Х,аа((т) + 1Х;, (т)1[соь(2лтп/М) + и-0 +)ып(2лтп/Х)1 . (13-56) Перемножение комплексных членов (13-56) дает нам и-1 = (1/М)~,[Хгаа((т)соь(2лтп/)()) — Х;, (т)ь(п(2лтп/ИЯ + и-0 +/[Х„аа)(т)ып(2лтп/Х) + Х; (т)соь(2лтп/М)] .
(13-57) Формула (13-57) представляет общее выражение для обратного ДПФ, и мы скоро покажем, что процесс, представленный на рисунке 13.15, реализует это выражение. ПосколькУ Х(т) = Х„, ((т) +/Х„ааа(т), пеРестановка этих членов пРиводит к Хяаар(т) - Х(маа(т) +/Х„аа)(т) (13-58) Прямое ДПФ последовательности Х „(т) имеет вид М вЂ” 1 ~> [Х(~~(т) +)Х„, )(т)1[соь(2лтп/М) -/ь(п(2лтп/))))) - (13-59) и=0 Перемножение комплексных множителей в (13-59) дает ~> [Х( (т)соь(2лтп/М) + Х~а)(т)ь(п(2лтп/))))) + Прямое и-0 +Я Х )(т)соь(2лтп/1))) — Хап (т)ь(п(2лтп/(())) .
(13-60) Второй метод реализуется в соответствии с интересной схемой, показанной на рисунке 13.15. В этой остроумной схеме нам не нужно возиться с сопряженными последовательностями. Вместо этого мы просто меняем местами действительные и мнимые части последовательностей комплексных отсчетов [211. Чтобы понять, как работает эта схема, рассмотрим еще раз выражение для обратного ДПФ, представив входную последовательность Х(т) в виде действительной и мнимой части и помня, что е)г = соь(ф) +/ь(п(ф). 13.7. Уп щенная с а КИХ- иль Поменяв местами действительную и мнимую части результата этого ДПФ, мы получаем то, к чему стремились: М-1 ~]Х„~Ят)соз(2лтп/Х) — Х;„мв(т)з(п(2лтп/Ж)) + ДПФепаР О +1) Х, (т)соз(2лтп/Х) + Хе,~(т)з]п(2птп/Ю)) .
(13-61) Если мы разделим (13-61) на Ь1, то получим в точности выражение для обрат- ногаДПФ (13-57), и это как раз то, что мы хотели показать. 13.7. Упрощенная структура КИХ-фильтра Если мы реализуем цифровой КИХ-фильтр с линейной ФЧХ, используя стандартную структуру, показанную на рисунке 13.16 (а), то мы можем уменьшить количество умножителей в случае, когда длина фильтра нечетна. Посмотрим на верхнюю часть рисунка 13.16 (а), где коэффициенты КИХ-фильтра с пятью ответвлениями обозначены как Ь(0) — Ь(4), а выходной сигнал у(п) вычисляется как у(п) - Ь(4) х(п — 4) + Ь(3)х(п — 3) + Ь(2)х(п — 2) + Ь(1)х(п — 1) + Ь(0)х(п) (13-62) Если коэффициенты КИХ-фильтра симметричны, мы можем уменьшить количество умножений: если Ь(4) = Ь(0) н Ь(3) = Ь(1), мы можем реализовать (13-62) как у(п) - Ь(4)~х(п — 4)+х(п)) + Ь(ЗЯх(п — 3)+х(п — 1)) + Ь(2)х(п — 2) (13-63) которое требует всего трех умножений, как показано в нижней части рисунка 13.16 (а).
В данном примере фильтра с пятью ответвлениями мы убрали два умно- жителя за счет добавления двух сумматоров. Эта структура с минимальным количеством умножителей называется сложенной структурой КИХ-фильтра. В общем случае КИХ-фильтров с симметричными коэффициентами, имеющих 5 ответвлений, мы можем обменять (5 — 1)/2 умножителей на (5 — 1)/2 сумматоров, когда 5 является нечетным числом. Таким образом, в случае нечетного количества ответвлений нам необходимо выполнить только (5 — 1)/2 + 1 умножений на каждый выходной отсчет фильтра. В случае четного количества симметричных ответвлений, как показано на рисунке 13.16 (Ъ), этот метод позволяет нам уменьшить количество необходимых умножений до Я/2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
