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

Рассмотрим две конечные последовательности x(n) и h(n) длины по N₁ и N₂ отсчетов.

Последовательность x(n) отлична от нуля при 0  n  N₁ – 1, a последовательность h(n) — при 0  n  N₂ – 1. Линейной или апериодической сверткой этих последовательностей x(n) и h(n) называют по­следовательность y(n), определяемую соотношением

y(n) =h(m) x(n – m), (5)

здесь h(m) и x(n – m) равны нулю вне соответствующих интерва­лов.

Последовательность y(n) конеч­ная – имеет длину (N₁ + N₂ – 1) отсчетов – рис. 2.

Обратным преобразованием Фурье произведения ДПФ двух конечных последовательностей полу­чаем такой же результат, как при круговой свертке эквивалентных пе­риодических последовательностей, образованных из данных конечных последовательностей. Исходя из это­го, можно получить линейную свертку двух конечных последовательностей – рис. 1. Свертка пери­одических последовательностей пери­одична и имеет тот же период, что и сами последовательности.

Рис. 2. Линейная (апериодическая) свертка

Период свертки y(n) равен (N₁ + N₂ – 1) отсчетам, поэтому для получения такого периода при кру­говой свертки необходимо, чтобы x(n) и h(n) содержали по (N₁ + N₂ – 1) отсчетов, что достигается дополне­нием каждой из двух последователь­ностей соответствующим числом нулевых отсчетов – рис. 2. После этого можно найти (N₁ + N₂ – 1)-точечных ДПФ дополненных последовательностей, перемножить их и выполнить обратное ДПФ произведения. В ре­зультате получается искомая свертка y(n). На рис. 6.3 изображены эквивалентные периоди­ческие последовательности, используемые при вычислении кру­говой свертки; дополнение исходных последовательно­стей конечной длины x(n) и h(n) нулевыми отсчетами доводит период до нужной величины и позволяет устранить круговые наложения, характерные для круговой свертки. В результате каждый период последовательности y_p(n) совпадает с последовательностью y(n) – рис. 3 и 2.

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

Метод вычисления свертки двух ­конечных последовательностей с применением алгоритма ДПФ называется быстрой сверткой в противоположность методу пря­мого вычисления суммы (5), называемому прямой или медлен­ной сверткой. Термин «быстрая» применяется потому, что ДПФ можно вычислить быстро и аффективно, используя один из алго­ритмов быстрого преобразования Фурье (БПФ). Можно пока­зать, что даже при умеренных величинах (N₁ + N₂ – 1) (напри­мер, порядка 30) быстрая свертка оказывается эффективнее пря­мой. Поэтому рассмотренная методика – полезное вычи­слительное средство при обработке сигналов.

Для практических приложений важно отметить, что в рассмо­тренном выше примере размер ДПФ не обязательно ограничивать величиной (N₁ + N₂ – 1). ДПФ можно выполнять по любому числу отсчетов L, удовлетворяющему условию L  N₁ + N₂ – 1. Если это условие удовлетворяется, то в отличие от вышеописан­ной методики последовательности x(n) и h(n) дополняются дру­гим числом нулевых отсчетов. В результате эквивалентная пе­риодическая последовательность y_p(n) имеет в конце пе­риодов (L – N₁ – N₂ + 1) нулей – эти отличия никак не искажают желаемого результата. Возможность произвольного выбора L существенна, поскольку практические алгоритмы вы­числения ДПФ при разных L имеют неодинаковую эффективность. Так, например, для некоторых алгоритмов необходимо, чтобы L равнялось степени 2. В этом случае в качестве L приходится вы­бирать число, равное степени 2 и не меньшее, чем (N₁ + N₂ – 1).