引言
OFDM（正交頻分復用）是一種多載波數(shù)字調(diào)制技術，被公認為是一種實現(xiàn)高速雙向無線數(shù)據(jù)通信的良好方法。在OFDM系統(tǒng)中，各子載波上數(shù)據(jù)的調(diào)制和解調(diào)是采用FFT（快速傅里葉變換）算法來實現(xiàn)的。因此在OFDM系統(tǒng)中，F(xiàn)FT的實現(xiàn)方案是一個關鍵因素。其運算精度和速度必須能夠達到系統(tǒng)指標。對于一個有512個子載波，子載波帶寬20 kHz的OFDM系統(tǒng)中，要求在50 μs內(nèi)完成512點的FFT運算。
硬件實現(xiàn)FFT算法的主要方案有：DSP（通用數(shù)字信號處理器）；FFT專用芯片；FPGA（現(xiàn)場可編程門陣列）。DSP具有純軟件實現(xiàn)的靈活性，適合用于流程復雜的算法，例如在通信系統(tǒng)中的信道編、解碼，QAM映射等算法。如果在DSP中完成FFT運算，不僅要占用大量D SP的運算時間，使整個系統(tǒng)的數(shù)據(jù)吞吐率降低，也無法發(fā)揮DSP軟件實現(xiàn)的靈活性。因此，前端的FFT運算應由ASIC或FPGA完成。采用專用的FFT處理芯片，雖然速度能達到要求，但其可擴展性差。FPGA具有硬件結(jié)構(gòu)可重構(gòu)的特點。適合于算法結(jié)構(gòu)固定、運算量大的前端數(shù)字信號處理。新近推出的FPGA產(chǎn)品都采用多層布線結(jié)構(gòu)，更低的核心電壓，更豐富的IO管腳，容量可達到100 k個邏輯單元（LES），內(nèi)置嵌入式RAM資源，內(nèi)部集成多個數(shù)字鎖相環(huán)，多個嵌入的硬件乘法器，所有這一切都使得FPGA在數(shù)字信號處理領域顯示出自己特有的優(yōu)勢。
本設計根據(jù)OFDM系統(tǒng)的實際需要，提出一種用FPGA實現(xiàn)FFT運算的方案，并以64點FFT為例，在Quartus II軟件上通過了綜合和仿真。
2方案分析
FFT是DFT（離散傅里葉變換）的快速算法。以圖1為例，N點FFT共需要log2N級運算，每級需要N/2個蝶型運算。因為系統(tǒng)中FFT運算點數(shù)為2的奇數(shù)次方，因此本設計采用的是按時間抽取的基二FFT運算。
FPGA實現(xiàn)FFT需考慮的問題有：
(1) 整體實現(xiàn)結(jié)構(gòu)的設計。
對FFT算法進行合理的模塊劃分，各個模塊在中央控制單元的管理下并行工作，實現(xiàn)框圖如圖2所示。 
(2) 數(shù)據(jù)格式和長度的選擇
通常的數(shù)據(jù)表示方法有3種：浮點，定點和塊浮點。浮點數(shù)用2組固定的bit來表示指數(shù)和小數(shù)，動態(tài)范圍大。只要表示指數(shù)的位數(shù)足夠多，浮點運算就不會發(fā)生溢出現(xiàn)象。但是完成浮點運算所需要的電路復雜，運算速度慢。定點數(shù)小數(shù)點位置固定，用固定的bit來表示整數(shù)和小數(shù)部分。定點數(shù)動態(tài)范圍小，容易溢出。但是其運算電路簡單、速度快。塊浮點介于浮點和定點之間。在FFT運算過程中，逐級進行溢出判斷和移位選擇，實現(xiàn)動態(tài)范圍擴展。
本方案采用塊浮點運算。即小數(shù)點的位置隨中間運算結(jié)果動態(tài)范圍的增大而右移。入口基帶 數(shù)據(jù)為10 b補碼格式。FFT運算結(jié)果輸出2路10 b。實部、虛部各一路，補碼表示。由于入口數(shù)據(jù)精度的限制，旋轉(zhuǎn)因子的實部、虛部取和輸入數(shù)據(jù)同樣的量化位數(shù)［3］。
(3) 地址生成單元的設計
在FFT中，輸入數(shù)據(jù)和旋轉(zhuǎn)因子的尋址是設計中最靈活的部分。一種容易想到的實現(xiàn)方案是 利用RAM為每級蝶型運算生成地址查找表，蝶型運算序數(shù)作為查找表地址，讀出的內(nèi)容為輸入數(shù)據(jù)和旋轉(zhuǎn)因子地址。優(yōu)點是地址生成速度快，缺點是消耗大量的片上RAM資源。N點FFT需要log2N b表示地址。N/2個旋轉(zhuǎn)因子用log2(N/2) b表示地址。每級地址查找表都需要(N·log2N+N/2·log(N/2)) b。
本文設計的一種地址生成邏輯，采用流水線結(jié)構(gòu)，通過簡單的移位和加法運算，延遲4個時鐘得到數(shù)據(jù)地址，并對原理進行了詳細的闡述。 3實現(xiàn)技術
整體設計分為數(shù)據(jù)接收部分和FFT運算部分。數(shù)據(jù)接收部分工作在頻率低的clk_data。其他邏輯工作在頻率高的clk_fast。兩個時鐘通過雙口的接收RAM進行銜接。
3.1數(shù)據(jù)接收單元
數(shù)據(jù)接收單元將每幀數(shù)據(jù)按碼位倒置的順序乒乓存入接收RAM1或接收RAM2。數(shù)據(jù)接收模塊 有2 b的標志信息通知給中心控制單元。中心控制單元根據(jù)標志位，交替的對接收RAM中的數(shù)據(jù)進行處理。當中央控制單元將接收RAM中的數(shù)據(jù)取出，經(jīng)過蝶型運算，結(jié)果存入運算RAM1的同時，上一幀數(shù)據(jù)的FFT運算結(jié)果從運算RAM2取出。
為了實現(xiàn)乒乓操作，接收RAM共有2塊，用FPGA的片上RAM實現(xiàn)，為Simple DualPort模式。讀、寫端口分別有自己獨立的數(shù)據(jù)總線、地址總線和工作時鐘。數(shù)據(jù)接收單元控制寫端口，中心控制單元控制讀端口。
3.2運算單元
運算單元由蝶型運算器和運算RAM組成。
蝶型運算器完成對輸入數(shù)據(jù)A，B的蝶型運算。設輸
 從上兩式可以看出共有2個乘累加項(bpWp-bqWq)和(bpWq+bqWp)。蝶型運算的各個模塊都利用QuartusII開發(fā)軟件中所提供的宏單元生成。整個蝶型運算為同步邏輯，共需要4個時鐘周期。輸入數(shù)據(jù)A，B為10 b，因此乘累加運算單元輸出為20 b，才能保證不溢出。乘累加運算單元輸出結(jié)果，截斷低8位（蝶型運算因子低8位為小數(shù)），保留整數(shù)部分輸入到加法器、減法器。同時為了使數(shù)據(jù)同步，數(shù)據(jù)通過寄存器組延遲3個時鐘。同時符號擴展2位，與乘累加單元輸出結(jié)果對齊。
