测距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.