A Novel Accelerating Algorithm and Its Implement in Real Sequence FFT

Author(s): Honggui Deng, Sheng-wei Guo, Jian Duan

We propose an improved FFT algorithm, which costs only a half of the calculation time compared with the conventional FFT if the input data are real numbers. The algorithm is optimized by dividing 2N data points into 2 separated groups through parity. The odd part and even part of the 2N data points are used as the real part and imaginary part of a new complex data sequence with N data points. After FFT of this new data sequence, the FFT of the original 2N data points can be calculated through formulations. From our experiment based on FPGA, this new implementation is more effective than conventional FFT by saving half of calculation time.

FFT, real sequence, FPGA

1. S Sukhsawas, K Benkrid. A High-level Implementation of a High Performance Pipeline FFT on Virtex-E FPGAs IEEE Computer Society Annual Symposium on VLSI, p 229-230, 2004
2. Kumhom P. Johnson J.R. Nagvajara P. Design, Optimization, and Implementation of a Universal FFT Processor. Proceedings of 13th Annual IEEE International ASIC/SOC Conference (Cat. No.00TH8541), p 182-187, 2000
3. Chen he, Zhao zhong-wu. ASIC design of floating-point FFT pro-cessor[J] Journal of University of Beijing for Science & Technology:English Version 2004,13(4): 389-393.
4. [4] LU Jianfeng. Real time Fourier Transform syetem design based on double DSP[J] Photoelectric engineering, 2005,32(11): 93-96
5. Radhouane, R. Liu, P.; Modlin, C. Minimizing the memory requirement for continuous flow FFT implementation: continuous flow mixed mode FFT (CFMM-FFT) 2000 IEEE International Symposium on Circuits and Systems. Emerging Technologies for the 21st Century. Proceedings (IEEE Cat No.00CH36353), p 116-134 vol.1, 2000
6. GAN Liang-cai, DING Ya-hu. CPLD implementation of 1024-point FFT of short-wave wideband channel simulator[J].Electricity Journal:English version, 2006,15(4): 692-696.
7. Cepisca, C., Grigorescu, S.D., Covrig, M.,Andrei, H.. About the Efficiency of Real Time Sequences FFT Computing. Proceedings of the 2007 IEEE Workshop on Design and Diagnostics of Electronic Circuits and Systems, DDECS, p 211-214, 2007
8. M. Rawshi, M.Wojtyski. Distributed arithmetic based implementation of Fourier transform targeted at FPGA architectures[C]. Proceedings of the 14th International Conference "Mixed Design of Integrated Circuits and Systems", MIXDES 2007, p 152-156, 2007
9. LIU Guodong,CHEN Boxiao,CHEN Duofang. FPGA design of FFT processor[J]. Aviation calculation technology, 2004,34(3): 101-104
10. KUO JC,WEN CH,WUAY. Implementation ofa programmable 64-2048-pointFFT/IFFT processor forOFDM based communication sys-tems[C]. Proceeding of IEEE International Symposium on Circuits and Systems. 2003: 121-124
11. Wang, Yuke;Tang, Yiyan Jiang; Yingtao; Chung, Jin-Gyun; Song, Sang-Seob; Lim, Myoung-Seob. Novel memory reference reduction methods for FFT implementations on DSP processors. IEEE Transactions on Signal Processing, 2007, 55(5):2338-2349