CRCアルゴリズムのZ/2Z上の多項式の係数列とは？

質問

こんにちはお世話になります。
私はネットワークに興味があるオジサンです。
先日、データリンク層のプロトコル群を勉強していたとき、誤り訂正でCRCが出てきました。

CRC（Cyclic Redundancy Cheak）の解説には、
>ビット列をZ/2Z上の多項式の係数列とみなし, もとのデータにチェックビットを
継ぎ足して必ず特定の生成多項式で割り切れるデータのみを送るようにする.
>
とありました。
上記の「Z/2Z上」とは何を指しているのでしょうか。
数学が大の苦手ですので優しく解説していただければ幸いです。

何卒よろしくお願い申し上げます。

回答No.2

punchan_jp · ベストアンサー

～上の多項式というと、～にはガロア体が入りそうですね。符号理
論の教科書を見ると、GF(2)上の多項式という表現がよく使われま
すが、これの別の表現のような気がします。Z/2Z の 2 というのは、
GF(2) と関係あるかもしれません。で、それが当たっているとして…

簡単にいうと、二つの要素からなる集合で、その要素の中だけで加
減乗除が定義できるなら、その集合と演算をセットで、ガロア体
GF(2) といいます。この加減乗除において、0を表す要素と、1を表
す要素が必要ですので、GF(2) は結局0と1の集合です。乗算は普通
の演算と同じに考えればいいですが、加算に関しては 1+1=0 とい
う排他的論理和を用いることになります。

GF(2)上の多項式というのは、係数がGF(2)の要素であるような多項
式です。多項式どうしの加減乗除を考えるときに、項の加減乗除が
必要ですが、それらの係数の演算を GF(2) 上の演算として行うと
いう意味です。

お礼

早速の回答ありがとうございます。

「ガロア体」やはり符号理論の知識が必要なのですね。
どうやら「算数のドつぼ」にはまってしまったようです。

二進数の特殊な世界（排他的理論和？）がなぜ必要なのかという点も、すんなり納得できません。集合ももう一度やり直す必要ありです。
GF(2)に置き換えてくださった解説はなんとなく理解できました。

punchan_jpさんには
"CRTのアルゴリズム"
http://oshiete1.goo.ne.jp/kotaeru.php3?qid=33895
でもお世話になっており、重ねて御礼を申し上げます。
これからもよろしくお願い申し上げます。
ありがとうございました。

回答No.4

motsuan

すいません、訂正です。
ブール代数って１＋１＝１でしたっけ？
Ｚ／２Ｚは演算は
０＋０＝１＋１＝０
０＋１＝１＋０＝１
０・０＝０
１・０＝０・１＝０
１・１＝１
です（定義にもどってやってみるとわかると思います）。
あとはビット列を０、１に当てはめればよいのではないでしょうか？
混乱させてしまい申し訳ありません。

お礼

詳しい回答ありがとうございます。

matsuanさんの回答をみて"Z/2Z"が、理論的な演算を示しているということはなんとなく理解できました。
理解能力に欠けるこの頭には、代数学を始めとしたもろもろの『算数エキス』が必要なことを痛感しました。

こんな情けないオヤジにご親切な回答ありがとうございました。
貴重なお時間を割いていただき感謝しております。
今後ともよろしくお願い申し上げます。

回答No.3

motsuan

Ｚ／２Ｚというと整数全体（整数環）Ｚを
イデアル２Ｚ（２の倍数全体）で割ったもの
（Ｚの要素ｕが与えられたときに、２Ｚのある要素ｈがあって
　ｕ＝ｖ＋ｈ（ｖは０または１）
　となるとき、ｖをＺ／２Ｚの要素として表したもので、
　これは代数的に閉じています）
つまり０または１となるブール代数のようなもんじゃないでしょうか？
Ｚ／２Ｚの多項式というのはそれを係数とする多項式で、多項式の演算で
係数部分をブール代数としてあつかえばいいのではないかと思います。
そういう文脈ではなかったでしょうか？
見当違いでしたらごめんなさい。

回答No.1

stomachman

とりあえず。

符号理論の巡回符号の話ですねえ。
Z/2Z ってのは多項式環の名前であると思われますが、調べないとわかんないです。
多項式環の概念については下記URLがご参考になるかも。

参考URL：

http://oshiete1.goo.ne.jp/kotaeru.php3?q=31041

お礼

早速の回答ありがとうございます。

ご紹介いただいた参照URLで、生成多項式が用いられる符号化について理解することができました（完全ではありませんが）。
ネットワークの勉強をするためには符号化技術は切っても切れない様子。符号化理論の勉強が必要だと痛感しています。前途多難。

stomachmanさんには有用な情報をいただき大変感謝しております。
今後ともよろしくお願い申し上げます。
ありがとうございました。