基于數(shù)據(jù)重復(fù)的快速傅里葉算法改進(jìn)

陳天峰，師劍軍，崔 瓊

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

0 引言

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

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

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

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

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

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

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

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

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

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

而對(duì)于同樣的序列，8點(diǎn)基2的FFT計(jì)算公式為：

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

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

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

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

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

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

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

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

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

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

圖1 未改進(jìn)算法與改進(jìn)算法對(duì)比Fig.1 Comparison between the not improved algorithm and the improved algorithm

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

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

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

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

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

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

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

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

3 仿真分析

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

圖3 未進(jìn)行算法改進(jìn)的FFTFig.3 FFT algorithm without the improvement

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

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

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

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

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

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

4 結(jié)論

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

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

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

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

［4］李春林，伍勇.基于FFT與自相關(guān)函數(shù)的快速功率譜估計(jì)方法［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ù)字信號(hào)處理”中采樣定理的教學(xué)探索［J］.中國電力教育，2012（29）：79－80.

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