• ベストアンサー

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

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

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

  • ベストアンサー
  • ymmasayan
  • ベストアンサー率30% (2593/8599)
回答No.2

No.1のymmasayanです。 やはり、舌足らずでしたね。 まず、モジュロにはいろんな意味がありますが、ここでは「剰余:あまり」の事だと思ってください。商は考えずにあまりだけを求める演算をモジュロ演算(モジュロ除算)といいます。BASICでは Y=25 MOD 3 と書き、Yは1になります。 同様に Y=1 MOD 3 もYは同じ1になります。 次にビット列同士の割り算を考えます。あくまでも、あまりを求めるのが目的です。前回も言ったように電子回路で演算するとき、桁借りは複雑になるので、空中から借りることにします。(そういう割り算ルールを作るのです) 2進数では割り算は2進数の引き算と同じです。1桁だけ考えると 1-1=0 1-0=1 0-0=1 で問題ないですが  0-1=-1だけは空中から桁借りして、0-1=1とします。 あくまでもそういう約束ですので、覚えてください。 >なぜ上の桁から、桁借りをしなくて、空中から借りてしまってもいいのですか? あくまでもそういう約束です。回路を簡単にするためだと思います。 >普通に演算しても、モジュロ除算を使用しても、演算結果は、同じなのですか?(自分でやってみて、なんか違うような感じがしたもんで・・・) もちろん、答えは違うはずです。でも受信側でも同じ演算をするので一向に構いません。 >あと、モジュロ2除算とは、どういうものなのですか?申し訳ないのですが、宜しくお願いします。 2で割ってあまりを求めることですが、先ほど言ったように、ここでは桁ごとに分解して行っています。

1976no12ri29
質問者

お礼

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

その他の回答 (1)

  • ymmasayan
  • ベストアンサー率30% (2593/8599)
回答No.1

モジュロ除算といっても言葉で受ける印象ほど難しいことはやっていません。 2進法を前提にすれば隣の桁との桁借り、桁貸しのない引き算を桁ごとにやればよいのです。しかも商が欲しい訳ではなくあまりだけが欲しいのですね。 でも引けないときはどうするか? このときは(上の桁からでなく)空中から2を借りてきます。これが起きるのは、0-1=1のときだけです。 桁の貸し借りがないので、EX-ORで演算できるわけがお分かりでしょう。 桁の貸し借りをしないので、CRCチェック用のハードが超簡単化されるはずです。 判りにくければ補足ください。

1976no12ri29
質問者

補足

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

