李靖宇，許江寧，李 豹，曹可勁

(1.海軍工程大學(xué) 導(dǎo)航工程系，湖北 武漢 430033;2.海軍91821部隊，廣東 潮州 515700)

責(zé)任編輯:時 雯

快速傅里葉變換是DSP的核心技術(shù)之一，作為時域和頻域轉(zhuǎn)換的基本運算，是數(shù)字譜分析的必要前提，在雷達(dá)、觀測、跟蹤、高速圖像處理、保密無線通信和數(shù)字通信等領(lǐng)域有廣泛應(yīng)用。FPGA(現(xiàn)場可編程門陣列)內(nèi)部含有大量邏輯單元和高速RAM模塊，使FFT算法可以靈活快速地實現(xiàn)，并具有很高的性能。針對快速信號處理的要求及FPGA器件的特點，提出了一種基于CORDIC算法的基二流水線結(jié)構(gòu)的FFT處理器設(shè)計方法。

1 基二FFT算法原理分析

設(shè)序列長度是為N=2M，M為正整數(shù)。如此可以將序列x(n)分解成兩組，偶數(shù)項為一組，奇數(shù)項為一組，可以得到兩個N/2點的子序列，即:x1(r)=x(2r)，x2(r)=x(2r+1)，r=0，1，…，N/2 －1;相應(yīng)地將 DFT 運算分為兩組［1］。

繼續(xù)照上式將序列分解，直到最后是二點的DFT為止。8點FFT蝶形圖如圖1所示。

圖1 k=8的時間抽取FFT流圖

2 基二FFT的FPGA實現(xiàn)

在FPGA上實現(xiàn)流水線型FFT處理器，其主要結(jié)構(gòu)模塊包括:輸入的乒乓RAM模塊、蝶形運算模塊、旋轉(zhuǎn)因子乘法模塊(本文用CORDIC算法實現(xiàn))、倒序輸出模塊、旋轉(zhuǎn)相角(φ)ROM，還有信號流程控制模塊和地址產(chǎn)生器模塊。具體如圖2所示。

圖2 FFT硬件實現(xiàn)流程

2.1 RAM的乒乓讀取

為了使輸入數(shù)據(jù)無等待周期，采取了乒乓操作。這種結(jié)構(gòu)是將輸入數(shù)據(jù)流不斷寫入存儲深度為2N的存儲單元，用RAM寫地址值的最高位來區(qū)分低、高存儲部分，數(shù)據(jù)首先輸入的低位存儲區(qū)，當(dāng)?shù)蚇個存儲單元存儲滿之后，數(shù)據(jù)開始存入高N個存儲單元，同時開始讀取低N個存儲單元的數(shù)據(jù)，由于讀寫頻率相同，低存儲單元的數(shù)據(jù)讀完后高存儲單元已經(jīng)寫滿，此時則開始將數(shù)據(jù)寫入低存儲單元，讀出高存儲單元。如此循環(huán)往復(fù)，一旦RAM存滿最初N個數(shù)據(jù)后，RAM就可以不間斷的輸出按要求分組的N個數(shù)據(jù)點。

由于FFT的蝶形運算特性，要求最終輸出結(jié)果是順序輸出，即:RAM的讀地址應(yīng)該是其同步寫地址的低N－1位二進(jìn)制碼的求逆。如此即可將按正常次序存入RAM的數(shù)據(jù)進(jìn)行逆序輸出。其中RAM寫地址和RAM讀地址均由地址產(chǎn)生單元產(chǎn)生，而要保證RAM讀、寫同步速，在進(jìn)行求逆時不能有延時，因此對求逆運算要采用組合邏輯電路或者是函數(shù)運算來實現(xiàn)。

2.2 蝶形運算的實現(xiàn)

由于讀入蝶形單元的數(shù)據(jù)是串行輸入的，而蝶形單元涉及到前后不同地址的數(shù)據(jù)的加減運算，因此必須對先前輸出的數(shù)據(jù)進(jìn)行寄存，利用兩個選擇控制信號對輸入數(shù)據(jù)進(jìn)行運算控制，如圖3所示［2］。

