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

FFT在導(dǎo)航信號(hào)捕獲中的應(yīng)用分析?

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

針對(duì)偽碼捕獲過(guò)程中，傳統(tǒng)的滑動(dòng)相關(guān)捕獲方法存在捕獲時(shí)間長(zhǎng)，捕獲精度低等問(wèn)題，選擇了將FFT應(yīng)用于偽碼捕獲中，提高了捕獲的時(shí)間以及速度。并對(duì)兩種方法進(jìn)行分析比較和仿真驗(yàn)證，證實(shí)了FFT的使用大大減少了捕獲時(shí)間，提高了捕獲速度。最后對(duì)于在FFT捕獲過(guò)程中的問(wèn)題，提出了一些改進(jìn)措施。

相關(guān)；FFT；運(yùn)算量；捕獲時(shí)間

ClassNumber TN927.1

1 引言

全球定位系統(tǒng)（GPS），是一種典型的直接序列擴(kuò)頻系統(tǒng)，它可以為用戶提供全天候、連續(xù)、實(shí)時(shí)、高精度的位置、速度和時(shí)間（PVT）服務(wù)［1］。而這一切服務(wù)的基礎(chǔ)，從本地接收機(jī)方面來(lái)看，便是來(lái)源于對(duì)GPS信號(hào)的捕獲，信號(hào)捕獲成功之后才能進(jìn)行接下來(lái)的跟蹤、觀測(cè)量提取和定位解算等。

GPS是直擴(kuò)系統(tǒng)［2~3］，而且導(dǎo)航星一直處于高速運(yùn)動(dòng)狀態(tài)，接收機(jī)與衛(wèi)星之間有很大的距離，這就使得接收到的信號(hào)產(chǎn)生很大頻率的偏移以及碼相位的偏移，對(duì)GPS信號(hào)的捕獲就是對(duì)偽碼相位偏移和頻率偏移的粗確定。

傳統(tǒng)的相關(guān)捕獲算法，雖然實(shí)現(xiàn)比較簡(jiǎn)單，硬件資源占用比較少，但是其運(yùn)算量很大，因此相應(yīng)的捕獲時(shí)間也會(huì)很長(zhǎng)，無(wú)法滿足實(shí)時(shí)性的要求［4~5］。根據(jù)數(shù)字信號(hào)處理的知識(shí)，進(jìn)行L點(diǎn)相關(guān)的結(jié)果可以通過(guò)使用2次FFT和1次IFFT求得，這使得運(yùn)算量下降，捕獲時(shí)間減少，滿足實(shí)時(shí)性的要求，這種方法是基于FFT捕獲方法。

2 傳統(tǒng)的相關(guān)捕獲方法

傳統(tǒng)相關(guān)捕獲方法是利用偽碼的優(yōu)良的自相關(guān)特性［6~7］，將本地信號(hào)與接收信號(hào)做相關(guān)處理，對(duì)相關(guān)結(jié)果進(jìn)行門(mén)限檢測(cè)，超過(guò)門(mén)限則完成捕獲；否則將本地碼移位，繼續(xù)進(jìn)行相關(guān)和峰值檢測(cè)，直到峰值超過(guò)閾值。

2.1 捕獲原理及時(shí)間分析

對(duì)GPS信號(hào)的捕獲是二維的捕獲過(guò)程，那么捕獲過(guò)程中就要進(jìn)行二維的搜索，一維是多普勒頻移的搜索，另一維是偽碼相位的搜索，每一次二維的搜索為一個(gè)搜索單元。如圖1所示。

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

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

2.2 捕獲過(guò)程及計(jì)算量分析

根據(jù)二維捕獲原理，需要對(duì)信號(hào)進(jìn)行頻率和碼相位的二維搜索［9］，其捕獲過(guò)程如圖2所示。

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

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

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

3 基于FFT的捕獲方法

3.1 FFT捕獲原理

