-PR-
解決済み

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

  • 暇なときにでも
  • 質問No.33910
  • 閲覧数378
  • ありがとう数7
  • 気になる数0
  • 回答数4
  • コメント数0

お礼率 84% (11/13)

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

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

何卒よろしくお願い申し上げます。
通報する
  • 回答数4
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.2
レベル11

ベストアンサー率 55% (155/280)

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

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

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

お礼率 84% (11/13)

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

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

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

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

その他の回答 (全3件)

  • 回答No.1
レベル14

ベストアンサー率 57% (1014/1775)

とりあえず。

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

お礼率 84% (11/13)

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

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

stomachmanさんには有用な情報をいただき大変感謝しております。
今後ともよろしくお願い申し上げます。
ありがとうございました。
投稿日時 - 2001-01-30 19:14:38


  • 回答No.3
レベル10

ベストアンサー率 40% (54/135)

Z/2Zというと整数全体(整数環)Zを
イデアル2Z(2の倍数全体)で割ったもの
(Zの要素uが与えられたときに、2Zのある要素hがあって
 u=v+h(vは0または1)
 となるとき、vをZ/2Zの要素として表したもので、
 これは代数的に閉じています)
つまり0または1となるブール代数のようなもんじゃないでしょうか?
Z/2Zの多項式というのはそれを係数とする多項式で、多項式の演算で
係数部分をブール代数としてあつかえばいいのではないかと思います。
そういう文脈ではなかったでしょうか?
見当違いでしたらごめんなさい。
  • 回答No.4
レベル10

ベストアンサー率 40% (54/135)

すいません、訂正です。
ブール代数って1+1=1でしたっけ?
Z/2Zは演算は
0+0=1+1=0
0+1=1+0=1
0・0=0
1・0=0・1=0
1・1=1
です(定義にもどってやってみるとわかると思います)。
あとはビット列を0、1に当てはめればよいのではないでしょうか?
混乱させてしまい申し訳ありません。
お礼コメント
iyokiti

お礼率 84% (11/13)

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

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

こんな情けないオヤジにご親切な回答ありがとうございました。
貴重なお時間を割いていただき感謝しております。
今後ともよろしくお願い申し上げます。
投稿日時 - 2001-01-30 20:23:11
このQ&Aのテーマ
このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


専門家があなたの悩みに回答!

-PR-

ピックアップ

-PR-
ページ先頭へ