M系列はなぜ自己相関が高いのか

M系列(Maximum Length Sequence)はLFSRの最上位ビット(MSB)で生成される一種の疑似乱数である。

例）g[3:0]=1011のとき

M系列は次の性質をもっている。(2)(3)が乱数的な特徴で、(1)が本物でなく疑似たるゆえんである。

(1) 周期は2ⁿ-1

(2) 周期内の0と1の個数はほぼ同じ(1の方が1個多いだけ)

(3) 自己相関が高い：

1周期分の系列{a[j]}とそれをkだけ巡回シフトした系列{a[j+k]}をビット毎に比較したとき、自己相関R(k)＝(値が同じビット数－値が異なるビット数)は

このうち(1)(2)は、LFSRはゼロを除くnビット値すべてをつくすことからわかる。

◇

(3)の自己相関が高いことは次の性質(4)と上記(2)からわかる。すなわち、{a[j]} と{a[j+k]}とで値が同じ/異なるビット数はa[j] XOR a[j+k]=0/1のビット数であり、a[j] XOR a[j+k]は(4)から第三のM系列になっていて、(2)から1の方が1個だけ多い。

(4) {a[j] XOR a[j+k]}は第三のM系列{a[i+j+k]}になっている

◇◇

(4)は前項で見たGF(2ⁿ)の言葉を使って説明できる。

LFSRの値は次のようなxのべき乗になっていて、GF(2ⁿ)のゼロを除く全要素をつくしていた。

　{ 1　x　x**2 ... x**(2ⁿ-2) }　(x**(2ⁿ-1)=1)

今、1周期分の系列とそれをkだけシフトしたものを加算(XOR)すると

　{ x**(j) x**(j+1) ... x**(j+2ⁿ-2) } XOR { x**(j+k) x**(j+k+1) ... x**(j+k+2ⁿ-2) }

　= (1+x**(k)) * { x**(j) x**(j+1) ... x**(j+2ⁿ-2) }

となるが、(1+x**(k))もGF(2ⁿ)のゼロを除く全要素のひとつなので、xのべき乗になっている

　1+x**(k) = x**(i)

結局、1周期分の系列にkだけシフトした系列を加算(XOR)したものもxのべき乗の系列になっている

　{ x**(i+j+k) x**(i+j+k+1) ... x**(i+j+k+2ⁿ-2) }

ちなみにx**(2ⁿ-1)=1に注意すると、これは

　{1　x　x**2 ... x**(2ⁿ-2)}

を巡回シフトしたものである。

◇◇◇

補足 - 疑似乱数はいろいろな略語がある

PN Pseudo Noise

PRN Pseudo-Random Noise

PRBS Pseudo-Random Bit Sequence

[←]　[↑]　[→]