LFSRの生成多項式について

お世話になります。
ワード長は16ビットと仮定しています。

Q1)特性多項式"x^16 +x^14+x^13+x^11+1"の現在の状態がACE1（16進）の
ばあい、次の状態の値の計算方法は？

Q２)特性多項式"x^16 +x^６+x^４+x^３+1"の現在の状態がACE1（16進）の
ばあい、次の状態の値の計算方法は？

注）シフトレジスターとそのフィードバックにより状態の遷移は求める事は可能ですが、
　数学的な方法（加減乗除）により求める事はかのうですか？
　つまり、回路図があれば、そのシステムの挙動は把握出来ますが、特性多項式から
　システムの状態をしる事が可能ですか？

以上、素人の質問ですが、宜しくお願いします。

No.2 ベストアンサー 回答者： rabbit_cat 回答日時： 2017/03/18 11:15

誤 x^17-1 ⇒ 正 x^16-1

誤 x^17 ⇒ 正 x^17
の間違いです。

No.1 回答者： rabbit_cat 回答日時： 2017/03/18 11:13

もともと、特性多項式というのは、それを使って計算したり、その数学的な性質を議論するために考え出されたものなわけで、

特性多項式で表されているものをわざわざ回路図に戻して計算するほうが邪道といえば邪道なやり方です。

具体的には、
Q1の例で言えば、
ACE1（16進）を2進数にすれば、1010110011100001ですから、現在の状態を多項式で表すと、
I(x) = 1*x^0 + 0*x^1 + 1*x^2 + … = 1 + x^2 + x^4 + x^5 + x^8 + x^9 + x^10 + x^15 です。
これと、特性多項式 P(x) = x^16 +x^14+x^13+x^11+1 を掛け算して、R(x) = n^16 -1 で割った余りが、次の状態になります。
式で書けば、次の状態 I'(x)として
I'(x) = P(x)*I(x) mod (x^17-1)
です。
ただし、計算は、GF(2) 上で行います。つまり、多項式同士の計算で、係数が2以上になったら、それを２で割った余り（0 or 1）を実際の係数とします。

本来は上記の計算法がLFSRの定義ですが、簡単な式変形により、上記の計算が、
I'(x) = xI(x) + P(x) mod (x^17)
と等しいことを示せます。
つまり、I(x) に x をかけて（１つシフトして）、そこに特性多項式 P(x) を足したもの のうち、x^16以下のものだけを取り出せばよいことになります。
これが、つまり、よく見る回路図を用いた計算方法のことです。

この回答へのお礼

回答有難うございました。
下記の計算を行いまして、0xE270を得ることが出来ました。
I=[1 0 0 0 0 1 1 1 0 0 1 1 0 1 0 1]
P=[1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1]
I1 = conv(I,P)
I2=mod( I1, 2)
%I2=1 0 0 0 0 1 1 1 0 0 1 0 0 0 1 1
%I2=0 0 0 0 1 1 1 0 0 1 0 0 0 1 1 1-->072E
つまり最後に左方向にループシフトしまして、0xE270を
求めることが出来ました。

お礼日時：2017/03/18 19:16