基于FPGA的新型高速FFT算法研究與實(shí)現(xiàn)_圖文

1、第 31卷 第 4期2008年 8月電 子 器 件Chinese J ournal Of Elect ron DevicesVol. 31 No. 4Aug. 2008R esearch and Implementation of a Novel F ast FFT Algorithm B ased on FPGAGU Yan 2li3, Z HOU Hon g 2mi n(College of optoelect ronic engineering , N anj i ng Uni versit y of posts and telecommunications , N anj ing 21

2、0003, China Abstract :A novel radix 28/4FF T algorit hm and architect ure are introduced , fast p rocessor is designed. The design can realize 8k 、 4k or 2k point alternatively ; obtain significant hardware reduction by multipliers multiplexing ; increase t he continuous comp uting capability of t h

3、e butterfly core by using a symmetry ping 2pang RAM st ruct ure. The module is described wit h Verilog HDL ,and performed wit h translated synt he 2sized , routed in t he Quart us5. 0software. The result shows t hat t he algorit hm architect ure has achieved t he expected p urpo se bot h on precisio

4、n and speed , and can meet t he demand of reality needs. K ey w ords :novel and fast FF T ;ping 2pang RAM ;butterfly p rocessing ;verilog EEACC :6140基于 FPGA 的新型高速 FFT 顧艷麗 3(, 收稿日期 :2007210216作者簡(jiǎn)介 :顧艷麗 (19812 , 女 , 碩士研究生 , 助教 , 從事電子電路教學(xué)工作 ,nlggyl 163. com摘 要 :, 設(shè)計(jì)出高速的處理模塊 。該設(shè)計(jì)可選擇性地實(shí)現(xiàn) 8k 、 4k 及 2k 點(diǎn)FF

5、T ; , ; 應(yīng)用對(duì)稱(chēng)乒乓 RAM 結(jié)構(gòu)提高了蝶型運(yùn)算單元的連續(xù)運(yùn)算能力 。 模塊利用 Ver 2ilog 語(yǔ)言進(jìn)行描述 , 在 Quartus5. 0軟件環(huán)境中完成輸入 、 綜合及布局布線 。 結(jié)果表明本文提出的算法結(jié)構(gòu)具有優(yōu)越的精度和速度 , 充分能夠滿(mǎn)足實(shí)際應(yīng)用要求 。關(guān)鍵詞 :新型高速 FFT ; 乒乓 RAM ; 蝶型運(yùn)算 ;Verilog 中圖分類(lèi)號(hào) :TN911. 23 文獻(xiàn)標(biāo)識(shí)碼 :A 文章編號(hào) :100529490(2008 0421249203 快速傅立葉變換 (FF T 不是一種新的變換 , 是 離散傅立葉變換 (DF T 的一種快速算法 , 是描述離 散信號(hào)時(shí)域和頻域

6、關(guān)系的重要數(shù)學(xué)工具 , 在圖像處 理和數(shù)字信號(hào)處理方面得到廣泛的應(yīng)用 。 FF T 算 法可以采用軟件 、 DSP 、 專(zhuān)用 FF T 處理芯片或 FP 2GA 等來(lái)實(shí)現(xiàn) 。 軟件和 DSP 實(shí)現(xiàn)的速度較慢 ; 專(zhuān)用處理芯片速度雖快 , 但價(jià)格高 、 不易擴(kuò)展 ; 而 FP GA 資源豐富 , 組織結(jié)構(gòu)便于采用流水線結(jié)構(gòu)和并行運(yùn) 算 , 這樣不僅速度快 、 擴(kuò)展能力強(qiáng) , 而且增加設(shè)計(jì)靈 活性 、 節(jié)約開(kāi)發(fā)成本 。文中提出一種新型基 8/4算法結(jié)構(gòu) , 能實(shí)現(xiàn) 8k 、 4k 、 2k 點(diǎn) FF T 。 設(shè)計(jì)中采用單個(gè)基 8蝶形運(yùn)算單元順序處理 ; 通過(guò)乘法器復(fù)用 , 有效平衡處理速度 與資源

7、消耗之間的矛盾 ; 同時(shí)采用防溢出機(jī)制和對(duì)稱(chēng)乒乓 RAM 結(jié)構(gòu) , 提高運(yùn)算精度及連續(xù)運(yùn)算能 力 。 該結(jié)構(gòu)利于擴(kuò)展 , 可廣泛應(yīng)用于各種系統(tǒng)中 , 如 DVB 、 圖象處理系統(tǒng)等 。1 FFT 算法基本原理對(duì)于 N 點(diǎn) 序 列 x (n , 其 離 散 傅 立 葉 變 換(DF T 變換可寫(xiě)為 :X (k = N -1n =0x (n WnkN 0n N -1其中 :W =e -j2/N 。分析可知 , 直接計(jì)算 DF T , 乘法和加法次數(shù)都 和 N 2成正比 , 當(dāng) N 很大時(shí) , 運(yùn)算量是很可觀的 。 若 利用旋轉(zhuǎn)因子的對(duì)稱(chēng)性 、 周期性和可約性 , 將 DF T 逐次分解成幾個(gè)較短序

8、列的 DF T ,可使計(jì)算量大 大降低 。 快速傅立葉變換算法正是基于這樣的基本 思路發(fā)展起來(lái)的 1。2 FFT 的實(shí)現(xiàn)結(jié)構(gòu)FF T 的設(shè)計(jì)結(jié)構(gòu)框圖如圖 1所示 , 結(jié)構(gòu)中包含控制模塊 、 旋轉(zhuǎn)因子 ROM 、 8k 數(shù)據(jù)存儲(chǔ) RAM 、 輸 入緩沖 (實(shí)際結(jié)構(gòu)中是將一個(gè) 8kRAM 分成 4個(gè) 2kRAM 并行使用 、 基 8/4運(yùn)算模塊 、 限制模塊 223。 設(shè)計(jì)中 FF T 的精度取 10位有符號(hào)數(shù) 。圖 1 FF T 實(shí)現(xiàn)框圖2. 1 基 8/4運(yùn)算模塊基 8/4分 , 理器的性能 ?；?8+基 4” 模塊 (如圖 24復(fù)用蝶型運(yùn)算模塊 , 兩模塊分別運(yùn)算之后共用一個(gè)限制模塊 , 進(jìn)

9、行數(shù)據(jù)溢出檢測(cè)和溢出處理 。圖 2 基 8FFT 基本運(yùn)算的信號(hào)流圖2. 2 復(fù)乘法器實(shí)現(xiàn)復(fù)乘法是設(shè)計(jì)中關(guān)鍵模塊均要用的一種運(yùn)算 。 復(fù)乘包含實(shí)加和實(shí)乘兩種運(yùn)算 , 當(dāng)參與運(yùn)算數(shù)據(jù)位數(shù)較多時(shí) , 加法較乘法所占資源比例是相當(dāng)小的 。 為此改進(jìn)復(fù)乘算法 , 減少實(shí)數(shù)乘法次數(shù)可以節(jié)省大 量硬件資源 。這里的復(fù)乘一般是指一個(gè)復(fù)數(shù) x r +j x i 和旋轉(zhuǎn)因子 W =-j2/N=co s A -jsin A 相乘 , 結(jié)果仍為復(fù)數(shù) y r +j y i =(x r cos A -x i sin A +j (x i co sA +x r sin A , 可見(jiàn)完成一次復(fù)乘要進(jìn)行 4次實(shí)乘和 2次實(shí)加運(yùn)

10、算 。 為減少乘法次數(shù) , 將 y r +j y i 做以下變換 :y r =(x r +x i co s A -x i (sin A +co s A , y i =(x r +x i cos A +x r (sin A -cos A , 從而完成一次復(fù)乘則只需進(jìn)行 3次實(shí)乘和 5次實(shí)加 , 較變換前減 少一次實(shí)數(shù)乘法運(yùn)算 , 減少了使用面積 。2. 3 RAM 和 R OM 的地址產(chǎn)生規(guī)律RAM 采用對(duì)稱(chēng)乒乓結(jié)構(gòu) , 蝶型運(yùn)算開(kāi)始時(shí)使用 8kRAM 1、 8kRAM 2作為乒乓結(jié)構(gòu)即可實(shí)現(xiàn) 。 根據(jù)產(chǎn)生的 RAM 讀地址 , 并行的從 4個(gè) 2kRAM 中分別讀取 8個(gè)數(shù)據(jù) , 每隔 2個(gè)時(shí)

11、鐘分時(shí)送入基 8/4蝶算單元進(jìn)行運(yùn)算 , 隔 8個(gè)時(shí)鐘后得到 64個(gè)結(jié)果 , 再根據(jù)產(chǎn)生的 RAM 寫(xiě)地址寫(xiě)入 8kRAM 2, 然后 8kRAM 1和 8kRAM 2交換功能 。對(duì)于 4k 點(diǎn) , 要進(jìn)行 64次完成一級(jí)基 8/4蝶形運(yùn)算 , 因此經(jīng)過(guò) 4級(jí) 8/4蝶算后 ,8kRAM 1中為輸出結(jié)果 , 此時(shí)將輸入緩存和 8kRAM 2作為乒乓結(jié)構(gòu)實(shí)現(xiàn)蝶型運(yùn)算 。這 樣就保持了數(shù)據(jù)輸入和運(yùn)算的連續(xù)性 , 加快了處理 速度 。本設(shè)計(jì)可以有選擇的實(shí)現(xiàn) 8、 4k 、 2k 點(diǎn)的 FF , 中并行使、 余弦0, 2周期內(nèi)的正 、 余 1/4周期內(nèi)旋轉(zhuǎn)因子變換得到 , 所以 可只存 儲(chǔ) 2k 旋轉(zhuǎn)

12、 因子 。下 面 具 體 討 論 RAM 、ROM 的數(shù)據(jù)存儲(chǔ)規(guī)律 2,425。 2. 3. 1 抽取數(shù)據(jù)規(guī)律本文采用以基 8/4為基本單元的混合基順序處 理算法 , 選擇性的實(shí)現(xiàn) 8k 、 4k 或 2k 點(diǎn) FF T 。根 據(jù) FF T 算法分解過(guò)程 , 具體的基數(shù)劃分如表 1。如 要實(shí)現(xiàn) N =8192=4×4×8×8×8點(diǎn)的 FF T , 需要 進(jìn)行 2次基 4運(yùn)算 , 再進(jìn)行 3次基 8運(yùn)算 。表 1 FFT 基數(shù)劃分選擇性radixtemp remain 8k 4×4×8×8×81×4

13、5;16×128×10242048×512×64×8×14k 8×8×8×81×8×64×512512×64×8×12k4×8×8×81×4×32×256512×64×8×1 Radix :每級(jí)的實(shí)際基數(shù) 。 判斷調(diào)用何模塊進(jìn)行 FF T ; 抽取旋轉(zhuǎn)因子的個(gè)數(shù) ; 第一級(jí)不乘旋轉(zhuǎn)因子 。Temp :為 1時(shí)不抽取旋轉(zhuǎn)因子 ; 每個(gè)蝶型單元的結(jié)點(diǎn)間距 ;te

14、mp 3radix 的結(jié)果為蝶型單元間距 ;做每級(jí) FF T 時(shí) , 旋轉(zhuǎn)因子變化的次數(shù) 。Remain :相同的旋轉(zhuǎn)因子中蝶型運(yùn)算的次數(shù) 。 2. 3. 2 抽取旋轉(zhuǎn)因子舉例說(shuō)明 :進(jìn)行 2k 2FF T 的第 2級(jí)時(shí) , 最后 8位 數(shù)的旋轉(zhuǎn)因子為 , 見(jiàn)表 2。0521電 子 器 件 第 31 卷表 2 2k 2FFT 的第 2級(jí)最后 8位數(shù)的旋轉(zhuǎn)因子 RAM 地址 cos sin2019 1. 000000 0. 000000 2023 0. 831470-0. 555570 2027 0. 382683-0. 923880 2031-0. 195090-0. 980785 2035-

15、0. 707107-0. 707107 2039-0. 980785-0. 195090 2043-0. 923880 0. 382683 2047-0. 555570 0. 831470 利用算法得出表 2中旋轉(zhuǎn)因子的地址位置分別 為 (暫不考慮符號(hào)和第一個(gè)旋轉(zhuǎn)因子 :768,1536, 1792,1024,256,512,1280。 設(shè) a =768, 則其它數(shù)分別 為 :2×a ,4096-3×a ,4096-4×a ,4096-5×a , 6×a -4096,7×a -4096。 若用 13bit 二進(jìn)制數(shù)表 示七個(gè)地址數(shù) ,

16、 則如表 3中 b12b0一欄所示。 若高 兩位 (b12,b11 =00或 10時(shí) , 取低 11位的原碼輸出 , 當(dāng) (b12,b11 =01或 11時(shí) , 取低 11位的補(bǔ)碼輸出 , 此 時(shí)發(fā)現(xiàn)換算后的 13位二進(jìn)制數(shù)如表 3中乘值一欄所 示。 若仍設(shè) a =768, 則乘值一欄的十進(jìn)制值可表示 為 :a, 2×a, 3×a, 4×a, 5×a, 6×a, 7×a 。表 3 FFTa 值 由于 ROM 存取地址為 02047, 所以乘值一列 中所有數(shù)均需 -1。2. 3. 3 旋轉(zhuǎn)因子的取值象限表 3中的 (b12,b11 兩位

17、除了上面所說(shuō)作用以 外 , 其四種取值情況還可以用來(lái)定義旋轉(zhuǎn)因子的各 種象限關(guān)系 , 如表 4。 當(dāng) (b12,b11 =0011時(shí) , 分 別對(duì)應(yīng)為第一到第四象限 。表 4 旋轉(zhuǎn)因子各象限取值關(guān)系(b12,b11 00011011象 限 cos -cos -cos cos sin sin -sin -sin2. 4 溢出處理對(duì)于 FF T 的每級(jí)運(yùn)算結(jié)果都可能存在溢出的 問(wèn)題 , 但是溢出的數(shù)據(jù)較少 。對(duì)于一次基 8的運(yùn)算 來(lái)說(shuō) , 若截掉低 3位 , 即可防止溢出 , 但這樣對(duì)沒(méi)有 溢出的數(shù)據(jù)同樣進(jìn)行了截位 , 大大降低了精度 。根據(jù)運(yùn)算規(guī)律 , 文中采用一個(gè)限制模塊來(lái)防溢出。 因取 FF

18、T 的精度為 10位有符號(hào)數(shù) , 故數(shù)據(jù)范圍為 -512511。 每一級(jí)運(yùn)算后保留數(shù)據(jù)的 b 11b 1位 (相當(dāng) 于除以 2 。 此時(shí)數(shù)據(jù)中超過(guò)范圍的按就近原則處理 , 即小于 -512的數(shù)都取 -512, 大于 511的數(shù)都取 511; 范圍之內(nèi)的數(shù)取 b 10b 1位。 這樣經(jīng)過(guò)幾級(jí)運(yùn)算 , 只對(duì) 少部分有溢出的數(shù)據(jù)進(jìn)行了處理 , 大部分無(wú)溢出的數(shù) 據(jù)進(jìn)入運(yùn)算 , 大大提高了精度。 每一級(jí)運(yùn)算后的截位 范圍可以根據(jù)原始數(shù)據(jù)進(jìn)行調(diào)整 , 如原始數(shù)據(jù)較大 , 可 取 b12b2位 (相當(dāng)于除以 4 。3 性能分析本文提出了新型高速 FF T 的完整設(shè)計(jì)方案 , 并 在 Altera 公司 C

19、yclone 系列的 EP1C20F400C6芯 片上加以實(shí)現(xiàn) 6。整個(gè)設(shè)計(jì)占用 6700個(gè)邏輯單 元 , 處理器時(shí)鐘頻率最高可達(dá) 53M Hz , 運(yùn)算結(jié)果絕 對(duì)誤差僅為 0. 16, 信噪比很高 ,。, 從本文詳細(xì)描述了基于 FP GA 的混合基 8/4FF T 算法 , 設(shè)計(jì) 、 實(shí)現(xiàn)了硬件系統(tǒng) 。 該設(shè)計(jì)可選擇性的實(shí) 現(xiàn) 8k 、 4k 、 2k 點(diǎn)的 FF T 運(yùn)算 ; 采用新的乘法器結(jié) 構(gòu) , 減小了硬件面積 , 加快了運(yùn)算速度 ; 數(shù)據(jù) RAM 應(yīng)用對(duì)稱(chēng)乒乓結(jié)構(gòu) , 提高了連續(xù)運(yùn)算能力 ; 溢出電路 簡(jiǎn)單且提高了計(jì)算精度 。硬件運(yùn)行結(jié)果表明 , 本文 提出的大點(diǎn) FF T 系統(tǒng)是切實(shí)可行的 , 獲得了