組み込みアルゴリズム CRCチェックアルゴリズム

[[350334]]

データ伝送中にエラーが発生することは避けられません。データを受信した後、受信側はまずデータの正確性を検証し、異常なデータを特別に処理します。チェックする方法は多数ありますが、最も一般的なのは CRC 巡回冗長検査です。 CRC アルゴリズムは強力なエラー検出能力と高い効率性を備えており、情報通信分野で最も一般的な検証方法です。 CRC チェックサム アルゴリズムは広く使用されており、実装も簡単ですが、その背後にあるエラー訂正コードの代数理論は、一般の人が理解できるものではありません。したがって、巡回検証の原理を理解せずにアルゴリズムフローを分析するのは賢明ではありません。ソースコードに基づいて実装プロセスを逆にしたとしても、なぜこのように実行されるのか理解できません。一般的に、人々はCRCをアプリケーションの観点から注目し、同じCRC16アルゴリズムであるにもかかわらず、なぜ得られる結果が異なるのかを考えます。この記事はまさにそれを目的としています。

1. CRCの定義

996 という数字を送信するとします。これを 7 で割ると余りが 2 になります。送信するときは、996 から 2 を引いて送信します。受信側は同じ計算を使用して、データ パケットが正しいかどうかを判断します。同じソース データでも、除数が異なると余りが異なります。 CRC アルゴリズムも同様の原理に基づいています。

CRC アルゴリズムのパラメータは次のように説明されます。

1. 除算は2を法として定義されます

2. 除数は、x^16+x^12+x^5+1(0x1021) 2^16+2^12+2^5+2^0=65536+4096+32+1= 69665=0x11021 などの多項式に設定されます。言い表せない規格によれば、多項式の最上位ビットと最下位ビットは 1 でなければならないため、通常は最上位ビットを無視して 0x1021 に簡略化され、Poly として記録されます。

3. 多項式の長さが異なるため、一般的には CRC8、CRC16、CRC32 に分類されます。モジュロ 2 除算は XOR とシフト演算に簡略化されるため、初期値は Init です。

4. さらに3つのパラメータがあります

RefIn: テストするデータの各バイトがビット反転されているかどうか (TRUE または FALSE)。

RefOut: 計算後、XOR 出力前に、データ全体がビット反転されているかどうか (TRUE または FALSE)。

XorOut: 計算結果とこのパラメータを XOR して、最終的な CRC 値を取得します。ただし、0 と XOR された数値は数値自体となるため、値が 0 の場合は無視できます。

5. 多項式や初期値などの違いにより、CRC にはさまざまなバージョンがあります。理論的には、多項式は任意に定義できますが、異なるデータに対して計算される CRC 値が可能な限り異なるようにするために、普遍的な標準多項式が数学的に導出されます。

6. https://crccalc.com/ の定義を参照してください。シナリオによって異なる多項式が使用されます。

2. CRCアルゴリズムとテンプレート

CRC アルゴリズムの一般的なバージョンは次のとおりです。

CRC8

 //CRC-8/ITUに基づく
符号なし文字CRC8(符号なし文字*データ、符号なし整数長さ)
 {
    符号なしchar i;
    unsigned char poly = 0x07; // 表の Poly 列に対応します
    unsigned char init = 0x00; // テーブルのInit列に対応します
 
    符号なしchar wChar = 0; 
 
    (長さ--)の間 
    {
        wChar = *(データ++); 
 
        //RefIn がTRUEの場合は実行し、 FALSEの場合は削除します
        //InvertUint8(&wChar,&wChar); 
 
        初期化 ^= wChar;
 (i = 0;i < 8;i++)の場合
        {
            if(init & 0x80)
            {
                初期化 = (初期化 << 1) ^ ポリ;
            }
それ以外 
            {
                初期化 = 初期化 << 1;
            }
        }
    } 
 
    //RefOutがTRUEの場合は実行し、 FALSEの場合は削除します
    //InvertUint8(&init,&init); 
 
    //XorOut との XOR。0 の場合は、実行してもしなくても違いはありません。
    初期化=初期化^0x55; 
 
戻り値(init); 
 
 }

