Number theoretic transforms to implement fast digital convolution
- 1 April 1975
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Proceedings of the IEEE
- Vol. 63 (4) , 550-560
- https://doi.org/10.1109/proc.1975.9791
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.Keywords
This publication has 13 references indexed in Scilit:
- Fast Convolution using fermat number transforms with applications to digital filteringIEEE Transactions on Acoustics, Speech, and Signal Processing, 1974
- A note on exact discrete Fourier transformsIEEE Transactions on Audio and Electroacoustics, 1973
- Discrete Convolutions via Mersenne TransformsIEEE Transactions on Computers, 1972
- Block realization of digital filtersIEEE Transactions on Audio and Electroacoustics, 1972
- Effects of finite register length in digital filtering and the fast Fourier transformProceedings of the IEEE, 1972
- Algebraic theory of finite fourier transformsJournal of Computer and System Sciences, 1971
- The Fast Fourier Transform in a Finite FieldMathematics of Computation, 1971
- The Relationship Between Two Fast Fourier TransformsIEEE Transactions on Computers, 1971
- High-speed convolution and correlationPublished by Association for Computing Machinery (ACM) ,1966
- An algorithm for the machine calculation of complex Fourier seriesMathematics of Computation, 1965