Triple-Matrix Product-Based 2D Systolic Implementation of Discrete Fourier Transform

详细信息    查看全文

• 作者：I. Mamatha ; T. S. B. Sudarshan ; Shikha Tripathi…
• 关键词：Discrete Fourier transform ; Fast Fourier transform ; Systolic array architecture ; VLSI ; FPGA
• 刊名：Circuits, Systems, and Signal Processing
• 出版年：2015
• 出版时间：October 2015
• 年：2015
• 卷：34
• 期：10
• 页码：3221-3239
• 全文大小：777 KB
• 参考文献：1.J.L. Aravena, Triple matrix product architecture for fast signal processing. IEEE Trans. Circuits Syst. 35(1), 119-22 (1988)
  2.V. Boriakoff, FFT computation with systolic arrays a new architecture. IEEE Trans. Circuits Syst. II(41), 278-84 (1994)
  3.C.H. Chang, C.L. Wang, Y.T. Chang, Efficient VLSI architectures for fast computation of the discrete Fourier transform and its inverse. IEEE Trans. Signal Proc. 48(11), 3206-216 (2000)MathSciNet
  4.L.W. Chang, M.Y. Chen, A new systolic array for discrete Fourier transform. IEEE Trans. Acoust. Speech Signal Process. 36(10), 1665-666 (1998)
  5.J. Choi, V. Boriakoff, A new linear systolic array for FFT computation. IEEE Trans. Circuits Syst. II 39(4), 236-39 (1992)
  6.J.W. Cooley, J.W. Tukey, An algorithm for the machine computation of complex Fourier series. Math. Comput. 19, 297-01 (1965)MathSciNet
  7.S. He, M. Torkelson, A systolic array implementation of common factor algorithm to compute DFT, in Proceedings International Symposium Parallel Architectures, Algorithms and Networks (1994), pp. 374-81
  8.S. He, M. Torkelson, A new expandable 2D systolic array for DFT computation based on symbiosis of 1D arrays, in Proceedings IEEE International Conference Algorithms and Architectures for parallel Processing, vol. 1 (1995), pp. 12-9
  9.S. He, M. Torkelson, Design and implementation of a 1024-point pipeline FFT processor, in Proceedings IEEE Custom Integrated Circuits Conference (1998), pp. 131-34
  10.S.F. Hsiao, W.R. Shiue, Low-cost unified architectures for the computation of discrete trigonometric transforms, in Proceedings IEEE International Conference Acoustics, Speech Signal Processing, vol. 6 (2000), pp. 3299-302
  11.H.T. Kung, Special-purpose device for signal and image processing: an opportunity in very large scale integration (VLSI). Proc. SPIE Int. Soc. Opt. Eng. 241, 74-4 (1980)
  12.H.T. Kung, Why systolic architectures? IEEE Comput. 15(1), 37-6 (1982)
  13.S.-C. Lai, S.-F. Lei, W.-H. Juang, C.-H. Luo, A low-cost, low-complexity, and memory-free architecture of novel recursive DFT and IDFT algorithms for DTMF application. IEEE Trans. Circuits Syst. II 57(9), 711-15 (2010)
  14.H. Lim, E.E. Swartzlander, Multidimensional systolic arrays for the implementation of discrete Fourier transforms. IEEE Trans. Signal Proc. 47(5), 1359-370 (1999)
  15.N. Ling, M.A. Bayoumi, The design and implementation of multidimensional systolic arrays for DSP applications, in Proceedings International Conference Acoustics, Speech, Signal Processing, vol. 2 (1989), pp. 1142-145
  16.X. Liu, F. Yu, Z.-K. Wang, A pipelined architecture for normal I/O order FFT. J. Zhejang University-Science 12(1), 76-2 (2011)MathSciNet
  17.V. Mahendra, R. Arvind, Design and FPGA implementation of systolic array architecture for matrix multiplication. Int. J. Comput. Appl. 26(3), 18-2 (2011)
  18.A. Mankar, N. Prasad, S. Meher, FPGA implementation of discrete Fourier transform core using NEDA, in International Conference Communication Systems and Network Technologies (2013), pp. 711-15
  19.W. Marwood, A.P. Clarke, Matrix product machine and the Fourier transform. Proc. Inst. Elect. Eng. G 137(4), 295-01 (1990)
  20.P.K. Meher, Highly concurrent reduced complexity 2-D systolic array for discrete Fourier transform. IEEE Signal Proc. Lett. 13(8), 481-84 (2006a)
  21.P.K. Meher, Efficient systolic implementation of DFT using a low-complexity convolution-like formulation. IEEE Trans. Circuits Syst. II 53(8), 702-06 (2006b)MathSciNet
  22.P.K. Meher, J.C. Patra, A.P. Vinod, Efficient systolic designs for 1 and 2-dimensional DFT of general transform-lengths for high speed wireless communication applications. J. Signal Proc. Syst. 60(1), 1-4 (2010)
  23.N.R. Murthy, M.N.S. Swamy, On the real time computation of DFT and DCT through systolic architectures. IEEE Trans. Signal Proc. 42(4), 988-91 (1994)
  24.J.G. Nash, Computationally efficient systolic architecture for computing the discrete Fourier transform. IEEE Tran. Signal Proc. 53(12), 4640-651 (2005)MathSciNet
  25.C.V. Niras, V. Thomas, Systolic variable length architecture for discrete Fourier transform in long-term evolution, in 2012 International Symposium Electronic System Design (2012), pp. 52-5
  26.Z.-X. Yang, Y.-P. Hu, C.-Y. Pan, L. Yang, Design of a 3780-point IFFT processor for TDS-OFDM. IEEE Trans. Broadcast. 48(1), 57-1 (2002)
  27.W.C. Yeh, C.-W. Jen, High-speed and low power split-radix FFT. IEEE Trans. Signal Proc. 51(3), 864-74 (2003)MathSciNet
  28.X. Zhang, N. Jindapetch, An efficient VLSI architecture for the radar algorithm based DFT prime-factor, in International Conference Electrical Engineering/Electronics Computer Telecommunications and Information Technology (ECTI-CON) (2010), pp. 941-44
  
