こんにちはお世話になります。
私はネットワークに興味があるオジサンです。
先日、データリンク層のプロトコル群を勉強していたとき、誤り訂正でCRCが出てきました。誤り訂正ではパリティーチェックやチェックサム等は聞き覚えがありましたが、CRCは始めて見たので興味を持ち少し調べてみようと思いました。
それが間違いの元でした。
インターネットでCRCの構造を詳しく解説するサイトが少なく、その解説は難しすぎて手におえません。
数学にはめっぽう弱い私には、多項式同士の加減乗除算などは頭痛の肥やしにしかなりません。
今ではCRCが気になって勉強に集中できない状態です。
そこで、表題にもあるCRCのアルゴリズムを、何方か分かり易く教えてくださいませんか。もしくは、CRCのアルゴリズムを簡単に解説している書籍をご存知でしたら教えてください。
カテゴリー(本来は数学系?)が違うかもしれませんが、何卒よろしくお願い申し上げます。

このQ&Aに関連する最新のQ&A

A 回答 (2件)

偶数パリティについておさらいすると、1 となるビットの個数が偶


数になるように、検査ビットを定めるというものですよね?で、検
査側では、1 の個数を数えて奇数だとエラーと判断するわけです。

実は、この偶数パリティというチェックのしかたは、CRC の一種な
んです。CRC では、ある特定の生成多項式を使いますが、CRC の生
成多項式として x + 1 を使ったものが偶数パリティです。

多項式の加減乗除で頭痛ということなら、ちょっと説明が厳しいの
ですが、2進数の加減乗除はできるでしょうか?これがだいじょう
ぶなら、1+1=0(つまり、0-1=1)という世界での2進数の加減乗除
を考えるということでも同じです。

この場合、x+1 という多項式は、11 と考えます。(xのi乗の係数
を第iビットの値とみなす)

例えば、10110 というデータに対して、11 という生成多項式で
CRC の検査ビットを求めるには、生成多項式の桁数-1=1ビット
分データを左にシフトして、101100 を得ます。この値を、上の特
殊な2進数の世界で、生成多項式の 11 で割ります。そうすると、
商として 11011、余りとして 1 が得られます。試しにやってみて
ください。この余りを、101100 から引いて(特殊な2進数の世界で
は足すのと同じ)やると、101101 が出ます。これが送るべき符号
ということになります。実際、1の個数は偶数ですので、付け足し
たビットが偶数パリティとなっていることがわかります。

余りの分を引いたわけですから、このデータは 11 で割り切れるは
ずですので、検査側では 11 で割って、余りが 0 であることを確
認すればいいわけです。

この生成多項式の選び方で、検査の能力が変わってきます。やみく
もに選んだら、検査能力がまったくなくなります。通常の CRC は、
それを考慮してうまく多項式を作ってあるというだけのことです。

なぜ 11 なら偶数パリティと同じなのかとか、生成多項式をどう選
べばいいかとかについては、符号理論の勉強が必要です。前者はそ
れほど難しくはないですが。
    • good
    • 0
この回答へのお礼

丁寧な回答ありがとうございます。
パリティティーチェックで1ビットだったパリティーが、CRCでは多項式で多ビットに置き換えたのですね。理解しました(^_^;)。
ご指導の通り計算してみました。最初は「特殊な二進数の世界」に戸惑ってしまいましたが、めでたく計算できました。

ビット列を高次元に表すことは、アドレスからデータ範囲までチェックするために必要だったんですね(ホンマかいな)、と勝手に納得しています。
おっしゃる通り符号理論の勉強が必要なようです(頭が痛い)。

punchan_jpさんの回答で多項式の符号化計算まで理解(ほんの少しですが)できるとは思っていませんでした。とても得した気分です。

punchan_jpさんには貴重な時間を割いていただき、大変感謝しております。
これからもよろしくお願い申し上げます。
ありがとうございました。

お礼日時:2001/01/30 18:50

凄い難しい事ですね。

