快速傅立葉轉換處理器設計

Abstract

本論文針對幾種傅立葉演算法去分析比較其算術複雜度, 並對不同的架構做硬體效率、硬體花費和速度上的比較分析。最後，我們提出一種高效率的二基數蝴蝶處理單元的設計，使複數乘法器的使用效率從傳統的百分之五十提昇至百分之百，並且可以達到加速的功能。另外，我們亦針對傳統複數乘法器做化簡，使複數乘法器由原來的三個乘法器、五個加法器變成三個乘法器、四個加法器。因此，可以節省一個加法器。

In this thesis, we analyze the computational complexity of several FFT algorithms. And we compare the hardware utilization efficiency, the hardware cost, and speed of different architecture. At last, we propose a hardware-efficient architecture and the utilization efficiency of complex multiplier is from half utilization efficiency to full utilization efficiency, and the speed is two times of conventional case. Besides, we also simplify the conventional complex multiplier composed of 3 multipliers and 5 adders and get a complex multiplier composed of 3 multipliers and 4 adders. Hence, one adder can be saved.