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

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

2、碼組與多項(xiàng)式系數(shù)序列的對應(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個多項(xiàng)式系數(shù)分別是1，1，0，1，0，和1。 whenwhen采用多項(xiàng)式編碼的方法，發(fā)送方和采用多項(xiàng)式編碼的方法，發(fā)送方和接收方必須事先商定一個生成多項(xiàng)式接收方必須事先商定一個生成多項(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)和加在幀的末尾，使這個帶校驗(yàn)和的幀的多項(xiàng)式能被使這個帶校驗(yàn)和的幀的多項(xiàng)式能被G(x)G(x)除盡。當(dāng)接收方收到帶有校驗(yàn)和的幀時，除盡。當(dāng)接收方收到帶有校驗(yàn)和的幀時，用用G(x)G(x)去除它，如果有余數(shù)，則傳輸出去除它，如果有余數(shù)，則傳輸出錯。錯。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)碼。 下面以一個例子來具體說明整個過程。現(xiàn)假設(shè)選擇的下面以一個例子來具體說明整

4、個過程。現(xiàn)假設(shè)選擇的CRC生成多項(xiàng)式為生成多項(xiàng)式為GX） = X4 + X3 + 1，要求出，要求出二進(jìn)制序列二進(jìn)制序列10110011的的CRC校驗(yàn)碼。具體的計(jì)算過校驗(yàn)碼。具體的計(jì)算過程如下不會作圖沒辦法啦）：程如下不會作圖沒辦法啦）： （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的位，也的位，也就是這個二進(jìn)制的第就是

5、這個二進(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個個0，得到，得到101100110000，然，然后把這個數(shù)以后把這個數(shù)以“模模2除法方式除以生除法方式除以生成多項(xiàng)式成多項(xiàng)式11001，得到的余數(shù)，即

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