基于DSP的任意长度伪随机序列产生方法

在实际应用中, 直接利用DSP产生任意长度伪随机序列的方法, 可以为系统设计和测试带来便利。文中基于线性同余算法, 结合Analo Gdevices公司DSP芯片TigerSHARC20XS的运算结构, 设计出一种利用寻址递减长度序列, 从而产生具有遍历性的任意长度伪随机序列的方法。通过对比, 说明此方法成功解决了传统方法中, 利用DSP的反馈位移寄存器只能产生2n (1≤n≤32)长度伪随机序列的问题, 在生成序列的任意长度方面具有一定创新性, 对通信传输和雷达变频抗干扰具有一定的参考价值。

关键词　线性同余算法; 伪随机数; 任意长度序列; DSP

Genera tion Method about Pseudo Random Sequence of Optiona l Cycle Ba sed on DSP

Abstract　In many p rojects, it is a great advantage for designing and debugging systems to generate the p seudo random sequence by DSP. Based on the analysis of the linear congruential generator and TigerSHARC20XS of ANALOGDEV ICES, this paper p resents a method for generating the p seudo random sequence in op tional cycle by ad2 dressing the sequence of descending length. Compared with traditionalmethods, the new method, which is innova2 tive in op tional cycle, solves the p roblem that the p seudo random sequence can only be in a fixed cycle of 2n ( 1≤n≤32) using DSP in traditional methods and is of value in the transmission of communication and anti2jamming of the frequency hopp ing radar.
Keywords　LCG; p seudo random number; op tional cycle sequence; DSP

　随机数是虽然具有一定的统计学规律, 但抽样值不能事先确定的数。实际中产生的随机数不是绝对随机数, 而是相对的, 称为“伪随机数” 。伪随机数既有随机数所具有的优良相关性, 又有随机数所不具备的规律性。这两个特点, 使得以伪随机数为基础的伪随机信号既易于从干扰信号中被识别和分离出来,又可以方便的产生和重复。因此伪随机序列在通讯、雷达、导航、测量、密码、计算机、相关辨识及故障诊断等许多领域中都有着广泛的应用。

在许多文献中, 涉及的伪随机序列产生方法多是基于高级语言的, 较少涉及硬件具体实现问题。已有的一些硬件实现方法, 在FPGA芯片和DSP芯片上都有过应用 。其中在用DSP芯片实现时, 如果要求产生任意长度M (M > 0)的一个伪随机序列并保证在无重复数的前提下该序列包含0～M - 1的每一个数,传统做法无法完成; 只有将生成的序列长度M 限制为2n (1≤n ≤32)时, 才能满足要求。文中介绍的基于DSP的伪随机序列产生方法解决了这样的问题, 可以产生任意长度的伪随机序列, 对工程应用有一定的现实意义。

1　线性同余算法的基本原理

线性同余算法[ 6 ]的核心公式是Xn + 1 = ( aXn + b) modM, n = 0, 1, ⋯, M - 1。其中, a ( 0≤a≤M )是 乘数, b ( 0 ≤ b ≤M ) 是加数, M (M > 0 ) 是模数, X0 (0≤X0 ≤M )是初值即种子。模数M 也等于生成的 伪随机序列的长度, 所有参数均为整数。 线性同余算法产生的伪随机序列在不更换种子的 前提下以M (M = 2n )为周期出现循环, 如果M 不等于 2n, 序列将以<m ="x0 = 7时, 生成序列为{ 6, 9, 0, 7, 6, 9, ...} , 周期为4; 当M = 8, a =5, b = 1, X0 = 1 时, 生成序列为{ 6, 7, 4, 5, 2,3, 0, 1, 6, 7, ...} , 周期为8; 当M = 16, a = 5,b = 3, X0 = 7 时, 生成序列为{ 6, 18, 11, 10, 5,12, 15, 14, 9, 0, 3, 2, 13, 4, 7, 6, 1, ...} ,周期为16。

由上面的例子可以看出, 直接运用线性同余算法用硬件产生伪随机序列在实际工程应用中并不灵活。比如在雷达信号处理中, 为了减小外界对雷达信号接收的干扰, 会要求发射机和接收机以一定的时间间隔随机地在一定数目的频点上跳频, 在跳频过程中不跳完所有规定的频点不允许重复。如果一个频点用一个伪随机数来对应, 这就可以等价为一个伪随机序列问题。显然, 不能因为传统方法生成的伪随机序列长度必须为2n ( 1≤n ≤32) , 而要求发射机和接收机的跳频点个数也设计为2n (1≤n≤32) 。

