2.24. Линейная свертка конечных последовательностей

Рассмотрим две конечные последовательности  и  длины по  и  отсчетов, т. е.  отлична от нуля при , a  — при . Линейной или апериодической сверткой этих последовательностей называют последовательность , определяемую соотношением

где  и  равны нулю вне соответствующих интервалов. На фиг. 2.30 приведены примеры последовательностей ,  и . Ясно, что последовательность  является конечной и имеет длину  отсчетов.

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

Фиг. 2.30. Линейная (апериодическая) свертка.

Фиг. 2.31. Вычисление линейной свертки с помощью круговой свертки.

В результате получается искомая свертка . На фиг. 2.31, иллюстрирующей эти операции, изображены эквивалентные периодические последовательности, используемые при вычислении круговой свертки. Ясно, что дополнение исходных последовательностей конечной длины  и  нулевыми отсчетами доводит период до нужной величины и позволяет устранить круговые наложения, характерные для круговой свертки. В результате каждый период последовательности  (фиг. 2.31) совпадает с  (фиг. 2.30). Рассмотренный метод вычисления свертки двух конечных последовательностей с применением алгоритма ДПФ называется быстрой сверткой в противоположность методу прямого вычисления суммы (2.165), называемому прямой или медленной сверткой. Термин «быстрая» применяется потому, что ДПФ можно вычислить быстро и эффективно, используя один из алгоритмов быстрого преобразования Фурье (БПФ). Можно показать, что даже при умеренных величинах  (например, порядка 30) быстрая свертка оказывается эффективнее прямой. Поэтому рассмотренная методика является важным вычислительным средством при обработке сигналов.

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