サイクル冗長検査符号化(CRC検査)

5276 ワード

コンピュータデータ通信では,干渉など様々な内外要因により,データの誤りが避けられないため,データ通信ではデータの誤り検出が必要である.エラー検出を実現する基本原理は、送信側が送信データに基づいていくつかの符号化を生産し、その後、検査符号化をデータの後ろに付加して一緒に送信し、受信側はデータと検査符号を受信した後、検査符号でデータを検査し、伝送されたデータが正しいかどうかを確認することである.エラー検出技術の核心は検証符号化であり、よく使われる検証にはパリティ、恒比較検証と循環冗長検証符号化の3種類がある.ここでは主にサイクル冗長検査符号化について説明する.
1.パリティ:送信するフォーマットメッセージ中の数字「1」のシンボル個数を統計し、パリティを採用する場合、1つのシンボルを追加してメッセージ中の「1」を奇数(パリティ)または偶数(パリティ)とし、受信時にメッセージ中の「1」のシンボル数がパリティの規定に合わないことを発見した場合、データエラーを判定する.パリティには一定の欠陥がある:エラーシンボルの個数が奇数の場合に有効であり、偶数であればパリティは検出できない.ISOは、同期伝送システムにおいて、奇数検査を採用し、非同期伝送システムにおいて、偶数検査を採用することを規定している.
2.定比符号:通信時には、原符号伝送ではなく、送信されたデータを符号化して符号化した後のバイト毎に、国内電報通信に用いられる「1」と「0」の個数の比を一定に保つ定比符号.一定比符号誤り訂正能力はパリティよりやや強く、符号群に奇数個の数の誤りが発生した場合、「0」と「1」の一定比関係を破壊して検出することができ、偶数個の数の誤りが発生した場合、非置換型の2つのシンボル誤り、すなわち2つの「0」がすべて「1」に誤り、あるいは逆に検出することができるが、置換型の誤り、すなわちある位置の「1」が「0」に誤り、一方、別の位置の「0」エラーは「1」であり、定数コードは検出できない.
3.サイクル冗長検査コード:CRCコードと略称し、CRC検査コードは高性能の検査ミスコードであり、検査ミス能力が強く、簡単で容易で、良好な代数構造を実現するなどの特徴があり、例えばパリティ検査と一定比コードで検出できない置換型エラーであり、CRC検査はよく検出できる.
線形符号と循環符号:k個の情報シンボルとr個の検査シンボルからなる線形符号群があり、そのうち各検査シンボルは当該符号群の一部の情報シンボルのモード2除算(各データビット、除数と論理的異論的または演算)であり、この構造フォーマットを有する符号群は線形符号である.線形符号については、いずれかの符号群のサイクルごとに右シフトまたは左シフトする性質を有するが、得られた新しい符号群は依然として符号のうちの1符号群であり、このようなサイクルシフト不変性を有する線形符号をサイクル符号と呼ぶ.
サイクルコードの代数的検討を容易にするために、コード群の各シンボルは、コード群C=(Cn−1,Cn−2,Cn−3....C 1,C 0,)に対応する多項式として、C(X)=C(X)=Cn−1+Cn−2+…+C 1+C 0と表現される多項式である
 