從以上描述和FFT算法的分析［2］表明：每級FFT運算結(jié)果的動態(tài)范圍最多需要擴展2 b。因此中間運算結(jié)果的位寬應為24 b，實部、虛部各12 b。在進行下一級蝶型運算時，12 b數(shù)據(jù)被取出。按照塊浮點單元記錄的動態(tài)范圍擴展bit數(shù)，完成定標。截取其中的10 b送入蝶型運算器。 
運算RAM1和運算RAM2作為FFT的中間的數(shù)據(jù)緩存。兩塊RAM交替作為數(shù)據(jù)讀出和運算結(jié)果寫入 單元。直到第6級蝶型運算完成。運算RAM采用True DualPort Memory模式。每一側(cè)的端口均可在獨立的工作時鐘下完成隨機地址數(shù)據(jù)的讀或者寫操作。即可以同時將蝶型運算所需要的兩個入口數(shù)據(jù)讀出，也可以同時將兩個運算結(jié)果寫入。比單口RAM減小了一半的讀寫周期。
3.3旋轉(zhuǎn)因子查找表
旋轉(zhuǎn)因子查找表，存儲FFT運算所需要的旋轉(zhuǎn)因子
 3.4地址產(chǎn)生單元
地址產(chǎn)生單元產(chǎn)生每一級蝶型運算所需的兩個輸入數(shù)據(jù)和旋轉(zhuǎn)因子的地址。從圖1可以看到，該FFT實現(xiàn)結(jié)構(gòu)為原位運算。蝶型運算的結(jié)果仍然寫回輸入數(shù)據(jù)讀出地址。因此需將讀數(shù)據(jù)地址延遲若干時鐘周期，作為運算結(jié)果寫入地址。
對于N點FFT運算，設m∈(0…log2N-1)，n∈(0…N/2-1)表示第m級的第n個蝶型運算。addr_A，addr_B，(addr_A<addr_B)分別表示兩個入口數(shù)據(jù)的地址。觀察地址生成規(guī)律：每一級蝶型運算可分為若干組(0…N/2/2m- 1)，每組2m個蝶型運算，兩個入口數(shù)據(jù)共占用2m+1個地址。
 則m級的第n個蝶型運算的位置為第n/2m組的第n%2m個。因此：
 (n/2m)*2m+1操作可描述為將n的低m位清零，再左移1位。n%2m描述為取n的低m b位。為了獲得更高頻率的工作時鐘，將該運算拆分為較小的邏輯單元，分為4個節(jié)拍流水輸出。 
N點FFT共需要旋轉(zhuǎn)因子N/2個， r=(0…N/2-1)。設addr_w為當前蝶型運算所對應的旋轉(zhuǎn)因子查找表入口地址。從時間抽取FFT算法的推導過程［2］可知第m級蝶型運算所需旋轉(zhuǎn)因子的排列規(guī)律。即在0~N/2-1的數(shù)中，可以被2整除的數(shù)，按從小到大的順序重復排列，規(guī)則為：
 需要移位和求余兩種簡單的運算。
