Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 40
Текст из файла (страница 40)
На вход свертки могут поступать две последовательности во временной области, при этом результат будет тоже последовательностью во временной области или две последовательности в частотной области, преобразуемые в последовательность в частотной области. (Хотя для того, чтобы свертка имела какой-то практический смысл, обе последовательности должны принадлежать одной области, их длины не обязательно должны быть равными.) Допустим, мы имеем две последовательности Ь(Ь) длины Р и х(Ь) длины Я во временной области.
Выходная последовательность свертки у(п) двух входных последовательностей определяется формулой у(п) = Я Ь(Ь)х(п-Ь), (5-26) у(0) = Ь(0)х(0 — О) + Ь(1)х(0 — 1) + Ь(2)х(0-2) + Ь(3)х(0 — 3) э Ь(4)х(0 — 4) э Ь(5)х(0-5), у(1) - Ь(0)х(1 — О) + Ь(1)х(1-1) + Ь(2)х(1 — 2) + Ь(3)х(1 — 3) + Ь(4)х(1-4) + Ь(5)х(1-5), у(2) = Ь(0)х(2 — О) ь Ь(1)х(2 — 1) ь Ь(2)х(2-2) -~ Ь(3)х(2 — 3) + Ь(4)х(2 — 4) + Ь(5)х(2 — 5), у(3) = Ь(0)х(3 — О) + Ь(1)х(3- 1) + Ь(2)х(3 — 2) + Ь(3)х(3 — 3) + Ь(4)х(3 — 4) ь Ь(5)х(3 — 5), у(4) = Ь(0)х(4 — О) + Ь(1)х(4 — 1) + Ь(2)х(4 — 2) э Ь(3)х(4-3) + Ь(4)х(4-4) + Ь(5)х(4-5), и у(5) = Ь(0)х(5 — О) ь Ь( 1)х(5 — 1) -ь Ь(2)х(5 — 2) + Ь(3)х(5 — 3) ь Ь(4)х(5 — 4) + Ь(5)х(5-5).
(5-27) Рассмотрим (5-26) на примере, используя последовательности Ь(Ь) и х(Ь), показанные на рисунке 5.38. В этом примере мы можем записать слагаемые для каждого у(п) в (5-26) как 5.9. Обобщенное описание диск гной све тки 207 -3-2-1 О 1 2 3 4 6 6 Ь -3-2-1 О 1 2 3 4 6 6 (а) (Ь) Рис. 6.38. Входные последовательности для примера свертки: (а) первая последовательность й(Ь) длины Р= 4; (Ь) вторая последовательность к(Ь) длины 0 =3 При Р- 4 и Д -3 мы должны вычислить только 4 + 3 — 1 = б отдельных слагаемых у(п). Поскольку Ь(4) и Ь(5) равны нулю, мы можем отбросить некоторые слагаемые в (5-2?) и вычислить оставшиеся, представив у(п) в виде: у(0) = Ь(0)х(0) + Ь(1)х( — 1) + Ь(2)х( — 2) + Ь(3)х( — 3), у(1) - Ь(0)х(1) -ь Ь(1)х(0) + Ь(2)х( — 1) 1- Ь(3)х( — 2), у(2) = Ь(0)х(2) 1- Ь(1)х(1).
+ Ь(2)х(0) + Ь(3)х( — 1), у(3) = Ь(0)х(3) + Ь(1)х(2) + Ь(2)х(1) -ь Ь(3)х(0), у(4) = Ь(0)х(4) + Ь(1)х(3) -ь Ь(2)х(2) + Ь(3)х(1), у(5) - Ь(0)х(5) + Ь(1)х(4) + Ь(2)х(3) + Ь(3)х(2). (5-28) Рассматривая индексы переменных Ь(Ь) и х(Ь) в (5-28), мы видим два важных момента. Во-первых, свертка представляет собой просто сумму поэлементных произведений, так что это не очень сложный процесс. Во-вторых, заметьте, что для заданного у(п), индекс Ь(Ь) возрастает при уменьшении индекса х(Ь).
Это дает основание некоторым авторам ввести новую последовательность х( — Ь) и использовать ее для графического изображения процесса свертки. Последовательность х( — Ь) представляет собой просто нашу исходную последовательность х(Ь), зеркально отображенную относительно индекса О, как показано на рисунке 5.39. Такое определение х( — Ь) дает нам возможность изобразить процесс перемножения и суммирования в (5-28) так, как показано на рисунке 5.40; т.
е. мы теперь можем для вычисления у(п) расположить отсчеты х( — Ь) напротив соответствующих отсчетов Ь(Ь) при текущем значении индекса л. Как показано на рисунке 5.40 (а), выравнивание отсчетов Ь(Ь) их(п-Ь) при и - 0 дает у(0) - 1. Это совпадает с результатом вычисления в первой строке (5-28), которую мы повторили в правой части рисунка 5.40 (а).
Вычисление у(1), при и = 1, изображено на рисунке 5АО (Ь), где последовательность х(л — Ь) сдвинута на один элемент вправо, в результате чего получаем у(1) - 3. Мы продолжает этот сдвиг последовательности х(п — Ь) и увеличение индекса и до тех пор, пока не получим последний ненулевой отсчет свертки у(5), показанный на рисунке 5.40 (г). Итак, выполнение свертки Ь(Ь) и х(Ь) состоит из следующих шагов: Шаг 1: построение графиков последовательностей Ь(Ь) и х(Ь). Шаг2: зеркальное отображение последовательности х(Ь) относительно значения Ь - 0 для получения х( — Ь).
аОВ Глава5. Фильт ысимп льснойха акте истикойконечнойдлины Шаг 3: суммирование произведений Ь(Ь) и х(0 — Ь) для всех Ь для получения у(0). Шаг 4: сдвиг х( — Ь) на один отсчет вправо. Шаг 5: суммирование произведений Ь(Ь) и х(1 — Ь) для всех Ь для получения у(1). Шаг 6: сдвиг последовательности и суммирование произведений до тех пор, пока последовательность Ь(Ь) перекрывается сдвинутой последовательностью х(л — Ь), после чего все дальнейшие отсчеты у(п) остаются равными нулю, и вычисления заканчиваются. Полная свертка последовательностей Ь(Ь) их(Ь) представляет собой последовательность у(л), показанную в правой части рисунка 5АО ((). Мы прошли последовательностью х( — Ь) вдоль последовательности Ь(Ь) и просуммировали произведения перекрывающихся отсчетов. Кстати, обратите внимание на то, что последовательность у(л) на рисунке 5.40 (() содержит шесть ненулевых отсчетов, тогда как Ь(Ь) имела четыре таких отсчета, а последовательность х(Ь) — три.
В общем случае, если Ь(Ь) имеет длину Р, ах(Ь) имеет длину Я, у(л) будет иметь длину А, где (5-29) Ь =(Р+ ΄— 1) ~ х(й) 3 1 о -3 -2 -1 О 1 2 3 4 5 6 К -3 -2 -1 О 1 2 3 4 5 6 й (а) (Ь) Рис. 5.39. Входная последовательность для примера вычисления свертки: (а) вторая последовательность х(Ь) длины 3; (Ь) зеркальное отображение второй последовательности относительно индекса к = 0 Здесь начинающий читатель вполне может задать вопрос: «Хорошо, ну и что из этого? Какое отношение этот странный процесс вычисления свертки имеет к цифровой обработке сигналов?» Ответ на этот вопрос опирается на понимание значения теоремы о свертке. 5.9.2. Теорема о свертке Теорема о свертке представляет собой краеугольный камень цифровой обработки сигналов.
Она проявляет себя всегда, когда мы фильтруем дискретные данные или выполняем ДПФ. Чтобы увидеть, почему это так, упростим запись (5-26) и будем использовать сокращенную форму у(л) =Ь(Ь)»х(Ь), (5-30) где символ» обозначает операцию свертки. 5.9. Обобщенное описание диск етной све тки 209 у(0) = Ь(0)х(0) + Ь(1)к(-!) + Ь(2)х(-2) т И(3)х(-3) = 1 + О + О т О = 1 свертка 49С:» О О 1 2 3 4 5 б 7 8 и -4 -3 -2 -1 О 1 2 3 4 5 5 свертка оп=1 О 1 2 3 4 5 б 7 8 и -4 -3 -2 -1 0 1 . 2 3 4 5 6 Иг) = Ь(0)х(2) + Ь(1)х(1) + Ь(2)ИО) + Ь(З)х(-1> .4 = з + г + ! + о = 6 6 свертка ел=2 О 1 2 3 4 5 б 7 8 л Из) = 140)жз> т ь(1)к(2> к ь(2>х(1) + ь(3лко) С =ОтЗтг. 1=6 Ф а свертка О 1 2 3 4 5 б 7 8 и -4 -3 -2 -1 0 1 2 3 4 5 6 д У(4) = Ь(0)к(4) + Ь(1)ИЗ) + Ь(2)Х(2) + Ь(З>к(1) ° % =0 Отз+2=5 Ю свертка ел=4 О О 1 2 3 4 5 6 7 8 и свертка сп=5 О 1 2 3 4 5 6 7 8 и Рис. 5.40.
Графическое изображение процесса вычисления свертки последовательностей ))()() и к()(), приведенных на рисунке 5.38 о -5 -4 -3 .2 -1 0 1 2 3 4 5 (а) З х(О-И) г 1 о 0 -5 .4 -3 -2 -1 0 1 2 3 4 5 6 (Ь) з (! Ь) 2 1 0 0 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 (С) з (гв а 2 1 0 -4 -3 -2 -1 0 1 2 3 4 5 6 Ь 0 -5 -4 -3 -2 .1 0 1 2 3 4 3 х(3 К) а 2 1 0 0 -5.4-3-2-1 01 23 4 56 (е) з г 1 0 -4 -3 -2 -1 0 1 2 3 4 5 5 0 -5 -4 -3 .2 -1 0 1 2 3 4 5 6 (~т 3 х(5-х> кт 2 1 О -4 -3 -2 -1 0 1 2 3 4 5 6 И1) = Ь(0)х(1) + Ь(1)х(О) + Ь(2)х(-1) + Ь(3)х(-2) = 2 + ! к О т О = 3 4 2 О 4 2 О 4 а 2 О 1 ° И5) = Ь(О)х(5> т Ь(1)х(4) + Ь(2)к(З) + Ь(3)42> 6 а и а % 2 О 210 Глава 5.
Фильт ы с имп льсной хе акте исгикой конечнойдлины Теорему о свертке можно сформулировать следующим образом: если две последовательности во временной области Ь(Ь) их(Ь) имеют ДПФ Н(т) и Х(т) соответственно, то ДПФ свертки Ь(Ь) + х(Ь) представляет собой произведение Н(т) ° Х(т).
Аналогично, обратное ДПФ произведения Н(т) 'Х(т) дает свертку Ь(Ь) + х(Ь). Мы можем представить это соотношение как дпФ Ь(Ь) «х(п) Н(т) ° Х(т) (5-31) ОДПФ Соотношение (5-31) говорит о том, что две последовательности Ь(Ь)+х(Ь) и Н(т) 'Х(т) образуют пару преобразований Фурье. Таким образом, ДПФ свертки Ь(Ь)+х(Ь) всегда дает произведение Н(т) Х(т). Мы можем также вычислить свертку Ь(Ь)»х(Ь), выполнив обратное ДПФ последовательности Н(т) 'Х(т). Мы должны усвоить важный вывод из (5-31), который состоит в том, что выполнение свертки во временной области эквивалентно умножению в частотной области. (Мы не будем здесь доказывать теорему о свертке, потому что ее доказательство имеется в ряде доступных книг [26-29].) Чтобы помочь нам в этом, на рисунке 5.41 в наглядной форме показано соотношение между сверткой во временной области и умножением в частотной области.
Временная область Па преобра Фу Частотная область Рис. 5.41. Соотношения теоремы о свертке Мы можем легко продемонстрировать теорему о свертке, вычислив 8-точечные ДПФ последовательностей Ь(Ь) и х(Ь) для получения Н(т) и Х(т) соответственно и записав полученные значения в таблицу 5.3. (Конечно, мы должны дополнить последовательности Ь(Ь) и х(Ь) нулями так, чтобы обе они имели длину 8.) Вычисление и занесение в таблицу обратного ДПФ произведения Н(лг) Х(т) позволяет 5.9. Обобщенное описание диск етной све тки 211 нам проверить (5-31) по данным, приведенным в двух последних колонках таблицы 5.3, где аббревиатура ОДПФ обозначает обратное ДПФ. Значения, приведенные в таблице 5.3, показаны на рисунке 5А2. (Для простоты на рисунке приведены только модули Н(т), Х(т) и Н(т) ' Х(т).) Нам необходимо освоить свертку во временной области, потому что, как мы уже знаем, она используется в КИХ- фильтрах.