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

 找回密碼
 立即注冊(cè)

QQ登錄

只需一步,快速開始

搜索
查看: 6505|回復(fù): 2
打印 上一主題 下一主題
收起左側(cè)

最通俗的CRC校驗(yàn)原理剖析

[復(fù)制鏈接]
跳轉(zhuǎn)到指定樓層
樓主
    以下內(nèi)容摘自筆者即將出版的最新著作《深入理解計(jì)算機(jī)網(wǎng)絡(luò)》一書。本書將于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)原理看起來比較復(fù)雜,好難懂,因?yàn)榇蠖鄶?shù)書上基本上是以二進(jìn)制的多項(xiàng)式形式來說明的。其實(shí)很簡單的問題,其根本思想就是先在要發(fā)送的幀后面附加一個(gè)數(shù)(這個(gè)就是用來校驗(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ù)幀之前就已通過附加一個(gè)數(shù),做了“去余”處理(也就已經(jīng)能整除了),所以結(jié)果應(yīng)該是沒有余數(shù)。如果有余數(shù),則表明該幀在傳輸過程中出現(xiàn)了差錯(cuò)。
     【說明】“模2除法”與“算術(shù)除法”類似,但它既不向上位借位,也不比較除數(shù)和被除數(shù)的相同位數(shù)值的大小,只要以相同位數(shù)進(jìn)行相除即可。模2加法運(yùn)算為:1+1=0,0+1=1,0+0=0,無進(jìn)位,也無借位;模2減法運(yùn)算為:1-1=0,0-1=1,1-0=1,0-0=0,也無進(jìn)位,無借位。相當(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乘法”示例
     具體來說,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ù),如果沒有余數(shù),則表明該幀在傳輸過程中沒出錯(cuò),否則出現(xiàn)了差錯(cuò)。
    通過以上介紹,大家一定可以理解CRC校驗(yàn)的原理,并且不再認(rèn)為很復(fù)雜吧。
    從上面可以看出,CRC校驗(yàn)中有兩個(gè)關(guān)鍵點(diǎn):一是要預(yù)先確定一個(gè)發(fā)送端和接收端都用來作為除數(shù)的二進(jìn)制比特串(或多項(xiàng)式);二是把原始幀與上面選定的除進(jìn)行二進(jìn)制除法運(yùn)算,計(jì)算出FCS。前者可以隨機(jī)選擇,也可按國際上通行的標(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è)例子來具體說明整個(gè)過程。現(xiàn)假設(shè)選擇的CRC生成多項(xiàng)式為G(X) = X4 + X3 + 1,要求出二進(jìn)制序列10110011的CRC校驗(yàn)碼。下面是具體的計(jì)算過程:
   (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ù)在傳輸過程中沒有出現(xiàn)差錯(cuò),否則出現(xiàn)了差錯(cuò)。
    通過以上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)碼是多少。

評(píng)分

參與人數(shù) 1黑幣 +8 收起 理由
Mr_Shier + 8 絕世好帖!

查看全部評(píng)分

分享到:  QQ好友和群QQ好友和群 QQ空間QQ空間 騰訊微博騰訊微博 騰訊朋友騰訊朋友
收藏收藏1 分享淘帖 頂 踩
回復(fù)

使用道具 舉報(bào)

沙發(fā)
ID:317482 發(fā)表于 2018-5-15 22:39 | 只看該作者
謝謝分享
回復(fù)

使用道具 舉報(bào)

板凳
ID:328014 發(fā)表于 2018-9-23 15:08 | 只看該作者
很好的科普貼,確實(shí)寫得比較通俗易懂
回復(fù)

使用道具 舉報(bào)

本版積分規(guī)則

手機(jī)版|小黑屋|51黑電子論壇 |51黑電子論壇6群 QQ 管理員QQ:125739409;技術(shù)交流QQ群281945664

Powered by 單片機(jī)教程網(wǎng)

快速回復(fù) 返回頂部 返回列表
主站蜘蛛池模板: 亚洲精品一区二区三区蜜桃久 | 欧美日韩视频网站 | 一区二区三区四区不卡 | 日韩视频成人 | 中文一区二区视频 | 成人欧美一区二区三区在线观看 | 精品国产一区二区三区性色av | 日韩在线h | 日日操网站 | 一区二区三区国产好的精 | 日日操操 | 久久国产精品-国产精品 | 91网站在线观看视频 | 日韩三级 | 91福利在线观看 | 色橹橹欧美在线观看视频高清 | com.国产| 国产一级特黄视频 | 黄色国产| 日本一区二区高清不卡 | 国产精品女人久久久 | 日韩色图在线观看 | 99久久精品免费看国产四区 | 亚洲一区不卡在线 | av手机免费在线观看 | 久久艹av| 在线免费亚洲视频 | av天天看| 激情的网站 | 久久精品国产一区老色匹 | 国产精品亚洲综合 | 成年人免费网站 | 久久久久久久综合色一本 | 看真人视频一级毛片 | 亚洲成人精品久久 | 欧美黄色网络 | 日本三级日产三级国产三级 | 国产在线一区二 | 久久国产区 | 久久综合一区 | 国产免费又色又爽又黄在线观看 |