CRCの計算方法だけでも結構な厚さの本が出来てしまうので、ここでは、簡潔に書きます。
----ここから
 CRCは、データ列を高次の多項式と考えて、その多項式をあらかじめ定められた生成多項式で割る。その余りをBCCとしてデータの後ろに付加して送信する。
 また、受信側では同じ生成多項式で割り算を行い、余りがなけば転送データに誤りがないと判断する。
-----
 こんな感じでですが....どうでしょうか?

 もし勉強に集中出来ないって事なら、CRCはチェックサムのやり方(計算方法)って覚えると良いでしょう。
 具体的な計算方法が判らなくても、何をする物なのか理解出来ればそれほど大きな問題になるとは思えません。

詳しく知りたい場合には、通信プロトコル関係の書籍を呼んで下さい。説明が詳しく書かれています。
    • good
    • 1
この回答へのお礼

早速の回答ありがとうございます。
要点を易しく解説していただき、ウニ状態の頭の中もようやく整理できました。
CRCはエラーチェックだと軽くCRCを流したかったのですが、データリンク層に使われているからには何か理由があるのかと思い込み、調べ始めたのが運のつきでした。オヤジの冷や水、数学はもうこりごりです。

mnabeさんには当質問で貴重な時間を割いていただき、大変感謝しております。
これからもよろしくお願い申し上げます。
ありがとうございました。

お礼日時:2001/01/30 18:20

このQ&Aに関連する人気のQ&A

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

QCRC556について

冬に乗っていなかったらブレーキディスクに大量のさびがありCRC556を300円くらいで買ってきたんですがディスクに塗っても大丈夫でしょうか?
車のナットにさびどめとはかいてありました

Aベストアンサー

絶対にやってはだめです。このサイトでも何度も書いてきたことですが、こと、ブレーキに関しては、そのパーツのすべての役割と仕組みがわかる人以外は手を出すべきではありません。ブレーキの故障は事故に直結し、自分はもちろん他人の生命まで危険にさらす可能性があるからです。まして大きな摩擦作り出すのが目的のブレーキディスクに潤滑在など使おうというのは正気の沙汰とは思えません。

通常状態であれば、ブレーキディスクのさびは走行して何度がブレーキを使えば落ちますので、気にする必要はありませんが、あまり大量にさびが発生している状態では、ブレーキパッドにさびが食い込み、ブレーキ泣きなどの原因になる場合もあります。また、停止時にブレーキパッドの挟まれていた部分ではさびの発生が起こりにくいのですが、他の部分はさびていきます。この状態があまり極端になると、錆びを落としたときに錆びていた部分と錆びていなかったところでディスクローターの厚みに差が出てしまい、ブレーキペダルにキックバック(ペダルを押し戻すような振動)が発生したり、強くブレーキを踏んだときなどに不意にロックしたりなど危険な状態になります。このような症状が出た場合はディスクローターの交換または研磨を行う必要があります。



とにかく、普通にブレーキを何回か操作してみて問題があるようであれば、あなたにはそれ以上の整備などをするスキルはありませんので、専門家による点検整備をされることをお勧めします。

絶対にやってはだめです。このサイトでも何度も書いてきたことですが、こと、ブレーキに関しては、そのパーツのすべての役割と仕組みがわかる人以外は手を出すべきではありません。ブレーキの故障は事故に直結し、自分はもちろん他人の生命まで危険にさらす可能性があるからです。まして大きな摩擦作り出すのが目的のブレーキディスクに潤滑在など使おうというのは正気の沙汰とは思えません。

通常状態であれば、ブレーキディスクのさびは走行して何度がブレーキを使えば落ちますので、気にする必要はありません...続きを読む

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

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

Aベストアンサー

crcで使われる多項式の係数は普通は0と1からなる体です
その体上での足し算は
0+0=0,0+1=1,1+0=1,1+1=0でありまさにmod2の足し算なのです
その体上でのかけ算は
0・0=0,0・1=0,1・0=0,1・1=1です

