CRC算法（對齊版）

ssafa

               

  
  CRC算法原理
  


  
   
  
   
  CRC原理介紹:
   CRC的英文全稱為Cyclic
  Redundancy
  Check（Code），中文名稱為循環(huán)冗余校驗(yàn)（碼）。它是一類重要的線性分組碼，編碼和解碼方法簡單，檢錯(cuò)和糾錯(cuò)能力強(qiáng)，在通信領(lǐng)域廣泛地用于實(shí)現(xiàn)差錯(cuò)控制。  
   
      
  CRC計(jì)算與普通的除法計(jì)算有所不同。普通的除法計(jì)算是借位相減的，而CRC計(jì)算則是異或運(yùn)算。任何一個(gè)除法運(yùn)算都需要選取一個(gè)除數(shù)，在CRC運(yùn)算中我們稱之為poly，而寬度W就是poly最高位的位置。比如poly
  1001的W是3，而不是4。注意最高位總是1，當(dāng)你選定一個(gè)寬度，那么你只需要選擇低W各位的值。假如我們想計(jì)算一個(gè)位串的CRC碼，并要保證每一位都要被處理，因此我們需要在目標(biāo)位串后面加上W個(gè)0。下面舉例說明CRC算法的過程。
   
      
  在此例中，我們假設(shè)位串為110101101。
   
  Poly                     =
  10011（寬度W = 4）
  Bitstring + W
  zeros = 110101101 0000
  10011/ 1101011010000/110000101 （我們不關(guān)心此運(yùn)算的商）
   
         1101011010000
         10011||||||||
         -----||||||||
          10011|||||||
  
          10011|||||||
        -----|||||||
           00001||||||
           00000||||||
           -----||||||
  
            00010|||||
          00000|||||
  
            -----|||||
           00101||||
             00000||||
             -----||||
              01010|||
              00000|||
              -----|||
               10100||
               10011||
               -----||
                01110|
                00000|
                -----|
                 11100
                 10011
                 -----
                  1111 -> 余數(shù)
  -> CRC！
  計(jì)算過程總結(jié)如下：
  1.
  只有當(dāng)位串的最高位為1，我們才將它與poly做XOR運(yùn)算，否則我們只是將位串左移一位。
  2.
  異或運(yùn)算的結(jié)果實(shí)質(zhì)上是被操作位串與poly的低W位進(jìn)行運(yùn)算的結(jié)果，因?yàn)樽罡呶豢倿?。
  

               
               
               
               
               

本文來自ChinaUnix博客，如果查看原文請點(diǎn)：http://blog.chinaunix.net/u1/45304/showart_1983077.html