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)

すなわLSFRxのべき乗の計算になっており、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を引くよりもxg(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)は、やや長くなるので次項で説明する。


[] [] []