A VLSI array processing oriented fast fourier transform algorithm and hardware implementation

ABSTRACT

Many parallel Fast Fourier Transform (FFT) algorithms adopt multiple stages architecture to increase performance. However, data permutation between stages consumes volume memory and processing time. An FFT array processing mapping algorithm is proposed in this paper to overcome this demerit. In this algorithm, arbitrary 2^k butterfly units (BUs) could be scheduled to work in parallel on n=2² data (k=0, 1,..., s-1). Because no inter stage data transfer is required, memory consumption is reduced to 1/3 of the original algorithm. Moreover, with the increasing of BUs, not only does throughput increase linearly, system latency also decreases linearly. This array processing orientated architecture provides flexible tradeoff between hardware cost and system performance. An 18-bit word-length 1024-point FFT architecture with 4 BUs is given to demonstrate this mapping algorithm. The design is implemented with TSMC 0.18μm CMOS technology. The core area is 2.99x1.12mm 2 and clock frequency is 326MHz in typical condition (1.8V, 25°C). This processor could complete 1024 FFT calculation in 7.839μs.

REFERENCES

• 1: D. Takahashi, "High-Performance Parallel FFT Algorithms for the HITACHI SR8000", The Fourth International Conference/Exhibition on High Performance Computing in the Asia-Pacific Region, Vol. 1, pp. 192--199, May 2000.
• 2: Daisuke Takahashi , Yasumasa Kanada, High-Performance Radix-2, 3 and 5 Parallel 1-D Complex FFT Algorithms for Distributed-Memory Parallel Computers, The Journal of Supercomputing, v.15 n.2, p.207-228, Feb.1.2000 [doi>10.1023/A:1008160021085]
• 3: Kuninobu Tanno , Toshihiro Taketa , Susumu Horiguchi, Parallel FFT algorithms using radix 4 butterfly computation on an eight-neighbor processor array, Parallel Computing, v.21 n.1, p.121-136, Jan. 1995 [doi>10.1016/0167-8191(94)00034-8]
• 4: G. D. Bergland, H. W. Hale, "Digital Real-Time Spectral Analysis", IEEE Transactions on Computers, Vol. EC-16, No. 2, pp. 180--185, April 1967.
• 5: G. C. O'Leary, "Non-recursive Digital Filtering Using Cascade Fast Fourier Transformers", IEEE Transactions on Audio Electroacoustics, Vol. AU-18, No. 2, pp. 177--183, June 1970.
• 6: D. R. Bungard, L. Lau, T. L. Rorahaugh, "New Programmable FFT Implementation for Radar Signal Processing", IEEE International Symposium on Circuits and Systems-ISCAS89, Vol. II, pp. 1323--1327, May 1989.
• 7: N. M. Brenner, "Fast Fourier Transform of Externally Stored Data", IEEE Transactions on Audio Electroacoustics, Vol.AU-17, No. 2, pp. 128--132, June 1969.
• 8: R. Shenhav, "The Decomposition of Long FFT's for High Throughput Implementation", IEEE International Conference on Acoustics, Speech, and Signal Processing-ICASSP87, pp. 1043--1046, April 1987.
• 9: D. L. Jones, H. V. Sorenon, "A Bus-Oriented Multiprocessor Fast Fourier Transform", IEEE Transactions on Signal Processing, Vol. 39, No. 11, pp. 2547--2551, November 1991.
• 10: Y. T. Ma, "A VLSI-Oriented Parallel FFT Algorithm", IEEE Transactions on Signal Processing, Vol. 44 No. 2, pp. 445--448, February 1996.
• 11: J. W. Cooley, J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series", Math of Computation, Vol. 19, pp. 297--301, April 1965.
• 12: R. C. Singleton, "A Method for Computing the Fast Fourier Transform with Auxiliary Memory and Limited High-Speed Storage", IEEE Transactions on Audio and Electroacoustics, Vol. AU-15, pp. 91--98, June 1967.
• 13: S. Y. Kung, "On Supercomputing With Systolic Wavefront Array Processors", Proceedings of IEEE, Vol. 72, No. 7, pp. 867--884, July 1984.
• 14: P. Lee , Z. M. Kedem, Synthesizing Linear Array Algorithms from Nested FOR Loop Algorithms, IEEE Transactions on Computers, v.37 n.12, p.1578-1598, December 1988 [doi>10.1109/12.9735]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Algorithms

Additional Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic
          Subjects: Cost/performance
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration); Algorithms implemented in hardware

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
array processing, fast fourier transform (FFT), singleton algorithm