移位位反序列捕获算法

摘 要：当捕获周期较长的序列时，传统的滑动相关捕获方式会消耗巨大的系统资源。为此提出位反向量和移位位反向量，使得由序列状态的试错结果可直接推断出后续序列状态的试错结果，从而避免重复的序列推算过程，提高滑动相关效率。随后通过证明控制状态的生成规律，节省了位反向量及移位位反向量的存储空间。据前述原理，设计出了移位位反序列捕获算法及其接收机，使得捕获复杂度从常规的O（n2）下降为O（n）。

关键词：序列捕获；m序列；序列状态；移位位反向量；信息安全

中图分类号： TN911；TP309.7

文献标志码：A

0 引言

扩频通信系统利用了伪随机（PseudoNoise， PN）序列良好的自相关和互相关特性，不仅在军用通信系统、制导系统等军事技术领域中占有重要地位，而且在移动通信系统WCDMA（Wideband Code Division Multiple Access）、CDMA2000（Code Division Multiple Access）、无线电测距/测速、导航以及目标探测等民用领域也得到了非常广泛的应用[1]。扩频通信系统的窃听及同步均需要高性能的序列捕获算法[2-3]。在同步过程对PN序列进行捕获即是首先要确定PN序列的相位[4-5]。目前较为实用的是序列滑动相关捕获算法。

滑动相关捕获法基于滑动相关的思想，目前有关滑动相关捕获法的研究分为两个方向：

1）主要着眼于研究一些捕获参数[6]，包括判决门限、捕获序列状态量等。文献[7-8]综合各种信道因素针对参数进行了讨论，并且提出了一些自适应参数计算法则；文献[9] 分析了部分相关捕获算法在多径环境中的性能；文献[10]讨论了在乘性噪声和加性噪声环境中的相关捕获性能；文献[11]为直扩序列捕获设置自适应门限。

2）借助于辅助的接收序列进行捕获。例如文献[12] 针对长周期序列，采用部分序列尝试捕获重构；文献[13]中设计出一种串行接收机，主要利用辅助序列对初始状态进行修正，从而提高捕获速度；文献[14]通过建立预备的估计序列协助后续序列并行捕获。

相关捕获法每次只对一个可能的初始状态与接收序列进行相关运算，所以当PN序列的周期巨大时，现有上述方法将无法实时进行捕获[15]。所以如何设计序列计算结构，降低相关运算的复杂度是提高序列捕获性能的根本。

为此本文提出位反移位序列捕获算法。算法首先构造了位反向量和移位位反向量，这两个向量凭借序列控制状态刻画了两序列状态改变量的映射关系，因此算法可通过直接建立待捕获序列状态与后续序列状态间的误码对应关系，降低滑动相关运算的复杂度。为保证算法的实时性，降低接收机的存储空间，本文还推导、证明了序列控制状态的生成规律。最终算法可以通过查询移位位反向量表来实现低复杂度的序列捕获过程，将捕获复杂度从常规的O（n2）下降为O（n）。

1 序列状态与的元素映射关系

移位位反向量表主要用于降低移位相关的复杂度，提高计算序列相关峰的速度。其主要思想是讨论序列状态改变后的后续状态变化关系。利用此关系建立序列相关的移位位反向量表，通过查表直接修改序列状态后续的状态，从而实现序列快速遍历相关。移位位反向量的基础是序列状态与元素间的映射关系，下面进行该映射关系的讨论。

由于引入了控制状态，移位位反序列捕获算法可以利用较小的存储空间快速实现捕获。原本算法需要大量的空间存储位反向量和移位位反向量，从而以存储空间换取序列捕获速度。以式（12）所示的序列为例，每个向量需要42b存储空间，通常采用8B存放，当信噪比低导致每个序列状态中误码平均为3个时，需要的存储空间为2×423×8=1.185408（MB），随着待捕获序列中的误码数量增多，需要本地存储空间增大。为了在此算法中减少本地存储空间，本文通过理论分析证明了移位位反向量的生成规律（见文中定理1）。利用定理中描述的规律可以实时生成全部本地所存储的向量，此时本地所需的存储空间降为42×8=336（B），最终使得移位位反序列捕获算法所需的存储空间较小。

