一種新的級聯(lián) FFT 算法

張大煒（中國電子進(jìn)出口總公司，北京 100037）

一種新的級聯(lián) FFT 算法

張大煒（中國電子進(jìn)出口總公司，北京 100037）

提出針對交叉項補償?shù)男录壜?lián) FFT 算法。通過交叉項補償處理及級聯(lián) FFT 運算順序的調(diào)整，解決了傳統(tǒng)算法數(shù)據(jù)量大的問題，以及柵瓣效應(yīng)的出現(xiàn)，同時降低了在進(jìn)行大數(shù)據(jù)量 FFT 運算時，單次處理負(fù)荷過大的問題。該算法在雷達(dá)、聲吶并行信號處理領(lǐng)域具有較好的應(yīng)用前景，理論推導(dǎo)和仿真驗證的結(jié)果都表明了該算法的可行性和有效性。

級聯(lián)FFT；交叉項抑制；能量泄露

0　引　言

快速傅里葉變換（FFT）出現(xiàn)以來，人們提出了多種以 FFT 算法為基礎(chǔ)的數(shù)字信號處理方法。其中，級聯(lián) FFT、掃頻窄帶分析法、復(fù)調(diào)制 Zoom FFT 法、直接抽取法等都是能夠進(jìn)行頻率細(xì)化的 FFT 算法［1］。在艦船電子信息系統(tǒng)中，F(xiàn)FT 作為基本的信號處理算法，在雷達(dá)、聲吶、導(dǎo)航、電子對抗等電子裝備中大量使用，是基本的時頻信號處理工具。FFT 運算作為主要的信號處理工具通常占據(jù)了大量的信號處理硬件資源。級聯(lián) FFT 通過將大序列數(shù)據(jù)分成兩級短序列數(shù)據(jù)進(jìn)行 FFT 處理的方式大大減輕了硬件上實現(xiàn)大序列FFT 的壓力。但是，分段處理的方法帶來了能量泄漏和頻率鏡像現(xiàn)象的出現(xiàn)。文獻(xiàn)［2］研究了 FFT 和級聯(lián)FFT 計算結(jié)果之間的差異，并對正弦信號的分析結(jié)果給出了一種補償方法，但在采用級聯(lián) FFT 對非正弦的一般信號進(jìn)行處理時，該文獻(xiàn)描述的補償方法受到一定的限制。文獻(xiàn)［3］提出了一種改進(jìn)的級聯(lián) FFT 算法，通過對數(shù)據(jù)的加窗和對輸出結(jié)果進(jìn)行相鄰段之間的平均和修正來減小誤差帶來的影響，但仍然沒有能夠完全避免能量泄漏和處理數(shù)據(jù)量增大的現(xiàn)象。

1　基本級聯(lián) FFT 的算法原理

級聯(lián) FFT 算法的理論基礎(chǔ)是通過將數(shù)據(jù)分段，通過兩級長度較短的 FFT 運算來實現(xiàn)一個序列全長度的FFT 結(jié)果，使得頻譜分辨能力，從而減少硬件資源上的消耗。

M × N 點序列信號 x（n + mN），n = 0，1，2，…，N-1；m = 0，1，2，…，M-1，利用級聯(lián) FFT 進(jìn)行處理可以表示為2 級 FFT 串聯(lián)的變現(xiàn)形式。通過矩陣化，一維序列可以表示為二維 M × N 矩陣的形式，對于 N 點表示的數(shù)據(jù)進(jìn)行 FFT 運算可以表示為：

對第一次 FFT 之后，相同頻率點上但不同段上的M 點數(shù)據(jù)做 FFT 分析，可以表示為：

其中 q = 0，1，2，…，N-1；p = 0，1，2，…，M-1，這樣就得到了基本級聯(lián) FFT 算法的結(jié)果。

對一個長度為 M × N 的時間序列信號 x（n + mN），n = 0，1，2，…，N-1；m = 0，1，2，…，M-1，進(jìn)行離散傅里葉變換之后得到的頻譜為：

其中 q = 0，1，2，…，N-1；p = 0，1，2，…，M-1考慮因子則式（3）可用兩級 FFT 形式表示為：

可以看到，式（4）與式（2）的表現(xiàn)形式相同。這就表明，級聯(lián) FFT 算法是在的情況下，全長度序列的 FFT 變換結(jié)果。也就是說，通過粗頻譜和細(xì)頻譜兩步分析，得到了全序列的全頻譜分析譜線，也即，在因子情況下通過兩級串聯(lián)的 FFT 序列x（n + mN）的頻譜。

2　基于交叉項補償?shù)募壜?lián) FFT 算法

