M系列にはオールゼロ以外のすべてのnビット列が1回ずつ登場する
M系列には前項の(1)-(4)の他に次の性質(5)がある。
|
(5) オールゼロ以外のすべてのnビット列が1回ずつ登場する |
例) g[3:0]=1011のとき
|
順番 |
d[3:0] |
|
0 |
001 |
|
1 |
010 |
|
2 |
100 |
|
3 |
011 |
|
4 |
110 |
|
5 |
111 |
|
6 |
101 |
M系列は周期23-1で0010111の繰り返しとなるが、このM系列の先頭からスライドしながら3ビットずつ抜き出すと000以外の全ての3ビット列が1回ずつ登場する。
|
0010111 |
|
001 |
|
010 |
|
101 |
|
011 |
|
111 |
|
110 |
|
100 |
この性質を使えば、M系列の中でnビットだけ抜き出してチェックしていれば全長2n-1ビット中の位置が検出できることになる。
◇
性質(5)は、ガロアLFSRの代わりにフィボナッチLFSRで考えるとすぐわかる。(→直接形と転置形)
どちらのLFSRも初期値d[N-1:0]=0...01から始めると同じM系列が得られるが、フィボナッチLFSRのd[N-1:0]は単なるシフトレジスタなので、ちょうどM系列からNビットずつ抜き出した値になっている。
|
順番 |
ガロア |
ﾌｨﾎﾞﾅｯﾁ |
|
0 |
001 |
001 |
|
1 |
010 |
010 |
|
2 |
100 |
101 |
|
3 |
011 |
011 |
|
4 |
110 |
111 |
|
5 |
111 |
110 |
|
6 |
101 |
100 |
LFSRの値はオールゼロ以外の全てのnビット列をつくすから、上記の性質(5)が言える。
◇◇
逆に、オールゼロ以外の全てのnビット列が1回ずつしか登場しないような系列はM系列の他にも作ることができる。(→補足 - 繰り返しのない列)
(例1) 3ビット列が1回ずつ登場する系列は2個あって((1')は(1)の逆方向になっている)
(1)0010111 ←g[3:0]=1011のM系列と同じ
(1')0011101 ←g[3:0]=1101のM系列と同じ
これらは2個ともM系列と同じになっている。
(例2) 4ビット列が1回ずつ登場する系列は16個あって((1')等は(1)等の逆方向になっている)
(1)000100110101111 ←g[4:0]=10011のM系列と同じ
(2)000100111101011
(3)000101001101111
(4)000101001111011
(5)000101100111101
(6)000101101001111
(7)000101111001101
(8)000101111010011
(1')000111101011001 ←g[4:0]=11001のM系列と同じ
(2')000110101111001
(3')000111101100101
(4')000110111100101
(5')000101111001101
(6')000111100101101
(7')000101100111101
(8')000110010111101
このうち2個だけがM系列と同じになっている。
ただし、M系列と違って、M系列以外のこれらの系列はいずれも自己相関が高くない。
例えば
(1)000100110101111の自己相関は
R(0)=15
R(その他)=-1
であるのに対して
(2)000100111101011の自己相関は
R(0)=15
R(5)=R(10)=3
R(6)=R(9)=-5
R(その他)=-1