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

組み込みアルゴリズム 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

  1.  //CRC-8/ITUに基づく
  2. 符号なし文字CRC8(符号なし文字*データ、符号なし整数長さ)
  3.  {
  4.     符号なしchar i;
  5.     unsigned char poly = 0x07; // 表の Poly 列に対応します
  6.     unsigned char init = 0x00; // テーブルのInit列に対応します
  7.  
  8.     符号なしchar wChar = 0; 
  9.  
  10.     (長さ--)の間 
  11.     {
  12.         wChar = *(データ++); 
  13.  
  14.         //RefIn がTRUEの場合は実行し、 FALSEの場合は削除します
  15.         //InvertUint8(&wChar,&wChar); 
  16.  
  17.         初期化 ^= wChar;
  18.  (i = 0;i < 8;i++)の場合
  19.         {
  20.             if(init & 0x80)
  21.             {
  22.                 初期化 = (初期化 << 1) ^ ポリ;
  23.             }
  24. それ以外 
  25.             {
  26.                 初期化 = 初期化 << 1;
  27.             }
  28.         }
  29.     } 
  30.  
  31.     //RefOutがTRUEの場合は実行し、 FALSEの場合は削除します
  32.     //InvertUint8(&init,&init); 
  33.  
  34.     //XorOut との XOR。0 の場合は、実行してもしなくても違いはありません。
  35.     初期化=初期化^0x55; 
  36.  
  37. 戻り値(init); 
  38.  
  39.  }

CRC16

  1.  //CRC-16/X-25を参照として使用
  2. 符号なしショートCRC16(符号なし文字*データ、符号なし整数長さ)
  3.  {
  4.     符号なしchar i;
  5.     unsigned short poly = 0x1021; // 表のPoly列に対応します
  6.     unsigned short init = 0xFFFF; // 表のInit列に対応します
  7.     符号なしchar wChar = 0; 
  8.  
  9.     (長さ--)の間 
  10.     {
  11.         wChar = *(データ++); 
  12.  
  13.         //RefIn がTRUEの場合は実行し、 FALSEの場合は削除します
  14.         InvertUint8(&wChar,&wChar); 
  15.  
  16.         初期化^=(wChar << 8);
  17.  (i = 0;i < 8;i++)の場合
  18.         {
  19.             初期化と0x8000の場合
  20.             {
  21.                 初期化 = (初期化 << 1) ^ ポリ;
  22.             }
  23. それ以外 
  24.             {
  25.                 初期化 = 初期化 << 1;
  26.             }
  27.         }
  28.     } 
  29.  
  30.     //RefOutがTRUEの場合は実行し、 FALSEの場合は削除します
  31.     InvertUint16(&init,&init); 
  32.  
  33.     //XorOut との XOR。0 の場合は、実行してもしなくても違いはありません。
  34.     初期化=初期化^0xFFFF; 
  35.  
  36. 戻り値(init);
  37.  }

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

  1.  void InvertUint8(符号なしchar *DesBuf、符号なしchar *SrcBuf)
  2.  {
  3. 整数i;
  4.     符号なし文字 温度= 0; 
  5.  
  6.  (i = 0; i < 8; i++)の場合
  7.     {
  8.         SrcBuf[0] & (1 << i) の場合
  9.         {
  10. 温度|= 1 << (7 - i);
  11.         }
  12.     }
  13.     *DesBuf =一時;
  14.  } 
  15.  
  16.  void InvertUint16(符号なしショート *DesBuf、符号なしショート *SrcBuf)
  17.  {
  18. 整数i;
  19.     符号なしショートtemp = 0; 
  20.  
  21.  (i = 0; i < 16; i++)の場合
  22.     {
  23.         SrcBuf[0] & (1 << i) の場合
  24.         {
  25. 温度|= 1 << (15 - i);
  26.         }
  27.     }
  28.     *DesBuf =一時;
  29.  }

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

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

  1.  // CRC-8/ITUを例に、配列ルックアップテーブルを生成します
  2. テーブルを作成します。
  3.  {
  4.     符号なしchar i、初期化;
  5.     符号なしショート j;
  6.  (j=0;j<=255;j++)の場合
  7.     {
  8.         j%16==0の場合
  9.         {
  10.             printf( "\r\n" );
  11.         } 
  12.  
  13.         初期化 = j;
  14.  (i = 0;i < 8;i++)の場合
  15.         {
  16.             if(init & 0x80)
  17.             {
  18.                 init = (init << 1) ^ 0x07; //実際のポリゴンに従います。
  19.             }
  20. それ以外 
  21.             {
  22.                 初期化 = 初期化 << 1;
  23.             }
  24.         }
  25.         printf( "0x%02X," , 初期化);
  26.     }
  27.  }

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

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

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

  1.  //CRC-8/ITUに基づく
  2. 符号なし文字CRC8(符号なし文字*データ、符号なし整数長さ)
  3.  {
  4.     符号なしchar i;
  5.     unsigned char poly = 0x07; // 表の Poly 列に対応します
  6.     unsigned char init = 0x00; // テーブルのInit列に対応します
  7.  
  8.     符号なしchar wChar = 0; 
  9.  
  10.     (長さ--)の間 
  11.     {
  12.         wChar = *(データ++); 
  13.  
  14.         //RefIn がTRUEの場合は実行し、 FALSEの場合は削除します
  15.         //InvertUint8(&wChar,&wChar); 
  16.  
  17.         初期化 ^= wChar; 
  18.  
  19.  /********************************************************************/
  20.  #1の場合
  21.  
  22.         init=crcTable[init]; //テーブルを検索し、空間を時間と交換する
  23. ＃それ以外 
  24.  (i = 0;i < 8;i++)の場合
  25.         {
  26.             if(init & 0x80)
  27.             {
  28.                 初期化 = (初期化 << 1) ^ ポリ;
  29.             }
  30. それ以外 
  31.             {
  32.                 初期化 = 初期化 << 1;
  33.             }
  34.         }
  35.  #終了
  36. /********************************************************************/
  37.     } 
  38.  
  39.     //RefOutがTRUEの場合は実行し、 FALSEの場合は削除します
  40.     //InvertUint8(&init,&init); 
  41.  
  42.     //XorOut との XOR。0 の場合は、実行してもしなくても違いはありません。
  43.     初期化=初期化^0x55; 
  44.  
  45. 戻り値(init);
  46.  }

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

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

