陳天峰，師劍軍，崔 瓊

（空軍工程大學(xué)防空反導(dǎo)學(xué)院，陜西 西安 710000）

0 引言

FFT（快速傅里葉算法）作為現(xiàn)代數(shù)字處理的一種核心算法，在廣闊的領(lǐng)域有著重要的作用，尤其是在雷達測速中。其中分辨率在很大的程度上決定了雷達測速的精度。隨著數(shù)字系統(tǒng)的發(fā)展，人們將傅里葉變換引進到數(shù)字系統(tǒng)，形成DFT（數(shù)字傅里葉算法）理論。但是，數(shù)字傅里葉算法的運算量極大，非常不利于實際應(yīng)用。20世紀(jì)60年代，Cooley和Tukey提出FFT算法解決了這個問題，將N點的DTF的乘法運算量由N2降為log2N［1］。自 從Cooley－Tukey算法提出后，新的算法不斷涌現(xiàn)，總體主要有兩種趨勢：一種是針對N是2的整次冪的算法，如基2算法、基4算法、實因子算法和分裂基算法；一種是針對N不是2的整次冪的算法［2］。在FFT運算中，分辨率與N點采樣時間長度成反比，即獲得更高的分辨率就大量地增加采樣點，進而使得采樣時間大幅提高影響了整個FFT的速度。無論哪種算法，現(xiàn)有的FFT改進算法大幅度提高了采樣后計算的速度，但是對于解決如何提高分辨率與延長采樣時間這對矛盾卻沒有行之有效的方法。本文針對此矛盾提出了一種基于數(shù)據(jù)重復(fù)使用的快速傅里葉算法。

1 快速傅里葉算法和數(shù)據(jù)重復(fù)

FFT是離散傅里葉變換的快速算法，可以將一個信號變換到頻域。有些信號在時域上是很難看出什么特征的，但是如果變換到頻域之后就很容易看出特征了。這就是很多信號采用FFT變換的原因。另外，F(xiàn)FT可以將一個信號的頻譜提取出來，這在頻譜分析方面也是經(jīng)常用的。

一個模擬信號，經(jīng)過ADC采樣后就變成了數(shù)字信號。接著，就可以進行FFT變換了。

假設(shè)采樣頻率為Fs，信號頻率為F，采樣點數(shù)為N。這樣，F(xiàn)FT之后的結(jié)果就是一個為N點的復(fù)數(shù)序列，每一個點對應(yīng)著一個頻率點。其中，第一個點代表的是直流分量（即0Hz），而最后一個點的再下一個點（即第N＋1個點，實際上是不存在的）則表示采樣頻率Fs。這中間被N－1個點平均分成N等份，每個點的頻率依次增加。如此，點n表示的頻率為：Fn＝（n－1）＊Fs／N。由上面的公式可以看出，F(xiàn)n所能分辨到的頻率為Fs／N［3］。

舉例來說，如果采樣頻率Fs為1 024Hz，采樣點數(shù)為1 024點，就FFT可以分辨到1Hz。1 024 Hz的采樣率采樣1 024點，剛好是1s。也就是說采樣1s的信號做FFT，可以分辨到1Hz。如果采樣2s并做FFT，則可以分辨到0.5Hz。

上述說明表明，在采樣頻率固定的情況下，如果FFT要提高頻率分辨率，就必須增加采樣點數(shù)，即增加采樣時間。

基于數(shù)據(jù)重復(fù)的快速傅里葉算法就是在基n的Cooley－Tukey算法基礎(chǔ)上得來的。

現(xiàn)假設(shè)有一離散序列x（n）。對于8點的數(shù)字傅里葉變換而言，計算公式為［4］：

由數(shù)字傅里葉的計算公式我們易知乘運算的計算量為82。

而對于同樣的序列，8點基2的FFT計算公式為：

如上述公式所表示，對于8點基2的FFT，后4點的計算的完全利用了前四點的計算數(shù)據(jù)。如此，F(xiàn)FT就將數(shù)字傅里葉的運算量降了下來。

改進算法在一次計算中不但使用了此次采集的數(shù)據(jù)，而且使用了經(jīng)過變換的前面若干次采集地數(shù)據(jù)，從而使得采樣點數(shù)相應(yīng)的增加，提高了FFT的分辨率。

為了高效地利用重復(fù)數(shù)據(jù)，先對FFT數(shù)據(jù)的特點進行分析。下面以8點基2的FFT為例，進行數(shù)據(jù)內(nèi)在特點分析。

現(xiàn)假設(shè)有一離散序列x（n）。8點基2的FFT計算過程如下：

