Однако в общем случае результаты фильтрации дискретного сигнала в частотной области не совпадают с дискретной линейной сверткой.

Различия являются следствием:

- предположения о периодическом продолжении сигналов за пределами окна анализа при вводе понятия ДПФ;

- размерность выходного сигнала ДПФ совпадает с размерностью входного сигнала.

Различия для цифрового фильтра в виде задержки на один временной дискрет приведены на рисунке 9.4.

Рисунок 9.4 – различия линейной свертки и свертки в частотной области

9.1.3. Дискретная круговая свертка

Результатом применения обратного дискретного преобразования Фурье (ОДПФ) к дискретному спектру является свертка периодических последовательностей и , которая называется круговой:

. (9.11)

9.1.4. Связь круговой и линейной сверток

Если имеются исходные конечные последовательности и с длительностями и , то их нужно дополнить нулями до числа отсчетов .

Длины двух последовательностей становятся одинаковыми и равными длине линейной свертки исходных последовательностей.

В этом случае круговая свертка дополненных таким образом нулями исходных последовательностей и будет соответствовать линейной свертке исходных последовательностей:

. (1.13)

Рисунок 9.5 – вычисление линейной свертки с помощью круговой

9.1.5. Быстрая линейная свертка

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

Необходимо выбрать количество нулей таким, чтобы длина получившейся последовательности была равна целочисленной степени двойки, чтобы можно было использовать БПФ.

Таким образом, алгоритм быстрой фильтрации в частотной области имеет вид:

1. Последовательности отсчетов входного сигнала и импульсной характеристики дополняются нулями, чтобы длины последовательностей стали

- равными

- и не меньшими (целочисленная степень двойки),чем сумма длин исходных последовательностей минус единица (длительность линейной свертки).

2. Вычисляются БПФ дополненных нулями последовательностей.

3. Вычисленные БПФ поэлементно умножаются.

4. Вычисляется обратное БПФ от результата перемножения.

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

Очевидно, что для получения линейной свертки двух N-точечных последовательностей и необходимо умножить каждое значение на каждое значение . Следовательно, N значений нужно перемножить с N значениями и потребуется всего умножений.

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

Таким образом, непосредственное вычисление линейной свертки требует действительных умножений, в то время как метод быстрой свертки требует действительных умножений. Сравнительный анализ вычислительных затрат для быстрой линейной свертки и непосредственно линейной свертки приведен в Таблице 9.1. Из Таблицы видно, что быстрая свертка лучше прямого метода в том случае, если длина последовательностей превышает 128 дискретов данных. Для последовательности из 1024 точек быстрая свертка дает результат за время, в 10 раз меньшее, чем для линейной свертки.

Таблица 9.1. Вычислительные затраты линейной свертки и быстрой линейной свертки

Литература

Маркович И.И. Цифровая обработка сигналов в системах и устройствах: монография / И.И. Маркович; Южный федеральный университет. – Ростов н/Д: Издательство Южного федерального университета, 2012. – 236 с. (стр. 62)

Солонина А.И., Арбузов С.М. Цифровая обработка сигналов: Курс лекций. / А.И. Солонина, С.М. Арбузов. – СПб.: БХВ – Петербург, 2007 – 744 с (232 c.).

Лозовский И.Ф. Цифровая обработка сигналов в РЛС обзора: монография / И.Ф. Лозовский. – Новосибирск: Изд-во НГТУ, 2016. – 270 с. (с. 73)

Цифровая обработка сигналов в многофункциональных радиолокаторах. Методы. Алгоритмы. Аппаратура. Коллективная монография / Под ред. Г.В. Зайцева. – М.: Радиотехника, 2015. – 376 с. (с. 93)