こんにちはお世話になります。
私はネットワークに興味があるオジサンです。
先日、データリンク層のプロトコル群を勉強していたとき、誤り訂正で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と関連する良く見られている質問

QCRCの計算方法について

色々なサイトを参考にして、自分なりにCRC-ITU-TでCRCを計算する関数を作成しました。
いまいち理解が浅く、そのCRCの値が正しいのか判断できずに困っています。
以下にソースを載せます。
アドバイスを、どうかよろしくお願いします。


unsigned short Crc(unsigned char *Data, unsigned long num)
{
  unsigned short vCrc;    //CRCを計算する変数
  unsigned char vData;
  unsigned long i;
  int j;

  vCrc = 0;
  vData = 0;  //初期化

  for(i = 0; i <= num; i++){
    vData = *(Data+i);  //1byte読み込み
    for(j = 0; j < 8; j++){

      //CRC計算変数がシフトで桁あふれする場合
      if((vCrc & 0x8000) != 0){
        vCrc = vCrc << 1;  //1bitシフト
        vCrc = vCrc ^ 0x1021;  //多項式とXOR
      }
      else{
        vCrc = vCrc << 1;
      }

      if((vData & 0x80) != 0){
        vData = vData << 1;  //データ変数1bitシフト        
        vCrc = vCrc ^ 0x0001;  //CRC計算変数に1をXOR
      }
      else{
        vData = vData << 1;
      }
    }
  }
  return(vCrc);
}

色々なサイトを参考にして、自分なりにCRC-ITU-TでCRCを計算する関数を作成しました。
いまいち理解が浅く、そのCRCの値が正しいのか判断できずに困っています。
以下にソースを載せます。
アドバイスを、どうかよろしくお願いします。


