CRCの生成回路

[←]　[↑]　[→]

---

CRCの生成回路を素直に考えると、メッセージをシフトインしていってMSB=1のときg[n:0]を引くという除算回路になる。

しかし本に書いてあるCRCの生成回路はこれとは少し異なっている。なぜこの回路でCRCが計算できるのだろうか。

◇

例で確かめてみると、この回路でも途中は異なるものの最終結果はあっているし、素朴な除算回路では最初のビットがd[n-1]に到達するまでnクロック余計にかかったのに対して、この回路では余計なクロックが必要ない。

例) g[3:0]=1101, msg[4:0]=10011

素朴な除算回路	本に書いてある回路
d[2:0]←{msg[4:0],000} _-----____------------------ _000____10011000 _001____0011000 _010____011000 _100____11000 _100____1000 _100____000 _101____00 _111____0 _011	d[2:0]←msg[4:0] _-----____------------- _000____10011 _101____0011 _111____011 _011____11 _011____1 _011

◇◇

一般の本では除算回路にxⁿの乗算を組み合わせた回路と説明しているが、次のように「あるメッセージのCRCが既に計算されていて、このメッセージに1ビットを付け加えたときのCRCを計算する」と考えた方がわかりやすい。

今、あるメッセージmsg[ ]のCRCをcrc[n-1:0]とおくと

  crc[n-1:0] = {msg[ ],0…0} mod g[n:0]  (0…0はnビットのゼロ)

このメッセージに1ビットdinを付け加えた{msg[ ],din}のCRCは

  {msg[ ],din,0…0} mod g[n:0]

  = {msg[ ],0,0…0} mod g[n:0] + {din,0…0} mod g[n:0]

  = {crc[n-1:0],0} mod g[n:0] + {din,0…0} mod g[n:0]

  = {crc[n-2:0],0} + (crc[n-1])? g[n-1:0]:0 + (din)? g[n-1:0]:0  (最上位ビットg[n]は計算不要)

  = {crc[n-2:0],0} + (crc[n-1]+din)? g[n-1:0]:0

と上記の回路になる。ここで + はGF(2ⁿ)の加算(XOR)である。

初期値は、オールゼロのmsg[ ] に対応するCRC=0…0から始めればよい。

◇◇◇

実際に通信規格で使われているCRCは定義どおりではなく次のように加工されているようである。

項目	定義どおり	加工あり
レジスタ初期値	0･･･0	1･･･1
シフト入力順	バイト毎にMSBから	バイト毎にLSBから
結果の左右ビット反転	そのままcrc[n-1:0]	左右ビット反転crc[0:n-1]
結果の01反転	そのままcrc	01反転 ~crc

このような加工をして誤り検出に影響しないのか気になるが、ビット順の並べ替えや01反転は明らかに影響なさそうであり、

レジスタ初期値はその時点でのCRC値であるから、そのCRC値に対応するメッセージが本来のメッセージの前に付け加わったのと等価であり、この付加メッセージを除いて考えればやはり影響ない。

なお、初期値をゼロ以外にする理由は、オールゼロのメッセージのCRCはオールゼロなので、シリアル通信で0固定の故障が検出されないのを防ぐためと思われる。オール1のメッセージのCRCはオール1ではないので1固定の故障は検出される。

(例1) HDLC

・生成多項式 CRC-16-CCITT　g(x) = x¹⁶+x¹²+x⁵+1　g[16:0]=11021

・初期値 crc[15:0]=ffff

・シフト入力順はバイト毎にLSBから

・結果を左右ビット反転する

・結果を01反転する

例で計算してみると、メッセージにCRCを付加したコードのCRCは~crc[0:15]=0f47になる。

メッセージ	CRC
msg[7:0] ="A"=41	~crc[0:15]=a3f5
msg[23:0]={"A",f5a3}=41f5a3	~crc[0:15]=0f47
msg[71:0]="123456789"       =313233343536373839	~crc[0:15]=906e
msg[87:0]={"123456789",6e90}       =3132333435363738396e90	~crc[0:15]=0f47

ちなみに定義どおりだと、メッセージにCRCを付加したコードのCRCはゼロになる。

メッセージ	CRC
msg[7:0] ="A"=41	crc[15:0]=58e5
msg[23:0]={"A",58e5}=4158e5	crc[15:0]=0000
msg[71:0]="123456789"       =313233343536373839	crc[15:0]=31c3
msg[87:0]={"123456789",31c3}       =31323334353637383931c3	crc[15:0]=0000

