Циклическая свертка

Обычная дискретная свертка двух последовательностей определяется следующим соотношением:

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

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

Рис. 5.1. Последовательности и их циклическая свертка

каждого из N значений свертки. Циклическая свертка определяется выражением

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

В качестве примера циклической свертки рассмотрим рис. 5.1, где представлен случай, для которого

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

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

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

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

Значительная часть последующего материала посвящена именно циклической свертке, и едва ли есть необходимость введения специального символа для этой операции. Напомним, что в данной главе будет использоваться символ . Таким образом,