LFSRはどこにXORをつけると周期2n-1になるのか
Linear Feedback Shift Register (LFSR)はシフトレジスタにXORをつけた一種のカウンタである。(ちなみに直接形と転置形がある)
カウンタ値がオールゼロだとずっとオールゼロにとどまるので、使える値はオールゼロ以外の2n-1個である。
実はXORをつける位置をうまく選ぶとカウンタ周期を最大の2n-1にできるのだが、どこにXORをつければよいのだろうか。
◇
LFSRの回路をVerilogで書くと
|
if(d[n-1]==1) d[n-1:0] = (d[n-2:0]<<1) ^ g[n-1:0] else__________d[n-1:0] = (d[n-2:0]<<1) |
これを前項のGF(2n)の多項式表記で書き直すと、左シフトはxをかけること、
(d[n-1]==1)のときg[n-1:0]を引くのは、xをかけてn次になったらg(x)で割ること(1回引けばよい)だから
|
d(x) = _ ___ __d[n-1]xn-1 + ... + d[1]x + d[0] g(x) = g[n]xn + g[n-1]xn-1 + ... + g[1]x + g[0] とおくと d(x) = x d(x) mod g(x) |
すなわちLSFRはxのべき乗の計算になっており、LSFRの周期を2n-1にするXORの位置を求めることは
xのべき乗 { 1 x x**2 ... x**(2n-2) } mod g(x) がゼロを除く全要素をつくすようなg(x)
を求めることになる。このようなg(x)を原始多項式(primitive polynomial)という。
ちなみにx**(2n-1) は必ず1になる。なぜなら一般にGF(N)のゼロを除く任意の要素bに対してbN-1=1になるから。
∵GF(N)のゼロを除く全要素をa1,a2, ... aN-1とおくと、
これらにゼロを除く任意の要素bをかけたb*a1,b*a2, ... b*aN-1 もゼロを除く全要素になっているから
a1 * a2 * ... * aN-1 = (b*a1)*(b*a2 )* ... *(b*aN-1) = bN-1 *(a1 * a2 * ... * aN-1)
◇◇
答えを先に言うと原始多項式g(x)を簡単に求める方法はないらしく実用的なご利益はないのだが、LFSRを使ったM系列やCRCの性質を理解するのに役に立つので、以下では原始多項式の感覚をつかめるように具体例で説明する。
◇◇◇
既約なg(x)でxのべき乗を手計算してみる。
なお多項式で計算するときはg(x)=x3+x+1を引くよりもxをg(x)=0の根とみてx3=x+1と次数を下げていった方が簡単である。
(1) n=3ビットのとき 既約なg(x)は2つあり2つとも原始多項式になっている。
g(x)=x3+1 g[3:0]=1001=(111)*(11)
g(x)=x3+x+1 g[3:0]=1011は既約で原始多項式
g(x)=x3+x2+1 g[3:0]=1101は既約で原始多項式
g(x)= x3+x2+x+1 g[3:0]=1111=(101)*(11)=(11)*(11)*(11)
|
g(x)=x3+x+1 |
g[3:0]=1011 |
|
g(x)=x3+x2+1 |
g[3:0]=1101 |
|
x0=1 x1=x x2=x2 x3=x+1 x4=x2+x x5=x3+x2=x2+x+1 x6=x3+x2+x=x2+1 x7=x3+x=1 |
(10)0=________001 (10)1=________010 (10)2=________100 (10)3=1000=011 (10)4=________110 (10)5=1100=111 (10)6=1110=101 (10)7=1010=001 |
|
x0=1 x1=x x2=x2 x3=x2+1 x4=x3+x=x2+x+1 x5=x3+x2+x=x+1 x6=x2+x x7= x3+x2=1 |
(10)0=________001 (10)1=________010 (10)2=________100 (10)3=1000=101 (10)4=1010=111 (10)5=1110=011 (10)6=________110 (10)7=1100=001 |
(2) n=4ビットのとき 既約なg(x)は3つあり、このうち2つが原始多項式になっている。
g(x)= x4+1 g[4:0]=10001=(1111)*(11)
g(x)= x4+x+1 g[4:0]=10011は既約で原始多項式
g(x)= x4+x2+1 g[4:0]=10101=(111)*(111)*(111)
g(x)= x4+x2+x+1 g[4:0]=10111=(1101)*(11)
g(x)= x4+x3+1 g[4:0]=11001は既約で原始多項式
g(x)= x4+x3+x+1 g[4:0]=11011=(1001)*(111)
g(x)= x4+x3+x2+1 g[4:0]=11101=(1011)*(11)
g(x)= x4+x3+x2+x+1 g[4:0]=11111は既約だがで原始多項式でない
|
g(x)=x4+x+1 |
g[4:0]=10011 |
|
g(x)=x4+x3+1 |
g[4:0]=11001 |
|
x0_=1 x1_=x x2_=x2 x3_=x3 x4_=x+1 x5_=x2+x x6_=x3+x2 x7_=x4+x3=x3+x+1 x8_=x4+x2+x=x2+1 x9_=x3+x x10=x4+x2=x2+x+1 x11=x3+x2+x x12=x4+x3+x2=x3+x2+x+1 x13=x4+x3+x2+x=x3+x2+1 x14=x4+x3+x=x3+1 x15=x4+x=1 |
(10)0_=_________0001 (10)1_=_________0010 (10)2_=_________0100 (10)3_=_________1000 (10)4_=10000=0011 (10)5_=_________0110 (10)6_=_________1100 (10)7_=11000=1011 (10)8_=10110=0101 (10)9_=_________1010 (10)10=10100=0111 (10)11=_________1110 (10)12=11100=1111 (10)13=11110=1101 (10)14=11010=1001 (10)15=10010=0001 |
|
x0_=1 x1_=x x2_=x2 x3_=x3 x4_=x3+1 x5_=x4+x=x3+x+1 x6_=x4+x2+x=x3+x2+x+1 x7_=x4+x3+x2+x=x2+x+1 x8_=x3+x2+x x9_=x4+x3+x2=x2+1 x10=x3+x x11=x4+x2=x3+x2+1 x12=x4+x3+x=x+1 x13=x2+x x14=x3+x2 x15=x4+x3=1 |
(10)0_=_________0001 (10)1_=_________0010 (10)2_=_________0100 (10)3_=_________1000 (10)4_=10000=1001 (10)5_=10010=1011 (10)6_=10110=1111 (10)7_=11110=0111 (10)8_=_________1110 (10)9_=11100=0101 (10)10=_________1010 (10)11=10100=1101 (10)12=11010=0011 (10)13=_________0110 (10)14=_________1100 (10)15=11000=0001 |
|
g(x)=x4+x3+ x2+ x+1 |
g[4:0]=11111 |
|
x0 =1 x1 =x x2 =x2 x3 =x3 x4 =x3+x2+x+1 x5 = x4+x3+x2+x =1 |
(10)0 =_________0001 (10)1 =_________0010 (10)2 =_________0100 (10)3 =_________1000 (10)4 =10000=1111 (10)5 =11110=0001 |
|
周期が15に満たないので原始多項式ではない |
|
◇◇◇
手計算の例でも確かめられるが、原始多項式には次の性質がある。
|
(1) g[0]=1 (2) g[i]=1の項は奇数個(奇パリティ) (3) g[n:0]が原始多項式ならば左右ひっくり返したg[0:n]も原始多項式になっている (4) n次の原始多項式はφ(2n-1)/n個ある。 ここでφ(N)は1からN-1までの数のうちNと素な数の個数を示す |
なぜならば
(1)は、もしg[0]=0だと(10)で割り切れて既約でないから
(2)は、もしg[n:0]が偶パリティだとg[n:0]を加算してもパリティは不変、また左シフトしてもパリティは不変だから、結局LFSRのパリティは偶か奇のどちらか一方にとどまることになり不都合だから
(3)は、係数を左右ひっくり返すことは、LFSRを逆回しすること、すなわち右シフトしてLSB=1になったらg[n:0]を引く(加算する)のと同じだから
(4)は、やや長くなるので次項で説明する。