正交頻分復(fù)用OFDM(Orthogonal Frequency Division Multiplex)是近幾年興起的一種在無線信道上實(shí)現(xiàn)高速數(shù)據(jù)傳輸?shù)男录夹g(shù),。它采用多載波調(diào)制技術(shù)，其最大的特點(diǎn)是傳輸速率高,，對碼間干擾和信道選擇性衰落 具有很強(qiáng)的抵抗能力,。在OFDM系統(tǒng)中，各子載波的調(diào)制解調(diào)采用一個(gè)實(shí)時(shí)的快速傅立葉變換(FFT)處理器實(shí)現(xiàn),，因此高速FFT處理器是OFDM系統(tǒng)實(shí)現(xiàn)中的一個(gè)重要因素,。目前通用的FFT模塊可以達(dá)到的速度數(shù)量級為1024點(diǎn)16位字長定點(diǎn),、塊浮點(diǎn)、浮點(diǎn)運(yùn)算在幾十到數(shù)百微秒量級^[1],，其中采用TI公司的DSP62XX定點(diǎn)系列達(dá)到66μs量級處理速度,，新近的64XX在600MHz時(shí)鐘頻率下完成1024點(diǎn)定點(diǎn)FFT的時(shí)間僅需10μs。C6701浮點(diǎn)DSP在167MHz時(shí)鐘頻率下完成32位1024點(diǎn)浮點(diǎn)FFT的運(yùn)算時(shí)間需120μs^[2],。而AD公司的ADSP-21160 SHARC在100MHz下完成需要90μs,。但是如果僅用于FFT處理而廢棄其他功能性價(jià)比就很低。采用Xilinx公司的FFT IP核處理,也可以達(dá)到160MHz的工作頻率^[3],，但由于其采用固核,，外圍引腳較多不利于使用，且不利于針對特殊要求進(jìn)行修改,。
　　本文在分析了基4按時(shí)域分解的FFT算法特點(diǎn)的基礎(chǔ)上^[4],，提出了一種便于VLSI實(shí)現(xiàn)的FFT處理器結(jié)構(gòu)。處理器運(yùn)算單元的流水并行及操作數(shù)的并行讀寫保證了每個(gè)周期能夠完成一次蝶形運(yùn)算,。而文獻(xiàn)[5～6]提出的地址映射算法不適用于本設(shè)計(jì)單蝶形運(yùn)算結(jié)構(gòu),；文獻(xiàn)^[7]中，尋址方案基于線形變換,，但是需要復(fù)雜的位矩陣點(diǎn)積算法；文獻(xiàn)^[8]方案做了改進(jìn),，但仍然較復(fù)雜,。本文提出一種完全同址的數(shù)據(jù)全并行FFT處理器設(shè)計(jì)方法。此方案僅需要一個(gè)計(jì)數(shù)器,，通過簡單的線形變換,，即可實(shí)現(xiàn)對不同長度N=4^P的FFT處理。
1 原理分析
　　設(shè)序列x(n)的長度為N=4^P,，其中p為正整數(shù),，則x(n)的DFT為：
　　
　　由上述運(yùn)算步驟可推得基4按時(shí)間抽取在第s級的蝶形運(yùn)算單元的方程為：
　　
　　其中s為基4 DIT算法流圖中蝶形運(yùn)算單元的級數(shù)；n=b₂·4^s+b₁,；s=1,2,…,，p；b₁取遍0,1,…,，4^s-1-1,；b₂取遍0,1,…，4^p-s-1,。
　　式(4)給出了DIT算法的蝶形運(yùn)算公式,，由此可以得出抽取數(shù)據(jù)的規(guī)律，同時(shí)也得到了每個(gè)數(shù)據(jù)在每級蝶形運(yùn)算中相應(yīng)的旋轉(zhuǎn)因子的值,，因此式(4)是VLSI實(shí)現(xiàn)基4 FFT算法的基礎(chǔ),。
　　FFT運(yùn)算中與旋轉(zhuǎn)因子相乘的運(yùn)算是復(fù)數(shù)乘法,。可以看出,，若采用并行處理" title="并行處理">并行處理方式在一個(gè)時(shí)鐘周期" title="時(shí)鐘周期">時(shí)鐘周期內(nèi)實(shí)現(xiàn)復(fù)乘,，需4個(gè)實(shí)數(shù)乘法器" title="乘法器">乘法器和2個(gè)實(shí)數(shù)加法器。存在如下等式：
　　
　　即可用3個(gè)實(shí)數(shù)乘法器和5個(gè)實(shí)數(shù)加法器實(shí)現(xiàn)復(fù)乘,。在VLSI的實(shí)現(xiàn)中,，陣列乘法器所占面積遠(yuǎn)大于加法器，故通常用式(5)完成復(fù)乘,。
2 FFT處理器的硬件實(shí)現(xiàn)
　　假定處理器需要做N點(diǎn)FFT變換,，則基4按時(shí)域抽取FFT運(yùn)算包括lg₄N級運(yùn)算，每一級包括N/4個(gè)基4蝶形運(yùn)算單元,。
2.1 系統(tǒng)總體結(jié)構(gòu)設(shè)計(jì)
　　FFT處理器設(shè)計(jì)中采用同址運(yùn)算有利于系統(tǒng)存儲器的片內(nèi)集成,，從而提高FFT處理器訪問存儲器的速度。對于基4 FFT處理器,，一次蝶形運(yùn)算需要讀取4個(gè)操作數(shù),。因此，如能充分利用硬件的并行特點(diǎn),，在一個(gè)周期內(nèi)并行讀取4個(gè)操作數(shù),，計(jì)算速度將是順序處理器的4倍。
　　在設(shè)計(jì)中,，使用i,、j遞增計(jì)數(shù)器(i表示需要做的級數(shù)，j表示每一級運(yùn)算所需的存儲器容量),。由數(shù)據(jù)地址產(chǎn)生單元生成數(shù)據(jù)存儲器地址B0,、B1、B2,、B3,由旋轉(zhuǎn)因子地址產(chǎn)生單元生成旋轉(zhuǎn)因子存儲器地址C0,、C1、C2,。為了在一個(gè)時(shí)鐘周期內(nèi)完成一個(gè)基4蝶形運(yùn)算,，采用了4個(gè)并行存儲器A、B,、C,、D存放FFT運(yùn)算的操作數(shù)。系統(tǒng)結(jié)構(gòu)框圖如圖1所示,。

