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() - полином степени N₁+N₂-2, то он может быть представлен вычетом по модулю полинома степени N  N₁+N₂-1 и, в частности, по модулю ^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. Показать на примере вычисления свертки двух последовательностей, состоящих соответственно из 4 и 15 отсчетов, что алгоритм перекрытия с накоплением более эффективен алгоритма перекрытия с суммированием.

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

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

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

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