【正文】 濾波時(shí)，并行算法與 DSP 處理器的尋址能力不相 適應(yīng)，不能有效利用數(shù)據(jù)傳輸?shù)膸捄瓦\(yùn)算能力，造成硬件資源的浪費(fèi)。是指應(yīng)特定用戶要求和特定電子系統(tǒng)的需要而設(shè)計(jì)、制造的集成電路。因此，任何的線路改版都需要重新設(shè)計(jì)并且重新制造，這不僅增加開(kāi)發(fā)成本，而且造成產(chǎn)品快速上市的障礙，不太適合處理算法和參數(shù)經(jīng)常改變的場(chǎng)合。它不僅速度快、集成度高，并且?guī)缀跄茈S心所欲的完成定義的邏輯功能，還可以加密和重新編程，其編程次數(shù)可以達(dá)到 1 萬(wàn)次以上 。因此，可編程邏輯器件是設(shè)計(jì)數(shù)字系統(tǒng)的理想器件?？删幊踢壿嬈骷膽?yīng)用不僅使電子產(chǎn)品性能有了很大改善，而且也使數(shù)字系統(tǒng)設(shè)計(jì)方法發(fā)生了根本性變革?，F(xiàn)場(chǎng)可編程門(mén)陣列（ FPGA）是 20 世紀(jì) 80 年代中期由美國(guó) Xilinx 公司首先推出的大規(guī)?？删幊踢壿嬈骷? FPGA 的功能由邏輯結(jié)構(gòu)的配置數(shù)據(jù)決定。使用無(wú) SRAM 的 FPGA，在工作前需要從芯片外部加載配置數(shù)據(jù)。 理工大學(xué)學(xué)士學(xué)位論文 4 世界上第一片 FPGA 由美國(guó) Xilinx 公司于 1985 年發(fā)明，因而 FPGA 技術(shù)在國(guó)外發(fā)展較早，隨著 FPGA 技術(shù)的普及，使用 FPGA 芯片設(shè)計(jì)正在世界范圍內(nèi)興起。 目前在國(guó)際上，兩大 FPGA 巨頭 Xilinx 和 Altera 除了 FPGA 的生產(chǎn)外還與其第三方合作伙伴致力于 IP 核的開(kāi)發(fā)。由于 FPGA 芯片廠商對(duì)自己公司生產(chǎn)的芯片的性能非常了解，因此設(shè)計(jì)的模塊能最大限度的發(fā)揮芯片的性能。使用 IP 核構(gòu)建數(shù)字信號(hào)處理系統(tǒng)具有諸多優(yōu)點(diǎn)，如開(kāi)發(fā)周期短、性能穩(wěn)定、可靠、維護(hù)方便等。 國(guó)內(nèi)方面，我國(guó)的 FPGA 技術(shù)起步較晚，但是進(jìn)入 21 世紀(jì)后，發(fā)展非常迅速。 20xx 年羅雪茍、詹陽(yáng)分析了使用 FPGA 實(shí)現(xiàn) FFT 的幾種方法，對(duì)這幾種方法的優(yōu)缺點(diǎn)進(jìn)行了討論。采用流水方式對(duì)復(fù)數(shù)數(shù)據(jù)實(shí)現(xiàn)了加窗、 FFT、求模平方三種運(yùn)算，整個(gè)設(shè)計(jì)使用雙基 2 蝶形運(yùn)算單元，采用流水線方式盡量避免瓶頸的出現(xiàn)，提高了系統(tǒng)時(shí)鐘頻率。 20xx 年魯欣等也設(shè)計(jì)了 4096 點(diǎn) FFT，但是他使用了 1024 點(diǎn)的 FFT IP 核進(jìn)行了擴(kuò)展設(shè)計(jì)，如果系統(tǒng)輸入時(shí)鐘為 50MHz，計(jì)算時(shí)間為 。 理工大學(xué)學(xué)士學(xué)位論文 5 篇章結(jié)構(gòu) 本文主要針對(duì)基 2 順序處理的 FFT 處理器和 FIR 數(shù)字濾波器的 FPGA 實(shí)現(xiàn)進(jìn)行了研究，涉及算法選取、處理器結(jié)構(gòu)設(shè)計(jì)、系統(tǒng)仿真、 FPGA 實(shí)現(xiàn)和系統(tǒng)測(cè)試。 第 2 章為離散福利葉變換的快速算法的基本理論； 第 3 章為基于 modelsim的 FFT 算法的設(shè)計(jì) 第 4 章為基于 verilog 語(yǔ)言的 32 點(diǎn)基 2 復(fù)數(shù)的 FFT 的設(shè)計(jì)與仿真 最后一章為結(jié)論 最后對(duì)整篇論文進(jìn)行了總結(jié)和討論。 基 2FFT 算法 概述 長(zhǎng)度為 N的有限長(zhǎng)序列 x(n)的 DFT的表達(dá)式為 [1]： 1,.. .,1,0,)()( 10 ??? ??? NkWnxkX NN knN () x(n)在一般情況下是為復(fù)數(shù)序列的。那么對(duì)于 N個(gè) k值，一共需要 N2次復(fù)數(shù)乘法以及 N(N1)次復(fù)數(shù)加法運(yùn)算。從上面的說(shuō)明中可以看出， N點(diǎn)DFT的乘法和加法運(yùn)算次數(shù)均與 N2成正比。如果 N取 1024，那么 N2將達(dá)到 1,048,576。所以要想使得 DFT在各種科學(xué)和工程計(jì)算中得 到廣泛的應(yīng)用就必須想辦法減少其運(yùn)算量。其實(shí)一個(gè) N點(diǎn) DFT可以看做是由幾個(gè)較短的 DFT組成的。此外，旋轉(zhuǎn)因子 wmN具有明顯的周期性和對(duì)稱性。比較常用的 FFT 算法有基 2FFT和基 4FFT 兩種。下面就以 8 點(diǎn)的 FFT 為例詳細(xì)分析基 2FFT 算法。 由于這兩種算法的基本原理是相同的，所以下面主要介紹 DITFFT算法。 設(shè)序列 x(n)的長(zhǎng)度為 N，并且有以下的條件成立 N=2M， M為自然數(shù) 1(r)和 2(r)是 x(n)按 n的奇偶性分解成的兩個(gè) N/2 點(diǎn)的子序列，如下式所示 12,.. .1,0),2()(1 ??? Nrrxrx 12,...,1,0),12()(2 ???? Nrrxr 那么 x(n)的 DFT 為 ?? ?? ?? n knNn knN WnxWnxkX )()()( ?? ?? ??? ?? 12/ 0 )12(212/ 0 2 )12()2( N r rkNN r krN WrxWrx ?? ???? ? 12/ 0 2212/ 0 1 )()( N r krNN r kN WrxWrx 由于 krNkrNjkrNjkrN WeeW 2 2/22222 ??? ??ππ 所以 1,.. .,1,0)()()()()( 2112/0 2/212/0 2/1?????? ?? ????NkkXWkXWrxWWrxkW kNNrkrNkNNrkrN （ ） 其中)(1kX和)(2k分別為 1rx和(2r的 N/2 點(diǎn) DFT，即 理工大學(xué)學(xué)士學(xué)位論文 8 )]([)()()]([)()(212/02/22112/02/11rxDFTWrxkXrxDFTWrxkXNrkrNNrkrN?????????? （ ） （ ） 又由于)(1kX和)(2k都是以 N/2 為周期，且 kNNkN WW ??? 2 所以 X(k)又可 以表示為如下所示的表達(dá)式 12,...,1,0)()()( 21 ???? NkkXWkXkX kN （ ） 12,...1,0)()()2( 21 ????? NkkXWkXNk kN （ ） 這樣一個(gè) N點(diǎn)的 DFT就被拆分成為了兩個(gè) N/2點(diǎn)的 DFT。通常為了后續(xù)說(shuō)明的方便，和其它許多文獻(xiàn)一樣，在本文中也將式 ()和式 ()的運(yùn)算用圖 。 圖 采用蝶形運(yùn)算符號(hào)的這種圖示方法，可以用圖 2． 2來(lái)表示前面所講到的運(yùn)算。由圖 ，要完成一個(gè)蝶形運(yùn)算，需要一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法運(yùn)算。由前面的說(shuō)明可以 知道，計(jì)算一個(gè) N/2點(diǎn) DFT需要 (N2)2次復(fù)數(shù) 乘 法 和 N/2(N/21) 次 復(fù) 數(shù) 加 法 。通過(guò)對(duì)比可以看出，只進(jìn)行過(guò)這樣的次分解就使得運(yùn)算量減少了近一半，充分說(shuō)明了這樣分解對(duì)減少 DFT的運(yùn)算量是十分有效的。 圖 N點(diǎn) DFT的一次時(shí)域抽取分解圖 (NtiS) 與第一次分解相同，1(3x和 4為)rx按奇偶分解成的兩個(gè)長(zhǎng)為 N/4的子序列，即 14,.. .,1,0,)12()( )2()(1423 ???????? Nllxlx lxlx 那么，)(1kX又可表示為 ?? ?? ??? ??? 14/ 0 )12( 2/114/ 0 2 2/11 )12()2()( N i lkNN i klN WlxWlxkX ?? ???? ?? 14/ 0 4/42/14/ 0 4/3 )()( N i klNkNN i klN WlxWWlx 12/,.. .,1,0),()( 42/3 ???? NkkXWkx kN （ ） 其中 ??????????14/044/414/034/33)]([)())]([)()(NiklNNiklNlxDFTWlxklxDFTWlxkx 同理，由)(3kX和)(4k的周期性和 Wm2/N尼的對(duì)稱性2/2/4/ NkNNk WW ???最后得到： 理工大學(xué)學(xué)士學(xué)位論文 10 14/,.. .,1,0,)()()4/( )()()(42/3142/31 ?????????? ?? NkkXWkXNkX kXWkXkXkNkN （ ） 同理可得 14/,.. .,1,0,)()4/( )()()(62/5262/52 ?????????? ?? NkkXWkXNkX kXWkXkXkNkN （ ） 其中有 14/,.. .1,0,)12()()2()()]([)()()]([)()(2625614/04/66514/04/55??????????????????NllxlxlxlxlXDFTWlxkXlXDFTWlxkXNiklNNiklN 這樣，如圖 ，經(jīng)過(guò)第二次的分解，一個(gè) N/2點(diǎn)的 DFT就被拆分成為了兩個(gè) N/4點(diǎn)的 DFT了。依次類(lèi)推，經(jīng)過(guò) M1次分解，最后將 N點(diǎn) DFT分解成 N/2個(gè) 2點(diǎn) DFT。圖中 用到關(guān)系式mkNk m WW ?/。 圖 N點(diǎn) DFT的第二次時(shí)域抽取分解圖 (N_8) 理工大學(xué)學(xué)士學(xué)位論文 11 圖 N點(diǎn) DITFFT運(yùn)算流圖 （ N=8） DITFFT算法與直接計(jì)算 DFT運(yùn)算量的比較 由 DITFFT算法的分解過(guò)程及圖 ， N=2M時(shí)，其運(yùn)算流圖應(yīng)該有 M級(jí)蝶形，每一級(jí)都由 N/2蝶形 運(yùn)算構(gòu)成。所以， M級(jí)運(yùn)算總共需要的復(fù)數(shù)乘次數(shù)為 NNMNC M 2log22)2( ?? 復(fù)數(shù)加次數(shù)為 NNNMC A 2log)2( ?? 而由前面的介紹，直接計(jì)算 N點(diǎn)的 DFT需要 N2次復(fù)數(shù)乘法以及 N(N1)次復(fù)數(shù)加法運(yùn)算。當(dāng) N=210=1024時(shí)，可以求得直接計(jì)算 N點(diǎn)的 DFT和使用基 2DITFFT算法的所需乘法次數(shù)的比值為 )2/( 22 ??NN N 這樣，運(yùn)算效率就提高了 200多倍。由此圖更加直觀地看出 FFT算法的優(yōu)越性，從圖 ， N越大時(shí)，優(yōu)越性就越明顯。 (1)原址計(jì)算 由 圖 ， DITFFT的運(yùn)算過(guò)程是很有規(guī)律的。在同一級(jí)運(yùn)算中，每一個(gè)蝶形運(yùn)算是有兩個(gè)輸入和兩個(gè)輸出的。因?yàn)檫@樣，當(dāng)計(jì)算完一個(gè)蝶形以后，所得輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元 i以此類(lèi)推，當(dāng) M級(jí)運(yùn)算都計(jì)算完畢以后，原來(lái)存放輸入序列數(shù)據(jù)的 N個(gè)存儲(chǔ)單元中便依次存放了 X(k)的 N個(gè)值。很明顯原址計(jì)算可以節(jié)省存儲(chǔ)資源，從而降低硬件的成本。每個(gè)蝶形都要乘以因子pW。 通過(guò)觀察圖 ，第 L級(jí)共有 2L1個(gè)不同的旋轉(zhuǎn)因子。如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距 B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，則蝶形運(yùn)算可表示成如下形式： pNLLpNLLWBJXJXBJ WBJXJXJX )()()( )()()( 11 11 ????? ???? ?? ?? 其中 p=J2ML； J=0,1,...,2L1。 (4)序列的倒序 仔細(xì)分析可以發(fā)現(xiàn)看似毫無(wú)規(guī)律可循的 DITFFT算法的輸入序列的排序其實(shí)是很有規(guī)律的。 當(dāng) N=8時(shí)，這種規(guī)律就可以用圖 。圖 DITFFT的一種變形的運(yùn)算流圖，其中蝶形運(yùn)算的旋轉(zhuǎn)因子、運(yùn)算量與圖 。這種結(jié)構(gòu)的信號(hào)流圖有一個(gè)非常特別的優(yōu)點(diǎn)就是前一級(jí)的旋轉(zhuǎn)因子剛好是后一級(jí)上一半蝶形運(yùn)算的旋轉(zhuǎn)因子，且順序不變，如果旋轉(zhuǎn)因子的計(jì)算采用查表法，只要構(gòu)造出一個(gè) N/2點(diǎn)的NpW，就可以 用它來(lái)計(jì)算 N、 N/ N/ ...長(zhǎng)度的 FFT。本課題也是采用的圖 。 浮點(diǎn)表示法所能表示的數(shù)值范圍將遠(yuǎn)遠(yuǎn)大于定點(diǎn)表示法。浮點(diǎn)運(yùn)算要比 定點(diǎn)運(yùn) 算 復(fù)雜。 定點(diǎn)數(shù)加減法的溢出及檢測(cè)方法 在定點(diǎn)小數(shù)機(jī)器中，數(shù)的表示范圍為 |X|1。在定點(diǎn)機(jī)中，正常情況下是不允許出現(xiàn)溢出的。 x=， Y=，那么 [x]補(bǔ) =， [y]補(bǔ) =，同理可得： [x+y]補(bǔ) =，兩個(gè)負(fù)數(shù)相加的結(jié)果成為正數(shù)，這同樣是錯(cuò)誤的。兩個(gè)正數(shù)相加，結(jié)果大于機(jī)器所能表示的最大正數(shù)，稱為上溢。為了判斷“溢出”是否發(fā)生，可以采用雙符號(hào)位法，也稱為“變形補(bǔ)碼”或“模 4補(bǔ)碼”，從 而可使模 2補(bǔ)碼所能表示的數(shù)的范圍擴(kuò)大一倍。 理工大學(xué)學(xué)士學(xué)位論文 16 采用變形補(bǔ)碼后，任何小于 l的 正數(shù)，兩個(gè)符號(hào)位都是 0，即 00．nxxx ...21；任何大于 l的負(fù)數(shù)，兩個(gè)符號(hào)位都是“ 1”，即 11．nxx ...21；如果兩個(gè)數(shù)相加后，其結(jié)果的符號(hào)位出現(xiàn)“ 01”或“ 10”兩種組合時(shí)，表示發(fā)生溢出。 定點(diǎn)數(shù)的定標(biāo) 數(shù)的定標(biāo)就是根據(jù)需要，人為地指定小數(shù)點(diǎn)的位置，這 主要是由于在利用 FPGA進(jìn)行數(shù)字系統(tǒng)設(shè)計(jì)的時(shí)候無(wú)法將小數(shù)直接表示出來(lái)?，F(xiàn)在以 16位為例，通過(guò)表 精度。 表 16位有符號(hào)數(shù)的定標(biāo)表示法 Q表示 S表示