高抗噪性的SFFT-DT快速捕獲算法

張浩冉 徐 穎 羅瑞丹 毛 億

（1.中國科學院空天信息創(chuàng)新研究院，北京 100094；2.中國科學院大學光電學院，北京 100049；3.空中交通管理系統(tǒng)與技術國家重點實驗室，江蘇南京 210007）

1 引言

全球衛(wèi)星導航系統(tǒng)（Global Navigation Satellite System，GNSS）可向全球用戶提供高質量的定位、導航和授時服務，目前已在各個領域得到了廣泛應用［1-3］。導航接收機在實現(xiàn)導航定位功能之前，必須先對導航信號進行捕獲、跟蹤與解調，其中，信號捕獲過程消耗著接收機的大量資源，據(jù)統(tǒng)計在整個導航定位過程中大約有30%至75%的資源消耗來自于信號捕獲過程。隨著GPS 定位芯片在各種便攜式設備中的普及，功耗逐漸成為評價其適用性的關鍵指標之一［4-5］。為此本文設計了一種針對GNSS直接序列擴頻信號的快速捕獲算法，在降低捕獲過程資源消耗的同時具有良好的信號檢測性能。

目前常見的捕獲算法有時域線性捕獲、基于FFT 的并行頻率捕獲和并行碼相位捕獲［6］算法等。其中，基于FFT 的并行碼相位捕獲（FFT-Capture）算法由于可以通過一次變換實現(xiàn)偽碼相位的全搜索，目前最為常用。但當數(shù)據(jù)長度較長時，其計算量仍過于龐大，有學者提出將計算效率更高的SFFT 引入到并行碼相位捕獲算法中。SFFT 算法最早由文獻［7-8］提出，該算法主要通過對時域信號進行頻譜重排、加窗、混疊降采樣以及FFT 以較小的計算量將原始信號的傅里葉系數(shù)投影到低維空間中。對于稀疏信號（頻域僅有少數(shù)大值點），每個投影點中很大概率只包含一個大值點，通過對投影結果進行定位（找到它在原始頻譜中的位置）和估值，可以以較小的計算量得到大值點在原始頻譜中的位置及幅值。目前該算法已在頻譜分析［9］、圖像處理［10-11］、5G［12］通信和雷達探測［13］等領域得到了廣泛應用。

文獻［14］首次將稀疏快速傅里葉變換的混疊降采樣過程應用于信號捕獲中，提出了一種快速同步算法（QuickSync），但當衛(wèi)星信號較弱時，需要進行長時間相干積分來提升算法的信號檢測能力［15］。文獻［16］用逆快速傅里葉變換（Inverse Sparse Fast Fourier Transform，ISFFT）替換了并行碼相位捕獲中的IFFT過程，從而提升了算法的捕獲效率。但由于SFFT 中的定位與估值過程對噪聲容忍能力均比較差，導致算法的總體抗噪性能仍然較弱。文獻［17］提出一種用相關計算代替SFFT 估值過程的捕獲算法（SFFT-Correlate），使得其抗噪性能較文獻［16］有所提升，但并沒有對噪聲容忍能力較差的定位過程進行優(yōu)化，改善此過程可進一步提升算法的抗噪性能。

本文提出了一種新的SFFT-DT 并行碼相位捕獲算法，該算法利用DFFT［18］及SFFT 進行聯(lián)合大值點定位，去除了SFFT 中對噪聲容忍能力較差的定位循環(huán)與估值循環(huán)過程，在降低捕獲過程計算量的同時保證了算法具有較好的信號檢測能力。本文首先對SFFT 捕獲算法的不足進行了詳細分析，然后對SFFT-DT 算法進行了論述，最后結合理論分析及實驗仿真對設計算法進行了驗證。

2 SFFT捕獲算法性能分析

2.1 基于SFFT的快速捕獲算法

如圖1 所示，SFFT 一般被用于并行碼相位捕獲算法的逆變換過程。記R（k）為混頻信號（由輸入數(shù)字中頻信號與本地復制載波信號相乘得到的信號）與本地復制的偽碼信號分別進行FFT 變換后共軛相乘得到的結果，此時SFFT 并行碼相位捕獲算法的逆變換過程主要分為以下幾步：

i：首先利用哈希映射以少量運算將輸入信號的傅里葉系數(shù)投影到低維空間中，其主要過程為：

（1）對R（k）進行頻譜重排及窗函數(shù)濾波，即

其中x∈RN表示輸入信號，σ-1表示關于模N的數(shù)論倒數(shù)［7］，τ∈[0，N-1]為一隨機數(shù)。Fk表示平坦窗函數(shù)，可以有效減弱頻譜泄露對IFFT 變換結果的影響。

