快速傅里葉變換(FFT)在雷達、通信和電子對抗等領域有廣泛應用。近年來現場可編程門陣列(FPGA)的飛速發展，與DSP技術相比，由于其并行信號處 理結構，使得FPGA能夠很好地適用于高速信號處理系統。由于Altera等公司研制的FFT IP核，價錢昂貴，不適合大規模應用，在特定領域中，設計適合于自己領域需要的FFT處理器是較為實際的選擇。
本文設計的FFT處理器，基于FPGA技術，由于采用移位寄存器流水線結構，實現了兩路數據的同時輸入，相比傳統的級聯結構，提高了蝶形運算單元的運算效 率，減小了輸出延時，降低了芯片資源的使用。在OFDM系統的實際應用中，因它可以采用快速傅里葉變換，能方便快捷地實現調制和解調，故結合MIMO技 術，設計的FFT處理器結構，可以很好地應用于2根天線的MIMO-OFDM系統中。
1 FFT處理的應用及DIF FFT算法原理
圖1給出一個2根天線MIMO-OFDM系統中FFT的使用?？焖俑道锶~變換算法基本上分為兩大類：時域抽取(DIT)和頻域抽取(DIF)，這里設計的FFT處理器采用基-2 DIF算法。
對于N點序列x(N)，其傅里葉變換
將x(n)分成上、下兩部分，得：
這樣將兩個N點的DFT分成兩個N／2點的DFT，分的方法是將x(k)按序號k的奇、偶分開。通過這種方式繼續分下去，直到得到兩點的DFT。采用DIF方法設計的FFT，其輸入是正序，輸出是按照奇偶分開的倒序。
2 移位寄存器流水線結構的FFT
在傳統流水線結構的FFT中，需要將全部數據輸入寄存器后，可開始蝶形運算。在基-2 DIF算法中可以發現，當前N／2個數據進入寄存器后，運算便可以開始，此后進入的第N／2+1個數據與寄存器第一個數據進行蝶形運算，以此類推。
由于采用頻域抽取法，不需要對輸入的數據進行倒序處理，簡化了地址控制，這樣，可以采用移位寄存器的方式，依次將前N／2個數據移入移位寄存器，在 N／2+l時刻，第一個數據移出移位寄存器，參與運算。相對于傳統的RAM讀寫方式，采用移位寄存器存儲結構綜合后的最大工作頻率為500 MHz，遠大于RAM方式的166 MHz。
當移位寄存器相繼有數據移出時，在移位寄存器中會出現空白位。此時，引入第二路數據，在第一路數據依次移出進行蝶算時，第二路數據依次補充到移位寄存器的 空白位中，為運算做準備。通過這樣一種類似“乒乓操作”的結構，可以使蝶形運算模塊中的數據不間斷地輸入，運算效率達到100％。不同于傳統的“乒乓操 作”結構，由于使用移位寄存器，不需要兩塊RAM，可以省掉一半的寄存器。圖2為256點FFT處理器的第一級結構。
基于上述基本原理，將這種移位寄存器結構擴展到整個FFT系統的各級，可以發現各級使用的移位寄存器數量是遞減的?，F使用一個8點結構來進行說明。
如圖3所示，數據由輸入l和輸入2進入第一級。通過開關進行選通控制。由于是N=8的運算，所以各級分別加入4級、2級和1級的移位寄存器。
分兩路來說明運算過程：
將K1打到位置①，第一路數據進入移位寄存器，待第一路的前4個數據存入4級移位寄存器后，第一路進入的第5個數據與移位寄存器移出的第1個數據進行蝶形運算。
由于輸出結果有上下兩路，第二級是一個四點的DFT，所以對于上路的輸出結果x0(0)+x0(4)類似于第一級，直接存入下一級寄存器，為四點運算做準備，下路的輸出，
先存入本級2級移位寄存器中，等到上路的四點運算開始，第二級的移位寄存器有空白位時，移入第二級，為下路的四點運算做準備。所以第一級蝶形運算上路輸出前N／4=2個進入下一級寄存器，下路輸出的數據依次存入本級移位寄存器中。
當第一級的輸出前N／4=2個數據x0(0)+x0(4)和x0(1)+x0(5)存入第二級移位寄存器時，運算便可以開始，這時開關K2打到位置②，此 時第一級上路輸出的數據x0(2)+x0(6)，即第一級上路輸出的第三個數據與第二級移位寄存器移出的第一個數據，即x0(O)+x0(4)進行蝶形運 算，輸出的第四個數據x0(3)+x0(7)與x0(1)+x0(5)進行蝶算。在這個運算過程中，第一級的2級移位寄存器移出數據依次移位存入到第二級 的移位寄存器產生的空白位中。
兩個時鐘后，第一級上路輸出的四個數據完成了蝶形運算，K2打到位置①，在接下來的兩個時鐘里，第一級中2級移位寄存器的輸出依次與此時第二級中2級移位寄存器的輸出數據進行蝶形運算，即與
，
與
完成第一級下路輸出的四個數據的蝶形運算。
此時，第一路在第一級運算后的輸出數據，在第二級完成了全部的蝶形運算。第二級的輸出結果同第一級一樣，蝶形運算的上路輸出前N／8=1個進入下一級寄存器，后一個數據直接進入后一級進行碟算，下路輸出的數據存入本級移位寄存器中。
第三級的運算與第二級和第一級類似，即移入1級寄存器的數據與其后一個數據進行碟算，同時使前一級寄存器的輸出數據進入后一級寄存器的空白位中，然后開關打到位置②，對下路輸出數據進行碟算。
對于第二路數據，通過開關控制，在第二級中，待第一路第一級下路輸出數據進行蝶形運算時，移入寄存器的空白位，為運算做準備，由于前級運算周期是后級運周 期的兩倍，對于第二級碟算模塊而言，數據仍然是不間斷輸入的。通過這樣兩路數據的交替運算和存儲，實現“乒乓操作”，從而提高了蝶形運算模塊的運算效率。 圖4是256點FFT的具體運算輸入和輸出時序圖。對于只有一路數據的應用場合，可以在前級加入，門控開關和數據緩沖寄存器分成兩路數據，實現一路數據的 不間斷讀入。
由于采用移位寄存器結梅，各級寄存器使用的數量都是固定的，即為N／2+N／4。其中，N為該級DFT運算的點數，各級使用的移位寄存器深度逐級遞減，從而大大降低了寄存器的使用數量。
此外，由于各級結構固定，所以大點數FFT只是小點數FFT基礎上級數的增加，而且由于移位寄存器的輸出相對于RAM而言不需要復雜的地址控制，所以這種 結構的FFT處理器具有非常好的可擴展性。比如需要實現512點的FFT，只需要在256點的基礎上增加一級即可。
3 具體模塊的設計
3．1 控制與地址產生模塊
由于兩路數據同時輸入，為了防止發生兩路數據間的串擾，對數據的控制顯得極其關鍵。從上面的算法結構分析中知道，由于后級的DFT運算點數是前一級的一 半，所以后一級的開關轉換周期也是前一級的一半，基于這種關系，可以使用一個8位計數器的每一位狀態來對各級開關進行控制。最高位控制第一級，同時由于上 一級數據進入下一級需要一個時鐘，所以下一級的開關轉換時刻要比上一級延遲一個時鐘周期。
對于移位寄存器，在實現時，各級的前級移位寄存器深度為N／2-1，從本質而言，是使運算開始的時鐘上升沿到來時，數據已經出現在碟算模塊輸入線上，而不 需要下一個時鐘的驅動來移出寄存器，比如第二級移位寄存器的級數為63。這樣，運算周期正好是2的倍數，從而方便使用計數器的各位直接對開關進行控制。
同時，計數器還可以用來產生所需旋轉因子的RAM地址。根據各級蝶形運算所需旋轉因子的規律，可以利用計數器的高位補零來產生查找表的地址。比如，對于第一級，因為需要在最低位第一次出現1時提供
，第二次出現1時提供
，…，以此類推，周期為128，所以可以使用計數器的低七位作為地址。對于第二級，由于所需要的地址為偶數，可以由計數器的[6：1]和最低位置O產生。表l為8點時使用三位計數器輸出旋轉因子的地址情況。
控制和地址產生模塊的仿真結果如圖5所示，其中sel代表開關控制，addr代表產生的地址。
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算法可知，運算結果需要倒序輸出?？梢韵葘⒔Y果存儲到RAM中，然后使用O～255的二進制數倒序產生RAM讀取地址，依次將結果讀出，其中實現一個8位二進制數倒序的算法如下：
(1)將8位數字的相鄰兩位交換位置；
(2)將相鄰的兩位看作1組，相鄰兩組交換位置；
(3)將相鄰的4位看作1組，相鄰兩組交換位置。
經過這樣的交換位置后，輸出即為原來8位二進制數的倒序。
舉例對于8位二進制數10110110來說，第一次交換位置的結果是01111001，第二次交換位置的結果是11010110，最后交換位置的結果是01101101。可見正好是原來數字的倒序。
另外，由于設計的是兩路數據同時寫入，一路數據讀出，所以讀取的頻率是寫入頻率的2倍，使用PLL實現原始時鐘的二倍頻，用來讀取RAM。倒序模塊仿真結果如圖8所示。
最終生成的FFT處理器模塊圖如圖9所示。
4 仿真結果
各級間數據時序情況如圖10所示，設計的FFT處理器仿真結果如圖1l所示。采用一路階梯遞增信號和另一路：XXXX信號進行仿真，通過與Matlab計 算結果進行對比，結果基本一致，可以滿足系統要求。系統總的延時由延時最大的第一級決定，為第一級運算的延時加上倒序輸出的延時，總共是 (256+128)×clk，相對于一般流水線結構(256×讀入周期+7×128×蝶算周期+128×讀入周期)，系統延時大為減少。
通過仿真可知，系統最大頻率由蝶形運算模塊的最大工作頻率決定。使用QuartusⅡ軟件時序仿真后，得到處理器的工作頻率為72 MHz。
5 結語
通過采用移位寄存器流水線結構，可以有效地提高FFT處理器中蝶形運算單元的效率，減少寄存器的使用數量，并且簡化了地址控制，提高處理器的工作頻率，具 有良好的可擴展性，同時可以實現兩路數據的同時輸入，從而增大了一倍的數據吞吐量。對于工作頻率要求較高，數據吞吐量較大，尤其對于需要兩路數據輸入的場 合，比如兩天線的MIMO-OFDM系統，具有很大的實用價值。