CRCについて教えてください

｢b1～bp｣のビットシーケンスにＸ16 を乗じた後、生成多項式 Ｘ16＋Ｘ12＋Ｘ5＋1 で割算（モジュロ２）した剰余

このような計算をしたいのですが、X16を乗じる方法がわかりません、この後の生成多項式にかける方法はわかります。

例えばb1-bp(パリティービット)が01010101の場合にX16を乗じると結果はどのようになるでしょうか？計算方法を教えてください。

またビットシーケンスの意味もわかりません、１キャラクタのみを指すのかCRCにかける全体のキャラクタにＸ16 を乗じるのでしょうか？

よろしくお願いします。

質問者からの補足コメント

• 

  下記のようにしました。
  初期値や0x8408の値はこれで良いでしょうか？
  0x8408ここの値はいろいろあり迷います。
  
  
  unsigned short 受信箱大;
  CRC演算 = 0xffff;
  
  for (i = 0; i < 受信文字数; i++) {
  受信箱大 = 受信箱[i] * 16;
  CRC演算 ^= 受信箱大;//ビット毎の排他的OR
  for (j = 0; j < 8; j++) {
  if (CRC演算 & 1) {
  CRC演算 = (CRC演算 >> 1) ^ 0x8408;//0xA001ビット毎の排他的OR
  } else {
  CRC演算 >>= 1;
  }
  }
  }

  No.6の回答に寄せられた補足コメントです。 補足日時：2018/01/03 17:51

• 

  回答のほど、よろしくお願いいたします。
  
  for (i = 0; i < 受信文字数; i++) {
  CRC演算 ^= 受信箱[i];
  for (j = 0; j < 8; j++) {
  if (CRC演算 & 1) {
  CRC演算 = (CRC演算 >> 1) ^ 0x8408;
  } else {
  CRC演算 >>= 1;
  }
  }
  }
  
  これを実行すると、次のような結果になりました。
  上段が演算結果、下段が受信したCRCデータになります。
  
  f2f1
  8f4f
  
  5ad4
  2b5a
  
  efef
  f7f7
  
  7ec6
  637e
  
  ＞01010101 * 0x10000 = 01010101 0000 0000 0000 0000
  ＞で、24ビットになります。
  これを２バイトのCRC演算とXORをとる方法はあるでしょうか？

    補足日時：2018/01/04 20:43

• 

  度々の回答ありがとうございました、解決しました。
  
  CRC値の受信で取り込むビットの方向が逆でした、（送信業者の資料がおかしい！！！）
  やはり、”Ｘ16 を乗じた後、”これは必要がありませんでした。

  No.7の回答に寄せられた補足コメントです。 補足日時：2018/01/05 22:09

No.7 ベストアンサー 回答者： kmee 回答日時： 2018/01/04 23:17

外出先からなので、関連URLとか探すのが大変なので、キーワードを元にご自身ので資料を確認してください。

CRCには、細かい仕様の違いがあります。
◯入力されたデータを先頭から処理するのか、最後から処理するのか
その時のプログラムを、入力順番を逆にして対応するのか、多項式を上下逆にするのか
◯初期値は？
◯データ終了後の後処理は？

プログラムの結果と、実際のCRCの上下が逆になっているので、どちらかの順番が間違えているように思えます。
が、こちらでは確認取れないので、詳細な条件設定できるCRC計算サイトなどで確認してください

この回答へのお礼

お忙しいところでの回答感謝申し上げます。

＞詳細な条件設定できるCRC計算サイトなどで確認してください

これについては、幸い色々な条件でのCRC演算を試せるサイト（アプリ）がありました。
どの条件でも受信したCRC値と一致又は類似しませんでした。

ご指摘のように、受信ビットを先頭又末尾バイトから送ったり、初期値も0,-1を試したり又シフトも左右試してみましたが効果がありません。

１）受信ビットは右送りで受信箱に受けているのでCRC演算も右で良いと思いますがいかがでしょうか？
２）送信側はＸ16＋Ｘ12＋Ｘ5＋1を指定していますから、右送りですとXOR値は0x8408で良いと思います。
３）問題は最初のXOR値だと考えます・・・
”｢b1～bp｣のビットシーケンスにＸ16 を乗じた後”これが出来ていない気がしますがいかがでしょうか？

演算結果の所見として、上位下位の４ビット又は8ビットが入れ替わっていたり、シフト数が過不足だったりします。

他にお気づきの点がありましたら、お力をお貸しください。

お礼日時：2018/01/05 07:20

No.6 回答者： kmee 回答日時： 2018/01/03 12:51

>01010101の場合にX16を乗じると結果はどのようになるでしょうか？

01010101 * 0x10000 = 01010101 0000 0000 0000 0000
で、24ビットになります。
もし、元のデータが100万ビットあったら、100万+16ビットになります。

> ｢b1～bp｣のビットシーケンスにＸ16 を乗じた後、生成多項式 Ｘ16＋Ｘ12＋Ｘ5＋1 で割算（モジュロ２）した剰余

というのは、この24ビットを生成多項式で割った余り、ということになります。

