測距m序列擴頻碼的快速捕獲算法

安凱　張利彬

摘 要： 針對測距m序列擴頻碼，提出一種快速捕獲方法。假定m序列發生器的移位寄存器個數為[r，]該方法首先根據連續接收的一段長度為[r]的序列，通過一個寄存器狀態解算器，推算出發送完這段序列后m序列發生器寄存器的狀態，并將本地m序列發生器的寄存器狀態置為該狀態。接收機接收上述長度為[r]的序列，再接收一段長度為[2r-1]的序列后，本地m序列發生器開始工作，并與接收的m序列進行相關運算和相關性判定。若相關性超過某一閾值，判定結果為“相關”，則捕獲成功，否則繼續重復上述過程，直到判定結果為“相關”為止。出現不相關情況的原因是作為解算器輸入的上述一段長度為[r]的序列包含誤碼，以[r=20]為例，其概率僅為[1-0.980 2=0.019 8，]也就是說，這種方法一次捕獲成功的概率為0.980 2。

關鍵詞： 測距； m序列； 擴頻； 捕獲算法

中圖分類號： TN97?34 文獻標識碼： A 文章編號： 1004?373X（2014）11?0065?03

Abstract： A fast acquisition algorithm of m?sequence spread spectrum codes for ranging is put forward in this paper. Presuming that the number of the shift registers of m?sequences generator is[r]， according to a consecutively?received sequence with length [r，] the register state of the m?sequence generator is deduced through a register state resolver when the sequence is transmitted completely， and then the local registers of the m?sequences generator is set the same state. After another sequence with length[2r-1] is received， a local m?sequence generator starts working， and simultaneously the correlator compares the local m?sequence with the received one by calculation. The correlation judgment is made. If the correlation is larger than a threshold， the decision that the current cell is true and the search finishes is made. Otherwise the search system examines the next cell and repeats the above?mentioned process， until the result of the judgment is “correlation”. In the case of [r=20，] for example， the probability of finishing acquisition in one search is 0.980 2.

Keywords： ranging； m?sequence； spread spectrum； acquisition algorithm

0 引 言

擴頻通信是傳輸信息的射頻帶寬遠大于信息本身帶寬的一種通信方式，是通信的一個重要分支和發展方向[1?3]。擴頻通信技術的特點在于抗干擾性強、截獲率低、抗多路徑干擾性能好、保密性好、易于實現碼分多址，因此其應用領域已迅速從軍用擴展到民用通信中，并實現了與第三代移動通信系統的完美結合，成為發展前景極為廣闊的一種通信方式[4?5]。然而，擴頻通信在偽隨機碼捕獲過程中接收碼與本地碼之間的相關運算卻是一件十分復雜、耗時的工作[6?8]。

以20級移位寄存器產生的最大長度偽隨機碼序列為例，一個周期內序列長度為[220-1]個碼元。如果將每個碼元比作齒輪的一個齒，一個周期的隨機碼序列就是一個具有[220-1]個齒的齒輪，偽隨機碼周期性地依次產生類似于齒輪一周周地轉動。如果將齒輪甲比作偽隨機碼接收機，齒輪乙比作本地偽隨機碼發生器，則一次相關運算相當于一個齒輪的某一個齒與另一個齒輪的某一個齒根對應，兩齒輪嚙合后轉動一周。其間，每一對齒與齒根的接觸就是一個“乘”運算，而在轉動一周后所有這些運算結果還要進行“加”的運算，并根據“加”的結果判定是否相關。在不相關的情況下該齒再與另一個齒輪的下一個齒根對應，兩齒輪嚙合后再轉動一周；……，不斷重復這種過程，直到找到惟一一個正確的齒根為止才算完成擴頻碼的捕獲。在最多的情況下，擴頻碼的捕獲大約需要進行[（220-1）2=109 950 000 000]次“乘”運算和“加”的運算！

為了減少擴頻碼的捕獲時間，工程技術人員通常是利用FPGA進行并行計算，但由于運算量太大，即使采用1 000個相關器進行并行計算，在最多的情況下，每個相關器仍需要進行至少[（220-1）2=109 950 000]次“乘”運算和“加”的運算！盡管大量地占用了運算資源，但運算量依舊很大。可見，僅靠并行計算雖然提高了成本但仍不能從根本上改善擴頻碼的捕獲時間，只有改進擴頻碼的捕獲方法才是縮短捕獲時間出路所在[9?10]。

