隨著無線可攜式產品的需求亦加殷切，低工率晶片設計成為一項值得研究的課題，另外，WiMAX的堀起更引發一股SOFDMA的研究熱潮。本論文揭露一種可用於SOFDMA領域的低功率FFT架構。
　　SOFDMA是Scalable Orthogonal Frequency Division Multiple Access的縮寫。可多點數化(Scalable)使得WiMAX系統能配合外在環境的變化適時地調整FFT的點數以達到最有效率而又符合最低QoS要求之通訊傳輸。多用戶接取(Multiple Access)使得WiMAX能夠在給定頻譜範圍內單點對多點地進行互通傳輸，本架構即是利用多用戶接取特性設計可子通道化(Subchannelization)之FFT處理器。
　　由於晶片製程的進步，晶粒屬性有些已從核心侷限型(Core limited)導向焊盤侷限型(Pad limited)，面積已非電路設計的首要考量，因此，本論文提出快閃式架構，致使處理器設計同時符合低功率與高速度兩項要求。另外，為了降低功率控制機制的複雜度，本架構提出一種記錄式方法(Registry Method)。
　　妥善的非同步設計能夠同時提供低功率與高速度兩項好處，基於此，本架構的FFT核心部分採用的是非同步設計，伹電子設計自動化工具(EDA)廠商近十數年來的研究重點皆著重在同步設計，因此，本發明在非同步核心之外係用同步電路予以包裹，目的在於晶片系統(SOC)設計時的穩健性與易整合性。
　　本論文的重心在於架構設計與功耗估算，主要是用MATLAB程式寫成，分別針對IEEE 802.16e WiMAX和IEEE 802.16-2004 WiMAX所需的128/512/1024及256/2048點FFT評估採用本架構時，興一般FFT處理器相比較所能節省下來的功率（高達80%至98%）。為了便於晶片實現所需，更以Agilent® ADS製作一可即調即跑式(tunable)模擬環境，便於設計者估算可能耗散的功率。

An inventive FFT architecture, which is both scalable and subchannelizable, is provided with low-power and high-speed characteristics for SOFDMA application in IEEE 802.16 WiMAX communication protocol and other fields that have features in SOFDMA applications.
     OFDMA (Orthogonal Frequency Division Multiple Access) is a multiple access scheme for OFDM systems.  OFDMA works by assigning a subset of subcarriers to individual users.  SOFDMA is a scalable version of OFDMA, the point number of FFT processors are scalable in sessions.  Scalability is required to adapt FFT point number to changing channels, and subchannelizability is required for MA (Multiple Access).
     As the chip manufacturing process becomes more and more advanced, the die size is less critical than before.  For the increasing demands in portable devices, low-power feature becomes the critical issue in chip design.  Therefore, unused arithmetic operations are prohibited in the present inventive design to achieve low-power requirement because only a small subset of FFT outputs are of interests for a specific SS (Subscriber Station) in one session of a IEEE 802.16e or IEEE 802.16-2004 WiMAX systems.  It is the spirits of the present subchannelization design.
     IEEE 802.16e and IEEE 802.16-2004 WiMAX systems requires scalability in FFT processing for 128/512/1024 and 256/2048 points.  The present scalability design uses multiplexing concept to build only one 1024-point and only one 2048-point FFT processors in an IEEE 802.16e and an IEEE 802.16-2004 WiMAX systems, respectively.
     Registry method and Sync-Async architecture are also disclosed for the purposes of structure simplification and low-power/high-speed designs.  The performance on areas and power efficiency are analyzed based on MATLAB codes.  A closed system platform is used to tune design parameters for chip implementation by using Agilent® ADS (Advanced Design System) tool.