在選擇器控制信號sel0的控制下選擇對輸入數(shù)據(jù)或輸入數(shù)據(jù)與寄存器輸出相加的結(jié)果進(jìn)行寄存。當(dāng)sel0為高電平時選擇對輸入數(shù)據(jù)進(jìn)行寄存，低電平時對輸入數(shù)據(jù)與寄存器輸出的數(shù)據(jù)相加結(jié)果進(jìn)行寄存。sel1信號控制對寄存器輸出數(shù)據(jù)或寄存器與輸入數(shù)據(jù)之差進(jìn)行輸出。移位寄存器深度可表示為2m－1，m為蝶形運算所在的級數(shù)。每級蝶形運算都有sel0、sel1兩個控制信號，所有控制信號由控制單元產(chǎn)生。sel1信號為sel0取反后的信號，其頻率為主控制時鐘的2m分頻，m為該蝶形所在的級數(shù)。每級蝶形運算輸出即送往下一級蝶形運算，在輸入下一級之前需與旋轉(zhuǎn)因子進(jìn)行相乘。

圖3 蝶形運算實現(xiàn)方法

2.3 利用CORDIC算法實現(xiàn)旋轉(zhuǎn)因子乘法器

旋轉(zhuǎn)因子的獲取有兩種方法:一種是將先所需要的旋轉(zhuǎn)因子計算預(yù)先存儲在ROM中，再通過ROM尋址獲取后和相應(yīng)的數(shù)據(jù)相乘。本文采用的是實時計算的方法，即將需要旋轉(zhuǎn)的角度值預(yù)先存儲在ROM中，通過ROM尋址將需要旋轉(zhuǎn)的角度送入CORDIC計算器，直接計算出數(shù)據(jù)與cosφ和sinφ乘積值。實時計算的方法對計算點數(shù)不多的FFT，具有很大的靈活性，也可以節(jié)省存儲空間。

CORDIC 算法的原理如式(3)所示［3－4］:CORDIC算法的流水線實現(xiàn)流程如圖4所示。

圖4 圓周CORDIC算法流程圖

式(3)中(x0，y0)為旋轉(zhuǎn)向量點的坐標(biāo)值，經(jīng)過逐步迭代移位相加運算后可以得到式(5)

當(dāng)旋轉(zhuǎn)向量和x軸重合時，即y0=0時，其最終結(jié)果可表示為

表1 預(yù)旋轉(zhuǎn)角度表

2.4 地址產(chǎn)生單元與ROM存儲設(shè)計

地址產(chǎn)生單元主要用來產(chǎn)生RAM的讀、寫地址和旋轉(zhuǎn)相角ROM的讀地址。主要是根據(jù)時鐘的步速(串行數(shù)據(jù)的輸入步速)產(chǎn)生RAM的寫地址，并按照求逆的要求將寫地址的低N－1位二進(jìn)制數(shù)按位序求逆產(chǎn)生對應(yīng)RAM讀地址。按照寫地址的最高位是1還是0判定讀地址的最高位是0還是1，保證其進(jìn)行乒乓讀取。ROM讀地址的產(chǎn)生與RAM讀地址的產(chǎn)生同步同時產(chǎn)生，但不用求逆，即與RAM寫地址的低N－1位完全相同，并以N點為周期進(jìn)行循環(huán)產(chǎn)生。

由于ROM地址產(chǎn)生器產(chǎn)生的地址是與RAM寫地址的低位N－1值相等的，即數(shù)據(jù)開始串行輸入蝶形單元的順序值。而經(jīng)過蝶形單元運算后產(chǎn)生了數(shù)據(jù)延遲，等到N個數(shù)據(jù)完全移出一級蝶形單元時，ROM的地址值已經(jīng)重新開始計數(shù)，由此產(chǎn)生了ROM的循環(huán)尋址，即:將相角數(shù)據(jù)φ預(yù)先存入ROM時要考慮延遲后的尋址，ROM地址重新歸零后對應(yīng)的存儲單元要存放的數(shù)據(jù)是對應(yīng)延遲輸出的幾個相角值。如此就像循環(huán)右移一樣，將本應(yīng)該存儲地址末尾的內(nèi)容拿到存儲地址的前幾個地址，如圖5所示。

2.5 控制信號與數(shù)據(jù)對準(zhǔn)

圖5 ROM存儲設(shè)置示意圖

