基于CORDIC算法的流水線型FFT處理器設計

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

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

責任編輯:時 雯

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

1 基二FFT算法原理分析

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

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

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

2 基二FFT的FPGA實現

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

圖2 FFT硬件實現流程

2.1 RAM的乒乓讀取

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

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

2.2 蝶形運算的實現

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

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

圖3 蝶形運算實現方法

2.3 利用CORDIC算法實現旋轉因子乘法器

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

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

圖4 圓周CORDIC算法流程圖

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

當旋轉向量和x軸重合時，即y0=0時，其最終結果可表示為

表1 預旋轉角度表

2.4 地址產生單元與ROM存儲設計

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

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

2.5 控制信號與數據對準

圖5 ROM存儲設置示意圖

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

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

3 仿真與驗證

利用MATLAB產生的數據作為FFT的輸入激勵。設計輸入信號為100 kHz與300 kHz的疊加，采樣頻率為1 MHz，FFT點數定為32，將采樣值轉換成二進制數據，并寫入txt文件，如下文所示:

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

MYMreadmemb(″binarydata.txt″，datamem)

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

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

圖6 MODELSIM輸出結果驗證

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

4 總結

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

［1］俞卞章.數字信號處理［M］.2版.西安:西北工業大學出版社，2002.

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

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

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

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