5 结语

本文提出了移位位反序列捕获算法，算法的主要思想是在序列捕获的试错过程中，通过建立序列状态间的改变量对应关系，直接对前次试错结果进行修改，以得到下一次试错结果，从而降低序列捕获过程的复杂度。在研究过程中，发现序列状态的改变量对应关系可以用具有一一映射关系的移位向量和移位位反向量来表示，从而依据该关系设计出移位位反序列捕获算法，使得捕获性能相同的基础上，复杂度从常规的O（n2）下降为O（n）。为进一步提高序列捕获效率，在后续的研究中需要对每次试错结果对后续试错的启发式信息进行挖掘，以减少试错次数，降低捕获时间。

参考文献：

[1]刘家胜，黄贤武，朱灿焰，等.基于m序列整数调制和置乱的图像加密算法[J].计算机应用，2007，27（1）：118-121.

[2]吉江，黄开枝，金梁，等.可控单积累状态序列捕获算法[J].中国科学：F辑，2009，39（10）：1112-1124.

[3]花文昭，赵龙，韩文报.椭圆曲线线性同余序列的格攻击[J].计算机应用，2011，31（S2）： 97-99.

[4]YANG LL， HANZO L.Acquisition of msequences using recursive soft sequential estimation [J].IEEE Transactions on Communications， 2004， 52（2）：199-204.

[5]LIU Y Z， PAN Y H， YAO F Q. A modified adaptive filtering acquisition method for PN code with data modulation [J]. IEEE Communications Letters， 2011， 15（8）： 869-871.

[6]SHEN F， GAI M， HE R.PN code acquisition using locally optimum statistics in blind channels [C]// Proceedings of the 2011 3rd International Conference on Advanced Computer Control. Piscataway： IEEE， 2011： 337-340.

[7]冯富强， 陈鹏举， 武传华， 等.低信噪比条件下DS信号的检测和参数估计[J].通信学报， 2002， 23（9）：63-67.

[8]KIM CJ， LEE HJ， LEE HS.Adaptive acquisition of PN sequences for DSSS communications [J].IEEE Transactions on Communications， 1998， 46（8）：993-996.

[9]DU X H， ZHANG T Q， GAO Y S， et al. Analysis on PN code acquisition performance in DSSS over multipath environment [C]// Proceedings of the 3rd International Congress on Image and Signal Processing. Piscataway： IEEE， 2010， 9： 4349-4353.

[10]SHEN F， GAI M， WANG ZL， et al. Code acquisition using the locally optimum test statistics in both multiplicative and additive noises [C]// Proceedings of the 2011 IEEE International Conference on Mechatronics and Automation. Piscataway： IEEE， 2011：1 174-1178.

[11]YEOM S， JUNG Y， LEE S.An adaptive threshold technique for fast PN code acquisition in DSSS systems [J]. IEEE Transactions on Vehicular Technology， 2011， 60（6）： 2870-2875.

[12]LI H， LU M， FENG Z.Partialcorrelationresult reconstruction technique for weak global navigation satellite system long pseudonoisecode acquisition [J]. IET Radar Sonar Navigation， 2011， 5（7）： 731-740.

[13]SALIH M， TANTARARATANA S.A closedloop coherent PN acquisition system with a preloop estimator [J]. IEEE Transactions on Communications， 1999， 47（9）：1394-1405.

[14]DELVA J G R， HOWITT I. PN acquisition for DS/SS using a preloop parallel binary search phase estimator and a closedloop selective search subsystem [J]. IEEE Transactions on Wireless Communications， 2004， 3（2）：408-417.

[15]钟锦， 王大刚.图像信息安全处理的矩阵序列的周期性性质[J].计算机应用， 2012， 32（9）：2592-2594.