（2）對yk進行頻域混疊及IFFT變換，即

其中B為頻域混疊因子，由式（2）至（4）可知，利用哈希映射可將參與IFFT變換的數(shù)據(jù)長度由原來的N維降低到B維，從而大大降低逆變換過程的計算復雜度。

其中hσ(i)和oσ(i)分別表示哈希函數(shù)及偏移函數(shù)［7］，即

iii：對i和ii步驟進行L=log2N次循環(huán)，得到大值點可能的位置集合Ir={I1，I2，…，IL}。統(tǒng)計Ir中各個下標出現(xiàn)的次數(shù)，記為Ti={i|count(i=k)，k∈Ir}，找出其中出現(xiàn)次數(shù)大于L/2的下標，記為最終定位結果Is={i|Ti≥L/2}。利用估值循環(huán)對Is中的點進行估值，即

找出其中幅值最大的點，其下標值即為大值點在原始IFFT結果中的位置。

通過ISFFT變換，可將逆變換過程的計算復雜度由原來的O(Nlog2N)降為，計算復雜度僅為IFFT 算法的，且數(shù)據(jù)長度越長，ISFFT 捕獲算法的計算優(yōu)勢越明顯，進而實現(xiàn)導航信號的快速捕獲。

2.2 SFFT并行碼相位捕獲算法不足

雖然利用ISFFT 替代并行碼相位捕獲的IFFT過程后，算法的計算效率得到了有效提升，但基于SFFT的并行碼相位捕獲算法還存以下兩個問題：

（1）算法的抗噪性能較差：如式（1）和（2）所示，在已有的SFFT 捕獲算法中，為保證各次哈希逆映射結果間除大值點外其余位置不會重合，在每次哈希映射前需對輸入信號進行頻譜重排。對于寬帶信號，該過程不會對哈希映射結果產生較大影響。但由于偽碼相關信號屬于窄帶信號，如圖2 所示其能量主要分布在頻寬為2.046 MHz 的主峰中，頻譜重排會使得信號能量近似均勻的分布在整個頻域上，導致信號加窗后會產生較大信噪比損失，從而造成算法的抗噪性能變差。

（2）算法流程比較繁瑣：現(xiàn)有的SFFT 算法是針對所有信號的一個通用設計，對于偽碼相關信號這種超稀疏信號（時域相關結果僅有一個峰值），定位循環(huán)和估值循環(huán)過程顯得有些繁瑣和不合時宜，此時可通過其他的方法來對此過程進行進一步優(yōu)化，以提升算法的抗噪性能同時降低其實現(xiàn)的復雜度。

上述兩個問題限制了SFFT 算法在并行碼相位捕獲算法中的應用，需根據(jù)導航信號的特點對其加以改進。

3 高抗噪性的SFFT-DT快速捕獲算法

為解決SFFT 捕獲算法中定位循環(huán)信噪比損失較大、算法流程繁瑣的問題，提出了一種新的基于SFFT-DT 的快速捕獲算法。該算法去除了SFFT 捕獲算法中對算法抗噪性能影響較大的定位循環(huán)與估值循環(huán)過程，轉而通過DFFT 的變換結果與SFFT的哈希映射結果的交集來確定大值點位置，在提升捕獲算法抗噪性能的同時簡化了其實現(xiàn)流程。

3.1 本文算法介紹

本文算法的主要流程如下：

步驟1：首先將本地偽碼與混頻信號的FFT 變換結果共軛相乘，得到R（k），即

步驟2：將R（k）與窗函數(shù)F(k)相乘，得到加窗后信號。對Rc(k)進行頻域混疊后得到Rcd(k)，對Rcd(k)進行IFFT變換后得到時域降采樣結果cd(n)，即Rc(k)

為避免時域變換結果發(fā)生頻譜泄露，本文仍采用平坦窗函數(shù)對信號進行加窗。

步驟3：當cd(n)大于閾值時，記其下標為k1，利用式（8）進行哈希逆映射，得到大值點在原始IFFT變換中可能的位置集合I1，即

步驟4：對R（k）直接進行降采樣，即Rm(k)=R(mk)，對Rm(k)進行IFFT 變換后得到其時域變換結果cd1(n)，記其大值點下標為k2，則其在原始IFFT變換中大值點的可能位置為

步驟5：計算大值點的位置：km=I1∩I2。當兩者下采樣因子選取適當時，I1，I2存在唯一交點，即為大值點所在位置。

如圖4 所示，去除定位循環(huán)過程后，步驟3 得到的結果存在一個連續(xù)的模糊度p=N/B。步驟4 得到的結果模糊度為m，這m個位置點以N/m為步長等間隔分布在整個變換域上，通過對兩者做交集可以快速得到大值點的真實位置。