在每級蝶形單元的交叉運算中都需要控制信號sel0，sel1，總計需要2M個控制時鐘，M為基二運算過程中的蝶形運算中所需的級數(shù)。從數(shù)據(jù)開始輸入的同時開始計數(shù)、分頻，由于每級不同的延遲，數(shù)據(jù)從第m級輸入到輸出由于中間有移位寄存器的延遲作用會對數(shù)據(jù)的輸出造成延遲，延遲量可以表述為2m－1，其中2m－1為移位寄存器的深度，讀入數(shù)據(jù)過程中本身就有一個數(shù)據(jù)延遲，因此第m級的數(shù)據(jù)輸出相對于開始輸入蝶形單元的數(shù)據(jù)總延遲量可以表述為1+2+…+2m－1+2m。而控制數(shù)據(jù)輸出的sel1信號不斷經(jīng)過時鐘的2的整數(shù)次冪得到的，此時會產(chǎn)生各級輸出數(shù)據(jù)(下級的輸入)與下級蝶形運算控制信號的上升沿未能對準(zhǔn)的情況，因此需要將各級數(shù)據(jù)在輸出過程中進(jìn)行不同單位的延遲(增加寄存次數(shù))以保證蝶形單元的輸出數(shù)據(jù)與下級蝶形單元的選擇器控制時鐘對齊，只有輸入數(shù)據(jù)與蝶形單元的控制時鐘的上升沿對準(zhǔn)，才能保證數(shù)據(jù)進(jìn)行正確的寄存和運算。

在蝶形運算過程中，由于是控制時鐘的關(guān)系，按照二進(jìn)制碼逆序輸入的數(shù)據(jù)最終在FFT處理器輸出是十進(jìn)制的逆序，即先輸出的是第N個數(shù)據(jù)，最后才輸出第一位數(shù)據(jù)。要得到正確的順序輸出在最后一級蝶形運算后需要進(jìn)行倒序處理，同樣為保證輸出的連續(xù)性也采取了乒乓操作，只是此時有實、虛兩部分?jǐn)?shù)據(jù)，存儲空間要比輸入時的RAM大一倍。

3 仿真與驗證

利用MATLAB產(chǎn)生的數(shù)據(jù)作為FFT的輸入激勵。設(shè)計輸入信號為100 kHz與300 kHz的疊加，采樣頻率為1 MHz，F(xiàn)FT點數(shù)定為32，將采樣值轉(zhuǎn)換成二進(jìn)制數(shù)據(jù)，并寫入txt文件，如下文所示:

在testbench中利用verilog語言的系統(tǒng)函數(shù)MYM-readmemb將txt文件中的二進(jìn)制數(shù)據(jù)讀入存儲數(shù)組datamem，在采樣時鐘的控制下，將datamem中數(shù)據(jù)串行讀入FFT處理器，作為輸入激勵，如下文所示:

MYMreadmemb(″binarydata.txt″，datamem)

利用verilog系統(tǒng)函數(shù)MYMfdisplay將FFT處理器輸出的實部和虛部數(shù)據(jù)寫入txt文件，方便利用MATLAB讀取分析。部分代碼如下:

利用MATLAB繪圖對比分析結(jié)果如圖6所示。

圖6 MODELSIM輸出結(jié)果驗證

對比分析可以證實該設(shè)計基本滿足了FFT對頻譜分析的要求。其幅度值不等是因為在硬件設(shè)計中采用了防止溢出的限幅措施。

4 總結(jié)

主要討論了基二FFT在FPGA上的實現(xiàn)方法，結(jié)合CORDIC算法，在FPGA芯片上實現(xiàn)了FFT處理器，解決了設(shè)計過程中的乒乓讀取，CORDIC旋轉(zhuǎn)運算，ROM存儲，數(shù)據(jù)與控制時鐘的對準(zhǔn)等問題。并進(jìn)行了MODELSIM和MATLAB的聯(lián)合仿真，仿真結(jié)果表明該設(shè)計滿足了FFT處理的處理要求。在10 MHz采樣率的情況下完成32點的FFT運算需要14.45 μs，滿足實時處理的要求，并且具有可以繼續(xù)擴展到更高的點數(shù)，具有推廣價值。下一步將考慮更為節(jié)約資源的方法，使其用于具體的裝備中。

［1］俞卞章.數(shù)字信號處理［M］.2版.西安:西北工業(yè)大學(xué)出版社，2002.

［2］高亞軍.基于FPGA的數(shù)字信號處理［M］.北京:電子工業(yè)出版社，2012.

［3］UWE M.Digital signal processing with field programmable gate arrays［M］.劉凌，譯.北京:清華大學(xué)出版社，2003.

［4］劉福奇，劉波.Verilog HDL應(yīng)用程序設(shè)計［M］.北京:電子工業(yè)出版社，2009.

［5］文婧媛，徐欣鋒.基于CORDIC算法的高速可配置FFT的FPGA實現(xiàn)［J］.微電子學(xué)與計算機，2010，27(3):24－28.