Дополнение нулями

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

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

Однако если осуществляется циклическая свертка двух 4-элементных последовательностей, то в результате также получим последовательность из 4 элементов

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

Поэтому для получения выходной последовательности треугольной

формы дополним заданные последовательности нулями и получим

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

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

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

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

Вышеприведенный пример может быть решен вручную; аналоговое вычислительное устройство, облегчающее выполнение свертки, имеет два концентрических наборных диска, каждый из которых состоит из N сегментов, в которые могут быть записаны две последовательности, вращающиеся относительно друг друга в противоположных направлениях, что обусловлено знаком «минус» в одном из сомножителей в сумме, определяющей процедуру свертки. Для вычисления каждого члена свертки следует повернуть ротор на угол, равный длине дуги одного сегмента, и затем определить сумму произведений, составленных для соседних сегментов (рис. 5.2). Вращающиеся механизмы, использующие этот принцип, были сконструированы во времена применения электромеханических аналоговых вычислительных устройств.