• 作者单位：I. Mamatha (1)
  T. S. B. Sudarshan (1)
  Shikha Tripathi (1)
  Nikhil Bhattar (2)
  
  1. School of Engineering, Amrita Vishwa Vidyapeetham (University), Bangalore Campus, Bangalore, 560035, India
  2. Engineer Staff-II, IC Design, Broadcom India Research Pvt. Ltd, Bangalore, India
  
• 刊物类别：Engineering
• 刊物主题：Electronic and Computer Engineering
  
• 出版者：Birkh盲user Boston
• ISSN：1531-5878

文摘

Realization of \(N\)-point discrete Fourier transform (DFT) using one-dimensional or two-dimensional systolic array structures has been developed for power of two DFT sizes. DFT algorithm, which can be represented as a triple-matrix product, can be realized by decomposing \(N\) into smaller lengths. Triple-matrix product form of representation enables to map the \(N\)-point DFT on a 2D systolic array. In this work, an algorithm is developed and is mapped to a two-dimensional systolic structure where DFT size can be non-power of two. The proposed work gives flexibility to choose \(N\) for an application where \(N\) is a composite number. The total time required to compute \(N\)-point DFT is \(2(N_{1}-1)+N_{2}+N\) for any \(N=N_{1}N_{2}\). The array can be used for matrix–matrix multiplication and also to compute the diagonal elements of triple-matrix multiplication for other applications. The proposed architecture produces in-order stream of DFT sequence at the output avoiding need for reordering buffer. Large sized DFT can be computed by repeatedly using the proposed systolic array architecture.