New Algorithms for Digital Convolution

Abstract

It is shown how the Chinese Remainder Theorem (CRT) can be used to convert a one-dimensional cyclic convolution to a multidimensional convolution which is cyclic in all dimensions. Then, special algorithms are developed which compute the relatively short convolutions in each of the dimensions. The original suggestion for this procedure was made in order to extend the lengths of the convolutions which one can compute with number-theoretic transforms. However, it is shown that the method can be more efficient, for some data sequence lengths, than the fast Fourier transform (FFT) algorithm. Some of the short convolutions are computed by methods in an earlier paper by Agarwal and Burrus. Recent work of Winograd, consisting of theorems giving the minimum possible numbers of multiplications and methods for achieving them, are applied to these short convolutions. Copyright © 1977 by The Institute of Electrical and Electronics Engineers, Inc.