同樣地對于更多點數(shù)的FFT而言，也會存在類似的關(guān)聯(lián)。數(shù)據(jù)的重復(fù)利用，意味著同一個信號會進行多次FFT變換?，F(xiàn)假設(shè)分別對第一個點到第八個點，第二個點到第九個點，依次到第八個點到第十五個點，共八組信號進行FFT變換。對于一直參與變換的第八個點，進行系數(shù)分析。8點基2的FFT將一次的采樣點一分為二，相應(yīng)的系數(shù)相同，故一次FFT的系數(shù)只列一半，如下所示：

上述系數(shù)，每行是一次變換中的系數(shù)，每列是每次變換中同一行的系數(shù)。對于這八次變換中，這第八個點構(gòu)成的數(shù)據(jù)每次變換的位置變化就是式（4）中每列的變換。反映到上述系數(shù)矩陣就是各行系數(shù)相同的列之間的替換。

再次帶著上述結(jié)論去觀察上述系數(shù)會發(fā)現(xiàn)隔行之間存在著簡單關(guān)系。第一列系數(shù)相同，第二列為依次乘以j，第三列依次取反，第四列為依次乘以－j。因為數(shù)據(jù)存儲時實部虛部分別存儲，所以其中第二列與第四列的數(shù)據(jù)可以通過交換實虛部并由條件適當(dāng)取反實現(xiàn)。

經(jīng)過上述簡單的變換，先前的數(shù)據(jù)便變得符合這次的變換運算的要求。即數(shù)據(jù)經(jīng)過變換后，就可以用于下次的FFT變換了。

2 數(shù)據(jù)重復(fù)快速傅里葉算法思路

對于新的FFT算法，其關(guān)鍵在于將過往數(shù)據(jù)變換并保存，其與傳統(tǒng)的流程對比如圖1。

圖1 未改進算法與改進算法對比Fig.1 Comparison between the not improved algorithm and the improved algorithm

通過增加了系數(shù)變換和數(shù)據(jù)存儲部分，使得對過往數(shù)據(jù)的利用成為了可能。同時，因為系數(shù)變換和數(shù)據(jù)存儲兩部分與系數(shù)添加是一種并行的關(guān)系，因此，這兩部分的添加并不會加大運算時間的負擔(dān)。

在具體的實現(xiàn)過程中，其實現(xiàn)的關(guān)鍵在于存儲器結(jié)構(gòu)和計算器的設(shè)計。具體而言，使用跳躍分級存儲，以及多路相加。同樣以8點基2的FFT為例，進行一段時間按之后的FFT的某個數(shù)據(jù)的存儲位置分別為7、5、3、1或者6、4、2、0。圖2以其中一路作為例子，圖解以便理解。

圖2 數(shù)據(jù)重復(fù)FFT存儲計算圖Fig.2 FFT repeated calculation data storage

在實際的設(shè)計過程中，采用流水線技術(shù)，使得系數(shù)變換部分可以在幾個周期內(nèi)順利完成。從而使得FFT的運算效率進一步加大。

具體而言，系數(shù)添加部分到系數(shù)變換部分的數(shù)據(jù)傳輸應(yīng)該比這兩部分向結(jié)果傳輸數(shù)據(jù)要有一個固定的延遲，以便于整體數(shù)據(jù)傳輸?shù)牧鲿掣咝АＭ瑫r系數(shù)添加部分和系數(shù)變換部分采用并行運算也是一種有效的方法。

現(xiàn)針對8點基2的FFT，第一次FFT變換使用第一個到第八個數(shù)據(jù)，第二次使用第三個到第八個數(shù)據(jù)。第二次FFT變換只采樣兩個點，對于同樣采樣率的兩點采樣FFT，根據(jù)分辨率公式，分辨率提高了4倍。

現(xiàn)在將8點基2的FFT向外推廣。對于p點基m的FFT。一次FFT變換系數(shù)只分析p／m個。對于不同批次的FFT變換，同一個采樣點的數(shù)據(jù)系數(shù)變化就是式（4）中單行中各列的變換。由式，可知當(dāng)k固定時（即計算固定一個頻率點時），為了使k的取值不會使得數(shù)據(jù)重復(fù)使用的難度增加，取2 （n1－n2）／p為1／2或者1／2的整數(shù)倍。即在數(shù)據(jù)中，兩個數(shù)據(jù)相距p／4或者p／4整數(shù)倍個（在p／m個數(shù)據(jù)中相距p／4m），就可以使得FFT各行數(shù)據(jù)系數(shù)變換簡單易行。