係数が実数の普通の多項式間除算によって余りを出す場合には
「割る方の多項式」にxのべき乗と適当な実数をかけたものを「割られる多項式」から引く演算を繰り返して実行して最終的に「割る方の多項式」の多項式より次数が小さい多項式を余りとして求めますね
今回は同じことを上の体を係数とする多項式で行うだけで同じです
ただ引き算は足し算と同じですし0と1しか現れないのでむしろ簡単です

「割られる多項式」の次数をn-1とし「割る方の多項式」の次数をmとすれば
最大n-m回多項式間の足し算をすれば余りが得られます

QCRC556を使うとホコリと一緒に固まる

CRC556を使うと、時間が経ったときにホコリと一緒に固まります。
そのため、逆にスムーズな動きができなくなります。
これは、どの成分が悪さをしているのでしょうか?
または、その成分がない油とはどんなものでしょうか?

Aベストアンサー

ステンレスのような金属同士ですべりの速度が高くない用途であれば、固体潤滑剤が使えるかもしれませんね。これはオイルのように液体の幕で金属同士の接触を防ぐのではなく、PTEFや二硫化モリブデンという非常に摩擦係数の小さな固体の皮膜や粒子で摩擦部分を覆ってしまうやり方です。塗布後しばらくは固体潤滑剤を分散させるための油分がありますが、固体潤滑剤自体が金属表面に定着した後はふき取ってしまっても効果は持続しますので、埃の吸着なども少ないでしょう。まぁ、簡単に言ってしまえば、摩擦部分にごく薄いテフロン加工(フライパンなどでおなじみ)や二硫化モリブデン加工をしてしまうようなものです。液体に頼らないため、埃の吸着なども起こりません。

大きな力(面圧)が掛かっている部分では二硫化モリブデンの方がいいでしょうし、それほどでもなければPTEFでいいでしょう。この製品は乾燥皮膜ですので噴射後何回か動かしてなじませた後は自然に乾燥してしまいますので、ふき取りの手間もないでしょう。ただし、これらの製品の性能を十分に発揮するには、使用前に摩擦部分の汚れをきれいに落としておく必用があります。分解できないようなところであれば、脱脂剤(パーツクリーナー)などを使って、一度きれいにしてから使用することで、より長い間、十分な潤滑があられるようになります。

参考URLにPTEFの乾燥皮膜形成用のスプレーを載せておきます。

参考URL:http://www.haikanbuhin.com/shopping/detail/14426/?gclid=CMyxna3EmKgCFUqFpAodDB6pCw

ステンレスのような金属同士ですべりの速度が高くない用途であれば、固体潤滑剤が使えるかもしれませんね。これはオイルのように液体の幕で金属同士の接触を防ぐのではなく、PTEFや二硫化モリブデンという非常に摩擦係数の小さな固体の皮膜や粒子で摩擦部分を覆ってしまうやり方です。塗布後しばらくは固体潤滑剤を分散させるための油分がありますが、固体潤滑剤自体が金属表面に定着した後はふき取ってしまっても効果は持続しますので、埃の吸着なども少ないでしょう。まぁ、簡単に言ってしまえば、摩擦部分...続きを読む

Qパソコンでのインターネット放送の誤り訂正・変調方式

パソコンでのインターネット放送の、誤り訂正方式と変調方式は、それぞれ何ですか?但し、WiFiのを除きます。

Aベストアンサー

インターネット、すなわちネットワーク上のエラー訂正(エラー検出及び再送)は、「データリンク層」で行われています。

>Wikipedia: イーサネット
>https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%BC%E3%82%B5%E3%83%8D%E3%83%83%E3%83%88

このため、通信する機器間(アプリケーション層)では、「受け取ったデータが壊れているかどうか?」という心配をすることは無く、「データパケットが届いたならば、その内容は全て正しい」ものとして、扱えます。

>OSI参照モデル
>http://ja.wikipedia.org/wiki/OSI%E5%8F%82%E7%85%A7%E3%83%A2%E3%83%87%E3%83%AB

