6.8. Приложение. сравнение линейной и круговой свертки

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

На рис. 6.12 показаны две последовательности  и , которые мы хотим подвергнуть свертке. Для выполнения линейной свертки последовательность  сдвигается во времени назад относительно исходной (рис. 6.13, б), затем последовательно сдвигается вправо для получения свернутого выходного сигнала (рис. 6.13, в). При каждом сдвиге значения выборок  и  перемножаются в каждой точке, и эти четыре произведения складываются для получения выборки выходного сигнала.

а.

б.

Рис. 6.12. Последовательности, подлежащие свертке.

Рис. 6.13. Сравнение линейной и круговой сверток.

На рис. 6.13, г и д  показана круговая свертка, полученная с помощью - мерного БПФ (в данном примере длина блока  установлена равной 8). Сначала  выборок сдвигаются во времени назад на число периодов, кратное , чтобы получить значение  в точках (, кратных ),  как показано на рис. 6.13, г. Затем эти  выборок  последовательно  вращаются для получения   выборок выходного сигнала, показанных на рис. 6.13, д. Круговая свертка отличается от линейной из-за оборачивания  . Однако некоторые выходные выборки оказываются одинаковыми. Это имеет место только потому, что последние  выборок последовательности  были нулями: если бы последовательность  выбиралась произвольно, то две свертки различались бы во всех выходных выборках, кроме одной. При произвольной последовательности  каждый выходной сигнал круговой свертки является взвешенной суммой всех  выборок последовательности .

Метод уменьшения перекрытия – один из способов применения БПФ для выполнения линейной свертки длинной последовательности данных  и относительно короткой последовательности . Если длина короткой последовательности  равна , то размерность БПФ  должна быть больше ; Тогда последовательность дополняется достаточным количеством нулей, чтобы ее длина стала равной . Последовательность  разбивается на отрезки длиной , причем каждый из них перекрывает смежный отрезок на  выборок. Причина перекрытия станет очевидной позже. Сначала вычисляется БПФ одного из этих отрезков, и результат умножается на БПФ, выполненное для . Обратное БПФ произведения будет круговой сверткой длиной  выборок. Последние  выборки  круговой свертки идентичны результатам, которые мы могли бы получить при выполнении линейной свертки. Мы оставляем эти выборки и отбрасываем остальные. Поскольку мы получили   выборок выходного сигнала, необходимо сдвинуть последовательность на эту величину, прежде чем приступить к вычислению следующего блока выходных сигналов.  Это приводит к перекрытию смежных отрезков на  выборку. Обычный оптимальный случай – это , что приводит к 50% - ному перекрытию выборок во временной области. Альтернативный метод – добавочное перекрытие, когда между следующими друг за другом текущими выборочными данными добавляются неверные произведения для того, чтобы получить точные выборки выходного сигнала [58].