《循環(huán)冗余校驗(yàn)碼》PPT課件

《《循環(huán)冗余校驗(yàn)碼》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、循環(huán)冗余校驗(yàn)編碼（CRC）CyclicRedundancychecking(CRC)循環(huán)冗余校驗(yàn)，又稱多項(xiàng)式碼。在循環(huán)冗余校驗(yàn)中，不是通過(guò)將各比特位相加來(lái)得到期望的校驗(yàn)，而是通過(guò)在數(shù)據(jù)單元末尾加一串冗余比特，稱作循環(huán)冗余校驗(yàn)碼或循環(huán)冗余校驗(yàn)余數(shù)，使得整個(gè)數(shù)據(jù)單元可以被另一個(gè)預(yù)定的二進(jìn)制數(shù)所整除。1.CRC校驗(yàn)基本思想CRC校驗(yàn)的基本思想是：(1)根據(jù)欲發(fā)的k位信息生成一個(gè)r比特的序列，稱為幀校驗(yàn)序列FCS（FramecheckingSeries）。（2）求出實(shí)際發(fā)送的數(shù)據(jù)幀（k+r位），這個(gè)幀所對(duì)應(yīng)二進(jìn)制序列恰好

2、能夠被某個(gè)預(yù)先確定的數(shù)（生成多項(xiàng)式）整除。（3）接收器用相同的數(shù)（生成多項(xiàng)式）去除傳來(lái)的幀。如果無(wú)余數(shù)，則認(rèn)為無(wú)差錯(cuò)；如果余數(shù)不為0，剛認(rèn)為傳輸出錯(cuò)。奇偶校驗(yàn)對(duì)一個(gè)字符校驗(yàn)一次，適合異步通訊；而CRC對(duì)一個(gè)數(shù)據(jù)塊（frame）校驗(yàn)一次，適合同步通訊。在串行同步通信中，幾乎都使用這種校驗(yàn)方法。如磁盤(pán)信息的讀/寫(xiě)等。2.CRC校驗(yàn)常用場(chǎng)合CRC碼生成和校驗(yàn)基本分為三步：第一步：在數(shù)據(jù)單元(k位）的末尾加上r個(gè)0。r是一個(gè)比預(yù)定除數(shù)的比特位數(shù)(r+1)少1的數(shù)。第二步：采用二進(jìn)制除法將新的加長(zhǎng)的數(shù)據(jù)單元（k+r位)除以

3、除數(shù)。由此除法產(chǎn)生的余數(shù)就是循環(huán)冗余碼校驗(yàn)碼。3.CRC碼的生成第三步：求CRC循環(huán)冗余校驗(yàn)碼(K+r)被除數(shù)+r(余數(shù))如果余數(shù)位數(shù)小于r，最左的缺省位數(shù)為0。如果余數(shù)為0,則r=0。CRC碼的生成CRC碼校驗(yàn)：到達(dá)接收方的數(shù)據(jù)單去除以用來(lái)產(chǎn)生循環(huán)冗余校驗(yàn)余數(shù)的G（X）。如果余數(shù)0，將通過(guò)檢驗(yàn)。如果余數(shù)非零，將通不過(guò)檢驗(yàn)。4.CRC碼的校驗(yàn)任何一個(gè)二進(jìn)制數(shù)序列可以和一個(gè)只含有0和1兩個(gè)系數(shù)的代數(shù)多項(xiàng)式建立起一一對(duì)應(yīng)的關(guān)系。因此，用來(lái)求CRC碼的那個(gè)除數(shù)通常用多項(xiàng)式來(lái)表示。原因如下：代數(shù)多項(xiàng)式很短可以通過(guò)多項(xiàng)式來(lái)

4、進(jìn)行概念的數(shù)學(xué)證明。5.多項(xiàng)式多項(xiàng)式任何一個(gè)n位的二進(jìn)制數(shù)都可以用一個(gè)n-1次的多項(xiàng)式來(lái)表示,這種多項(xiàng)式叫碼多項(xiàng)式（又叫信息多項(xiàng)式）。碼多項(xiàng)式與二進(jìn)制序列之間的一一對(duì)應(yīng)關(guān)系：（an-1an-2……a1a0）NA(x)=an-1Xn-1+an-2Xn-2+……+a1X+a0X0碼多項(xiàng)式多項(xiàng)式二進(jìn)制序列實(shí)例以n=3位二進(jìn)制數(shù)為例二進(jìn)制數(shù)對(duì)應(yīng)多項(xiàng)式00000101001110010111101xx+1x2x2+1x2+x+11011011?x6+x4+x3+x+1x5+x4+x2+x?110110碼多項(xiàng)式運(yùn)算法則:二進(jìn)

