モジュロ２除算ってどうやるの？

質問

情報処理の勉強をしてるのですが、CRCを算出する時の過程でモジュロ2除算というのを使うと書いてあります。

その中でこのように書かれているのですが、この計算の意味がわかりません。

X11+X10+X7 ÷　X6+X2+1 = X5+X4+1 余り…X5+X4+X2+1

モジュロ２除算って、どうやって計算するんですか？
教えて下さい。

回答No.3

zabuzaburo · ベストアンサー

まずは予備知識から。
----------
例えば整数を3で割ると
「割り切れる」か「1余る」か「2余る」か、のいずれかです。
すなわち、余りは「0.1.2」以外にはありません。
それでは「-7」を3で割るとどうなるでしょうか？
(-7) ÷ 3 = (-2) 余り (-1)？
これは間違いとは言いにくいですが、
余りは「0,1,2」しか許されないとすれば
(-7) ÷ 3 = (-3) 余り 2
とするのが良いですね。
これは、数直線上に等間隔に整数をとって、
その下に余りを「0,1,2,0,1,2,……」と書いていき、
負の整数に対しても同様に延長すれば納得できます。
----------

ご質問の除算を、全く普通に行なえば
(x^11 + x^10 + x^7) ÷(x^6 + x^2 + 1)
= (x^5 + x^4 - 1) 余り (- x^5 - x^4 + x^2 + 1)
となります。これなら分かりますね。
ここで係数だけを取り出すと、
(1 1 0 0 1 0 0 0 0 0 0 0) ÷ (1 0 0 0 1 0 0)
= (1 1 0 0 0 -1) 余り (-1 -1 0 1 0 1)
となります。被除数(割られる数)と余りだけを対応させると、
(1 1 0 0 1 0 0 0 0 0 0 0) → (-1 -1 0 1 0 1)
すなわち、「110010000000」というデータがあったとき、
これらを係数に持つ多項式(x^11 + x^10 + x^7)を作り、
あらかじめ用意しておいた別の多項式(x^6 + x^2 + 1)で割った余りを計算し、
その係数を再びビット列に直して記録しておくわけです。
このとき、コンピュータは0か1しか格納できませんから、
これら以外の係数が現れたら偶数は0に、奇数は1に変換します。
これは言い換えれば、2で割った余り(modulo 2)を考えていることに相当します。
すなわち、上の例で得られた係数はさらに
(-1 -1 0 1 0 1) ≡ (1 1 0 1 0 1)と変換され、
ビット列「110101」が格納されます。
これを多項式に書き戻すと、
ご質問のような一見奇妙なmodulo除算ができあがります。

CRCでは、この余分な(= 冗長な)ビット列をチェックすることによって、
データ転送の誤りを検出するわけです。

回答No.4

nubou

私の回答は商ではなく余りの求め方でしたが
符号理論にとっては商はほとんど意味なくて
あまりの方が重要なのです
従って商は捨てるようにして余りを求めるのが普通です

回答No.2

nubou

ｍｏｄ（２）の世界では０と１しかなく２は０とみなします
引き算も足し算も同じです
ｘ＾１１＋ｘ＾１０＋ｘ＾７をｘ＾６＋ｘ＾２＋１で割る場合には
まず
最高次数ｘ＾１１に着目してｘ＾６＋ｘ＾２＋１にｘ＾５を掛けて最高次数を同じにしてｘ＾１１＋ｘ＾１０＋ｘ＾７から引き（＝に足し）ます
そうするとｘ＾１１＋ｘ＾１０＋ｘ＾７の次数が下がります
このような操作をｘ＾１１＋ｘ＾１０＋ｘ＾７の操作結果の次数が６未満になるまで繰り返します
その操作の最終結果が
（ｘ＾１１＋ｘ＾１０＋ｘ＾７）÷（ｘ＾６＋ｘ＾２＋１）です

回答No.1

ymmasayan

２進数で割り算をやりますが、桁ごとの引き算に関して１つだけ特別な約束があります。
０－１＝１とします。（この約束を使う除算がモジュロ２除算です）
モジュロと言うのは余りと言う意味のようです。余りだからマイナスは許さないので
２を足してプラスにすると言うことのようです。

後は、上記の式を（２＾１１＋２＾１０＋２＾７）÷（２＾６＋２＾２＋２＾０）
と考えて割り算していきます。
上記の（０－１＝１）は例えば「０－２＾５＝２＾５（０－１）＝２＾５」というような形であらわれます。

頑張って下さい。判りにくければ補足してください。