Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Radix-43 based two-dimensional FFT architecture with efficient data reordering scheme

  • Author(s): Kala S. 1 ; Jimson Mathew 2 ; Babita R. Jose 1 ; Nalesh S. 3
    • View affiliations
  • Source: Volume 13, Issue 2, March 2019, p. 78 – 86
    DOI:  10.1049/iet-cdt.2018.5075 , Print ISSN 1751-8601, Online ISSN 1751-861X
© The Institution of Engineering and Technology
Received 29/05/2018, Accepted 21/09/2018, Revised 25/08/2018, Published 03/10/2018

Multi-dimensional Discrete Fourier Transforms (DFTs) play an important role in signal and image processing applications. Image reconstruction is a key component in signal processing applications like medical imaging, computer vision, face recognition etc. Two dimensional fast Fourier Transform (2D FFT) and Inverse FFT plays vital role in reconstruction. In this paper we present a fast 64 × 64 point 2D FFT architecture based on radix-43 algorithm using a parallel unrolled radix-43 FFT as the basic block. Our radix-43 architecture is a memory optimized parallel architecture which computes 64-point FFT, with least execution time. Proposed architecture produces reordered output of both 64-point one dimensional (1D) FFT and 64 × 64 point 2D FFT, without using any additional hardware for reordering. The proposed architecture has been implemented in UMC 40nm CMOS technology with clock frequency of 500 MHz and area of 0.841 mm2. The power consumption of proposed architecture is 358 mW at 500 MHz. Energy efficiency (FFTs computed per unit of energy) is 341 points/Joule. Computation time of 64 × 64 point FFT is 8.19 μs. ASIC implementation results shows better performance of proposed work in terms of computation time when compared with state-of-art implementation. Proposed architecture has also been implemented in Virtex-7 FPGA which gives comparable area.

Inspec keywords: discrete Fourier transforms; CMOS logic circuits; fast Fourier transforms; computational complexity; parallel architectures; application specific integrated circuits; field programmable gate arrays

Other keywords: application specific integrated circuit; 2D FFT architecture; frequency 500.0 MHz; multidimensional DFT; two-dimensional fast Fourier transform; time 8.19 mus; power consumption; face recognition; radix-43 algorithm; row–column decomposition; image reconstruction; FFT computation; signal processing applications; two-dimensional FFT architecture; data reordering; discrete Fourier transforms; size 0.841 mm; UMC complementary metal oxide semiconductor; medical imaging; size 40.0 nm; power 358.0 mW; computer vision; parallel unrolled radix-4; memory optimised parallel architecture; Virtex 7 field programmable gate array; signal processing systems

Subjects: Integral transforms in numerical analysis; Logic circuits; Logic and switching circuits; Integral transforms in numerical analysis; Mixed analogue-digital circuits; CMOS integrated circuits; Parallel architecture