2.1級聯(lián) FFT 算法的局限性

在上面的數(shù)學(xué)運算過程中，假定交叉項因子等于1，而實際上該因子是一個變量。根據(jù)推導(dǎo)，交叉項因子式以下面的形式存在并耦合到兩級運算當(dāng)中，即

該交叉項因子兩級變量 n 和 p 的函數(shù)。在 p ≠ 0 的情況下，該交叉項因子的結(jié)果不等于 1。如果不對第一段 FFT 運算的結(jié)果進(jìn)行修正，將會出現(xiàn)誤差，并帶來相鄰頻點上能量的擴散。通過分析和仿真計算，在p/M ≈ 1/2 附近時，將產(chǎn)生最大誤差，能量的泄漏大約在 50% 左右。

為解決粗頻譜分析時的能量泄漏，往往采用對第一次分段的數(shù)據(jù)進(jìn)行重疊，并通過加窗降旁瓣和對最終的輸出結(jié)果進(jìn)行幅度矯正才能達(dá)到較滿意的效果［1-2］。但是，為達(dá)到較好處理效果的 50% 以上的重疊比將會大大增加處理的運算量以及復(fù)雜程度。

2.2基于交叉項補償?shù)募壜?lián) FFT 算法

根據(jù)分析發(fā)現(xiàn)，對于誤差項的補償，將會大大影響處理的結(jié)果?？紤]到 FFT 預(yù)算的線性特性，矩陣化后數(shù)據(jù)的兩維傅里葉變化的順序并不影響最終的運算結(jié)果。因此，在將兩維變換順序調(diào)整之后，可以得到：

其中 X（p，n）為沿 m 方向進(jìn)行 FFT 計算的結(jié)果。

如果從 z 變換的角度來理解 FFT，F(xiàn)FT 實際上是從單位圓零相角開始，角度等分之后得到的 z 變換的數(shù)值。根據(jù)式（7）的結(jié)果，第 2 次變換時的 FFT 核函數(shù)變?yōu)?，也就是說第 2 次 FFT 變換取樣點的起始角頻率不同，是增加了一個分?jǐn)?shù)分量的 FFT 變換。這樣，如果交叉項帶來的分?jǐn)?shù)分量能夠得到補償，2 次 FFT 運算的結(jié)果就與全長度序列的FFT 結(jié)果相同。圖1 給出了新算法的實現(xiàn)步驟圖。圖2給出了 FFT 相角受交叉項影響的示意圖。

可以看出，改進(jìn)算法采用了與傳統(tǒng)算法不同的矩陣運算順序，同時增加了交叉項抑制和相位補償運算。新算法不需要對分段后的數(shù)據(jù)取重疊，只是通過復(fù)乘的操作就實現(xiàn)了交叉項抑制和補償，運算量相比傳統(tǒng)方法將會大大減小，同時還能得到較好的處理結(jié)果。

圖1　基于交叉項補償?shù)?FFT 算法示意圖Fig. 1　Diagram of FFT algorithm based on intersection factor compensation

圖2　交叉項影響相角示意圖Fig. 2　Diagram of influence of intersection factor to the phase angle

3　算法仿真及性能分析

根據(jù)上文的分析，給出基于交叉項補償?shù)募壜?lián)FFT 算法的實現(xiàn)流程如圖2 所示。

圖3　基于交叉項補償?shù)募壜?lián) FFT 處理流程圖Fig. 3　Flow chart of Cascade FFT algorithm based on intersection factor compensation

根據(jù)逆序級聯(lián) FFT 算法的步驟，下面給出對一個線性調(diào)頻信號進(jìn)行頻譜分析的實例，并對實現(xiàn)時的運算量大小進(jìn)行分析。仿真所用的線性調(diào)頻信號的帶寬為 80 Hz，信號持續(xù)時間為 5 s，采樣頻率為 200 Hz，采用的分段方式為 N = 50， M = 20 和 N = 10， M = 100。

表1 給出了基本算法在不取重疊、50% 重疊的計算結(jié)果和采用基于交叉項補償?shù)募壜?lián) FFT 算法進(jìn)行運算時的運算量對比。

從分析結(jié)果可看出，通過增加一次復(fù)乘操作來進(jìn)行交叉項補償，實現(xiàn)了 2 級 FFT 運算之間分?jǐn)?shù)分量的影響，并得到與一次全長度序列 FFT 完全相同的運算結(jié)果。相對傳統(tǒng)算法采用大重疊比實現(xiàn)柵瓣抑制的方法，新算法每次進(jìn)行 FFT 運算的長度可大大縮短，同時以較小的復(fù)乘運算換來了實現(xiàn)長序列 FFT 頻譜分析的問題，這對于雷達(dá)、聲吶、電子對抗等大量需要大數(shù)據(jù)量 FFT 運算的領(lǐng)域很有實際意義。

