Айфичер Э., Джервис Б. Цифровая обработка сигналов, практический подход (2-е изд., 2004) (1095888), страница 58
Текст из файла (страница 58)
5.31. Эквивалентность ьеетода наложеиия-сложения и прямой свертки Пример 5ЛО Используйте процедуру наложения-сложения, чтобы найти свертку двух последовательностей (1 (тг) = 11; О; 1) и и(12) = 11; 3; 2; — 3; О; 2; — 1; О: — 2; 3; — 2; 1;...). Решение Пусть последовательность и(')г) разбита на сегменты длиной Х( = 6, при этом Ж (числоточеквДПФ)равно%1+Юг — ! ---- 6+3 — 1 -- 8 =- 2",глеб сь З,такимобразомудовлетворяются требования к использованию линейной свертки и БПФ по основанию 2.
ззз 5.3. Описание свертки Дополняя 6(11) нулями, получаем тюслсдовательность 6'(11)1 6'(21) = 11;0;1;0;0;0;0;О). Первые две расширенные последовательности х(11) имеют такой вид: х', (и) =- ~ 1; 3: 2; — 3; 0; 2; 0; 0~ х', (н) -:-- 1 — 1; 0', — 2; 3; — 2: 1; 0; 0) . Сверточная сумма х1 (11),*~ 1г'(и) содержит следующие члены: ! уы = 6охго — 1~ У11 = 6ох11 + 61хго = 3+ О = 31 У12 — 6охтг ~ 61хп + 6гхго Утз =- 11ох1з + 61 хтг + 6гх11 — — — 3 + 0 + 3 = О. Уы -- 6ох'„+ 6.',хгз+ 62х12.-: 0+ 0+ 2 -- 2: Утз = 6охы+ 61х11 р 62хгз 2+ 0 Уы -- 6охы + 6,хы + 62х,, =:: О+ О+ О.::= О, У11 6охгт р 61хы ~ бгхы — О ! О+ 2 — 2. Сверточная сумма х' (и) ® 6'(11) состоит из таких компонентов: Уго = '"охго = Угт "- 6охл + 61хго --' 0 + 0 =-' 0 Угг = — 11охгг+ 61хл+ 61хго 2+ 0 У23'6ох23+61х+6х1''3+0+0 — 3 Угз = 6охгз ! 61хгз > 62хгг = 2 + 0 2 = 4 Угз — - 6о ггз + 61х24 + 61 хгз ---.
1 + 0 + 3 -=. 4, У2о 6охго ~ 61хгз+ 62хга = О г О 2 = 2: Угт =- 6охгт + 6тхго + 6гхг, — — 0 + 0+ 1 = 1. Приведенные выше сверточные суммы показаны на рис. 5.31, а и б соответственно. Если первые 1'тг — 1 — 2 точки данных хг наложить на последние 1'т'г — 1 точек данных х', и просуммировать сверточные суммы, получатся первые 12 точек данных данных итогового сверточного сигнала, показанные на рис. 5.31, в.
334 Глава 5. Корреляция и свертка Можно показать, что цриведсццый выше результат идентичен тому, который получается цри прямом вычислении свертки. Исходная последовательность х(п) содержит 12, а )г(~г) — 3 точки данных. Чтобы получить линейную свертку этих двух последовательностей, их нужно дополнить нулями, чтобы длина обеих составляла!2+3 — 1 ==: 14 точек данных. Таким образом, последовательности становятся равцымн 6(п) =--.
11:0; 1;0;0;0;0;0; 0;0;0;0;0:О) х(п) = !1;3:2; — 3:0;2; — 1„0„— 2„3; — 2;1;0;О), Ниже приводятся первые девять членов сверточной суммы. уо = 6озо = 11 уг —— — 6ох1 Р 6'гхо — — 3, уг — 6охг + 6гхг + 6зхо — 2+ О+ ! уз = 6,', х'. + 6', х', + 6.' х', = — 3 + 0 + 3 = О, уг --' Ьоха + 6гхз + 6„'х',:--- 0 + 0 + 2:--- 2, Уз = 6охз + 1ггха + 6гхз = 2+ О того .... йохо + 6 х, + 6зхт -: — -1 + 0+ 0 --= -1, ут = 6охт + 6гхо + 6.',хь = 0 + 0 + 2 =- 2, Уз = 6'„хз + 6', хт 1- 6'.,х'„= — 2 Ч 0 — 1 = — 3. Члены этой сверточной суммы действительно идентичны величинам, полученным методом наложения-сложения, изображенным на рис.
5.31, в. На основе сказанного можно вывести следующую процедуру наложения-сложения для быстрой свертки (или корреляции) с помощью сегментации. 1. Выбрать число дтг данных нослсдовагсльцости х(тг) порядка числа гтг данных последовательности 6(~г) (причем Хг > Лг) и число гочек ДПФ в виде Ж = 2~, где г!— целое и гт » Хз + Хг — 1. Для удовлетворения этим условиям последовательности данных цри необходимости дополняются нулями. 2.
Сместить расширенные сегменты данных:г.1п) в начало координат. 3. Для каждо~о расширенного сегмента данных х(п), х'(тг), найти быструю свертку тОг) ® 6 (тг), т е. вычислить Х (А) Н (6) и затем применить обратное преобразование. 4. Последовательно наложить полученные свертки, совмещая последние Юз — 1 точек одного РезУльтата с Гттг — 1 пеРвыми точками дРУгого, и пРосУммиРовать свеРтки. 5.3.10. Метод наложения-записи Рассмотрим еще раз свертку х!~г) Гяэ 6(~г), проиллюстрированную на рис. 5.32, где к 6(зг) добавлено дтз — 1 нулей, так что обе последовательности имеют длину Дтг. Чтобы получить линейную свертку указанных последовательностей, 6(гг) можно последовательно (гзо одной точке) смещать 6(п) вцраво, проводить перекрестное умножение 335 5.3.
Описание свертки Чз — 1 пвоо1шсннмх тзлся Л", Лапина Ю~ Занима Рис. 5.52. Последовательности с(о ~ и Цо1, причем Ь(о1 дополнена № — 1 нулимн соответствующих членов и суммировать результаты. В то же время, поскольку ни одна последовательность не имеет длины Хт +1ттг — 1, результат не будет равен х(п) См 6(н). Фактически, если длина последовательности х(п) равна Х1, пропущено зтзг — 1 нулей. Это означает, что первые № — 1 членов сверточпой суммы будут неверными, и их следует отбросить.
Следовательно, если данные х(н) делятся на смежные сегменты длины К„первые 1т'г — 1 значений каждой сверточной суммы следует отбрасывать. Значит, свертка х(п) ® 6(п) будет содержать периодическую последовательность пропусков длины № — 1. Данные пропуски можно корректно заполнить, наложив последние Жг — 1 точек данных каждой последовательности х(п) длины 1ттт на первые Жг — 1 точек данных следующей последовательности, а затем отбросив эти первые Хг — 1 точек данных.
Описанная процедура известна как гиетод игьтожеиая-записи. Пример 5.11 Исг1ользуйтс процедуру наложения-записи для свертки последовательностей, приведенных в разделе 5.3хб т.е. 6(в) =-. 11;О: !) х(в) = (113:2; — 3:О;2: — 1;О: — 2:3,' — 2;1). Решение Поскольку для 6(в) 1"11 .=.-.
3, величина наложения !Уг — ! -:= 2. Само наложение выполняется так, как показано па рис. 5.33. Ниже приводится расчет сверток для каждого сегмента. Для сегмента 1: ую 6охто уы -'. 6ох11 ! 61хзо "' !+ О -'- 3: Узг = 6охзг + 61хи + 6гхто = 2 6 О+ ! = 3~ Утз = 6ох1з + 61 хи + 6гхи + 6зх1о = 3 + О + 3+ О =- О. Следовательно, у, =- (1:,3;3;О).
336 Глава 5. Корреляция и свертка Для остальных сегментов следует помнить, что 6, =- 62 = О. Итак, для сегмента 2 тюлучаем: уго -: 6отго утт = 6о"'м =- — 1 У22 --- 6о~22 + 62~то 2 + О У22 60~22 + 62~22 + 622'22 У2 = (2; — 3;'2; — 11. Подобным образом, дла сегмента 3 получаем: Уз — — — (О; 2: — 1, 21. Для сегмента 4: 1У4 —.- (-1; О: -3; 3). Наконец, для сегмента 5 находим: у, = — ( — 2:3: — 4;'1). Данные результаты иллюстрируются в табл.
5.2, из которой видно, что первые Ж2 — 1 результатов каждой последовательности отбрасываются. Последняя строка кроме первой позиции содержит правильное значение свертки. Таблица 5.2. Результаты решения примера 5.11 Сегмент 1 бр у1 3 О 2 3 гр Сегмент 2 Сегмент 3 — 2 У2 бр Сегмент 4 уз — 1 О бр; Сегмент 5 уб 2.(н1 .е. 6Ррн) 2 3 — 4 4 „;бр 3 3 — 4 4 1 3 — 2 3 О 'бр' Таким образом, получаем следующую процедуру наложения-записи.
1. Выбрать число точек данных последовательности ш122) равным зт'г -....- 2" и добавить к 6122) № — 1 нулей, чюбы обе последовательности имели длину Лгг. 2. Разместить обе последовагсльности в начале координат. 3. Для каждой послсдовагелыюсти вычислить соответствующие значения Х1б:) и Х1б:), используя БПФ. ЗЗУ 5.3. Описание свертки Рнс. 5.ЗЗ. Пало>кение сеглгентов для выполнения свертки методом наложения-записи 4.
Вычислить Х® Н (1>) и обратное к нему, которое равно свертке каждой последова- телыюсти с тт(п). 5. Расположить все свертки так, чтобы каждая следующая совмещалась с предыдущей по № — 1 точкам. б. Отбросить первые Лв — 1 точек данных каждой свертки и считать оставшиеся значения, которые соответствуют верной свертке.
5.3.11. Вычислительные преимущества быстрой свертки через сегментацию В разделе 5.3.8 показано, что ненужных вычислений можно избежать, перенеся начало каждого сегмента в начало координат. Предположим, что это уже сделано. Зачем допустим, что вычислительные требования методов наложения-сложения и наложения- записи подобны, поэтому достаточно рассмотреть только первый из этих методов. Предполагается, что последовательность ж(п) длины Лг делится на Ж/Х> сегментов, каждый из которых имеет длину Л„что последователыюсть 6(п) имеет длину тяя и что длины последовательностей, подлежащих линейной свертке, равны № = 2" > Лтт + Лв — 1. КРоме того, в Разделе 5.3.7 было показано, что длЯ выполнениЯ быстРой свеРтки двУх №-точечных последовательностей тРебУетсЯ 12№ зо8я 2№ + 8№ действительных умножений. Следовательно, чтобы выполнить быструю свертку Лгточечной последовательности х(>л) с помощью мегода наложения-сложения, потребуется (Ю/>>№ )(12Лп 1о8 2№+8№):=.
Й,(5) действительных операпий умножения. Отсюда следует, что длина сворачиваемых последовательностей № должна быть малой, а длины ттт сегментов х(п) — близкими к Л". В идса>льном случае № = 2" = Л>+ Ля — 1. Число действительных умножений, необходимых для обработки исходной Лг-точечной последовательности, Равно 12% 1окя 2Л> + 8Л> -:= 11„(Л>).
Из табл. 5.3 следУет, что длЯ примера из раздела 5.3.9 отношение й (5)~77„,(Лг) < 1, при этом экономия времени вычислений может составлять порядка 50о4. ззв Глава 5. Корреляция и свертка Таблица 5.3. Отношение Я (Я)/Я (М) (числа действительных умножений для метода сегментации к числу действительных умножений при быстрой свертке обычным образом) Ь Л Ж тт (~ь Лг 72 (Д)/ т1п (®) клмнентирнй Наилучший результат лрл малом у „ дч =ж ж -жз 1020 8 6 170 0,54 1024 256 254 4 1020 128 102 1О 1020 256 204 5 0,83 0.93 1,04 5.3.12.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