CRC16

 //CRC-16/X-25を参照として使用
符号なしショートCRC16(符号なし文字*データ、符号なし整数長さ)
 {
    符号なしchar i;
    unsigned short poly = 0x1021; // 表のPoly列に対応します
    unsigned short init = 0xFFFF; // 表のInit列に対応します
    符号なしchar wChar = 0; 
 
    (長さ--)の間 
    {
        wChar = *(データ++); 
 
        //RefIn がTRUEの場合は実行し、 FALSEの場合は削除します
        InvertUint8(&wChar,&wChar); 
 
        初期化^=(wChar << 8);
 (i = 0;i < 8;i++)の場合
        {
            初期化と0x8000の場合
            {
                初期化 = (初期化 << 1) ^ ポリ;
            }
それ以外 
            {
                初期化 = 初期化 << 1;
            }
        }
    } 
 
    //RefOutがTRUEの場合は実行し、 FALSEの場合は削除します
    InvertUint16(&init,&init); 
 
    //XorOut との XOR。0 の場合は、実行してもしなくても違いはありません。
    初期化=初期化^0xFFFF; 
 
戻り値(init);
 }

CRC8 および CRC16 の場合、異なるバージョンのパラメータの違いに応じて、表を参照してテンプレート内のパラメータを対応する値に変更すると、対応するバージョンの CRC 値を取得できます。データの逆転に関係するコードは次のとおりです。

 void InvertUint8(符号なしchar *DesBuf、符号なしchar *SrcBuf)
 {
整数i;
    符号なし文字 温度= 0; 
 
 (i = 0; i < 8; i++)の場合
    {
        SrcBuf[0] & (1 << i) の場合
        {
温度|= 1 << (7 - i);
        }
    }
    *DesBuf =一時;
 } 
 
 void InvertUint16(符号なしショート *DesBuf、符号なしショート *SrcBuf)
 {
整数i;
    符号なしショートtemp = 0; 
 
 (i = 0; i < 16; i++)の場合
    {
        SrcBuf[0] & (1 << i) の場合
        {
温度|= 1 << (15 - i);
        }
    }
    *DesBuf =一時;
 }

3. ルックアップテーブル

上記のコードでは、CRC シフト XOR 演算のループ本体を解きます。時間要件が高いシナリオでは、事前に値テーブルを計算して生成し、スペースと時間を交換することができます。

 // CRC-8/ITUを例に、配列ルックアップテーブルを生成します
テーブルを作成します。
 {
    符号なしchar i、初期化;
    符号なしショート j;
 (j=0;j<=255;j++)の場合
    {
        j%16==0の場合
        {
            printf( "\r\n" );
        } 
 
        初期化 = j;
 (i = 0;i < 8;i++)の場合
        {
            if(init & 0x80)
            {
                init = (init << 1) ^ 0x07; //実際のポリゴンに従います。
            }
それ以外 
            {
                初期化 = 初期化 << 1;
            }
        }
        printf( "0x%02X," , 初期化);
    }
 }

poly を決定した後、init が 0 ～ 255 であると仮定して、256 個のパラメータを見つけて 1 次元配列に変換します。上記のように、CRC-8/ITU を例にとると、生成される配列は次のようになります。