ただし、CRCに関する各種資料を読むと、通常の剰余( % で求められるもの)ではないことがわかります。
ここで求められる「剰余」を一気にやってくれる演算子は、C言語には無いので、1ビットずつ筆算する要領で計算する必要があります。
ということで、実際のプログラムでは「X16を乗じる」ことなく、｢『b1～bp』のビットシーケンス」から1ビットずつ順番に取り出して計算します。
(あるいは、先に1バイト8ビット256通りのパターンを計算したテーブルを用意して、1バイトずつ計算します)

検索すれば、実際のプログラムが沢山見つかりますから、それを見た方がわかりやすいかもしれません。

この回答へのお礼

回答いただきありがとうございます。
＞実際のプログラムでは「X16を乗じる」ことなく
これはしないでとりあえずやってみます。
受信データ最後に送られてくる、CRC演算結果と符合すればそれで良しとします。

お礼日時：2018/01/03 13:40

No.5 回答者： Tacosan 回答日時： 2018/01/02 23:53

「ただiが負数の時　i = i >> 4　とやると 0 が補完されないので、工夫が必要」ってどういうことなんだろうか.

「負数」を負数として扱わないとダメなの?

この回答へのお礼

返事が遅くなり申し訳ありません。

解説いただいたロジカルシフトの場合は右シフトも「空いた左側には0を補完する」とのことでしたが、i = i >> 4の場合には0が入らなくて負数ビットの1が残ったままになります。これをシフト後に0に入れ替える必要がありますよね。

NO.4で回答いただいた、
＞データを保存して全ビット列を蓄えてから
私は、受信した1,0のビット波形を解析して１キャラクタ毎にchar変数に蓄えています。
全ての文字をこの変数に受信したら、この配列変数を計算に反映させる方法がわかりません、よろしくお願いします。

お礼日時：2018/01/03 06:56

No.4 回答者： t_fumiaki 回答日時： 2018/01/02 19:33

>>８ビットの変数配列で受信しているため

データ送受信では関係なし。
8ビットしか無いなら、データを保存して全ビット列を蓄えてから、計算する。

ロジカルシフトとは、0を補完するシフト。
110を右へ4ビットロジカルシフト=0000110
110を左へ4ビットロジカルシフト=1100000

この回答へのお礼

ありがとうございます。助かります！
ロジカルシフトについては理解できました。ただiが負数の時　i = i >> 4　とやると 0 が補完されないので、工夫が必要ですね・・・

＞データを保存して全ビット列を蓄えてから
私は、１キャラクタ毎にchar変数に蓄えています。
全ての文字をこの変数に受信したら、このデータを計算に反映させる方法がわかりません、よろしかったらもう少しお力をお貸しください。

お礼日時：2018/01/02 20:48

No.3 回答者： t_fumiaki 回答日時： 2018/01/02 16:39

>>変数が８ビットなので左シフトを４回すると上位４ビットは無くなってしまいますが

CRCが解って無いね！

送信ビット列は、1万ビットだろうが100万ビットだろうが関係ない。
生成多項式の最上位を掛け算（つまり、送信ビット列をロジカルに左シフトする）したビット列に、多項式で割った余りを左シフトした右の0に足し算するんだ。

受取った方は、多項式で割った商を送られたデータをし、余りが0なた正常と判断する訳。

生成多項式の最上位がX³²であっても、100万ビットだって来る事が出来る。

この回答へのお礼

再度の回答感謝します。

>CRCが解って無いね！
はい！CRCを知ってからまだ2,3日しかたっていなくて全く困っています！！

＞（つまり、送信ビット列をロジカルに左シフトする）
送信ビット列のことですが８ビットの変数配列で受信しているためこの配列をシフトすると下位４ビットのデータが単に上位に移行して上位のビットデータが消えることになります。
ロジカルの意味を教えてください。

よろしくお願いします。

お礼日時：2018/01/02 17:03

No.2 回答者： t_fumiaki 回答日時： 2018/01/02 14:41

>>X16を乗じる

16ビット左にロジカルシフトするだけ。

この回答へのお礼

早速の回答ありがとうございました。
CRC対象の変数が８ビットなので左シフトを４回すると上位４ビットは無くなってしまいますが、元のデータを１６ビットに伸張する必要はないでしょうか？

お礼日時：2018/01/02 15:08

No.1 回答者： t_fumiaki 回答日時： 2018/01/02 14:39

>>01010101の場合にX16を乗じると結果はどのようになるでしょうか？

普通に多項式を計算するだけです。

(0･x⁷+1･x⁶+0･x⁵+1･x⁴+0･x³+1･x²+0･x¹+1･x⁰)･x¹⁶

=(x⁶+x⁴+x²+x⁰)･x¹⁶

=x²²+x²⁰+x¹⁸+x¹⁶

ビット列で表現すれば
10101010000000000000000

この回答へのお礼

多項式は難解でわからないのですが、NO.２の回答だと明快ですがやはり入れ物を伸張する必要がありそうです。
＞10101010000000000000000
これは23ビットとすこし大きいと思いますが、多項式で計算するとこのビット数になるでしょうか、16ビットに伸張ではダメでしょうか？

お礼日時：2018/01/02 15:07