DocumentCode :
933868
Title :
Number theoretic transforms to implement fast digital convolution
Author :
Agarwal, Ramesh C. ; Burrus, C. Sidney
Author_Institution :
IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y.
Volume :
63
Issue :
4
fYear :
1975
fDate :
4/1/1975 12:00:00 AM
Firstpage :
550
Lastpage :
560
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 :
Convolution; Digital arithmetic; Digital filters; Discrete Fourier transforms; Discrete transforms; Fast Fourier transforms; Fourier transforms; Galois fields; Polynomials; Quantization;
fLanguage :
English
Journal_Title :
Proceedings of the IEEE
Publisher :
ieee
ISSN :
0018-9219
Type :
jour
DOI :
10.1109/PROC.1975.9791
Filename :
1451721
Link To Document :
بازگشت