基于LTE-A的伪随机序列生成的改进算法

An Improved Algorithm Based on LTE-A for Pseudo Random Sequence Generation

李小文　李淑娜　苏建松

(重庆邮电大学通信与信息工程学院，重庆　400065)



基于LTE-A的伪随机序列生成的改进算法

An Improved Algorithm Based on LTE-A for Pseudo Random Sequence Generation

李小文李淑娜苏建松

(重庆邮电大学通信与信息工程学院，重庆400065)

摘要：在先进长期演进(LTE-A)系统中，伪随机序列生成时内存占用量和执行时间会随着序列长度的增加而显著增加。针对该问题，提出了一种循环替换算法，即在3GPP LTE-A系统中的低消耗(内存)、低复杂度的伪随机序列生成算法。此外，对传统伪随机序列生成算法进行了改进，使得伪随机序列生成过程中的内存占用量和执行时间大大缩短。仿真结果证明了所提出算法的高效性和低消耗性。该算法对提高整个系统的性能有一定的意义。

关键词：随机序列循环替换算法算法改进DSP实现信息通信

Abstract：In LTE-A system,memory usage and execution time for generating pseudo random sequence are significantly increasing with the increment of the sequence length.For solving this problem,the circularly replacement algorithm is proposed.This generation algorithm features low memory consumption and low complexity in 3GPP LTE-A system.In addition,the traditional pseudo random sequence generation algorithm is improved.The memory usage and execution time in pseudo random sequence generation is greatly reduced.The simulation results verify the high efficiency and low consumption of the proposed algorithm.This algorithm possesses certain significance for enhancing the performance of entire system.

Keywords:Random sequenceCircularly replacement algorithmAlgorithm improvementDSP implementationInformation communication

0引言

通信现代化是人类社会进入信息时代的重要标志，怎样在恶劣的环境条件下保证通信有效地、迅速地进行是当今摆在通信工作者面前的一大课题。伪随机序列具有以下特征：一方面它是可以预先确定的，并且可以重复地生产和复制；另一方面它又具有某种随机序列的随机特性(即统计特性)。随机噪声的存在会对输出信号进行干扰，使信号产生失真。然而，人们在试图消除和减少通信系统中的随机噪声的同时也希望获得随机噪声并充分利用它，用于更为有效的通信。目前先进长期演进(long time evolution advance,LTE-A)[1]正是利用伪随机序列来对有用信号进行加扰以提高在无线通信环境中的性能。它是利用一对周期和速率均相同的m序列优选对异或后得到的。

在实际的项目工程中，不仅要求能够快速准确地实现通信，还要求尽量减少复杂度和内存占用量。笔者主要从LTE-A中的Gold序列生成过程中内存占用和执行时间两个方面来进行研究。基于所做的LTE-A综测仪项目，本文提出一种循环替换算法。与常规算法相比，该算法可以大大减少内存，提高执行速度。

1Gold序列生成算法

1.1LTE-A系统伪随机序列的生成

在LTE-A协议[1]中，伪随机序列是由长度为31位的Gold序列生成的，用c(n)表示最后输出的伪随机序列，其中n=1,2,3,…，M，M为c(n)的长度。用x1(n)和x2(n)表示两个m序列，且x1(n)和x2(n)满足下面的初始化：

(1)

(2)

式中：ns为时隙号;nRNTI与无线网络临时鉴定 (radio network temporary identifier,RNTI)有关。

x1(n)和x2(n)的递推公式为：

x1(n+31)=[x1(n+3)+x1(n)]mod2

(3)

x2(n+31)=[x2(n+3)+x2(n+2)+

x2(n+1)+x2(n)]mod2

(4)

伪随机序列由下式决定：

c(n)=[x1(n+Nc)+x2(n+Nc)]mod2

(5)

式中：Nc=1 600，Nc是为了保证不同序列之间的非相关性而特意增加的状态偏移量。

1.2伪随机序列的常规算法

