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

Операция свертки может быть выполнена в полном объеме без перестановки элементов ценой запоминания второго типа преобразования. Алгоритмы, рассмотренные в данной книге, предполагают использование перестановки с последующим замещением, однако существуют алгоритмы другого типа, в которых замещение элементов предшествует процедуре перестановки. Описание структур этих алгоритмов применительно к ДПФ приводится в статье: W. Т. Cochran et al. What is the Fast Fourier Transform? IEEE Trans. Audio and Electroacoustics, vol. AU-15, pp. 45-55, 1985 (Кохран. Что такое быстрое преобразование Фурье?).

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

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

долю всего времени счета, а эта доля уменьшается с ростом N. Однако могут иметь место частные случаи, когда имеет смысл не выполнять процедуру перестановки.