A two-dimensional discrete convolution algorithm

A theoretical result concerning the discrete Fourier transform is derived and used to develop a transform algorithm for computing two-dimensional convolutions. The use of this algorithm minimises the number of arithmetic operations and the memory requirements in computing a convolution of order (M¿¿N) using a transform processor or program designed for a length No, where M¿¿N0 and N¿¿N0.It is particularly suitable for computing convolutions whose orders are not powers of two using conventional fast Fourier transform processors. Methods of implementing the algorithm are also presented.