New Approach to the Computations of Large One Dimensional Discrete Fourier Transforms
Original Publication Date: 1980-Jul-01
Included in the Prior Art Database: 2005-Feb-13
In this paper, we introduce a new method for computing one-dimensional Discrete Fourier Transforms (DFTs). This method evaluates DFTs of dimension N(1)N(2), where N(1) is a power of 2 and N(2) is a prime Fermat number. With this approach, the transforms of dimension N(2) are calculated by polynomial transforms and the DFTs of dimension N(1) are computed by a Fast Fourier Transform (FFT) technique. The new approach reduces significantly the number of arithmetic for large transform lengths. We consider a DFT of dimension N(1)xN(2), with N(1)=2/t/1 and N(2)=2/t2/+1, with t(2)=2/v/, and v restricted to 1, 2, 3, 4, Thus, N(2) is a prime Fermat number, and the DFT X(k(1),k(2)) is defined by: (see original).