References

    1. 1)
      • 43. Shirazi, N., Athanas, P.M., Abbott, A.L.: ‘Implementation of a 2-d fast Fourier transform on an FPGA-based custom computing machine’. 5th Int. Workshop Field Programmable Logic and Applications, Oxford, UK, 1995, pp. 282–292.
    2. 2)
      • 7. Akin, B., Milder, P.A., Franchetti, F., et al: ‘Memory bandwidth efficient two-dimensional fast Fourier transform algorithm and implementation for large problem sizes’. 2012 IEEE 20th Int. Symp. on Field-Programmable Custom Computing Machines, Toronto, ON, Canada, 2012, pp. 188–191. doi: 10.1109/FCCM.2012.40.
    3. 3)
      • 22. Xia, K., Wu, B., Zhou, X., et al: ‘A generalized conflict-free address scheme for arbitrary 2k-point memory-based FFT processors’. 2016 IEEE Int. Symp. On Circuits and Systems (ISCAS), Montreal, QC, Canada, 2016, pp. 2126–2129.
    4. 4)
      • 17. Cohen, D.: ‘Simplified control of FFT hardware’, IEEE Trans. Acoust. Speech Signal Process., 1976, 24, (6), pp. 577–579, 10.1109/TASSP.1976.1162854.
    5. 5)
      • 14. Cho, T., Lee, H., Park, J., et al: ‘A high-speed low-complexity modified radix-25 FFT processor for gigabit WPAN applications’. 2011 IEEE Int. Symp. on Circuits and Systems (ISCAS), Rio de Janeiro, Brazil, 2011, pp. 1259–1262. doi: 10.1109/ISCAS.2011.5937799.
    6. 6)
      • 24. Huang, S.J., Chen, S.G.: ‘A high-parallelism memory-based FFT processor with high SQNR and novel addressing scheme’. 2016 IEEE Int. Symp. on Circuits and Systems (ISCAS), Montreal, QC, Canada, 2016, pp. 2671–2674, doi: 10.1109/ISCAS.2016.7539143.
    7. 7)
      • 20. Reisis, D., Vlassopoulos, N.: ‘Conflict-free parallel memory accessing techniques for FFT architectures’, IEEE Trans. Circuits Syst. I, Regul. Pap., 2008, 55, (11), pp. 3438–3447, 10.1109/TCSI.2008.924889.
    8. 8)
      • 1. Proakis, J.G., Manolakis, D.G.: ‘Digital signal processing: principles, algorithms, and applications’ (Prentice-Hall, Inc., New Jersey, 1996, 3rd edn.).
    9. 9)
      • 25. Dillon, T.: ‘Two virtex-II FPGAs deliver fastest, cheapest, best high-performance image processing system’, Xilinx Xcell J., 2001, 41, pp. 70–71.
    10. 10)
      • 36. Kala, S., Nalesh, S., Nandy, S.K., et al: ‘Design of a low power 64 point FFT architecture for WLAN applications’. 2013 25th Int. Conf. on Microelectronics (ICM), Beirut, Lebanon, 2013, pp. 1–4. doi: 10.1109/ICM.2013.6734951.
    11. 11)
      • 19. Tsai, P.Y., Lin, C.Y.: ‘A generalized conflict-free memory addressing scheme for continuous-flow parallel-processing FFT processors with rescheduling’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2011, 19, (12), pp. 2290–2302, 10.1109/TVLSI.2010.2077314.
    12. 12)
      • 21. Ma, Z.G., Yin, X.B., Yu, F.: ‘A novel memory-based FFT architecture for real-valued signals based on a radix-2 decimation-in-frequency algorithm’, IEEE Trans. Circuits Syst. II, Express Briefs, 2015, 62, (9), pp. 876–880, 10.1109/TCSII.2015.2435522.
    13. 13)
      • 8. Kee, H., Bhattacharyya, S.S., Petersen, N., et al: ‘Resource-efficient acceleration of 2-dimensional fast Fourier transform computations on FPGAs’. Int. Conf. on Distributed Smart Cameras, Como, Italy, 2009, pp. 1–4.
    14. 14)
      • 44. Kim, Y.J., Lee, H.S.: ‘The implementation of 2D FFT using multiple topology on 4 × 4 torus’. 2009 9th Int. Symp. on Communications and Information Technology, Icheon, Republic of Korea, 2009, pp. 615–620. doi: 10.1109/ISCIT.2009.5341171.
    15. 15)
      • 9. Babionitakis, K., Chouliaras, V., Manolopoulos, K., et al: ‘Fully systolic FFT architecture for Giga-sample applications’, J. Signal Process. Syst., 2010, 58, pp. 281–299.
    16. 16)
      • 4. Frigo, M., Johnson, S.G.: ‘FFTW: an adaptive software architecture for the FFT’. Proc. 1998 IEEE Int. Conf. on Acoustics, Speech and Signal Processing, Seattle, WA, USA, vol. 3, 1998, pp. 1381–1384, doi: 10.1109/ICASSP.1998.681704.
    17. 17)
      • 28. Sorokin, H., Takala, J.: ‘Conflict-free parallel access scheme for mixed-radix FFT supporting I/O permutations’. 2011 IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), Prague, Czech Republic, 2011, pp. 1709–1712, doi: 10.1109/ICASSP.2011.5946830.
    18. 18)
      • 15. Lin, H.L., Lin, H., Chang, R.C., et al: ‘A high-speed highly pipelined 2n-point FFT architecture for a dual OFDM processor’. Proc. Int. Conf. on Mixed Design of Integrated Circuits and System, 2006 (MIXDES 2006), Gdynia, Poland, 2006, pp. 627–631, doi: 10.1109/MIXDES.2006.1706659.
    19. 19)
      • 35. Marti-Puig, P., Bolano, R.R.: ‘Radix-4 FFT algorithms with ordered input and output data’. IEEE DSP, Santorini-Hellas, Greece, 2009.
    20. 20)
      • 3. Puschel, M., Moura, J.M.F., Johnson, J.R., et al: ‘Spiral: code generation for DSP transforms’, Proc. IEEE, 2005, 93, (2), pp. 232–275, 10.1109/JPROC.2004.840306.
    21. 21)
      • 26. Lenart, T., Gustafsson, M., wall, V.: ‘A hardware acceleration platform for digital holographic imaging’, J. Signal Process. Syst., 2008, 52, pp. 297–311, 10.1007/s11265-008-0161-2.
    22. 22)
      • 32. Kristensen, F., Nilsson, P., Olsson, A.: ‘Flexible baseband transmitter for OFDM’. IASTED Conf. on Circuits Signals Syst., Cancun, Mexico, 2003, pp. 356–361.
    23. 23)
      • 5. Yu, C.-L., Kim, J.-S., Deng, L., et al: ‘FPGA architecture for 2D discrete Fourier transform based on 2D decomposition for large-sized data’, J. Signal Process. Syst., 2011, 64, (1), pp. 109–122.
    24. 24)
      • 6. D'Alberto, P., Milder, P.A., Sandryhaila, A., et al: ‘Generating FPGA-accelerated DFT libraries’. 15th Annual IEEE Symp. on Field-Programmable Custom Computing Machines (FCCM 2007), Napa, CA, USA, 2007, pp. 173–184. doi: 10.1109/FCCM.2007.58.
    25. 25)
      • 29. Hu, H.-S., Chen, H.-Y., Jou, S.-J.: ‘Novel FFT processor with parallel-in-parallel-out in normal order’. 2009 Int. Symp. on VLSI Design, Automation and Test, Hsinchu, Taiwan, 2009, pp. 150–153, doi: 10.1109/VDAT.2009.5158117.
    26. 26)
      • 10. Kala, S., Nalesh, S., Maity, A., et al: ‘High throughput, low latency, memory optimized 64k point FFT architecture using novel radix-4 butterfly unit’. 2013 IEEE Int. Symp. on Circuits and Systems (ISCAS2013), Beijing, China, 2013, pp. 3034–3037. doi: 10.1109/ISCAS.2013.6572518.
    27. 27)
      • 11. Cooley, J.W., Tukey, J.W.: ‘An algorithm for machine computation of complex Fourier series’, Math Comput., 1965, 9, pp. 297–301.
    28. 28)
      • 45. Wang, M., Li, Z.: ‘A hybrid SDC/SDF architecture for area and power minimization of floating-point FFT computations’. IEEE Int. Symp. on Circuits and Systems (ISCAS2016), Montreal, Canada, 2016, pp. 2170–2173.
    29. 29)
      • 34. Huang, S.J., Chen, S.G.: ‘A high-throughput radix-16 FFT processor with parallel and normal input/output ordering for IEEE 802.15.3c systems’, IEEE Trans. Circuits Syst. I, Regul. Pap., 2012, 59, (8), pp. 1752–1765, 10.1109/TCSI.2011.2180430.
    30. 30)
      • 38. Rodrguez-Ramos, J.M., Castell, E.M., Conde, C.D., et al: ‘2D-FFT implementation on FPGA for wavefront phase recovery from the CAFADIS camera’, Proc. SPIE, 2008, 7015, pp. 1–11.
    31. 31)
      • 42. Uzun, I.S., Amira, A., Bouridane, A.: ‘FPGA implementations of fast Fourier transforms for real-time signal and image processing’, IEE Proc. Vis. Image Signal Process., 2005, 152, (3), pp. 283–296.
    32. 32)
      • 12. He, S., Torkelson, M.: ‘Design and implementation of a 1024-point pipeline FFT processor’. Proc. IEEE 1998 Custom Integrated Circuits Conf. (Cat. No. 98CH36143), Santa Clara, CA, USA, 1998, pp. 131–134. doi: 10.1109/CICC.1998.694922.
    33. 33)
      • 40. Deng, L., Yu, C.-L., Chakrabarti, C., et al: ‘Efficient image reconstruction using partial 2d Fourier transform’. SIPS 2008, Washington DC, USA, 2008.
    34. 34)
      • 41. Mahmood, F., Toots, M., Öfverstedt, L.-G., et al: ‘2D discrete Fourier transform with simultaneous edge artifact removal for real-time applications’. 2015 Int. Conf. on Field Programmable Technology (FPT), Queenstown, New Zealand, doi: 10.1109/FPT.2015.7393157.
    35. 35)
      • 16. Yin, X.B., Yu, F., Ma, Z.G.: ‘Resource-efficient pipelined architectures for radix-2 real-valued FFT with real datapaths’, IEEE Trans. Circuits Syst. II, Express Briefs, 2016, 63, (8), pp. 803–807, 10.1109/TCSII.2016.2530862.
    36. 36)
      • 33. Chakraborty, T.S., Chakrabarti, S.: ‘On output reorder buffer design of bit reversed pipelined continuous data FFT architecture’. APCCAS 2008–2008 IEEE Asia Pacific Conf. on Circuits and Systems, Macao, China, 2008, pp. 1132–1135, doi: 10.1109/APCCAS.2008.4746224.
    37. 37)
      • 2. Yu, C.L., Chakrabarti, C., Park, S., et al: ‘Bandwidth-intensive FPGA architecture for multi-dimensional DFT’. 2010 IEEE Int. Conf. on Acoustics, Speech and Signal Processing, 2010, pp. 1486–1489, doi: 10.1109/ICASSP.2010.5495495.
    38. 38)
      • 37. Lin, Y.-W., Liu, H.-Y., Lee, C.-Y.: ‘A dynamic scaling FFT processor for DVB-T applications’, IEEE J. Solid State Circuits, 2004, 39, (11), pp. 2005–2013.
    39. 39)
      • 27. Chen, R., Prasanna, V.K.: ‘Energy optimizations for FPGA based 2d FFT architecture’. IEEE High Performance Extreme Computing Conf. (HPEC), Waltham, MA, USA, 2014, pp. 1–6.
    40. 40)
      • 23. Xing, Q.J., Ma, Z.G., Xu, Y.K.: ‘A novel conflict-free parallel memory access scheme for FFT processors’, IEEE Trans. Circuits Syst. II, Express Briefs, 2017, 64, (11), pp. 1347–1351, 10.1109/TCSII.2017.2683643.
    41. 41)
      • 13. Oh, J.Y., Lim, M.S.: ‘New radix-2 to the 4th power pipeline FFT processor’, IEICE Trans. Electron., 2005, E88-C, (8), pp. 1740–1746.
    42. 42)
      • 31. Yang, K.J., Tsai, S.H., Chuang, G.C.H.: ‘MDC FFT/IFFT processor with variable length for MIMO-OFDM systems’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2013, 21, (4), pp. 720–731, 10.1109/TVLSI.2012.2194315.
    43. 43)
      • 18. Hsiao, C.F., Chen, Y., Lee, C.Y.: ‘A generalized mixed-radix algorithm for memory-based FFT processors’, IEEE Trans. Circuits Syst. II, Express Briefs, 2010, 57, (1), pp. 26–30, 10.1109/TCSII.2009.2037262.
    44. 44)
      • 30. Garrido, M., Grajal, J., Gustafsson, O.: ‘Optimum circuits for bit reversal’, IEEE Trans. Circuits Syst. II, Express Briefs, 2011, 58, (10), pp. 657–661, 10.1109/TCSII.2011.2164141.
    45. 45)
      • 39. Wang, W., Duan, B., Zhang, C., et al: ‘Accelerating 2D FFT with non-power-of-two problem size on FPGA’. 2010 Int. Conf. on Reconfigurable Computing and FPGAs, Quintana Roo, Mexico, 2010, pp. 208–213, doi: 10.1109/ReConFig.2010.13.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cdt.2018.5075
Loading

Related content

content/journals/10.1049/iet-cdt.2018.5075
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address