[發明專利]I/O個數不相等的快速非均勻離散傅里葉變換方法及系統

有效

• 申請號: 201410673810.3
• 申請日: 2014-11-21
• 公開（公告）號: CN104462017A
• 公開（公告）日: 2015-03-25
• 發明（設計）人: 劉喆;俞詠江;張曉玲
• 申請（專利權）人: 電子科技大學
• 主分類號: G06F17/14
• 分類號: G06F17/14
• 代理公司: 成都宏順專利代理事務所(普通合伙) 51227
• 代理人: 周永宏

技術領域

本發明屬于數值計算領域，具體涉及一種I/O個數不相等的快速非均勻離散傅里葉變換方法及系統。

背景技術

非均勻離散傅里葉變換(Non-uniform?discrete?Fourier?transform,簡寫為NUDFT)是輸入/輸出(I/O)采樣位置為非均勻實數的離散傅里葉變換。由于I/O位置非均勻，傳統快速傅里葉變換方法(Fast?Fourier?transform,簡寫FFT)無法直接用以提高NUDFT實現效率；而快速非均勻傅里葉變換方法(Non-uniform?fast?Fourier?transform,簡寫為NUFFT)在I/O非均勻采樣位置進行過采樣及插值操作，而后再利用FFT實現NUDFT。NUFFT方法具有高效、精確等優點，因此廣泛應用于譜方法(spectral?method)、磁共振成像(magnetic?resonance?imaging)、雷達信號處理等領域。

目前，有代表性的NUFFT實現方法有美國學者A.Dutt等提出的NUFFT實現方法(見文獻1：A.Dutt,V.Rokhlin,“Fast?Fourier?transforms?for?nonequispaced?data”,SIAM?J.SCI.COMPUT.,Vol.14,no.6,pp.1368-1393,Nov.1993)，J.A.Fessler等提出的NUFFT實現方法(見文獻2：J.A.Fessler,B.P.Sutton,IEEE?Trans.Signal?Processing,Vol.51,no.2,pp.560-574,2003)，Q.Liu等提出的NUFFT實現方法(見文獻3：Q.H.Liu,N.Nguyen,An?accurate?algorithm?for?nonuniform?fast?Fourier?transforms(NUFFT’s).IEEE?Microwave?and?Guided?Wave?Letters,Vol.8,no.(1),pp.18-20,1998)等。這些方法不同之處在于使用了不同的插值方法。然而，這些方法都無法實現I/O個數不相等的快速NUDFT處理。在實際應用中，如合成孔徑雷達信號處理大場景數據時(見文獻4：Franceschetti,G.,R.Lanari,and?E.S.Marzouk,“A?new?two-dimensional?squint?mode?SAR?processor,IEEE?Transactions?on?Aerospace?and?Electronic?Systems,vol.32,pp.854-863,1996.)，常需要高效計算I/O個數不相等的NUFFT處理。因此，現有的NUFFT實現方法難以滿足實際應用需求。

發明內容

為解決上述技術問題，本發明提出一種I/O個數不相等的快速非均勻離散傅里葉變換方法。

本發明技術方案為：I/O個數不相等的快速非均勻離散傅里葉變換方法，在I/O非均勻采樣位置進行過采樣及插值操作后，利用調頻Z變換實現I/O個數不相等的非均勻快速傅里葉變換；具體包括以下步驟：

S1：初始化NUDFT參數，包括：待變換的輸入數據x，I/O非均勻位置α_m和ω_k，I/O采樣點個數M和K；

其中，x表示待變換的輸入數據，即輸入的離散序列，α_m表示第m個輸入采樣點位置，ω_k表示第k個輸出采樣點位置，M表示輸入采樣點個數，K表示輸出采樣點個數，k＝0,1,...,K-1，m＝0,1,...,M-1，α_m∈[-M/2,M/2-1]，ω_k∈[-K/2,K/2-1]；

初始化NUFFT參數，包括：插值參數G，b和Q；

其中，G是過采樣倍數，b是大于1/2的實數，Q是插值點總個數；

S2：根據步驟S1中的NUDFT參數及NUFFT參數以及公式：