TABLE OF CONTENTS
CHAPTER 1 INTRODUCTION	1
1.1	WiMAX Overview	1
1.2	Applications	3
1.3	Features	3
1.4	Organization of the Thesis	4
CHAPTER 2 PRINCIPLES	5
2.1	FFT History	5
2.2	Flash-typed FFT DIF Scheme with Radix 2	6
2.3	Power Reduction based on Arithmetic Operator Numbers	8
2.3.1 OPTIMAL Mode Canonical Form for Arithmetic Operator Number	9
2.3.2 INV Mode Canonical Form for Arithmetic Operator Number	12
2.4	Examples of Power Reduction	13
CHAPTER 3 ARCHITECTURE	15
3.1	Scalable Flash-typed FFT Design	15
3.1.1 Accumulation Scheme	15
3.1.2 Scalability Scheme	16
3.2	Subchannelizable Flash-typed FFT Design	18
3.2.1 AND-Typed Operand Isolation Technology	19
3.2.2 OR-Typed Operand Isolation Technology	19
3.3	SELDIF Registry Control Methodology	20
3.4	Advanced Sync-Async Chip Implementation	22
3.5	Benefits from the Present Innovative Scheme	25
CHAPTER 4 LOW POWER ALGORITHMS AND POWER ANALYSIS	26
4.1	Optimum Power Efficiency Algorithm (OPTIMAL Mode)	26
4.2	Sub-Optimum Power Efficiency Algorithm (INV Mode)	28
4.3	Power Analysis for IEEE 802.16e WiMAX Application	28
4.3.1 Scale of 128 for IEEE 802.16e Power Analysis	29
4.3.2 Scale of 512 for IEEE 802.16e Power Analysis	32
4.3.3 Scale of 1024 for IEEE 802.16e Power Analysis	36
4.4	Power Analysis for IEEE 802.16-2004 WiMAX Application	39
4.4.1 Scale of 256 for IEEE 802.16-2004 Power Analysis	39
4.4.2 Scale of 2048 for IEEE 802.16-2004 Power Analysis	42
CHAPTER 5 INTRODUCTION TO ANALYSIS PLATFORM	45
5.1	System View	45
5.2	Source Generation	47
5.3	SELDIF Generation	48
5.4	Tuning Window	49
5.5	Display Window	50
CHAPTER 6 CONCLUSION	53
6.1	Summary	53
6.2	Future Work	55
REFERENCE 	57
LIST OF FIGURES
Figure 2.1 Radix-2 FFT schematic view....................................................8
Figure 2.2 Butterfly of 8-point FFT with DIF..........................................10
Figure 3.1 Accumulation scheme of FFT module in SOFDMA application
................................................................................................15
Figure 3.2 Scalability scheme of a FFT processor......................................17
Figure 3.3 Subchannelizable Flash-typed FFT architecture ....................18
Figure 3.4 AND-type Operand Isolation Low Power Technology ..........19
Figure 3.5 OR-type Operand Isolation Low Power Technology .............20
Figure 3.6 SELDIF Registry Control Methodology ................................21
Figure 3.7 Advanced Sync-Async design architecture ............................24
Figure 4.1 OPTIMAL Mode for the Optimum Algorithm.......................27
Figure 4.2 INV Mode for the Sub-Optimum Algorithm ..........................28
Figure 4.3 Activation Proportion of Arithmetic Operators for 128-point
FFT..........................................................................................29
Figure 4.4 Power Usage of 128-point FFT in OPTIMAL mode..............31
Figure 4.5 Power Usage of 128-point FFT in INV mode ........................31
Figure 4.6 Activation Proportion of Arithmetic Operators for 512-point
FFT..........................................................................................34
Figure 4.7 Power Usage of 512-point FFT in OPTIMAL mode..............35
Figure 4.8 Power Usage of 512-point FFT in INV mode ........................35
Figure 4.9 Activation Proportion of Arithmetic Operators for 1024-point
FFT .........................................................................................37
Figure 4.10 Power Usage of 1024-point FFT in OPTIMAL mode..........38
Figure 4.11 Power Usage of 1024-point FFT in INV mode.....................38
Figure 4.12 Activation Proportion of Arithmetic Operators for 256-point
FFT........................................................................................40
Figure 4.13 Power Usage of 256-point FFT in OPTIMAL mode............41
Figure 4.14 Power Usage of 256-point FFT in INV mode ......................41
Figure 4.15 Activation Proportion of Arithmetic Operators for 2048-point
FFT .......................................................................................43
Figure 4.16 Power Usage of 2048-point FFT in OPTIMAL mode..........44
Figure 4.17 Power Usage of 2048-point FFT in INV mode ....................44
Figure 5.1 Simulation System View using ADS tool...............................46
Figure 5.2 Source Generation Block using ADS .....................................48
Figure 5.3 SELDIF Generation Block using ADS...................................49
Figure 5.4 Tuning Window using ADS....................................................50
Figure 5.5 Information about Usages of Arithmetic Operators using ADS
................................................................................................52
Figure 5.6 Bode Diagram Analysis using ADS........................................52
LIST OF TABLES
Table 1.1 Comparison of IEEE 802.16-2004 and 802.16e WiMAX..........1
Table 1.2 Comparison among IEEE 802.xx standards...............................2
Table 2.1 Number of Activated Arithmetic Operator in OPTIMAL Mode
..................................................................................................11
Table 2.2 Number of Activated Arithmetic Operator in INV Mode.........12
Table 3.1 Equivalent number of complex adders in a separate FFT module
..................................................................................................16
Table 3.2 Comparison between Synchronous and Asynchronous designs
..................................................................................................23
Table 4.1 Usage of Arithmetic Operators for 128-point FFT in OPTIMAL
Mode.........................................................................................30
Table 4.2 Usage of Arithmetic Operators for 128-point FFT in INV Mode
..................................................................................................30
Table 4.3 Usage of Arithmetic Operators for 512-point FFT in OPTIMAL
Mode.........................................................................................32
Table 4.4 Usage of Arithmetic Operators for 512-point FFT in INV Mode
..................................................................................................33
Table 4.5 Usage of Arithmetic Operators for 1024-point FFT in
OPTIMAL Mode ......................................................................36
Table 4.6 Usage of Arithmetic Operators for 1024-point FFT in INV
Mode ........................................................................................36
Table 4.7 Usage of Arithmetic Operators for 256-point FFT in OPTIMAL
Mode ........................................................................................39
Table 4.8 Usage of Arithmetic Operators for 256-point FFT in INV Mode
..................................................................................................40
Table 4.9 Usage of Arithmetic Operators for 2048-point FFT in
OPTIMAL Mode......................................................................42
Table 4.10 Usage of Arithmetic Operators for 2048-point FFT in INV
Mode ......................................................................................42
Table 6.1 Latency Comparison for FFT processors ....................................54

