基于FFT譜分析測(cè)頻算法的FPGA實(shí)現(xiàn)

0引言

在FPGA實(shí)驗(yàn)中，主要是用FPGA來(lái)實(shí)現(xiàn)FFT,使其完 成對(duì)信號(hào)的頻譜分析。流水線(xiàn)結(jié)構(gòu)FFT的設(shè)計(jì)主要是蝶形單 元的設(shè)計(jì)，通過(guò)旋轉(zhuǎn)參數(shù)的生成，將運(yùn)算結(jié)果寫(xiě)入地址并完 成輸出。

1實(shí)驗(yàn)原理及步驟

1.1 Quartus H開(kāi)發(fā)環(huán)境

Quartus H是Altera公司提供的FPGA/CPLD集成開(kāi)發(fā)軟 件，在Quartus 口上可以完成設(shè)計(jì)輸入、HDL綜合、布新布局(適 配)、仿真和選擇以及硬件測(cè)試等流程，它提供了一種與結(jié)構(gòu) 無(wú)關(guān)的設(shè)計(jì)環(huán)境，使設(shè)計(jì)者能方便地進(jìn)行設(shè)計(jì)輸入、開(kāi)始處 理和器件編程。Quartus 口具備仿真功能，同時(shí)支持第三方的 仿真工具(如 ModelSin)。此外，Quartus 口與 Matlab 和 DSP Builder結(jié)合，可用進(jìn)行基于FPAG的DSP系統(tǒng)開(kāi)發(fā)，是DSP 硬件系統(tǒng)實(shí)現(xiàn)的工具EDA工具。

Quartus 口設(shè)計(jì)與開(kāi)發(fā)的流程如圖1所示。

圖1 QuartusII設(shè)計(jì)與開(kāi)發(fā)的流程

1.2快速傅里葉變換(FFT)

FFT是DFT的快速算法。設(shè)離散的有限長(zhǎng)時(shí)間序列為x(n),0 < n < N— 1，則其離散的傅里葉變換為：

其中：(n)為時(shí)域點(diǎn)；X(k)為頻域點(diǎn)Wn為旋轉(zhuǎn)因子；(n)、 X(k)、Wn都是復(fù)數(shù)。完成整個(gè)DFT運(yùn)算共需要N次復(fù)數(shù)乘 法以及N(N-1)次復(fù)數(shù)加法運(yùn)算。當(dāng)N很大時(shí)，運(yùn)算量很大， 對(duì)于實(shí)時(shí)信號(hào)處理，要求CPU運(yùn)算速度很高，難以工程實(shí)現(xiàn)。 因此，出現(xiàn)了快速傅里葉變換(FFT)算法。FFT算法的基本 思想是利用旋轉(zhuǎn)因子Wn的周期性、對(duì)稱(chēng)性、特殊性以及周期 N的可互換性，將長(zhǎng)度為N點(diǎn)序列的DFT運(yùn)算逐次分級(jí)為較 短序列的DFT運(yùn)算，并將相同項(xiàng)合并，因?yàn)镈FT的運(yùn)算量與 N2成正比，當(dāng)N減小時(shí)，就大大減少了運(yùn)算量，提高了運(yùn)算 效率。N=2n個(gè)點(diǎn)的DFT復(fù)數(shù)乘法量由N次降為(N/2) logzN 次，復(fù)數(shù)加法由N(N-1)次降為(N/2) log2N次。

FFT算法種類(lèi)很多，基本上可分為兩大類(lèi)：一類(lèi)是針對(duì) N等于2的整數(shù)次冪的算法，如基2算法、基4算法和分裂 基算法等；另一類(lèi)是針對(duì)N不等于2的整數(shù)次冪的算法，以 Winograd為代表，它們有重要的理論價(jià)值，但是不適于硬件 實(shí)現(xiàn)?；?算法結(jié)構(gòu)簡(jiǎn)單，但運(yùn)算量大?；?算法相對(duì)于基 2算法更為復(fù)雜，但是計(jì)算量減少了。FFT算法按分解方式的 不同又可以分為時(shí)域抽取算法(decimation in time，DIT)和 頻域抽取算法(decimation in frequency，DIF)兩種。這兩種 算法在本質(zhì)上都是一種基于標(biāo)號(hào)分解的算法，在運(yùn)算量和復(fù) 雜性等方面完全一樣?？紤]到本設(shè)計(jì)FFT運(yùn)算的點(diǎn)數(shù)不是太 多，故選用了時(shí)域抽取基2算法(DIT)。

