Title :
A new approach for computing the discrete Fourier transform of arbitrary length
Author :
Xianchao, Zhang ; Liusheng, Huang ; Guoliang, Chen
Author_Institution :
Nat. High Performance Comput. Center, Hefei, China
Abstract :
A new approach for computing DFT of arbitrary length is proposed, which is based on the arithmetic Fourier transform (AFT). The algorithm needs only 𝒪(N) multiplications and has a simple computational structure, so it can be easily performed in parallel and it is very suitable for VLSI design. The algorithm is faster than the classical FFT when the length of the DFT contains relatively large factors. It is especially efficient for computing the DFT of prime length, where FFT does not work. The algorithm is competitive with the FFT in term of accuracy. A method to enhance the accuracy of the algorithm is also proposed for cases when higher accuracy is required
Keywords :
computational complexity; discrete Fourier transforms; parallel algorithms; signal processing; DFT length; DSP; FFT; VLSI design; algorithm accuracy; arithmetic Fourier transform; computational complexity; digital signal processing; discrete Fourier transform; multiplications; parallel computational structure; prime length DFT; Algorithm design and analysis; Arithmetic; Concurrent computing; Discrete Fourier transforms; Discrete transforms; Electrostatic precipitators; Fourier transforms; High performance computing; Signal processing algorithms; Very large scale integration;
Conference_Titel :
Signal Processing Proceedings, 2000. WCCC-ICSP 2000. 5th International Conference on
Conference_Location :
Beijing
Print_ISBN :
0-7803-5747-7
DOI :
10.1109/ICOSP.2000.894449
