畢業(yè)設(shè)計(jì)報(bào)告-基于FPGA的FFT設(shè)計(jì)與實(shí)現(xiàn)

信息與通信工程學(xué)院 綜合實(shí)驗(yàn)（ 1）設(shè)計(jì)報(bào)告 基于 FPGA 的 FFT 設(shè)計(jì)與實(shí)現(xiàn) 學(xué) 號(hào)： S309080034 專 業(yè) ： 光學(xué)工程 學(xué)生姓名： 彭歡 任課 教師： 鐘志 副教授 2010 年 7 月 基于 FPGA 的 FFT 的設(shè)計(jì)與實(shí)現(xiàn) 彭歡 信息與通信工程學(xué)院 摘 要： 本文主要研究如何利用 FPGA 實(shí)現(xiàn) FFT 處理器，包括算法選取、算法驗(yàn)證、系統(tǒng)結(jié)構(gòu)設(shè)計(jì)、各個(gè)模塊設(shè)計(jì)、FPGA 實(shí)現(xiàn)和測試整個(gè)流程。設(shè)計(jì)采用基 -2 按時(shí)間抽取算法，以 XILINX 公司提供的 ISE6.1 為軟件平臺(tái)，利用 Verilog HDL 描述的方式實(shí)現(xiàn)了 512 點(diǎn) 16bist 復(fù)數(shù)塊浮點(diǎn)結(jié)構(gòu)的 FFT 系統(tǒng)，并以 FPGA 芯片場 Virtex II XC2V1000 為硬件平臺(tái)，進(jìn)行了仿真、綜合等工作。仿真結(jié)果表明其計(jì)算結(jié)果達(dá)到了一定的精度，運(yùn)算速度可以滿足一般實(shí)時(shí)信號(hào)處理的要求。 關(guān)鍵詞： 快速傅立葉變換，現(xiàn)場可編程門陣列，塊浮點(diǎn)， Verilog HDL 1 引言 目前， FFT 己廣泛應(yīng)用在頻譜分析、匹配濾波、數(shù)字通信、圖像處理、語音識(shí)別、雷達(dá)處理、遙感遙測、地質(zhì)勘探和無線保密通訊等眾多領(lǐng)域。在不同應(yīng)用場合，需要不同性能要求的 FFT 處理器。在很多應(yīng) 用領(lǐng)域都要求 FFT 處理器具有高速度、高精度、大容量和實(shí)時(shí)處理的性能。因此，如何更快速、更靈活地實(shí)現(xiàn) FFT 變得越來越重要。 在過去很長一段時(shí)間， DSP 處理器是 DSP 應(yīng)用系統(tǒng)核心器件的唯一選擇。盡管 DSP 處理器具有通過軟件設(shè)計(jì)能適用于實(shí)現(xiàn)不同功能的靈活性，但面對當(dāng)今速度變化的 DSP 應(yīng)用市場，特別是面對現(xiàn)代通信技術(shù)的發(fā)展， DSP 處理器在處理速度上早已力不從心。 與 DSP 相比， FPGA 實(shí)現(xiàn) FFT 的主要優(yōu)越性有 ： (1)、 FPGA 實(shí)現(xiàn)數(shù)字信號(hào)處理最顯著的特點(diǎn)就是高速性能好。 FPGA 有內(nèi)置的高速乘法器和加法器，尤其適合于 乘法和累加等重復(fù)性的 DSP 任務(wù)。 (2)、 FPGA 的存儲(chǔ)量大。 DSP 內(nèi)部一般沒有大容量的存儲(chǔ)器，但是 FTF 實(shí)時(shí)處理運(yùn)算需要存儲(chǔ)大量的數(shù)據(jù)，只能外接存儲(chǔ)器，這樣往往會(huì)使運(yùn)算速度下降，同時(shí)電路也會(huì)更復(fù)雜和不穩(wěn)定。目前，高檔的 FPGA 中有巨量的高速存儲(chǔ)器，不用外接存儲(chǔ)器便可實(shí)現(xiàn) FFT 實(shí)時(shí)處理運(yùn)算，其速度更快，電路更簡單，集成度和可靠性也大幅度提高。 (3)、 FPGA 是硬件可編程的，比 DSP 更加靈活。 DSP 往往需要外部的接口和控制芯片配合工作， FPGA 則不需要，這樣使得硬件更簡單和小型化。 (4)、 在比較 FPGA 和 DSP 時(shí)，一個(gè)極為重要的系統(tǒng)參數(shù)是輸入 /輸出 (1/0)帶寬。除了一些專用引腳外， FPGA 上幾乎所有的引腳均可供用戶使用，這使得 FPGA 信號(hào)處理方案具有非常高性能的 FO 帶寬。大量的 FO 引腳和多塊存儲(chǔ)器可讓系統(tǒng)在設(shè)計(jì)中獲得優(yōu)越的并行處理性能。 2 現(xiàn)場可編程門陣列 (FPGA)技術(shù) 2.1 FPGA 器件簡介 FPGA 即現(xiàn)場可編程門陣列，它是作為 ASIC 領(lǐng)域中的一種半定制電路而出現(xiàn)的，既 解決了定制電路的不足，又克服了原有可編程器件門電路數(shù)有限的缺點(diǎn) 。 FPGA 結(jié)合了微電子技術(shù)、電路技術(shù)、 EDA 技術(shù)，使設(shè)計(jì)者可以集中精力進(jìn)行所需邏 輯功能的設(shè)計(jì)，縮短設(shè)計(jì)周期，提高設(shè)計(jì)質(zhì)量。 FPGA 己經(jīng)在計(jì)算機(jī)硬件、工業(yè)控制、遙感遙測、雷達(dá)聲納、數(shù)據(jù)處理、智能儀器儀 表、廣播電視、醫(yī)療電子和現(xiàn)代通信等多種領(lǐng)域中得到廣泛應(yīng)用 ， FPAG 開發(fā)技術(shù)，己經(jīng)成為數(shù)字系統(tǒng)的教學(xué)實(shí)踐、科研試驗(yàn)、樣機(jī)調(diào)試和中小批量生產(chǎn)的首選方案。 2.1.1 FPGA 的基本結(jié)構(gòu) FPGA 采用了邏輯單元陣列 LCA 這樣一個(gè)新概念，內(nèi)部一般是 由可配置邏輯模CLB、可編程輸入 /輸出模塊 IOB 和互連資源 ICR 及一個(gè)用于存放編程數(shù)據(jù)的靜態(tài)存儲(chǔ)器 SRAM 組成，以 XILNIX 公司的 XC4000， 基本結(jié)構(gòu)如圖 2.1 所 示。 圖 2.1 XC4000 系列 FPGA 基本結(jié)構(gòu) 2.1.2 FPGA 器件的性能特點(diǎn) FPGA 器件的性能特點(diǎn)主要有 ： (1)、 采用 FPGA 設(shè)計(jì) ASIC 電路，用戶不需要投片生產(chǎn)，就能得到合用的芯片。 (2)、 FPGA 提供豐富的 I/O 引腳和觸發(fā)器，集成度遠(yuǎn)遠(yuǎn)高于可編程陣列邏輯 (PAL)器件。 (3)、 FPGA 器件結(jié)構(gòu)靈活，內(nèi)部的 CLB、 IOB 和 ICR 均可以編程，可以實(shí)現(xiàn)多個(gè)變量的任意邏輯。 (4)、 某些器件提供片內(nèi)高速 RAM，可用于 FIFO 等設(shè)計(jì)。 (5)、 基于 SRAM 編程技術(shù)，具有高密度、高速度、高可靠性和低功耗的特 性。 (6)、 FPGA 是 ASIC 電路中設(shè)計(jì)周期最短、開發(fā)費(fèi)用最低、風(fēng)險(xiǎn)最小的器件之一。 2.2 基于 FPGA 的系統(tǒng)開發(fā) 以 XILNIX 為例， FPGA 設(shè)計(jì)的一般流程包括設(shè)計(jì)輸入、功能仿真、設(shè)計(jì)實(shí)現(xiàn)、時(shí)序仿真、器件編程與測試幾個(gè)步驟。設(shè)計(jì)流程圖如圖 2.2 所示。 規(guī) 劃 和 預(yù) 算編 寫 代 碼繪 制 原 理 圖H D L R T L 仿 真綜 合 建 立 網(wǎng) 絡(luò) 表功 能 仿 真轉(zhuǎn) 換實(shí) 現(xiàn)映 射布 局 布 線實(shí) 現(xiàn) 時(shí) 序 逼 近 時(shí) 序 仿 真 建 立 位 流 文 件圖 2.2 FPGA 設(shè)計(jì)流程 (l)、設(shè)計(jì)輸入 :主要輸入方法有硬件描述語言和原理圖，結(jié)構(gòu)向?qū)?(Architrcture Wizard)和核生成器 (Core Geneartor)可以輔助設(shè)計(jì)輸入。 (2)、 功能仿真 :功能仿真沒有器件內(nèi)部邏輯單元和連線的實(shí)際延時(shí)信息，只是初步驗(yàn)證系統(tǒng)的邏輯功能。 (3)、設(shè)計(jì)實(shí)現(xiàn) :實(shí)現(xiàn)包括轉(zhuǎn)換、映射、布局布線、時(shí)間參數(shù)提取，同時(shí)產(chǎn)生各種報(bào)告和文件。 (4)、時(shí)序仿真 :時(shí)序仿真中使用了電路延時(shí)的最壞情況，分析時(shí)序關(guān)系，檢查和消除競爭冒險(xiǎn)、并對器件的實(shí)際工作性能進(jìn)行估計(jì)。 (5)、器件編程與測試 :設(shè)計(jì)實(shí)現(xiàn)以后，建立 FPGA 可識(shí)別文件，將編程數(shù)據(jù)下載到相應(yīng)的 FPGA 器件中去。 在 FPGA 設(shè)計(jì)的各個(gè)環(huán)節(jié)都有不同公司提供的不同的 EDA 工具。一般由 FPGA 廠商提供集成開發(fā)環(huán)境，如 ALTERA 公司的 Quartus II 和 XILINX 公司的 ISE。為提高設(shè)計(jì)效率，優(yōu)化設(shè)計(jì)結(jié)果，很多廠家提供了各種專業(yè)軟件，用以配合 FPGA/CPLD 芯片廠家提供的工具進(jìn)行更高效的設(shè)計(jì)。比較常見的使用方式是 ： 集成開發(fā)環(huán)境，專業(yè)邏輯仿真軟件和專業(yè)邏輯綜合軟件一起使用，進(jìn)行多種 EDA 工具的協(xié)同設(shè)計(jì)。本設(shè)計(jì)采用ISE6.1+Modelsim5.7g+SynpliyfPor。 2.3 硬件描述語言 Verilog HDL HDL 是硬件描述語言 (Hardware Description Language)的縮寫，是一種用形式方法來描述數(shù) 字電路和系統(tǒng)的語言。利用這種語言，數(shù)字電路系統(tǒng)的設(shè)計(jì)可以從抽到具體逐層描述自己的設(shè)計(jì)思想，用一系列分層次的模塊來表示極其復(fù)雜的數(shù)字統(tǒng)。隨著 EDA 技術(shù)的發(fā)展，使用 HDL 設(shè)計(jì) FPGA 已成為一種趨勢。目前最主要 HDL 是 VHDL 和 Verilog HDL，本設(shè)計(jì)采用 Verilog HDL。 作為硬件描述語言， Verilog HDL 具有如下特點(diǎn) ： (1)、 能夠在不同的抽象層次上，如系統(tǒng)級(jí)、行為級(jí)、寄存器傳輸級(jí) RTL、門級(jí)和開關(guān)級(jí)，對設(shè)計(jì)系統(tǒng)進(jìn)行精確而簡練的描述 ； (2)、 能夠在每個(gè)抽象層次的描述上對設(shè)計(jì)進(jìn)行仿真驗(yàn)證，及 時(shí)發(fā)現(xiàn)可能存在的設(shè)計(jì)錯(cuò)誤，縮短設(shè)計(jì)周期，并保證整個(gè)設(shè)計(jì)過程的正確性 ； (3)、 由于代碼描述與具體工藝實(shí)現(xiàn)無關(guān)，因此易于設(shè)計(jì)標(biāo)準(zhǔn)化，提高了設(shè)計(jì)的重用性。如果有 C 語言的編程經(jīng)驗(yàn)，只需很短的時(shí)間就能掌握 Verilog HDL。 使用 HDL 進(jìn)行設(shè)計(jì)時(shí)，需要設(shè)計(jì)者完成的任務(wù)有編寫電路描述和編寫包含激勵(lì)波形描述的測試平臺(tái)文件，其激勵(lì)用于進(jìn)行電路功能測試，代測電路的行為特性由仿真器顯示波形。 3 FFT 算法原理及其硬件結(jié)構(gòu)設(shè)計(jì) 3.1 FFT 算法基本原理 有限長序列 ()xn 及其頻域表示 ()Xk 可由以下離散傅立葉變換得出 ： 10( ) D F T ( ) ( ) , ( 0 1 )N nkNnX k x n x n W k N （ 3.1） 101( ) I D F T ( ) ( ) , ( 0 1 )N nkNkx n X k X k W n NN （ 3.2） 其中， 2e j nknk NNW 。式 (3.1)稱為離散傅立葉 (正 )變換，式 (3.2)稱為離散傅立葉反變換，x(n)與 X(k)構(gòu)成了離散傅立葉變換對。 根據(jù)上述公式，計(jì)算一個(gè) X(k)，需要 N 次復(fù)數(shù)乘法和 N-1 次復(fù)數(shù)加法， 而計(jì)算全部 X(k) (0kN-1)，共需要 N2 次復(fù)數(shù)乘法和 N(N-1)次復(fù)數(shù)加法。實(shí)現(xiàn)一次復(fù)數(shù)乘法需要四次實(shí)數(shù)乘法和兩次實(shí)數(shù)加法，一次復(fù)數(shù)加法需要兩次實(shí)數(shù)加法，因此直接計(jì)算全部 X(k)共需要 4N2 次實(shí)數(shù)乘法和 2N(2N-1)次實(shí)數(shù)加法。當(dāng) N 較大時(shí)，對實(shí)時(shí)信號(hào)處理來說，對 處理器計(jì)算速度有十分苛刻的要求，于是如何減少計(jì)算離散傅里葉變換運(yùn)算量的問題變得至關(guān)重要。 為減少運(yùn)算量，提高運(yùn)算速度，就必須改進(jìn)算法。計(jì)算 DFT 過程中需要完成的運(yùn)算的系數(shù)里，存在相當(dāng)多的對稱性。通過研究這種對稱性，可以簡化計(jì)算過程中的運(yùn) 算，從而減少計(jì)算 DFT 所需的時(shí)間。 nkNW 具有周期性、對稱性和可約性。 利用 其 特性，將 x(n)或 X(k)序列按一定規(guī)律分解成短序列進(jìn)行運(yùn)算，這樣可以避免大量的重復(fù)運(yùn)算，提高計(jì)算 DFT 的運(yùn)算速度。算法形式有很多種，但基本上可以分為兩大類，即按時(shí)間抽取 FFT 算法和按頻率抽取 FFT算法。 3.1.1 基 -2 時(shí)間抽取 FFT 算法 如果序列 x(n)的長度 N=2M，其中 M 是整數(shù) (如果不滿足此條件，可以人為地增補(bǔ)零值點(diǎn)來達(dá)到 )，在時(shí)域上按奇偶抽取分解成短序列的 DFT，使最小 DFT 運(yùn)算單元為 2 點(diǎn)。通常將 FFT 運(yùn)算中最小 DFT 運(yùn)算單元稱為基 (radix)，因而把這種算法稱為基 -2 時(shí)間抽取 FFT(DIT-FFT)算法。 若 Xm(p)和 Xm(q)為輸入數(shù)據(jù)， Xm+1(p)和 Xm+1(q)為輸出數(shù)據(jù)， rNW為旋轉(zhuǎn)因子，則對于基 -2DIF-FFT 算法，蝶形運(yùn)算的基本公式為 ： 11( ) ( ) ( )( ) ( ) ( )km m m Nkm m m NX p X p X q WX q X p X q W （ 3.3） 其圖形表示如圖 3.1 所示，稱 Xm(p)為上結(jié)點(diǎn)， Xm(q)為下結(jié)點(diǎn)。 X m ( p )Xm( q )WNk+-Xm + 1( p )Xm + 1( q )圖 3.1 時(shí)間抽取蝶形運(yùn)算單元 3.1.2 基 -2 頻率 抽取 FFT 算法 上述的基 -2DIT-FFT 算法是按奇偶原則對輸入序列 x(n)進(jìn)行抽取分解，結(jié)果在頻域使 X(k)前后分組。如果在時(shí)域把 x(n)分解成前后兩組，那么在頻域就會(huì)使 X(k)形成奇偶抽取分組，稱為頻率抽取 FFT(DIF-FFT)算法。 若 Xm(p)和 Xm(q)為輸入數(shù)據(jù)， Xm+1(p)和 Xm+1(q)為輸出數(shù)據(jù)， rNW為旋轉(zhuǎn)因子， 則對于基 -2DIF-FFT 算法，蝶形運(yùn)算的基本公式為 ： 11( ) ( ) ( )( ) ( ) ( ) m m m km m m NX p X p X qX q X p X q W（ 3.4） 其圖形表示如圖 3.2 所示，稱 Xm(p)為上結(jié)點(diǎn)， Xm(q)為下結(jié)點(diǎn)。 Xm( p )Xm( q )WNk+-Xm + 1( p )Xm + 1( q )圖 3.2 頻率抽取蝶形運(yùn)算單元 DIT-FFT 算法與 DIF-FFT 算法均為原位運(yùn)算，而且運(yùn)算量相同，不同之處在于 ： 數(shù)據(jù)存放的方式不同， DIT 為倒序輸入、正序輸出，而 DIF 為正序輸入、倒序輸出，運(yùn)算完畢需進(jìn)行整 序操作 ； 蝶形運(yùn)算不同， DIT的復(fù)數(shù)乘法出現(xiàn)在 (加 )減法之前，而 DIF的復(fù)數(shù)乘法出現(xiàn)在 (加 )減法之后。 所以 DIT-FFT 算法和 DIF-FFT 算法是兩種等價(jià)的 FFT 運(yùn)算。參照 DIT-FFT 的數(shù)據(jù)地址產(chǎn)生規(guī)律，可總結(jié)出 DIF-FFT 的數(shù)據(jù)地址產(chǎn)生規(guī)律。 3.2 FFT 的硬件實(shí)現(xiàn)結(jié)構(gòu) 選擇合適的系統(tǒng)結(jié)構(gòu)，是提高 FFT 處理器性能的關(guān)鍵。以基 -2DIT-FFT 算法為例，本章將首先討論幾種常用 FFT 處理器的實(shí)現(xiàn)形式。 (1)順序處理 順序處理是 FFT 專用處理器的基本形式，蝶形運(yùn)算單元在控制器的控制下，根據(jù)標(biāo)準(zhǔn)的 FFT 信號(hào)流 圖，按時(shí)間順序依次進(jìn)行運(yùn)算。即從第 1 級(jí)開始，從上至下依次進(jìn)行，第 1 級(jí)算完后，然后進(jìn)行第 2 級(jí)，第 3 級(jí)， ，直至算完為止。 順序處理具有以下特點(diǎn) ： 只用一個(gè)蝶形運(yùn)算單元 ； 輸入數(shù)據(jù)、中間數(shù)據(jù)和輸出結(jié)果均使用同一組存儲(chǔ)器 ； 順序執(zhí)行2log2N N次蝶形運(yùn)算； 如果一次蝶形運(yùn)算時(shí)間為 T，則總的運(yùn)算時(shí)間為2lo g2NTN(2)流水線處理 流水線處理是把一個(gè)重復(fù)的過程分解為若干個(gè)子過程，每個(gè)子過程可以與其他子過程并行進(jìn)行。 對一個(gè) N 點(diǎn)的 FFT 變換，每一級(jí)的 N/2 次蝶形運(yùn)算安排一個(gè)獨(dú)立的蝶形處理器按順序完成，總共采用2log N個(gè)蝶形運(yùn)算單元同時(shí)進(jìn)行工作，這種形式稱為流水線處理或者級(jí)聯(lián)處理。 流水線處理具有以下特點(diǎn) ： 使用2logMN個(gè)蝶形運(yùn)算單元 ； M 個(gè)蝶形運(yùn)算單元在各級(jí)間并行運(yùn)算，即級(jí)與級(jí)之間是并行工作的 ； 每個(gè)蝶形運(yùn)算單元在每一級(jí)中順序執(zhí)行 N/2 個(gè)蝶形運(yùn)算，即每一級(jí)運(yùn)算的內(nèi)部是串行工作的 ； 如果一次蝶形運(yùn)算時(shí)間為 T，則理論上總的運(yùn)算 時(shí)間和每一級(jí)數(shù)據(jù)運(yùn)算時(shí)間一樣(沒考慮級(jí)與級(jí)之間的數(shù)據(jù)緩沖 )，為 /2TN 。 (3)并行迭代處理 對于每一級(jí)中的 N/2 個(gè)蝶形運(yùn)算，采用 N/2 個(gè)蝶形運(yùn)算單元并行工作，級(jí)與級(jí)之間順序進(jìn)行計(jì)算，這種實(shí)現(xiàn)形式稱為并行迭代處理。 并行迭代處理具有以下特點(diǎn) ： 使用 N/2 個(gè)蝶形運(yùn)算單元，在每一級(jí)中并行工作 ； 各級(jí)間順序處理工作 ； 如果一次蝶形運(yùn)算時(shí)間為 T，則總的運(yùn)算時(shí)間為2logTN。 (4)陣列處理 把流水線處理和并行迭代處理結(jié)合 起來， 采用2log2N N個(gè)蝶形 運(yùn)算單元實(shí)現(xiàn)全 并行工作，稱為陣列處理。 陣列處理具有以下特點(diǎn) ： 使用2log2N N個(gè)蝶形運(yùn)算單元 并行完成全部蝶形運(yùn)算； 由于采用流水線工作方式，使單位時(shí)間內(nèi)處理的數(shù)據(jù)增大了2log N倍，也就是說數(shù)據(jù)的吞吐量增大了2log N倍 ； 總的運(yùn)算時(shí)間理論上等于一次蝶形運(yùn)算時(shí)間 T。 從空間復(fù)雜度和設(shè)備使用量上看，順序 處理最小，流水線處理次之，并行迭代和陣列處理則設(shè)備量最大，成本最昂貴。從處理速度上看，順序處理最慢，流水線次之，并行迭代和陣列處理速度最快，可應(yīng)用于實(shí)時(shí)性要求很高的場合 (如雷達(dá)信號(hào)處理系統(tǒng) )。綜上所述，處理速度的提高是以設(shè)備量和成本的增加為代價(jià)的。因此，在具體設(shè)計(jì)中，必須綜合考慮和適當(dāng)采用上述的各種形式的處理器，根據(jù)實(shí)際需求確定具體的實(shí)現(xiàn)方案，以取得 “ 速度 /成本 ” 的最佳值。本設(shè)計(jì)采用最基本的順序處理方案來實(shí)現(xiàn) 512 點(diǎn)16 位復(fù)數(shù)的 FFT 運(yùn)算系統(tǒng)。 4 FFT 處理器的 FPGA 的設(shè)計(jì)及實(shí)現(xiàn) 4.1 FFT 處理器總體設(shè)計(jì) 基 -2FFT 模塊設(shè)計(jì)主要由 6 部分組成 ： 蝶形運(yùn)算單元，存儲(chǔ)單元，地址產(chǎn)生單元，功能切換單元，浮點(diǎn)單元和時(shí)序控制元，如圖 4.1 所示。 地址產(chǎn)生單元雙 口R A M1功 能切 換雙 口R A M2塊浮點(diǎn)單元蝶 形運(yùn) 算單 元R O M時(shí) 序 控 制 單 元圖 4.1 FFT 處理器結(jié)構(gòu)框圖 各模塊的功能概述如下 ： (l)、 蝶形運(yùn)算單元 ： 采用 DIT 方式完成基 -2 蝶形運(yùn)算，若數(shù)據(jù)從雙口 RAM1 中讀出，則計(jì)算結(jié)果存入雙口 RAMZ 中，反之亦然 ； (2)、 存儲(chǔ)單元 ： 主要用來存儲(chǔ)輸入數(shù)據(jù)、中間結(jié)果 (RAM)，預(yù)置旋轉(zhuǎn)因子 (ROM)，以及最后的計(jì)算結(jié)果 (RAM)； (3)、 地址產(chǎn)生單元 ： 產(chǎn)生 RAM 的讀、寫地址和 ROM 的讀地址 ； (4)、 功能切換單元 ： 完成 RAMI 與 RAMZ 間數(shù)據(jù)讀寫功能的切換 ； (5)、 塊浮點(diǎn)單元 ： 記錄蝶算單元輸出數(shù)據(jù)的位信息，并完成蝶算單元輸入數(shù)據(jù)的 截位 ； (6)、 時(shí)序控制單元 ： 產(chǎn)生各模塊的使能、控制信號(hào)，使整個(gè)流程正常工作。 4.2 蝶形運(yùn)算單元的 設(shè)計(jì) FFT 的核心操作是蝶形運(yùn)算，蝶形運(yùn)算直接影響著 FFT 處理器的速度，所以如何加快蝶形運(yùn)算的處理速度是提高 FFT 處理器速度的關(guān)鍵問題。 基 -2 時(shí)間抽取 FFT 運(yùn)算可分解成 ： 1 R R R R I1 I I I I I1 R R R R I1 I I I I I( ) ( ) ( ( ) ( ) )( ) ( ) ( ( ) ( ) )( ) ( ) ( ( ) ( ) )( ) ( ) ( ( ) ( ) )rrm m m N m N Im m m N m N Irrm m m N m N Im m m N m N IX p X p X q W X q WX p X p X q W X q WX q X p X q W X q WX q X p X q W X q W （ 4.1） 其中 p， q 表示序列下標(biāo) ， R， I 表示實(shí)部和虛部 。 并行結(jié)構(gòu)如圖 4.2 所示蝶形運(yùn)算分 3個(gè)階段實(shí)現(xiàn)。 4.2 蝶形運(yùn)算并行結(jié)構(gòu) 在蝶形單元設(shè)計(jì)中，考慮到 Virtex 系列 FPGA 豐富的乘法器資源，采用了四個(gè)乘法器并行運(yùn)算，使乘法運(yùn)算在一個(gè)時(shí)鐘周期內(nèi)完成，提高了運(yùn)算速度。在設(shè)計(jì)中為增大數(shù)據(jù)的動(dòng)態(tài)范圍，采用塊浮點(diǎn)結(jié)構(gòu)，蝶形運(yùn)算單元輸入數(shù)據(jù)為 16 位，輸出數(shù)據(jù)為 18 位。同時(shí)， 6 次加 (減 )法運(yùn)算分別用 6 個(gè)加 (減 )法器來實(shí)現(xiàn)。 根據(jù)上述的設(shè)計(jì)原理對蝶形運(yùn)算單元進(jìn)行硬件實(shí)現(xiàn)。蝶形運(yùn)算模塊示意圖如圖 4.3所示 ，其中， xl， y1， x2， y2 分別表示上、下結(jié)點(diǎn)數(shù)據(jù)的實(shí)部和虛部輸入，其位寬為 16bist；wx， wy 分別表示旋轉(zhuǎn)因子的實(shí)部和虛部，其位寬為 16bits； mx1， myl， mx2， my2 分別表示蝶形運(yùn)算上、下結(jié)點(diǎn)實(shí)部和虛部輸出，其位寬為 18bits； clk 是時(shí)鐘信號(hào) reset 是復(fù)位信號(hào)。為了保證數(shù)據(jù)的同步性，在蝶形運(yùn)算單元加入了使能信號(hào) start，使下結(jié)點(diǎn)數(shù)據(jù)和旋轉(zhuǎn)因子同步進(jìn)入乘法器。同時(shí)，上結(jié)點(diǎn)數(shù)據(jù)延遲 2 個(gè)時(shí)鐘周期后與復(fù)乘結(jié)果進(jìn)行加減運(yùn)算。 圖 4.3 蝶形運(yùn)算模塊示意圖 圖 4.4 為該蝶形運(yùn)算單元在 Modelsim中的仿真波形圖。 圖 4.4 蝶形運(yùn)算單元的 Modelsim 功能仿真波形圖 由圖 4.4 所示仿真波形圖可以看出，蝶形運(yùn)算單元在使能信號(hào) start=1 后的 3 個(gè)時(shí)鐘周期內(nèi)完成一次蝶形運(yùn)算，且如果每個(gè)時(shí)鐘來臨輸入新的操作數(shù)據(jù)，結(jié)果則連續(xù)輸出，與理論值比較，計(jì)算結(jié)果正確。 4.3 塊浮點(diǎn)單元設(shè)計(jì) 在 FFT 處理器設(shè)計(jì)中，若采用定點(diǎn)運(yùn)算，插入定衰減系數(shù)的方法防止溢出，結(jié)構(gòu)簡單，但運(yùn)算精度不高 ；若采用浮點(diǎn)運(yùn)算，精度高，但運(yùn)算復(fù)雜度增加，且速度降低。因此本設(shè)計(jì)采用介于定點(diǎn)和浮點(diǎn)之間的塊浮點(diǎn)算法。這種算法相比定點(diǎn)運(yùn)算，提 高了精度，相比浮點(diǎn)運(yùn)算，提高了速度，保證了 FFT 處理器處理器具有高精度、高速度的特點(diǎn)。 蝶形運(yùn)算單元和存儲(chǔ)器 RAM 兩者之間的數(shù)據(jù)流動(dòng)必須經(jīng)過塊浮點(diǎn)單元。塊浮點(diǎn)單元由溢出檢測單元 status_judge(有限狀態(tài)機(jī) )、指數(shù)累加器 accumulator 和數(shù)據(jù)選擇 器 mux組成，結(jié)構(gòu)如圖 4.5 所示，其中 L 表示數(shù)據(jù)位長，即在本系統(tǒng)中 L=16， L+1:0表示數(shù)據(jù)位寬為 L+2 位。 蝶 形 運(yùn) 算 單 元數(shù) 據(jù) 選 擇 器 溢 出 檢 測 單 元 指 數(shù) 累 加 器數(shù) 據(jù) 輸 入 L + 1 : 0 指 數(shù) 輸 出 L - 1 : 0 L + 1 : 0 圖 4.5 塊浮點(diǎn)單元結(jié)構(gòu)圖 參加蝶形運(yùn)算的 4 路 18 bits 數(shù)據(jù)從雙口 RAM 中 讀出后，送入數(shù)據(jù)選擇器，由數(shù)據(jù)選擇器選擇其中的 16bits 送入蝶形運(yùn)算單元 ；經(jīng)過蝶形運(yùn)算后，將 4 路 18bits 的輸出數(shù)據(jù)送入溢出檢測單元，首先檢測出絕對值最大的那個(gè)數(shù)據(jù)的高三位值，然后判斷出本次蝶形運(yùn)算的狀態(tài)機(jī)，并將其寄存 ；這樣依次進(jìn)行處理一級(jí)中每個(gè)蝶形運(yùn)算的結(jié)果，直至本級(jí) 蝶形運(yùn)算結(jié)束，此時(shí)溢出檢測單元產(chǎn)生下一級(jí)的溢出控制，由此決定數(shù)據(jù)選擇器在下一級(jí)運(yùn)算中該如何進(jìn)行工作，并將溢出結(jié)果送入指數(shù)累加器，累加溢出位數(shù)。這樣循環(huán)進(jìn)行，直至 FFT 運(yùn)算結(jié)束。 4.4 誤差分析 根據(jù)本設(shè)計(jì)所采用的 FFT 算法以及蝶形運(yùn)算單元的實(shí)現(xiàn) 結(jié)構(gòu)，其最化誤差分析模型如圖 4.6 所示，其中， Q 表示量化， 表示移位。 Q溢出檢測指數(shù)累加+- QQXm( p )Xm( q )WNkXm + 1( p )Xm + 1( q )圖 4.6 DIT 基 -2 蝶形運(yùn)算誤差分析模型 現(xiàn)假設(shè)每級(jí) FFT 蝶形運(yùn)算發(fā)生一次溢出，且溢出由復(fù)加運(yùn)算引入，數(shù)據(jù)格式為(b+1)bits 的二進(jìn)制補(bǔ)碼，量化方法中引入的誤差為舍入誤差。對于舍入量化，當(dāng)舍棄位數(shù)等于 1bits 時(shí)，其均值為 Q/4，方差為 Q2/16； 當(dāng)舍棄位數(shù)大于 1bits 時(shí)，其均值為 Q，方差為 Q2/12， Q=2-b 為量化步長。根據(jù)圖 4.6 所示的誤差分析模型，可得出誤差上 限時(shí)最后一級(jí)輸出中平均每個(gè)輸出點(diǎn)的均方誤差 MSE。對于塊浮點(diǎn)法有 ： 22222M S E ( ) ( 2 l o g ) ( ) 0 , 1 , . . . , 162QQk N N N N N k N （ 4.2） 對于定點(diǎn)算法： 22 8M S E ( ) ( 6 ) ( 1 ) 0 , 1 , . . . , 11 8 4QQk N N k NN （ 4.3） 假設(shè) FFT 輸入數(shù)據(jù) x(n)為白色隨機(jī)序列， x(n)對不同的 n 值無關(guān)， x(n)的實(shí)部、虛部均勻分布在 -1,1)上且無關(guān)。根據(jù)式 (4.2)和 (4.3)可以得到平均每個(gè) FFT 輸出頻點(diǎn)的噪信比 NSR。對于塊浮點(diǎn)算法有 ： 2 213N S R ( ) ( l o g ) 0 , 1 , . . . , 124k Q N N k N （ 4.4） 對于定點(diǎn)算法： 221 1 2 1 1 6N S R ( ) ( ) 0 , 1 , . . . , 12 4 1 1 1 1k Q N N k N （ 4.5） (a) N=512， NSR 隨數(shù)據(jù)位寬 b 的變化曲線 (b) b=16， NSR 隨 FFT 點(diǎn)數(shù) N 的變化曲線 圖 4.7 平均每個(gè) FFT 輸出頻點(diǎn)的 NSR 根據(jù)式 (4.4)和 (4.5)可以畫出誤差上限時(shí)，每個(gè) FFT 輸出頻點(diǎn)的信噪 比 NSR 隨數(shù)據(jù)位寬 b 的變化曲線，如圖 4.7 所示。其中，圖 (a)為 N=512， NSR 隨數(shù)據(jù)位寬 b 的變化曲線，圖 (b)為 b=16， NSR 隨 FFT 點(diǎn)數(shù) N 的 變化曲線，其中，“ -o-”表示塊浮點(diǎn)的變化曲線，“ -+-”表示定點(diǎn)的變化曲線。 4.5 其它單元模塊的設(shè)計(jì) 包括地址產(chǎn)生單元，倒序輸出地址單元設(shè)計(jì)， ROM 設(shè)計(jì)， RAM 設(shè)計(jì) ，數(shù)據(jù)切換模塊，時(shí)序控制單元模塊 ， DCM 模塊 等。在此不再一一贅述。 5 FFT 系統(tǒng)仿真與測試 為了證明系統(tǒng)設(shè)計(jì)的正確性，需要對系統(tǒng)進(jìn)行測試試驗(yàn)。將系統(tǒng)仿真結(jié)果在 Modelsim中以數(shù)字和模擬形式顯示，再把經(jīng)過導(dǎo)出的數(shù)據(jù)與 MATLAB 中的價(jià)函數(shù)計(jì)算的理論值進(jìn)行比較，完成對系統(tǒng)的測試工作。 5.1 FPGA 的仿真驗(yàn)證 從硬件設(shè)計(jì)到芯片流片，整個(gè)過程都離不開仿真驗(yàn)證。仿真驗(yàn)證與設(shè)計(jì)流程 相關(guān)，一般是通過仿真、時(shí)序分析、下載調(diào)試等來檢驗(yàn)設(shè)計(jì)的正確性。在 FPGA 開發(fā)流程中，仿真驗(yàn)證主要包括功能仿真和時(shí)序仿真兩個(gè)部分。功能仿真是為了檢驗(yàn)設(shè)計(jì)功能是否正確。通過功能仿真，及時(shí)發(fā)現(xiàn)設(shè)計(jì)中的錯(cuò)誤，加快設(shè)計(jì)的進(jìn)度，提高設(shè)計(jì)的可靠性。時(shí)序仿真是為了保證設(shè)計(jì)滿足時(shí)序要求，使數(shù)據(jù)能被正確地采樣。準(zhǔn)確高效的仿真驗(yàn)證可以最大限度地避免設(shè)計(jì)失誤所造成的風(fēng)險(xiǎn)。 為提高數(shù)字電路設(shè)計(jì)的仿真驗(yàn)證效率，可采取的主要措施一是提高仿真驗(yàn)證工具 的速度和精度，二是改進(jìn)仿真驗(yàn)證的設(shè)計(jì)方法。 Modelsim 是業(yè)界公認(rèn)的專用 EDA 仿真工 具，它可以對 XLINIX 公司的全部FPGA/CPLD 產(chǎn)品進(jìn)行高精度的仿真驗(yàn)證。 Testbench 是最基本的仿真驗(yàn)證手段，其主要作用是 ： 例化待測試的設(shè)計(jì) ； 通過測試向量進(jìn)行仿真 ； 輸出仿真結(jié)果。 Testbench 是一個(gè)具有獨(dú)立結(jié)構(gòu)的 Verilog 模塊，其結(jié)構(gòu)如圖 5.1 所示，它包括激勵(lì)生成和監(jiān)視、待測系統(tǒng)和響應(yīng)顯示器三個(gè)部分。 待 測 生 成 和 監(jiān) 視 待 測 系 統(tǒng) 響 應(yīng) 顯 示 器圖 5.1 Testbench 結(jié)構(gòu) ISE 軟件具有輔助設(shè)計(jì)測試激勵(lì)的功能。根據(jù)設(shè)計(jì)源文件的模塊名稱與輸入輸出端口生成測試 激勵(lì)文件模板，使用板寫測試激勵(lì)，省去了許多格式化部分，如文件頭、測試激勵(lì)模塊名、測試激勵(lì)端口信號(hào)、待測模塊的調(diào)用和部分信號(hào)的初始化等部分。 在本文所設(shè)計(jì)的 FFT 系統(tǒng)的功能驗(yàn)證中， FFT 處理器的輸入端口高達(dá) 34 個(gè)，且測試激勵(lì)多次變化，同時(shí)還需要提供時(shí)鐘信號(hào)。在這種情況下，考慮首先在測試代碼中申明一個(gè) ROM，將所有測試激勵(lì)作為一個(gè)二進(jìn)制文件單獨(dú)保存，在功能驗(yàn)證運(yùn)行時(shí)，將此文件讀入到此 ROM 中，然后由測試模塊提供正確的時(shí)序信息，將此 ROM 的內(nèi)容提供給待測模塊的接口。這樣將測試激勵(lì)與時(shí)序明顯分開，便于編寫，也便于修 改。 5.2 正弦信號(hào)的仿真測試 5.2.1 信號(hào)在 matlab 中的處理 系統(tǒng)的輸入函數(shù)為 ( ) 2 0 0 0 0 s i n ( 2 0 )x t t ， 點(diǎn)數(shù) N=512，采樣頻率為 500Hz，即采樣間隔為 0.0025，采樣的時(shí)間長度為 0.002 512s。在 MATLAB 中實(shí)現(xiàn) FFT 處理的程序描 述如下 ： N=512； n=0:511； t=0.002*n； p=n*500/N； x=20000*sin(2*pi*10*t)； y=fft(x,N)； r=real(y)； i=imag(y)； subplot(3,1,1)； plot(t,x)；title(orignal signal)； subplot(3,1,2)； plot(p,r)；title(real)； subPlot(3,1,3)； plot(p,i)；title(imag)； 圖 5.2 正弦信號(hào) 512點(diǎn) F盯在 MATLAB中實(shí)部與虛部結(jié)果 5.2.2 信號(hào)在 modelsim 中的處理結(jié)果 在 ISE 平臺(tái)下編寫 Testbench 波形測試文件，先將輸入的原始數(shù)據(jù)存儲(chǔ)在 .bin 文 件 (數(shù)據(jù)以補(bǔ)碼二進(jìn)制形式存儲(chǔ) )中，作為測試激勵(lì)文件，在波形仿真時(shí)調(diào)用該文件可完成輸入。 512 點(diǎn) FFT 的計(jì) 算結(jié)果分別以文本文件和模擬波形文件形式輸 出。 Testbench 部分VerilogHDL 描述如下 ： reg31:0rom255:0； initial $readmemb(test.bin,rom)； initial fida=$fopen(dout_a,txt)； initial fidba=$fopen(dout_b,txt)； initial begin #1200 for(m=0；m256；m=m+1) #50 ina=romm31:16； inb=romm15:0； end always begin #251050 for(i=0；i512；i=i+l) #50 $fwrite(fida,%bn,outa)； $fwrite(fida,%bn,outb)； end 經(jīng)過仿真運(yùn)行， FFT 計(jì)算結(jié)果的實(shí)部和虛部分別存儲(chǔ)到 dout_a.txt， dout_b.txt 文本文件中。圖 5.3 所示圖為該正弦信號(hào)在 Modelsim 中生成的實(shí)部和虛部的模擬形式仿真圖。 圖 5.3 正弦信號(hào)在 modelsim 中的實(shí)部和虛部結(jié)果 圖 5.4 所示圖為該正弦信號(hào)輸出結(jié)果的總體仿真圖，可以看出 512 點(diǎn) FFT 系統(tǒng)分 9級(jí)完成，在級(jí)數(shù)計(jì)數(shù)器 cnt=0 時(shí)，輸出使能信號(hào) rd_en=1，輸出最后結(jié)果 ； 溢出指示 count有 7 次為 1，說明共有 7 次 1bit 溢出，故指數(shù)累加器 accumulator 最后顯示 7， 輸出數(shù)據(jù)乘以 128 便為實(shí)際的計(jì)算結(jié)果。 圖 5.4 512 點(diǎn) FFT 在 modelsim 中的仿真圖 5.2.3 上述兩種結(jié)果的比較 圖 5.5 所示圖為該正弦信號(hào)通過 FFT 處理器處理后的結(jié)果在 MATLAB 中的仿真圖形，其中，上圖表示 FFT 處理后的模值，中圖表示 FFT 處理后的實(shí)部值 ，下圖 FFT 處理后的 虛部值。 圖 5.5 512 點(diǎn) FFT 處理器結(jié)果在 MATLAB 中的仿真結(jié)果 比較圖 5.2 和圖 5.5 的，可以看出 FFT 處理器處理后的結(jié)果和 MATLAB 處理的結(jié)果基本一致 。 圖 5.6 為 FFT 處理器結(jié)果和 MATLAB 理論值之間的相對誤差曲線，其中上圖表示實(shí)部誤差，下圖表示虛部誤差。 圖 5.6 FFT 處理器結(jié)果和 MATLAB 理論值之間相對誤差 從圖 5.6 可以看出，實(shí)部和虛部數(shù)據(jù)相對誤差大部分控制在 0.5%左右，有幾個(gè)數(shù)據(jù)的相對誤差在 1.5%左右，稍微大一些，但總體上符合精度要求。這表明采用塊 浮點(diǎn)結(jié)構(gòu)可以達(dá)到一定的處理精度。 5.3 三角信號(hào)的仿真測試 5.3.1 信號(hào)在 MATLAB 中的處理 利用 MATLAB 產(chǎn)生一個(gè)三角信號(hào)，將此信號(hào)擴(kuò)大 100 倍后輸入到 FFT 處理器中。 n=1:128； x(n)=n-1； x(n+128)=128-n； x(n+256)=n-1； x(n+384)=128-n； y=fft(x)； r=real(y)； i=imag(y)； subplot(3,1,1)；plot(x)； subplot(3,1,2)；plot(r)； subplot(3,1,3)；plot(i)； 圖 5.7 三角信號(hào) 512 點(diǎn) FFT 在 MATLAB 中的結(jié)果 該三角信號(hào)通過 512 點(diǎn) FFT 的處理后結(jié)果如圖 5.7 所示，其中，上圖表示原信號(hào)，中圖表示序列通過 FFT 處理后的實(shí)部值，下圖表示序列通過 FFT 處理后的虛部值。 5.3.2 信號(hào)在 modelsim 中處理 圖 5.8 三角信號(hào) 512 點(diǎn) FFT 在 modelsim 中的實(shí)部和虛部結(jié)果 編寫 Testbench 波形測試文件，將該三角信號(hào)的 512 點(diǎn) FFT 處理器處理結(jié)果分別以文本文件和模擬波形文件輸出，輸出結(jié)果圖如圖 5.8 所示。 圖 5.9 為該三角信號(hào)輸出結(jié)果總體仿真圖，可以看出指數(shù)累加器 ac