1 移位寄存器狀態的確定

圖1是測距m序列擴頻碼發生器結構示意圖。圖中[a1，a2，…，ar]為當前寄存器狀態，[b（D）]為當前輸出。

在接收信號無誤碼的情況下， 捕獲m序列就是在本地m序列發生器上產生與接收測距碼序列相同（包括相位）的m序列，這就需要根據獲得的一定長度的接收序列確定本地m序列發生器的當前狀態。假定寄存器的個數為[r]，由長度為[r]的接收序列就可以確定移位寄存器狀態。圖1為通用反饋移位寄存器的結構，生成多項式為：

實現其運算的移位寄存器連接如圖2所示。圖中的輸入數據[x1，x2，…，xr]是由接收器連續接收的一段長度為[r]的序列，該序列依次輸入寄存器狀態解算器中。

然而，如此的狀態解算器，在執行過程中需要一定的時間才能解出本地m序列發生器的狀態，而后才能產生本地m序列。這樣，本地m序列發生器與接收到的m序列之間必然存在較大的相位滯后，實現兩序列的同步成為捕獲問題的關鍵。慶幸的是m序列是周期序列。假定生成多項式[g（D）]為本原多項式，則m序列具有最大長度[2r-1]。當接收一段長度為[r]的m序列[x1，x2，…，xr-1，xr]之后采用并行處理的方法，一方面通過狀態解算器解算本地m序列發生器的狀態，并將本地m序列發生器的寄存器狀態置為該狀態，一方面等待另一段長度為[2r-1]的m序列中最后一個碼元的出現。這一段等待時間為本地m序列發生器寄存器狀態的設置留出了足夠的時間。

2 接收序列錯誤概率分析

上述移位寄存器狀態確定的條件是接收信號無誤碼，這是一種理想的情況。實際問題中接收信號是一個隨機變量，它以一定的概率正確接收，以另外的概率錯誤接收，錯誤接收的概率即誤碼率。假定通信信道的誤碼率為[p]，接收的一段長度為[r]的m序列為：

[x1，x2，…，xr-1，xr]

這一段接收序列發生錯誤也就是[r]比特的序列中至少有1個比特發生接收錯誤；這一段接收序列未發生錯誤也就是[r]比特的序列中每1個比特都未發生接收錯誤，其概率為[（1-p）r。]以[p=0.001，][r=20]為例，正確接收一段長度為[r]的m序列的概率為：

[（1-p）r=0.99920=0.980 2]

而當[p=0.005]，[r=20]時，正確接收一段長度為[r]的m序列的概率為：

[（1-p）r=0.99520=0.904 6]

可見接收的一段長度為[r]的m序列發生錯誤的概率非常小。

3 執行步驟

（1） 依次接收一段m序列[x1，x2，…，xr-1，xr，]置[i=0，k=0]（分別為接收比特計數和本地m序列發生器開始信號）；

（2） 以[x1，x2，…，xr-1，xr]作為狀態解算器的輸入，獲得狀態解算器的輸出，并以此作為本地m序列發生器的狀態，與此并行處理的是：

（3） 接收1個比特信號，[i=i+1]，若[i>2r-1]則返回（3），否則[k=1；]

（4） 若[k=1]則開始相關運算，否則返回（4）；

（5） 若相關，捕獲成功，否則返回（1）。

上述分析已經表明，當步驟（1）中獲得的序列[x1，x2，…，xr-1，xr]無誤碼時，步驟（5）無須返回步驟（1），只有在[x1，x2，…，xr-1，xr]存在誤碼的情況下步驟（5）才可能返回到步驟（1），因此返回概率只有0.019 8。

4 結 論

本發明的特點之一是極大地減少了捕獲的運算量和時間。傳統的捕獲方法平均需要進行[（2r-1）2]次相關運算，而本發明專利提出的方法一次相關運算捕獲成功的概率為0.980 2。本發明的特點之二是容易實現，只需增加一個狀態解算器并對捕獲軟件稍作修改即可。

