FFT在導航信號捕獲中的應用分析?

徐 浩 曾芳玲（電子工程學院合肥230037）

FFT在導航信號捕獲中的應用分析?

徐 浩 曾芳玲
（電子工程學院合肥230037）

針對偽碼捕獲過程中，傳統的滑動相關捕獲方法存在捕獲時間長，捕獲精度低等問題，選擇了將FFT應用于偽碼捕獲中，提高了捕獲的時間以及速度。并對兩種方法進行分析比較和仿真驗證，證實了FFT的使用大大減少了捕獲時間，提高了捕獲速度。最后對于在FFT捕獲過程中的問題，提出了一些改進措施。

相關；FFT；運算量；捕獲時間

ClassNumber TN927.1

1 引言

全球定位系統（GPS），是一種典型的直接序列擴頻系統，它可以為用戶提供全天候、連續、實時、高精度的位置、速度和時間（PVT）服務［1］。而這一切服務的基礎，從本地接收機方面來看，便是來源于對GPS信號的捕獲，信號捕獲成功之后才能進行接下來的跟蹤、觀測量提取和定位解算等。

GPS是直擴系統［2~3］，而且導航星一直處于高速運動狀態，接收機與衛星之間有很大的距離，這就使得接收到的信號產生很大頻率的偏移以及碼相位的偏移，對GPS信號的捕獲就是對偽碼相位偏移和頻率偏移的粗確定。

傳統的相關捕獲算法，雖然實現比較簡單，硬件資源占用比較少，但是其運算量很大，因此相應的捕獲時間也會很長，無法滿足實時性的要求［4~5］。根據數字信號處理的知識，進行L點相關的結果可以通過使用2次FFT和1次IFFT求得，這使得運算量下降，捕獲時間減少，滿足實時性的要求，這種方法是基于FFT捕獲方法。

2 傳統的相關捕獲方法

傳統相關捕獲方法是利用偽碼的優良的自相關特性［6~7］，將本地信號與接收信號做相關處理，對相關結果進行門限檢測，超過門限則完成捕獲；否則將本地碼移位，繼續進行相關和峰值檢測，直到峰值超過閾值。

2.1 捕獲原理及時間分析

對GPS信號的捕獲是二維的捕獲過程，那么捕獲過程中就要進行二維的搜索，一維是多普勒頻移的搜索，另一維是偽碼相位的搜索，每一次二維的搜索為一個搜索單元。如圖1所示。

接收機采用相關技術進行捕獲，捕獲的成功與否就是通過匹配程度來衡量。在頻率和偽碼相位的二維搜索中，通常情況下，碼的匹配度閾值δt￡ 0.5個碼元，多普勒頻率的閾值δf一般設定為250Hz，當兩者同時滿足要求時，認定捕獲成功。對應二維捕獲過程中的搜索單元設定為δf×δt，D F表示的是多普勒頻率的搜索范圍，也就是捕獲時本地載波與接受信號頻率的最大偏差，D F表示要搜索的偽碼相位范圍，也就是本地偽碼和接受信號偽碼之間的最大偏差。因此捕獲時要搜索的最大的單元個數為

其中NC為搜索的最大單元個數，PEA表示的是虛警概率，PD為檢測概率，τ(PEA×PD)表示的是在虛警概率為PEA，檢測概率為PD的條件下每個搜索單元的駐留時間。

2.2 捕獲過程及計算量分析

根據二維捕獲原理，需要對信號進行頻率和碼相位的二維搜索［9］，其捕獲過程如圖2所示。

信號捕獲時，首先將接收信號分為I路和Q路兩路分別處理，之后將兩路信號分別與本地載波相乘，一方面是對多普勒頻率的搜索，另一方面是完成載波剝離，之后將剝離載波后的信號與本地偽碼進行相關運算，經過積分和累加濾波器（IDF）進行累加，然后把兩路的積分和進行平方后相加，最后進行閾值的比較。若超過閾值，則捕獲成功，否則將調整本地載波和偽碼相位，重復以上步驟，直到捕獲完成。

時域相關法和FFT方法除偽碼相關模塊外，其余的模塊進行的處理相似，運算量也大致相等，所以研究運算量之間的關系時主要針對碼相關模塊。根據相關捕獲流程圖，對包含L個碼元的信號，完成一個單元搜索時，需完成L次乘法和L-1次加法。在一個載波頻率下要完成所有L個碼元相位的搜索，需要的計算量為L2次乘法和L() L-1次加法。為了保證頻率匹配度在δf以內，那么應當以2δf為步進頻率要完成D F頻率范圍內的搜索，需要完成的加法計算量MAC1為