實(shí)現(xiàn)從時(shí)域到頻域的轉(zhuǎn)換進(jìn)行捕獲，其理論原理是基于信號(hào)的互相關(guān)、線性卷積以及循環(huán)卷積之間的關(guān)系［10~11］。對(duì)于兩個(gè)信號(hào)x(n)和h(n)，它們之間的L點(diǎn)互相關(guān)函數(shù)為

而對(duì)于一個(gè)線性時(shí)不變的系統(tǒng)，兩者的線性卷積為

根據(jù)兩者的關(guān)系，可以推得：

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

由上邊的幾種關(guān)系，可以得到信號(hào)相關(guān)和信號(hào)FFT之間存在如下的關(guān)系：

根據(jù)上式將時(shí)域相關(guān)運(yùn)算轉(zhuǎn)換到了頻域進(jìn)行計(jì)算，2次FFT和1次IFFT運(yùn)算可以求得相關(guān)結(jié)果，減少了運(yùn)算量，提高了捕獲速度。

3.2 基于FFT捕獲過(guò)程

根據(jù)FFT和信號(hào)相關(guān)之間的關(guān)系，將信號(hào)捕獲過(guò)程中的時(shí)域運(yùn)算轉(zhuǎn)換到了頻域，其捕獲流程如圖3所示。

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

3.3 運(yùn)算量和捕獲時(shí)間分析

FFT的運(yùn)用使得信號(hào)捕獲過(guò)程中的運(yùn)算量以及捕獲時(shí)間大大減少，原本相關(guān)過(guò)程中的多次乘法以及加法運(yùn)算，現(xiàn)在只需進(jìn)行2次FFT和一次IFFT運(yùn)算就可以完成。同樣只考慮偽碼的相關(guān)過(guò)程模塊，對(duì)于擁有L個(gè)碼元的信號(hào)，完成在一個(gè)頻率上的所有碼元相位搜索，需要的運(yùn)算量為2次FFT，1次IFFT，而通常情況下本地碼的FFT可以在捕獲之前已經(jīng)完成并儲(chǔ)存，認(rèn)為只進(jìn)行2次FFT變換的運(yùn)算量就可以。1次的L點(diǎn)FFT變換需要進(jìn)行復(fù)數(shù)加L logL2次，需要進(jìn)行復(fù)數(shù)乘0.5×L次。兩個(gè)2加法器構(gòu)成1個(gè)復(fù)數(shù)加，3個(gè)加法器4個(gè)實(shí)數(shù)乘法器構(gòu)成一個(gè)復(fù)數(shù)乘。那么以2δf為步進(jìn)頻率要完成D F頻率范圍內(nèi)的搜索，所需的加法運(yùn)算量為

根據(jù)上式，基于FFT的信號(hào)捕獲過(guò)程其加法運(yùn)算量和乘法運(yùn)算量的大小與頻率搜索范圍成正比，與搜索的碼元個(gè)數(shù)成正比，但是比例關(guān)系卻是比時(shí)域相關(guān)運(yùn)算少很多，這也是FFT減少運(yùn)算量的根本原因。

用TD表示進(jìn)行1次FFT所用的時(shí)間，那么完成捕獲所需要的最長(zhǎng)時(shí)間，即搜索完所有頻率才捕獲到的時(shí)間為

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

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

4.1 運(yùn)算量的比較

為了保證比較更加合理，必須要保持兩種方法是在同樣的搜索頻率范圍，和同樣的碼元個(gè)數(shù)下進(jìn)行比較。另外通過(guò)上邊的分析，可以明顯發(fā)現(xiàn)兩種方法的運(yùn)算量差別主要來(lái)源于碼元個(gè)數(shù)L。對(duì)于一般接收機(jī)來(lái)說(shuō)，通常產(chǎn)生的多普勒頻移在±10KHz內(nèi)，因此我們?nèi)∷阉鞣秶鶧 F=20KHz。為保證頻率匹配度在250Hz之內(nèi)，那么頻率步進(jìn)為500Hz。表1和表2分別給出了在L分別等于512、1024、2048時(shí)加法運(yùn)算量和乘法運(yùn)算量的大小比較。

