1974/04/01 by Ramesh K. Agarwal, R. Agarwal, C. Burrus +1 · 3 citations
Computer Science · Mathematics · #Algorithm #Arithmetic #Computation #Computer science #Convolution (computer science) #Convolution theorem #Cyclotomic fast Fourier transform #Digital Filter Design and Implementation #Digital filter #Discrete Fourier transform (general) #Discrete mathematics #Fast Fourier transform #Fermat number #Fermat's Last Theorem #Filter (signal processing) #Fourier analysis #Fourier transform #Fractional Fourier transform #Mathematical Analysis and Transform Methods #Mathematical analysis #Mathematics #Numerical Methods and Algorithms #Overlap–add method #Rader's FFT algorithm
paper · doi:10.1109/tassp.1974.1162555
openalex publication_date 1974/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
The structure of transforms having the convolution property is developed. A particular transform is proposed that is defined on a finite ring of integers with arithmetic carried out modulo Fermat numbers. This Fermat number transform (FNT) is ideally suited to digital computation, requiring on the order ofN log Nadditions, subtractions and bit shifts, but no multiplications. In addition to being efficient, the Fermat number transform implementation of convolution is exact, i.e., there is no roundoff error. There is a restriction on sequence length imposed by word length but multi-dimensional techniques are discussed which overcome this limitation. Results of an implementation on the IBM 370/155 are presented and compared with the fast Fourier transform (FFT) showing a substantial improvement in efficiency and accuracy.