CRC 檢驗

 

今天在寫8-bit MCU存取EEPROM時候，思考了幾種驗證資料正確性的方法

 
第一種：Repetition codes

將同一筆資料寫入N個block

優點：讀取時只要採取多數決的決策法就能找出正確資料，構想簡單

缺點：佔用空間和寫入時間為N倍

 

第二種：Parity bit

檢查二進位資料串中為1的個數，可分為奇同位(odd parity)和偶同位(even parity)

優點：實現簡單

缺點：錯誤bit為偶數時，parity check會認為接收資料是正確的，既使接收資料是錯的

parity check 範例

unsigned int parity_check(unsigned int data){
    data ^= (data >> 1);
    data ^= (data >> 2);
    data ^= (data >> 4);
    data ^= (data >> 8);
    data ^= (data >> 16);
    return (data & 0x1);
}

_parity_check:
  lsr.w W0,#1,W1
  xor.w W0,W1,W0 ;data ^= (data >> 1);
  lsr.w W0,#2,W1
  xor.w W0,W1,W0  ;data ^= (data >> 2);
  lsr.w W0,#4,W1
  xor.w W0,W1,W0  ;data ^= (data >> 4);
  lsr.w W0,#8,W1
  xor.w W0,W1,W0  ;data ^= (data >> 8);
  and.w W0,#1,W0
  return      ;return (data & 0x1);

 

 

第三種：Checksum

checksum沒有一定的工業標準，這裡只提longitudinal redundancy check (LRC)

優點：使用8bit MCU處理超過8 bit資料時，只要使用XOR即可算出checksum值(不需bit shift)，和parity bit相比，有更高的可靠度

缺點：binary stream中，同一bit stream出現偶數次錯誤，會將錯誤的接收資料判斷為正確資料

 

第四種：CRC ( Cyclic redundancy check )

優點：可針對各種位元長度資料作，如CRC-8 CRC-16 CRC-32

缺點：運算複雜度較前述為高，CRC-128以上已經漸漸被hash所取代

Table from Wikipedia

http://en.wikipedia.org/wiki/Cyclic_redundancy_check

 

CRC-8範例

unsigned char crc8_calc(unsigned char *byt, unsigned int size )
{
/* Calculate CRC-8 value; uses The CCITT-8 polynomial,
expressed as X^8 + X^5 + X^4 + 1 */

    unsigned char crc = (unsigned char) 0xff;
    unsigned int index;
    unsigned char b;
    for( index=0; index<size; index++){
        crc ^= byt[index];
        for( b=0; b<8; ++b ){
            if( crc & 0x80 )
                crc = (crc << 1) ^ 0x31;
            else
                crc = (crc << 1);
        }
    }

    return crc;
}

CRC-16範例

// Update the CRC for transmitted and received data using
// the CCITT 16bit algorithm (X^16 + X^12 + X^5 + 1).

    unsigned char ser_data;
    static unsigned int crc;

    crc = (unsigned char)(crc >> 8) | (crc << 8);
    crc ^= ser_data;
    crc ^= (unsigned char)(crc & 0xff) >> 4;
    crc ^= (crc << 8) << 4;
    crc ^= ((crc & 0xff) << 4) << 1;