CRC-16  g(X)=+++1
CRC-CITT g(X)=+++1
上記の3つの多項式はすでに国際標準となっており、このうち、CRC-12は6ビット文字同期システムに用いられ、長さが12以内のバーストエラーを検出することができ、CRC-16とCRC-CITTは8ビット文字同期システムに用いられ、すべての1ビット、2ビットと奇数ビットのエラーを検出することができ、長さが16ビット以下のバーストエラーと、99.997%のビットバーストエラーと99.998%の18ビット以上のバーストエラーがある.
CRCサイクルコードプログラミング:(ルックアップ法、C#言語コード、CRC-16サイクルコード、うちCRC_LEN=0)
C#言語コード:
public static byte[] CRC16(byte[] data)///CRC16 , , 
 {
  byte[] outdata = new byte[2];
#region CRC16 
byte[] auchCRCHi = {
0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40,0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40, 0x01, 0xC0, 0x80, 0x41, 0x01, 0xC0, 0x80, 0x41, 0x00, 0xC1, 0x81, 0x40
};
byte[] auchCRCLow = {
0x00, 0xC0, 0xC1, 0x01, 0xC3, 0x03, 0x02, 0xC2, 0xC6, 0x06, 0x07, 0xC7, 0x05, 0xC5, 0xC4, 0x04, 0xCC, 0x0C, 0x0D, 0xCD, 0x0F, 0xCF, 0xCE, 0x0E, 0x0A, 0xCA, 0xCB, 0x0B, 0xC9, 0x09, 0x08, 0xC8, 0xD8, 0x18, 0x19, 0xD9, 0x1B, 0xDB, 0xDA, 0x1A, 0x1E, 0xDE, 0xDF, 0x1F, 0xDD, 0x1D, 0x1C, 0xDC, 0x14, 0xD4, 0xD5, 0x15, 0xD7, 0x17, 0x16, 0xD6, 0xD2, 0x12, 0x13, 0xD3, 0x11, 0xD1, 0xD0, 0x10, 0xF0, 0x30, 0x31, 0xF1, 0x33, 0xF3, 0xF2, 0x32, 0x36, 0xF6, 0xF7, 0x37, 0xF5, 0x35, 0x34, 0xF4, 0x3C, 0xFC, 0xFD, 0x3D, 0xFF, 0x3F, 0x3E, 0xFE, 0xFA, 0x3A, 0x3B, 0xFB, 0x39, 0xF9, 0xF8, 0x38, 0x28, 0xE8, 0xE9, 0x29, 0xEB, 0x2B, 0x2A, 0xEA, 0xEE, 0x2E, 0x2F, 0xEF, 0x2D, 0xED, 0xEC, 0x2C, 0xE4, 0x24, 0x25, 0xE5, 0x27, 0xE7, 0xE6, 0x26, 0x22, 0xE2, 0xE3, 0x23, 0xE1, 0x21, 0x20, 0xE0, 0xA0, 0x60, 0x61, 0xA1, 0x63, 0xA3, 0xA2, 0x62, 0x66, 0xA6, 0xA7, 0x67, 0xA5, 0x65, 0x64, 0xA4, 0x6C, 0xAC, 0xAD, 0x6D, 0xAF, 0x6F, 0x6E, 0xAE, 0xAA, 0x6A, 0x6B, 0xAB, 0x69, 0xA9, 0xA8, 0x68, 0x78, 0xB8, 0xB9, 0x79, 0xBB, 0x7B, 0x7A, 0xBA, 0xBE, 0x7E, 0x7F, 0xBF, 0x7D, 0xBD, 0xBC, 0x7C, 0xB4, 0x74, 0x75, 0xB5, 0x77, 0xB7, 0xB6, 0x76, 0x72, 0xB2, 0xB3, 0x73, 0xB1, 0x71, 0x70, 0xB0, 0x50, 0x90, 0x91, 0x51, 0x93, 0x53, 0x52, 0x92, 0x96, 0x56, 0x57, 0x97, 0x55, 0x95, 0x94, 0x54, 0x9C, 0x5C, 0x5D, 0x9D, 0x5F, 0x9F, 0x9E, 0x5E, 0x5A, 0x9A, 0x9B, 0x5B, 0x99, 0x59, 0x58, 0x98, 0x88, 0x48, 0x49, 0x89, 0x4B, 0x8B, 0x8A, 0x4A, 0x4E, 0x8E, 0x8F, 0x4F, 0x8D, 0x4D, 0x4C, 0x8C, 0x44, 0x84, 0x85, 0x45, 0x87, 0x47, 0x46, 0x86, 0x82, 0x42, 0x43, 0x83, 0x41, 0x81, 0x80, 0x40
};
#endregion
  byte crcHi = 0xff;
  byte crcLow = 0xff;
  for (int i = 0; i < data.Length - CRC_LEN; i++)
   {

    int crcIndex = crcHi ^ data[i];
    crcHi = (byte)(crcLow ^ auchCRCHi[crcIndex]);
    crcLow = auchCRCLow[crcIndex];
    }
   outdata[0] = crcHi;
   outdata[1] = crcLow;
   return (outdata);
}