An Algorithm for Computing DFT Using Arithmetic Fourier Transform
Xian Zhang · Dianzi xuebao · 2000
The Discrete Fourier Transform (DFT) plays an important role in digital signal processing and many other fields.In this paper,a new Fourier analysis technique called the arithmetic Fourier transform (AFT) is used to compute DFT.This algorithm needs only O(N) multiplications.The process of the algorithm is simple and it has a unified formula,which overcomes the disadvantage of the traditional fast method that has a complex program containing too many subroutines.The algorithm can be easily performed in parallel,especially suitable for VLSI designing.For a DFT at a length that contains big prime factors,especially for a DFT at a prime length,it is faster than the traditional FFT method.The algorithm opens up a new approach for the fast computation of DFT.