基于稀疏傅里葉變換的快速捕獲方法

張春熹， 李先慕， 高爽

(北京航空航天大學 儀器科學與光電工程學院, 北京 100083)

衛星信號捕獲是衛星接收機內基帶信號處理的第一步，其目的是完成可見衛星的確認并估算出接收信號碼相位和載波頻率的粗略值，為跟蹤通道提供參數的初始化值。常用的捕獲方法有基于時域的串行搜索、基于頻域的并行頻率搜索和基于頻域的并行碼相位搜索[1-2]。基于時域的串行搜索方法硬件實現復雜度低，但是其所需運算量大、花費時間長；基于頻域的并行頻率搜索在載波頻率方向上進行并行搜索，而在碼相位方向上進行串行搜索，捕獲的運算量在載波頻率方向減小，縮短了捕獲時間；基于頻域的并行碼相位搜索是目前軟件接收機平臺中常用的捕獲方法，通過快速傅里葉變換(Fast Fourier Transform, FFT)實現在碼相位方向上的并行搜索，大幅度提高了衛星信號捕獲的速度。

在基于頻域的并行搜索方法中，FFT運算是實現衛星信號快速捕獲的核心[3-4]，為了改善衛星信號捕獲性能，產生了基4FFT和分裂基FFT算法[5-7]，通過優化FFT相關運算的效率，提高了捕獲速度；但是這些優化的FFT算法的整體時間復雜度仍然是以點數、點數對數的乘積為漸近上限，在運算時間和捕獲性能上并沒有明顯的改善。

由于衛星的偽隨機碼具有強自相關性，當本地復制偽碼和輸入信號的偽碼相位接近時才能產生很強的相關值，其余搜索單元的相關值都接近于零以致可以忽略。因此對于某顆衛星的二維搜索而言，捕獲的相關值具有稀疏的特性，從而可以將稀疏傅里葉變換(Sparse Fourier Transform, SFT)引入并行搜索過程中。

SFT是由MIT的Hassanieh等[8]于2012年提出，其核心思想是利用信號在頻域中的稀疏特性，通過加窗—混疊—重構等步驟實現算法的亞線性處理。近年來，SFT在語音處理、醫學成像和通信等領域得到應用[9-10]，而在衛星信號捕獲中的應用主要是理論分析及仿真驗證。文獻[11]提出了利用SFT進行GPS信號捕獲的方法，并進行了可行性分析，但是沒有給出具體的捕獲方案和結果。文獻[12-13]提出了一種基于SFT的快速捕獲與干擾抑制聯合技術，簡化了算法中快速傅里葉反變換(Inverse Fast Fourier Transform，IFFT)的計算量，但是沒有簡化輸入信號與本地信號FFT算法的運算量。文獻[14]利用SFT實現了GPS信號的快速捕獲，并分析了降采樣因子對捕獲速度的提升，但是其對降采樣因子的選取不太合理。

本文通過分析衛星信號捕獲中的相關值具有稀疏的特性，在基于頻域FFT的并行碼相位的基礎上，提出了基于SFT的快速捕獲方法，利用實測的中頻數據通過衛星軟件接收機進行了捕獲實驗的驗證，實驗結果表明本文方法可以降低捕獲運算的復雜度，提高捕獲效率。

1 衛星信號捕獲過程分析

衛星接收機中的信號捕獲是一個三維搜索：衛星號(PRN碼)、碼相位和載波頻率[15]。當本地碼和信號的碼相位對齊的情況下，并且本地載波頻率和輸入信號的載波頻率接近，才能產生很強的相關值。圖1為某顆GPS衛星信號捕獲成功時的各個搜索單元上的IFFT結果。很明顯，在該衛星的二維搜索范圍中出現了一個峰值，其不但明顯高于其他各個搜索單元的積分值，而且也超過了捕獲門限，可以說明對該衛星的信號已被成功捕獲，同時也證明了捕獲結果的輸出值具有稀疏的特性。

基于FFT的并行碼相位捕獲方法通過FFT實現頻域的循環相關，在碼相位空間內實現并行搜索捕獲功能，衛星信號捕獲的效率得到極大的提高。由于FFT相關軟件編程模塊已經成熟并廣泛應用，基于FFT的并行碼相位捕獲方法成為衛星軟件接收機中常用的捕獲方法，其實現原理框圖如圖2所示。

采用基于頻域FFT并行碼相位捕獲方法，其實現的運算步驟如下：

步驟1將數字中頻信號和本地載波發生器輸出的正弦載波QNCO和余弦載波INCO混頻，分別得到同相I支路信號Im和正交Q支路信號Qm，以I支路為實部、Q支路為虛部得到基帶的復信號s(t)。

