偽亂數二進位數列
維基百科,自由的 encyclopedia
偽亂數二進位數列(英語:pseudorandom binary sequence,簡稱:PRBS),是一種特別的二進位數列,若二進位數列的位元數為N,其中為1的數字有m個,則其其自相關函數:
只有以下二個值:
其中
稱為偽亂數二進位數列的占空比,類似連續時間信號的占空比。
偽亂數二進位數列稱為偽亂數,雖然它是決定性的,不過其的數值和前後元素的數值無關,看似隨機的,因此稱為偽亂數。
偽亂數二進位數列可以延伸到無限長,方式是在個元素都出現過之後,再從
再出現一次……,這點和真正的由放射性衰減或白雜訊產生的數列不同,後者在本質上就是無限長的。偽亂數二進位數列比最大長度數列更普遍,後者是特別的N位元偽亂數二進位數列,是由線性移位暫存器所產生的。最大長度數列的占空比恆為50%,長度為k位元的暫存器,其數列長度為
。偽亂數二進位數列可以用在電信、密碼學及模擬等應用。
實際的實現
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2b/PRBS_15_generator.png/640px-PRBS_15_generator.png)
一些常見的的數列產生多項式為
PRBS7 =
PRBS15 =
PRBS23 =
PRBS31 =
以下是一個用 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)
參考資料
- Paul H. Bardell, William H. McAnney, and Jacob Savir, "Built-In Test for VLSI: Pseudorandom Techniques", John Wiley & Sons, New York, 1987.