由此可知，當碼元個數確定時，其加法運算量和乘法運算量的大小均與頻率搜索范圍成正比；當頻率范圍確定時，加法運算量的大小和L()L-1的乘積正比例關系，乘法運算量的大小和碼元個數的平方成正比。

3 基于FFT的捕獲方法

3.1 FFT捕獲原理

實現從時域到頻域的轉換進行捕獲，其理論原理是基于信號的互相關、線性卷積以及循環卷積之間的關系［10~11］。對于兩個信號x(n)和h(n)，它們之間的L點互相關函數為

而對于一個線性時不變的系統，兩者的線性卷積為

根據兩者的關系，可以推得：

另外L點的循環卷積Rxh(k)是線性卷積rxh(k)以L為周期的周期延拓序列的主值序列。循環卷積定義為［12］

由上邊的幾種關系，可以得到信號相關和信號FFT之間存在如下的關系：

根據上式將時域相關運算轉換到了頻域進行計算，2次FFT和1次IFFT運算可以求得相關結果，減少了運算量，提高了捕獲速度。

3.2 基于FFT捕獲過程

根據FFT和信號相關之間的關系，將信號捕獲過程中的時域運算轉換到了頻域，其捕獲流程如圖3所示。

與時域相關捕獲相似，將接收信號分為I和Q兩路，然后分別進行頻域搜索和載頻剝離。但不同的是載頻剝離后，將兩路信號混頻得到I+jQ，之后對I+jQ進行FFT變換，同時對本地偽碼信號也進行FFT變換，并取共軛，將兩者進行相乘后的結果，進行FFT反變換。最后將反變換的結果求和相加，進行閾值判決，若大于閾值，則捕獲成功，否則調整載波頻率和偽碼相位重新捕獲，直到捕獲成功。

3.3 運算量和捕獲時間分析

FFT的運用使得信號捕獲過程中的運算量以及捕獲時間大大減少，原本相關過程中的多次乘法以及加法運算，現在只需進行2次FFT和一次IFFT運算就可以完成。同樣只考慮偽碼的相關過程模塊，對于擁有L個碼元的信號，完成在一個頻率上的所有碼元相位搜索，需要的運算量為2次FFT，1次IFFT，而通常情況下本地碼的FFT可以在捕獲之前已經完成并儲存，認為只進行2次FFT變換的運算量就可以。1次的L點FFT變換需要進行復數加L logL2次，需要進行復數乘0.5×L次。兩個2加法器構成1個復數加，3個加法器4個實數乘法器構成一個復數乘。那么以2δf為步進頻率要完成D F頻率范圍內的搜索，所需的加法運算量為

根據上式，基于FFT的信號捕獲過程其加法運算量和乘法運算量的大小與頻率搜索范圍成正比，與搜索的碼元個數成正比，但是比例關系卻是比時域相關運算少很多，這也是FFT減少運算量的根本原因。

用TD表示進行1次FFT所用的時間，那么完成捕獲所需要的最長時間，即搜索完所有頻率才捕獲到的時間為

最短的用時，即一次頻率搜索就捕獲到的用時為

4 兩種捕獲方法的比較分析

4.1 運算量的比較

為了保證比較更加合理，必須要保持兩種方法是在同樣的搜索頻率范圍，和同樣的碼元個數下進行比較。另外通過上邊的分析，可以明顯發現兩種方法的運算量差別主要來源于碼元個數L。對于一般接收機來說，通常產生的多普勒頻移在±10KHz內，因此我們取搜索范圍D F=20KHz。為保證頻率匹配度在250Hz之內，那么頻率步進為500Hz。表1和表2分別給出了在L分別等于512、1024、2048時加法運算量和乘法運算量的大小比較。

表1 加法運算量的比較

表2 乘法運算量的比較

為了更加直觀的顯示運算量的差異，使用MATLAB進行了仿真，仿真結果分別如圖4所示。

結果顯示無論是加法還是乘法，在運算量上基于FFT的方法要比時域相關捕獲法少幾個數量級。也就是說FFT的應用使得捕獲過程中的計算量大大降低。并且捕獲碼元數越多，計算量相差越大。

