基于FPGA的移位寄存器流水線結構FFT處理器

　　3．2 蝶形運算模塊

　　蝶算模塊由一個復數加法器，一個復數減法器和一個旋轉因子的復數乘法器構成，如圖6所示。

　　旋轉因子乘法器通常由4次實數乘法和2次加／減法運算實現，但因為cos和sin的值可以預先存儲，通過下面的算法可以簡化復數乘法器：

　　（1）存儲如下三個系數：C，C+S，C-S

　　（2）計算：E=X-Y和Z=C*E=C*（X-Y）

　　（3）用R=（C-S）*Y+Z，I=（C+S）*X-Z，

　　得到需要的結果。

　　這種算法使用了3次乘法，1次加法和2次減法，但是需要使用存儲3個表的ROM資源。

　　設計中數據的輸入為16位復數，所以將旋轉因子cos(2kπ／N)，sin(2kπ／N)量化成帶符號數的16位二進制數后，存儲到ROM中，由于值域不同，需要注意C+S和C-S的表要比C表多1位精度。

　　運算后的結果需要除以量化時乘以的倍數16b011111llllllllll。具體實現時由于除法運算在FPGA器件需要消耗較多的資源，設計中采用二進制數移位的方法來實現除法運算。為了防止數據溢出，設計對輸出結果除以2。圖7為蝶形運算模塊的RTL級結構圖。

　　3．3 倒序輸出模塊

　　由頻域抽取的基-2算法可知，運算結果需要倒序輸出。可以先將結果存儲到RAM中，然后使用O～255的二進制數倒序產生RAM讀取地址，依次將結果讀出，其中實現一個8位二進制數倒序的算法如下：

　　(1)將8位數字的相鄰兩位交換位置；

　　(2)將相鄰的兩位看作1組，相鄰兩組交換位置；

　　(3)將相鄰的4位看作1組，相鄰兩組交換位置。

　　經過這樣的交換位置后，輸出即為原來8位二進制數的倒序。

　　舉例對于8位二進制數10110110來說，第一次交換位置的結果是01111001，第二次交換位置的結果是11010110，最后交換位置的結果是01101101。可見正好是原來數字的倒序。