基于FFT譜分析測頻算法的FPGA實現

田西柱

摘 要：在信號頻譜分析試驗中，通過FPGA實現FFT。在MAX+plusⅡ系統環境下，介紹了流水線結構FFT的蝶形單元設計，詳解了旋轉因子的生成，通過地址產生單元和塊浮點單元實現了運算結果的輸出，并將其輸出結果與Matlab結果進行比較。

關鍵詞：FPGA；QuartusⅡ；FFT處理器；旋轉因子

中圖分類號：TP391 文獻標志碼：A 文章編號：2095-1302（2014）10-00-03

0 引 言

在FPGA實驗中，主要是用FPGA來實現FFT，使其完成對信號的頻譜分析。流水線結構FFT的設計主要是蝶形單元的設計，通過旋轉參數的生成，將運算結果寫入地址并完成輸出。

1 實驗原理及步驟

1.1 QuartusⅡ開發環境

QuartusⅡ是Altera公司提供的FPGA/CPLD集成開發軟件，在QuartusⅡ上可以完成設計輸入、HDL綜合、布新布局（適配）、仿真和選擇以及硬件測試等流程，它提供了一種與結構無關的設計環境，使設計者能方便地進行設計輸入、開始處理和器件編程。QuartusⅡ具備仿真功能，同時支持第三方的仿真工具（如ModelSin）。此外，QuartusⅡ與Matlab和DSP Builder結合，可用進行基于FPAG的DSP系統開發，是DSP硬件系統實現的工具EDA工具。

QuartusⅡ設計與開發的流程如圖1所示。

圖1 QuartusII設計與開發的流程

1.2 快速傅里葉變換（FFT）

FFT是DFT的快速算法。設離散的有限長時間序列為 x（n），0≤n≤N-1，則其離散的傅里葉變換為：

（1）

k=0，1，…，N-1 WN=e-j（2nN） （2）

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

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

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

FFT運算的基本單元是蝶形運算單元，基2蝶形運算符號如圖2所示。設蝶形運算輸入數據為A=Ap+Aqj，B=Bp+Bqj，旋轉因子W rN=Wp+Wqj。則蝶型運算輸出為：

（3）

圖2 基2蝶形運算

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

圖3 N=8點時的DIT-FFT運算流圖

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

1.4 FFT處理器結構設計

FFT算法的FPGA硬件實現在Altera公司的MAX+plusⅡ系統環境下開發完成，選用基于查找表結構內嵌存儲器的APEX20系列FPGA器件。圖4為FFT處理器的結構圖。本設計采用單元結構設計思路，整個處理器由數據接收單元、運算單元、旋轉因子存儲單元、地址產生單元和中央控制單元5個單元組成，各單元在中央控制單元的控制下協調工作。其中，內部接收單元采用乒乓RAM結構，擴大了數據吞吐量，計算單元采用流水與并行結合的結構，加快了運算速。

圖4 FFT處理器的結構圖

1.5 中央控制單元

中央控制單元是整個系統的控制核心，其主要功能是控制數據流向，協調各單元之間的運行。中央控制單元根據系統時鐘確定當前蝶型運算所處的級數m和個數n，并把m、n傳送給地址產生單元。地址產生單元產生蝶型運算兩個輸入數據和旋轉因子的地址，并把地址傳送給運算RAM和旋轉因子存儲器。在中央控制單元讀使能信號控制下兩個輸入數據和旋轉因子被讀出。讀出的數據進行必要的延遲和定標處理后，送給運算單元。經過蝶型運算后，運算結果按原址寫入RAM。

1.6 數據接收單元

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

1.7 運算單元

運算單元由蝶型運算器和運算RAM組成。蝶型運算器完成對輸入數據的蝶型運算，運算RAM作為FFT的中間數據緩存。蝶型運算器輸入數據為A=Ap+Aqj，B=Bp+Bqj，旋轉因子W rN=Wp+Wqj，蝶型運算輸出如式（3）所示。根據式（3），蝶型運算器可由一個復數乘法和兩個復數加（減）法器組成。為了提高運算速度采用并行運算，用四個實數乘法器、三個實數加法器、三個實數減法器組成。蝶型運算器實現框圖如圖5所示。蝶型運算各個模塊利用MAX+plusⅡ開發軟件中所提供的宏單元生成。

