Proceedings of International Conference on Applied Innovation in IT
2014/03/27, Volume 2, Issue 1, pp.11-20
Efficiency Comparison of DFT/IDFT Algorithms by Evaluating Diverse Hardware Implementations, Parallelization Prospects and Possible Improvements
Danijela Efnusheva, Natasha Tagasovska, Aristotel Tentov, Marija Kalendar
Abstract: In this paper we investigate various algorithms for performing Fast Fourier Transformation (FFT)/Inverse Fast Fourier Transformation (IFFT), and proper techniques for maximizing the FFT/IFFT execution speed, such as pipelining or parallel processing, and use of memory structures with pre-computed values (look up tables - LUT) or other dedicated hardware components (usually multipliers). Furthermore, we discuss the optimal hardware architectures that best apply to various FFT/IFFT algorithms, along with their abilities to exploit parallel processing with minimal data dependences of the FFT/IFFT calculations. An interesting approach that is also considered in this paper is the application of the integrated processing-in-memory Intelligent RAM (IRAM) chip to high speed FFT/IFFT computing. The results of the assessment study emphasize that the execution speed of the FFT/IFFT algorithms is tightly connected to the capabilities of the FFT/IFFT hardware to support the provided parallelism of the given algorithm. Therefore, we suggest that the basic Discrete Fourier Transform (DFT)/Inverse Discrete Fourier Transform (IDFT) can also provide high performances, by utilizing a specialized FFT/IFFT hardware architecture that can exploit the provided parallelism of the DFT/IDF operations. The proposed improvements include simplified multiplications over symbols given in polar coordinate system, using sinе and cosine look up tables, and an approach for performing parallel addition of N input symbols.
Keywords: Cooley-Tukey, DFT/IDFT, FFT/IFFT, Intelligent RAM, look up tables, OFDM, pipeline and parallel processing, polar coordinate system
- S. W. Smith, “The Scientist and Engineer's Guide to Digital Signal Processing,”. California: California technical publishing, 1997.
- K. Adzha and B. Kadiran, “Design and implementation of OFDM transmitter and receiver on FPGA hardware,” M.S. thesis, Faculty of electrical engineering, Universiti teknologi Malaysia, Malaysia, 2005.
- M. Bernhard and J. Speidel, “Implementation of an IFFT for an optical OFDM transmitter with 12.1 Gbit/s,” ITG Symposium on Photonic Networks, Germany, 2010.
- F. Buchali, R. Dischler, A. Klekamp, M. Bernhard, and D. Efinger, “Realisation of a real-time 12.1 Gb/s optical OFDM transmitter and its application in a 109 Gb/s transmission system with coherent reception,”, 35th European Conference on Optical Communication, Germany, 2009.
- R. Schmogrow and M. Winter, et al, “101.5 Gbit/s real-time OFDM transmitter with 16QAM modulated subcarriers,” OSA/OFC/NFOEC 2011, vol. A247, pp. 529-551, April 1955.
- C. Toal and S. Sezer, et al, “A 1Gbps FPGA-based wireless baseband MIMO transceiver,” IEEE International SOC Conference (SOCC'12), pp. 202-207, September 2012.
- K. Maharatna, E. Grass, and U. Jagdhold, “A 64-point Fourier transform chip for high-speed wireless LAN application using OFDM,” IEEE Journal of Solid-State Circuits, vol. 39, March 2004.
- K. Maharatna, E. Grass, and U. Jagdhold, “A Low-power 64-point FFT/IFFT architecture for wireless broadband communication,” in Proc. 7th Int’l Conf. on Mobile Multimedia Communication (MoMuC), Tokyo, Japan, 2000.
- C. Lin, Y. Yu, and L. Van, “A Low-power 64-point FFT/IFFT design for IEEE 802.11a WLAN application,” IEEE International Symposium on Circuits and Systems, Greece, 2006.
- M. Bhardwaj, A. Gangwar, and D. Soni, “A review on OFDM: concept, scope & its applications,” IOSR Journal of Mechanical and Civil Engineering, Volume 1, Issue 1, pp. 07-11, 2012.
- L. Lit win and M. Pugel, “The principles of OFDM,” RF Signal Processing Journal, pp 30-48, 2001.
- T. Fung, “FPGA design and implementation of a memory based mixed-radix 4/2 FFT processor,” M.S. thesis, Dept. of Electrical Eng., Tatung University, Tatung, July 2008.
- R. E. Blahut, “Fast Algorithms for Signal Processing,” United Kingdom: Cambridge University Press, 2010.
- J. J. Fúster and K. S. Gugel, “Pipelined 64-point fast Fourier transform for programmable logic devices,” in Proc. International conference on advances in recent technologies in communication and computing, India, 2010.
- J. García1, J. A. Michell, G. Ruiz, and A.l M. Burón, “FPGA realization of a split radix FFT processor,” in Proc. SPIE, Microtechnologies for the New Millennium, vol. 6590, pp. 1-11, 2007.
- D. Ghosh, D. Debnath, and A. Chakrabarti, “FPGA based implementation of FFT processor using different architectures,”International Journal of Advance Innovations, Thoughts & Ideas, 2012.
- M. Chandan, S. L. Pinjare, and C. Mohan Umapthy, “Optimised FFT design using constant co-efficient multiplier,” International Journal of Emerging Technology and Advanced Engineering, 2012.
- R. Thomas, “An architectural performance study of the fast Fourier transform on vector IRAM,” Berkeley University, California, Tech. Rep, 2000.
- Y. Ouerhani, M. Jridi, and A. Alfalou, "Implementation techniques of high-order FFT into low-cost FPGA", in Proc. IEEE 54th International Midwest Symposium on Circuits and Systems, Korea, 2011.
- P. Duhamel and M. Vetterli, “Fast Fourier transforms: a tutorial review and a state of the art,” Signal Processing Journal, vol. 19, 1990.
- S. Meiyappan, “Implementation and performance evaluation of parallel FFT algorithms,” School of Computing. National University of Singapore, Singapore.
- S. K. Palaniappan, “Design and implementation of radix-4 fast Fourier transform in ASIC chip with 0.18 μm standard CMOS technology,” M.S. thesis, Malaysia, 2008.
- M. Soni and P. Kunthe, “A General comparison of FFT algorithms,”Pioneer Journal Of IT & Management, 2011.
- B. Gough, “FFT algorithms,” Tutorial paper, 1997
- K. M. Pavan Kumar and P. Jain, et al, “FFT algorithms: a survey,”The International Journal Of Engineering And Science, India, 2013.
- S. Winograd, “On computing the discrete Fourier transform,”Proceedings of the National Academy of Sciences of the United States of America, 1975.
- F. Piccinin, “The fast Hartley transform as an alternative to the fast Fourier transform,” Australia, Technical Memorandum, SRL-0006-TM, 1988.
- R. Vincke and S. V. Landschoot, et al., “Calculating fast Fourier transform by using parallel software design patterns,” Tech. Report, CW 627, October 2012.
- A. Cortés, I. Vélez, M. Turrillas, and J. F. Sevillano, “Fast Fourier transform processors: implementing FFT and IFFT cores for OFDM communication systems,” Fourier Transform - Signal Processing, 2012.
- M. Frigo and S. G. Johnson, “The fastest Fourier transform in the west,” Tech. Report, MIT-LCS-TR-728, 1997.
- Bevan M. Baas, “An approach to low-power, high-performance, fast Fourier transform processor design,” PhD Thesis, Stanford University, USA, 1999.
- Y. Zhao and T. Ahmet, et al., “Architectural evaluation of flexible digital signal processing for wireless receivers,” Signals, Systems and Computers, 2000.
- A. Ganapathiraju, J. Hamaker, J. Picone, and A. Skjellum, “Contemporary view of FFT algorithms,” Mississippi State University.
- J. F. Herron, “Design and development of a high-speed Winograd fast Fourier transform processor board,” M.S. thesis, Air University, USA, 1992.
- C. Li, “Design and implementation of variable-length fast Fourier transform processor,” M.S. thesis, Tatung University, 2006.
- C. Kozyrakis and D. Patterson, “Vector vs. superscalar and VLIW architectures for embedded multimedia benchmarks,” In proc. of the 35th International Symposium on Microarchitecture, Instabul, Turkey, November 2002.
- T. Lippert, K. Schilling, et al., “Transpose algorithm for FFT on APE/Quadrics,” In Proc. of HPCN Europe, pp. 439-448, 1998.
- H.G. Yeh and G. Truong, “Speed and area analysis of memory based FFT processors in a FPGA,” Wireless Telecommunications Symposium, pp. 1-6, 2007.
- E. Brachos, “Parallel FFT libraries,” M.S. thesis, Edinburgh University, 2011.
- S. Johnsson and D. Cohen, “Computational arrays for the discrete Fourier transform,” In Proc. 22nd Computer Society International Conference, 1981.
- C.A. Silambarasan and L. Vanitha, “Design and implementation of low power and area efficient adder and Vedic multiplier for FFT,” International Journal of Communications and Engineering, Vol. 1, 2012.
- S. S. Kerur and Prakash Narchi, et al., “Implementation of Vedic multiplier for digital signal processing,” International Journal of Computer Applications, 2011.
- S. A. White, “Applications of distributed arithmetic to digital signal processing: a tutorial review,” IEEE ASSP Magazine, 1989.
- T. Sung, H. Hsin, and L. Ko, “Reconfigurable VLSI architecture for FFT processor,” WSEAS Transactions on Circuits and Systems, 2009.