數(shù)據(jù)通信網(wǎng)絡(luò)的認(rèn)知與應(yīng)用 CRC檢錯(cuò)碼的工作原理

CRC檢錯(cuò)碼的工作原理目錄CONTENTS02CRC循環(huán)冗余校驗(yàn)碼舉例01CRC工作原理理解CRC工作原理掌握CRC編碼方法學(xué)習(xí)目標(biāo)循環(huán)冗余校驗(yàn)碼循環(huán)冗余校驗(yàn)碼（CycleRedundancyCheck，CRC），由兩部分組成，前一部分是k+1個(gè)比特的待發(fā)送信息，后一部分是r個(gè)比特的冗余碼。由于前一部分是實(shí)際要傳輸?shù)膬?nèi)容，因此是固定不變的，CRC碼的產(chǎn)生關(guān)鍵在于后一部分冗余碼的計(jì)算。CRC計(jì)算中主要用到兩個(gè)多項(xiàng)式：K（x）和G（x）。其中，K（x）是一個(gè)k階多項(xiàng)式，其系數(shù)是待發(fā)送的k+1個(gè)比特序列；G（x）是一個(gè)r階的生成多項(xiàng)式，由發(fā)收雙方預(yù)先約定。任何一個(gè)待發(fā)送的二進(jìn)制比特流都可以看成是某個(gè)一元多項(xiàng)式中各項(xiàng)系數(shù)的組合，如1011011可以看成是一元多項(xiàng)式1*X6+0*X5+1*X4+1*X3+0*X2+1*X1+1*X0，即：

X6+X4+X3+X1+X0，同理多項(xiàng)式X5+X3+X2+X1+X0對應(yīng)的代碼為101111。課堂習(xí)題請完成下面的多項(xiàng)式到比特序列的轉(zhuǎn)化：G（x）=X6+X5+X2+1G（x）=X7+X4+X2G（x）=X7+X6+X5+X2+X1CRC校驗(yàn)碼工作原理

CRC工作原理是：將要發(fā)送的數(shù)據(jù)比特序列當(dāng)做一個(gè)多項(xiàng)式K（x）的系數(shù)，在發(fā)送端用收發(fā)雙方約定的生成多項(xiàng)式G（x）去除，求得一個(gè)余數(shù)多項(xiàng)式，并附加在發(fā)送數(shù)據(jù)多項(xiàng)式之后發(fā)送到接收端。接收端收到數(shù)據(jù)后，除以多項(xiàng)式G（x），如果得到結(jié)果為0，則數(shù)據(jù)傳輸無差錯(cuò)，若不為0，則傳輸出錯(cuò)，請求重發(fā)。發(fā)送端接收端發(fā)送數(shù)據(jù)K（x）生成多項(xiàng)式G（x）接收數(shù)據(jù)K’（x）生成多項(xiàng)式G（x）利用除法運(yùn)算求出校驗(yàn)字段數(shù)據(jù)字段校驗(yàn)字段利用除法求余數(shù)余數(shù)為0，未出錯(cuò)余數(shù)不為0，出錯(cuò)CRC編碼校驗(yàn)過程（1）發(fā)送方和接收方事先約定一個(gè)生成多項(xiàng)式G（x）。（2）發(fā)送端根據(jù)生成多項(xiàng)式G（x）去計(jì)算要附加在信息幀尾部的冗余位。計(jì)算校驗(yàn)和的算法如下：假設(shè)信息幀的比特?cái)?shù)為k位，對應(yīng)的多項(xiàng)式為K（x），G（x）為r階。在信息幀的低位端加上r個(gè)0，此時(shí)信息幀的比特?cái)?shù)變?yōu)閗+r位，對應(yīng)的多項(xiàng)式為K（x）·xr。按模2除法，用對應(yīng)于G(x)的比特串去除對應(yīng)于xrK（x）的比特串，從而得到一個(gè)小于等于r位的余數(shù)。這個(gè)余數(shù)便可作為校驗(yàn)和。（3）將校驗(yàn)和附加在k位信息幀尾部，組成一個(gè)新的幀，由發(fā)送端發(fā)送給接收端。CRC編碼舉例例：CRC實(shí)例。假設(shè)要發(fā)送的信息幀數(shù)據(jù)比特序列為110011，雙方約定的生成多項(xiàng)式為G（x）=X4+X3+X0。（1）發(fā)送端發(fā)送數(shù)據(jù)計(jì)算方法：信息幀的多項(xiàng)式為K（x）=X5+X4+X1+X0。由生成多項(xiàng)式G（x）=X4+X3+X0可知階數(shù)r為4，生成多項(xiàng)式的比特序列為11001。此時(shí)利用公式xr.K(x)，即信息幀的數(shù)據(jù)比特序列乘以x4，則信息幀的多項(xiàng)式變?yōu)閄9+X8+X5+X4，即信息幀的比特序列變?yōu)?100110000。將乘積用多項(xiàng)式比特序列去除，按模2運(yùn)算，求出余數(shù)為：CRC編碼舉例例：CRC實(shí)例。假設(shè)要發(fā)送的信息幀數(shù)據(jù)比特序列為110011，雙方約定的生成多項(xiàng)式為G（x）=X4+X3+X0。（1）發(fā)送端發(fā)送數(shù)據(jù)計(jì)算方法：110011000011001K(x)?xr1000011100110000110011001余數(shù)生成多項(xiàng)式G（x）通過上一步計(jì)算可知余數(shù)為1001，也就是校驗(yàn)碼，將校驗(yàn)碼加在信息幀的后面即發(fā)送數(shù)據(jù)為1100111001。CRC編碼舉例（2）發(fā)送端發(fā)送數(shù)據(jù)計(jì)算方法如果在數(shù)據(jù)的傳輸過程中沒有發(fā)生錯(cuò)誤，那么接收端收到的帶有CRC校驗(yàn)碼的數(shù)據(jù)比特序列一定能被相同的生成多項(xiàng)式整除，即110011100111001K(x)?xr1000011100111001110010余數(shù)生成多項(xiàng)式G（x）CRC校驗(yàn)碼

CRC具有較強(qiáng)的檢錯(cuò)能力，可以檢測出所有的奇數(shù)位錯(cuò)、雙比特錯(cuò)、小于等于校驗(yàn)和長度的突發(fā)錯(cuò)。CRC中生成多項(xiàng)式G（x）的選擇是非常重要的。目前廣泛使用的生成多項(xiàng)式主要有以下幾種：CRC-16G（x）=X16+X15+X2+1CRC-CCITTG（x）=X16+X12