A more Efficient Algorithm for Computing DFT of Primary Length
Xian Zhang · Journal of Yantai University · 2000
The discrete Fourier transform (DFT) plays an important role in digital signal processing, digital image processing and many other fields. The fast computing of DFTs of prime length is the basic and an important part of the fast computing of DFTs of any length. Traditional fast methods for computing DFTs of prime length show low efficiency. They also have many other disadvantages such as too complex programs, too many child proceedings, etc, which makes them difficult for using in practice. In this paper, we adopt a new technique for Fourier analysis called the arithmetic Fourier transform (AFT) for computing DFT. This method needs only O(N ) multiplications, when used for computing DFTs of prime length, this method shows much higher efficiency than the traditional methods. It has a very simple program and it can be easily performed in parrallel, which overcomes the difficulties of the traditional methods. Moreover, it gives a new idea and road for computing DFTs of any length.