圖5 蝶形運算器

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

1.8 旋轉因子存儲單元

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

1.9 地址產生單元

地址產生單元產生蝶型運算兩個輸入數據和旋轉因子的地址。實現的方法是根據地址產生的算法，通過邏輯運算產生。前面已介紹本設計FFT實現結構為同址運算，即蝶型運算的結果仍然寫回輸入數據讀出單元。因此，將讀數據地址延遲若干時鐘周期，就可作為運算結果寫入地址。對于N點FFT運算，用m∈（0∧log2N-1），n∈（0∧N/2-1）表示第m級的第n個蝶型運算。addr_A，addr_B（addr_A

（4）

式中：（n/2m）×2m+1描述為將n的低m位清零，再左移一位。n%2m描述為取n的低m位。蝶型運算所對應的旋轉因子存儲器入口地址設為addr_w，對于N點FFT共需要N/2個旋轉因子，W rN=e（-j2π/N）r （r=0，1，…，N/2-1）。根據第m級蝶型運算所需旋轉因子的排列規律，旋轉因子存儲器入口地址應為：

addr_w=（n×2（log2N-1-m））（N/2） （5）

64點FFT旋轉因子有32個，共需要5位表示地址。第m級、第n個蝶型運算的旋轉因子地址可由邏輯移位的方法快速得到。將n（5位）左移位（5-m），低位補0，得到了在（0～31）中的addr_w。

1.10 塊浮點單元

塊浮點單元的實現思路是每級蝶型運算結果動態擴展但最大擴展2位。塊浮點單元對蝶型運算結果的高3位進行檢測，判斷當前結果動態范圍擴展位數，記錄當前級的最大擴展位數。下一級蝶型運算時，根據前一級的最大擴展位數，對讀出的數據進行定標，選取數據送入蝶型運算器。塊浮點單元將每一級運算結果動態范圍擴展位數進行累加，和FFT運算結果一同輸出。

1.11 FFT處理器功能仿真與設計驗證

仿真結果如圖6所示：

由仿真結果可以看出，該FFT處理器為串行流水線結構，各級運算模塊沒有實現并行運行。

圖6 時序仿真圖

2 實驗情況記錄

為驗證仿真結果的正確性，采用上述方法實現256點FFT處理器，同時為提高精度將輸入數據的實部和虛部采用16位二進制數。對函數：

x=cos（200πt）+cos（400π）

以120 MHz的頻率進行抽樣，取256點作為FFT處理器輸入數據進行快速傅里葉變換，并將其輸出結果與Matlab結果進行比較，結果如圖7～圖9所示。

圖7 抽樣函數及Matlab計算頻譜

圖8 FPGA計算頻譜

圖9 各采樣點相對誤差

3 結 語

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

參考文獻

[1]張輝. 張記龍.基-2 FFT處理器的FPGA實現[J].計算機與現代化.2009（9）：154-157.

[2]程佩青.數字信號處理教程[M].3版.北京：清華大學出版社，2007.

[3]袁俊泉.孫敏琪.曹瑞.Verilog HDL數字系統設計及其應用[M].西安：西安電子科技大學出版社，2002.

[4]謝彥林.可變點流水線結構FFT處理器的設計及其FPGA實現[D].西安：西安電子科技大學，2007.

[5]云霄.可配置FFT/IFFT處理器的設計及其FPGA構造[D].西安：西安電子科技大學，2009.

[6]蔡可紅.基于FPGA的FFT設計與實現[D].南京：南京理工大學，2006.

1.6 數據接收單元

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

1.7 運算單元

