奇同位檢查

在上一篇CRC-8裡面有個比較簡單的偵錯法，就是同位元檢查

同位元又分為奇同位元檢查和偶同位元檢查

不過我在看到一篇文章的時候，發現他程式的寫法好特別

裡面的範例是偶同位元檢查：

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);
}

我改了一下，之後的比較都是以奇同位元檢查做比較

WORD parity_check(BYTE  data){
   WORD parity = data;
   parity ^= (parity >> 1);
   parity ^= (parity >> 2);
   parity ^= (parity >> 4);

   return ((~(parity & 0x01))& 0x01);
}

我還是搞不懂為什麼他要這樣寫

那就回到奇同位元的原理來寫最簡單的程式了

如果8位元有奇數個1，那同位元就補上0

反之，如果是偶數個1，那就補上1

那麼最簡單的程式就是利用for 回圈

WORD parity_check2(WORD data)
{
   WORD i;
   WORD parity = 0;

   for (i = 0; i < 8; i++)
   {
      parity += data ;
      data >>= 1;
   }

   return ((~(parity & 0x01))& 0x01);
}

 

可是這樣寫的話，效率真的是……   爛透了

那就利用CRC查表的想法來實現

利用高4位元組和低4位元組做xor，最後查出相對應的同位元資料

 

因為已經知道同位的方式，所以可以自行建一張16byte的資料

當然，如果記憶體夠大，那麼建256個資料是最快的

const BYTE par_table[16]={
 0x01,0x00,0x00,0x01,
 0x00,0x01,0x01,0x00,
 0x00,0x01,0x01,0x00,
 0x01,0x00,0x00,0x01,
};

查表的程式就是

WORD parity_check3(WORD data)
{
   WORD nibble = data>>4;
   WORD parity = 0;
   parity = (data & 0x0f) ^ nibble;

   return (par_table[parity]);
}

 

可是我又發現，這張表就只有0和1的資料結果，如果把16byte 合成1個word的話，那就可以省去不少的空間

我又把剛剛建的表，照著順序把好，那這個常數資料就會是

const WORD PAR_word=0x9669;

 

最後我只要把運算好的資料結果，照著順序取出來，那麼就可以得到相同的結果了

WORD parity_check4(WORD data)
{
   WORD nibble = data>>4;
   WORD parity = 0;
   parity = (data & 0x0f) ^ nibble;

   return ( (PAR_word>>parity) & 0x01 );
}

 

這是一個不錯的練習動腦筋的範例程式~

最後我發現parity_check4的code size 和執行速度都是最佳的(以C30 compiler 做比較)，真的，一樣的結果，但程式的執行效率還是有差，不過在理解上，我想還是以for 迴圈的寫法，是最容易懂的，但是只要多花一點時間，就可以得到不錯的成效了~

或許還有更好的寫法，但我大概就只有想到這些了~