5、制碼多項(xiàng)式的加減運(yùn)算為⊕模2加運(yùn)算，即兩個(gè)碼多項(xiàng)式相加時(shí)，對(duì)應(yīng)項(xiàng)系數(shù)進(jìn)行模2加減。乘除運(yùn)算與普通多項(xiàng)式類似；模2加減：即各位做不帶進(jìn)位、借位的按位加減。這種加減運(yùn)算實(shí)際上就是邏輯上的異或運(yùn)算。即加法和減法等價(jià)。碼多項(xiàng)式生成多項(xiàng)式G(x):求CRC碼時(shí)所用的“除數(shù)”所對(duì)應(yīng)的多項(xiàng)式叫生成多項(xiàng)式。在串行通信中通常使用下列三種生成多項(xiàng)式G（X）來(lái)產(chǎn)生CRC碼。CRC-16：G(x)=X16+X15+X2+1，美國(guó)二進(jìn)制同步系統(tǒng)中采用。CRC-CCITT：G(x)=X16+X12+X5+1，CCITT推薦。CRC-32：G

6、(x)=X32+X26+X23+X22+X16+X12+X11+X10+X8+1X7+X5+X4+X2+X+1碼多項(xiàng)式循環(huán)冗余碼生成器采用模2除法。下圖顯示了這一過(guò)程。CRC校驗(yàn)器的功能完全像發(fā)生器一樣，當(dāng)收到附加了CRC碼的數(shù)據(jù)后，做同樣的模2除法。如果余數(shù)是全0，則將CRC碼丟棄，接受數(shù)據(jù)。否則，丟棄收到的數(shù)據(jù)。6.CRC碼生成器和校驗(yàn)器CRC校驗(yàn)碼的生成器和校驗(yàn)器r個(gè)比特0數(shù)據(jù)g(x)CRC校驗(yàn)碼r+1r余數(shù)先發(fā)數(shù)據(jù)位后發(fā)校驗(yàn)位g(x)余數(shù)r+1r數(shù)據(jù)0接收，非0拒絕數(shù)據(jù)發(fā)送方接收方?0G(X)111010

7、100011010CRC校驗(yàn)碼信息碼CRC冗余校驗(yàn)碼7.CRC碼性能CRC碼是很有效的差錯(cuò)校驗(yàn)方法。除了正好數(shù)據(jù)塊的比特值是按除數(shù)值變化的錯(cuò)誤外，循環(huán)冗余校驗(yàn)(CRC)將檢測(cè)出其他所有錯(cuò)誤。而且，常用的CRC除數(shù)通常有17，或是33個(gè)比特，使得不可檢測(cè)的錯(cuò)誤可能降低到幾乎近于零。CRC接收電路再配上適當(dāng)?shù)挠布娐凡粌H可以檢錯(cuò)，而且可以糾錯(cuò)，糾錯(cuò)能力很強(qiáng)特別適合檢測(cè)突發(fā)性錯(cuò)誤，在數(shù)據(jù)通信中得到較廣泛的應(yīng)用。檢錯(cuò)性能能檢測(cè)出全部單個(gè)錯(cuò)誤能檢測(cè)出全部隨機(jī)二位錯(cuò)誤能檢測(cè)出全部奇數(shù)個(gè)錯(cuò)誤能檢測(cè)出全部長(zhǎng)度小于k位的突發(fā)錯(cuò)誤能

8、以[1-（1/2）k-1]概率檢測(cè)出長(zhǎng)度為（k+1）位的突發(fā)性錯(cuò)誤課堂練習(xí)題設(shè)某一循環(huán)碼，其生成多項(xiàng)式為G（X）=X5+X2+1，試求出信息序列1101010101011的循環(huán)校驗(yàn)碼CRC（要求寫(xiě)出計(jì)算步驟）。設(shè)某一循環(huán)碼，其生成多項(xiàng)式為G（X）=X5+X4+X2+1，試求出信息序列1010001100的CRC循環(huán)校驗(yàn)碼（要求寫(xiě)出計(jì)算步驟）。