參考文獻

[1] VALERY P. Spread spectrum and CDMA： principles and applications [M]. Chichester： John Wiley & Sons， 2005.

[2]LEVANON N， MOZESON E. Radar signals [M]. Chichester： John Wiley & Sons， 2004.

[3] SKLAR B. Digital communications [M]. Upper Saddle River， NJ： Prentice?Hall， 2001.

[4] DIXON R C. Spread spectrum systems with commercial applications [M]. Chichester： John Wiley & Sons， 1994.

[5] HAYKIN S. Communication systems [M]. Chichester： John Wiley & Sons， 2001.

[6] ZIEMER R E， PETERSON R L. Introduction to digital communication [M]. Upper Saddle River， NJ： Prentice?Hall， 2001.

[7] PROAKIS J G. Digital communications [M]. New York： McGraw?Hill， 2001.

[8] PROAKIS J， SALEHI M. Communication systems engineering [M]. Upper Saddle River， NJ： Prentice?Hall， 2002.

[9]安凱.測距m序列擴頻碼的快速捕獲方法：中國，CN201010621331.9[P]. 2011?06?29.

[10] 安凱，邢進生，邱祖廉.模糊神經網絡的二階段變半徑隨機搜索算法[J].自動化學報，2000，26（5）：616?622.

[11] 林智慧，陳綏陽，王元一.m序列及其在通信中的應用[J].現代電子技術，2009，32（9）：49?51.

[12] 王立松，梁光明，劉東華，等.一種長周期擴頻碼設計[J].現代電子技術，2010，33（11）：61?64.

圖1是測距m序列擴頻碼發生器結構示意圖。圖中[a1，a2，…，ar]為當前寄存器狀態，[b（D）]為當前輸出。

在接收信號無誤碼的情況下， 捕獲m序列就是在本地m序列發生器上產生與接收測距碼序列相同（包括相位）的m序列，這就需要根據獲得的一定長度的接收序列確定本地m序列發生器的當前狀態。假定寄存器的個數為[r]，由長度為[r]的接收序列就可以確定移位寄存器狀態。圖1為通用反饋移位寄存器的結構，生成多項式為：

實現其運算的移位寄存器連接如圖2所示。圖中的輸入數據[x1，x2，…，xr]是由接收器連續接收的一段長度為[r]的序列，該序列依次輸入寄存器狀態解算器中。

然而，如此的狀態解算器，在執行過程中需要一定的時間才能解出本地m序列發生器的狀態，而后才能產生本地m序列。這樣，本地m序列發生器與接收到的m序列之間必然存在較大的相位滯后，實現兩序列的同步成為捕獲問題的關鍵。慶幸的是m序列是周期序列。假定生成多項式[g（D）]為本原多項式，則m序列具有最大長度[2r-1]。當接收一段長度為[r]的m序列[x1，x2，…，xr-1，xr]之后采用并行處理的方法，一方面通過狀態解算器解算本地m序列發生器的狀態，并將本地m序列發生器的寄存器狀態置為該狀態，一方面等待另一段長度為[2r-1]的m序列中最后一個碼元的出現。這一段等待時間為本地m序列發生器寄存器狀態的設置留出了足夠的時間。

2 接收序列錯誤概率分析

上述移位寄存器狀態確定的條件是接收信號無誤碼，這是一種理想的情況。實際問題中接收信號是一個隨機變量，它以一定的概率正確接收，以另外的概率錯誤接收，錯誤接收的概率即誤碼率。假定通信信道的誤碼率為[p]，接收的一段長度為[r]的m序列為：

[x1，x2，…，xr-1，xr]

這一段接收序列發生錯誤也就是[r]比特的序列中至少有1個比特發生接收錯誤；這一段接收序列未發生錯誤也就是[r]比特的序列中每1個比特都未發生接收錯誤，其概率為[（1-p）r。]以[p=0.001，][r=20]為例，正確接收一段長度為[r]的m序列的概率為：

[（1-p）r=0.99920=0.980 2]

而當[p=0.005]，[r=20]時，正確接收一段長度為[r]的m序列的概率為：

[（1-p）r=0.99520=0.904 6]

可見接收的一段長度為[r]的m序列發生錯誤的概率非常小。

