一種新的級聯 FFT 算法

張大煒（中國電子進出口總公司，北京 100037）

一種新的級聯 FFT 算法

張大煒（中國電子進出口總公司，北京 100037）

提出針對交叉項補償的新級聯 FFT 算法。通過交叉項補償處理及級聯 FFT 運算順序的調整，解決了傳統算法數據量大的問題，以及柵瓣效應的出現，同時降低了在進行大數據量 FFT 運算時，單次處理負荷過大的問題。該算法在雷達、聲吶并行信號處理領域具有較好的應用前景，理論推導和仿真驗證的結果都表明了該算法的可行性和有效性。

級聯FFT；交叉項抑制；能量泄露

0　引　言

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

1　基本級聯 FFT 的算法原理

級聯 FFT 算法的理論基礎是通過將數據分段，通過兩級長度較短的 FFT 運算來實現一個序列全長度的FFT 結果，使得頻譜分辨能力，從而減少硬件資源上的消耗。

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

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

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

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

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

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

2　基于交叉項補償的級聯 FFT 算法

2.1級聯 FFT 算法的局限性

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

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

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

2.2基于交叉項補償的級聯 FFT 算法

根據分析發現，對于誤差項的補償，將會大大影響處理的結果。考慮到 FFT 預算的線性特性，矩陣化后數據的兩維傅里葉變化的順序并不影響最終的運算結果。因此，在將兩維變換順序調整之后，可以得到：

其中 X（p，n）為沿 m 方向進行 FFT 計算的結果。

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

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

圖1　基于交叉項補償的 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　算法仿真及性能分析

根據上文的分析，給出基于交叉項補償的級聯FFT 算法的實現流程如圖2 所示。

圖3　基于交叉項補償的級聯 FFT 處理流程圖Fig. 3　Flow chart of Cascade FFT algorithm based on intersection factor compensation

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

表1 給出了基本算法在不取重疊、50% 重疊的計算結果和采用基于交叉項補償的級聯 FFT 算法進行運算時的運算量對比。

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

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

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

4　結　語

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

［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-），男，博士，高級工程師，研究方向為信息系統工程及信息系統集成。