18. Вычисление периодической, круговой и линейной свертки. Алгоритм быстрой свертки. Вычислительная эффективность.

Свертка является одной из основных операций, выполняемых при решении многих задач теории цифровых систем, а также при их разработке и применении. Задачи, связанные с вычислением свертки, часто встречаются в электротехнике, статистике, оптике и других областях физики. Это – фильтрация, спектральный анализ, преобразование изображений, задачи, связанные с теорией поля (акустика, распространение волн, электричество и магнетизм).

Свертка, кроме того, – основная операция при выполнении интерполяции. При обработке сигналов часто сталкиваются с ситуацией, когда период выборки больше, чем требуется. В этом случае для получения значений между имеющимися отсчетами можно воспользоваться интерполяцией, которая состоит в том, что вычисляется некоторая взвешенная сумма по соседним отсчетам.

Как известно, принято различать периодическую, круговую и линейную (апериодическую) свертки двух последовательностей. Рассмотрим методы вычисления каждой из них.

Пусть имеются две периодические последовательности и с периодом N. И пусть коэффициенты их дискретного ряда Фурье есть и соответственно.

Периодической сверткой этих последовательностей является последовательность определяемая выражением:

(1.173)

Последовательность также является периодической с периодом N. Поэтому периодическую свертку достаточно вычислить на одном периоде.

Коэффициенты дискретного ряда Фурье последовательности будет определяться следующим образом:

(1.174)

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

(1.175)

где

Соответствующее ДПФ последовательности будет определяться произведением ДПФ исходных последовательностей, т. е.

(1.176)

При малых значениях N возможно и непосредственное вычисление круговой свертки по соответствующей формуле. Однако при последовательностях большой длительности возникают существенные вычислительные трудности. Поэтому в таких случаях для вычисления свертки используют прямое и обратное дискретное преобразование Фурье. С этой целью для заданных последовательностей и вычисляют соответствующие им ДПФ и Полученные последовательности перемножаются. Для последовательности вычисляется обратное ДПФ, что дает искомую последовательность

(1.177)

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

Линейная свертка, представляющая основной интерес для практических приложений, определяется следующим образом:

(1.178)

где и – конечные последовательности длительности N.

Непосредственно проверяется, что имеет длину 2N – 1, т. е. она может иметь самое большое 2N – 1 ненулевых отсчетов.

Если последовательность получается путем нахождения обратного дискретного преобразования Фурье после перемножения ДПФ последовательностей и то каждое из этих преобразований Фурье и должно вычисляться на основе 2N – 1 точек, т. е. в этом случае вычислительная процедура будет выглядеть следующим образом:

(1.179)

Здесь и будет линейной сверткой и

Следует отметить, что линейная свертка была бы получена, если бы ДПФ вычислялось на основе более чем 2N – 1 точек. Но в общем случае линейная свертка не получилась бы, если бы ДПФ вычислялось на основе меньшего числа точек.

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

Первый метод, основанный на использовании алгоритмов БПФ и получивший название метода быстрой свертки, приводит к существенному сокращению требуемого числа арифметических операций. Действительно, необходимые расчеты для прямого метода вычисления показывают, что для получения линейной свертки двух N-точечных последовательностей x₁(m) и x₂(n – m) следует умножить каждое значение x₁(m) на каждое значение x₂(n – m). Следовательно, N значений x₁(m) нужно перемножить с N значениями x₂(n – m), в результате чего требуется N  N = N² умножений.

При вычислении линейной свертки тех же двух N-точечных последовательностей с помощью алгоритмов БПФ прибавление необходимых дополняющих нулей означает, что каждая последовательность будет иметь длину 2N – 1 точек. Пусть 2N – 1  2 N. так как число комплексных умножений для N-точечного БПФ равна то для 2N-точечного БПФ необходимо или комплексных умножений. В соответствии с процедурой вычисления свертки требуется вычислить два ДПФ и одно обратное ДПФ, которое можно рассчитать с помощью модифицированного ДПФ. Следовательно, необходимо вычислить 2N-то­чечных БПФ, включающих в сумме комплексных умножений. Кроме того, для каждого из 2N значений необходимо выполнить комплексное умножение Таким образом, общее число комплексных умножений возросло до Далее комплексное умножение вида требует четырех действительных умножений AC, AD, BC и BD. Значит, в целом необходимо действительных умножений.

В табл. 1.9 сравнивается число действительных умножений, необходимых для вычисления линейной свертки двух последовательностей при различных N. Как видно, быстрая свертка эффективнее прямого метода для значений N  128.

Таблица 1.9