久久久久久久999_99精品久久精品一区二区爱城_成人欧美一区二区三区在线播放_国产精品日本一区二区不卡视频_国产午夜视频_欧美精品在线观看免费

<li id="2w44o"></li>

標(biāo)題: 最通俗的CRC校驗(yàn)原理剖析 [打印本頁(yè)]

作者: 51黑dd 時(shí)間: 2016-4-7 03:39
標(biāo)題: 最通俗的CRC校驗(yàn)原理剖析
以下內(nèi)容摘自筆者即將出版的最新著作《深入理解計(jì)算機(jī)網(wǎng)絡(luò)》一書(shū)。本書(shū)將于12月底出版上市，敬請(qǐng)留意��！

5.3.2 循環(huán)冗余校驗(yàn)檢錯(cuò)方案

上節(jié)介紹的奇偶校驗(yàn)碼（PCC）只能校驗(yàn)一位錯(cuò)誤，本節(jié)所要介紹的循環(huán)冗余校驗(yàn)碼（CRC）的檢錯(cuò)能力更強(qiáng)，可以檢出多位錯(cuò)誤。

1. CRC校驗(yàn)原理

CRC校驗(yàn)原理看起來(lái)比較復(fù)雜，好難懂，因?yàn)榇蠖鄶?shù)書(shū)上基本上是以二進(jìn)制的多項(xiàng)式形式來(lái)說(shuō)明的。其實(shí)很簡(jiǎn)單的問(wèn)題，其根本思想就是先在要發(fā)送的幀后面附加一個(gè)數(shù)（這個(gè)就是用來(lái)校驗(yàn)的校驗(yàn)碼，但要注意，這里的數(shù)也是二進(jìn)制序列的，下同），生成一個(gè)新幀發(fā)送給接收端。當(dāng)然，這個(gè)附加的數(shù)不是隨意的，它要使所生成的新幀能與發(fā)送端和接收端共同選定的某個(gè)特定數(shù)整除（注意，這里不是直接采用二進(jìn)制除法，而是采用一種稱之為“模2除法”）。到達(dá)接收端后，再把接收到的新幀除以（同樣采用“模2除法”）這個(gè)選定的除數(shù)。因?yàn)樵诎l(fā)送端發(fā)送數(shù)據(jù)幀之前就已通過(guò)附加一個(gè)數(shù)，做了“去余”處理（也就已經(jīng)能整除了），所以結(jié)果應(yīng)該是沒(méi)有余數(shù)。如果有余數(shù)，則表明該幀在傳輸過(guò)程中出現(xiàn)了差錯(cuò)。

【說(shuō)明】“模2除法”與“算術(shù)除法”類似，但它既不向上位借位，也不比較除數(shù)和被除數(shù)的相同位數(shù)值的大小，只要以相同位數(shù)進(jìn)行相除即可。模2加法運(yùn)算為：1+1=0，0+1=1，0+0=0，無(wú)進(jìn)位，也無(wú)借位；模2減法運(yùn)算為：1-1=0，0-1=1，1-0=1，0-0=0，也無(wú)進(jìn)位，無(wú)借位。相當(dāng)于二進(jìn)制中的邏輯異或運(yùn)算。也就是比較后，兩者對(duì)應(yīng)位相同則結(jié)果為“0”，不同則結(jié)果為“1”。如100101除以1110，結(jié)果得到商為11，余數(shù)為1，如圖5-9左圖所示。如11×11=101，如圖5-9右圖所示。

圖5-9 “模2除法”和“模2乘法”示例

具體來(lái)說(shuō)，CRC校驗(yàn)原理就是以下幾個(gè)步驟：

（1）先選擇（可以隨機(jī)選擇，也可按標(biāo)準(zhǔn)選擇，具體在后面介紹）一個(gè)用于在接收端進(jìn)行校驗(yàn)時(shí)，對(duì)接收的幀進(jìn)行除法運(yùn)算的除數(shù)（是二進(jìn)制比較特串，通常是以多項(xiàng)方式表示，所以CRC又稱多項(xiàng)式編碼方法，這個(gè)多項(xiàng)式也稱之為“生成多項(xiàng)式”）。

（2）看所選定的除數(shù)二進(jìn)制位數(shù)（假設(shè)為k位），然后在要發(fā)送的數(shù)據(jù)幀（假設(shè)為m位）后面加上k-1位“0”，然后以這個(gè)加了k-1個(gè)“0“的新幀（一共是m+k-1位）以“模2除法”方式除以上面這個(gè)除數(shù)，所得到的余數(shù)（也是二進(jìn)制的比特串）就是該幀的CRC校驗(yàn)碼，也稱之為FCS（幀校驗(yàn)序列）。但要注意的是，余數(shù)的位數(shù)一定要是比除數(shù)位數(shù)只能少一位，哪怕前面位是0，甚至是全為0（附帶好整除時(shí)）也都不能省略。

