伪乱数二进制数列
伪乱数二进制数列（英语：pseudorandom binary sequence，简称：PRBS），是一种特别的二进制数列<math>a_0,\ldots, a_{N-1}</math>，若二进制数列的位元数为N，其中为1的数字有m个，则其其自相关函数：
- <math>C(v)=\sum_{j=0}^{N-1} a_ja_{j+v}</math>
只有以下二个值：
- <math>C(v)=
\begin{cases} m, \mbox{ if } v\equiv 0\;\; (\mbox{mod}N)\\ \\ mc, \mbox{ otherwise } \end{cases}</math>
其中
- <math>c=\frac{m-1}{N-1}</math>
称为伪乱数二进制数列的占空比，类似连续时间信号的占空比。
伪乱数二进制数列称为伪乱数，虽然它是决定性的，不过其<math>a_j</math>的数值和前后元素的数值无关，看似随机的，因此称为伪乱数。
伪乱数二进制数列可以延伸到无限长，方式是在<math>N</math>个元素都出现过之后，再从<math>a_0,\ldots, a_{N-1}</math>再出现一次……，这点和真正的由放射性衰减或白噪声产生的数列不同，后者在本质上就是无限长的。伪乱数二进制数列比最大长度数列更普遍，后者是特别的N位元伪乱数二进制数列，是由线性移位暂存器所产生的。最大长度数列的占空比恒为50%，长度为k位元的暂存器，其数列长度为<math>N = 2^k-1</math>。伪乱数二进制数列可以用在电信、密码学及模拟等应用。
实际的实现[编辑]
一些常见的的数列产生多项式为
PRBS7 = <math>x^{7} + x^{6} + 1</math>
PRBS15 = <math>x^{15} + x^{14} + 1</math>
PRBS23 = <math>x^{23} + x^{18} + 1</math>
PRBS31 = <math>x^{31} + x^{28} + 1</math>
以下是一个用 PRBS-7 产生伪乱数二进制数列的C语言程式
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
int main(int argc, char* argv[]) {
uint8_t start = 0x02;
uint8_t a = start;
int i;
for(i = 1;; i++) {
int newbit = (((a >> 6) ^ (a >> 5)) & 1);
a = ((a << 1) | newbit) & 0x7f;
printf("%x\n", a);
if (a == start) {
printf("repetition period is %d\n", i);
break;
}
}
}
此例中，PRBS-7的周期为127位元。
相关条目[编辑]
参考资料[编辑]
- ^ Paul H. Bardell, William H. McAnney, and Jacob Savir, "Built-In Test for VLSI: Pseudorandom Techniques", John Wiley & Sons, New York, 1987.