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

[] [] []


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

 

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

順番

d[3:0]

0

001

1

010

2

100

3

011

4

110

5

111

6

101

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

(1)    周期は2n-1

(2)    周期内の01の個数はほぼ同じ(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(2n)の言葉を使って説明できる。

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

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

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

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

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

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

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

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

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

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

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

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

◇◇◇

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

PN   Pseudo Noise

PRN  Pseudo-Random Noise

PRBS Pseudo-Random Bit Sequence


[] [] []