對于實際的一個p點基m的FFT變換來說，數(shù)據(jù)選擇相距p／4時，采樣點變作原先的1／4，數(shù)據(jù)選擇相距p／4的a倍時，采樣數(shù)點變?yōu)樵鹊腶／4（a＜m）。對于后續(xù)運算，因為只有原先數(shù)據(jù)的一部分需要重新與系數(shù)相乘，故時間上也會大大減少。

3 仿真分析

現(xiàn)在我們以256點的FFT為例，采用Matlab軟件中的Simulink模塊搭建對0.7·sin（2·π·50·t）＋sin（2·π·120·t）的信號加上一個隨機干擾進行3次FFT變換仿真，分別是未進行算法改進的FFT，通過改進采樣點數(shù)提高2倍的FFT以及采樣點數(shù)提高4倍的FFT。仿真結(jié)果臺圖3、圖4、圖5［6］。

圖3 未進行算法改進的FFTFig.3 FFT algorithm without the improvement

圖4 經(jīng)算法改進的采樣點數(shù)提高2倍的FFTFig.4 The algorithm to improve the sampling points increased 2times FFT

圖5 經(jīng)算法改進的采樣點數(shù)提高4倍的FFTFig.5 The algorithm to improve the sampling points increased 4times FFT

通過上述3圖的對比我們可以發(fā)現(xiàn)在未經(jīng)算法改進的FFT中，頻率在120附近的頻率點被很好地分離了出來，而頻率在50附近的頻率點則未能在噪聲中分離出來。而經(jīng)過了算法改進使得采樣點提高的FFT中，兩個頻率點均獲得了很好的分離，其中4倍采樣點的FFT中兩個頻率點的幅值均高于噪聲幅值3倍以上，很好地分離了頻率點，為后續(xù)的工作提供了良好的基礎(chǔ)。

本文設(shè)計的基于數(shù)據(jù)重復(fù)利用的FFT算法，其使用有兩種方式：一種是減少采樣點，這種方式不僅減少了采樣時間，同時在現(xiàn)有的FFT算法上大大地減少了乘法的運算，因而有效地提高了運算速度，因為沒有減少參與運算的采樣點數(shù)，故而分辨率不變；而另一種方式則是采樣點不變，但是參與運算的采樣點數(shù)大大增加，因而大幅度地提高了FFT的分辨率，而每次FFT的后繼運算部分，只需重新計算新采樣的點數(shù)的乘法，故而沒有因為參與運算的采樣點數(shù)的增加而降低速度。

另一方面，算法對于結(jié)構(gòu)的要求并不比傳統(tǒng)的FFT高出多少，只是添加一個系數(shù)變換部分。這些對于現(xiàn)在的FPGA系統(tǒng)來說是極易實現(xiàn)的。所以說，本算法同樣有經(jīng)濟的優(yōu)點，便于實際應(yīng)用。

事實上，如果在不考慮系數(shù)變換的簡易性的基礎(chǔ)上，分辨率的提高力度可以進一步加強。但是，這無疑會大大地增加系數(shù)變換的結(jié)構(gòu)和控制復(fù)雜程度。

4 結(jié)論

本文提出基于數(shù)據(jù)重復(fù)利用的FFT算法。該算法通過對過往數(shù)據(jù)的變換再利用增加了一次FFT運算的點數(shù)。仿真表明該算法可以在不明顯增加FFT的運算時間的基礎(chǔ)上有效地提高FFT的分辨率。該算法不但解決了FFT算法改進中一直無人問津的分辨率與采樣時間之間的矛盾，使得FFT的分離效果更為明顯，為高速系統(tǒng)的FFT部分的設(shè)計提供了一種簡單經(jīng)濟可行的選擇；而且為FFT算法改進提供了一種新的方向。

［1］Altera.Alter Corporation Cyclone Device Handbook［M］.US：Alter Corpration，2004.

［2］蘇濤，吳順君，廖曉群.高性能數(shù)字信號處理器與高速實時信號處理［M］.西安：西安電子科技大學(xué)出版社，1999.

［3］胡廣書.數(shù)字信號處理［M］.北京：清華大學(xué)出版社，2003

［4］李春林，伍勇.基于FFT與自相關(guān)函數(shù)的快速功率譜估計方法［J］.艦船電子工程，2011，31（10）：108－111.LI Chunlin，WU Yong.Fast power spectrum estimation method based on FFT and autocorrelation function［J］.Ship Electronic Engineering，2011，31（10）：108－111.

［5］賈中云，李秀梅，董文.“數(shù)字信號處理”中采樣定理的教學(xué)探索［J］.中國電力教育，2012（29）：79－80.

［6］吳迪，朱金秀，朱昌平.“數(shù)字信號處理”課程的教學(xué)改革與實踐［J］.中國電力教育，2012（32）：78－80.