関連するQ&A

  • データ伝送の誤り訂正の技術について

    誤り訂正の技術の1つであるCRC演算回路について勉強しているのですが。その中で、Ex-ORを使った、モジュロ2除算というものが出てきたのですが、どうもいまいち納得できないので、教えて下さい。どうしてEx-ORを用いることによって、余りのを出す事が出来るのですか?どこまで(何回)演算すれば、その余りをCRCコード(伝送時に誤り訂正として付属するもの)として利用できるのですか?私はかなりの初心者なので、出来れば詳しく教えて下さい。宜しくお願いします。

  • モジュロ2除算ってどうやるの?

    情報処理の勉強をしてるのですが、CRCを算出する時の過程でモジュロ2除算というのを使うと書いてあります。 その中でこのように書かれているのですが、この計算の意味がわかりません。 X11+X10+X7 ÷ X6+X2+1 = X5+X4+1 余り…X5+X4+X2+1 モジュロ2除算って、どうやって計算するんですか? 教えて下さい。

  • 引き放し法による除算アルゴリズムについて

    突然の質問失礼いたします。 現在私は学校で引き戻し法・引き放し法といった除算のアルゴリズムについて学んでいるのですが、そのうちの引き放し法について質問したく投稿しました。 引き放し法について自分で勉強しようと思い、いろいろ調べていたのですが、商と余りを出す引き放し法は見つかっても、小数点以下にわたってまで商を求める引き放し法がまったく見つかりませんでした。 (例えば5÷2=2あまり1と結果を出すのではなく、5÷2=2.5と結果を出す引き放し法のことです。) 少数点以下にわたってまで商を求める引き放し法は商と余りを出す引き放し法で表現できるのでしょうか? もしよろしければ教えていただけると幸いです。また、参考にすべきインターネットサイト等もあれば教えていただけると助かります。

  • [2進数 シフト演算 除算について]

    [2進数 シフト演算 除算について] シフト演算について勉強中です。ご協力お願い出来たら幸いです。 乗算について例えば『1010』(符号ビットを考えず)を2倍 4倍 8倍(2のn乗)した場合 ビットを2倍であれば1つ、4倍であれば2つ・・・左に シフトすれば良いというのは理解しました。 また3倍 5倍などのケースも、 3倍であれば1ケタ左にシフトした数+1010で求まる事も理解しました。 問題は除算です。他の質問を探ってみたのですが、考え方は一緒という回答で・・・詰まっています 除算は右シフトとの事ですが 先ほどの例である『1010』(10)ですがこれを1/2、つまり2で割ると 1つ右にシフトし1010→0101 となり 1010を1/4する場合右に2ビットシフトし 1010→0010.10 となり理解は出来ます。 しかし1/3 、1/5といった場合の計算の仕方が分かりません。 余りを出さないという考えで(近似値になると思いますが) 解き方をご教授願えたらと思います。

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

    こんにちはお世話になります。 私はネットワークに興味があるオジサンです。 先日、データリンク層のプロトコル群を勉強していたとき、誤り訂正でCRCが出てきました。 CRC(Cyclic Redundancy Cheak)の解説には、 >ビット列をZ/2Z上の多項式の係数列とみなし, もとのデータにチェックビットを 継ぎ足して必ず特定の生成多項式で割り切れるデータのみを送るようにする. > とありました。 上記の「Z/2Z上」とは何を指しているのでしょうか。 数学が大の苦手ですので優しく解説していただければ幸いです。 何卒よろしくお願い申し上げます。

  • 四則演算についてです

    四則演算の除算法についてですが {23/6}を2進数で求めたいです。 但し、被除数は6ビット、除数は4ビットという条件付き。 23=(0 10111)2 6=(0 110)2 2の補数を用いて-6=(1 010)2 減算結果が正の場合、商として1をたて 減算結果が負の場合、商として0を立てるのですが 010111 +)1010    商 --------- 111111 …0 +) 1010 --------- 1010011 …0 +) 1010 --------- 1101 …0 +) 1010 --------- 10111 となってしまい商と余りがうまく出ません! 間違ってるところ教えてください!

  • EX-OR回路って?

    自分はこの春から回路の勉強をはじめた大学生なのですが、 「EX-OR回路とは何か調べよ」というレポートに苦しんでいます。 詳しい方、よろしくお願いしますm(__)m

  • CRC8 ATMの計算方法

    CRC8 ATMの演算を行うツールの検証を行っているのですが、 CRCの机上計算方法を詳しく解説したサイトが無く生成多項式で 割って余りを求めると言う事しかわかりませんでした。 CRCを求める際はCRCの初期値も重要な筈ですが、CRCの初期値は 余りを求める際にどの様に使うのかを開設した物がなく、私に 検証を依頼してきた人に聞いてもまともな回答をもらえません でした(検証を依頼してきた人もちゃんと理解していない?)。 このサイトの別の質問の回答で 1. 与えられたデータの下位 (ビット送りの反対側) に「初期値」   を付加する 2. 生成多項式で割って余りを求める とあったので、その通りに計算しましたが初期値が0x00の時は ツールと机上計算の結果が一致するのですが、初期値0xFFの時は ツールと机上計算の結果が一致しませんでした。 実際の計算過程と結果は下記です。 生成多項式:x8+x2+x1+1(9'b100000111) 入力データ:0x12345678 CRC初期値:0x00 データ左送り、入出力反転なし 机上計算 初期値:0001001000110100010101100111100000000000(0x1234567800) 100000111 ---------------------------------------- 0001001000100010101100111100000000000 100000111 ---------------------------------------- 0001001010010101100111100000000000 100000111 ---------------------------------------- 0001011100101100111100000000000 100000111 ---------------------------------------- 0011101011100111100000000000 100000111 ---------------------------------------- 01101000000111100000000000 100000111 ---------------------------------------- 0101001110111100000000000 100000111 ---------------------------------------- 001001001111100000000000 100000111 ---------------------------------------- 0001000001100000000000 100000111 ---------------------------------------- 0000000010000000000 100000111 ---------------------------------------- 00000011100 なのでCRC(余り)は0x1C(00011100)でツールの結果0x1Cと一致。 CRC初期値:0xFF 机上計算 初期値:0001001000110100010101100111100011111111(0x12345678FF) 100000111 ---------------------------------------- 0001001000100010101100111100011111111 100000111 ---------------------------------------- 0001001010010101100111100011111111 100000111 ---------------------------------------- 0001011100101100111100011111111 100000111 ---------------------------------------- 0011101011100111100011111111 100000111 ---------------------------------------- 01101000000111100011111111 100000111 ---------------------------------------- 0101001110111100011111111 100000111 ---------------------------------------- 001001001111100011111111 100000111 ---------------------------------------- 0001000001100011111111 100000111 ---------------------------------------- 0000000010011111111 100000111 ---------------------------------------- 00011100011 なのでCRC(余り)は0xE3(11100011)でツールの結果0xCDと不一致 となりました。 これは計算の仕方が間違っているのでしょうか? それともツールの結果が間違っているのでしょうか? 何方かCRCの計算に詳しい人、ご回答をお願いします。

  • 差動符号化(NRZI)について

    通信の「符号化技術」についてなのですが なぜ符号化をするのか がわかりません。 いろいろ本屋に行ってデータ通信に関する本を読んだのですが 「これ」というものがありません。  また、論理回路でOR、AND、Ex-ORなどの操作をすることの「意味」はどのように考えればよいのでしょうか。演算の仕方はわかってきたのですが、これらの操作の「意味」がわかりません。  もし知っている方、わかりやすい本を知っている方がいましたら是非教えて下さい。よろしくお願いします。

  • ラダー設計について教えてください

    反応炉システムの設定値をLED表示灯に表示するという ラダーの設計の例題を解きたいのですが、初心者で 全く手が付けられません。参考になるものがあれば、 教えていただきたいのですが・・・ 問題の詳細は、出力レジスタに数値をセットすると その値が表示されるというものです。 設計条件:ネットワーク方式 Pt100Ωよりの信号はアナログモジュールへ入力され、アナログモジュール で0~200℃/0~4095に変換される(Pt:白金) 入力レジスタ:30001 LED表示灯用の出力レジスタは40001で10進3桁整数表示 (演算結果は小数点1桁目四捨五入) 途中経過の演算レジスタは40501,49502と49503を使用 一次関数演算回路 演算は乗算回路が先で除算回路と続き桁上げ回路が最後 上記の内容ですが、さっぱり分かりません。 こんな質問で申し訳ないですが、何方かアドバイスを いただければと思います。