表1 加法運(yùn)算量的比較

表2 乘法運(yùn)算量的比較

為了更加直觀的顯示運(yùn)算量的差異，使用MATLAB進(jìn)行了仿真，仿真結(jié)果分別如圖4所示。

結(jié)果顯示無(wú)論是加法還是乘法，在運(yùn)算量上基于FFT的方法要比時(shí)域相關(guān)捕獲法少幾個(gè)數(shù)量級(jí)。也就是說(shuō)FFT的應(yīng)用使得捕獲過(guò)程中的計(jì)算量大大降低。并且捕獲碼元數(shù)越多，計(jì)算量相差越大。

4.2 捕獲時(shí)間的比較

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

表3 兩種方法的捕獲時(shí)間比較

其仿真結(jié)果如圖5所示。

根據(jù)仿真結(jié)果，在捕獲時(shí)間上，基于FFT捕獲方法的用時(shí)相比相關(guān)捕獲方法少二到三個(gè)數(shù)量級(jí)，甚至更多。并且碼元數(shù)越多，兩者相差時(shí)間越大。

5結(jié)語(yǔ)

導(dǎo)航信號(hào)捕獲過(guò)程中，相關(guān)捕獲方法，雖然計(jì)算量大，捕獲時(shí)間較長(zhǎng)，但是實(shí)現(xiàn)簡(jiǎn)單，使用硬件資源較少，資源利用率高。FFT的應(yīng)用減少了運(yùn)算量，也使捕獲時(shí)間減少了幾個(gè)數(shù)量級(jí)，更加滿足了信號(hào)捕獲的實(shí)時(shí)性要求，但是也存在硬件要求高，資源消耗高，利用率低功耗大的缺點(diǎn)。因此對(duì)于捕獲方法，還有根據(jù)目的性和綜合各方面的考慮，選擇最優(yōu)化的方法。

［1］邱致和，王萬(wàn)義.GPS原理與應(yīng)用［M］.北京：電子工業(yè)出版社，2002：45-56.

［2］尚曉琉，胡修林，楊靈.直接序列擴(kuò)展頻譜通信系統(tǒng)仿真［J］.系統(tǒng)工程與電子技術(shù).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ī)的中頻信號(hào)處理算法研究［J］.天文學(xué)進(jìn)展，2007，25（1）：84-95.

［5］張勇，林寶軍，徐志翰.軟件GPS接收機(jī)信號(hào)搜索捕獲的仿真實(shí)驗(yàn)研究［J］.系統(tǒng)仿真學(xué)報(bào)，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ī)捕獲與跟蹤算法實(shí)現(xiàn)［J］.中國(guó)慣性技術(shù)學(xué)報(bào)，2007，8：423-426.

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

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

［10］胡廣書(shū).數(shù)字信號(hào)處理理論算法與實(shí)現(xiàn)［M］.北京：清華大學(xué)出版社有限公司，2003：33-54

［11］AbdulqadirTracking forAlaqeeli，Janusz Starzyk，F(xiàn)rank van Graas.Real-time Acquisition andGPS receivers［J］. Circuitsand Systems，2003，5：500-503

［12］趙琳，高帥和，丁繼成.基于FFT的高動(dòng)態(tài)GPS信號(hào)捕獲方法優(yōu)化［J］.系統(tǒng)工程與電子技術(shù)，2011，33（01）：151-156.

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

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，F(xiàn)FT，computation，capture time

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

2016年11月7日，

2016年12月20日

徐浩，男，碩士研究生，研究方向：導(dǎo)航與定位和衛(wèi)星信號(hào)捕獲。曾芳玲，女，教授，博士生導(dǎo)師，研究方向：導(dǎo)航與時(shí)統(tǒng)。