CRC碼的簡(jiǎn)單計(jì)算ppt課件

1、CRC碼的計(jì)算 1.什么是CRC碼？ 循環(huán)冗余碼校驗(yàn)英文名稱為Cyclical RedundancyCheck，簡(jiǎn)稱CRC。它是利用多項(xiàng)式除法及余數(shù)的原理來(lái)作錯(cuò)誤偵測(cè)Error Detecting的。實(shí)際應(yīng)用時(shí)，發(fā)送裝置計(jì)算出CRC值并隨數(shù)據(jù)一同發(fā)送給接收裝置，接收裝置對(duì)收到的數(shù)據(jù)重新計(jì)算CRC并與收到的CRC相比較，若兩個(gè)CRC值不同，則說(shuō)明數(shù)據(jù)通訊出現(xiàn)錯(cuò)誤。 2.多項(xiàng)式的生成多項(xiàng)式的生成CRC碼把整個(gè)數(shù)據(jù)塊當(dāng)作一串連續(xù)的二進(jìn)制數(shù)據(jù)。代數(shù)結(jié)構(gòu)可看作是一個(gè)報(bào)文碼多項(xiàng)式，是基于將位串看成是系數(shù)為0或1的多項(xiàng)式，一個(gè)k位幀可以看成是從xk-1到x0的k次多項(xiàng)式的系數(shù)序列，這個(gè)多項(xiàng)式的階數(shù)：k-1。

2、碼組與多項(xiàng)式系數(shù)序列的對(duì)應(yīng)，高位(最左邊)是x的k-1項(xiàng)系數(shù)，下一位是x的k-2項(xiàng)的系數(shù)，以此類推，生成多項(xiàng)式的最高位和最低位必須是1，且生成多項(xiàng)式必須比該校驗(yàn)和的多項(xiàng)式短。For example,110101有6位，表示成多項(xiàng)式是x5+x4+x2+0，即它的6個(gè)多項(xiàng)式系數(shù)分別是1，1，0，1，0，和1。 whenwhen采用多項(xiàng)式編碼的方法，發(fā)送方和采用多項(xiàng)式編碼的方法，發(fā)送方和接收方必須事先商定一個(gè)生成多項(xiàng)式接收方必須事先商定一個(gè)生成多項(xiàng)式G(x)G(x)。要計(jì)算。要計(jì)算mm位幀位幀M(x)M(x)的校驗(yàn)和，生的校驗(yàn)和，生成多項(xiàng)式必須比該校驗(yàn)和的多項(xiàng)式短。成多項(xiàng)式必須比該校驗(yàn)和的多項(xiàng)式短。

3、 基本思想是：將校驗(yàn)和加在幀的末尾，基本思想是：將校驗(yàn)和加在幀的末尾，使這個(gè)帶校驗(yàn)和的幀的多項(xiàng)式能被使這個(gè)帶校驗(yàn)和的幀的多項(xiàng)式能被G(x)G(x)除盡。當(dāng)接收方收到帶有校驗(yàn)和的幀時(shí)，除盡。當(dāng)接收方收到帶有校驗(yàn)和的幀時(shí)，用用G(x)G(x)去除它，如果有余數(shù)，則傳輸出去除它，如果有余數(shù)，則傳輸出錯(cuò)。錯(cuò)。CRC碼的計(jì)算碼的計(jì)算 由以上分析可知，既然除數(shù)是隨機(jī)，或者按標(biāo)準(zhǔn)選定由以上分析可知，既然除數(shù)是隨機(jī)，或者按標(biāo)準(zhǔn)選定的，所以的，所以CRC校驗(yàn)的關(guān)鍵是如何求出余數(shù)，也就是校驗(yàn)的關(guān)鍵是如何求出余數(shù)，也就是CRC校驗(yàn)碼。校驗(yàn)碼。 下面以一個(gè)例子來(lái)具體說(shuō)明整個(gè)過(guò)程?，F(xiàn)假設(shè)選擇的下面以一個(gè)例子來(lái)具體說(shuō)明整