3 執行步驟

（1） 依次接收一段m序列[x1，x2，…，xr-1，xr，]置[i=0，k=0]（分別為接收比特計數和本地m序列發生器開始信號）；

（2） 以[x1，x2，…，xr-1，xr]作為狀態解算器的輸入，獲得狀態解算器的輸出，并以此作為本地m序列發生器的狀態，與此并行處理的是：

（3） 接收1個比特信號，[i=i+1]，若[i>2r-1]則返回（3），否則[k=1；]

（4） 若[k=1]則開始相關運算，否則返回（4）；

（5） 若相關，捕獲成功，否則返回（1）。

上述分析已經表明，當步驟（1）中獲得的序列[x1，x2，…，xr-1，xr]無誤碼時，步驟（5）無須返回步驟（1），只有在[x1，x2，…，xr-1，xr]存在誤碼的情況下步驟（5）才可能返回到步驟（1），因此返回概率只有0.019 8。

4 結 論

本發明的特點之一是極大地減少了捕獲的運算量和時間。傳統的捕獲方法平均需要進行[（2r-1）2]次相關運算，而本發明專利提出的方法一次相關運算捕獲成功的概率為0.980 2。本發明的特點之二是容易實現，只需增加一個狀態解算器并對捕獲軟件稍作修改即可。

參考文獻

[1] VALERY P. Spread spectrum and CDMA： principles and applications [M]. Chichester： John Wiley & Sons， 2005.

[2]LEVANON N， MOZESON E. Radar signals [M]. Chichester： John Wiley & Sons， 2004.

[3] SKLAR B. Digital communications [M]. Upper Saddle River， NJ： Prentice?Hall， 2001.

[4] DIXON R C. Spread spectrum systems with commercial applications [M]. Chichester： John Wiley & Sons， 1994.

[5] HAYKIN S. Communication systems [M]. Chichester： John Wiley & Sons， 2001.

[6] ZIEMER R E， PETERSON R L. Introduction to digital communication [M]. Upper Saddle River， NJ： Prentice?Hall， 2001.

[7] PROAKIS J G. Digital communications [M]. New York： McGraw?Hill， 2001.

[8] PROAKIS J， SALEHI M. Communication systems engineering [M]. Upper Saddle River， NJ： Prentice?Hall， 2002.

[9]安凱.測距m序列擴頻碼的快速捕獲方法：中國，CN201010621331.9[P]. 2011?06?29.

[10] 安凱，邢進生，邱祖廉.模糊神經網絡的二階段變半徑隨機搜索算法[J].自動化學報，2000，26（5）：616?622.

[11] 林智慧，陳綏陽，王元一.m序列及其在通信中的應用[J].現代電子技術，2009，32（9）：49?51.

[12] 王立松，梁光明，劉東華，等.一種長周期擴頻碼設計[J].現代電子技術，2010，33（11）：61?64.

圖1是測距m序列擴頻碼發生器結構示意圖。圖中[a1，a2，…，ar]為當前寄存器狀態，[b（D）]為當前輸出。

在接收信號無誤碼的情況下， 捕獲m序列就是在本地m序列發生器上產生與接收測距碼序列相同（包括相位）的m序列，這就需要根據獲得的一定長度的接收序列確定本地m序列發生器的當前狀態。假定寄存器的個數為[r]，由長度為[r]的接收序列就可以確定移位寄存器狀態。圖1為通用反饋移位寄存器的結構，生成多項式為：

實現其運算的移位寄存器連接如圖2所示。圖中的輸入數據[x1，x2，…，xr]是由接收器連續接收的一段長度為[r]的序列，該序列依次輸入寄存器狀態解算器中。

然而，如此的狀態解算器，在執行過程中需要一定的時間才能解出本地m序列發生器的狀態，而后才能產生本地m序列。這樣，本地m序列發生器與接收到的m序列之間必然存在較大的相位滯后，實現兩序列的同步成為捕獲問題的關鍵。慶幸的是m序列是周期序列。假定生成多項式[g（D）]為本原多項式，則m序列具有最大長度[2r-1]。當接收一段長度為[r]的m序列[x1，x2，…，xr-1，xr]之后采用并行處理的方法，一方面通過狀態解算器解算本地m序列發生器的狀態，并將本地m序列發生器的寄存器狀態置為該狀態，一方面等待另一段長度為[2r-1]的m序列中最后一個碼元的出現。這一段等待時間為本地m序列發生器寄存器狀態的設置留出了足夠的時間。