圖4　新算法進(jìn)行處理后的頻譜分析對比Fig. 4　Spectrum comparison of new algorithm

表1　兩種算法的運算量比較Tab. 1　Calculation amount comparison of two algorithm

4　結(jié)　語

本文在分析傳統(tǒng)的級聯(lián) FFT 算法的基礎(chǔ)上，提出一種新的基于交叉項補償?shù)募壜?lián) FFT 算法。該算法首先對輸入時間序列的數(shù)據(jù)進(jìn)行抽樣，然后對抽樣后數(shù)組內(nèi)的數(shù)據(jù)進(jìn)行 FFT 運算處理，然后進(jìn)行交叉項的補償，再對 FFT 之后不同數(shù)組間相同位置上的數(shù)據(jù)進(jìn)行第 2 次 FFT 處理，從而達(dá)到一次 FFT 運算能夠得到的效果。該算法能夠有效避免柵瓣效應(yīng)和能量泄漏現(xiàn)象給級聯(lián) FFT 運算帶來的影響，從而實現(xiàn)用短序列 FFT運算來進(jìn)行長序列 FFT 運算的結(jié)果。同傳統(tǒng)的級聯(lián)FFT 算法相比，改進(jìn)的算法能夠避免了原有算法的不足，同時在運算量上也避免了由于不同數(shù)據(jù)段之間重疊比過高所帶來的運算量的增加。

［1］PERRY R P， KAISER H W. Digital step transform approach to airborne radar processing［C］//Proceedings of IEEE National Aerospace and Electronics Conference. New York： IEEE， 1973：280-287.

［2］YIP P C Y. Some aspects of the Zoom transform［J］. IEEE Transactions on Computers， 1976， C-25（3）： 287-296.

［3］FJELL P O， LUNDE E B. A modified cascade fast Fourier transform in a spectrum analysing system［C］//Proceedings of IEEE international conference on ICASSP '77 acoustics， speech，and signal processing. Hartford， CT， USA： IEEE， 1997， （2）：873-876.

［4］HOYER E A， STORK R F. The Zoom FFT using complex modulation［C］//Proceedings of IEEE international conference on ICASSP '77 acoustics， speech， and signal processing. Hartford，CT， USA： IEEE， 1977， （2）： 78-81.

［5］WU K H， VANT M R. Extensions to the step transform SAR processing technique［J］. IEEE Transactions on Aerospace and Electronic Systems， 1985， AES-21（3）： 338-344.

［6］MCGOEY-SMITH A D， VANT M R. Modification of the SAR Step Transform algorithm［J］. IEEE Transactions on Aerospace and Electronic Systems， 1992， 28（3）： 666-674.

［7］MOREIRA A. Real-time Synthetic aperture radar （SAR） processing with a new subaperture approach［J］. IEEE Transactions on Geoscience and Remote Sensing， 1992， 30（4）： 714-722.

［8］SUN X B， YEO T S， ZHANG C B， et al. Time-varying steptransform algorithm for high squint SAR imaging［J］. IEEE Transactions on Geoscience and Remote Sensing， 1999， 37（6）：2668-2677.

［9］YEO T S， TAN N L， ZHANG C B， et al. A new subaperture approach to high squint SAR processing［J］. IEEE Transactions on Geoscience and Remote Sensing， 2001， 39（5）： 954-968.

A new inverse order cascade FFT algorithm

ZHANG Da-wei
（China National Electronics Import and Export Corporation， Beijing 100037， China）

A new Inverse Order Cascade FFT （IOCFFT） algorithm is provided in this paper based on the analysis of the principle and shortage to the traditional Cascade FFT algorithm. The order of the traditional Cascade FFT algorithm is changed to reduce the processing load and energy leakage phenomenon. The inverse order of the traditional Cascade FFT is adopted in this new algorithm and intersection factor compensation is done between the two FFT stages. The phenomenon of grating lobes and high processing load is avoided in this new method. The validity and feasibility of the new algorithm is tested by deduction of the formulation and simulation of the theory.

cascade FFT；inverse order cascade FFT；intersection factor

TN957

A

1672-7619（2016）05-0060-04

10.3404/j.issn.1672-7619.2016.05.013

2015-05-29；

2015-06-08

張大煒（1981-），男，博士，高級工程師，研究方向為信息系統(tǒng)工程及信息系統(tǒng)集成。