Ｍ系列の生成多項式
デジタル通信分野で広く用いられているＭ系列(Maximum length sequence) と呼ばれる n ビットのシフトレジスタと
フィードバックで生成される周期が n^2 - 1 の符号列がある。
回路構成は fig.1 のようになり、フィードバックの形成の仕方で２種類ある。
fig.1 中の (＋) 印は排他的論理和（EX-OR）である。
このシフトレジスタとフィードバックで形成している回路はつまり原始多項式で
の除算器ともいえる。
fig.1 LFSR による構成例
主としてデジタル通信のさまざまなところに使われていて、
フレーム同期信号やスクランブル、周波数拡散用の拡散符号や誤り率測定や測距、
擬似雑音発生などに利用されている。
このように広く使われている訳は、Ｍ系列で生成されるビット列には、
次のような特徴があるからである。
- ０と１の発生確率がほぼ同じ。(０と１の発生個数が１周期で１だけ違う）
- 自己相関のピークが１周期に１度だけある。つまり、周期をＮ、ずれをτ
として τ＝０，Ｎ，２ｎ…の時 ｎ、それ以外のとき−１である。(fig.2)
- nビットのＭ系列の１周期の中の連続する n ビットはユニークである
2番目の特徴は、つまりＮを十分大きく取ればほとんどホワイトノイズと近似してよいということである。
3番目の特徴は、測距や絶対位置エンコーダーなどにも利用されている。
fig.2 自己相関の例(n=7)
fig.3 実際の波形の例(n=9, 7.3728Mbps)
Ch1 : Pseudo-random pattern for systems using 9-1 pattern length
Ch2 : Correlation
Math: FFT (Hamming)
下に筆者の知る範囲でまとめた主な生成多項式を示す。
次数:
2,
3,
4,
5,
6,
7,
8,
9,
10,
11,
12,
13,
14,
15,
16,
17,
18,
19,
20,
21,
22,
23,
24,
25,
26,
27,
28,
29,
30,
31,
32,
33,
35,
41,
47,
49,
52,
55,
57,
58,
61,
63,
65,
89,
127,
255,
521,
607,
756
2: (2,1)
3: (3,1)
4: (4,1)
5: (5,2), (5,4,3,2), (5,4,2,1)
6: (6,1), (6,5,2,1), (6,5,3,2)
7: (7,1), (7,3), (7,3,2,1), (7,4,3,2), (7,6,4,2), (7,6,3,1),(7,6,5,2), (7,6,5,4,2,1), (7,5,4,3,2,1)
8: (8,4,3,2), (8,6,5,3), (8,6,5,2), (8,5,3,1), (8,6,5,1), (8,7,6,1), (8,7,6,5,2,1), (8,6,4,3,2,1)
9: *(9,4), (9,6,4,3), (9,8,5,4), (9,8,4,1), (9,5,3,2), (9,8,6,5),(9,8,7,2), (9,6,5,4,2,1), (9,7,6,4,3,1), (9,8,7,6,5,3)
10: (10,3), (10,8,3,2), (10,4,3,1), (10,8,5,1), (10,8,5,4), (10,9,4,1), (10,8,4,3), (10,5,3,2), (10,5,2,1), (10,9,4,2)
11: *(11,2), (11,8,5,2), (11,7,3,2), (11,5,3,2), (11,10,3,2), (11,10,3,2), (11,6,5,1), (11,5,3,1), (11,9,4,1), (11,8,6,2), (11,9,8,3)
12: (12,6,4,1), (12,9,3,2), (12,11,10,5,2,1), (12,11,6,4,2,1), (12,11,9,7,6,5), (12,11,9,5,3,1), (12,11,9,8,7,4), (12,11,9,7,6,5), (12,9,8,3,2,1), (12,10,9,8,6,2)
13: (13,4,3,1), (13,10,9,7,5,4), (13,11,8,7,4,1), (13,12,8,7,6,5), (13,9,8,7,5,1), (13,12,6,5,4,3), (13,12,11,9,5,3), (13,12,11,5,2,1), (13,12,9,8,4,2), (13,8,7,4,3,2)
14: (14,12,2,1), (14,13,4,2), (14,13,11,9), (14,10,6,1), (14,11,6,1), (14,12,11,1), (14,6,4,2), (14,11,9,6,5,2), (14,13,6,5,3,1), (14,13,12,8,4,1), (14,8,7,6,4,2), (14,10,6,5,4,1), (14,13,12,7,6,3), (14,13,11,10,8,3)
15: *(15,1), (15,13,10,9), (15,13,10,1), (15,14,9,2), (15,9,4,1), (15,12,3,1), (15,10,5,4), (15,10,5,4,3,2), (15,11,7,6,2,1), (15,7,6,3,2,1), (15,10,9,8,5,3), (15,12,5,4,3,2), (15,10,9,7,5,3), (15,13,12,10), (15,13,10,2), (15,12,9,1), (15,14,12,2), (15,13,7,4,1), (15,4), (15,13,7,4)
16: (16,12,3,1), (16,12,9,6), (16,9,4,3), (16,12,7,2), (16,10,7,6), (16,15,7,2), (16,9,5,2), (16,13,9,6), (16,15,4,2), (16,15,9,4)
17: (17,3), (17,3,2,1), (17,7,4,3), (17,16,3,1), (17,12,6,3,2,1), (17,8,7,6,4,3), (17,11,8,6,3,2), (17,9,8,6,4,1), (17,16,14,10,3,2), (17,12,11,8,5,2)
18: (18,7), (18,10,7,5), (18,13,11,9,8,7,6,3), (18,17,16,15,10,9,8,7), (18,15,12,11,9,8,7,6)
19: (19,5,2,1), (19,13,8,5,4,3), (19,12,10,9,7,3), (19,17,15,14,13,12,6,1), (19,17,15,14,13,9,8,4,2,1), (19,16,13,11,10,9,4,1), (19,9,8,7,6,3), (19,16,15,13,12,9,5,4,2,1), (19,18,15,14,11,10,8,5,3,2), (19,18,17,16,12,7,6,5,3,1)
20: *(20,3), (20,9,5,3), (20,19,4,3), (20,11,8,6,3,2), (20,17,14,10,7,4,3,2)
21: (21,2), (21,14,7,2), (21,13,5,2), (21,14,7,6,3,2), (21,8,7,4,3,2), (21,10,6,4,3,2), (21,15,10,9,5,4,3,2), (21,14,12,7,6,4,3,2), (21,20,19,18,5,4,3,2)
22: (22,1), (22,9,5,1), (22,20,18,16,6,4,2,1), (22,19,16,13,10,7,4,1), (22,17,9,7,2,1), (22,17,13,12,8,7,2,1), (22,14,13,12,7,3,2,1)
23: *(23,5), (23,17,11,5), (23,5,4,1), (23,12,5,4), (23,21,7,5), (23,16,13,6,5,3), (23,11,10,7,6,5), (23,15,10,9,7,5,4,3), (23,17,11,9,8,5,4,1), (23,18,16,13,11,8,5,2)
24: (24,7,2), (24,4,3,1), (24,22,20,18,16,14,11,9,8,7,5,4), (24,21,19,18,17,16,15,14,13,10,9,5,4,1)
25: (25,3), (25,3,21), (25,20,5,3), (25,12,4,3), (25,17,10,3,2,1), (25,23,21,19,9,7,5,3), (25,18,12,11,6,5,4), (25,20,16,11,5,3,2,1), (25,12,11,8,7,6,4,3)
26: (26,6,2,1), (26,22,21,16,12,11,10,8,5,4,3,1)
27: (27,5,2,1), (27,18,11,10,9,5,4,3)
28: (28,3), (28,13,11,9,5,3), (28,22,11,10,4,3), (28,24,20,16,12,8,4,3,2,1)
29: (29,2), (29,20,11,2), (29,13,7,2), (29,21,5,2), (29,26,5,2), (29,19,16,6,3,2), (29,18,14,6,3,2)
30: (30,23,2,1), (30,6,4,1), (30,24,20,16,14,13,11,7,2,1)
31: (31,29,21,17), (31,28,19,15), (31,3), (31,3,2,1), (31,13,8,3), (31,30,29,25), (31,28,24,10), (31,20,15,5,4,3), (31,16,8,4,3,2)
32: (32,22,2,1), (32,7,5,3,2,1), (32,28,19,18,16,14,11,10,9,6,5,1)
33: (33,13), (33,22,13,11), (33,26,14,10), (33,6,4,1), (33,22,16,13,11,8)
35: (35,2)
39: (39,4),(39,8),(39,14)
41: (41,3),(41,20)
47: (47,5),(47,14),(47,20)
49: (49,9),(49,12),(49,15),(49,22)
52: (52,19)
55: (55,24)
57: (57,7),(57,22)
58: (58,19)
59: (59,58,38,37)
60: (60,59)
61: (61,5,2,1)
62: (62,61,6,5)
63: (63,1),(63,5),(63,31)
64: (64,63,61,60)
65: (65,18),(65,32)
89: (89,51),(89,6,5,3)
93: (93,91)
94: (94,73)
95: (95,84)
97: (97,91)
98: (98,87)
100: (100,63)
127: (127,1),(127,7),(127,15),(127,30),(127,63)
255: (255,52),(255,56),(255,82)
521: (521,32),(521,48),(521,158)
524: (524,167)
607: (607,105),(607,147),(607,273)
756: (756,19)
●
方式検討やアルゴリズムの実装でお困りではありませんか？
センシングや通信分野での実績が豊富なファインチューンに
お気軽にメールにてご相談下さい ●
REFFERENCES
W. P. Horton, "Shift Counters," Computer Control Corporation.
W. W. Peterson, "Error Correctiong Codes," MIT Press, Wiley, New York.
R. C. White, Jr., "Experiments with Digital Computer Simulation of Pseudo-Random Noise Gerenatiors, " IEEE Trans. Elect. Comp., June 1967.
ITU-T recommendation O.150, O.151, O.152, O.153
© 2000 Takayuki HOSODA.
![[Mail]](/~lyuka/images/mail.gif)
