臺灣博碩士論文加值系統

本論文依據基底為4分時快速傅立葉轉換(FFT)的演算法，及以數位座標旋轉器(CORDIC)為基礎的算術運算所具有之特性，提出一種高效率Pipeline FFT processor的架構。本論文所提出之架構，利用將連續性的輸入訊號，加以重組成平行的資料流同時運算，不僅將硬體的使用效率提高接近至100%，而且與之前被提出的FFT processor相比，亦有較少的記憶體空間需求。另一方面，本論文利用化簡多餘的轉動係數(twiddle factor)並配合以CORDIC control information代替被乘數的實部及虛部，更有效率的減少4分之三儲存factors的ROM大小。

This thesis presents an efficient implementation of the pipeline FFT processor based on radix-4 decimation-in-time algorithm with the use of CORDIC-based arithmetic units. By recombining the sequential input samples to parallel data streams, the proposed architecture can’t only achieve nearly fully hardware utilization, but also require much less memory compared with the previous FFT processor. In addition, in FFT processors, several modules of ROM are required for the storage of twiddle factors. Exploiting the redundancy of the factors and using the CORDIC control information instead of multiplicands can efficiently reduce the overall ROM size by a factor of 4.

TABLE OF CONTENTS
摘要.................................................. i
ABSTRACT.............................................. ii
TABLE OF CONTENTS..................................... iii
LIST OF FIGURES....................................... v
LIST OF TABLES........................................ vii
CHAPTER 1. INTRODUCTION............................... 1
CHAPTER 2. FFT ALGORITHMS............................. 3
2.1 Decimation In Time (DIT) Radix-2 Algorithm........ 3
2.2 Decimation In Frequency (DIF) Radix-2 Algorithm... 5
2.3 Radix-4 and Radix-2^2 Algorithm................... 7
2.4 In-Place Computations............................. 8
CHAPTER 3. PIPELINE FFT PROCESSOR ARCHITECTURES....... 10
3.1 Review of FFT processors.......................... 10
3.2 Classifying Architectures......................... 11
CHAPTER 4.COMPLEX MULTIPLIER DESIGN AND IMPLEMENTATION 16
4.1 Conventional CSA Multiplier....................... 16
4.1.1 Radix-4 Modified Booth Recoding Algorithm....... 16
4.1.2 CSA Multiplier with Modified Booth Recoding..... 18
4.2 Distributed Arithmetic............................ 18
4.2.1 Conventional Distributed Arithmetic............. 19
4.2.2 Offset-Binary coding............................ 20
4.2.3 DA-based complex Multiplier with Offset-Binary
coding.......................................... 21
4.3 CORDIC Technique.................................. 23
4.3.1 CORDIC Algorithm................................ 23
4.3.2 The Design of a CORDIC-Based Complex Multiplier 24
4.4 Implementation in an FPGA......................... 26
CHAPTER 5. PROPOSED ARCHITECTURE...................... 28
5.1 Radix-4 Word-Serial FFT Processors Using CORDIC-
basedArithmetic................................... 28
5.2 Comparison........................................ 32
5.3 Implementation.................................... 33
5.3.1Environments and Designated Specification........ 33
5.3.2 Control Unit.................................... 35
5.3.3 Parallel R2^2SDF................................ 36
5.3.4 R4MDC and Arithmetic Unit....................... 37
5.3.5 Synthesis Results............................... 39
CHAPTER 6. CONCLUSION................................. 42
REFERENCES............................................ 43

