作者；张毅
伪随机序列具有以下特征：一方面它是可以预先确定的，并且可以重复地生产和复制；另一方面它又具有某种随机序列的随机特性（即统计特性）。随机噪声的存在会对输出信号进行干扰，使信号产生失真。然而，人们在试图消除和减少通信系统中的随机噪声的同时也希望获得随机噪声并充分利用它，用于更为有效的通信。目前先进长期演进(long time evolution advance，LTE -A)正是利用伪随机序列来对有用信号进行加扰以提高在无线通信环境中的性能。它是利用一对周期和速率均相同的m序列优选对异或后得到的。
在实际的项目工程中，不仅要求能够快速准确地实现通信，还要求尽量减少复杂度和内存占用量。笔者主要从LTE -A中的Gold序列生成过程中内存占用和执行时间两个方面来进行研究。基于所做的LTE -A综测仪项目，本文提出一种循环替换算法。与常规算法相比，该算法可以大大减少内存，提高执行速度。
1 Gold序列生成算法
1.1 LTE -A系统伪随机序列的生成
在LTE -A协议中，伪随机序列是由长度为31位的Gold序列生成的，用c(n)表示最后输出的伪随机序列，其中n=1，2，3，…，M，M为c(n)的长度。用x1(n)和X2(n)表示两个m序列，且x1(n)和x2(n)满足下面的初始化：
不同的场合Ciru．的值不同。例如在LTE -A物理广播信道( physical broadcast channel channel, PBCH)中，c；。。= NIcD'I（小区ID）；在下行共享信道中(physicaldownlink shared channel,PDSCH):
式中：n。为时隙号；nRNTI与无线网络临时鉴定(radionetwork temporary identifier,RNTI)有关。
x1(n)和X2(n)的递推公式为：
伪随机序列由下式决定：
式中：N。=1 600，N。是为了保证不同序列之间的非相关性而特意增加的状态偏移量。
1.2伪随机序列的常规算法
伪随机序列c(n)生成过程中，两个m序列分别由31个带有反馈的线性移位寄存器移位产生。从上面的式子可以看出，正是Nc的存在使得两个m序列x1(n)和x2(n)在普通算法中各自都要首先迭代Ne次，而且Gold序列作为伪随机序列运用在多种场合，并且有些应用场合系统所需要生成的伪随机序列非常短。例如，伪随机序列作为PBCH的RS序列时，所需序列的长度为48 bits，利用常规算法生成RS序列时需要移位l648次，而生成的序列长度为48 bit，导致序列生成时间较长，且浪费了大量的系统资源。由式(5)可知，c(n)序列只与x1(n)和X2(n)的后M个值有直接关系，如果将x1(n)和X2(n)的全部值都保存起来会浪费大量的内存，在大的项目工程中则会影响系统的健壮性。正是基于这一点，提出了一种新的实现方法，可以节省大量内存，提高随机序列生成的速度。
1.3算法优化
目前，很多人对随机序列生成中面临的问题进行了研究，也提出了很多的算法来优化随机序列的生成。例如，在文献[3]中，提出利用状态转移矩阵和初始向量来减少两个m序列x1(n)和X2(n)生成时的多次移位迭代。x1(n)定义公式写成：
根据式(3)可知，ho =1，h。=0，n=1，2，3，…，30。定义初始状态向量：
根据式(3)可知，移位反馈寄存器移位一次后的初始状态向量变为：
式中：x．(31)是由式(3)计算出来的；x1(1)，x1(2)，…，x1(30)是由向量vo左移一位得到的。
则初始状态向量左移k次得到中间向量Vk：
根据上面的分析可以得到31×31的状态转移矩阵M，其中矩阵的初始值和式(3)中的系数h。(n=0，1，2，3，…，30)有关：
利用状态转移矩阵，可得中间向量vl的计算公式为：
则移位反馈寄存器任意移动K次得到的中间向量为：
式中：l，。向量为序列的第k位与第h+30位之间的值。
在式(12)中，根据状态转移矩阵M的初始状态值可以计算出矩阵Mk，利用序列初始状态值与矩阵M的乘积一次完成K次序列移位。该方法确实可以一次得到移位寄存器K次移位，节省很多中间值存储所占用的资源，对节省内存起到一定的作用。但是文献[4]没有考虑矩阵Mk的计算复杂度。在单个DSP中，矩阵的乘法是利用多层次的循环来实现的。如果不使用并行优化，对两个4x4的矩阵相乘所需要的行周期为3 963，至于维数为31×31的两个矩阵的乘法，运行时间将会大大增加，这在实际项目工程中是不适用的。因此，提出了一种新的算法，不仅可以节省内存，还可以减少运行时间。
文献[4]将分段思想应用到伪随机序列的生成中。在此启发下，将循环替换思想应用到伪随机序列的常规生成算法中。循环替换算法示意图如图1所示。
从图1可以看到，内存分配只需要36个单元，每次迭代后的新一轮数据被放到与前一轮中对应的单元中，对应图中为x1(32n)放在了x1(0)单元中。这样仅占用36 x2个单元就完成了x1(n)和X2(n)各自的前1 600个数据的获取。
本例中，根据N=1 600来选择前部分的长度为32，后半部分的数据与随机序列的生成机制有关，在本例中是必须的。该方法可应用到类似的算法中（即中间值在之后计算中不需要时），可以省去大量不必要的中间值存储，节省了内存资源。
2 DSP实现及仿真分析
2.1 DSP实现流程
改进算法在DSP中实现的流程图如图2所示。
本文采用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，序列长度为l 920 bit；
扰码序列，带宽为50RB，序列长度为2 300 bit。
用这6组数据进行仿真，结果如图3所示。
为了清楚地表示3种算法的执行效率，图3中横坐标采用对数形式。
从图3可以看到，与传统算法相比，M算法有比较好的性能，随着随机序列长度的增加，M算法所执行的周期数和常规算法的执行时间差距呈线性增加。与M算法相比，循环替换算法可以更快地实现随机序列的生成，当序列的长度很大时，它们之间的时间差变化不大。在时间要求不是很严格的场景，m序列也有比较好的性能。图4给出了3种算法占用内存的性能比较。
从图4可以看出，3种算法所占用的内存随着序列长度的增长而线性增长，且随着序列长度的增长，循环替换算法和M算法所占内存差是常数，这两种算法和常规算法所占用的内存差随着序列长度的增加而线性增加。其中，循环替换算法所占用的内存几乎为常规算法所占内存的三分之一。
3结束语
针对伪随机序列生成过程中大量中间值的不必要的内存占用问题，提出了应用循环替换思想来实现LTE -A系统中伪随机序列的生成。通过将常规算法、M算法和循环替换算法在时间复杂度和占用内存两个方面进行比较可知，M算法和循环替换算法要优于常规算法，尤其是循环替换算法可以节省常规算法三分之一的时间和几乎一半以上的内存使用量。循环替换算法和M算法相比，循环替换算法优于M算法。该算法的可行性和实时性使其能够很好地应用到作者参与的实验室项目工程中。通过详细介绍循环替换算法的执行过程，说明了该算法可以推广到类似的计算过程中，可以节省时间并占用少量的内存。
4摘要：在先进长期演进( LTE - A)系统中，伪随机序列生成时内存占用量和执行时间会随着序列长度的增加而显著增加。针对该问题，提出了一种循环替换算法，即在3CPP LTE -A系统中的低消耗（内存）、低复杂度的伪随机序列生成算法。此外，对传统伪随机序列生成算法进行了改进，使得伪随机序列生成过程中的内存占用量和执行时间大大缩短。仿真结果证明了所提出算法的高效性和低消耗性。该算法对提高整个系统的性能有一定的意义。