運算單元由蝶型運算器和運算RAM組成。蝶型運算器完成對輸入數據的蝶型運算，運算RAM作為FFT的中間數據緩存。蝶型運算器輸入數據為A=Ap+Aqj，B=Bp+Bqj，旋轉因子W rN=Wp+Wqj，蝶型運算輸出如式（3）所示。根據式（3），蝶型運算器可由一個復數乘法和兩個復數加（減）法器組成。為了提高運算速度采用并行運算，用四個實數乘法器、三個實數加法器、三個實數減法器組成。蝶型運算器實現框圖如圖5所示。蝶型運算各個模塊利用MAX+plusⅡ開發軟件中所提供的宏單元生成。

圖5 蝶形運算器

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

1.8 旋轉因子存儲單元

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

1.9 地址產生單元

地址產生單元產生蝶型運算兩個輸入數據和旋轉因子的地址。實現的方法是根據地址產生的算法，通過邏輯運算產生。前面已介紹本設計FFT實現結構為同址運算，即蝶型運算的結果仍然寫回輸入數據讀出單元。因此，將讀數據地址延遲若干時鐘周期，就可作為運算結果寫入地址。對于N點FFT運算，用m∈（0∧log2N-1），n∈（0∧N/2-1）表示第m級的第n個蝶型運算。addr_A，addr_B（addr_A

（4）

式中：（n/2m）×2m+1描述為將n的低m位清零，再左移一位。n%2m描述為取n的低m位。蝶型運算所對應的旋轉因子存儲器入口地址設為addr_w，對于N點FFT共需要N/2個旋轉因子，W rN=e（-j2π/N）r （r=0，1，…，N/2-1）。根據第m級蝶型運算所需旋轉因子的排列規律，旋轉因子存儲器入口地址應為：

addr_w=（n×2（log2N-1-m））（N/2） （5）

64點FFT旋轉因子有32個，共需要5位表示地址。第m級、第n個蝶型運算的旋轉因子地址可由邏輯移位的方法快速得到。將n（5位）左移位（5-m），低位補0，得到了在（0～31）中的addr_w。

1.10 塊浮點單元

塊浮點單元的實現思路是每級蝶型運算結果動態擴展但最大擴展2位。塊浮點單元對蝶型運算結果的高3位進行檢測，判斷當前結果動態范圍擴展位數，記錄當前級的最大擴展位數。下一級蝶型運算時，根據前一級的最大擴展位數，對讀出的數據進行定標，選取數據送入蝶型運算器。塊浮點單元將每一級運算結果動態范圍擴展位數進行累加，和FFT運算結果一同輸出。

1.11 FFT處理器功能仿真與設計驗證

仿真結果如圖6所示：

由仿真結果可以看出，該FFT處理器為串行流水線結構，各級運算模塊沒有實現并行運行。

圖6 時序仿真圖

2 實驗情況記錄

為驗證仿真結果的正確性，采用上述方法實現256點FFT處理器，同時為提高精度將輸入數據的實部和虛部采用16位二進制數。對函數：

x=cos（200πt）+cos（400π）

以120 MHz的頻率進行抽樣，取256點作為FFT處理器輸入數據進行快速傅里葉變換，并將其輸出結果與Matlab結果進行比較，結果如圖7～圖9所示。

圖7 抽樣函數及Matlab計算頻譜

圖8 FPGA計算頻譜

圖9 各采樣點相對誤差

3 結 語

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

參考文獻

[1]張輝. 張記龍.基-2 FFT處理器的FPGA實現[J].計算機與現代化.2009（9）：154-157.

[2]程佩青.數字信號處理教程[M].3版.北京：清華大學出版社，2007.

[3]袁俊泉.孫敏琪.曹瑞.Verilog HDL數字系統設計及其應用[M].西安：西安電子科技大學出版社，2002.

[4]謝彥林.可變點流水線結構FFT處理器的設計及其FPGA實現[D].西安：西安電子科技大學，2007.

[5]云霄.可配置FFT/IFFT處理器的設計及其FPGA構造[D].西安：西安電子科技大學，2009.

[6]蔡可紅.基于FPGA的FFT設計與實現[D].南京：南京理工大學，2006.

1.6 數據接收單元

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

1.7 運算單元

