モジュロ除算について教えて下さい。お願いします。

質問

現在、CRC演算回路(Cyclic Redundancy Check)の勉強をしているのですが、モジュロ２除算というものがよくわからないので、教えて下さい。何か、Ex-ORを使用して演算しているのですが、どうしてそのような演算結果で、余りが出るのかわからないので、よろしければ、詳しく教えて下さい。よろしくお願いします。

回答No.2

ymmasayan · ベストアンサー

No.1のymmasayanです。
やはり、舌足らずでしたね。
まず、モジュロにはいろんな意味がありますが、ここでは「剰余：あまり」の事だと思ってください。商は考えずにあまりだけを求める演算をモジュロ演算（モジュロ除算）といいます。ＢＡＳＩＣでは
Ｙ＝２５　ＭＯＤ　３　と書き、Ｙは１になります。
同様に　Ｙ＝１　ＭＯＤ　３　もＹは同じ１になります。
次にビット列同士の割り算を考えます。あくまでも、あまりを求めるのが目的です。前回も言ったように電子回路で演算するとき、桁借りは複雑になるので、空中から借りることにします。（そういう割り算ルールを作るのです）

２進数では割り算は２進数の引き算と同じです。１桁だけ考えると
１－１＝０　１－０＝１　０－０＝１　で問題ないですが　
０－１＝－１だけは空中から桁借りして、０－１＝１とします。
あくまでもそういう約束ですので、覚えてください。

＞なぜ上の桁から、桁借りをしなくて、空中から借りてしまってもいいのですか？

あくまでもそういう約束です。回路を簡単にするためだと思います。

＞普通に演算しても、モジュロ除算を使用しても、演算結果は、同じなのですか？（自分でやってみて、なんか違うような感じがしたもんで・・・）

もちろん、答えは違うはずです。でも受信側でも同じ演算をするので一向に構いません。

＞あと、モジュロ２除算とは、どういうものなのですか？申し訳ないのですが、宜しくお願いします。

２で割ってあまりを求めることですが、先ほど言ったように、ここでは桁ごとに分解して行っています。

お礼

丁寧に解説していただき、本当にありがとうございます。大変参考になり、助かりました。また機会があれば、いろいろと教えてください。ありがとうございます。

回答No.1

ymmasayan

モジュロ除算といっても言葉で受ける印象ほど難しいことはやっていません。
２進法を前提にすれば隣の桁との桁借り、桁貸しのない引き算を桁ごとにやればよいのです。しかも商が欲しい訳ではなくあまりだけが欲しいのですね。
でも引けないときはどうするか？　このときは（上の桁からでなく）空中から２を借りてきます。これが起きるのは、０－１＝１のときだけです。
桁の貸し借りがないので、ＥＸ－ＯＲで演算できるわけがお分かりでしょう。
桁の貸し借りをしないので、ＣＲＣチェック用のハードが超簡単化されるはずです。
判りにくければ補足ください。

補足

ありがとうございます。大体のことは、わかったのですが、少し疑問が残ります。なぜ上の桁から、桁借りをしなくて、空中から借りてしまってもいいのですか？あと、普通に演算しても、モジュロ除算を使用しても、演算結果は、同じなのですか？（自分でやってみて、なんか違うような感じがしたもんで・・・）あと、モジュロ２除算とは、どういうものなのですか？申し訳ないのですが、宜しくお願いします。