符号なしchar crcTable[]={
 0x00、0x07、0x0E、0x09、0x1C、0x1B、0x12、0x15、0x38、0x3F、0x36、0x31、0x24、0x23、0x2A、0x2D、
 0x70,0x77,0x7E,0x79,0x6C,0x6B,0x62,0x65,0x48,0x4F,0x46,0x41,0x54,0x53,0x5A,0x5D、
 0xE0、0xE7、0xEE、0xE9、0xFC、0xFB、0xF2、0xF5、0xD8、0xDF、0xD6、0xD1、0xC4、0xC3、0xCA、0xCD、
 0x90,0x97,0x9E,0x99,0x8C,0x8B,0x82,0x85,0xA8,0xAF,0xA6,0xA1,0xB4,0xB3,0xBA,0xBD、
 0xC7、0xC0、0xC9、0xCE、0xDB、0xDC、0xD5、0xD2、0xFF、0xF8、0xF1、0xF6、0xE3、0xE4、0xED、0xEA、
 0xB7、0xB0、0xB9、0xBE、0xAB、0xAC、0xA5、0xA2、0x8F、0x88、0x81、0x86、0x93、0x94、0x9D、0x9A、
 0x27,0x20,0x29,0x2E,0x3B,0x3C,0x35,0x32,0x1F,0x18,0x11,0x16,0x03,0x04,0x0D,0x0A,
 0x57,0x50,0x59,0x5E,0x4B,0x4C,0x45,0x42,0x6F,0x68,0x61,0x66,0x73,0x74,0x7D,0x7A,
 0x89,0x8E,0x87,0x80,0x95,0x92,0x9B,0x9C,0xB1,0xB6,0xBF,0xB8,0xAD,0xAA,0xA3,0xA4,
 0xF9、0xFE、0xF7、0xF0、0xE5、0xE2、0xEB、0xEC、0xC1、0xC6、0xCF、0xC8、0xDD、0xDA、0xD3、0xD4、
 0x69,0x6E,0x67,0x60,0x75,0x72,0x7B,0x7C,0x51,0x56,0x5F,0x58,0x4D,0x4A,0x43,0x44,
 0x19,0x1E,0x17,0x10,0x05,0x02,0x0B,0x0C,0x21,0x26,0x2F,0x28,0x3D,0x3A,0x33,0x34,
 0x4E、0x49、0x40、0x47、0x52、0x55、0x5C、0x5B、0x76、0x71、0x78、0x7F、0x6A、0x6D、0x64、0x63、
 0x3E、0x39、0x30、0x37、0x22、0x25、0x2C、0x2B、0x06、0x01、0x08、0x0F、0x1A、0x1D、0x14、0x13、
 0xAE、0xA9、0xA0、0xA7、0xB2、0xB5、0xBC、0xBB、0x96、0x91、0x98、0x9F、0x8A、0x8D、0x84、0x83、
 0xDE、0xD9、0xD0、0xD7、0xC2、0xC5、0xCC、0xCB、0xE6、0xE1、0xE8、0xEF、0xFA、0xFD、0xF4、0xF3、 };

元の直接計算は、次のようにテーブル参照に変更されます。

 //CRC-8/ITUに基づく
符号なし文字CRC8(符号なし文字*データ、符号なし整数長さ)
 {
    符号なしchar i;
    unsigned char poly = 0x07; // 表の Poly 列に対応します
    unsigned char init = 0x00; // テーブルのInit列に対応します
 
    符号なしchar wChar = 0; 
 
    (長さ--)の間 
    {
        wChar = *(データ++); 
 
        //RefIn がTRUEの場合は実行し、 FALSEの場合は削除します
        //InvertUint8(&wChar,&wChar); 
 
        初期化 ^= wChar; 
 
 /********************************************************************/
 #1の場合
 
        init=crcTable[init]; //テーブルを検索し、空間を時間と交換する
＃それ以外 
 (i = 0;i < 8;i++)の場合
        {
            if(init & 0x80)
            {
                初期化 = (初期化 << 1) ^ ポリ;
            }
それ以外 
            {
                初期化 = 初期化 << 1;
            }
        }
 #終了
/********************************************************************/
    } 
 
    //RefOutがTRUEの場合は実行し、 FALSEの場合は削除します
    //InvertUint8(&init,&init); 
 
    //XorOut との XOR。0 の場合は、実行してもしなくても違いはありません。
    初期化=初期化^0x55; 
 
戻り値(init);
 }

CRC16 にはテーブル検索方式も使用できます。

この記事はWeChatのパブリックアカウント「Embedded Systems」から転載したものです。以下のQRコードからフォローできます。この記事を転載する場合は、Embedded System パブリック アカウントにお問い合わせください。