運算單元由蝶型運算器和運算RAM組成。蝶型運算器完成對輸入數據的蝶型運算，運算RAM作為FFT的中間數據緩存。蝶型運算器輸入數據為A=Ap+Aqj，B=Bp+Bqj，旋轉因子W rN=Wp+Wqj，蝶型運算輸出如式（3）所示。根據式（3），蝶型運算器可由一個復數乘法和兩個復數加（減）法器組成。為了提高運算速度采用并行運算，用四個實數乘法器、三個實數加法器、三個實數減法器組成。蝶型運算器實現框圖如圖5所示。蝶型運算各個模塊利用MAX+plusⅡ開發軟件中所提供的宏單元生成。

圖5 蝶形運算器

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

1.8 旋轉因子存儲單元

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

1.9 地址產生單元

地址產生單元產生蝶型運算兩個輸入數據和旋轉因子的地址。實現的方法是根據地址產生的算法，通過邏輯運算產生。前面已介紹本設計FFT實現結構為同址運算，即蝶型運算的結果仍然寫回輸入數據讀出單元。因此，將讀數據地址延遲若干時鐘周期，就可作為運算結果寫入地址。對于N點FFT運算，用m∈（0∧log2N-1），n∈（0∧N/2-1）表示第m級的第n個蝶型運算。addr_A，addr_B（addr_A

（4）

式中：（n/2m）×2m+1描述為將n的低m位清零，再左移一位。n%2m描述為取n的低m位。蝶型運算所對應的旋轉因子存儲器入口地址設為addr_w，對于N點FFT共需要N/2個旋轉因子，W rN=e（-j2π/N）r （r=0，1，…，N/2-1）。根據第m級蝶型運算所需旋轉因子的排列規律，旋轉因子存儲器入口地址應為：

addr_w=（n×2（log2N-1-m））（N/2） （5）

64點FFT旋轉因子有32個，共需要5位表示地址。第m級、第n個蝶型運算的旋轉因子地址可由邏輯移位的方法快速得到。將n（5位）左移位（5-m），低位補0，得到了在（0～31）中的addr_w。

1.10 塊浮點單元

塊浮點單元的實現思路是每級蝶型運算結果動態擴展但最大擴展2位。塊浮點單元對蝶型運算結果的高3位進行檢測，判斷當前結果動態范圍擴展位數，記錄當前級的最大擴展位數。下一級蝶型運算時，根據前一級的最大擴展位數，對讀出的數據進行定標，選取數據送入蝶型運算器。塊浮點單元將每一級運算結果動態范圍擴展位數進行累加，和FFT運算結果一同輸出。

1.11 FFT處理器功能仿真與設計驗證

仿真結果如圖6所示：

由仿真結果可以看出，該FFT處理器為串行流水線結構，各級運算模塊沒有實現并行運行。

圖6 時序仿真圖

2 實驗情況記錄

為驗證仿真結果的正確性，采用上述方法實現256點FFT處理器，同時為提高精度將輸入數據的實部和虛部采用16位二進制數。對函數：

x=cos（200πt）+cos（400π）

以120 MHz的頻率進行抽樣，取256點作為FFT處理器輸入數據進行快速傅里葉變換，并將其輸出結果與Matlab結果進行比較，結果如圖7～圖9所示。

圖7 抽樣函數及Matlab計算頻譜

圖8 FPGA計算頻譜

圖9 各采樣點相對誤差

3 結 語

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

參考文獻

[1]張輝. 張記龍.基-2 FFT處理器的FPGA實現[J].計算機與現代化.2009（9）：154-157.

[2]程佩青.數字信號處理教程[M].3版.北京：清華大學出版社，2007.

[3]袁俊泉.孫敏琪.曹瑞.Verilog HDL數字系統設計及其應用[M].西安：西安電子科技大學出版社，2002.

[4]謝彥林.可變點流水線結構FFT處理器的設計及其FPGA實現[D].西安：西安電子科技大學，2007.

[5]云霄.可配置FFT/IFFT處理器的設計及其FPGA構造[D].西安：西安電子科技大學，2009.

[6]蔡可紅.基于FPGA的FFT設計與實現[D].南京：南京理工大學，2006.