2.2 數(shù)據(jù)及旋轉(zhuǎn)因子地址生成
　　對于N=4^P,，設(shè)待變化的原始數(shù)據(jù)是按順序輸入的，由式(4)可知完成的DFT變換結(jié)果是按兩位二進(jìn)制倒序排列的,，即若輸入序列的地址線每兩位為一組,，其序號用兩位二進(jìn)制表示為a_p-1a_p-2…a₁a₀,，則輸出結(jié)果的排序?yàn)閍₀a₁…a_p-2a_p-1。每級數(shù)據(jù)及旋轉(zhuǎn)因子抽取關(guān)系如表1所示,。數(shù)據(jù)A0,、A1、A2,、A3經(jīng)過當(dāng)前級的地址線交換器" title="交換器">交換器后得到一個(gè)蝶形運(yùn)算所對應(yīng)的4個(gè)數(shù)據(jù)的地址B0,、B1、B2,、B3,。經(jīng)過蝶形運(yùn)算后，數(shù)據(jù)重新寫回原地址,。一個(gè)基4蝶形運(yùn)算需要3個(gè)旋轉(zhuǎn)因子W1,、W2、W3,。地址B1,、B2、B3經(jīng)過旋轉(zhuǎn)因子交換器及判決交換器(如表2所示)得到相應(yīng)的旋轉(zhuǎn)因子地址C0,、C1,、C2。讀寫地址及旋轉(zhuǎn)因子地址的產(chǎn)生框圖如圖2所示,。

2.3 并行存儲結(jié)構(gòu)" title="存儲結(jié)構(gòu)">存儲結(jié)構(gòu)
　　設(shè)N=2ⁿ,，則數(shù)據(jù)地址產(chǎn)生單元的輸入數(shù)據(jù)Bk(k=0,1,2,3)可表示為：
　　B_k=b_n-1b_n-2…b₀??????????????? (6)
　　得到存儲器地址m_q及各存儲器數(shù)據(jù)地址r_q對應(yīng)關(guān)系為：
　　
　　其中，mod表示取余運(yùn)算,，⊕表示多位異或運(yùn)算,，[·]表示對其中的數(shù)據(jù)取最近的小于其的整數(shù),，gcd(·)表示其中兩個(gè)數(shù)的最大公約數(shù),。
　　筆者采用4對RAM(一個(gè)地址位對應(yīng)一個(gè)復(fù)數(shù)，實(shí)部在前,，虛部在后)來存儲蝶形運(yùn)算中的操作數(shù)out(0),、out(1)、out(2),、out(3),。如圖3所示，數(shù)據(jù)地址為B0,、B1,、B2、B3,。存儲器分類處理單元由m1m0構(gòu)成,，分別得到4個(gè)地址對應(yīng)數(shù)據(jù)所在的存儲器號,。地址交換器處理單元由r_n-3r_n-4…r₁r₀構(gòu)成，分別得到4個(gè)地址對應(yīng)數(shù)據(jù)所在存儲器中的地址信息,。處理器在每個(gè)時(shí)鐘周期從相應(yīng)的RAM中讀取數(shù)據(jù)out(0),、out(1)、out(2),、out(3)送入基4蝶形運(yùn)算單元,如圖4,。運(yùn)算結(jié)果in(0)、in(1),、in(2),、in(3)在下一個(gè)時(shí)鐘周期寫回原地址。

2.4基4蝶形單元
　　蝶形單元是FFT設(shè)計(jì)的核心部分,根據(jù)式(4),、(5)可得基4蝶形單元的結(jié)構(gòu)如圖4所示,。它采用流水線結(jié)構(gòu)^[9]，主要包括乘法器和加法器,。蝶形運(yùn)算單元可在一個(gè)時(shí)鐘周期內(nèi)完成一次蝶形運(yùn)算,。其中，4個(gè)操作數(shù)分別位于4個(gè)RAM中,，3個(gè)旋轉(zhuǎn)因子分別位于3個(gè)ROM中,。由于運(yùn)算可能產(chǎn)生溢出，所以需進(jìn)行量化^[10],。本設(shè)計(jì)在每一級蝶形運(yùn)算后采用量化右移兩位處理,。

3 硬件設(shè)計(jì)及性能分析
　　針對本文提出的結(jié)構(gòu)采用Xilinx公司的Virtex-Ⅱ系列的xc2v250器件進(jìn)行了1024點(diǎn)FFT處理器的VLSI結(jié)構(gòu)驗(yàn)證。由于此器件包含大量的18×18位硬件乘法器,、片內(nèi)可配置RAM塊以及觸發(fā)器資源,，因而便于硬件設(shè)計(jì)驗(yàn)證。輸入及輸出數(shù)據(jù)為18位,，當(dāng)系統(tǒng)的工作頻率為100MHz時(shí),，完成1024點(diǎn)復(fù)數(shù)FFT運(yùn)算所需時(shí)間將近13μs。部分仿真波形如圖5所示,。表3比較了幾種FFT處理器的性能指標(biāo),。