CRCの計算
通信では、送信側と受信側で、伝達情報に誤りがないのかを 確認するため、CRCを使うこと多くあります。 CANで使う通信処理で、CRCを計算する必要があったので 仕組み理解に、Cのコードを作成しました。 アルゴリズムは単純で、２進数の除算を繰り返すだけ。 調べてみると、次のように単純でした。 ｎビットの除算の余りが必要なときは、（ｎ＋１）ビットの 除数で被除数の割り算を繰り返す。 ２進数での乗算、除算には、排他的論理和を使うというのは FPGAの中にデジタル回路を入れて動かす技術者には、定石と いうので、次の被除数、除数で実験してみます。 被除数 10100000000000010000000000000000000000000000000000000001 (0xA0,0x01,0x00,0x00,0x00,0x00,0x01) 除数 100011101 (0x11D) 少し調べてみると、処理は次のように単純でした。
- 被除数の最上位と除数の最上位を比較
- 被除数の最上位が１なら、除数と排他的論理和をとる
- ひとつ前で求めた値（ｎ＋１）ビット分を、被除数と入れ替える
- 被除数の最上位が０なら、一つ位を下げる
CAN LINKは、USBで使えるプロトコルアナライザー。
実験に使ったCのソースコードは、以下。
#include <stdio.h>
#define OFF 0
#define ON OFF+1
typedef unsigned char UBYTE ;
typedef unsigned short UWORD ;
UBYTE zz[9] ;
UBYTE target[64] ;
UBYTE uu[64] ;
UBYTE sflag ;
void init_array();
void show_array();
void show_target();
void show_code(UBYTE *xptr);
void add_line(UBYTE x);
int main()
{
UBYTE i ;
UBYTE j ;
UBYTE xtmp[9] ;
/* init */
init_array();
/* show */
show_array();
putchar('\n');
/* perform */
for ( i = 0 ; i < 56 ; i++ ) {
printf("counter(%3d)\n",i);
/* show */
puts("\t<input string>");
show_target();
add_line(i);
/* get target */
for ( j = 0 ; j < 9 ; j++ ) { *(xtmp+j) = *(uu+i+j) ; }
printf(" source = "); show_code( xtmp ); putchar('\n');
printf(" poliminal = "); show_code( zz ); putchar('\n');
/* exclusive or */
sflag = OFF ;
if ( *(xtmp+0) == 1 ) {
sflag = ON ;
for ( j = 0 ; j < 9 ; j++ ) { *(xtmp+j) ^= *(zz+j) ; }
}
printf(" result = "); show_code( xtmp ); putchar('\n');
if ( sflag ) { puts(" --> EXCLUSIVE OR"); }
else { puts(" --> SKIP"); }
/* return */
for ( j = 0 ; j < 9 ; j++ ) { *(uu+i+j) = *(xtmp+j) ; }
/* show */
puts("\t<output string>");
show_target();
add_line(i);
printf("\n\n");
}
/* */
return 0 ;
}
void init_array()
{
UBYTE ii;
/* set 0x11D */
*(zz+0) = 1;
*(zz+1) = 0; *(zz+2) = 0; *(zz+3) = 0; *(zz+4) = 1;
*(zz+5) = 1; *(zz+6) = 1; *(zz+7) = 0; *(zz+8) = 1;
/* set target 0xa0 0x00 0x00 0x00 0x00 0x00 0x01 0x00 */
for ( ii = 0 ; ii < 64 ; ii++ ) { *(target+ii) = 0 ; }
/* 0 0xa0 */
/* 1 0x01 */
/* 6 0x01 */
/* 0xa0 */
*(target+8*0+0) = 1 ;
*(target+8*0+2) = 1 ;
*(target+8*1+7) = 1 ;
*(target+8*6+7) = 1 ;
for ( ii = 0 ; ii < 64 ; ii++ ) { *(uu+ii) = *(target+ii) ; }
}
void show_array()
{
UBYTE ii ;
UBYTE xtmp ;
/* zz */
for ( ii = 0 ; ii < 8 ; ii++ ) {
xtmp = *(zz+ii) ;
putchar('0'+xtmp);
}
putchar('_');
putchar('0'+zz[8]);
putchar('\n');
/* target */
for ( ii = 0 ; ii < 64 ; ii++ ) {
xtmp = *(target+ii) ;
putchar('0'+xtmp);
if ( (ii % 8) == 7 && ii < 60 ) { putchar('_'); }
}
putchar('\n');
/* buffer */
for ( ii = 0 ; ii < 64 ; ii++ ) {
xtmp = *(uu+ii) ;
putchar('0'+xtmp);
if ( (ii % 8) == 7 && ii < 60 ) { putchar('_'); }
}
putchar('\n');
}
void show_target()
{
UBYTE ii ;
UBYTE xtmp ;
/* tabulation */
putchar('\t');
/* ruler */
for ( ii = 0 ; ii < 64 ; ii++ ) {
xtmp = ' ' ;
if ( (ii % 8) == 7 ) { xtmp = '*' ; }
putchar(xtmp);
}
putchar('\n');
/* tabulation */
putchar('\t');
for ( ii = 0 ; ii < 64 ; ii++ ) {
xtmp = *(uu+ii) ;
putchar('0'+xtmp);
}
putchar('\n');
}
void show_code(UBYTE *xptr)
{
UBYTE ii ;
UWORD sum ;
sum = 0 ;
for ( ii = 0 ; ii < 9 ; ii++ ) {
printf("%d",*(xptr+ii));
sum = sum * 2 + *(xptr+ii) ;
}
printf("(0x%03X)",sum);
}
void add_line(UBYTE x)
{
UBYTE j ;
putchar('\t');
for ( j = 0 ; j < x ; j++ ) { putchar(' ');}
puts("---------");
}
やっていることは、単純で被除数の中から９ビットを
取り出して、除数と排他的論理和をとるか、そのまま
にするかして、戻すのを５６回反復するだけ。
56回の反復は、被除数が７バイト＝７ｘ８＝56で
56ビットになっているため。
Ｎバイトの被除数なら８Ｎ回の反復となります。
目次 前 次