伪随机序列c(n)生成过程中，两个m序列分别由31个带有反馈的线性移位寄存器移位产生。从上面的式子可以看出，正是Nc的存在使得两个m序列x1(n)和x2(n)在普通算法中各自都要首先迭代Nc次，而且Gold序列作为伪随机序列运用在多种场合[2]，并且有些应用场合系统所需要生成的伪随机序列非常短。例如，伪随机序列作为PBCH的RS序列时，所需序列的长度为48 bits，利用常规算法生成RS序列时需要移位1 648次，而生成的序列长度为48 bit，导致序列生成时间较长，且浪费了大量的系统资源。由式(5)可知，c(n)序列只与x1(n)和x2(n)的后M个值有直接关系，如果将x1(n)和x2(n)的全部值都保存起来会浪费大量的内存，在大的项目工程中则会影响系统的健壮性。正是基于这一点，提出了一种新的实现方法，可以节省大量内存，提高随机序列生成的速度。

1.3算法优化

目前，很多人对随机序列生成中面临的问题进行了研究，也提出了很多的算法来优化随机序列的生成。例如，在文献[3]中，提出利用状态转移矩阵和初始向量来减少两个m序列x1(n)和x2(n)生成时的多次移位迭代。x1(n)定义公式写成：

x1(n+31)=h30x1(n+30)+h29x1(n+29)+

h28x1(n+28)+…+h0x1(n)

(6)

根据式(3)可知，h0=1，hn=0，n=1,2,3,…,30。定义初始状态向量：

v0=[x1(0),x1(1),…,x1(30)]

(7)

根据式(3)可知，移位反馈寄存器移位一次后的初始状态向量变为：

v1=[x1(1),x1(2),…,x1(31)]

(8)

式中：x1(31)是由式(3)计算出来的；x1(1),x1(2),…,x1(30)是由向量v0左移一位得到的。

则初始状态向量左移k次得到中间向量vk：

vk=[x1(1+k),x1(2+k),…,x1(31+k)]

(9)

根据上面的分析可以得到31×31的状态转移矩阵M，其中矩阵的初始值和式(3)中的系数hn(n=0,1,2,3,…,30)有关：

(10)

利用状态转移矩阵，可得中间向量v1的计算公式为：

v1=v0M

(11)

则移位反馈寄存器任意移动K次得到的中间向量为：

(12)

式中：vk向量为序列的第k位与第k+30位之间的值。

在式(12)中，根据状态转移矩阵M的初始状态值可以计算出矩阵Mk，利用序列初始状态值与矩阵Mk的乘积一次完成K次序列移位。该方法确实可以一次得到移位寄存器K次移位，节省很多中间值存储所占用的资源，对节省内存起到一定的作用。但是文献[4]没有考虑矩阵Mk的计算复杂度。在单个DSP中，矩阵的乘法是利用多层次的循环来实现的。如果不使用并行优化，对两个4×4的矩阵相乘所需要的运行周期为3 963，至于维数为31×31的两个矩阵的乘法，运行时间将会大大增加，这在实际项目工程中是不适用的。因此，提出了一种新的算法，不仅可以节省内存，还可以减少运行时间。

文献[4]将分段思想应用到伪随机序列的生成中。在此启发下，将循环替换思想应用到伪随机序列的常规生成算法中。循环替换算法示意图如图1所示。

从图1可以看到，内存分配只需要36个单元，每次迭代后的新一轮数据被放到与前一轮中对应的单元中，对应图中为x1(32n)放在了x1(0)单元中。这样仅占用36×2个单元就完成了x1(n)和x2(n)各自的前1 600个数据的获取。

本例中，根据Nc=1 600来选择前部分的长度为32，后半部分的数据与随机序列的生成机制有关，在本例中是必须的。该方法可应用到类似的算法中(即中间值在之后计算中不需要时)，可以省去大量不必要的中间值存储，节省了内存资源。

图1　循环替换算法示意图

2DSP实现及仿真分析

2.1DSP实现流程

