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

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

當(dāng)傳輸過程中某一個(gè)bit被反轉(zhuǎn)了，例如： 10 0001 0000 （528）

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

10 0001 0000/1011 = 100 1000 余 0

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

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

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

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

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

由于除法操作可能需要借位，在實(shí)際的CRC計(jì)算中，采用的是異或（XOR）操作而避免了借位。同樣的，如果數(shù)據(jù)仍然是10 0000 0000b，而‘除數(shù)’是1011b，這個(gè)‘除數(shù)’也被稱之為二項(xiàng)式（polynomial），也可以表達(dá)成 X3+X+1。 那么我們一樣將原數(shù)據(jù)左移，只不過這次我們只移動(dòng)3位且補(bǔ)0，因?yàn)椴皇褂脺p法操作，只要異或完的結(jié)果少于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 其實(shí)就是相同就是0，不一樣就是1。下面是長除的整個(gè)過程：

1011100101 1011/1000000000000 1011 1100 1011 1110 1011 1010 1011 1000 1011 1100 1011 111 ----------‘余數(shù)’

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

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

原文標(biāo)題：PCIe核心技術(shù)之CRC系列1 - CRC3

文章出處：【微信公眾號：ssdfans】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。

責(zé)任編輯：haq