(12)发明专利申请
(10)申请公布号 CN 109375897 A(43)申请公布日 2019.02.22
(21)申请号 201710657524.1(22)申请日 2017.08.03
(71)申请人 普天信息技术有限公司
地址 100080 北京市海淀区海淀北二街6号
普天大厦(72)发明人 郭旭兵 徐荣荣
(74)专利代理机构 北京路浩知识产权代理有限
公司 11002
代理人 王莹 李官(51)Int.Cl.
G06F 7/58(2006.01)
权利要求书2页 说明书10页 附图3页
(54)发明名称
伪随机序列的生成方法
(57)摘要
本发明提供了一种伪随机序列的生成方法，根据N个第一初始数据和N个第二初始数据，分别计算N个第一数据和N个第二数据，并分别作为第一移位寄存器的初始数据和第二移位寄存器的初始数据。根据第一移位寄存器和第二移位寄存器的初始数据可通过一个时钟周期生成伪随机序列中的第一个数据，并且每一个时钟周期产生伪随机序列中的一个数据，最终生成伪随机序列。生成伪随机序列中的第一个数据只需一个时钟周期，大大提高了生成伪随机序列的速度，缩短了生成时间。
CN 109375897 ACN 109375897 A
权 利 要 求 书
1/2页
1.一种伪随机序列的生成方法，其特征在于，包括：S1，分别获取N个第一初始数据和N个第二初始数据；N为大于3的整数；S2，根据所述N个第一初始数据，基于第一递推公式，计算N个第一数据，并将所述N个第一数据作为第一移位寄存器的初始数据；
S3，根据所述N个第二初始数据，基于第二递推公式，计算N个第二数据，并将所述N个第二数据作为第二移位寄存器的初始数据；
S4，根据所述第一移位寄存器的初始数据和所述第二移位寄存器的初始数据，生成所述伪随机序列。
2.根据权利要求1所述的生成方法，其特征在于，S2具体包括：基于第一递推公式，通过所述N个第一初始数据中若干个第一初始数据对所述N个第一数据中每一个第一数据进行表示，并计算所述N个第一数据。
3.根据权利要求2所述的生成方法，其特征在于，所述第一递推公式通过如下公式迭代计算得到：
x1(n+N)＝[x1(n+3)+x1(n)]mod2其中，x1(n+N)为第一子序列x1中第n+N个数据，且所述x1中的前N个数据x1(0)～x1(N-1)为所述N个第一初始数据，n≥0。
4.根据权利要求3所述的生成方法，其特征在于，所述第一递推公式如下：
其中，x1(n)为所述x1中第n+1个数据，表示不大于n/N的最大整数，的最大整数，^为异或运算符号。
表示不大于
5.根据权利要求2所述的生成方法，其特征在于，S3具体包括：基于第二递推公式，通过所述N个第二初始数据中若干个第二初始数据对所述N个第二数据中每一个第二数据进行表示，并计算所述N个第二数据。
6.根据权利要求5所述的生成方法，其特征在于，所述第二递推公式通过如下公式迭代计算得到：
x2(n+N)＝[x2(n+3)+x2(n+2)+x2(n+1)+x2(n)]mod2其中，x2(n+N)为第二子序列x2中第n+N个数据，且所述x2中的前N个数据x2(0)～x2(N-1)为所述N个第二初始数据，n≥0。
7.根据权利要求6所述的生成方法，其特征在于，所述第二递推公式如下：
其中，x2(n)为所述x2中第n+1个数据，表示不大于n/N的最大整数，的最大整数，^为异或运算符号。
8.一种伪随机序列的生成设备，其特征在于，包括：
2
表示不大于
CN 109375897 A
权 利 要 求 书
2/2页
至少一个处理器；以及与所述处理器通信连接的至少一个存储器，其中：所述存储器存储有可被所述处理器执行的程序指令，所述处理器调用所述程序指令以执行如权利要求1至7任一所述的生成方法。
9.一种计算机程序产品，其特征在于，所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，使所述计算机执行如权利要求1至7任一所述的生成方法。
10.一种非暂态计算机可读存储介质，其特征在于，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行如权利要求1至7任一所述的生成方法。
3
CN 109375897 A
说 明 书伪随机序列的生成方法
1/10页
技术领域
[0001]本发明涉及通信技术领域，更具体地，涉及伪随机序列的生成方法。
背景技术
[0002]目前，伪随机序列在扩频通信系统中用于与调制后的信号相乘以扩展信号的带宽，或者用于实现数据加扰。实现简单伪随机序列的现有硬件电路通常是带有抽头结构的移位寄存器。在实际应用中，用于与信号相调制或解调的伪随机序列并不是单一序列，而是多个具有不同初始值的伪随机序列进行某种逻辑运算的结果。在长期演进技术的后续演进(Long Term Evolution Advance，LTE-A)系统中，伪随机序列的生成函数为两个子序列x1(n+NC)与x2(n+NC)进行模二加法的结果。[0003]在LTE-A系统中，承载不同业务的物理信道要求不同初始值的伪随机序列，例如在物理广播信道(physical broadcast channel，PBCH)中，要求初始值
其中，ID为
小区标识。而在下行共享信道(physical downlink control channel，PDCCH)要求初始值
其中，ns为时隙号，nRNTI与无线网络临时鉴定
(radio network temporary identifier，RNTI)。硬件实现中，对序列生成的实时性要求非常严格，但是通常生成伪随机序列的电路需要多个时钟周期的初始化之后，才能完成一个伪随机序列中第一个数据的计算输出。LTE-A系统中的伪随机序列可通过下式表示：c(n)＝[x1(n+NC)+x2(n+NC)]mod2，其中，x1(n+31)＝[x1(n+3)+x1(n)]mod2，x2(n+31)＝[x2(n+3)+x2(n+2)+x2(n+1)+x2(n)]mod2。式中子序列x1(n)与x2(n)分别为两个m序列，NC＝1600，NC是为了保证两个不同的m序列之间的非相关性而增加的状态偏移量，mod2表示对前面的数据进行模2加法运算。伪随机序列C的生成过程中，两个子序列x1(n)与x2(n)分别由31个带有反馈的线性移位寄存器移位产生，其中x1(0)～x1(30)与x2(0)～x2(30)分别为x1(n)与x2(n)的已知的初始值或者可间接计算得到的初始值。因此，由于NC的存在，要得到c(0)的值，在现有技术的普通算法中，至少需要等待NC个时钟周期完成x1(NC)与x2(NC)的计算，即需要迭代NC次才能计算出c(0)。
[0004]现有的伪随机序列C生成电路结构如图1所示。在初始状态下，子序列x1(n)与x2(n)的31个初始值分别装填在深度为31位的移位寄存器，然后移位寄存器在时钟的驱动下运行，分别计算出x1(n)与x2(n)的后续值，伪随机序列C的第一个数据c(0)需要等待1600个时钟周期之后，由x1(1600)与x2(1600)计算得出。
[0005]现有的伪随机序列的生成方法需要经过多次迭代才能计算得到需要的伪随机序列，大大增加了生成伪随机序列需要的时间，降低了生成伪随机序列的速度。发明内容
[0006]为克服上述问题或者至少部分地解决上述问题，本发明提供了一种伪随机序列的生成方法。
[0007]一方面，本发明提供了1、一种伪随机序列的生成方法，包括：S1，分别获取N个第一
4
CN 109375897 A
说 明 书
2/10页
初始数据和N个第二初始数据；N为大于3的整数；S2，根据所述N个第一初始数据，基于第一递推公式，计算N个第一数据，并将所述N个第一数据作为第一移位寄存器的初始数据；S3，根据所述N个第二初始数据，基于第二递推公式，计算N个第二数据，并将所述N个第二数据作为第二移位寄存器的初始数据；S4，根据所述第一移位寄存器的初始数据和所述第二移位寄存器的初始数据，生成所述伪随机序列。[0008]优选地，S2具体包括：基于第一递推公式，通过所述N个第一初始数据中若干个第一初始数据对所述N个第一数据中每一个第一数据进行表示，并计算所述N个第一数据。[0009]优选地，所述第一递推公式通过如下公式迭代计算得到：[0010]x1(n+N)＝[x1(n+3)+x1(n)]mod2[0011]其中，x1(n+N)为第一子序列x1中第n+N个数据，且所述x1中的前N个数据x1(0)～x1(N-1)为所述N个第一初始数据，n≥0。[0012]优选地，所述第一递推公式如下：
[0013][0014]
其中，x1(n)为所述x1中第n+1个数据，表示不大于n/N的最大整数，的最大整数，^为异或运算符号。
表示不
大于
[0015]
优选地，S3具体包括：基于第二递推公式，通过所述N个第二初始数据中若干个第二初始数据对所述N个第二数据中每一个第二数据进行表示，并计算所述N个第二数据。[0016]优选地，所述第二递推公式通过如下公式迭代计算得到：[0017]x2(n+N)＝[x2(n+3)+x2(n+2)+x2(n+1)+x2(n)]mod2[0018]其中，x2(n+N)为第二子序列x2中第n+N个数据，且所述x2中的前N个数据x2(0)～x2(N-1)为所述N个第二初始数据，n≥0。[0019]优选地，所述第二递推公式如下：
[0020]
[0021]其中，x2(n)为所述x2中第n+1个数据，表示不大于n/N的最大整数，的最大整数，^为异或运算符号。
表示不
大于
[0022]
另一方面，本发明提供了一种伪随机序列的生成设备，包括：至少一个处理器；以及与所述处理器通信连接的至少一个存储器，其中：所述存储器存储有可被所述处理器执行的程序指令，所述处理器调用所述程序指令以执行上述的生成方法。[0023]另一方面，本发明提供了一种计算机程序产品，所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，使所述计算机执行上述的生成方法。[0024]另一方面，本发明提供了一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行上述的生成方法。
5
CN 109375897 A[0025]
说 明 书
3/10页
本发明提供的伪随机序列的生成方法，根据N个第一初始数据和N个第二初始数
据，分别计算N个第一数据和N个第二数据，并分别作为第一移位寄存器的初始数据和第二移位寄存器的初始数据。根据第一移位寄存器和第二移位寄存器的初始数据可通过一个时钟周期生成伪随机序列中的第一个数据，并且每一个时钟周期产生伪随机序列中的一个数据，最终生成伪随机序列。生成伪随机序列中的第一个数据只需一个时钟周期。避免了通过第一移位寄存器和第二移位寄存器，直接根据N个第一初始数据和N个第二初始数据，经过指定数量的时钟周期后才能得到伪随机序列的第一个数据。生成伪随机序列的第一个数据的过程中，不需要进行迭代，只需通过一个时钟周期即可完成，大大提高了生成伪随机序列的速度，缩短了生成时间。附图说明
[0026]图1为现有技术中伪随机序列的生成电路结构示意图；
[0027]图2为本发明实施例提供的一种伪随机序列的生成方法流程图；
[0028]图3为本发明实施例提供的一种伪随机序列的生成方法中x1(n+NC)递归生成关系的示意图；
[0029]图4为本发明实施例提供的一种伪随机序列的生成方法中x2(n+NC)递归生成关系的示意图；
[0030]图5为本发明实施例提供的一种伪随机序列的生成方法流程图；
[0031]图6为现有技术中计算第一子序列中任一个数据时的递归实例个数和递归深度之间的关系示意图；
[0032]图7为现有技术中计算第二子序列中任一个数据时的递归实例个数和递归深度之间的关系示意图；
[0033]图8为本发明实施例提供的一种伪随机序列的生成方法流程图。
具体实施方式
[0034]下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。
[0035]通常为了使得生成的伪随机序列满足某种特定的需求，使用现有方法生成伪随机序列C时，通常是将多个不同的子序列的输出结果进行某种逻辑运算之后作为当前时刻的伪随机序列，需要进行多次递归式迭代才能得到。并且，生成伪随机序列C中不同序号的数据时，递归深度可能不同，表现在硬件电路的实现上，这些递归迭代运算需要多个时钟周期的计算才能完成。[0036]如图2所示，本发明一实施例提供了一种伪随机序列的生成方法，包括：S1，分别获取N个第一初始数据和N个第二初始数据；N为大于3的整数；S2，根据所述N个第一初始数据，基于第一递推公式，计算N个第一数据，并将所述N个第一数据作为第一移位寄存器的初始数据；S3，根据所述N个第二初始数据，基于第二递推公式，计算N个第二数据，并将所述N个第二数据作为第二移位寄存器的初始数据；S4，根据所述第一移位寄存器的初始数据和所述第二移位寄存器的初始数据，生成所述伪随机序列。[0037]具体地，如果一个序列，一方面它是可以预先确定的，并且是可以重复地生产和复
6
CN 109375897 A
说 明 书
4/10页
制；另一方面它又具有某种随机序列的随机特性(即统计特性)，这种序列为伪随机序列。伪随机序列是具有某种随机特性的确定的序列，由移位寄存器产生。m序列是最长线性反馈移存器序列的简称，它是由带线性反馈的移存器产生的周期最长的一种序列。m序列对优选的两个n次本原多项式乘积构成的新序列为Gold序列，或m序列对优选的两个本原多项式所产生序列的移位模2和对应的新序列也叫做Gold序列。以下以生成Gold序列对本发明方案进行描述，但本发明并不限于生成Gold序列，还可用于生成其他伪随机序列。[0038]在LTE-A系统中，Gold序列由第一子序列和第二子序列组成，每个子序列分别对应有N个初始数据，即N个第一初始数据和N个第二初始数据。这里的N为初始数据的个数，同时也是第一子序列和第二子序列的周期长度，由于Gold序列是由第一子序列和第二子序列组成，所以Gold序列的周期长度也为N。
[0039]由于第一子序列和第二子序列的初始数据均为N个，与第一子序列匹配的第一移位寄存器的位数也需要是N个，同样的，与第二子序列匹配的第二移位寄存器的位数也需要是N个。所以基于第一递推公式，计算第一子序列中能够用于生成伪随机序列中的第一个数据的N个第一数据，并将N个第一数据作为第一移位寄存器的初始数据。同理，基于第二递推公式，计算第二子序列中能够用于生成伪随机序列中的第一个数据的N个第二数据，并将N个第二数据作为第二移位寄存器的初始数据。[0040]本实施例中，S2和S3的执行顺序是相对独立的，并没有具体的时序关系，既可以先执行S2再执行S3，也可以先执行S3再执行S2，还可以同时执行S2和S3。在此不作具体限定。[0041]根据第一移位寄存器的初始数据和第二移位寄存器的初始数据，经过一个时钟周期可得到伪随机序列中的第一个数据，再基于移位寄存器的性质，每经过一个时钟周期，可产生一个新的数据，经过多个时钟周期后，可得到伪随机序列中的后续数据，生成伪随机序列。
[0042]本实施例中，根据N个第一初始数据和N个第二初始数据分别计算N个第一数据和N个第二数据，并将其分别作为第一移位寄存器和第二移位寄存器的初始数据，根据第一移位寄存器和第二移位寄存器的初始数据，可经过一个时钟周期生成伪随机序列中的第一个数据，并且每经过一个周期产生伪随机序列中的一个数据，最终生成伪随机序列。生成伪随机序列的第一个数据只需一个时钟周期。避免了通过第一移位寄存器和第二移位寄存器，直接根据N个第一初始数据和N个第二初始数据，经过指定数量的时钟周期后才能得到伪随机序列的第一个数据。生成伪随机序列的第一个数据的过程中，不需要进行迭代，只需通过一个时钟周期即可完成，大大提高了生成伪随机序列的速度，缩短了生成时间。[0043]需要注意的是，本发明实施例中提到的“第一”和“第二”仅起区分作用，并不是对时序或顺序的限定。
[0044]在LTE-A系统中，用于扩频的伪随机序列是周期长度N＝31的Gold序列，也就是在Gold序列中有31个初始数据。Gold序列的构成如下：[0045]c(n)＝[x1(n+NC)+x2(n+NC)]mod2
[0046][0047]
由于mod2表示对前面的数据进行模2加法运算，模2加法运算是一种二进制的运
算，等同于“异或”(“异或”的逻辑运算符号为^)运算。所以Gold序列c(n)还可表示为：
7
CN 109375897 A[0048][0049]
说 明 书
5/10页
c(n)＝x1(n+NC)^x2(n+NC)其中，
[0050]
x1为第一子序列，x2为第二子序列。下面引出数据的序号的概念，数据的序号是指
某一序列中，根据每一个数据在序列中的位置，为每一个数据设置不同的序号，从第一个数据开始，依次为每一个数据设置序号，序号分别为0、1、2、3……，其中，序号0对应的数据为第一个数据，序号1对应的数据为第二个数据，并以此类推。例如，第一子序列x1中的x1(0)表示此数据对应的序号为0，在x1中的位置为第一个，即代表x1中的第一个数据。[0052]在Gold序列c(n)的表达式中，第一子序列x1和第二子序列x2均与c(n)相差相同的状态偏移量NC，即要生成c(0)，需要x1(NC)和x2(NC)，生[0053]成c(1)，需要x1(NC+1)和x2(NC+1)，以此类推。x1(n+NC)与x2(n+NC)的递推关系如图3和图4所示。由图中可以得出，x1(n+NC)由前一时刻的两个值x1(n+NC-28)和x1(n+NC-31)决定，x2(n+NC)由前一时刻的四个值x2(n+NC-28)、x2(n+NC-29)、x2(n+NC-30)和x2(n+NC-31)决定。
[0054]根据LTE-A系统的物理信道和调制技术规范，x1与x2的前31个初始数据已经确定或者可以根据信道参数间接确定。初始数据的取值不同，得到的伪随机序列也不相同。[0055]当NC＝1600时，伪随机序列中的第一个数据c(0)＝x1(1600)^x2(1600)，也就是通过对第一子序列中第1601个数据和第二子序列中第1601个数据进行异或运算，得到c(0)。同理，要生成一个伪随机序列C，第一子序列中的数据和第二子序列中的数据都至少需要是第1601个数据或第1601个数据之后的数据。所以，为减小不必要的时钟周期，将第一移位寄存器的初始值分别设置为x1(1600)～x1(1630)，将第二移位寄存器的初始值分别设置为x2(1600)～x2(1630)，这样可在一个时钟周期内生成伪随机序列中的第一个数据，并利用第一移位寄存器和第二移位寄存器的性质，计算待生成的伪随机序列中的每一个数据。[0056]在上述实施例的基础上，S2具体包括：基于第一递推公式，通过所述N个第一初始数据中若干个第一初始数据对所述N个第一数据中每一个第一数据进行表示，并计算所述N个第一数据。[0057]具体地，所述第一递推公式通过如下公式迭代计算得到：[0058]x1(n+N)＝[x1(n+3)+x1(n)]mod2[0059]其中，x1(n+N)为第一子序列x1中第n+N个数据，且所述x1中的前N个数据x1(0)～x1(N-1)为所述N个第一初始数据，n≥0。
[0060]对第一子序列的迭代公式x1(n+N)进行分析，通过迭代公式执行的迭代次数和模2加法的运算，构建第一递推公式。其中迭代次数为
由于模2加法的运算法则可知，对于偶
[0051]
数个相同的数据做模2加法的运算则将该偶数个相同的数据均删除；对于奇数个相同的数据做模2加法的运算则仅保留一个数据，且数据的位置不变。则第一次迭代后与每经过2的倍数次迭代后均只剩下第一项和最后一项。
8
CN 109375897 A[0061][0062][0063]
说 明 书
6/10页
得到第一递推公式如下：
其中，x1(n)为x1中第n+1个数据，n为伪随机序列中任一个数据的序号，N为伪随机
表示不大于
的最大整数。
序列的周期长度，表示不大于n/N的最大整数，
[0064]
以下以N＝31为例，即x1(n+31)＝[x1(n+3)+x1(n)]mod2。对第一子序列的任一个数
据x1(n)，第一次迭代后得到x1(n)＝x1(n-31)^x1(n-28)，第二次迭代后得到：[0065]x1(n)＝x1(n-31×2)^x1(n-31-28)^x1(n-28-31)^x1(n-28×2)[0066]＝x1(n-31×2)^x1(n-28×2)
[0067]再分别对得到的两项利用上述公式进行第三次迭代，得到：
[0068]x1(n)＝x1(n-31×3)^x1(n-31×2-28)^x1(n-28×2-31)^x1(n-28×3)[0069]再分别对得到的两项利用上述公式进行第四次迭代，得到：[0070]x1(n)＝x1(n-31×4)^x1(n-28×4)[0071]以此类推，得到的第一递推公式如下式：
[0072]
[0073]
利用第一递推公式，可计算第一子序列中任一个数据x1(n)。以下以n＝1000，N＝31为例，计算序号为1000的第一数据x1(1000)。
由于
分别得到：
所以x1(1000)＝x1(8)^x1(104)。但由于x1(104)不能直接
[0074]
从第一子序列中已知或间接已知的31个初始数据中得到，需要对x1(104)再次利用第一递推公式，直至将x1(1000)用初始数据表示。x1(104)进一步可表示为x1(104)＝x1(42)^x1(48)＝x1(11)^x1(14)^x1(17)^x1(20)。[0075]综上，x1(1000)＝x1(8)^x1(11)^x1(14)^x1(17)^x1(20)。[0076]利用第一递推公式，可得到第一子序列中的第1601个数据至第1631个数据，即x1(1600)～x1(1630)，也就是31个第一数据，得到的结果如下：
[0077]x1(1600)＝x1(1)^x1(12)^x1(17)^x1(19)^x1(20)^x1(25)^x1(3)^x1(4)^x1(5)^x1(6)^x1(9)
[0078]x1(1601)＝x1(10)^x1(13)^x1(18)^x1(2)^x1(20)^x1(21)^x1(26)^x1(4)^x1(5)^x1(6)^x1(7)
[0079]x1(1602)＝x1(11)^x1(14)^x1(19)^x1(21)^x1(22)^x1(27)^x1(3)^x1(5)^x1(6)^x1(7)^x1(8)[0080]……
[0081]x1(1615)＝x1(1)^x1(12)^x1(16)^x1(18)^x1(19)^x1(20)^x1(21)^x1(24)^x1(27)^x1(3)^
[0082]x1(6)^x1(7)^x1(9)
[0083]x1(1630)＝x1(0)^x1(14)^x1(16)^x1(18)^x1(2)^x1(21)^x1(22)^x1(24)^x1(27)^x1
9
CN 109375897 A
说 明 书
7/10页
(4)^x1(6)^[0084]x1(7)
[0085]在上述实施例的基础上，S3具体包括：基于第二递推公式，通过所述N个第二初始数据中若干个第二初始数据对所述N个第二数据中每一个第二数据进行表示，并计算所述N个第二数据。[0086]具体地，所述第二递推公式通过如下公式迭代计算得到：[0087]x2(n+N)＝[x2(n+3)+x2(n+2)+x2(n+1)+x2(n)]mod2[0088]其中，x2(n+N)为第二子序列x2中第n+N个数据，且所述x2中的前N个数据x2(0)～x2(N-1)为所述N个第二初始数据，n≥0。
[0089]对于第二子序列的迭代公式x2(n+N)进行分析，通过迭代公式执行的迭代次数和模2加法的运算，构建第二递推公式。其中迭代次数为
和
由于公式可等效为第一项
与第二项作异或运算，第三项与第四项作异或运算，得到的结果再进行异或，所以第一项和第二项的迭代次数相同，第三项和第四项的迭代次数相同。[0090]由于模2加法的运算法则可知，对于偶数个相同的数据做模2加法的运算则将该偶数个相同的数据均删除；对于奇数个相同的数据做模2加法的运算则仅保留一个数据，且数据的位置不变。则第一次迭代后与每经过2的倍数次迭代后均只剩下第一项和最后一项。[0091]得到第二递推公式如下：
[0092]
[0093]
其中，x2(n)为所述x2中第n+1个数据，n为伪随机序列中任一个数据的序号，N为伪
表示不大于
的最大整数，
随机序列的周期长度，表示不大于n/N的最大整数，
^为异或运算符号。
[0094]以N＝31为例，即x2(n+31)＝[x2(n+3)+x2(n+2)+x2(n+1)+x2(n)]mod2。利用与得到第一递推公式相同的方法，得到第二递推公式如下：
[0095]
[0096]
利用第二递推公式，可计算第二子序列中任一个数据x2(n)。以下依然以n＝1000为例，计算序号为1000的第二数据x2(1000)。
可分别得到：
[0097][0098][0099]
所以x2
(1000)＝x2(8)^x2(40)^x2(72)^x2(104)。但由于x2(40)、x2(72)和x2(104)均不能直接从第二子序列中已知或间接已知的31个初始数据中得到，需要分别对x2(40)、x2(72)和x1(104)
10
CN 109375897 A
说 明 书
8/10页
再次利用第二递推公式，直至将x2(1000)用初始数据表示。x2(40)进一步可表示为x1(40)＝x1(9)^x1(10)^x1(11)^x1(12)，x2(72)进一步可表示为x1(72)＝x1(10)^x1(12)^x1(14)^x1(16)。x2(104)进一步可表示为：
[0100]x2(104)＝[x2(11)^x2(12)^x2(13)^x2(14)]^[x2(13)^x2(14)^x2(15)^x2(16)]^[0101][x2(15)^x2(16)^x2(17)^x2(18)]^[x2(17)^x2(18)^x2(19)^x2(20)][0102]由于异或(逻辑运算符号为^)，运算规则是：若符号^两侧的数值的每一个二进制位，同值取0，异值取1；同时，对多个数值进行异或运算时，多个数值的顺序不同得到的结果也不相同。所以在计算x2(1000)时，需要将偶数个相同的第二数据全部删除，将奇数个相同的第二数据保留一个，但要保证每个第二数据的位置不变，以避免因第二数据的顺序不同而导致计算得到的结果发生变化。[0103]综上，x2(1000)＝x2(8)^x2(9)^x2(12)^x2(14)^x2(19)^x2(20)。[0104]利用第二递推公式，可得到第二子序列中的第1601个数据至第1631个数据，即x2(1600)～x2(1630)，也就是31个第二数据，得到的结果如下：
[0105]x2(1600)＝x2(1)^x2(12)^x2(16)^x2(19)^x2(2)^x2(20)^x2(23)^x2(3)^x2(8)[0106]x2(1601)＝x2(13)^x2(17)^x2(2)^x2(20)^x2(21)^x2(24)^x2(3)^x2(4)^x2(9)[0107]x2(1602)＝x2(10)^x2(14)^x2(18)^x2(21)^x2(22)^x2(25)^x2(3)^x2(4)^x2(5)[0108]……
[0109]x2(1615)＝x2(0)^x2(1)^x2(10)^x2(16)^x2(17)^x2(18)^x2(2)^x2(23)^x2(27)^x2(8)^x2(9)……
[0110]x2(1630)＝x2(0)^x2(10)^x2(11)^x2(12)^x2(13)^x2(14)^x2(15)^x2(16)^x2(17)^x2(2)^
[0111]x2(23)^x2(24)^x2(25)^x2(3)^x2(5)^x2(7)^x2(8)^x2(9)[0112]利用初始数据计算出x1(1600)与x2(1600)之后，就可以在不用等待NC＝1600个时钟周期的情况下，仅经过一个时钟周期即可输出伪随机序列中的第一个数据c(0)，c(0)＝x1(1600)^x2(1600)。
[0113]分别将x1(1600)～x1(1630)与x2(1600)～x2(1630)作为第一移位寄存器和第二移位寄存器的初始数据，每个时钟周期得到伪随机序列的一个数据，最终生成整个伪随机序列C。输出待生成的伪随机序列中的第一个数据c(0)的流程如图5所示。[0114]下面说明本发明运算的复杂度相对于现有方案的优势。在现有的方案中，计算x1与x2中的每一个数据时是通过递归方式实现，例如计算x1(1000)时，需要递归地求解x1(1000-28)与x1(1000-31)，并将这两个数据作为递归实例存储在内存中，而计算x1(1000-28)的时候，又需要计算x1(1000-28×2)与x1(1000-28-31)，并将这两个数据作为递归实例存储在内存中，以此类推，直至x1(1000)能通过x1中的第一初始数据表示出来为止。计算x1(n)时需要存储的递归实例的个数随着递归深度(递归次数)的增加而呈2的指数幂增长，其中幂指数为
同样地，计算x2(1000)需要同时计算x2(1000-31)、x2(1000-30)、x2
(1000-29)与x2(1000-28)，而计算这四个数据中的每一个数据时都需要再递归地计算前四个数据，因此计算x2(1000)需要存储的递归实例的个数随着递归深度(递归次数)的增加而呈2的指数幂增长。
11
CN 109375897 A[0115]
说 明 书
9/10页
如图6所示，为现有技术中计算第一子序列中任一个数据时的递归实例个数和递
归深度之间的关系，横坐标为递归深度h，纵坐标为递归实例个数W1，则复杂度
即递归实例曲线与横坐标轴之间包围部分(如图6中斜线
部分)的面积。从公式和图6中可以看出，计算任一个数据的复杂度随递归深度呈2的指数幂增长。
[0116]如图7所示，为现有技术中计算第二子序列中任一个数据时的递归实例个数和递归深度之间的关系，横坐标为递归深度h，纵坐标为递归实例个数W2，则复杂度
即递归实例曲线与横坐标轴之间包围部分(如图7中斜
线部分)的面积。从公式和图7中可以看出，计算任一个数据的复杂度随递归深度呈4的指数幂增长。这种复杂度呈指数式的增长在算法实现中是不能容忍的。[0117]而使用本发明的方法，利用第一递推公式得到的任一数据或利用第二递推公式得到的任一数据，每两次递归之间的间隔增大，这样使得递归深度呈指数迅速下降，复杂度大约呈线性O(h)。如图8所示，横坐标为递归深度h，纵坐标为递归实例个数W，复杂度为几个矩形的面积和。例如计算x1(1000)时的复杂度可表示为递归实例的个数，即需要存储的数据个数为10，同理计算x2(200)时的复杂度为28。[0118]表1现有方案与本发明计算复杂度对比
[0119]
现有方案本发明方案复杂度O(2h)或O(4h)O(h)x1(1000)23210x2(200)4628
[0120]本发明的另一实施例中提供了一种伪随机序列的生成设备，包括：至少一个处理器；以及与所述处理器通信连接的至少一个存储器，其中：所述存储器存储有可被所述处理器执行的程序指令，所述处理器调用所述程序指令以执行上述实施例提供的生成方法，例如可执行以下伪随机序列的生成方法：S1，分别获取N个第一初始数据和N个第二初始数据；N为大于3的整数；S2，根据所述N个第一初始数据，基于第一递推公式，计算N个第一数据，并将所述N个第一数据作为第一移位寄存器的初始数据；S3，根据所述N个第二初始数据，基于第二递推公式，计算N个第二数据，并将所述N个第二数据作为第二移位寄存器的初始数据；S4，根据所述第一移位寄存器的初始数据和所述第二移位寄存器的初始数据，生成所述伪随机序列。
[0121]这里的处理器可以为微处理器(Micro-Controller Unit，MCU)和/或现场可编程门阵列(Field-Programmable Gate Array，FPGA)。还可以是其他调用所述程序指令以执行上述实施例提供的生成方法的处理器。本实施例在此不作具体限定。[0122]本发明的另一实施例中，提供了一种计算机程序产品，所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，使所述计算机执行上述实施例提供的生成方法。例如，计算机执行的伪随机序列的生成方法为：S1，分别获取N个第一初始数据和N个第二初始数据；N为
12
CN 109375897 A
说 明 书
10/10页
大于3的整数；S2，根据所述N个第一初始数据，基于第一递推公式，计算N个第一数据，并将所述N个第一数据作为第一移位寄存器的初始数据；S3，根据所述N个第二初始数据，基于第二递推公式，计算N个第二数据，并将所述N个第二数据作为第二移位寄存器的初始数据；S4，根据所述第一移位寄存器的初始数据和所述第二移位寄存器的初始数据，生成所述伪随机序列。
[0123]本发明的另一实施例中，提供了一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行上述实施例提供的伪随机序列的生成方法。伪随机序列的生成方法可以为：S1，分别获取N个第一初始数据和N个第二初始数据；N为大于3的整数；S2，根据所述N个第一初始数据，基于第一递推公式，计算N个第一数据，并将所述N个第一数据作为第一移位寄存器的初始数据；S3，根据所述N个第二初始数据，基于第二递推公式，计算N个第二数据，并将所述N个第二数据作为第二移位寄存器的初始数据；S4，根据所述第一移位寄存器的初始数据和所述第二移位寄存器的初始数据，生成所述伪随机序列。[0124]综上，本发明实施例提供了一种伪随机序列的生成方法，根据N个第一初始数据和N个第二初始数据，分别计算N个第一数据和N个第二数据，并分别作为第一移位寄存器的初始数据和第二移位寄存器的初始数据。根据第一移位寄存器和第二移位寄存器的初始数据可通过一个时钟周期生成伪随机序列中的第一个数据，并且每一个时钟周期产生伪随机序列中的一个数据，最终生成伪随机序列。生成伪随机序列中的第一个数据只需一个时钟周期。避免了通过第一移位寄存器和第二移位寄存器，直接根据N个第一初始数据和N个第二初始数据，经过指定数量的时钟周期后才能得到伪随机序列的第一个数据。生成伪随机序列的第一个数据的过程中，不需要进行迭代，只需通过一个时钟周期即可完成，大大提高了生成伪随机序列的速度，缩短了生成时间。同时，通过第一递归公式和第二递归公式可增加每两次递归之间的间隔，即减小递归次数，从而使递归深度成指数下降，进而使计算复杂度接近于线性，进一步提高了生成伪随机序列的速度，缩短了生成时间。[0125]最后，本发明的方法仅为较佳的实施方案，并非用于限定本发明的保护范围。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。
13
CN 109375897 A
说 明 书 附 图
1/3页
图1
图2
图3
14
CN 109375897 A
说 明 书 附 图
2/3页
图4
图5
图6
15
CN 109375897 A
说 明 书 附 图
3/3页
图7
图8
16
因篇幅问题不能全部显示，请点此查看更多更全内容