改进算法在DSP中实现的流程图如图2所示。

图2　DSP实现流程图

本文采用TI公司的C64x系列实现DSP。该系列DSP采用了取指令和执行指令可并行运行的哈佛结构，程序总线和数据总线也是独立运行的。其中，程序总线有256 bit，内存单次操作取8条指令，达到了高度运行的目的。由于C64芯片具有高容量、运行速度快的特征，其被应用于综合测试仪表的开发中。

2.2仿真分析

为比较常规算法、M(矩阵)算法和循环替换算法的优劣，从时间复杂度和所占用的内存两个方面进行仿真分析。考虑下面几种情形下3种算法的时间复杂度和内存占用量：

RS序列，带宽为6RB，序列长度为24 bit；

RS序列，带宽为6RB，序列长度为120 bit；

RS序列，带宽为50RB，序列长度为200 bit；

RS序列，带宽为100RB，序列长度为400 bit；

扰码序列，带宽为50RB，序列长度为1 920 bit；

扰码序列，带宽为50RB，序列长度为2 300 bit。

用这6组数据进行仿真，结果如图3所示。

图3　时间复杂度比较示意图

为了清楚地表示3种算法的执行效率，图3中横坐标采用对数形式。

从图3可以看到， 与传统算法相比，M算法有比较好的性能，随着随机序列长度的增加，M算法所执行的周期数和常规算法的执行时间差距呈线性增加。与M算法相比，循环替换算法可以更快地实现随机序列的生成，当序列的长度很大时，它们之间的时间差变化不大。在时间要求不是很严格的场景，m序列也有比较好的性能。图4给出了3种算法占用内存的性能比较。

图4　占用内存比较图示意图

从图4可以看出，3种算法所占用的内存随着序列长度的增长而线性增长，且随着序列长度的增长，循环替换算法和M算法所占内存差是常数，这两种算法和常规算法所占用的内存差随着序列长度的增加而线性增加。其中，循环替换算法所占用的内存几乎为常规算法所占内存的三分之一。

3结束语

针对伪随机序列生成过程中大量中间值的不必要的内存占用问题，提出了应用循环替换思想来实现LTE-A系统中伪随机序列的生成。通过将常规算法、M算法和循环替换算法在时间复杂度和占用内存两个方面进行比较可知，M算法和循环替换算法要优于常规算法，尤其是循环替换算法可以节省常规算法三分之一的时间和几乎一半以上的内存使用量。循环替换算法和M算法相比，循环替换算法优于M算法。

该算法的可行性和实时性使其能够很好地应用到作者参与的实验室项目工程中。通过详细介绍循环替换算法的执行过程，说明了该算法可以推广到类似的计算过程中，可以节省时间并占用少量的内存。

参考文献

[1] 3GPP TS 36.211v9.1.0,3rd Generation Partnership Project；Technical Specification Group Ration Access Network；Evolued Universal Terrestrial Radios Access(E-UTRA);Physical Channels and Modulation(Release 9)[S].2010.

[2] Divyanjali A,Pareek V.A new approach to pseudo random number generation[C]// International Conference on Advanced Computing & Communication Technologies,2014.

[3] 周孝忠，闵子健，袁慧梅.一种3GPP LTE伪随机序列生成优化算法[J].电视技术,2009,49(9):15-23.

[4] Min Lequan,Hu Kexin,Zhang Lijiao,et al.Study on Pseudo randomness of Some Pseudo random Number Generators with Application[C]//Ninth International Conference on Computational Intelligence and Security, 2013.

中图分类号：TH86;TP301+.6

文献标志码：A

DOI:10.16086/j.cnki.issn1000-0380.201602005

国家重大科技专项基金资助项目(编号：2011ZX03001-003-01、2012ZX03001009-004)。

修改稿收到日期：2015-05-20。

第一作者李小文(1955-)，男,1988年毕业于重庆大学信号与系统专业，获硕士学位，高级工程师；主要研究方向为无线移动通信系统协议。