（3）再把這個(gè)校驗(yàn)碼附加在原數(shù)據(jù)幀（就是m位的幀，注意不是在后面形成的m+k-1位的幀）后面，構(gòu)建一個(gè)新幀發(fā)送到接收端；最后在接收端再把這個(gè)新幀以“模2除法”方式除以前面選擇的除數(shù)，如果沒(méi)有余數(shù)，則表明該幀在傳輸過(guò)程中沒(méi)出錯(cuò)，否則出現(xiàn)了差錯(cuò)。

通過(guò)以上介紹，大家一定可以理解CRC校驗(yàn)的原理，并且不再認(rèn)為很復(fù)雜吧。

從上面可以看出，CRC校驗(yàn)中有兩個(gè)關(guān)鍵點(diǎn)：一是要預(yù)先確定一個(gè)發(fā)送端和接收端都用來(lái)作為除數(shù)的二進(jìn)制比特串（或多項(xiàng)式）；二是把原始幀與上面選定的除進(jìn)行二進(jìn)制除法運(yùn)算，計(jì)算出FCS。前者可以隨機(jī)選擇，也可按國(guó)際上通行的標(biāo)準(zhǔn)選擇，但最高位和最低位必須均為“1”，如在IBM的SDLC（同步數(shù)據(jù)鏈路控制）規(guī)程中使用的CRC-16（也就是這個(gè)除數(shù)一共是17位）生成多項(xiàng)式g（x）= x16 + x15 + x2 +1（對(duì)應(yīng)二進(jìn)制比特串為：11000000000000101）；而在ISO HDLC（高級(jí)數(shù)據(jù)鏈路控制）規(guī)程、ITU的SDLC、X.25、V.34、V.41、V.42等中使用CCITT-16生成多項(xiàng)式g（x）= x16 + x15 + x5 +1（對(duì)應(yīng)二進(jìn)制比特串為：11000000000100001）。

2. CRC校驗(yàn)碼的計(jì)算示例

由以上分析可知，既然除數(shù)是隨機(jī)，或者按標(biāo)準(zhǔn)選定的，所以CRC校驗(yàn)的關(guān)鍵是如何求出余數(shù)，也就是校驗(yàn)碼（CRC校驗(yàn)碼）。

下面以一個(gè)例子來(lái)具體說(shuō)明整個(gè)過(guò)程�，F(xiàn)假設(shè)選擇的CRC生成多項(xiàng)式為G（X） = X4 + X3 + 1，要求出二進(jìn)制序列10110011的CRC校驗(yàn)碼。下面是具體的計(jì)算過(guò)程：

（1）首先把生成多項(xiàng)式轉(zhuǎn)換成二進(jìn)制數(shù)，由G（X） = X4 + X3 + 1可以知道（，它一共是5位（總位數(shù)等于最高位的冪次加1，即4+1=5），然后根據(jù)多項(xiàng)式各項(xiàng)的含義（多項(xiàng)式只列出二進(jìn)制值為1的位，也就是這個(gè)二進(jìn)制的第4位、第3位、第0位的二進(jìn)制均為1，其它位均為0）很快就可得到它的二進(jìn)制比特串為11001。

（2）因?yàn)樯啥囗?xiàng)式的位數(shù)為5，根據(jù)前面的介紹，得知CRC校驗(yàn)碼的位數(shù)為4（校驗(yàn)碼的位數(shù)比生成多項(xiàng)式的位數(shù)少1）。因?yàn)樵瓟?shù)據(jù)幀10110011，在它后面再加4個(gè)0，得到101100110000，然后把這個(gè)數(shù)以“模2除法”方式除以生成多項(xiàng)式，得到的余數(shù)（即CRC碼）為0100，如圖5-10所示。注意參考前面介紹的“模2除法”運(yùn)算法則。

圖5-10 CRC校驗(yàn)碼計(jì)算示例

（3）把上步計(jì)算得到的CRC校驗(yàn)0100替換原始幀101100110000后面的四個(gè)“0”，得到新幀101100110100。再把這個(gè)新幀發(fā)送到接收端。

（4）當(dāng)以上新幀到達(dá)接收端后，接收端會(huì)把這個(gè)新幀再用上面選定的除數(shù)11001以“模2除法”方式去除，驗(yàn)證余數(shù)是否為0，如果為0，則證明該幀數(shù)據(jù)在傳輸過(guò)程中沒(méi)有出現(xiàn)差錯(cuò)，否則出現(xiàn)了差錯(cuò)。

通過(guò)以上CRC校驗(yàn)原理的剖析和CRC校驗(yàn)碼的計(jì)算示例的介紹，大家應(yīng)該對(duì)這種看似很復(fù)雜的CRC校驗(yàn)原理和計(jì)算方法應(yīng)該比較清楚了。

下面大家做一個(gè)練習(xí)，假設(shè)CRC生成多項(xiàng)式為G（X） = X5 + X4 +X+1，要發(fā)送的二進(jìn)制序列為100101110，求CRC校驗(yàn)碼是多少。

作者: thjk 時(shí)間: 2018-5-15 22:39
謝謝分享

作者: 51hei團(tuán)團(tuán) 時(shí)間: 2018-9-23 15:08
很好的科普貼，確實(shí)寫(xiě)得比較通俗易懂

歡迎光臨 (http://www.zg4o1577.cn/bbs/)