圖1 某顆GPS衛星捕獲成功結果Fig.1 Successful acquisition result of a GPS satellite

圖2 基于FFT的并行碼相位捕獲方法框圖Fig.2 Block diagram of parallel code phase search method based on FFT

步驟2對步驟1中得到的基帶復信號s(t)做FFT變換。

步驟3對本地偽碼發生器輸出的偽碼信號c(t)做FFT得到C(f)，并求復數共軛得到C*(f)。

步驟4將步驟2和步驟3得到的結果相乘并做IFFT變換。

步驟5對步驟4得到的IFFT結果取模，得到相關值，對相關值進行門限檢測。如果相關值的峰值超過捕獲門限值，則捕獲到了信號，并得到了信號的碼相位和載波頻率值；反之，如果相關值的峰值不足夠強，信號沒有捕獲成功，需要重新設置本地載波發生器的頻率，重復步驟1～步驟4。

上述方法在完成一個處理(2次FFT和1次IFFT)后能夠得到全部偽碼相位的結果，所以實現了偽碼域的并行處理，而多普勒頻率維度的搜索依然是串行的，即每次改變本地載波發生器的頻點，則需要完成一次新的處理，即2次FFT、1次IFFT和N次乘加運算。

2 稀疏傅里葉變換原理

SFT是利用信號在頻域中的稀疏特性，簡化FFT運算過程的一種快速有效的算法。在信號具有稀疏性且關鍵信息處在較大譜峰上時，SFT技術可以在獲得與傳統FFT相似的頻譜分析效果的同時降低其運算復雜度。隨著FFT點數的增大，SFT具有的非線性運算復雜度特性將使其在運算方面的優勢變得更加明顯。

2.1 頻域降采樣

SFT算法應用了信號在頻域中的“稀疏”特性，利用頻域降采樣減少信號輸入長度，提高FFT運算過程的效率。

設x(n)是長度為n的離散序列，X(k)為其頻域表示，其時域混疊結果為

(1)

式中：整數B能整除n。令p=n/B，則有

Y(k)=X(kn/B)k∈[0,B-1]

(2)

由式(1)、式(2)可得，時域的混疊對應頻域的降采樣，反之，時域的降采樣引起頻域的混疊。圖3闡釋了這一對應關系。

圖3 混疊和降采樣示意圖Fig.3 Schematic of aliasing and sub-sampling

2.2 稀疏傅里葉變換運算過程

SFT包括頻域重排、窗函數濾波、頻域降采樣、定位、估值及迭代等運算過程，如圖4所示。

1) 頻域重排。取隨機參數σ、τ(τ為奇數)

圖4 SFT運算過程Fig.4 Calculation process of SFT

2) 窗函數濾波。將q(n)通過濾波器后有：y(n)=q(n)g(n)。其中，窗函數濾波器通常選用多爾夫-切比雪夫濾波器或者理想的box-car濾波器，其特點滿足過渡帶陡峭、通帶平滑、運算量小和大系數集中。

3) 頻域降采樣。以因子p將y(n)混疊，對混疊后信號作B點FFT運算得Z(k)=Y(kn/B)。

4) 哈希映射。定義哈希函數和偏移量滿足：hσ′(k)=round(σ′kB/n)，oσ′(k)=σ′k-hσ′(k)(n/B)，round(·)表示取整操作。

5) 定位。將Z(k)中最大的譜峰表示為集合J，對于J中的每個元素，令集合H滿足條件：H={k∈[n]|hσ′(k)∈J}。

3 基于稀疏傅里葉變換的快速捕獲方法分析

3.1 稀疏傅里葉變換優化的捕獲方法實現過程

通過第2節對SFT的分析，結合圖1中捕獲成功的結果，由于偽碼信號的強自相關性特性，在FFT相關運算處理過程中，IFFT的變換域具有稀疏的特性，因此可以利用SFT算法對FFT相關過程進行優化。

另外，輸入中頻信號的頻域X(k)并不具有稀疏特性，僅使用加窗—混疊—重構的方法不能使運算效率最大化提升。考慮利用2.1節中“時域的混疊對應頻域的降采樣”思想對這一過程進行優化。圖5為基于SFT的快速捕獲方法。

具體算法實現步驟如下：

步驟1將數字中頻信號和本地載波發生器輸出的正弦和余弦載波混頻，得到基帶的復信號。

圖5 基于SFT的快速捕獲方法示意圖Fig.5 Schematic of fast acquisition method based on SFT

步驟3對混疊信號s(pt)做N/p點FFT。

步驟4對本地偽碼做N點FFT，輸出結果為C(f)。以因子p對其進行降采樣，得C(pf)，取其共軛C*(pf)。