unsigned short Crc(unsigned char *Data, unsigned long num)
{
  unsigned short vCrc;    //CRCを計算する変数
  unsigned char vData;
  unsigned long i;
  int j;

  vCrc = 0;
  vData = 0;  //初期化

  for(i = 0; i <= num; i+...続きを読む

Aベストアンサー

そうなんですか^^ 失礼しました。以下のコードを実行すると boost のライブラリで計算したもの、Ru-LaLaさんのコードで計算したもの、サンプル実装で計算したものを比較すると、Ru-LaLaさんので計算したものだけ値が違うので、Ru-LaLaさんのコードが間違ってる可能性があるような気がします^^;

サンプルコードは、
 http://page.freett.com/seaside/vip/crc/ProgramC1.htm
から取りました。サンプルコードをパクってしまえばいいのでは?(笑)

====
#include <iostream>
#include <boost/crc.hpp>

unsigned short ProgCrc1(unsigned char* Data, unsigned long StartAdr, unsigned long StopAdr)
{ unsigned short vCRC; /*CRCを計算する変数*/
unsigned char vData; /*CRC計算時に1データ読み込む変数*/

/*初期化*/
vCRC = 0;
vData = 0;
/*CRC書き込み位置の初期化*/
*(Data + StopAdr + 1) = 0;
*(Data + StopAdr + 2) = 0;

/*CRC-ITU-Tの計算*/
for(unsigned long Loop1=StartAdr; Loop1<=StopAdr+2; Loop1++) /*CRC書き込み位置までループ*/
{ vData = *(Data + Loop1); /*1Byte読みこみ*/
/*CRC1Byte計算*/
for(char Loop2=0; Loop2<8; Loop2++)
{/*CRC計算変数がシフトで桁あふれするか確認*/
if((vCRC & 0x8000) != 0)
/*桁あふれ有り*/
{ vCRC = vCRC << 1; /*CRC計算変数1Bitシフト*/
vCRC = vCRC ^ 0x1021; /*生成多項式のXOR*/
}
else
/*桁あふれ無し*/
{ vCRC = vCRC << 1; /*CRC計算変数1Bitシフト*/
}

/*データ変数がシフトで桁あふれするか確認*/
if((vData & 0x80) != 0)
/*桁あふれ有り*/
{ vData = vData << 1; /*データ変数1Bitシフト*/
vCRC = vCRC ^ 0x0001; /*CRC計算変数に1XOR*/
}
else
/*桁あふれ無し*/
{ vData = vData << 1; /*データ変数1Bitシフト*/
}
}
}
*(Data + StopAdr + 2) = (unsigned char)(vCRC & 0x00ff); /*CRCの下位書き込み*/
*(Data + StopAdr + 1) = (unsigned char)((vCRC >> 8) & 0x00ff); /*CRCの上位書き込み*/

return(vCRC);
}
unsigned short Crc(unsigned char *Data, unsigned long num)
{
unsigned short vCrc; //CRCを計算する変数
unsigned char vData;
unsigned long i;
int j;

vCrc = 0;
vData = 0; //初期化

for(i = 0; i <= num; i++){
vData = *(Data+i); //1byte読み込み
for(j = 0; j < 8; j++){

//CRC計算変数がシフトで桁あふれする場合
if((vCrc & 0x8000) != 0){
vCrc = vCrc << 1; //1bitシフト
vCrc = vCrc ^ 0x1021; //多項式とXOR
}
else{
vCrc = vCrc << 1;
}

if((vData & 0x80) != 0){
vData = vData << 1; //データ変数1bitシフト
vCrc = vCrc ^ 0x0001; //CRC計算変数に1をXOR
}
else{
vData = vData << 1;
}
}
}
return(vCrc);
}

unsigned short crc_itu_t(unsigned char *data, unsigned long num)
{
boost::crc_basic<16> calc(0x1021);
calc.process_bytes(data, num);
return static_cast<unsigned short>(calc.checksum());
}

int main()
{
unsigned char data[6 + 2] = { 'a', 'b', 'c', 'd', 'e', 'f' };
std::cout << std::showbase << std::hex;
std::cout << crc_itu_t(data, 6) << '\n';
std::cout << Crc(data, 6) << '\n';
std::cout << ProgCrc1(data, 0, 5) << '\n';
std::cout << static_cast<int>(data[6]) << '\n';
std::cout << static_cast<int>(data[7]) << '\n';
}
====
./a.exe
0x3afd
0x58e1
0x3afd
0x3a
0xfd

そうなんですか^^ 失礼しました。以下のコードを実行すると boost のライブラリで計算したもの、Ru-LaLaさんのコードで計算したもの、サンプル実装で計算したものを比較すると、Ru-LaLaさんので計算したものだけ値が違うので、Ru-LaLaさんのコードが間違ってる可能性があるような気がします^^;

サンプルコードは、
 http://page.freett.com/seaside/vip/crc/ProgramC1.htm
から取りました。サンプルコードをパクってしまえばいいのでは?(笑)

====
#include <iostream>
#include <boost/crc.hpp>

...続きを読む

QチェックサムとCRC

複数のデータを照合する時にチェックサムを使っています。
CRCというやり方もあると聞きましたが、
具体的にはどういうことをやるのでしょうか?
宜しくお願いします。

例えば、シリアル通信とかで8ビットデータが複数送られてきて、
そのデータ群が正しいかどうかをチェックする時。

Aベストアンサー

「CRC アルゴリズム」とかで検索すると出てくるかと。
http://hyphenlink.blog48.fc2.com/blog-entry-53.html とか。

んで…チェックサムの場合は…下記のような場合にエラーが検出されません。

・データの順番が入れ替わった場合。
 00 01 02 03 04 05 06 でチェックサムが15h
   ↓
 00 05 02 03 04 01 06 でもチェックサムは15h

・データの一部が減算されていて、別の一部が同じだけ加算されていた場合。
 00 01 02 03 04 05 06 でチェックサムが15h
   ↓
 04 01 00 00 09 01 06 でもチェックサムは15h

CRCだとデータの並びが変わった場合は算出されるCRC値も異なります。
 00 01 02 03 04 05 06 でCRC32がAD5809F9
 00 05 02 03 04 01 06 でCRC32が52A58EEB
 04 01 00 00 09 01 06 でCRC32が5DD68733

QCRC16計算について

CRC16のプログラムを作ったのでデバッグしていて気付いた事なのですが
(産業装置で使うMODBUS-RTUのソフト)
CRC16 x16+x15+x2+1
生成多項式 0xA001

CRC16でCRCを含めたデータを再CRCするとゼロになると言われておりますが
そうならないのですが何故でしょう?

もちろん、自分の作ったソフトが信用できないので他ソフトで検証


具体例
ベクターにあるCRC16の計算ソフト - CRC16.exe
http://blog.goo.ne.jp/masaki_goo_2006/e/50b20edb79f60964faeaefe6fa064469
これに文字列"ABCD" [0x4142,0x4344]を入れて計算実行

出力結果
 初期値:0xFFFF、出力XOR:0xFFFF、出力結果、右送り0x0F85


この出力を最初の文字列に追加する
0x4142,0x4344,0x0F85

結果は0xc7e6 となってゼロになりません
やりかたが違うのでしょうか?


尚、私の作ったプログラムと上記ソフトの結果が同じです
また、ネット上にある同様な他ソフトでも同じ結果でした
(もちろんCRC計算条件が同じ物)

尚、上記ソフトで
初期値:0x0000、出力XOR:0x0000、左送り:9AA8
この場合のみCRC追加しての再CRCはゼロになりました

ゼロになる場合とならない場合があるのでしょうか?

CRC16のプログラムを作ったのでデバッグしていて気付いた事なのですが
(産業装置で使うMODBUS-RTUのソフト)
CRC16 x16+x15+x2+1
生成多項式 0xA001

CRC16でCRCを含めたデータを再CRCするとゼロになると言われておりますが
そうならないのですが何故でしょう?

もちろん、自分の作ったソフトが信用できないので他ソフトで検証


具体例
ベクターにあるCRC16の計算ソフト - CRC16.exe
http://blog.goo.ne.jp/masaki_goo_2006/e/50b20edb79f60964faeaefe6fa064469
これに文字列"ABCD" [0x4142,0x4344]を入れて計...続きを読む

Aベストアンサー

すみません, 忘れてました.

CRC を計算するときには
1. 与えられたデータの下位 (ビット送りの反対側) に「初期値」を付加する
2. 生成多項式で割って余りを求める
3. 「出力XOR」との排他的論理和を計算する
という手順をとります. つまり,
「初期値:0x0000、出力XOR:0x0000、左送り:9AA8」
は (以下 16進で表記します)
1. データ列 41 42 43 44 に初期値 0000 を付加して 41 42 43 44 00 00 を得る
2. それを生成多項式で割って余り 9AA8 を得る
3. それと出力XOR 0000 との排他的論理和を計算して 9AA8 を求める
として得られた値です.

で, 「CRCを含めたデータを再CRCする」というのはこの場合
データ列 41 42 43 44 9A A8 に対して CRC を計算する
言い替えれば「データ列 41 42 43 44 に対し 9A A8 を初期値として CRC を求める」ということです (初期値の設定ができないので, 質問文に挙がっている CRC16.exe ではこのような計算はできません). 最後にある
「尚、上記ソフトで
初期値:0x0000、出力XOR:0x0000、左送り:9AA8
この場合のみCRC追加しての再CRCはゼロになりました」
はおそらく 41 42 43 44 9A A8 というデータを入力した結果だと思いますが, それは実際には
41 42 43 44 9A A8 00 00
に対して CRC を計算しています (41 42 43 44 9A A8 に対して CRC が 0 になるならこれに対しても 0 になるけど, それは「CRC が想定しているチェック方法」ではない).

ここまでは初期値 0000, 出力XOR 0000 なので簡単ですが, その他の値を使った場合には得られた CRC を「適切に」変化させた値を初期値にしないと「CRCを含めたデータを再CRCするとゼロになる」などという都合のいいことにはなりません.

ところで, 初期値と出力XOR が両方とも 0 なら右送りでも (左送りと同じ事情で) 最終的な CRC を 0 にできるんですけど, どうでしょうか?

すみません, 忘れてました.

CRC を計算するときには
1. 与えられたデータの下位 (ビット送りの反対側) に「初期値」を付加する
2. 生成多項式で割って余りを求める
3. 「出力XOR」との排他的論理和を計算する
という手順をとります. つまり,
「初期値:0x0000、出力XOR:0x0000、左送り:9AA8」
は (以下 16進で表記します)
1. データ列 41 42 43 44 に初期値 0000 を付加して 41 42 43 44 00 00 を得る
2. それを生成多項式で割って余り 9AA8 を得る
3. それと出力XOR 0000 との排他的論理和を計算して 9AA8 を求め...続きを読む

QCRC8を教えてください

Cにて16ByteデーターをCRC8にかけたいのですがアルゴリズムがよく理解できません。
どなたかプログラムを教えていただけませんでしょうか? 
また、12Byteのときはプログラムが変わるのでしょうか?

Aベストアンサー

★CRC8 って初めて聞きました。
・私は CRC16、CRC32、CRC64、CRC128 なら聞いた事があります。
 また、CRC16、CRC32 の計算を行うルーチンも作成した経験がありますが CRC8 は初めてです。
 なお、CRC16 の『16』は 16 ビットという意味ですが、CRC8 の 8 も 8 ビットのことですよね。
・CRC16 の場合は 16 ビット以内のサイズなら同じ数値になる確率がかなり低くなります。
 このことから CRC8 では 8 ビット(256バイト)以内のサイズなら同じプログラムでかまわないと
 思います。つまり、16 バイトでも 12 バイトでも同じ CRC8 で OK です。
・『CRC8 計算』キーワードでネット検索すると多数見つかりますね。
 検索した情報から CRC 生成多項式は
 CRC8……X^8 + X^7 + X^2 + 1
 CRC16…X^16 + X^12 + X^5 + 1
 http://www.sumtak.co.jp/japanese/products/linearencoders/pulscale/futabapdf/fmf.pdf
 ↑
 6 ページより抜粋
・CRC8 の実装方法は次のリンクを参考にして下さい。
 http://kone.vis.ne.jp/diary/diaryb07.html
 ↑
 一番下より抜粋すると『CRCの国際標準』として、以下の値がある。
 CRC-12 = x12 + x11 + x3 + x2 + x1 + 1
 CRC-16 = x16 + x15 + x2 + 1
 CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 + 1
 CRC-CCITT = x16 + x12 + x5 + 1
・今回は CRC8 ですので
 CRC8 = X8 + X7 + X2 + 1
 CRC8 = 110000101(2進数)
 となり、0x185 が多項式の値です。でも 8 ビットですので上位の 1 ビットを除いた 0x85 で計算します。
 CRC8 の多項式と 0x85 と他の CRC16 などのソースを元にプログラムしてみて下さい。
・以上。

参考URL:http://kone.vis.ne.jp/diary/diaryb07.html

★CRC8 って初めて聞きました。
・私は CRC16、CRC32、CRC64、CRC128 なら聞いた事があります。
 また、CRC16、CRC32 の計算を行うルーチンも作成した経験がありますが CRC8 は初めてです。
 なお、CRC16 の『16』は 16 ビットという意味ですが、CRC8 の 8 も 8 ビットのことですよね。
・CRC16 の場合は 16 ビット以内のサイズなら同じ数値になる確率がかなり低くなります。
 このことから CRC8 では 8 ビット(256バイト)以内のサイズなら同じプログラムでかまわないと
 思います。つまり、16 バイトで...続きを読む

QCRC32の計算方法

ZIPファイルを作るときにCRC32を算出すると思うのですが、
CRC32の計算方法を教えてください。

よろしくお願いします。

Aベストアンサー

CRCとは巡回冗長検査(じゅんかい・じょうちょう・けんさ)という誤りを検出する方法の1つです。
その他ハッシュ・キーを計算するハッシュ関数としても使うことが出来ます。

今回のCRCは32ビット幅で生成多項式に X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1 を利用します。
この生成多項式は CRC32 で使われているものです。

1.CRCタイプ
(1)CRCタイプ(CRC32)
(2)生成多項式(0x04C11DB7)
(3)初期値(0xFFFFFFFF)
(4)出力XOR(0xFFFFFFFF)
(5)入力ビット逆転(なし)
(6)出力ビット逆転(なし)
(7)ビット送り(左送り)

// サンプル
#include <stdio.h>
#include <string.h>
#include <limits.h> // CHAR_BIT

// CRC32のテーブル情報
static unsigned long CRC32Table[ 256 ] = {
0x00000000, 0x04C11DB7, 0x09823B6E, 0x0D4326D9,
0x130476DC, 0x17C56B6B, 0x1A864DB2, 0x1E475005,
0x2608EDB8, 0x22C9F00F, 0x2F8AD6D6, 0x2B4BCB61,
0x350C9B64, 0x31CD86D3, 0x3C8EA00A, 0x384FBDBD,
0x4C11DB70, 0x48D0C6C7, 0x4593E01E, 0x4152FDA9,
0x5F15ADAC, 0x5BD4B01B, 0x569796C2, 0x52568B75,
0x6A1936C8, 0x6ED82B7F, 0x639B0DA6, 0x675A1011,
0x791D4014, 0x7DDC5DA3, 0x709F7B7A, 0x745E66CD,
0x9823B6E0, 0x9CE2AB57, 0x91A18D8E, 0x95609039,
0x8B27C03C, 0x8FE6DD8B, 0x82A5FB52, 0x8664E6E5,
0xBE2B5B58, 0xBAEA46EF, 0xB7A96036, 0xB3687D81,
0xAD2F2D84, 0xA9EE3033, 0xA4AD16EA, 0xA06C0B5D,
0xD4326D90, 0xD0F37027, 0xDDB056FE, 0xD9714B49,
0xC7361B4C, 0xC3F706FB, 0xCEB42022, 0xCA753D95,
0xF23A8028, 0xF6FB9D9F, 0xFBB8BB46, 0xFF79A6F1,
0xE13EF6F4, 0xE5FFEB43, 0xE8BCCD9A, 0xEC7DD02D,

0x34867077, 0x30476DC0, 0x3D044B19, 0x39C556AE,
0x278206AB, 0x23431B1C, 0x2E003DC5, 0x2AC12072,
0x128E9DCF, 0x164F8078, 0x1B0CA6A1, 0x1FCDBB16,
0x018AEB13, 0x054BF6A4, 0x0808D07D, 0x0CC9CDCA,
0x7897AB07, 0x7C56B6B0, 0x71159069, 0x75D48DDE,
0x6B93DDDB, 0x6F52C06C, 0x6211E6B5, 0x66D0FB02,
0x5E9F46BF, 0x5A5E5B08, 0x571D7DD1, 0x53DC6066,
0x4D9B3063, 0x495A2DD4, 0x44190B0D, 0x40D816BA,
0xACA5C697, 0xA864DB20, 0xA527FDF9, 0xA1E6E04E,
0xBFA1B04B, 0xBB60ADFC, 0xB6238B25, 0xB2E29692,
0x8AAD2B2F, 0x8E6C3698, 0x832F1041, 0x87EE0DF6,
0x99A95DF3, 0x9D684044, 0x902B669D, 0x94EA7B2A,
0xE0B41DE7, 0xE4750050, 0xE9362689, 0xEDF73B3E,
0xF3B06B3B, 0xF771768C, 0xFA325055, 0xFEF34DE2,
0xC6BCF05F, 0xC27DEDE8, 0xCF3ECB31, 0xCBFFD686,
0xD5B88683, 0xD1799B34, 0xDC3ABDED, 0xD8FBA05A,

0x690CE0EE, 0x6DCDFD59, 0x608EDB80, 0x644FC637,
0x7A089632, 0x7EC98B85, 0x738AAD5C, 0x774BB0EB,
0x4F040D56, 0x4BC510E1, 0x46863638, 0x42472B8F,
0x5C007B8A, 0x58C1663D, 0x558240E4, 0x51435D53,
0x251D3B9E, 0x21DC2629, 0x2C9F00F0, 0x285E1D47,
0x36194D42, 0x32D850F5, 0x3F9B762C, 0x3B5A6B9B,
0x0315D626, 0x07D4CB91, 0x0A97ED48, 0x0E56F0FF,
0x1011A0FA, 0x14D0BD4D, 0x19939B94, 0x1D528623,
0xF12F560E, 0xF5EE4BB9, 0xF8AD6D60, 0xFC6C70D7,
0xE22B20D2, 0xE6EA3D65, 0xEBA91BBC, 0xEF68060B,
0xD727BBB6, 0xD3E6A601, 0xDEA580D8, 0xDA649D6F,
0xC423CD6A, 0xC0E2D0DD, 0xCDA1F604, 0xC960EBB3,
0xBD3E8D7E, 0xB9FF90C9, 0xB4BCB610, 0xB07DABA7,
0xAE3AFBA2, 0xAAFBE615, 0xA7B8C0CC, 0xA379DD7B,
0x9B3660C6, 0x9FF77D71, 0x92B45BA8, 0x9675461F,
0x8832161A, 0x8CF30BAD, 0x81B02D74, 0x857130C3,

0x5D8A9099, 0x594B8D2E, 0x5408ABF7, 0x50C9B640,
0x4E8EE645, 0x4A4FFBF2, 0x470CDD2B, 0x43CDC09C,
0x7B827D21, 0x7F436096, 0x7200464F, 0x76C15BF8,
0x68860BFD, 0x6C47164A, 0x61043093, 0x65C52D24,
0x119B4BE9, 0x155A565E, 0x18197087, 0x1CD86D30,
0x029F3D35, 0x065E2082, 0x0B1D065B, 0x0FDC1BEC,
0x3793A651, 0x3352BBE6, 0x3E119D3F, 0x3AD08088,
0x2497D08D, 0x2056CD3A, 0x2D15EBE3, 0x29D4F654,
0xC5A92679, 0xC1683BCE, 0xCC2B1D17, 0xC8EA00A0,
0xD6AD50A5, 0xD26C4D12, 0xDF2F6BCB, 0xDBEE767C,
0xE3A1CBC1, 0xE760D676, 0xEA23F0AF, 0xEEE2ED18,
0xF0A5BD1D, 0xF464A0AA, 0xF9278673, 0xFDE69BC4,
0x89B8FD09, 0x8D79E0BE, 0x803AC667, 0x84FBDBD0,
0x9ABC8BD5, 0x9E7D9662, 0x933EB0BB, 0x97FFAD0C,
0xAFB010B1, 0xAB710D06, 0xA6322BDF, 0xA2F33668,
0xBCB4666D, 0xB8757BDA, 0xB5365D03, 0xB1F740B4,
};

// メモリのCRC32コードを計算
extern unsigned long getMemCRC32( unsigned long crc32, unsigned const char buff[], size_t size )
{
while ( size != 0 ){
crc32 = CRC32Table[ (crc32 >> (32 - CHAR_BIT)) ^ *buff ] ^ (crc32 << CHAR_BIT);
buff++;
size--;
}
return crc32;
}

// ファイルのCRC32コードを計算
extern unsigned long getFileCRC32( const char file[] )
{
unsigned long crc32 = 0xFFFFFFFF;
char buff[ 10 * 1024 ];
size_t size;
FILE *fp;

if ( (fp = fopen(file,"rb")) != NULL ){
do {
size = fread( buff, 1, sizeof(buff), fp );
crc32 = getMemCRC32( crc32, (unsigned const char *)buff, size );
} while ( size != 0 );

fclose( fp );
}
return crc32 ^ 0xFFFFFFFF;
}

// メイン関数
int main( void )
{
char file[ 256 ];
char *find;

while ( fgets(file,sizeof(file),stdin) != NULL ){
if ( (find = strchr(file,'\n')) != NULL ){
*find = '\0';
}
printf( "0x%08lX⇒%s\n", getFileCRC32(file), file );
}
return 0;
}

試し方:
ファイル名をフルパスで入力します。
またはパイプやリダイレクションを利用して入力させます。
出力は32ビットの16進8桁とフルパス名が標準出力に表示されます。

CRCとは巡回冗長検査(じゅんかい・じょうちょう・けんさ)という誤りを検出する方法の1つです。
その他ハッシュ・キーを計算するハッシュ関数としても使うことが出来ます。

今回のCRCは32ビット幅で生成多項式に X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + 1 を利用します。
この生成多項式は CRC32 で使われているものです。

1.CRCタイプ
(1)CRCタイプ(CRC32)
(2)生成多項式(0x04C11DB7)
(3)初期値(0xFFFFFFFF)
(4)出力XOR(0xFFFFFFFF)
(5)入力ビット逆転(な...続きを読む

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

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

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

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

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

Aベストアンサー

まずは予備知識から。
----------
例えば整数を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では、この余分な(= 冗長な)ビット列をチェックすることによって、
データ転送の誤りを検出するわけです。

まずは予備知識から。
----------
例えば整数を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,……」と書いていき、
負の整数に対しても同様に延...続きを読む

Qエクセル2010で2進数の計算をするには

エクセル2010を使って2進数の乗算と加算を複数回行い、最後にそれぞれの答えをすべて加算したいのですが、こういうことは可能でしょうか。
また、最後の答えをすべて加算したときの桁数は100桁程度になると思います。
(できれば10進数をキーボードから入力すれば2進数の変換から複数回の乗算と加算などを自動で計算できれば大変ありがたいのですが)

書店で参考書を探したのですが、10進数→2進数、2進数→10進数の変換については載っているのですが、2進数の計算についてはどの本にも記述がありませんでした。

どうぞよろしくお願いします。

Aベストアンサー

2 進数では、乗法や除法も定義されます。0 x 0 = 0、0 x 1 = 0、1 x 0 = 0、1 x 1 = 1 となります。これを使うと、当たり前かもしれませんが、筆算もできます。例えば次のとおりです。

  1 0 1   =      1 x 2^2 + 0 x 2^1 + 1 x 2^0 = 5
x   1 1   =           1 x 2^1 + 1 x 2^0 = 3
―――――
  1 0 1
 1 0 1
―――――
 1 1 1 1   = 1 x 2^3 + 1 x 2^2 + 1 x 2^1 + 1 x 2^0 = 15


「整数である 2 進数」同士の計算そのものは、例えば =BIN2DEC(10)*BIN2DEC(110) といった具合にできるからいいのですが、質問文を読むと、桁数があまりにも多すぎなことが問題だと思います。

2^(100-1) = (2^100)/2
     = {(2^10)^10}/2
     = (1024^10)/2
     > (1000^10)/2
     = {(10^3)^10}/2
     = (10^30)/2
     = 5 x 10^29

となり、たとえ 10 進数で表示しても、0 が 29 個も並んだ数よりも更に大きいことになるわけだから、天文学的どころでは済まない、途方もない数だと分かります。せめて対数を取るくらいの工夫は必要でしょう。Excel の対数としては、LOG、LOG10、LN 関数が使えます。log x + log y = log xy というふうに、和から積を作れるのでしたね。

また、Excel の仕様では、誤差なく計算できる最大の桁数は 15 桁です。特に対数を取らない場合は、その点にも注意が必要です。


それから、BIN2DEC 関数は、符号を含めて 10 ビットまでの整数にしか対応できないことにも注意してください。つまり数字の部分は 9 ビットなので、-512 以上 511 以下の整数です。

小数も扱うには、(1)元の数を何倍かして小数点以下をなくす(整数化する)方法とか、(2)ユーザー定義関数その他の方法により 2 進の小数を 10 進の小数に直し、計算後に 10 から 2 に戻す方法などが考えられます。何倍かすると言っている意味は、10 進数を 10 倍すると小数点が右に一つ移動するのと同様に、2 進数では倍にすると小数点が動くという性質を使うということです。

次のページを参考にしてください。

2 進小数の求め方 http://oshiete.goo.ne.jp/qa/6756230.html
2 進小数の加法  http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1486952069

2 進数では、乗法や除法も定義されます。0 x 0 = 0、0 x 1 = 0、1 x 0 = 0、1 x 1 = 1 となります。これを使うと、当たり前かもしれませんが、筆算もできます。例えば次のとおりです。

  1 0 1   =      1 x 2^2 + 0 x 2^1 + 1 x 2^0 = 5
x   1 1   =           1 x 2^1 + 1 x 2^0 = 3
―――――
  1 0 1
 1 0 1
―――――
 1 1 1 1   = 1 x 2^3 + 1 x 2^2 + 1 x 2^1 + 1 x 2^0 = 15


「整数である 2 進数」同士の計算そのものは、例えば =BIN2DEC(10)*BIN2DEC(110) といった具合にでき...続きを読む

Q2進数の割り算が分かりません・・・。

2進数の割り算が分かりません・・・。
授業でいきなり出てきて大変に戸惑っています。
10010➗11(2進数)
の解き方を教えてください。
よろしくお願いします・・・!

Aベストアンサー

2進数の場合の割り算は引く事が出来るか?をフラグを立てていく感じになります。

QCRC計算方法

CRCの生成多項式によるmodulo2計算等については一通り調べて理解したつもりですが、実装するとなるとどうしたものかと止まってしまいます。

実装の要求が
「何バイトあるか不明なデータのCRCを計算する」
(CRC-16にて)
です。
どなたかお知恵を拝借できないものでしょうか。

Aベストアンサー

>何バイトあるか不明なデータ

何バイトであってもいいですが、上限値は決めないと実装
出来ませんね。
それとCRCはバイト単位でなくビット単位で扱います。
3ビットのデータとか49ビットのデータも許されます。

元のデータが何桁有っても余りが16ビット以下になる
までモジュロ2演算を続ければいいのです。

ただ16ビット単位で1ビットずつずらしながらモジュロ演算するので
データ配列をそのままバイトで持つか、1バイトを8バイトに
ばらすかが考えどころです。

Qエクセルで論理和などの値をセルに書きこみたい。

エクセルで数値AとBの論理和等を取ってセルに書き込みたいのですがどこかに具体的な方法が書いたサイトなどないでしょうか?真偽値が欲しいのではなく(A&B)や(AorB)の値が欲しいと言うことです。マクロは使った事がありません。よろしくお願いします。

Aベストアンサー

> マクロは使った事がありません。

経験がないという意味だけであって、使いたくない或は使うことが
禁止なのでしょうか?

※ お使いの Excel のバージョンをお書きになっていませんので
  環境によって動作するかはわかりませんが。(2000,2003で確認)

マクロ(VBA)を使うことに抵抗がないのであればメニューから
ツール → マクロ → Visual Basic Editor

Visual Basic Editor のウィンドウが出ましたら、メニューから
挿入 → 標準モジュール

標準モジュールの右側にエディタが開きますので

Function AndValue(A,B)
AndValue = Val(A) And Val(B)
End Function

と書いて、Visual Basic Editor を閉じて(最小化でも構いません)
Excel の A1 と B1 のセルに適当な数値を入れて、C1 のセルにでも
「=AndValue(A1,B1) 」と入れてみて A1 と B1 に数値を And した
数値が C1 に出たら成功です。

あとはご自身で Or とか Xor など所望の関数を定義してあげれば
よろしいかと思われます。
# 提示させて頂いた関数をコピーして関数名を変えて And の部分のを
# Or などに置き換えるだけで済むかと思います。

マクロのセキュリティ設定によっては異なりますが、マクロを含む
データを保存した場合、次回からマクロが含まれているという警告が
でます。
保存したものを開く場合セキュリティが「中」以下になっていないと
動作しません。(バージョンによっては異るかもしれません)
※ ただし「低」にしないことをお薦めします。

マクロを残したくない場合は、結果のセルをコピーして「形式を指定
して貼り付け」などで値のみを残しておけばよろしいかと思います。
マクロの削除は Visual Basic Editor で Module1 を開放します。
# Module1 という名前は異る場合もあります。

> マクロは使った事がありません。

経験がないという意味だけであって、使いたくない或は使うことが
禁止なのでしょうか?

※ お使いの Excel のバージョンをお書きになっていませんので
  環境によって動作するかはわかりませんが。(2000,2003で確認)

マクロ(VBA)を使うことに抵抗がないのであればメニューから
ツール → マクロ → Visual Basic Editor

Visual Basic Editor のウィンドウが出ましたら、メニューから
挿入 → 標準モジュール

標準モジュールの右側にエディタが開きますので

Fu...続きを読む


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

人気Q&Aランキング