2 接收序列錯誤概率分析

上述移位寄存器狀態確定的條件是接收信號無誤碼，這是一種理想的情況。實際問題中接收信號是一個隨機變量，它以一定的概率正確接收，以另外的概率錯誤接收，錯誤接收的概率即誤碼率。假定通信信道的誤碼率為[p]，接收的一段長度為[r]的m序列為：

[x1，x2，…，xr-1，xr]

這一段接收序列發生錯誤也就是[r]比特的序列中至少有1個比特發生接收錯誤；這一段接收序列未發生錯誤也就是[r]比特的序列中每1個比特都未發生接收錯誤，其概率為[（1-p）r。]以[p=0.001，][r=20]為例，正確接收一段長度為[r]的m序列的概率為：

[（1-p）r=0.99920=0.980 2]

而當[p=0.005]，[r=20]時，正確接收一段長度為[r]的m序列的概率為：

[（1-p）r=0.99520=0.904 6]

可見接收的一段長度為[r]的m序列發生錯誤的概率非常小。

3 執行步驟

（1） 依次接收一段m序列[x1，x2，…，xr-1，xr，]置[i=0，k=0]（分別為接收比特計數和本地m序列發生器開始信號）；

（2） 以[x1，x2，…，xr-1，xr]作為狀態解算器的輸入，獲得狀態解算器的輸出，并以此作為本地m序列發生器的狀態，與此并行處理的是：

（3） 接收1個比特信號，[i=i+1]，若[i>2r-1]則返回（3），否則[k=1；]

（4） 若[k=1]則開始相關運算，否則返回（4）；

（5） 若相關，捕獲成功，否則返回（1）。

上述分析已經表明，當步驟（1）中獲得的序列[x1，x2，…，xr-1，xr]無誤碼時，步驟（5）無須返回步驟（1），只有在[x1，x2，…，xr-1，xr]存在誤碼的情況下步驟（5）才可能返回到步驟（1），因此返回概率只有0.019 8。

4 結 論

本發明的特點之一是極大地減少了捕獲的運算量和時間。傳統的捕獲方法平均需要進行[（2r-1）2]次相關運算，而本發明專利提出的方法一次相關運算捕獲成功的概率為0.980 2。本發明的特點之二是容易實現，只需增加一個狀態解算器并對捕獲軟件稍作修改即可。

參考文獻

[1] VALERY P. Spread spectrum and CDMA： principles and applications [M]. Chichester： John Wiley & Sons， 2005.

[2]LEVANON N， MOZESON E. Radar signals [M]. Chichester： John Wiley & Sons， 2004.

[3] SKLAR B. Digital communications [M]. Upper Saddle River， NJ： Prentice?Hall， 2001.

[4] DIXON R C. Spread spectrum systems with commercial applications [M]. Chichester： John Wiley & Sons， 1994.

[5] HAYKIN S. Communication systems [M]. Chichester： John Wiley & Sons， 2001.

[6] ZIEMER R E， PETERSON R L. Introduction to digital communication [M]. Upper Saddle River， NJ： Prentice?Hall， 2001.

[7] PROAKIS J G. Digital communications [M]. New York： McGraw?Hill， 2001.

[8] PROAKIS J， SALEHI M. Communication systems engineering [M]. Upper Saddle River， NJ： Prentice?Hall， 2002.

[9]安凱.測距m序列擴頻碼的快速捕獲方法：中國，CN201010621331.9[P]. 2011?06?29.

[10] 安凱，邢進生，邱祖廉.模糊神經網絡的二階段變半徑隨機搜索算法[J].自動化學報，2000，26（5）：616?622.

[11] 林智慧，陳綏陽，王元一.m序列及其在通信中的應用[J].現代電子技術，2009，32（9）：49?51.

[12] 王立松，梁光明，劉東華，等.一種長周期擴頻碼設計[J].現代電子技術，2010，33（11）：61?64.