(例2) IEEE802.3 Ethernet

・生成多項式 CRC-32 g(x) = x³²+x²⁶+x²³+x²²+x¹⁶+x¹²+x¹¹+x¹⁰+x⁸+x⁷+x⁵+x⁴+x²+x+1  g[32:0]=104c11db7

・初期値 crc[31:0]=ffffffff

・シフト入力順はバイト毎にLSBから

・結果を左右ビット反転する

・結果を01反転する

例で計算してみると、メッセージにCRCを付加したコードのCRCは~crc[0:31]=2144df1cになる。

メッセージ	CRC
msg[7:0] ="A"=41	~crc[0:31]=d3d99e8b
msg[39:0]={"A",8b9e}=418b9ed9d3	~crc[0:31]=2144df1c
msg[71:0]="123456789"       =313233343536373839	~crc[0:31]=cbf43926
msg[103:0]={"123456789",2639f4cb}       =3132333435363738392639f4cb	~crc[0:31]=2144df1c

計算に使ったCコードは次のとおりで、VivadoHLSの固定小数点テンプレートap_int.hを使っている。

/* crc.cpp */

#include <ap_int.h>

using namespace std;

const int N = 16;           // CRCビット幅

typedef ap_uint<N> crc_t;   // CRCデータ型

const crc_t INIT = 0xffff;  // CRC初期値

const crc_t POLY = 0x1021;  // x16+x12+x5+x0 (X16は省略)

const bool LSB_FIRST = true;       // バイト毎にLSB firstで入力

typedef ap_uint<8> dat_t;   // バイト型

const int L = 20;           // 入力する最大バイト数

/**********************************************************

 * サブルーチン - バイト毎に入力してCRC計算する

 *********************************************************/

int calc_crc

    (crc_t *crc       // (o) CRC

    ,dat_t dat[L]     // (i) 入力バイト

    ,int len          // (i) 入力バイト数

    ) {

    crc_t crc_tmp = INIT;

    bool din;

    for(int k=0; k<len; k++) {

        for(int j=0; j<=7; j++) {

            din = (LSB_FIRST)? dat[k][j] : dat[k][7-j];

            if(crc_tmp[N-1] ^ din)

                crc_tmp = (crc_tmp << 1) ^ POLY;

            else

                crc_tmp = (crc_tmp << 1);

        }

        *crc = crc_tmp;

    }

}

/**********************************************************

 * サブルーチン - CRC計算結果を表示する

 *********************************************************/

int disp_crc

    (crc_t crc

    ,dat_t dat[L]

    ,int len

    ) {

    crc_t crc_rev;

    crc_t crc_inv;

    crc_t crc_rev_inv;

    for(int k=0; k<len; k++)

            printf("-- dat[%0d] = %02x\n",k,(int)dat[k]);

    printf("--  crc = %x\n",(int) crc);

    crc_inv = ~crc;

    printf("-- ~crc = %x\n",(int) crc_inv);

    for(int j=0; j<=N-1; j++) crc_rev[j] = crc[N-1-j];

    printf("--  crc = %x bit reversed\n",(int) crc_rev);

    crc_rev_inv = ~crc_rev;

    printf("-- ~crc = %x bit reversed\n",(int) crc_rev_inv);

    printf("\n");

}

/**********************************************************

 * メインルーチン - バイト列dat[len]についてCRCを求める

 **********************************************************/

int main(int argc, char *argv[]) {

    dat_t dat[L];

    crc_t crc;

    int   len;

    len = 1;

    dat[0] ='A';

    calc_crc(&crc,dat,len);

    disp_crc( crc,dat,len);

    len = 3;

    dat[0] ='A';

    dat[1] =0xf5;

    dat[2] =0xa3;

    calc_crc(&crc,dat,len);

    disp_crc( crc,dat,len);

    len = 9;

    sscanf("123456789","%s",dat);

    calc_crc(&crc,dat,len);

    disp_crc( crc,dat,len);

    len = 11;

    sscanf("123456789","%s",dat);

    dat[9] =0x6e;

    dat[10]=0x90;

    calc_crc(&crc,dat,len);

    disp_crc( crc,dat,len);

    return 0;

}

---

[←]　[↑]　[→]