3.2 算法參數(shù)設計

3.2.1 混疊因子B及降采樣因子m設計

在步驟2 中，為保證頻域混疊結果Rcd(k)中各點疊加的數(shù)據(jù)長度一致，最好滿足B可以整除N，即

如當N=10404時，B合適的取值有B={153，289，306，578，612，867，1734.......}等。B越小，算法的計算量越小，但算法抗噪性能也會隨之下降，因此B的選擇應綜合考慮算法的計算量和抗噪性能要求。

為保證步驟4 的定位結果I2與步驟3 的定位結果I1僅有一個交點，需滿足m≤B，則m的最終取值范圍可表示為m∈[1，B]。同時由于參與IFFT 變換的信號長度由原來的N降到了N/m，因此會使得算法產生約10 log10(m)dB 的信噪比損失，在實際應用中需根據(jù)算法的信噪比要求對參數(shù)m加以選擇。

3.2.2 窗函數(shù)參數(shù)設計

為保證步驟2的頻域混疊不會導致時域降采樣結果產生信息損失，取平坦窗函數(shù)的時域主瓣寬等于時域降采樣間隔N/B。同時由于去除了定位過程的log2N次循環(huán)，本文算法的計算復雜度與窗函數(shù)長度w（w=supp(F)，supp(x)表示信號x的支撐集）的關系由原來的O(wlog2N)降為了O（w），我們可以選擇更長的窗函數(shù)來對輸入信號進行濾波，在此我們取w=N。此時平坦窗F（k）可由高斯窗g（k）和標準窗h（k）相乘得到［7］，即

其中δ表示平坦窗函在其通帶內的波動幅度，一般取δ=1/N。

3.3 算法性能分析

3.3.1 信噪比性能分析

本節(jié)主要對去除定位循環(huán)的頻譜重排過程所帶來的信噪比增益進行分析，加窗后信號Rc(k)在整個頻域上的信噪比可近似表示為

其中f=2π/w表示信號頻率，Af表示頻域信號幅值，fe表示本地信號與輸入信號的頻差，表示頻域信號噪聲功率。假設窗函數(shù)在頻域的截止頻率為fc，且頻譜重排后信號能量近似均勻分布在整個變換域上，那么在窗函數(shù)的主瓣內，由去除定位循環(huán)的頻譜重排過程所帶來的信噪比增益可近似表示為

公式（19）的信噪比增益隨采樣率fs及窗函數(shù)截止頻率fc的變換關系如圖5所示。

結合式（18）、（19）和圖5可知，當窗函數(shù)截止頻率fc一定時，SNRgain，avg（去頻譜重排所帶來的信噪比增益）與采樣率fs成正相關，這是因為信號的采樣率越高，頻譜重排會造成頻域信號R(k)的能量越分散，進而導致加窗信號的能量損失越大，本文去除頻譜重排的信噪比性能優(yōu)勢就更加明顯。當采樣頻率fs一定時，SNRgain，avg與窗函數(shù)截止頻率fc呈負相關，這是因為窗函數(shù)的主瓣范圍越寬，頻譜重排對加窗信號能量損失的影響越弱。當窗函數(shù)截止頻率fc=fs時，SNRgain，avg近似為0，這是因為此時整個頻域都被窗函數(shù)的通帶所包含，頻譜重排對加窗信號能量損失的影響不大。

結合式（15）至（17）可知，平坦窗函數(shù)在頻域上的截止頻率可近似表示為fc=3Bfs/N（窗函數(shù)90%以上能量集中在此范圍內）。為保證算法的低運算量，要求B遠小于N，即fc取值較小，則由圖5可知此時本文算法與SFFT-Correlate 算法的頻譜重排變換相比，會有較大的信噪比性能提升。

由圖3 與步驟5 可知，為最終確定大值點位置，算法需同時得到正確的定位集合I1和I2。則算法的最終捕獲概率PSFFT-DT與步驟3 定位成功的概率PSFFT和步驟4定位成功的概率PDFFT成正比，即

因此當步驟3 的信噪比增益為SNRgain，avg時，本文算法最終的抗噪性能也會得到相同分貝的提升。

3.3.2 計算復雜度分析

