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

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

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

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

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

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

5、制碼多項式的加減運算為⊕模2加運算，即兩個碼多項式相加時，對應項系數進行模2加減。乘除運算與普通多項式類似；模2加減：即各位做不帶進位、借位的按位加減。這種加減運算實際上就是邏輯上的異或運算。即加法和減法等價。碼多項式生成多項式G(x):求CRC碼時所用的“除數”所對應的多項式叫生成多項式。在串行通信中通常使用下列三種生成多項式G（X）來產生CRC碼。CRC-16：G(x)=X16+X15+X2+1，美國二進制同步系統(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碼多項式循環(huán)冗余碼生成器采用模2除法。下圖顯示了這一過程。CRC校驗器的功能完全像發(fā)生器一樣，當收到附加了CRC碼的數據后，做同樣的模2除法。如果余數是全0，則將CRC碼丟棄，接受數據。否則，丟棄收到的數據。6.CRC碼生成器和校驗器CRC校驗碼的生成器和校驗器r個比特0數據g(x)CRC校驗碼r+1r余數先發(fā)數據位后發(fā)校驗位g(x)余數r+1r數據0接收，非0拒絕數據發(fā)送方接收方?0G(X)111010

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

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