擬似乱数バイナリシーケンス

擬似乱数バイナリシーケンス（PRBS）、擬似乱数バイナリコード、または擬似乱数ビットストリームは、決定論的アルゴリズムで生成されるものの予測が困難で^{[ 1 ]}、真の乱数シーケンスと同様の統計的挙動を示すバイナリシーケンスです。PRBSジェネレータは、アナログから情報への変換^{[ 2 ]}などの電気通信だけでなく、暗号化、シミュレーション、相関技術、飛行時間分光法にも使用されています。最も一般的な例は、（最大）線形フィードバックシフトレジスタ（LFSR）によって生成される最大長シーケンスです。その他の例としては、ゴールドシーケンス（ CDMAおよびGPSで使用）、カサミシーケンス、JPLシーケンスなどがあり、これらはすべてLFSRに基づいています。

電気通信において、擬似ランダムバイナリシーケンスは、擬似ランダムノイズとして使用されることから、擬似ランダムノイズコード（PNコードまたはPRNコード）として知られています。

バイナリシーケンス（BS）はシーケンスです${\displaystyle a_{0},\ldots ,a_{N-1}}$の${\displaystyle N}$ビット、つまり

${\displaystyle a_{j}\in \{0,1\}}$のために${\displaystyle j=0,1,...,N-1}$。

BSは以下から構成されます。${\displaystyle m=\sum a_{j}}$1つと${\displaystyle Nm}$ゼロ。

BS は、自己相関関数が次の条件を満たす場合、擬似ランダムバイナリシーケンス(PRBS)である。 ^{[ 3 ]}

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

値は2つしかありません。

${\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}}}$

これは、連続時間信号のデューティサイクルと同様に、PRBSのデューティサイクルと呼ばれます。最大長シーケンスの場合、${\displaystyle N=2^{k}-1}$デューティサイクルは1/2です。

PRBSは「擬似乱数」です。なぜなら、実際には決定論的であるにもかかわらず、ある意味でランダムに見えるからです。${\displaystyle a_{j}}$この要素は、実際の乱数列と同様に、他のどの要素の値にも依存しない。

PRBSは、それを繰り返すことで無限に伸ばすことができます。${\displaystyle N}$要素は存在するが、周期的になり、したがってランダムではなくなる。対照的に、放射性崩壊やホワイトノイズによって生成されるシーケンスなどの真のランダムシーケンスソースは無限である（あらかじめ定められた終了や周期はない）。しかし、この予測可能性の結果として、PRBS信号は再現可能なパターンとして使用できる（たとえば、電気通信信号経路のテストに使用される信号）。^{[ 4 ]}

擬似乱数バイナリシーケンスは、線形フィードバックシフトレジスタを使用して生成できます。^{[ 5 ]}

一般的な^{[ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ]}数列生成単項式は

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

PRBS9 =${\displaystyle x^{9}+x^{5}+1}$

PRBS11 =${\displaystyle x^{11}+x^{9}+1}$

PRBS13 =${\displaystyle x^{13}+x^{12}+x^{2}+x+1}$

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

PRBS20 =${\displaystyle x^{20}+x^{3}+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の値です。

PRBS kまたは PRBS- k表記 (例えば「PRBS7」または「PRBS-7」) は、シーケンスのサイズを示します。 ${\displaystyle N=2^{k}-1}$はシーケンスに含まれるビットの最大数です^{[ 4 ] : §3。k}はシーケンス内の一意のデータワードのサイズを示します。Nビットのデータを長さkのすべての可能なワードに分割すると、すべて0のワードを除いて、kビットのバイナリワードの0と1のすべての可能な組み合わせをリストできます^{[ 4 ] : §2。}たとえば、PRBS3 = "1011100"は以下から生成できます。${\displaystyle x^{3}+x^{2}+1}$[ ^{6 ] PRBS3 シーケンス内の 3 ビットワードの連続するグループをすべて取り出すと (最後の数個の} 3 ビットワードについては最初に戻る)、次の 7 つのワード配置が見つかります。

 「101 1100」→ 101 「1 011 100」→ 011 「10 111 00」→ 111 「101 110 0」→ 110 「1011 100」→ 100 " 1 0111 00 " → 001 (折り返しが必要) " 10 1110 0 " → 010 (折り返しが必要)

その7つの単語はすべて${\displaystyle 2^{k}-1=2^{3}-1=7}$ゼロ以外の3ビットバイナリワードは、数値順ではない可能性がある。これはPRBS3だけでなく、任意のPRBSkについても同様である。^{[ 4 ]： §2}

• 擬似乱数発生器
• ゴールドコード
• 相補配列
• ビットエラー率テスト
• 擬似ランダムノイズ
• 線形フィードバックシフトレジスタ

• OEISシーケンスA011686 （バイナリmシーケンス：逆数の展開） -- PRBS7のビットシーケンス =${\displaystyle x^{7}+x^{6}+1}$