若混頻信號可以表示為x∈CN，則步驟1 需要2N+Nlog2N次復數(shù)乘法和2Nlog2N次復數(shù)加法，步驟2 需要次復數(shù)乘法和(Blog2(B)+N-B)次復數(shù)加法，步驟3 線性映射的計算量為2（逆映射區(qū)間是連續(xù)的，不需一一映射）。步驟4 需要B1log2B1次復數(shù)加法和B1/2 log2B1次復數(shù)乘法，其中B1=N/m，步驟5 的計算量為m，m表示降采樣因子。假設整個搜索過程的非相干累加次數(shù)為S，偽碼FFT結果預先存儲在接收機中，由于步驟4和步驟5在整個捕獲過程中參與運算的次數(shù)很少，因此本文算法的計算復雜度可為O(SNlog2N+Blog2B+2N-B)，F(xiàn)FT-Capture 算法的計算復雜度為O(SNlog2N+Nlog2N)，SFFT-Correlate 捕獲算法的計算復雜度為，a為一常數(shù)。

4 仿真實驗

為驗證本文算法的抗噪性能和捕獲速度，本節(jié)利用仿真數(shù)據(jù)對設計算法的性能進行驗證分析，具體仿真參數(shù)如表1所示。

表1 實驗仿真參數(shù)Tab.1 Experimental simulation parameters

首先根據(jù)3.2.1 節(jié)對頻域混疊因子B進行取值，然后對不同B下步驟3 定位成功的概率PSFFT進行統(tǒng)計，若哈希逆映射結果I1包含大值點位置，則認為步驟3 變換成功。在不同信噪比下各進行1000 次仿真，仿真結果及不同B下算法的計算復雜度分別如圖6、圖7所示。

從圖6 可以看出，隨著B的增大，在相同信噪比下步驟3得到正確結果的概率PSFFT也隨之增加。但由于B的大小與算法的計算復雜度成正相關，如圖7 所示，綜合考慮算法計算復雜度及PSFFT，取B=612。則結合式（19）、（20）及圖5 可知，本文算法去除頻譜重排所獲得的信噪比增益大約為4.5 dB。

在不同的降采樣因子m下，對步驟4 定位成功的概率PDFFT進行仿真，在不同信噪比下各進行1000次獨立實驗，統(tǒng)計結果如圖8所示。

從圖8 可以看出，步驟4 的定位成功概率PDFFT與m的取值成反比。如當m=2 時，PDFFT在輸入信號信噪比大于-19.5 dB 時達到了95%以上。而當m=3 時，PDFFT在輸入信號信噪比大于-18 dB 時才達到了95%以上。在實際捕獲中，應根據(jù)實際需要對m的取值進行選擇。

現(xiàn)在我們對算法的總體抗噪性能PSFFT-DT進行仿真驗證，在不同信噪比下對上述三種算法分別進行1000 次獨立仿真，并對其捕獲概率進行統(tǒng)計，結果如圖9所示。

從圖9 可知，當m=1 時，本文算法與FFTCapture 算法的捕獲概率均在輸入信號信噪比大于-22 dB 時達到了95%以上。當m=2 時，本文算法的捕獲概率在輸入信號信噪比大于-19 dB 時達到了95%以上。當m=4時，本文算法與SFFT-Correlate算法的捕獲概率均在輸入信號信噪比大于-17 dB時達到了95%以上。通過上述對比可知，在捕獲概率高于95%的前提下，本文算法的抗噪性能最大可比SFFT-Correlate 算法高5 dB 左右。這是因為本算法去除了SFFT-Correlate 算法中對噪聲容忍能力較差的定位循環(huán)過程，使得加窗后信號的能量得到了更好的保留。此時三種算法的計算量對比如表2所示。

由表2可以看出，本文算法的計算量較文獻［6］的FFT 捕獲算法減少了約43%，較文獻［17］的SFFT-Correlate 算法減少了約19%。同時由于本文算法在IFFT 過程中沒有復雜的定位循環(huán)和估值循環(huán)，因此硬件實現(xiàn)的復雜度更低，更利于工程實現(xiàn)。

結合3.3 節(jié)分析、表2、圖6 至圖9 的仿真結果可知，本文算法的抗噪性能與文獻［17］的SFFT 捕獲算法相比有較大提高。與經(jīng)典的FFT 捕獲算法相比，當兩者抗噪性能近似相同（捕獲概率大于95%的前提下）時，本文算法計算量更小。

表2 運算量對比Tab.2 Comparison of calculation amount

5 結論

本文針對SFFT 捕獲算法中頻譜重排過程對捕獲算法抗噪性能的影響進行了分析，并利用偽碼相關信號大值點唯一的特征，提出了一種抗噪性能更好的高抗噪性快速捕獲算法。該算法用DFFT 替代了SFFT 捕獲算法中原有的對噪聲容忍能力較弱的定位循環(huán)過程，使得加窗后頻域信號的能量得到了最大程度的保留。理論分析及仿真結果均表明，本文算法不僅進一步降低了捕獲算法的計算量，而且與已有的SFFT 捕獲算法相比本文算法的抗噪性能也得到了較大提升，適用于導航信號的快速捕獲。