1.3按時(shí)間抽取的基2-FFT算法(DIT-基2-FFT)原理

FFT運(yùn)算的基本單元是蝶形運(yùn)算單元，基2蝶形運(yùn)算符 號(hào)如圖2所示。設(shè)蝶形運(yùn)算輸入數(shù)據(jù)為A=Ap+Aqj，B=Bp+Bqj，

FFT算法由多級(jí)蝶形運(yùn)算構(gòu)成，具體運(yùn)算流圖也有多種 形式。本設(shè)計(jì)選用了輸入倒序、輸出順序的運(yùn)算流圖，圖3所 示為N=8點(diǎn)時(shí)的DIT-FFT運(yùn)算流圖。這種運(yùn)算流圖是同址運(yùn) 算，其優(yōu)點(diǎn)是：在同一級(jí)運(yùn)算中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只 對(duì)計(jì)算本蝶形有用，而且蝶形的輸入輸出數(shù)據(jù)節(jié)點(diǎn)又同在一條 水平線(xiàn)上，這就意味著計(jì)算完一個(gè)蝶形運(yùn)算后，所得輸出數(shù) 據(jù)可以立即存入元出入數(shù)據(jù)所占用的存儲(chǔ)器。因此，在硬件實(shí) 現(xiàn)時(shí)可以節(jié)省存儲(chǔ)單元。

一個(gè)長(zhǎng)度為 N 的序列 x（n），滿(mǎn)足 N=2M，M 為整數(shù)。那么此序列 x（n）的 FFT 運(yùn)算流圖由 M 級(jí)蝶形運(yùn)算構(gòu)成，每一級(jí)有 N/2 個(gè)蝶形運(yùn)算，第 L 級(jí)蝶形運(yùn)算中使用旋轉(zhuǎn)因子的個(gè)數(shù)為 2L，L=0，1，2，…，M-1。64 點(diǎn) FFT 運(yùn)算，分 6 級(jí)，每級(jí)有 32 個(gè)蝶形運(yùn)算。

1.4 FFT處理器結(jié)構(gòu)設(shè)計(jì)

FFT 算 法 的 FPGA 硬 件 實(shí) 現(xiàn) 在 Altera 公 司 的MAX+plusⅡ系統(tǒng)環(huán)境下開(kāi)發(fā)完成，選用基于查找表結(jié)構(gòu)內(nèi)嵌存儲(chǔ)器的 APEX20 系列 FPGA 器件。圖 4 為 FFT 處理器的結(jié)構(gòu)圖。本設(shè)計(jì)采用單元結(jié)構(gòu)設(shè)計(jì)思路，整個(gè)處理器由數(shù)據(jù)接收單元、運(yùn)算單元、旋轉(zhuǎn)因子存儲(chǔ)單元、地址產(chǎn)生單元和中央控制單元 5 個(gè)單元組成，各單元在中央控制單元的控制下協(xié)調(diào)工作。其中，內(nèi)部接收單元采用乒乓 RAM 結(jié)構(gòu)，擴(kuò)大了數(shù)據(jù)吞吐量，計(jì)算單元采用流水與并行結(jié)合的結(jié)構(gòu)，加快了運(yùn)算速。

1.5 中央控制單元

中央控制單元是整個(gè)系統(tǒng)的控制核心，其主要功能是控制數(shù)據(jù)流向，協(xié)調(diào)各單元之間的運(yùn)行。中央控制單元根據(jù)系統(tǒng)時(shí)鐘確定當(dāng)前蝶型運(yùn)算所處的級(jí)數(shù)m和個(gè)數(shù)n，并把m、n傳送給地址產(chǎn)生單元。地址產(chǎn)生單元產(chǎn)生蝶型運(yùn)算兩個(gè)輸入數(shù)據(jù)和旋轉(zhuǎn)因子的地址，并把地址傳送給運(yùn)算 RAM 和旋轉(zhuǎn)因子存儲(chǔ)器。在中央控制單元讀使能信號(hào)控制下兩個(gè)輸入數(shù)據(jù)和旋轉(zhuǎn)因子被讀出。讀出的數(shù)據(jù)進(jìn)行必要的延遲和定標(biāo)處理后，送給運(yùn)算單元。經(jīng)過(guò)蝶型運(yùn)算后，運(yùn)算結(jié)果按原址寫(xiě)入RAM。

1.6 數(shù)據(jù)接收單元