ただし、「パケットが届いたならば、データは正しい」けれども、「データが届かない(パケットロス)」という可能性はあります。

そこを、アプリケーション層ではそれを検出し、元のサーバーへ再送要求を出したりします。(FTP等)

しかし、ストリーミングの動画データではまた事情が違います。
1パケット欠落したからと言って、動画の再生を止めて、そのパケットが正常に受信できるまで待つ…なんてことをやっていたら、動画はたびたび再生停止してしまうでしょう。

そこで、一定時間ごと(1秒毎など)に「キーフレーム」と言うのを入れて、データの途中からでも動画再生が可能なようになっています。
動画の圧縮形式というのは、基本的には「キーフレーム」に全画面の画像があり、その後しばらくは、その画像から変わった部分だけをデータとして送信する、そしてまたキーフレームがある…と言うような構造になっています。
パケットロスして、再生が引っかかったり画像の一部が壊れたりしても、次のキーフレームからはまた正常な再生が出来ます。

まあぶっちゃけ、動画再生のアプリケーション層ではエラー訂正はせず、そのまま再生を続けてるって事になりますけど。
ですので、誤り訂正方式も何もありません。

インターネット、すなわちネットワーク上のエラー訂正(エラー検出及び再送)は、「データリンク層」で行われています。

>Wikipedia: イーサネット
>https://ja.wikipedia.org/wiki/%E3%82%A4%E3%83%BC%E3%82%B5%E3%83%8D%E3%83%83%E3%83%88

このため、通信する機器間(アプリケーション層)では、「受け取ったデータが壊れているかどうか?」という心配をすることは無く、「データパケットが届いたならば、その内容は全て正しい」ものとして、扱えます。

>OSI参照モデル
>http://ja.wikipedia.org/wiki/OSI%E5%...続きを読む

QCRC-556をかけたらサッシが重くなった

お世話になります。
窓サッシのすべりが悪くなった(キーキー言う)ので、CRC-556をかけてみたところ、直後は大変すべりがよいのですが、しばらくするとサッシを動かすのが重くなってしまいました。解決方法をご存知の方、ご教授いただけますと幸いです。
※再度556をかけたところ、やはり直後は軽くなるのですが、しばらくすると重くなってしまいます。
※ちなみにキーキー音自体はなくなりました。

Aベストアンサー

サッシを外して戸車を確認されるのが良いとは思います

潤滑剤はサッシが入ったままですと肝心の戸車の軸部分に挿せません

極端な場合は、

・サッシが入ったままかけたので車輪とレールにかかっている
・車輪が回らないでレールの上を滑っている
・車輪が廻らないので当然音もしない
・潤滑剤が無くなると重くなる

こういう場合も有ります
そのまま使っていると車輪がいびつにすり減ります

サッシを持ち上げながら移動するとカチャッと上に持ち上がる箇所があると思いますのでそこなら外れます

 「戸車の確認」
 「戸車の軸に潤滑剤」
 「戸車の交換」

を、お勧めします

Qインターネットを流れる情報について解説して頂けませんか?もしくは解説サ

インターネットを流れる情報について解説して頂けませんか?もしくは解説サイトをお教えください。

IPアドレスとフレームの関係、また物理層でやりとりされている電気信号的なところも含めてどなたかお教えください!

L3スイッチやルータがIPアドレスでルーティングしており、L2スイッチがフレームで送信先を判別しいることは調べて分かりました。
しかし、いまいち整理できていない点や曖昧な部分も多く、信がないのでどなたかよろしくお願い致します。

現段階での、不明点です↓
・MACアドレスはどこで機能しているのか
・IPヘッダはどのタイミングで識別されるのか
・トランスポート層以降はどのように通信するのか

部分的な回答でもよいのでぜひお願い致します。
また、認識に間違いがあれば是非ご指摘ください。

よろしくお願いします。

Aベストアンサー

解説サイトも良いけど本読んで勉強した方がベターかも。
http://www.jbook.co.jp/p/p.aspx/3946863/s/
日経NETWORKの本は読みやすく判りやすいです。

