CRC-CCITTの計算法に納得いきません!
Posted: 2009年10月20日(火) 21:38
C言語の初級者が質問します。
講義の課題で、「伝送誤り検出方式として巡回符号方式(CRC:Cyclic Redundancy Check)を使用した場合、送り側でアルファベット6文字(例:nippon)の適当な単語を1文字ずつ入力した場合の検定コードを算出しなさい。生成多項式はCRC- 16-CCITT(Xの16乗)+(Xの12乗)+(Xの5乗)+1を使用し、検定コードは2byteとする。
という課題に対してネット上に以下のような模範解答がありました。
/***********************************************************
crc16.c -- CRC
***********************************************************/
#include <limits.h>
/* x^{16}+x^{12}+x^5+1 */
#define CRCPOLY1 0x8408U /* 左右逆転 */
typedef unsigned char byte;
unsigned int crc1(int n, byte c[/url])
{
unsigned int i, j, r;
r = 0xFFFFU;
for (i = 0; i < n; i++) {
r ^= c; /******************************(1)
for (j = 0; j < CHAR_BIT; j++)
if (r & 1) r = (r >> 1) ^ CRCPOLY1;
else r >>= 1;
}
return r ^ 0xFFFFU;
}
#include <stdio.h>
#include <stdlib.h>
int main()
{
static byte s[/url] = "nippon";
printf("crc1(%s) = %04X\n", s, crc1(6, s));
return 0;
} /* end */
ここで、*********(1)と記したところでは1文字目nに対しCRCを求めて、その結果をCRC初期値としてiのCRCを求め、その結果をまた次のCRC 初期値としてpの・・・・という計算をして最終的に1単語のCRCを求めていますが、理屈がよくわかりません。これはCRC計算のルールあるいは慣習と解釈すればよろしいのでしょうか?また、CRCの求め方は1通りではなく8種類ぐらいあると聞いたのですが本当ですか?
講義の課題で、「伝送誤り検出方式として巡回符号方式(CRC:Cyclic Redundancy Check)を使用した場合、送り側でアルファベット6文字(例:nippon)の適当な単語を1文字ずつ入力した場合の検定コードを算出しなさい。生成多項式はCRC- 16-CCITT(Xの16乗)+(Xの12乗)+(Xの5乗)+1を使用し、検定コードは2byteとする。
という課題に対してネット上に以下のような模範解答がありました。
/***********************************************************
crc16.c -- CRC
***********************************************************/
#include <limits.h>
/* x^{16}+x^{12}+x^5+1 */
#define CRCPOLY1 0x8408U /* 左右逆転 */
typedef unsigned char byte;
unsigned int crc1(int n, byte c[/url])
{
unsigned int i, j, r;
r = 0xFFFFU;
for (i = 0; i < n; i++) {
r ^= c; /******************************(1)
for (j = 0; j < CHAR_BIT; j++)
if (r & 1) r = (r >> 1) ^ CRCPOLY1;
else r >>= 1;
}
return r ^ 0xFFFFU;
}
#include <stdio.h>
#include <stdlib.h>
int main()
{
static byte s[/url] = "nippon";
printf("crc1(%s) = %04X\n", s, crc1(6, s));
return 0;
} /* end */
ここで、*********(1)と記したところでは1文字目nに対しCRCを求めて、その結果をCRC初期値としてiのCRCを求め、その結果をまた次のCRC 初期値としてpの・・・・という計算をして最終的に1単語のCRCを求めていますが、理屈がよくわかりません。これはCRC計算のルールあるいは慣習と解釈すればよろしいのでしょうか?また、CRCの求め方は1通りではなく8種類ぐらいあると聞いたのですが本当ですか?