Свертка с использованием быстрого преобразования Хартли

Процедура свертки, представленная в табл. 5.1, может быть реализована на базе быстрого алгоритма с использованием программы приведенной в приложении 1. Основная программа предполагает, что та или иная из заданных функций обладает свойством симметрии, так как в этом широкораспространенном случае скорость выполнения программы очень высока. Однако в отсутствие симметрии осуществляется обращение к подпрограмме 4400, а не 4000, просто реализующей перемножение двух вещественных ДПХ. Использование быстрого алгоритма предполагает ограничение числа элементов каждой последовательности, которое должно быть кратным 2, что является известным ограничением, причем не очень жестким по своему характеру. Большее значение имеет тот факт, что для последовательностей данных, над которыми выполняется

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

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

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

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