Number theoretic transforms to implement fast digital convolution

Abstract

Transforms using number theoretic concepts are developed as a method for fast and error-free calculation of finite digital convolution. The transforms are defined on finite fields and rings of integers with arithmetic carried out modulo an integer and it is shown that under certain conditions this gives the same results as conventional digital convolution. Because of these characteristics they are ideally suited to digital computation by taking into account quantization of amplitude as well as time in their definition. When the modulus is chosen as a Fermat number a transform results that requires only on the order of N log N additions and word shifts but no multiplications. In addition to being efficient, they have no roundoff error and do not require storage of basis functions. There is a restriction on sequence length imposed by word length and a problem with overflow but methods for overcoming these are presented. Results of an implementation on an IBM 370/155 are presented and compared with the fast Fourier transform showing a substantial improvement in efficiency and accuracy. Variations on the basic number theoretic transforms are also presented.