4. Свертка сигналов

4.1. Линейная и циклическая свертки

Дискретным эквивалентом линейного аналогового фильтра (согласованного, полосового и т.п.), выходной сигнал которого определяется интегралом свертки

является дискретный фильтр, формирующий весовую сумму (линейную свертку):

, (k-n)³0.               (99)

Здесь x[n]=x(nDt), n=0,1,2,…, - сигнал на входе фильтра, h[k-n] – весовые коэффициенты, определяющие импульсную характеристику аналогового фильтра h(t), N-  объем выборки. Для реализации цифрового фильтра необходимы устройства, выполняющие операции сложения, умножения и задержку.

В более общем виде можно рассмотреть класс линейных инвариантных к сдвигу (ЛИС) систем, который включает много полезных, широко используемых методов обработки сигналов, в том числе и фильтрацию сигналов. Соотношение вход-выход для ЛИС систем задается в виде свертки

,

где  - входной сигнал;  - множество отсчетов выходного сигнала; - импульсный отклик ЛИС системы; символ звездочка как двучленный оператор означает свертку.

Система ЛИС полностью определяется своим импульсным откликом . Считается, что система является каузальной тогда и только тогда, когда  при n < 0.

Рекомендуемые материалы

Если импульсная реакция имеет конечную длительность , то бесконечная сумма сводится к конечной сумме

.

Предположим, что обрабатываются два каузальных цифровых сигнала длиной L и  длиной M. Тогда линейная (апериодическая) свертка этих сигналов имеет длину (L + M –1) и определяется как

.                                               (100)

Если L = M , то выражение для линейной свертки можно записать в матричном виде

.         (101)

В большинстве алгоритмов вычисления свертки входная последовательность  делится на последовательные блоки по L отсчетов и  вычисляется как сумма линейных сверток каждого из этих блоков с M точечной последовательностью .

Используя понятия алгебры полиномов, процесс вычисления линейных сверток y(b) можно представить в виде произведения двух полиномов x(b) и h(b):

,         ,

.                                 (102)

Рассмотрим поведение свертки относительно дискретных преобразований. Начнем с дискретного преобразования Лапласа. Z-преобразование дискретной последовательности  имеет вид

.

Фундаментальным свойством ЛИС является соотношение, согласно которому операция свертки во временной области, соответствует операции умножения в области Z-преобразований:

.                                       (103)

Важным классом ЛИС систем являются системы, имеющие z – преобразование в виде рациональных функций. В этом случае H(z) = B(z)/A(z), где  и  – полиномы конечной степени. Так как Y(z) = H(z) X(z), то получаем A(z) Y(z) = B(z) X(z). Во временной области отклик системы и входное воздействие связаны между собой разностным уравнением

.

Без потери общности можно положить a₀ = 1.Тогда отклик системы на заданное входное воздействие при известных начальных условиях запишется как следующее рекуррентное соотношение

.

Заметим, что в рекуррентном соотношении каждая сумма представляет собой оператор свертки. Импульсный отклик такой системы имеет бесконечную длительность. Такие системы называют системами с бесконечной импульсной характеристикой (БИХ) или рекурсивными системами.

Важный подкласс множества рациональных Z-преобразований имеет знаменатель A(z) =1. В этом случае рекуррентное соотношение не содержит членов обратной связи, а отклик y[n] представляет собой просто свертку входного воздействия x[n] с коэффициентами b_k  полинома B(z). Такие системы  часто называют системами с конечной импульсной характеристикой (КИХ) или нерекурсивными системами.

Определим ДПФ для входного воздействия и импульсной характеристики ЛИС:

 и .

Рассмотрим обратное ДПФ произведения двух ДПФ X(k) H(k):

.

Подставив сюда определение X(k) и изменив порядок суммирования, получаем

,

откуда следует

.

Для того чтобы полученное выражение имело смысл, необходимо периодически продолжить сигнал h[n-l] с периодом N. С учетом периодического продолжения выражение для y[n] можно переписать как

.                                             (104)

В силу периодичности последовательностей номера отсчетов берутся по модулю N, поэтому x[-n] = x[N-n] и h[-n] = h[N-n]. Полученная сумма называется N-точечной циклической сверткой. В матричном виде циклическая свертка записывается как

                 (105)

Матрица вида  относится к классу ганкелевых, а матрицу вида  часто называют циркулянтной, или теплицевой. Циркулянтные матрицы занимают особое место в области математики, связанной с разработкой эффективных алгоритмов [5].

Используя алгебру полиномов, циклическую свертку можно записать в виде произведения двух многочленов свертываемых последовательностей по модулю полинома (b^N-1):

.                                                 (106)

В матричном виде, через матрицы Ганкеля и Теплица циклическая свертка запишется как

Если обозначить значения линейной и циклической сверток соответственно как  и , при L=M=N можно выразить одни значения свертки через другие следующим образом:

Таким образом, если положить равными нулю значения , , , то линейную свертку можно вычислить через циклическую.

Полином линейной свертки  имеет степень L+M-2 и он совпадает со своим вычетом по модулю полинома p(b), имеющего степень L+M-1:

.

Предположим, что полином модуля разлагается на взаимно простые линейные множители над полем коэффициентов F

,

где a_i-есть L+M-1 различных корней p(b) в поле F.

Согласно алгоритму Тоома-Кука линейная свертка может быть вычислена за L+M-1 операций умножения. При этом x[i], h[i] - рассматриваются как переменные, через которые выражаются значения y[i]. Для этого следует выбрать L+M-1 различных чисел (интерполяционных узлов) g_i и подставить их вместо b в выражение для свертки. Получим произведения линейных выражений. Затем применим интерполяционную формулу Лагранжа для однозначного определения полинома степени L+M-2:

