摘 要： 在OFDM系統的實現中，高速FFT處理器是關鍵。在分析了基4按時域抽取快速傅立葉變換(FFT)算法特點的基礎上，研究了一種高性能FFT處理器的硬件結構。此結構能同時從四個并行存儲器中讀取蝶形運算所需的4個操作數，極大地提高了處理速度。此結構控制單元簡單，便于模塊化設計。經硬件驗證，達到設計要求。在系統時鐘為100MHz時，1024點18位復數FFT的計算時間為13μs。
關鍵詞： FFT 蝶形單元 塊浮點 流水線
正交頻分復用OFDM(Orthogonal Frequency Division Multiplex)是近幾年興起的一種在無線信道上實現高速數據傳輸的新技術。它采用多載波調制技術，其最大的特點是傳輸速率高，對碼間干擾和信道選擇性衰落 具有很強的抵抗能力。在OFDM系統中，各子載波的調制解調采用一個實時的快速傅立葉變換(FFT)處理器實現，因此高速FFT處理器是OFDM系統實現中的一個重要因素。目前通用的FFT模塊可以達到的速度數量級為1024點16位字長定點、塊浮點、浮點運算在幾十到數百微秒量級[1]，其中采用TI公司的DSP62XX定點系列達到66μs量級處理速度，新近的64XX在600MHz時鐘頻率下完成1024點定點FFT的時間僅需10μs。C6701浮點DSP在167MHz時鐘頻率下完成32位1024點浮點FFT的運算時間需120μs[2]。而AD公司的ADSP-21160 SHARC在100MHz下完成需要90μs。但是如果僅用于FFT處理而廢棄其他功能性價比就很低。采用Xilinx公司的FFT IP核處理,也可以達到160MHz的工作頻率[3]，但由于其采用固核，外圍引腳較多不利于使用，且不利于針對特殊要求進行修改。
本文在分析了基4按時域分解的FFT算法特點的基礎上[4]，提出了一種便于VLSI實現的FFT處理器結構。處理器運算單元的流水并行及操作數的并行讀寫保證了每個周期能夠完成一次蝶形運算。而文獻[5～6]提出的地址映射算法不適用于本設計單蝶形運算結構；文獻[7]中，尋址方案基于線形變換，但是需要復雜的位矩陣點積算法；文獻[8]方案做了改進，但仍然較復雜。本文提出一種完全同址的數據全并行FFT處理器設計方法。此方案僅需要一個計數器，通過簡單的線形變換，即可實現對不同長度N=4P的FFT處理。
1 原理分析
設序列x(n)的長度為N=4P，其中p為正整數，則x(n)的DFT為：
由上述運算步驟可推得基4按時間抽取在第s級的蝶形運算單元的方程為：
其中s為基4 DIT算法流圖中蝶形運算單元的級數；n=b2·4s+b1；s=1,2,…，p；b1取遍0,1,…，4s-1-1；b2取遍0,1,…，4p-s-1。
式(4)給出了DIT算法的蝶形運算公式，由此可以得出抽取數據的規律，同時也得到了每個數據在每級蝶形運算中相應的旋轉因子的值，因此式(4)是VLSI實現基4 FFT算法的基礎。
FFT運算中與旋轉因子相乘的運算是復數乘法。可以看出，若采用并行處理" title="并行處理">并行處理方式在一個時鐘周期" title="時鐘周期">時鐘周期內實現復乘，需4個實數乘法器" title="乘法器">乘法器和2個實數加法器。存在如下等式：
即可用3個實數乘法器和5個實數加法器實現復乘。在VLSI的實現中，陣列乘法器所占面積遠大于加法器，故通常用式(5)完成復乘。
2 FFT處理器的硬件實現
假定處理器需要做N點FFT變換，則基4按時域抽取FFT運算包括lg4N級運算，每一級包括N/4個基4蝶形運算單元。
2.1 系統總體結構設計
FFT處理器設計中采用同址運算有利于系統存儲器的片內集成，從而提高FFT處理器訪問存儲器的速度。對于基4 FFT處理器，一次蝶形運算需要讀取4個操作數。因此，如能充分利用硬件的并行特點，在一個周期內并行讀取4個操作數，計算速度將是順序處理器的4倍。
在設計中，使用i、j遞增計數器(i表示需要做的級數，j表示每一級運算所需的存儲器容量)。由數據地址產生單元生成數據存儲器地址B0、B1、B2、B3,由旋轉因子地址產生單元生成旋轉因子存儲器地址C0、C1、C2。為了在一個時鐘周期內完成一個基4蝶形運算，采用了4個并行存儲器A、B、C、D存放FFT運算的操作數。系統結構框圖如圖1所示。
2.2 數據及旋轉因子地址生成
對于N=4P，設待變化的原始數據是按順序輸入的，由式(4)可知完成的DFT變換結果是按兩位二進制倒序排列的，即若輸入序列的地址線每兩位為一組，其序號用兩位二進制表示為ap-1ap-2…a1a0，則輸出結果的排序為a0a1…ap-2ap-1。每級數據及旋轉因子抽取關系如表1所示。數據A0、A1、A2、A3經過當前級的地址線交換器" title="交換器">交換器后得到一個蝶形運算所對應的4個數據的地址B0、B1、B2、B3。經過蝶形運算后，數據重新寫回原地址。一個基4蝶形運算需要3個旋轉因子W1、W2、W3。地址B1、B2、B3經過旋轉因子交換器及判決交換器(如表2所示)得到相應的旋轉因子地址C0、C1、C2。讀寫地址及旋轉因子地址的產生框圖如圖2所示。
2.3 并行存儲結構" title="存儲結構">存儲結構
設N=2n，則數據地址產生單元的輸入數據Bk(k=0,1,2,3)可表示為：
Bk=bn-1bn-2…b0??????????????? (6)
得到存儲器地址mq及各存儲器數據地址rq對應關系為：
其中，mod表示取余運算，⊕表示多位異或運算，[·]表示對其中的數據取最近的小于其的整數，gcd(·)表示其中兩個數的最大公約數。
筆者采用4對RAM(一個地址位對應一個復數，實部在前，虛部在后)來存儲蝶形運算中的操作數out(0)、out(1)、out(2)、out(3)。如圖3所示，數據地址為B0、B1、B2、B3。存儲器分類處理單元由m1m0構成，分別得到4個地址對應數據所在的存儲器號。地址交換器處理單元由rn-3rn-4…r1r0構成，分別得到4個地址對應數據所在存儲器中的地址信息。處理器在每個時鐘周期從相應的RAM中讀取數據out(0)、out(1)、out(2)、out(3)送入基4蝶形運算單元,如圖4。運算結果in(0)、in(1)、in(2)、in(3)在下一個時鐘周期寫回原地址。
2.4基4蝶形單元
蝶形單元是FFT設計的核心部分,根據式(4)、(5)可得基4蝶形單元的結構如圖4所示。它采用流水線結構[9]，主要包括乘法器和加法器。蝶形運算單元可在一個時鐘周期內完成一次蝶形運算。其中，4個操作數分別位于4個RAM中，3個旋轉因子分別位于3個ROM中。由于運算可能產生溢出，所以需進行量化[10]。本設計在每一級蝶形運算后采用量化右移兩位處理。
3 硬件設計及性能分析
針對本文提出的結構采用Xilinx公司的Virtex-Ⅱ系列的xc2v250器件進行了1024點FFT處理器的VLSI結構驗證。由于此器件包含大量的18×18位硬件乘法器、片內可配置RAM塊以及觸發器資源，因而便于硬件設計驗證。輸入及輸出數據為18位，當系統的工作頻率為100MHz時，完成1024點復數FFT運算所需時間將近13μs。部分仿真波形如圖5所示。表3比較了幾種FFT處理器的性能指標。
比較表明，本文提出的基4并行存儲結構控制部件簡單，地址生成速度快，數據訪問并行處理解決了順序訪問的瓶頸問題。對于各種形如N=4P的FFT運算能夠達到極高的處理性能。
OFDM作為一種可以有效對抗信號波形間干擾的高速傳輸技術，引起了廣泛的關注。人們開始集中越來越多的精力開發OFDM技術在移動通信領域的應用，預計第三代以后的移動通信的主流技術將是OFDM技術。OFDM技術中各載波調制解調器的實現需要高速的FFT處理器。本文在分析了基4按時域抽取FFT算法特點的基礎上，提出了一種高性能的FFT處理器實現結構。利用硬件并行無沖突的方法來訪問數據存儲器，與以往的設計相比大大提高了處理器的處理效率。同時系統結構規則，便于模塊化，易于版圖設計[11]。經由硬件驗證，系統性能完全可以滿足OFDM對高速數據流的處理需求。
參考文獻
1 http://nova.stanford.edu/~bbass/fftinfor.htm
2 http://dspvillage.ti.com/docs/catalog/dspdetails/dspplatfor-mdetails.jhtm
3 http://www.xilinx.com/ipcenter
4 劉朝輝，韓月秋.用FPGA實現FFT的研究. 北京理工大學學報，1999;19(2)
5 D Cohen.Simplified control of FFT hardware.IEEE Trans on Acoustics,Speech, Signal Processing,1976;24(12)
6 馬余泰.FFT處理器無沖突地址生成方法.計算機學報,1995；18(11)
7 A.Norton， E.Melton.A classof Boolean linear transformations for conflict-free power-of_two stride access.in Proc.Int.Conf.Parallel Processing,St.Charles, IL,USA. 1987
8 D.T.Harper.Block,multistride vector,and FFT accesses in parallel memory systems. IEEE Trans.Paralel and Distrib.Syst.,1991；2(1)
9 Ayman M.El-Khashab.A Module Pipelined Implementa-tion of Large Fast Fourier Trasforms.IEEE Transaction on Signal Processing,2002；(39)
10 Knight W R,Kaiser R. A simple fixed-point error bound for the fast Fourier transform[J].IEEE Trans Acous-tics,Speech and Signal Proc,1979；27(6)
11 馬維楨.快速傅立葉變化的發展現狀.華南理工大學學報，1995；5