[1]	E. Oran Brigham, The Fast Fourier Transform and its Applications. Prentice-Hall, 1988, pp. 134-135.
[2]	Cooley, J. W., and J. W. Tukey, “An Algorithm for Machine Calculation of Complex Fourier Series,” Math. Computation, Vol. 19, Apr. 1965, pp. 297-301.
[3]	Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, 1989, pp. 407-411.
[4]	Grigoryan, A.M., “A Novel Algorithm for Computing the 1-D Discrete Hartley Transform”, Signal Processing Letters, IEEE, vol. 11, Issue 2, Part 2, Feb. 2004, pp. 156 - 159
[5]	Zhiping Lin, Li Xu, and Huijin Fan, “On Minor Prime Factorizations for n-D Polynomial Matrices”, IEEE Transactions on Circuits and Systems-II: Express Briefs, vol. 52, No. 9, Sep. 2005, pp. 568 – 571.
[6]	Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. "Fast Fourier Transform." Ch. 12 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, 1992, pp. 490-529.
[7]	N. Banerjee, A. Raychowdhury, S. Bhunia, H. Mahmoodi, and K. Roy, “Novel Low-Overhead Operand Isolation Techniques for Low-Power Datapath Synthesis”, Proceedings of the 2005 International Conference on Computer Design (ICCD’05), Oct. 2005, pp. 206 – 211.
[8]	Minsu, C., and Nohpill P., “Locally Synchronous, Globally Asynchronous Design for Quantum-Dot Cellular Automata (LSGA QCA)”, Nanotechnology, 2005, 5th IEEE Conference, vol. 1, July 2005, pp. 121 – 124.
[9]	Kawokgy, M., and Salama, C.A.T., “Low-Power Asynchronous Viterbi Decoder for Wireless Applications”, Low Power Electronics and Design, 2004, ISLPED ‘04, Proceedings of the 2004 International Symposium, Aug. 2004, pp. 286 – 289.
[10]	Yuan, J.S., and Weidong Kuang, “Teaching Asynchronoous Design in Digital Integrated Circuits”, Education, IEEE Transactions, vol. 47, Issue 3, Aug. 2004, pp. 397 – 404.
[11]	Dettmer, R., “No Clock, No Bus – No Sweat [Asynchronous IC Interconnect Network]”, IEE Review, vol. 50, Issue 9, Sept. 2004, pp. 36 – 39.
[12]	Made, M., Felicijan, T., Efthymiou, A., Edwards, D., and Lavagno, L., “Asynchronous On-Chip Networks”, Computers and Digital Techniques, IEE Proceedings, vol. 152, Issue 2, Mar. 2005, pp. 273 – 283.
[13]	Altera Corporation, “Accelerating WiMAX System Design with FPGAs,” Altera Corporation, Oct. 2004, Table 2, pp. 10.
[14]	Altera Corporation, “Stratix II Device Handbook,” Altera Corporation, Vol. 1, April 2006, pp. 1-2.
[15]	Prepared on Behalf of WiMAX Forum, “Mobile WiMAX – Part I: A Technical Overview and Performance Evaluation,” WiMAX Forum, Feb. 2006, pp. 15.