3.7. ЛИНЕЙНАЯ СВЕРТКА С ИСПОЛЬЗОВАНИЕМ ДИСКРЕТНОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ

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

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

будет линейной сверткой Конечно, линейная свертка была бы также получена, если бы дискретное преобразование Фурье вычислялось на основе более чем точек. Но в общем случае линейная свертка не получалась бы, если бы ДПФ вычислялось на основе меньшего числа точек. Как другую интерпретацию этой процедуры вычисления линейной свертки, мы отметим, что вычисление ДПФ на основе точек соответствует ряду Фурье периодической последовательности, составленной из так, что последние точек каждого периода равны нулю. Эти периодические последовательности показаны на рис. 3.13. Этот рисунок также иллюстрирует процесс

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

Рис. 3.13. Периодические последовательности периода полученные из -точечных последовательностей конечной длины (последние точек каждого периода равны нулю]

В общем случае нам может понадобиться свертка двух последовательностей неравной длины. Если имеет длительность — длительность то их свертка будет иметь длину Поэтому следует умножать дискретные преобразования Фурье, вычисленные на основе точек.

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

Чтобы проиллюстрировать эту процедуру и разработать процедуру подгонки отфильтрованных секций друг к другу, рассмотрим импульсную характеристику длины М и сигнал изображенные на рис. 3.14. Представим как сумму отдельных секций, причем каждая секция имеет только ненулевых точек. Пусть секция

Тогда равна сумме т. е.

и свертка равна сумме сверток т. е.

Так имеет только ненулевых значений и имеет длину М, каждый из членов суммы имеет длительность Поэтому линейная свертка должна быть получена с использованием -точечного ДПФ.

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

Так как начало каждой секции отделено от соседней на точек и каждая отфильтрованная секция имеет длину ненулевые значения отфильтрованных секций будут перекрываться в точках при суммировании по (3.44). Это иллюстрируется на рис. 3.15. На рис. 3.15 а изображены входные секции а на рис 3.156 по казаны отфильтрованные секции Входное колебание восстанавливается путем сложения колебаний на рис. 3.15 а, а результат фильтрации получается сложением отфильтрованных секций, изображенных на рис. 3.15б. Эта процедура получения отфильтрованного выходного сигнала по отфильтрованным секциям часто называется методом перекрытия с суммированием в соответствии с тем, что выход получается путем сложения перекрывающихся отфильтрованных секций. Перекрытие вытекает из того, что линейная свертка каждой секции с импульсной характеристикой в общем случае длиннее, чем длина секции.

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

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

—1, где мы определяем точку начала отсчета времени для каждой секции в начале этой секции, а не в начале последовательности

Рис. 3.15. Разложение на неперекрывающиеся секции длины и результат свертки каждой секции с

Этот метод секционирования изображен на рис. 3.16а. Круговая свертка каждой секции с обозначается Эти последовательности изображены на рис. 3.16б. Часть каждой выходной секции в промежутке должна быть отброшена. Отфильтрованная последовательность получается

Рис. 3.16. Разложение на перекрывающиеся секции длины и результат круговой свертки каждой секции с (Указаны части каждой отфильтрованной секции, которые нужно отбросить при формировании линейной свертки)

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

Эта процедура — метод перекрытия с накоплением — получила свое название потому, что каждая последующая входная секция состоит из новых точек и точек из предыдущей секции.