.                                     (107)

С другой стороны, полиномы x(g_i=a_i), h(g_i=a_i) можно рассматривать как вычеты полиномов h_i(b) x_i(b) по модулю (b-a_i):

.

Полином свертки может быть восстановлен по формуле

,

где , , .   (108)

Так как поле коэффициентов F и интерполяционные узлы могут быть выбраны произвольно, то в качестве a_i - выберем набор из L+M-1 последовательных степеней числа W, считая их попарно различными в поле F. В этом случае  и приведение по модулю (b - a_i) выражается следующим образом:

.

Аналогичное выражение получается и для . Таким образом, в результате специального набора a_i алгоритм Тоома-Кука сводится к вычислению циклических сверток с помощью преобразований, имеющих структуру ДПФ.

Если , то алгоритм Тоома-Кука можно рассматривать как вычисление апериодической свертки с помощью ДПФ. В этом случае полином p(b) имеет вид

.

Следовательно, если узлы интерполяции выбираются комплексными корнями из единицы, то алгоритм Тоома-Кука эквивалентен вычислению с помощью ДПФ циклической свертки двух входных последовательностей длиной L+M-1, получающихся добавлением (L – 1) нулей к  h  и (M – 1) нулей к  x.

4.2. Алгоритмы свертки квазибесконечной последовательности

На практике при цифровой фильтрации приходится иметь дело с линейной сверткой y[k], ограниченной последовательностью h[k] (импульсной характеристикой цифрового фильтра) с квазибесконечной последовательностью данных x[n]. Для эффективного вычисления линейной свертки нужно уметь преобразовывать ее в серию циклических сверток. Это можно сделать двумя методами. Первый называется методом перекрытия с суммированием, второй – перекрытием с накоплением.

Алгоритм перекрытия с суммированием. Алгоритм на первом шаге разбивает входную последовательность x[n] на v смежных блоков  длиной N₂, m=u+vN₂, u=0,1,…N₂-1 и v=0,1,2,… для последовательных блоков. Линейная свертка каждого из этих блоков  с последовательностью h[n] длиной N₁ дает выходную последовательность  из N₁+N₂-1 членов. В полиномиальных обозначениях вычисление этой свертки равносильно нахождению коэффициентов полинома

,

где

, , .      (109)

Так как y_v(b) - полином степени N₁+N₂-2, то он может быть представлен вычетом по модулю полинома степени N ³ N₁+N₂-1 и, в частности, по модулю b^N-1. В этом случае последовательные линейные свертки y_v[l] вычисляются как N-точечные циклические, в которых входные блоки получаются добавлением (N-N₁) нулей в конце последовательности h и (N-N₂) нулей в конце последовательности .

Смежные блоки перекрываются в (N-N₂) позициях. Соответствующие этим перекрытиям выходные отсчеты суммируються и дают в результате истинный результат. Таким образом, если N = N₁+N₂-1, то при цифровой фильтрации вычисляется одна циклическая N-точечная свертка на каждые N₂ выходные отсчета плюс (N₁-1)/(N-N₁+1) сложений на каждый отсчет.

Алгоритм перекрытия с накоплением. Алгоритм разбивает входную последовательность на v перекрывающихся блоков  длиной N при m=u+vN, u = 0,1,…N-1 и v = 0,1,2,… для последовательных блоков. При этом каждый входной блок имеет длину N, а не N₂, как для перекрытия с суммированием, и перекрывается с предшествующим блоком в N- N₂ отсчетах. Выход цифрового фильтра представляет собой последовательные циклические N-точечные свертки блоков  с блоками длиной N, получающиеся в результате добавления N- N₁ нулей к h. Следовательно, выход каждой циклической свертки можно записать как

,

.                        (110)

Предположим, что N = N₁+N₂-1, тогда для l₁ ³ N₁-1 разность  всегда равна , так как все отсчеты последовательности h нулевые при n > N₁-1. Следовательно, последние (N – N₁ + 1) выходные члены каждой циклической свертки являются действительными выходными значениями цифрового фильтра, тогда как первые (N₁ – 1) выходные члены циклической свертки должны игнорироваться, поскольку они соответствуют перекрывающимся интервалам.

Можно показать, что алгоритм перекрытия с накоплением формирует N – N₁ + 1 выходных отсчетов цифрового фильтра без добавочного суммирования. Таким образом, этот алгоритм предпочтительнее алгоритма перекрытия с суммированием.

Контрольные вопросы и задачи

Если Вам понравилась эта лекция, то понравится и эта - 1.2 Геометрические характеристики плоских сечений.

1. Написать алгоритм вычисления линейной свертки с помощью ТЧПФ для задачи согласованной фильтрации кода Баркера.

2. Показать на примере вычисления свертки двух последовательностей, состоящих соответственно из 4 и 15 отсчетов, что алгоритм перекрытия с накоплением более эффективен алгоритма перекрытия с суммированием.

3. Синтезировать полиномиальный алгоритм трехточечной циклической свертки.

4. Вычислить линейную свертку последовательностей x=[1,2,-1]^T и h=[1,-1,1,1]^T.

5. Используя интерполяционную формулу Лагранжа, вычислить произведение двух полиномов, используя следующие точки интерполяции: 0, 1, -1, 2, -2.

6. Синтезировать алгоритм вычисления корреляционной функции сигнала с помощью циклической свертки, используя понятия теплицевой и ганкелевой матриц.