Reference
[1] E.E. Swartzlander, W. K. W. Young, and S. J. Joseph,"A radix-4 delay commutator for fast Fourier transform processor implementation”,IEEE Journal of Solid-State Circuits, vol. SC-19, pp. 702-709, Oct. 1984.
[2] E. Bidet, D. Castelain, C. Joanblanq, and P. Stenn,“A fast signal-chip Implementation of 8192 complex point FFT”, IEEE Journal of Solid-State Circuits, vol. 30, pp.300-305, Mar. 1995.
[3] E. H. Wold and A. M. Despain, “Pipeline and parallel-pipeline FFT processor for VLSI implementation”, IEEE Transactions an Computers, vol. C-33, pp. 414-426, May 1984.
[4] Bevan M. Bass, “A 9.5mW 330usec 1024-point FFT processor”, in Custom Integrated Circuits Conference, pp.127-130, San Jose, CA, May 1998.
[5] Yun-Nan Chang; Parhi, K.K, “Efficient FFT implementation using digit-serial arithmetic”, Signal Processing Systems, 1999. SiPS 99. 1999 IEEE Workshop on, 1999.
[6] J.E. Volder, “The CORDIC Trigonometric Computing Technique”, IRE Transactions on Electronic Computers, Vol. EC-8, No. 3, pp: 330-4, Sept. 1959.
[7] R. Andraka, “A Survey of CORDIC Algorithms for FPGA Based Computers”, Proc of the 1998 CM/SIGDA Sixth International Symposium on FPGAs, February 22-28, 1998, Monterey, CA, pp.191-200.
[8] Alvin M. Despain,“Fourier Transform Computers Using CORDIC Iterations”, IEEE Transactions on computers, vol. c-23, NO. 10, Oct 1974.
[9] B. Gold and T. Bially, “parallelism in fast Fourier transform hardware”, IEEE Trans. Audio Electroacoustics, vol. 21, pp. 5-16, 1973.
[10] C. C. W. Hui, T. J. Ding, J. V. McCanny, and R. F. Woods, “A 64-point Fourier transform chip for video motion compensation using phase correlation”, IEEE Journal of Solid-State Circuits, vol. 31, pp. 1751-1761, Nov. 1996.
[11] S. He and M. Torkelson, “Design and implementation of a 1024-point pipeline FFT processor”, in Custom Integrated Circuits Conference, pp.131-134, Santa Clara, CA, May 1998.
[12] Gin-Kou Ma and Fred J. Taylor, “Multiplier Policies For Digital Signal Processing”, IEEE ASSP Magazine, January 1990.
[13] K. K. Parhi, “VLSI Digital Signal Processing Systems: Design and Implementation”, John Wiley & Son, Inc. ISBN 0-471-24186-5, 1999.
[14] R. Fried, “Minimizing energy dissipation in high-speed multiplier,” in Proc. Of ISLPED-97, (Monterey, CA), pp. 214-219, Aug 1997.
[15] Croisier A., Esteban D.J., Levilion, Riso V. “Digital Filter for PCM Encoded Signals”, U.S. Patent 3777 130, Dec 1973.
[16] Pascual, A.P.; Valls, J.; Peiro, M.M.” Efficient complex-number multipliers mapped on FPGA”, IEEE International Conference on , Volume: 2 , 1999 Page(s): 1123 -1126 vol.2
[17] S. Bertazzoni, G.C. Cardarilli, M. Iannuccelli, M. Salmeri, A. Salsano, O. Simonelli, ൘-Point High Speed (I)FFT for OFDM Modulation", IEEE International Symposium on Circuit and Systems, ISCAS 98, Monterey, USA, May 31 - June 3, 1998.
[18] Peter Pirsch, “Architectures for Digital Signal Processing”, John Wiley & Son, Inc. ISBN 0-471-97145-6, 1998.
[19] C. D. Tose et al, “0.5-um CMOS circuits for demodulation and decoding of an OFDM-based digital TV signal conforming to the European DVB-T standard ”, IEEE Journal of Solid-State Circuits, vol. 33, pp. 1781-1791, November 1998.
[20] G. Bi and E. Jones, “A pipeline FFT processor for word-sequential data”, IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 37, pp. 1982-1985, Dec. 1989.
[21] Tion Jiu, John V. McCanny, Fellow, IEEE, and Yi Hu, “Rapid Design of Application Specific FFT Cores”, IEEE Transactions on Signal Processing, vol. 47, NO. 5, MAY 1999
[22] C. Hui, T. J. Ding, J. V. McCanny, and R. F. Woods, “a new FFT architecture and chip design for motion compensation based on phase correlation”, IEEE Trans. Solid-State Circuits, vol.31, pp. 1751-1761, Nov. 1996.