<<:  独学で機械学習エンジニアを目指す人のための 10 の戒律

>>:  無人バスは無人タクシーよりも信頼性が高いでしょうか?

ブログ    
ブログ    

推薦する

OpenAI、リーダーシップ争いの末に新事業GPTストアを立ち上げ

ChatGPT Team は OpenAI の Enterprise Edition 製品の小型版で...

インダストリー4.0: AIを活用した障害検出

[[359728]] AI の向上とマシン ビジョン制御の向上を組み合わせることで、スマート製造業界...

OpenAI、開発者向けGPTチャットボットAPIのメジャーアップデートを発表、価格を値下げ

6月14日、OpenAIは大規模言語モデルAPI（GPT-4およびgpt-3.5-turboを含む）...

機械学習は、インダストリー4.0の不安定性、不確実性、複雑性、曖昧性に対処する

序文科学技術の急速な発展により、インダストリアル4.0時代は終焉を迎えつつありますが、実際の発展には...

Zookeeper の選出アルゴリズムとスプリットブレイン問題の詳細な説明

ZKの紹介ZK = 動物園の飼育係ZK は、マイクロサービス ソリューションにおけるサービス登録と検...

...

人間支援型人工知能の6つの利点

人工知能は最近話題になっていますが、現実には人間のように考えることができるコンピューターの実現にはま...

職場でロボットが増えると、雇用に影響が出るでしょうか?

最近、中国労働・社会保障科学院の莫容研究チームが発表した研究結果によると、わが国における人工知能の雇...

AIのトップ研究者からのアドバイス：あなたもAIに取り組んでいると聞きましたが、この4つの落とし穴にはまらないように！

人工知能の人気が高まってきており、人工知能分野でビジネスを始めたい人も増えてきています。しかし、人工...

0 個のプロンプトワードと 1 枚の写真でビデオを生成する Gen-2 の新しいゲームプレイが画面を席巻します。ウェブ版は無料でプレイ可能

この記事はAI新メディアQuantum Bit（公開アカウントID：QbitAI）より許可を得て転載...

...

ビッグモデルの「錯覚」、この記事を読んでください

ビッグモデルの「幻想」がついに体系的にレビューされました！ 49 ページの記事では、幻覚の定義、分類...

人工知能は科学研究に革命を起こす力を持っている

人工知能 (AI) は、コンピューター サイエンス、数学、心理学、言語学などの分野が関わる学際的な分...

メジャーアップデート！ OpenAIがChatGPTエンタープライズ版をリリース、さまざまな業界向けにカスタマイズ可能なAI

人工知能研究企業OpenAIは8月29日、ChatGPTのメジャーアップグレードとなるChatGPT...

スマート物流の1兆ドル規模の扉が開かれ、物流ロボットがトレンドの先端に立っている

近年、インターネットの急速な発展、電子商取引の加速的な台頭、さまざまな新しいビジネスモデルの急速な実...