Айфичер Э., Джервис Б. Цифровая обработка сигналов, практический подход (2-е изд., 2004) (1095888), страница 57
Текст из файла (страница 57)
326 Глава 5. Корреляция и свертка После этого применяется процедура, описанная в разделе 5.2.3, приводящая в конечном итоге к искомому рсзультшу: х (1) ~ х, (г) — В .1[Х,(6)Хя(6)[ (5.12 1) для свертки во временной области. Для свертки в частотной области применяется аналогичное уравнение: — [Хк(6) '3 Х (6)[ .-:- к о~[хД)хя(г)[. ку (5.122) Последние две формулы представляют периодичссюзе, или круговые, свертки, которые можно преобразовать в линейные с помощью дополняющих нулей, как описано в разделе 5.3.2. 5.3.7. Вычислительные преимущества быстрой линейной свертки Метод быстрой линейной свертки предлагает преимущества меньшей вычислительной сложности по сравнению с прямым подходом, только если число значений, подлежащих свертке, достаточно велико. Ниже сравнивается число умножений, требуемых для выполнения свертки с помощью прямого и быстрого методов, выбранное в качестве меры нх относительной вычислительной эффективности.
Необходимые расчеты для прямого метода выполняются согласно уравнению (5.90). Очевидно, что для получения линейной свертки двух Х-точечных последовательностей 6(п. — т) и х(т) необходимо умножить каждое значение 6(п — гл) на кажлое значение х(т). Следовательно, гк значений 6(п — т) нужно перемножить с % значениями х(т), в результате всего требуется !У х Х вЂ” Х~ умножений. Рассмотрим теперь линейную свертку тех же двух !у-точечнгых последовательностей с помощью быстрого метода, записанного в уравнении (5.121).
Прибавление необходимых дополняющих нулей означает, что каждая последовательность имеет длину 2Х вЂ” 1 точек. Предположим, что 2!У вЂ” 1 2Ж, например, лг > 8, и что для использования БПФ по основанию 2 Х вЂ” целая степень 2, т.е. Х = 2", где г( — целое. Можно показать, что число комплексных Умножений длЯ Х-точечного БПФ Равно (Х/2)!окз 1к' (Раздел 3.5.3), так что для 2%-точечного БПФ необходимо (2!У12) 1ой, 2Х или Х 1ойя 2Х комплексных умножений. Согласно уравнению (5.121) требуется вычислить два ДПФ и одно обра~ное ДПФ.
Для расчета обратного ДПФ можно использовать модифицированное ДПФ (раздел 3.6). Таким образом, необходимо вычислить три 2)к'-точечных БПФ, включающих в сумме ЗЛ'1ок, 2Ж комплексных умножений. Для каждого из 2Х значений уравнения (5.121) необходимо выполнить комплексное умножение Х,(6)Х,(6), таким обРазом общее число комплексных Умножений возРастает до З)к' 1окя 2Х 1- 2)У.
Далее каждое комплексное умножение вида (А !-1В)(С+10) требует четырех действительных Умножений АС, АВ, ВС и ВВ. Значит, в целом необходимо 12% 1ойз 2!У+ 8% действительных умножений. Таким образом, можно сделать вывод, что прямой метод требует Х~ действительных Умножений, тогда как метод быстРой свсРтки тРебУет 12% = 1окз 2Ж+ 8Х Умножений. В табл.
5.1 сравниваются числа действительных умножений, необходимые для различных значений л(. Из таблицы видно, что быстрая свертка лучше прямого метода, если 5.3. Описание свертки 327 длина последовательностей превышает 128 точек данных, причсм для последователь- ностей из 1024 точек быстрая свертка даст результат за время, меньшсс примерно в 10 раз.
Тот же вывод справедлив и для прямой и быстрой корреляции. Таблица 5.1. Число действительных умножений. требуемых для выполнения свертки двух )тг- точечных последовательностей Ж ))рамой метод Бистран свертки (Бистран свертка)l(примой меппп!) 64 256 1 024 4 096 16 38~! 65 536 262 144 1 048 576 1 194 304 16 32 64 128 256 512 1024 2048 1 088 2 560 13 3!2 29 696 65 536 143 360 311 296 7 4,25 2,5 1.
4375 О, 8125 О. 4531 О, 250 О, 1367 О, 0742 5.3.8. Свертка и корреляция путем сегментации До этого момента предполагалось, что две функции, подлежащие свертке (или расчету корреляции), имеют конечную длительность. Впрочем, это справедливо не всегда. Например, можно считать, что входные данные имеют бесконечную длительность либо потому, что они поступают фактичсски непрерывно, либо (более вероятная причина) потому, что доступная память недостаточно велика, чтобы вместить их все. В подобных случаях свертку (или корреляцию) необходимо выполнять поэтапно, разделив входные данные на отдельные блоки, выполнив необходимые вычисления для каждого блока и затем обьсдипив результаты. Для реализации подобной схемы используются два метода: наложения-сложения (отег1ар-агЫ) и наложения-записи (отег(ар-явс), которые будут описаны ниже. Перел этим, впрочем, необходимо рассмотреть, как повысить эффективность вычислений, сслн две функции нс начинаются в нулевой момс!гт врсмспи.
На рис. 5.25 показаны два дискреп!ых сигнала х(п) и 12(и), а также их свсртка х(п) в) 6(п) = д(п). Сигналы х(п) и 6(п) начинаются соответственно в моменты а и 16 поэтомУ если в и 0 велики по сРавнению с количеством данных Ж~ и Мт в х(п) и 6(п) соответственно, то во многих тактах вычислений будут фигурировать расчеты с нулевыми данными. Число этих вычислений можно уменьшить, сместив сигналы так, чтобы они выходили из начала координат, как показано на рис. 5.2б. После этого данные необходимо дополнить нулями, чтобы оба сигнала содержали равное число точск Х = Ю, + Хт — 1, и их периодическая свертка соотвстствовала линейной свертке двух сигналов.
Свертка выполняется согласно теореме о свсртке (уравнение (5.117)) и алгоритму БПФ. Чтобы полученный результат был правильным, вычисленную свертку необходимо так сместить вдоль оси п, чтобы она начиналась в точке и е: а + 6 (рис. 5.2б, г). На приведенном рисунке прсдполагастся, что А! = 24, где с( — цслос, поэтому можно использовать БПФ по основанию 2.
Аналогичная иллюстрапия для корреляции х(п) и 6(п), т„ь(п), приведена на рис. 5 27. При трансляции указанных сигналов в начало координат вводятся дополнительные нули, так что Л = 2~ ) Х, + Кт — 1, и корреляция вычисляется согласно теореме о Глава 5.
Корреляция и свертка 328 Ь)а) .2522) г,о 0,5 а а а Ь2т чз азЬ Уз ь в) а) б) Рис. 5.25. Свертка 2л(н) = 22(о) Гя2 б!о) двух сигналов х(н) н И!22), не выходя!них из начала координат 2та) 22!а) х)а) т,о 0,5 О,Ь тз 'ь2 вб2 .ъ;-! а ~=Ь22" Ьз Ь2=2т,т У вЂ” ! Л"= Х2ь Ьгз — ! а) а) тЬ22) аьЬ г) Рнс. 5.26.
Свертка двух с2лгнаюв, изображенных на рис. 5.25, для получения которой а)п) и Ь22 ) транслировались в начало координат. Прибавление к а)п) № — ! дополняющих нулей )панель а). Прибавление к й)о) И2 — ! дополняющих нулей !панель б). Свертка И(о) =- г(22) 3 )2)н) (па!!ель а). Правильная линейная свертка попучается заменой л(22) влоль оси н функцией, начинюощейся в точке о — -- и -;- Ь (панель и) 329 5.3. Описание свертки я(а) з) гг) ч„(м) ),о 0,5 о,б лг г чз ) в) б) а) Рис. 5.27.
Взаимная корремция п(гп) двух сигналов я(п) и Ь(п), которые начинаготся нс в начале координас а) с(п); б) Ь(гг); в) г па(гп) т= 2" Ус У.— 1 Рис. 5.28. Неверная взаимная корреляция, полученная нри транс)ащнн я(п) и Ь(п) в начало координат коррсляции (формула (5.77)).
Получающийся результат представлен на рис. 5.28. Это не периодическая копия рнс. 5.27, в, хотя и содержит правильную базовую форму сигнала. Искомый периодический результат можно получить, перенеся х(г)) в точку и -: )9 — 1))г+1, при этом расположив 6()г) в точке и, гг О, как парис. 5.29, где видно, что в результате указанных действий получается требуемая периодическая корреляционная фУнкциЯ (Рис. 5.29, н). ПолУченный РезУльтат нУжно сместить на а — б( — Х + Х) )-Хя точек данных вправо, чтобы переместить в верное значение а — д (сравните с рис.
5.29, н). Распространим теперь приведенные соображения на задачу с бесконечной последовательностью ж(п), которую нужно свернуть с конечной последовательностью 6(т)). 5.3.9. Метод наложения-сложения Пусть х(и) делится на ссгме)ггы равной длины, состоящие из Х) точек данных. Далее предположим, ч)о данные последовательности псриодичны и требуется найти их свертку с Хя точками данных (последовательность 6(п)), дополненными Хг — гуз нулями, так что теперь обе последовательности периодичны и имеют длину Х).
Результат этой свертки будет неверным, поскольку для получсния правильного результата каждая последовательность должна иметь длину Х = Х) -)- 1'уз — 1. Впрочем, каждый сегмент ж(п) имеет длину гт') (и эту величину увеличить нельзя). Чтобы устранить эту проблему, можно рассмотреть сегменты т(п) с длиной Ж и заменить последние Жз — 1 точек данных нулями, расширив первопачальныс Х вЂ” Хя + 1 =- Х) данных (рис.
5.30). ззо Глава 5. Корреляция и саертка х(а1 1.О а1 бн2" й(а) 0,5 аь1м) од Рнс. 5.29. Метод получения правильной взаимной корреляпни двух последовательностей и(л) н 6(п): а) х(п) смешается в 29 — Х1 -~. 1; б) л(л) смещается в начало координат; в) получающийся правальный периодическиа козффипнент взаимной корреляпии тсь(ш) 5.3. Описание свертки 33 ! ! 2 Д 8 О я а 1 О 1 2 л л;=! в (! 5 б! 'б Й К О з О 1 2 ! В 5 б 7 Л', — 1 —. 5 к=б л; л'=.л;лл' -!.=8 .л;л,+л; — 1. в О! л! Рне.
5.30. Снертка методом наложения-сложения Подобным способом последовательность 1"в'! данных ж(п) с 15!2 — 1 дополняющими нулями сворачивается с Х2 данными последовательности 6!22) с Х2 — 1 дополняющими нулями. Обе последовательности содержат Х вЂ” ((г — 1 ( 282 — 1 точек данных, и их свертка находится правильно !рис. 5 31). Та же процедура выполняется для оставшихся последовательностей т(п) длины № Поскольку последние 2((2 — ! точек данных сегментов жЯ были заменены пулями, получающиеся сверточные функции ошибочны в первых и послелпих 812 — 1 точках каждой свертки, но все эти точки суммируются и Лают правильную свертку при трансляции каждого свернутого сигнала в точку его истинного начала !а + (2), а послелние № — ! точек свертки находятся путем наложения одного сегмента па другой. Данный процесс иллюстрируется па рис.
5.31. Подьпожим: вначале для устранения краевых эффектов к сегментам добавляется достаточное число нулей, затем результаты свертки накладываются друг на лруга точно так, как последовательность длиной Х! дополнялась нулями, а з нем находится их сумма. Название метода — паложепие-сложе~ие — следует нещ1срслствшшо из выполняемых действий, 332 Глава 5. Корреляция и свертка Обьжсть яатожеши 1 Область паложсяяя 2 .тр(п) Я(п) 1 а) л.'(п) * Ь'(п), смещеявоелля пишжеши- сложснпя 2 ! о я,п) * )бп) а) Область яаложепая 1 Область яаложепня 2 рстуесьтат свертка с лаложспясм сложсяшм я прямой свертки Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
