伪乱数二进制数列

伪乱数二进制数列（英语：pseudorandom binary sequence，简称：PRBS），是一种特别的二进制数列 $a_{0},\ldots ,a_{N-1}$ ，若二进制数列的位元数为N，其中为1的数字有m个，则其其自相关函数：

C(v)=\sum _{j=0}^{N-1}a_{j}a_{j+v}

只有以下二个值：

C(v)={\begin{cases}m,{\mbox{ if }}v\equiv 0\;\;({\mbox{mod}}N)\\\\mc,{\mbox{ otherwise }}\end{cases}}

其中

c={\frac {m-1}{N-1}}

称为伪乱数二进制数列的占空比，类似连续时间信号的占空比。

伪乱数二进制数列称为伪乱数，虽然它是决定性的，不过其 $a_{j}$ 的数值和前后元素的数值无关，看似随机的，因此称为伪乱数。

伪乱数二进制数列可以延伸到无限长，方式是在 $N$ 个元素都出现过之后，再从 $a_{0},\ldots ,a_{N-1}$ 再出现一次……，这点和真正的由放射性衰减或白噪声产生的数列不同，后者在本质上就是无限长的。伪乱数二进制数列比最大长度数列更普遍，后者是特别的N位元伪乱数二进制数列，是由线性移位暂存器所产生的。最大长度数列的占空比恒为50%，长度为k位元的暂存器，其数列长度为 $N=2^{k}-1$ 。伪乱数二进制数列可以用在电信、密码学及模拟等应用。

实际的实现

PRBS-15的示意图，

x^{15}+x^{14}+1

中的

x^{15}

和

x^{14}

表示将第15和14个位元进行XOR后，做为新的位元

伪乱数二进制数列可以用线性反馈移位寄存器产生^[1]。

一些常见的的数列产生多项式为

PRBS7 = $x^{7}+x^{6}+1$

PRBS15 = $x^{15}+x^{14}+1$

PRBS23 = $x^{23}+x^{18}+1$

PRBS31 = $x^{31}+x^{28}+1$

以下是一个用 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.

外部链接

https://web.archive.org/web/20131111050840/http://www.scriptwell.net/correlation.htm

[1] Paul H. Bardell, William H. McAnney, and Jacob Savir, "Built-In Test for VLSI: Pseudorandom Techniques", John Wiley & Sons, New York, 1987.

[1]

伪乱数二进制数列

目录

实际的实现

相关条目

参考资料

外部链接