巡回符号について

質問

「関数G(x)=X^4+X+1の周期が15であることを示せ」という問題があるのですが、周期の求め方が分かりません・・・
どなたか分かる方がいたらお願いします。

回答No.2

info22 · ベストアンサー

「(x^n)-1}/(x^4+x+1) 」が割り切れる最小のnが15になる事を示せばいいですね。
巡回符号(CRC符号)での係数の計算はmod 2での計算になります。
例えば、
-1=1 (mod 2) , 2=0 (mod 2), 4=0 (mod 2), 6=0 (mod 2)
などのように係数0,1以外の係数を「0」または「1」に置き換えて計算します。
n=15
{(x^15)-1}/(x^4+x+1)
=(0*x^2+0*x+0)/(x^4+x+1)+x^11+x^8+x^7+x^5+x^3+x^2+x+1 (mod 2)
=x^11+x^8+x^7+x^5+2*x^4+x^3+x^2+x+1 (mod 2)
で割り切れますね。
n=5～14の全てのnで割り切れない事を示せば、最小の周期がn=15である事を示せた事になります。

おまけにn=14の場合をやってみると
{(x^14)-1}/(x^4+x+1)
=(x^3)/(x^4+x+1)+x^10+x^7+x^6+x^4+x^2+x+1 (mod 2)
割り切れませんね。
n=13
n=12
n=11
...
n=5
をやって割り切れないことを示して下さい。
n=4は
明らかに
(x^4-1)/(x^4+x+1)は割り切れませんね。
頑張って、積み算の計算をして下さい。
計算法は参考URLを参考にして下さい。

係数だけでの計算法
http://www.ep.u-tokai.ac.jp/~kikn/MM2003/MM15-CRC.pdf
http://www2.ci.sys.fit.ac.jp/mdcom/control.html

多項式での計算法

参考URL：

http://laputa.cs.shinshu-u.ac.jp/~yizawa/logic2/chap9/index.html

お礼

返答ありがとうございました。
この説明でとてもよくわかりました！！

回答No.1

mister_moonlight

関数：f（x）がある時、任意の実数xに対して常に：f（x）＝f（x＋p）が成立する時、pをf（x）の（基本）周期という。

しかし、それをこの関数に当てはめると、実数pは存在しない。

問題（関数）が違ってないか？