4.2 捕獲時間的比較

進行時間比較時，為使比較更加合理，仍然選定頻域范圍是20KHz，頻域搜索步進為500Hz，碼元搜索步進為1個碼元。那么同樣對于L個碼元而言，設定積分累加時間為1ms，而相應的1次傅里葉變換時間在系統頻率下不會超過1ms。根據捕獲平均時間計算公式，在一定的范圍內，碼元個數的改變對FFT方法捕獲時間的影響極小，對相關捕獲影響比較大。表3給出了碼元個數為512、1024和 2048時的用時比較。

表3 兩種方法的捕獲時間比較

其仿真結果如圖5所示。

根據仿真結果，在捕獲時間上，基于FFT捕獲方法的用時相比相關捕獲方法少二到三個數量級，甚至更多。并且碼元數越多，兩者相差時間越大。

5結語

導航信號捕獲過程中，相關捕獲方法，雖然計算量大，捕獲時間較長，但是實現簡單，使用硬件資源較少，資源利用率高。FFT的應用減少了運算量，也使捕獲時間減少了幾個數量級，更加滿足了信號捕獲的實時性要求，但是也存在硬件要求高，資源消耗高，利用率低功耗大的缺點。因此對于捕獲方法，還有根據目的性和綜合各方面的考慮，選擇最優化的方法。

［1］邱致和，王萬義.GPS原理與應用［M］.北京：電子工業出版社，2002：45-56.

［2］尚曉琉，胡修林，楊靈.直接序列擴展頻譜通信系統仿真［J］.系統工程與電子技術.2003，25（2）：154-159

［3］Akopian，D.Fast FFT based GPS satellite acquisition methods［J］.IEEE Proceedings-Radar，Sonar and Naviga?tion，2005，152（4）：277-286.

［4］蔡凡，尹燕，張秀忠.GPS接收機的中頻信號處理算法研究［J］.天文學進展，2007，25（1）：84-95.

［5］張勇，林寶軍，徐志翰.軟件GPS接收機信號搜索捕獲的仿真實驗研究［J］.系統仿真學報，2006，18（9）：2646-2649.

［6］Chen Zhiguo，Chen Pei，Han Chao.GPS signal acquisi?tionmethodsusing sample-basedshiftingand FFT［J］.Per?vasive Computing Signal Processing and App lications，2010，9：1005-1008.

［7］陳熙源，張昆鵬.基于MATLAB的GPS軟件接收機捕獲與跟蹤算法實現［J］.中國慣性技術學報，2007，8：423-426.

［8］李菊，陳禾，金俊坤，等.基于FFT的兩種偽碼快速捕獲方案的研究與實現［［J］.電子與信息學報，2006，28（10）：1778-1781.

［9］魏玲玲，范勝林.高靈敏度GPS軟件接收機捕獲算法［J］.指揮控制與仿真2012，10：50-54.

［10］胡廣書.數字信號處理理論算法與實現［M］.北京：清華大學出版社有限公司，2003：33-54

［11］AbdulqadirTracking forAlaqeeli，Janusz Starzyk，Frank van Graas.Real-time Acquisition andGPS receivers［J］. Circuitsand Systems，2003，5：500-503

［12］趙琳，高帥和，丁繼成.基于FFT的高動態GPS信號捕獲方法優化［J］.系統工程與電子技術，2011，33（01）：151-156.

那么基于FFT的捕獲方法，平均捕獲時間是：

Application Analysisof FFT in Navigation SignalAcquisition

XU Hao ZENG Fangling
（SchoolofElectronic Engineering，Hefei 230037）

Aiming at the problem that the traditional sliding correlation acquisitionmethod has long capture time and low ac?quisition precision in the process of pseudo-code acquisition，the FFT is applied to the acquisition of PN code，and the acquisition time and accuracy are improved.The analysisand comparison of the twomethodsand the simulation results show that the FFTmeth?od greatly reduces the acquisition time and improves the acquisition speed.Finally，some improvementmeasuresare put forward in the processof FFT acquisition.

correlation，FFT，computation，capture time

TN927.1 DO I：10.3969/j.issn.1672-9730.2017.05.009

2016年11月7日，

2016年12月20日

徐浩，男，碩士研究生，研究方向：導航與定位和衛星信號捕獲。曾芳玲，女，教授，博士生導師，研究方向：導航與時統。