2　任意长度伪随机序列产生方法及DSP实现

由上面的举例可以看出, 在序列长度M ≠2n 的时候, 生成序列中的数都<M 并且会以<M 的周期出现循环。如果就用这个序列作为输出肯定是不符合要求的, 因为在0～M - 1之间有很多数都没有在结果中出现, 换种说法就是输出的序列没有对0～M - 1这M 个数进行遍历。但是换种思路, 如果把这个序列不直接用作输出, 而当作一个偏移地址, 就有可能间接地以访问某个地址的方式输出一串符合伪随机序列要求的数。这就是文中介绍的生成任意长度伪随序列方法的核心。

下面结合DSP的硬件实现具体阐述各个步骤。首先, 用DSP程序生成一组特定长度为M 的数然后放入内存中, 这里的M 可以等于2n 也可以是任意值。也可以事先在外部文件中写好需要输出的一组数然后导入DSP的内存中。根据不同的应用场合,放入内存的这组数可以是0～M - 1, 也可以是没有任何规律排列的任意M 个数。

其次, 根据要求给种子、乘数、加数和模数赋值, 调用求余子程序根据线性同余算法公式进行运算, 得到一个余数。用得到的余数作为偏移地址, 加上已放入内存中序列的首地址也就是基地值, 就得到了一个访问地址。因为刚才的求余操作是对M 进行,得到的余数即偏移地址一定<M, 所以按照得到的访问地址进行寻址, 得到的数一定是内存中长度为M的已存序列中的某个数, 将这个数输出。

再次, 把上一步已输出数后面的每个数都向前存放一个地址, 这样内存中的序列首地址不变, 序列长度减1。把模数M 也减1, 以对应新的序列长度。再调用求余子程序, 根据线性同余算法公式进行运算,得到又一个余数。然后同样会得到一个新访问地址,同样能输出内存中长度为M - 1的序列中的某个数,将其输出。

随后, 把上一步已输出数后面的每个数再都向前存放一个地址, 这样内存中的序列首地址还不变, 序列长度再减1, 把模数M 也再减1。按照刚才阐述的操作步骤重复进行, 直至模数被减为1, 就会输出一个符合要求的长度为的伪随机序列。此时的序列就是任意长度的伪随机序列。

最后, 如果内存中的数都被输出完, 重新导入长度为M 的序列, 并更换种子 , 乘数和加数可以更换也可以不更换。然后进入新一轮的伪随机数生成,新生成序列中的M 个数和已生成序列中的M 个数相比较顺序已经被完全打乱。这样一直重复操作下去,每输出M 个数更换一次种子, 就可以生成含有M 个元素的长度为n ×M ( n为正整数)的伪随机序列。

操作流程, 如图1所示。

当M = 8, a = b = X0 = 7时, 生成序列为{ 1, 2,5, 4, 3, 8, 6, 7, 12, ...} , 周期为8; 当M = 10,a = b = X0 = 7 时, 生成序列为( 7, 3, 1, 2, 6, 5,4, 10, 8, 9, 7, 3, ...) , 周期为10; 当M = 11,a = 5, b = 3, X0 = 4 时, 生成序列为{ 2, 5, 8, 11,4, 10, 7, 9, 6, 3, 1, 2, 5, ...} , 周期为11; 当M = 12, a = 5, b = 3, X0 = 4时, 生成序列为{ 12, 2,5, 8, 11, 4, 10, 7, 9, 6, 3, 1, 12, 2, ...} , 周期为12。

由仿真结果可以看出, 文中介绍的方法能灵活产生任意长度的伪随机序列。

3　结束语
伪随机序列有着广泛的应用前景, 在通信传输和雷达抗干扰方面尤为重要, 序列长度是影响其应用的关键因素。文中讨论了伪随机序列长度和遍历性的矛盾, 提出了基于DSP芯片具有遍历性的任意长度伪随机序列的工程实现方法。给出了对该实现方法具体步骤的分析, DSP程序的仿真结果显示了该实现方法的正确性和有效性。在应用中可方便地修改程序中各参数, 以满足各种场合不同的需求。