×

Scalable FFT processors and pipelined butterfly units. (English) Zbl 1138.94399

Summary: This paper considers partial-column radix-2 FFT processors and realizations of butterfly operations. The area and power-efficiency of butterfly units to be used in the proposed processor organization based on bit-parallel multipliers, distributed arithmetic, and CORDIC are analyzed and compared. All the selected butterfly units are synthesized onto the same \(0.11 \mu\) ASIC technology allowing the results to be compared. The proposed processor organization permits the area of the FFT implementation to be traded against the computation time, thus the final structure can be easily tailored according to the requirements of the given application. The power consumption comparison shows that butterflies based on bit-parallel multipliers are power-efficient but have limitations on clock frequency. Butterflies based on distributed arithmetic could be used when higher clock frequencies are used. If extremely long FFTs are needed, the CORDIC based butterflies are applicable.

MSC:

94C05 Analytic circuit theory
65T50 Numerical methods for discrete and fast Fourier transforms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Cooley and J. Tukey, ”An algorithm for the machine calculation of the complex Fourier series,” Math. Comput., vol. 19, 1965, pp. 297–301. · Zbl 0127.09002 · doi:10.1090/S0025-5718-1965-0178586-1
[2] Tran-Thong and B. Liu, ”Fixed-point fast Fourier transform error analysis,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 24, no. 6, 1976, pp. 563–573.
[3] J. Granata, M. Conner, and R. Tolimieri, ”Recursive fast algorithms and the role of the tensor product,” IEEE Trans. Signal Processing, vol. 40, no. 12, 1992, pp. 2921–2930. · Zbl 0771.65098
[4] S. F. Gorman and J. M. Wills. ”Partial column FFT pipelines,” IEEE Trans. Circuits Syst. II, vol. 42, no. 6, 1995, pp. 414–423. · Zbl 0939.68942
[5] S. He and M. Torkelson, ”Design and implementation of a 1024-point pipeline FFT processor,” in Proc. IEEE Custom Integrated Circuits Conf., Santa Clara, CA, 11–14 1998, pp. 131– 134.
[6] E. H. Wold and A. M. Despain, ”Pipeline and parallel-pipeline FFT processors for VLSI implementations,” IEEE Trans. Comput., vol. 33, no. 5, 1984, pp. 414–426. · Zbl 0528.68019
[7] M. Hasan and T. Arslan, ”Implementation of low-power FFT processor cores using a novel order-based processing scheme,” IEE Proc. Circuits Devices Syst., vol. 150, no. 3, 2003, pp. 149–154.
[8] M. Wosnitza, M. Cavadini, M. Thaler, and G. Tröster, ”A high precision 1024-point FFT processor for 2D convolution,” in Dig. Tech. Papers IEEE Solid-State Circuits Conf., San Francisco, CA, 5–7 1998, pp. 118–119.
[9] A. M. Despain, ”Fourier transform computers using CORDIC iterations,” IEEE Trans. Comput., vol. 23, no. 10, 1974, pp. 993–1001. · Zbl 0287.65073
[10] A. Berkeman, V. öwall, and M. Torkelson, ”A low logic depth complex multiplier using distributed arithmetic,” IEEE J. Solid-State Circuits, vol. 35, no. 4, 2000, pp. 656–659.
[11] L. Wanhammar, DSP Integrated Circuits. San Diego, CA: Academic Press, 1999.
[12] J. Takala and K. Punkka, ”Scalable FFT processors and pipelined butterfly units,” in Computer Systems: Architectures, Modeling, and Simulation, ser. Lecture Notes in Computer Science, A. D. Pimentel and S. Vassiliadis, Eds. Berlin, Germany: Springer-Verlag, 2004, pp. 373–382.
[13] J. Takala and T. Järvinen, ”Stride permutation access in interleaved memory systems,” in Domain-Specific Processors: Systems, Architectures, Modeling, and Simulation, S. S. Bhattacharyya, E. F. Deprettere, and J. Teich, Eds. New York, NY: Marcel Dekker, 2004, ch. 4, pp. 63–84.
[14] A. Wenzler and E. Lüder, ”New structures for complex multipliers and their noise analysis,” in Proc. IEEE ISCAS, vol. 2, Seattle, WA, 1995, pp. 1432–1435.
[15] S. A. White, ”A simple FFT butterfly arithmetic unit,” IEEE Trans. Circuits Syst., vol. 28, no. 4, 1981, pp. 352–355.
[16] E. Chu and A. George, Inside the FFT Black Box: Serial and Parallel Fast Fourier Transform Algorithms. Boca Raton, FL: CRC Press, 2000. · Zbl 0935.65149
[17] M. Hasan and T. Arslan, ”FFT coefficient memory reduction technique for OFDM applications,” in Proc. IEEE ICASSP, vol. 1, Orlando, FL, 13–17 2002, pp. 1085–1088.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.