徒手設計crc電路

• crc電路怎麼設計？
  • crc就是GF(2)中多項式除法，可是電路是怎麼樣的呢？大家一般上來就搬出LFSR，就說用LFSR實作校驗碼計算，也沒說為啥，根本看不懂。我試着自己設計一下crc電路。
  • 首先看公式，設
    • 資訊碼字 M，位寬為m
    • 生成多項式 G，階數為r
    • 商 Q
    • 餘數 R
  • 有 M/G=Q*G+R
  • M用二進制表示，顯然M為m個多項式的和，分别是

    

  • 代入M/G=Q*G+R，得到

    

  • 我們把M拆成m項，分别作為被除數，最後再把m個餘數加起來。Q不用考慮了，隻用看被除數，而被除數永遠是最高位加上一串0，唯一有效的就是一個最高位。是以電路的輸入隻要一個比特即可，就是把M從高位按順序輸入。
  • 但是被除數除一次也算不出來餘數呀，總不可能把餘數一個個先算出來再加起來吧。我們可以用循環移位，把計算餘數的過程套在一起，這樣當最後一個資料比特輸入，第一比特輸入的餘數也就計算完成了。
  • 餘數是r-1階，是以使用r個觸發器存儲即可，最高位為r-1階。
  • 首先對

    

    做除法，就是和G(x)異或一下。一次異或無法完成除法，把餘數向高位移動一位，加入下一次除法，繼續參與模除。r-1階左移一位就是r階了，又可以和G(x)對齊，和新的輸入加在一起，進行模除。其實新的輸入就是一個比特，其餘位全0，任何數和0異或等于本身，是以不用考慮了。那麼所謂和新的輸入加在一起，就是在輸入那裡異或一下。
  • 這樣的話，電路畫出來，發現就是LFSR。把M全部輸入進去，由于被除數其實添加了r+1個0，是以把資訊比特輸入完，還要把後續的0都輸入。最後，寄存器中剩下的就是

    

    ，即crc結果。
  • 搬運一個電路圖過來展示一下：

  •