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

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

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

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

級(jí)聯(lián)FFT；交叉項(xiàng)抑制；能量泄露

0　引　言

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

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

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

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

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

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

對(duì)一個(gè)長(zhǎng)度為 M × N 的時(shí)間序列信號(hào) 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）可用兩級(jí) FFT 形式表示為：

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

2　基于交叉項(xiàng)補(bǔ)償?shù)募?jí)聯(lián) FFT 算法

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

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

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

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

2.2基于交叉項(xiàng)補(bǔ)償?shù)募?jí)聯(lián) FFT 算法

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

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

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

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

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

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

3　算法仿真及性能分析

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

圖3　基于交叉項(xiàng)補(bǔ)償?shù)募?jí)聯(lián) FFT 處理流程圖Fig. 3　Flow chart of Cascade FFT algorithm based on intersection factor compensation

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

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

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

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

表1　兩種算法的運(yùn)算量比較Tab. 1　Calculation amount comparison of two algorithm

4　結(jié)　語(yǔ)

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

［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-），男，博士，高級(jí)工程師，研究方向?yàn)樾畔⑾到y(tǒng)工程及信息系統(tǒng)集成。