數(shù)據(jù)接收單元主要功能是按幀接收外部數(shù)據(jù)，并將每幀數(shù)據(jù)按碼位倒置的順序乒乓存入接收 RAM1 或接收 RAM2。中央控制單元交替的對(duì)接收 RAM 中的數(shù)據(jù)進(jìn)行處理，當(dāng)中央控制單元將接收 RAM1中的數(shù)據(jù)取出，經(jīng)過(guò)蝶型運(yùn)算，結(jié)果存入運(yùn)算 RAM1 的同時(shí)上一幀數(shù)據(jù)的 FFT 運(yùn)算結(jié)果從運(yùn)算 RAM2 取出。接收 RAM 用 FPGA 的片上雙口 RAM 實(shí)現(xiàn)，接收單元控制寫(xiě)端口，中心控制單元控制讀端口。

1.7 運(yùn)算單元

運(yùn)算單元由蝶型運(yùn)算器和運(yùn)算 RAM 組成。蝶型運(yùn)算器完成對(duì)輸入數(shù)據(jù)的蝶型運(yùn)算，運(yùn)算 RAM 作為 FFT 的中間數(shù)據(jù)緩存。蝶型運(yùn)算器輸入數(shù)據(jù)為 A=Ap+Aqj，B=Bp+Bqj，旋轉(zhuǎn)因子 WrN=Wp+Wqj，蝶型運(yùn)算輸出如式（3）所示。根據(jù)式（3），蝶型運(yùn)算器可由一個(gè)復(fù)數(shù)乘法和兩個(gè)復(fù)數(shù)加（減）法器組成。為了提高運(yùn)算速度采用并行運(yùn)算，用四個(gè)實(shí)數(shù)乘法器、三個(gè)實(shí)數(shù)加法器、三個(gè)實(shí)數(shù)減法器組成。蝶型運(yùn)算器實(shí)現(xiàn)框圖如圖 5 所示。蝶型運(yùn)算各個(gè)模塊利用 MAX+plusⅡ開(kāi)發(fā)軟件中所提供的宏單元生成。

運(yùn)算 RAM1 和運(yùn)算 RAM2 作為 FFT 的中間數(shù)據(jù)緩存。兩塊 RAM 交替作為數(shù)據(jù)讀出和運(yùn)算結(jié)果寫(xiě)入單元，直到第 6 級(jí)蝶型運(yùn)算完成。

1.8 旋轉(zhuǎn)因子存儲(chǔ)單元

旋轉(zhuǎn)因子存儲(chǔ)單元，存儲(chǔ) FFT 運(yùn)算所需要的旋轉(zhuǎn)因子WrN，WrN=e（-j2π/N）r（r=0，1， …，N/2 － 1）。 旋 轉(zhuǎn) 因 子 先 在Matlab 中分實(shí)部和虛部產(chǎn)生，轉(zhuǎn)化成 16 位定點(diǎn)數(shù)，并將結(jié)果保存成 hex 文件格式。利用 MAX+plusII 軟件提供的 ROM 宏模塊"lpm_rom”產(chǎn)生兩個(gè)(N/2) X16 b的ROM,并分別用 旋轉(zhuǎn)因子實(shí)部和虛部對(duì)應(yīng)的hex文件對(duì)兩個(gè)ROM初始化，這 樣旋轉(zhuǎn)因子的值就固化在了 FPGA中。對(duì)應(yīng)不同級(jí)的蝶型運(yùn)算, 地址產(chǎn)生器產(chǎn)生相應(yīng)的地址送給ROM將旋轉(zhuǎn)因子讀出。

1.9地址產(chǎn)生單元

地址產(chǎn)生單元產(chǎn)生蝶型運(yùn)算兩個(gè)輸入數(shù)據(jù)和旋轉(zhuǎn)因子的 地址。實(shí)現(xiàn)的方法是根據(jù)地址產(chǎn)生的算法,通過(guò)邏輯運(yùn)算產(chǎn)生。 前面已介紹本設(shè)計(jì)FFT實(shí)現(xiàn)結(jié)構(gòu)為同址運(yùn)算，即蝶型運(yùn)算的 結(jié)果仍然寫(xiě)回輸入數(shù)據(jù)讀出單元。因此，將讀數(shù)據(jù)地址延遲 若干時(shí)鐘周期，就可作為運(yùn)算結(jié)果寫(xiě)入地址。對(duì)于N點(diǎn)FFT 運(yùn)算，用 m G (0 A log2N— 1), n G (0 A N/2— 1)表示第 m 級(jí)的第n個(gè)蝶型運(yùn)算。addr_4, addr_B (addr_』＜addr_B)分 別表示數(shù)據(jù)AB的入口地址。隨著級(jí)數(shù)m不同，每一級(jí)蝶型 運(yùn)算可分為若干組(0,…，n/2m+1— 1,N/2— 1)，每組2m個(gè) 蝶型運(yùn)算，兩個(gè)輸入數(shù)據(jù)共占用2m+1個(gè)地址。則m級(jí)的第n 個(gè)蝶型運(yùn)算位置為第n/2m組的第n%2m個(gè)。因此地址應(yīng)為：