步驟5將步驟3和步驟4的結果相乘，并將乘積做IFFT變換。

步驟6步驟5的IFFT輸出結果為混疊結果，對其取模并進行門限判決。得出p個可能的譜峰位置，通過比較這p個坐標的相關值，得到相關值最大的坐標點，其對應的載波頻率和碼相位即為捕獲結果。

3.2 時間復雜度分析

3.1節的基于SFT捕獲方法在完成一個處理后能夠得到全部偽碼相位的結果。步驟2混疊過程需要N次加法；步驟3降采樣后N/p點FFT的運算量為(N/2p)lb(N/p)次復數乘法和(N/p)·lb(N/p)次復數加法；步驟4對本地偽碼信號的預處理為N點FFT運算量；步驟5相乘操作需要N/p次乘法，稀疏IFFT運算量同N/p點FFT；步驟6鑒別唯一解的運算量為pN/p=N。同基于FFT捕獲方法對比，得到單個相關結果，共需要[N+(N/p)(1+lb(N/p))+(N/2)lbN]次復數乘法和[N(1+lbN)+2(N/p)lb(N/p)]次復數加法。其中，本地偽碼發生器輸出的偽碼信號做FFT可以進行預處理，考慮其運算不占用算法時間。則采用FFT和SFT的捕獲方法時間復雜度分別為O(NlbN)和O((N/p)lb (N/p))，由此可見基于SFT的快速捕獲方法大大降低了相關的運算量，運算量減小到原來算法的plbp倍，且隨著數據長度N的增加，其效率提升更加明顯。

4 驗證實驗及分析

為了驗證基于SFT的快速捕獲方法的效率，利用實測的中頻數據對其進行測試。數據中頻頻率為9.584 MHz，采樣頻率為38.192 MHz。方法在基于MATLAB的軟件接收機上實現[16]，仿真實驗對比了基于FFT的并行碼相位捕獲方法和基于SFT的快速捕獲方法的捕獲性能。

圖6為信號長度T為1 ms，降采樣因子p=1、2、4時PRN3衛星捕獲結果，表1為捕獲實驗結果對比。

由圖6和表1可以看出，在信號長度為1 ms時，基于FFT的并行碼相位捕獲方法捕獲結果為：偽碼相位(采樣點)為3.421 2×104，多普勒頻率為2.5 kHz，運行時間約為0.26 s。

降采樣因子p=2時，檢測到的偽碼相位(采樣點)為1.511 5×104，對應的p=2個可能的偏移位置為N=1.511 5×104、3.421 1×104，分別計算這2個可能偏移位置各自的相關值，N=3.421 1×104點相關值遠遠大于N=1.511 5×104點的相關值；多普勒頻率為2.5 kHz，算法運行時間約為0.14 s，相對于基于FFT的并行碼相位捕獲方法，程序運行效率提高約1.86倍。

圖6 衛星捕獲結果(T=1 ms，p=1,2,4)Fig.6 Satellite acquisition results (T=1 ms，p=1,2,4)

p 值偽碼相位/(104采樣點)多普勒頻率/kHz峰值/107運算時間/s13．42122．53．2960．26248121．51152．54．8260．14356940．55695．05．7460．093134

降采樣因子p=4時，檢測到的偽碼相位(采樣點)為0.556 9×104，對應的p=4個可能的偏移位置為N=0.556 9×104、1.511 7×104、2.466 5×104、3.421 3×104，分別計算這4個可能偏移位置各自的相關值，N=3.421 3×104點相關值遠遠大于其他3個點的相關值；多普勒頻率為5.0 kHz，算法運行時間約為0.09 s，但是其多普勒頻率估計誤差較大，超出多普勒頻率搜索步長。

為了驗證運算效率隨著數據長度N的增大而提升，圖7給出了T=2ms的捕獲實驗結果，表2為T=2 ms時p=1、2、4的捕獲實驗結果對比。圖8給出了T=5 ms的捕獲實驗結果，表3為T=5 ms時p=1、2、4的捕獲實驗結果對比。

圖7 衛星捕獲結果(T=2 ms，p=1,2,4)Fig.7 Satellite acquisition results (T=2 ms，p=1,2,4)

由圖7、圖8和表2、表3可以得出，同T= 1ms時捕獲結果分析一致，基于SFT的快速捕獲方法可以實現成功捕獲。T=2 ms時，程序運行效率相對基于FFT的并行碼相位捕獲方法提升了2.04倍。T=5 ms時，程序運行效率提升到原來的2.2倍。說明隨著數據長度N的增大而運算效率提升更加明顯。

表2 衛星捕獲實驗結果(T=2 ms)

