基于CORDIC算法的流水線型FFT處理器設(shè)計(jì)

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

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

責(zé)任編輯:時(shí) 雯

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

1 基二FFT算法原理分析

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

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

圖1 k=8的時(shí)間抽取FFT流圖

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

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

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

2.1 RAM的乒乓讀取

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

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

2.2 蝶形運(yùn)算的實(shí)現(xiàn)

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

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

圖3 蝶形運(yùn)算實(shí)現(xiàn)方法

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

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

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

圖4 圓周CORDIC算法流程圖

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

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

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

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

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

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

2.5 控制信號(hào)與數(shù)據(jù)對(duì)準(zhǔn)

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

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

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

3 仿真與驗(yàn)證

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

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

MYMreadmemb(″binarydata.txt″，datamem)

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

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

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

對(duì)比分析可以證實(shí)該設(shè)計(jì)基本滿足了FFT對(duì)頻譜分析的要求。其幅度值不等是因?yàn)樵谟布O(shè)計(jì)中采用了防止溢出的限幅措施。

4 總結(jié)

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

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

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

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

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

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