式中：(n/2m) X2m+1描述為將n的低m位清零，再左移 一位。n%2m描述為取n的低m位。蝶型運(yùn)算所對(duì)應(yīng)的旋轉(zhuǎn)因 子存儲(chǔ)器入口地址設(shè)為addr_w,對(duì)于N點(diǎn)FFT共需要N/2個(gè) 旋轉(zhuǎn)因子，W N = e(-j2"/N)r(r=0, 1,…，N/2 — 1)根據(jù)第 m級(jí) 蝶型運(yùn)算所需旋轉(zhuǎn)因子的排列規(guī)律，旋轉(zhuǎn)因子存儲(chǔ)器入口地 址應(yīng)為：

64點(diǎn)FFT旋轉(zhuǎn)因子有32個(gè),共需要5位表示地址。第m級(jí)、 第n個(gè)蝶型運(yùn)算的旋轉(zhuǎn)因子地址可由邏輯移位的方法快速得 到。將n(5位)左移位(5-m),低位補(bǔ)0,得到了在(0?31) 中的 addr_w。

1.10塊浮點(diǎn)單元

塊浮點(diǎn)單元的實(shí)現(xiàn)思路是每級(jí)蝶型運(yùn)算結(jié)果動(dòng)態(tài)擴(kuò)展但 最大擴(kuò)展2位。塊浮點(diǎn)單元對(duì)蝶型運(yùn)算結(jié)果的高3位進(jìn)行檢測(cè)， 判斷當(dāng)前結(jié)果動(dòng)態(tài)范圍擴(kuò)展位數(shù)，記錄當(dāng)前級(jí)的最大擴(kuò)展位 數(shù)。下一級(jí)蝶型運(yùn)算時(shí)，根據(jù)前一級(jí)的最大擴(kuò)展位數(shù)，對(duì)讀 出的數(shù)據(jù)進(jìn)行定標(biāo)，選取數(shù)據(jù)送入蝶型運(yùn)算器。塊浮點(diǎn)單元 將每一級(jí)運(yùn)算結(jié)果動(dòng)態(tài)范圍擴(kuò)展位數(shù)進(jìn)行累加，和FFT運(yùn)算 結(jié)果一同輸出。

1.11 FFT處理器功能仿真與設(shè)計(jì)驗(yàn)證

仿真結(jié)果如圖6所示：

由仿真結(jié)果可以看出，該FFT處理器為串行流水線(xiàn)結(jié)構(gòu), 各級(jí)運(yùn)算模塊沒(méi)有實(shí)現(xiàn)并行運(yùn)行。

圖6時(shí)序仿真圖

2實(shí)驗(yàn)情況記錄

為驗(yàn)證仿真結(jié)果的正確性，采用上述方法實(shí)現(xiàn)256點(diǎn) FFT處理器，同時(shí)為提高精度將輸入數(shù)據(jù)的實(shí)部和虛部采用 16位二進(jìn)制數(shù)。對(duì)函數(shù)：

以120 MHz的頻率進(jìn)行抽樣，取256點(diǎn)作為FFT處理器 輸入數(shù)據(jù)進(jìn)行快速傅里葉變換，并將其輸出結(jié)果與Matlab結(jié) 果進(jìn)行比較，結(jié)果如圖7?圖9所示。

圖7抽樣函數(shù)及Matlab計(jì)算頻譜

圖8 FPGA計(jì)算頻譜

圖9各采樣點(diǎn)相對(duì)誤差

3結(jié)語(yǔ)

由于處理器采用定點(diǎn)運(yùn)算，在進(jìn)行乘法和加法運(yùn)算時(shí)不 可避免地造成一定誤差，尤其是在功率譜接近零值的這些點(diǎn) 上，相對(duì)誤差較大，但是在我們更為關(guān)心的功率譜幅值點(diǎn)上, 相對(duì)誤差僅為1%上下，完全可以滿(mǎn)足大多數(shù)應(yīng)用對(duì)于運(yùn)算精度的要求。

20211223_61c34fb10fe36__基于FFT譜分析測(cè)頻算法的FPGA實(shí)現(xiàn)