在圖1的8點FFT中，第1級 而在0~3中間可以被2整除的數(shù)為0和2。因此4個旋轉(zhuǎn)因子地址為(0,2,0,2)，進而又可以表示為(0×2)%4,(1×2)%4,(2×2)%4,(3×2)%4。64點FFT旋轉(zhuǎn)因子有32個，共需要5 b表示地址。第m級，第n個蝶型運算的WrN地址可由邏輯移位的方法快速得到。將n(5b)左移位(5-m)，低位補0，就得到了在(0…31)中的addr_w。
地址產(chǎn)生單元框圖見圖5。m，n作為輸入，4個時鐘周期后產(chǎn)生所需要的地址。 
3.5塊浮點單元
每級蝶型運算結(jié)果動態(tài)范圍最大需要擴展2 b。塊浮點單元對蝶型運算結(jié)果的高3位進行檢測，判斷當前結(jié)果動態(tài)范圍擴展bit數(shù)，記錄當前級的最大擴展bit數(shù)。下一級蝶型運算時，根據(jù)前一級的最大擴展bit數(shù)，對讀出的數(shù)據(jù)進行定標，選取數(shù)據(jù)送入蝶型運算器。塊浮點單元將每一級運算結(jié)果動態(tài)范圍擴展bit數(shù)進行累加，和FFT運算結(jié)果一同輸出。
3.6中央控制單元
中央控制單元為整個系統(tǒng)的控制核心。功能模塊之間的數(shù)據(jù)傳遞均通過中央控制單元。中央 控制單元記錄當前蝶型運算所處的級數(shù)和個數(shù)，傳遞給地址產(chǎn)生單元。地址產(chǎn)生單元在經(jīng)過4個時鐘后產(chǎn)生數(shù)據(jù)和旋轉(zhuǎn)因子的地址。中央控制單元讀取地址，向處于伺服狀態(tài)的運算RAM和旋轉(zhuǎn)因子查找表發(fā)出讀使能請求。2個時鐘延遲以后，數(shù)據(jù)和旋轉(zhuǎn)因子被讀出。讀出的數(shù)據(jù)進行必要的延遲和定標處理，送給蝶型運算器。4個時鐘延遲后，運算結(jié)果將被連續(xù)算出并寫入RAM。設計中共用了2個時鐘。 4驗證與仿真
采用自頂向下的設計思路，完成系統(tǒng)設計和各個功能模塊的VHDL代碼編寫。使用Quartus II 針對EP1C6F256完成了綜合和仿真，占用30%的邏輯單元和90%的片上RAM。clk_fast最快87.23 MHz。第一級蝶型運算需要75個時鐘，以后各級需要45個時鐘，完成64點FFT共需要300個時鐘共3.4μs。完成512點FFT，需要2 691個時鐘共33.63 μs，OFDM符號速率可以達到29 kS/s。 5結(jié)語
本設計的主要特點有：
(1) 采用pipleline流水結(jié)構(gòu)，各個單元協(xié)調(diào)同步工作。若FFT點數(shù)增大，流水線初始化時鐘開銷比率將顯著降低。
(2) 使用了2塊雙口RAM作為中間結(jié)果存儲器，1個時鐘可以同時讀出或者寫入2個操作數(shù)。減少了訪問存儲器的時鐘消耗。
(3) 塊浮點單元的使用，定點數(shù)動態(tài)范圍根據(jù)實際運算結(jié)果進行擴大，在實現(xiàn)復雜度，運算速度與運算精度方面得到了折衷。
(4) 簡易快捷的地址生成邏輯。
(5) 模塊化設計。設計中的各個邏輯單元功能單一，具有通用性，可以方便地擴展為更多點數(shù)的FFT處理模塊。也可以將log2N個該FFT單元進行極連，在同等時延下，可使數(shù)據(jù)吞吐率擴大log2N倍。又由于FFT和IFFT運算的對偶性：
 可以在FFT運算單元的數(shù)據(jù)入口和數(shù)據(jù)出口處添加取共軛邏輯來實現(xiàn)IFFT運算。
本設計提出了一種用FPGA完成FFT運算的方案，其運算結(jié)果經(jīng)過驗證達到設計要求。為以后使用FPGA完成OFDM實時通信系統(tǒng)中的調(diào)制和解調(diào)打下了基礎，也是使用FPGA完成DSP運算的一次有益嘗試。 參考文獻 ［1］褚振勇，翁木云.FPGA設計及應用［M］.西安：西安電子科技大學 出版社，2002.
［2］Alan V Oppenheim，Ronald W Schafer，John R Buck.離散時間信號處理［M］.第2版.劉樹棠，黃建國譯.西安：西安交通大學出版社，2001.
［3］FFT MegaCore Function User Guidehttp://www.altera.com.
［4］韓穎，王旭，吳嗣亮.FPGA實現(xiàn)高速FFT處理器的設計［J］.電訊技術，2003，(2). |
66821730(技術支持)
