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

0引言

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

1實驗原理及步驟

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

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

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

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

1.2快速傅里葉變換(FFT)

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

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

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

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

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

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

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

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

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

1.5 中央控制單元

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

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

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

1.7 運(yùn)算單元

運(yùn)算單元由蝶型運(yùn)算器和運(yùn)算 RAM 組成。蝶型運(yùn)算器完成對輸入數(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)算器可由一個復(fù)數(shù)乘法和兩個復(fù)數(shù)加（減）法器組成。為了提高運(yùn)算速度采用并行運(yùn)算，用四個實數(shù)乘法器、三個實數(shù)加法器、三個實數(shù)減法器組成。蝶型運(yùn)算器實現(xiàn)框圖如圖 5 所示。蝶型運(yùn)算各個模塊利用 MAX+plusⅡ開發(fā)軟件中所提供的宏單元生成。

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

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

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

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

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

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

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

1.10塊浮點(diǎn)單元

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

1.11 FFT處理器功能仿真與設(shè)計驗證

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

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

圖6時序仿真圖

2實驗情況記錄

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

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

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

圖8 FPGA計算頻譜

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

3結(jié)語

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

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