[PCIe]CRC系列1 – CRC3

原創內容,轉載請注明:  [http://www.od-music.com]  謝謝!

(本文將介紹了CRC相關的一些基礎知識,并用CRC3為例推導了CRC的部分原理)
CRC是CyclicRedundancyCheck的縮寫,是一種通過額外冗余bit來檢查數據完整性的一種方法。一個比較容易類比的方法就是除法操作。例如我們有數據512,我們將512除以11得到46余數是6。那么我們可以將6作為校驗信息一起傳遞給對方。接收端收到512和校驗信息6后,也做相同的除法操作,如果得到的余數與收到的校驗信息一致,我們認為收到的數據大概率是完整的。
我們將十進制轉換成二進制,重新看一遍過程,原始數據是
????512 =? 10 0000 0000
????11?? =? 1011
????10 0000 0000/1011 = 100 0110 余 110?
當傳輸過程中某一個bit被反轉了,例如:
????10 0001?0000 (528)

接收端使用收到的數據進行除法操作,將會得到:

10 0001 0000/1011 = 100 1000 余 0

那么這個校驗信息就不一樣了,所以接收端認為數據或者校驗信息在傳輸過程中可能出現了錯誤。

為了使得校驗比較方便,我們可以將需要校驗的信息放在數據的后面。由于除數是11(1011b),余數有可能是0(0000b)到10(1010b),所以我們可以將原數據向左移4位,空出來的空間存放校驗信息。左移4位相當于把原數據乘以了24,即十進制的16。
512*16 = 8192
二進制表示:10 0000 0000 0000b
然后用8192/11 = 744 余8
不難算出,只要將8192加上3,這個新的數就可以被11整除。
所以我們可以將3作為這個原數據的校驗信息,并放在原數據的后面一起傳送,即:
10 0000 0000?0011b?
如果接收端接收到的數據無法被11整除,即有余數,那么證明接收到的內容可能在傳輸過程中被修改了。
?
例如,仍然是原數據的第六個bit被反轉了,即:
?10 00010000?0011b (8451)?
那么接收端對接收到的內容進行運算會發現:
8451/11 = 768 余 3
并不能被11整除,所以內容可能在傳輸過程中被修改了。
我們仔細觀察會發現,原本的信息是可以被11整除的,多出來的部分是由于某個bit反轉而引起的,我們單獨將該信息拿出來,可以得到:
1 0000 0000b (256)
如果將這個錯誤信息除11,我們會發現:
256/11 = 23 余 3
也是余3,是不是發現了什么?沒有錯,導致最后整個信息不整除的主要原因,是因為反轉的bit與其所在的位置所表達的數不能夠被11整除。
因為我們在數字世界傳送信息的時候大部分都是01表示的二進制代碼,所以信息中有任意一個bit被反轉,都是2的多少次冪。所以只要除數不是偶數且不是1就可以檢測出任意一個bit的錯誤。例如3(11b),5(101b),7(111b)等等。
由于除法操作可能需要借位,在實際的CRC計算中,采用的是異或(XOR)操作而避免了借位。同樣的,如果數據仍然是10 0000 0000b,而‘除數’是1011b,這個‘除數’也被稱之為二項式(polynomial),也可以表達成 X3+X+1。
?
那么我們一樣將原數據左移,只不過這次我們只移動3位且補0,因為不使用減法操作,只要異或完的結果少于4位,我們就把那3位數作為‘余數’。具體操作如下:
首先將10 0000 0000b左移3位:
1 0000 0000 0000b,然后用1011b作為‘除數’:
異或操作的真值表:
0 xor 0 = 0
0 xor 1 = 1
1 xor 0 = 1
1 xor 1 = 0
其實就是相同就是0,不一樣就是1。下面是長除的整個過程:

 

         1011100101
 1011/1000000000000
      1011
       1100
        1011
         1110
         1011
          1010
          1011
             1000
             1011
               1100
               1011
                111 ----------‘余數’?
這里可以看到我們得到的‘余數’與實際的除法得到的余數有所不同,那么使用這種方式有什么好處呢?
我們接著往下看。
這個‘余數’被稱為CRC3的值,作為校驗信息可以直接替換掉數據的最后3位,這3位是原數據左移后,補了0的3個位置。當計算出CRC3的值后,可以直接把111b添加在后面,即:
1 0000 0000 0111b
因為異或的原因,這個數正好可以被1011b通過長除的方法整除,便利性與傳統除法來說要好不少,大家可以參考前面標紅的那句話。另外就是異或操作在數字設計中也比較容易實現。
?
接下來我們繼續分析一下檢錯能力,前面提到設計過的二項式可以保證任意一個bit反轉都可以被檢測出來。如果需要保證連續相鄰的兩個bit都反轉了也可以被檢測出來怎樣設計呢?那我們可以分析一下連續兩個bit都反轉的情況,錯誤信息的規律。例如我們可以用Xn+Xn-1來表示連續兩個bit都反轉的情況。因為原來的兩個bit與11b進行異或都會取反,所以我們可以用Xn+Xn-1來表示11b并處在任意的位置。通過提取公因數得到:
Xn+Xn-1?= Xn-1(X+1)
所以我們設計的二項式只要不能被X+1整除,那么連續兩個bit的錯誤信息就無法被該二項式整除。因此類似X2+1 或者X3+1這種二項式就是不錯的選擇。
Note:
二項式 X2+1就是101b
二項式 X3+1就是1001b?
?

Reference:

http://users.ece.cmu.edu/~koopman/crc/


以下是咱們金牌贊助商,某獵頭公司的提供的信息:

全球五百強企業,工作地點深圳,崗位為學習崗型,需求9人;

需要技能:
?
1.熟悉CXL協議;
2.熟悉PCIe協議;
3.熟悉其他芯片高速協議
4.熟練掌握芯片前端數字邏輯設計?
5.熟練掌握芯片數字邏輯仿真驗證;
6.邏輯思維能力強,主動性強,學習能力強。
6為必要條件,1-5任意滿足一個,滿足兩個條件或以上,優先考慮
薪資待遇:

根據面試結果,待遇豐厚,年薪預計130%-200%或以上

有意者請發簡歷到fleeves@163.com
分類目錄 國內動態, 未分類, 行業動態.
掃一掃二維碼或者微信搜索公眾號ssdfans關注(添加朋友->點最下面的公眾號->搜索ssdfans),可以經??吹絊SD技術和產業的文章(SSD Fans只推送干貨)。
ssdfans微信群介紹
技術討論群 覆蓋2000多位中國和世界華人圈SSD以及存儲技術精英
固件、軟件、測試群 固件、軟件和測試技術討論
異構計算群 討論人工智能和GPU、FPGA、CPU異構計算
ASIC-FPGA群 芯片和FPGA硬件技術討論群
閃存器件群 NAND、3D XPoint等固態存儲介質技術討論
企業級 企業級SSD、企業級存儲
銷售群 全國SSD供應商都在這里,砍砍價,會比某東便宜20%
工作求職群 存儲行業換工作,發招聘,要關注各大公司招聘信息,趕快來
高管群 各大SSD相關存儲公司高管和創始人、投資人

想加入這些群,請微信掃描下面二維碼,或搜索nanoarchplus,加阿呆為微信好友,介紹你的昵稱-單位-職務,注明群名,拉你進群。SSD業界需要什么幫助,也可以找阿呆聊。