圖8 衛星捕獲結果(T=5 ms，p=1,2,4)Fig.8 Satellite acquisition results (T=5 ms，p=1,2,4)

p 值偽碼相位/(104采樣點)多普勒頻率/kHz峰值/107運算時間/s13．42132．515．341．20567421．51172．520．310．54681640．55685．024．700．274991

5 結 論

本文在分析衛星捕獲輸出相關值結果具有“稀疏”特性的基礎上，將稀疏傅里葉變換(SFT)引入基于FFT的并行碼相位捕獲方法中，提出了基于SFT的快速捕獲方法，仿真結果表明：

1) 本文方法可以實現衛星信號的快速捕獲，與基于FFT的并行碼相位捕獲方法相比，算法性能提升到原來的2倍。

2) 當參與運算的信號長度N增大時，算法的運算效率提升更加明顯。T=1 ms時，算法運算效率提升約1.86倍；T=2 ms時，算法運算效率提升2.04倍；T=5 ms時，算法運算效率提升2.2倍。

為了更好地驗證本文方法，需要利用不同載噪比的中頻信號進行驗證。

參考文獻 (References)

[1] 魯郁.北斗/GPS雙模軟件接收機原理與實現技術[M].北京:電子工業出版社,2016:119-157.

LU Y.BDS/GPS dual-mode software receiver principles and realizing[M].Beijing:Publishing House of Electronics Industry,2016:119-157(in Chinese).

[2] 謝鋼.GPS原理與接收機設計[M].北京:電子工業出版社,2009:349-375.

XIE G.Principles of GPS and receiver design[M].Beijing:Publishing House of Electronics Industry,2009:349-375(in Chinese).

[3] COOLEY J W,TUKEY J W.An algorithm for the machine calculation of complex Fourier series[J].Mathematics of Computation,1965,19(90):297-301.

[4] RAO K R,KIM D N,HWANG J J.Fast Fourier transform-algorithms and applications[M].Berlin:Springer,2010:15-40.

[5] AKOPIAN D.Fast FFT based GPS satellite acquisition methods[J].IEE Proceedings:Radar Sonar and Navigation,2005,152(4):277-286.

[6] SPANGENBERG S M,SCOTT I,MCLAUGHLIN S,et al.An FFT-based approach for fast acquisition in spread spectrum communication systems[J].Wireless Personal Communications,2000,13(1-2):27-55.

[7] SAGIRAJU P K,RAJU G V S,AKOPIAN D.Fast acquisition implementation for high sensitivity global positioning systems receivers based on joint and reduced space search[J].IEE Proceedings: Radar Sonar and Navigation,2008,2(5):376-387.

[8] HASSANIEH H, INDYK P,KATABI D,et al.Nearly optimal sparse Fourier transform[C]∥Proceedings of the 44th ACM Symposium on Theory of Computing.New York:ACM,2012:563-578.

[9] 那美麗,周志剛,李霈霈.基于稀疏傅里葉變換的低采樣率帶寬頻譜感知[J].電子技術應用,2015,41(11):85-88.

NA M L,ZHOU Z G,LI P P.Wideband spectrum sensing at low sampling rate based on the sparse Fourier transform[J].Application of Electronic Technique,2015,41(11):85-88(in Chinese).

[10] 王雄.基于稀疏傅里葉變換的水聲快速解調算法研究[D].北京:北京理工大學,2015:39-42.

WANG X.Fast demodulation algorithm of underwater acoustic based on the sparse Fourier transform[D].Beijing:Beijing Institute of Technology,2015:39-42(in Chinese).

[11] HASSANIEH H, INDYK P,KATABI D,et al.FASTER GPS via the sparse Fourier transform[C]∥Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.New York:ACM,2012:353-364.

[12] MA Y,BU X Y,HAN H C，et al. Combined algorithm of acquisition and anti-jamming based on SFT[J].Journal of Systems Engineering and Electronics,2015,26(3):431-440.

[13] 龔巧嫻.基于SFT的快速捕獲與干擾抑制聯合算法研究[D].北京:北京理工大學,2015:20-32.

GONG Q X.Research on combined algorithm of acquisition and anti-jamming based on SFT[D].Beijing:Beijing Institute of Technology,2015:20-32(in Chinese).

[14] RAO M V G,RATNAM D V.Faster acquisition technique for software-defined GPS receivers[J].Defence Science Journal,2015,65(1):5-11.

[15] PARKINSON B,SPILKER J. Global positioning system: Theory and applications[M].Reston:AIAA,1996:245-325.

[16] BORRE K,AKOS D M,BERTELSEN N.A software-defined GPS and Galileo receiver[M].Berlin:Springer,2007:75-86.