4、個(gè)過(guò)程?，F(xiàn)假設(shè)選擇的CRC生成多項(xiàng)式為生成多項(xiàng)式為GX） = X4 + X3 + 1，要求出，要求出二進(jìn)制序列二進(jìn)制序列10110011的的CRC校驗(yàn)碼。具體的計(jì)算過(guò)校驗(yàn)碼。具體的計(jì)算過(guò)程如下不會(huì)作圖沒(méi)辦法啦）：程如下不會(huì)作圖沒(méi)辦法啦）： （1首先把生成多項(xiàng)式轉(zhuǎn)換成二進(jìn)制數(shù)，由首先把生成多項(xiàng)式轉(zhuǎn)換成二進(jìn)制數(shù)，由GX） = X4 + X3 + 1可以知道（，它一共是可以知道（，它一共是5位總位數(shù)位總位數(shù)等于最高位的冪次加等于最高位的冪次加1，即，即4+1=5），然后根據(jù)多項(xiàng)），然后根據(jù)多項(xiàng)式各項(xiàng)的含義多項(xiàng)式只列出二進(jìn)制值為式各項(xiàng)的含義多項(xiàng)式只列出二進(jìn)制值為1的位，也的位，也就是這個(gè)二進(jìn)制的第就是

5、這個(gè)二進(jìn)制的第4位、第位、第3位、第位、第0位的二進(jìn)制均位的二進(jìn)制均為為1，其它位均為，其它位均為0很快就可得到它的二進(jìn)制比特串很快就可得到它的二進(jìn)制比特串為為11001。 （2因?yàn)樯啥囗?xiàng)式的位數(shù)為因?yàn)樯啥囗?xiàng)式的位數(shù)為5，根據(jù)，根據(jù)前面的介紹，得知前面的介紹，得知CRC校驗(yàn)碼的位數(shù)為校驗(yàn)碼的位數(shù)為4校驗(yàn)碼的位數(shù)比生成多項(xiàng)式的位數(shù)少校驗(yàn)碼的位數(shù)比生成多項(xiàng)式的位數(shù)少1）。因?yàn)樵瓟?shù)據(jù)幀）。因?yàn)樵瓟?shù)據(jù)幀10110011，在它后，在它后面再加面再加4個(gè)個(gè)0，得到，得到101100110000，然，然后把這個(gè)數(shù)以后把這個(gè)數(shù)以“模模2除法方式除以生除法方式除以生成多項(xiàng)式成多項(xiàng)式11001，得到的余數(shù)，即

6、得，得到的余數(shù)，即得CRC校驗(yàn)碼為校驗(yàn)碼為0100。具體操作在黑板上。具體操作在黑板上演示。演示。 【說(shuō)明】【說(shuō)明】“模模2除法與除法與“算術(shù)除法類似，算術(shù)除法類似，但它既不向上位借位，也不比較除數(shù)和被除數(shù)但它既不向上位借位，也不比較除數(shù)和被除數(shù)的相同位數(shù)值的大小，只要以相同位數(shù)進(jìn)行相的相同位數(shù)值的大小，只要以相同位數(shù)進(jìn)行相除即可。模除即可。模2加法運(yùn)算為：加法運(yùn)算為：1+1=0，0+1=1，0+0=0，無(wú)進(jìn)位，也無(wú)借位；模，無(wú)進(jìn)位，也無(wú)借位；模2減法運(yùn)算為：減法運(yùn)算為：1-1=0，0-1=1，1-0=1，0-0=0，也無(wú)進(jìn)，也無(wú)進(jìn)位，無(wú)借位。相當(dāng)于二進(jìn)制中的邏輯異或運(yùn)算。位，無(wú)借位。相當(dāng)于二進(jìn)制中的邏輯異或運(yùn)算。也就是比較后，兩者對(duì)應(yīng)位相同則結(jié)果為也就是比較后，兩者對(duì)應(yīng)位相同則結(jié)果為“0”，不同則結(jié)果為不同則結(jié)果為“1”。如。如100101除以除以1110，結(jié)果得到商為結(jié)果得到商為11，余數(shù)為，余數(shù)為1，再如，再如1111=101。 總結(jié)計(jì)算：只要會(huì)把生成多項(xiàng)式按總結(jié)計(jì)算：只要會(huì)把生成多項(xiàng)式按項(xiàng)系數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)作為除數(shù)，項(xiàng)系數(shù)轉(zhuǎn)化為二進(jìn)制數(shù)作為除數(shù)，在原幀后補(bǔ)上多項(xiàng)式階數(shù)個(gè)在原幀后補(bǔ)上多項(xiàng)式階數(shù)個(gè)0得到的得到的新串作為被除數(shù)，做多項(xiàng)式