CRC是CyclicRedundancyCheck的縮寫，是一種通過額外冗余bit來檢查數(shù)據(jù)完整性的一種方法。一個比較容易類比的方法就是除法操作。例如我們有數(shù)據(jù)512，我們將512除以11得到46余數(shù)是6。那么我們可以將6作為校驗信息一起傳遞給對方。接收端收到512和校驗信息6后，也做相同的除法操作，如果得到的余數(shù)與收到的校驗信息一致，我們認為收到的數(shù)據(jù)大概率是完整的。 我們將十進制轉換成二進制，重新看一遍過程，原始數(shù)據(jù)是

512 = 10 0000 0000 11 = 1011 10 0000 0000/1011 = 100 0110 余 110

當傳輸過程中某一個bit被反轉了，例如： 10 0001 0000 （528）

接收端使用收到的數(shù)據(jù)進行除法操作，將會得到：

10 0001 0000/1011 = 100 1000 余 0

那么這個校驗信息就不一樣了，所以接收端認為數(shù)據(jù)或者校驗信息在傳輸過程中可能出現(xiàn)了錯誤。

為了使得校驗比較方便，我們可以將需要校驗的信息放在數(shù)據(jù)的后面。由于除數(shù)是11（1011b），余數(shù)有可能是0（0000b）到10（1010b），所以我們可以將原數(shù)據(jù)向左移4位，空出來的空間存放校驗信息。左移4位相當于把原數(shù)據(jù)乘以了24，即十進制的16。 512*16 = 8192 二進制表示：10 0000 0000 0000b 然后用8192/11 = 744 余8 不難算出，只要將8192加上3，這個新的數(shù)就可以被11整除。 所以我們可以將3作為這個原數(shù)據(jù)的校驗信息，并放在原數(shù)據(jù)的后面一起傳送，即： 10 0000 0000 0011b

如果接收端接收到的數(shù)據(jù)無法被11整除，即有余數(shù)，那么證明接收到的內容可能在傳輸過程中被修改了。 例如，仍然是原數(shù)據(jù)的第六個bit被反轉了，即： 10 00010000 0011b （8451）

那么接收端對接收到的內容進行運算會發(fā)現(xiàn)： 8451/11 = 768 余 3

并不能被11整除，所以內容可能在傳輸過程中被修改了。 我們仔細觀察會發(fā)現(xiàn)，原本的信息是可以被11整除的，多出來的部分是由于某個bit反轉而引起的，我們單獨將該信息拿出來，可以得到： 1 0000 0000b （256） 如果將這個錯誤信息除11，我們會發(fā)現(xiàn)： 256/11 = 23 余 3 也是余3，是不是發(fā)現(xiàn)了什么？沒有錯，導致最后整個信息不整除的主要原因，是因為反轉的bit與其所在的位置所表達的數(shù)不能夠被11整除。 因為我們在數(shù)字世界傳送信息的時候大部分都是01表示的二進制代碼，所以信息中有任意一個bit被反轉，都是2的多少次冪。所以只要除數(shù)不是偶數(shù)且不是1就可以檢測出任意一個bit的錯誤。例如3（11b），5（101b），7（111b）等等。

由于除法操作可能需要借位，在實際的CRC計算中，采用的是異或（XOR）操作而避免了借位。同樣的，如果數(shù)據(jù)仍然是10 0000 0000b，而‘除數(shù)’是1011b，這個‘除數(shù)’也被稱之為二項式（polynomial），也可以表達成 X3+X+1。 那么我們一樣將原數(shù)據(jù)左移，只不過這次我們只移動3位且補0，因為不使用減法操作，只要異或完的結果少于4位，我們就把那3位數(shù)作為‘余數(shù)’。具體操作如下： 首先將10 0000 0000b左移3位： 1 0000 0000 0000b，然后用1011b作為‘除數(shù)’： 異或操作的真值表： 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 ----------‘余數(shù)’

這里可以看到我們得到的‘余數(shù)’與實際的除法得到的余數(shù)有所不同，那么使用這種方式有什么好處呢？ 我們接著往下看。

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

原文標題：PCIe核心技術之CRC系列1 - CRC3

文章出處：【微信公眾號：ssdfans】歡迎添加關注！文章轉載請注明出處。

責任編輯：haq