偽亂數二進位數列

偽亂數二進位數列（英语：pseudorandom binary sequence，简称：PRBS），是一種特別的二進位數列${\displaystyle a_{0},\ldots ,a_{N-1}}$，若二進位數列的位元數為N，其中為1的數字有m'個，則其其自相关函数：

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

只有以下二個值：

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

其中

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

稱為偽亂數二進位數列的占空比，類似連續時間信號的占空比。

偽亂數二進位數列稱為偽亂數，雖然它是決定性的，不過其${\displaystyle a_{j}}$的數值和前後元素的數值無關，看似隨機的，因此稱為偽亂數。

偽亂數二進位數列可以延伸到無限長，方式是在${\displaystyle N}$個元素都出現過之後，再從${\displaystyle a_{0},\ldots ,a_{N-1}}$再出現一次……，這點和真正的由放射性衰減或白雜訊產生的數列不同，後者在本質上就是無限長的。偽亂數二進位數列比最大長度數列更普遍，後者是特別的N位元偽亂數二進位數列，是由線性移位暫存器所產生的。最大長度數列的占空比恆為50%，長度為k位元的暫存器，其數列長度為${\displaystyle N=2^{k}-1}$。偽亂數二進位數列可以用在電信、密碼學及模擬等應用。

實際的實現

 

PRBS-15的示意圖，${\displaystyle x^{15}+x^{14}+1}$ 中的${\displaystyle x^{15}}$ 和${\displaystyle x^{14}}$ 表示將第15和14個位元進行XOR後，做為新的位元

偽亂數二進位數列可以用线性反馈移位寄存器產生^[1]。

一些常見的的數列產生多項式為

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

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

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

PRBS31 = ${\displaystyle 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位元。

相關條目

• 偽亂數產生器（英语：Pseudorandom number generator）
• 金氏碼（英语：Gold code）
• 互补序列（英语：Complementary sequences）
• 比特误码率
• 偽亂數噪音（英语：Pseudorandom noise）

參考資料

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

外部連結