QCRC556は、ホコリと一緒に固まるのはなぜ?

ホームセンターなどにある、スプレー油CRC556は、時間が経つとホコリと一緒に固まります。

かなりひどい状態になり、長期的に見たら逆効果とさえ感じることがあります。

なぜ、固まるのでしょうか?

また、この固まってしまう成分は、何でしょうか?

Aベストアンサー

556は、サラッとした浸透性の成分と、油脂成分が両方入っています。

これは即効性がありますが、仇になるんですね。


浸透性の成分は揮発性でもあり、やがて揮発してなくなってしまいます。
最後に残るのは粘度の高い油脂成分のみ、というわけです。


これを考えると、機械用の潤滑油(ギヤオイルやエンジンオイル等)を使ったほうがいい用途もあります。

Qベルマンフォードのアルゴリズム

このカテゴリーであってる・・・かな・・。

とりあえず、ネットワークのアルゴリズムなので。

最短経路を求めるアルゴリズムは、
ダイクストラしか知らなかったのですが、
ベルマンフォードというアルゴリズムがあると知りました。
どのようなアルゴリズムなのでしょうか?
ダイクストラと比較してどうなのでしょうか?

Aベストアンサー

参考になるページがこちらに
http://www.threeweb.ad.jp/~makita/short2.html
http://premium.mag2.com/sample/P0000264.html
さらにドキュメントを探すと
http://www.google.co.jp/search?hl=ja&ie=UTF-8&oe=UTF-8&q=Bellman-Ford+routing&btnG=Google+%E6%A4%9C%E7%B4%A2&lr=
等があります。

QCRC556で有名なクレの製品の評価(チェーン関係の製品)

CRC556で有名なクレ工業からチェーンクリーナーとチェーングリスが
販売されていますが使ったことのある方感想を聞かせてください。
製品説明にはシールチェーンにも安心して使用できますと書いてありますし、何よりホームセンターにて格安(RKおよびホンダ純正などに比べ)売られていますのでちょっと気にかかってます。私個人としてはクレ工業は化学会社としては大きいですし556は有名ですし良いのではないかと思っているのですが。RKにしてもホンダにしても自分のところで作っているわけではないですよね(委託)そういうことで
ぜひお聞かせください。

Aベストアンサー

バイク用品通販を覗いてみたんですが、呉のチェーングリスが見当たりませんでした。チェーンルブとは別物でしょうか?
呉のチェーンルブだったらつかったことがあるのですが、粘度が低いのに浸透力が弱いので私はやめてしまいました。
今は別のを使っています。

QHDLCの誤り検出、再送処理

ネットワークの学習中に少し気になる点がありました。

HDLCは誤り検出、再送処理の機能を有しています。
そこで質問なのですが、なぜデータリンク層でそのような機能を有するのでしょうか。
誤り検出・再送処理は、一般にTCPなどのトランスポート層のプロトコルに依存するのではないのでしょうか。
トランスポート層は確かにエンドツーエンドの通信における保障ですが、各ポイントツーポイントで誤り、再送検出を行えばエンドツーエンドも可能かと思われますし、どちらか片方で良いような気がします。

分かりにくい質問かと思われますが、宜しくお願い致します。

Aベストアンサー

質問者の表現で言えば
レイヤが上位になるほど、一回に処理されるデータ量が多くなるからです

下位レイヤーでエラー検出再送を行った方が再送データは少なくて済みます

最上位層で全部まとめてチェック と言う考え方もありますが 、オールオアナッシングになります
エラー発生の確率が非常に低い場合は、その方が効率的な場合もありますが、エラー発生確率がある値を超えると全データがエラーになってしまいます

データ伝送の基本的な考え方として、ある程度のエラー発生は許容せざるを得ないとしています

なお、通信プロトコルの9割以上はエラーへの対応と思っても見当違いではありません

データ伝送の歴史は、エラー対応の歴史でもあります


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング

おすすめ情報