Proceedings of International Conference on Applied Innovation in IT
2014/03/27, Volume 1, Issue 2, 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

DOI: 10.13142/kt10002.03

Download: PDF

References:

  1. S. W. Smith, “The Scientist and Engineer's Guide to Digital Signal Processing,”. California: California technical publishing, 1997.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. L. Lit win and M. Pugel, “The principles of OFDM,” RF Signal Processing Journal, pp 30-48, 2001.
  12. 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.
  13. R. E. Blahut, “Fast Algorithms for Signal Processing,” United Kingdom: Cambridge University Press, 2010.
  14. 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.
  15. 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.
  16. D. Ghosh, D. Debnath, and A. Chakrabarti, “FPGA based implementation of FFT processor using different architectures,”International Journal of Advance Innovations, Thoughts & Ideas, 2012.
  17. 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.
  18. R. Thomas, “An architectural performance study of the fast Fourier transform on vector IRAM,” Berkeley University, California, Tech. Rep, 2000.
  19. 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.
  20. P. Duhamel and M. Vetterli, “Fast Fourier transforms: a tutorial review and a state of the art,” Signal Processing Journal, vol. 19, 1990.
  21. S. Meiyappan, “Implementation and performance evaluation of parallel FFT algorithms,” School of Computing. National University of Singapore, Singapore.
  22. 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.
  23. M. Soni and P. Kunthe, “A General comparison of FFT algorithms,”Pioneer Journal Of IT & Management, 2011.
  24. B. Gough, “FFT algorithms,” Tutorial paper, 1997
  25. K. M. Pavan Kumar and P. Jain, et al, “FFT algorithms: a survey,”The International Journal Of Engineering And Science, India, 2013.
  26. S. Winograd, “On computing the discrete Fourier transform,”Proceedings of the National Academy of Sciences of the United States of America, 1975.
  27. F. Piccinin, “The fast Hartley transform as an alternative to the fast Fourier transform,” Australia, Technical Memorandum, SRL-0006-TM, 1988.
  28. R. Vincke and S. V. Landschoot, et al., “Calculating fast Fourier transform by using parallel software design patterns,” Tech. Report, CW 627, October 2012.
  29. 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.
  30. M. Frigo and S. G. Johnson, “The fastest Fourier transform in the west,” Tech. Report, MIT-LCS-TR-728, 1997.
  31. Bevan M. Baas, “An approach to low-power, high-performance, fast Fourier transform processor design,” PhD Thesis, Stanford University, USA, 1999.
  32. Y. Zhao and T. Ahmet, et al., “Architectural evaluation of flexible digital signal processing for wireless receivers,” Signals, Systems and Computers, 2000.
  33. A. Ganapathiraju, J. Hamaker, J. Picone, and A. Skjellum, “Contemporary view of FFT algorithms,” Mississippi State University.
  34. J. F. Herron, “Design and development of a high-speed Winograd fast Fourier transform processor board,” M.S. thesis, Air University, USA, 1992.
  35. C. Li, “Design and implementation of variable-length fast Fourier transform processor,” M.S. thesis, Tatung University, 2006.
  36. 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.
  37. T. Lippert, K. Schilling, et al., “Transpose algorithm for FFT on APE/Quadrics,” In Proc. of HPCN Europe, pp. 439-448, 1998.
  38. 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.
  39. E. Brachos, “Parallel FFT libraries,” M.S. thesis, Edinburgh University, 2011.
  40. S. Johnsson and D. Cohen, “Computational arrays for the discrete Fourier transform,” In Proc. 22nd Computer Society International Conference, 1981.
  41. 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.
  42. S. S. Kerur and Prakash Narchi, et al., “Implementation of Vedic multiplier for digital signal processing,” International Journal of Computer Applications, 2011.
  43. S. A. White, “Applications of distributed arithmetic to digital signal processing: a tutorial review,” IEEE ASSP Magazine, 1989.
  44. T. Sung, H. Hsin, and L. Ko, “Reconfigurable VLSI architecture for FFT processor,” WSEAS Transactions on Circuits and Systems, 2009.

    Home

    PARTICIPATION

       - Call for Papers!!!
       - Paper Submission
       - Important Dates
       - Committee
       - Guest registration


    PROCEEDINGS

       - Issue 1 (ICAIIT 2013)
       - Issue 2 (ICAIIT 2014)
       - Issue 3 (ICAIIT 2015)
       - Issue 4 (ICAIIT 2016)
       - Issue 5 (ICAIIT 2017)

    ETHICS IN PUBLICATIONS

    ACCOMODATION

    CONTACT US

 


           ISSN 2199-8876
           Copyright © 2013-2017 Leonid Mylnikov. All rights reserved.