CRC32算法學(xué)習(xí)筆記以及如何用java實(shí)現(xiàn)

2019-11-18 10:42:08

字體：大中小

供稿：網(wǎng)友

　　一：說明
　　論壇上關(guān)于CRC32校驗(yàn)算法的具體介紹不多。前幾天偶然看到Ross N. Williams的文章，總算把CRC32算法的來龍去脈搞清楚了。本來想把原文翻譯出來，但是時(shí)間參促，只好把自己的一些學(xué)習(xí)心得寫出。這樣大家可以更快的了解CRC32的主要思想。由于水平有限，還懇請大家指正。原文可以訪問：http://www.repairfaq.org/filipg/LINK/F_crc_v31.Html 。
　　
　　二：基本概念及相關(guān)介紹
　　2．1 什么是CRC
　　
　　在遠(yuǎn)距離數(shù)據(jù)通信中，為確保高效而無差錯(cuò)地傳送數(shù)據(jù)，必須對(duì)數(shù)據(jù)進(jìn)行校驗(yàn)即差錯(cuò)控制。循環(huán)冗余校驗(yàn)CRC(Cyclic Redundancy Check/Code)是對(duì)一個(gè)傳送數(shù)據(jù)塊進(jìn)行校驗(yàn)，是一種高效的差錯(cuò)控制方法。
　　
　　CRC校驗(yàn)采用多項(xiàng)式編碼方法。多項(xiàng)式乘除法運(yùn)算過程與普通代數(shù)多項(xiàng)式的乘除法相同。多項(xiàng)式的加減法運(yùn)算以2為模，加減時(shí)不進(jìn)，錯(cuò)位，如同邏輯異或運(yùn)算。
　　
　　2．2 CRC的運(yùn)算規(guī)則
　　
　　CRC加法運(yùn)算規(guī)則：0+0=0
　　
　　0+1=1
　　
　　1+0=1
　　
　　1+1=0 (注重：沒有進(jìn)位)
　　
　　CRC減法運(yùn)算規(guī)則：
　　
　　0-0=0
　　
　　0-1=1
　　
　　1-0=1
　　
　　1-1=0
　　
　　CRC乘法運(yùn)算規(guī)則：
　　
　　0*0=0
　　
　　0*1=0
　　
　　1*0=0
　　
　　1*1=1
　　
　　CRC除法運(yùn)算規(guī)則：
　　
　　1100001010 (注重:我們并不關(guān)心商是多少。)
　　_______________
　　
　　10011 ) 11010110110000
　　
　　10011,,.,,....
　　
　　-----,,.,,....
　　
　　10011,.,,....
　　
　　10011,.,,....
　　
　　-----,.,,....
　　
　　00001.,,....
　　
　　00000.,,....
　　
　　-----.,,....
　　
　　00010,,....
　　
　　00000,,....
　　
　　-----,,....
　　
　　00101,....
　　
　　00000,....
　　
　　-----,....
　　
　　01011....
　　
　　00000....
　　
　　-----....
　　
　　10110...
　　
　　10011...
　　
　　-----...
　　
　　01010..
　　
　　00000..
　　
　　-----..
　　
　　10100.
　　
　　10011.
　　
　　-----.
　　
　　01110
　　
　　00000
　　
　　-----
　　
　　1110 = 余數(shù)
　　
　　2．3 如何生成CRC校驗(yàn)碼
　　
　　(1) 設(shè)G(X)為W階，在數(shù)據(jù)塊末尾添加W個(gè)0，使數(shù)據(jù)塊為M+ W位，則相應(yīng)的多項(xiàng)式為XrM(X)；
　　
　　　　(2) 以2為模，用對(duì)應(yīng)于G(X)的位串去除對(duì)應(yīng)于XrM(X)的位串，求得余數(shù)位串；
　　
　　　　(3) 以2為模，從對(duì)應(yīng)于XrM(X)的位串中減去余數(shù)位串，結(jié)果就是為數(shù)據(jù)塊生成的帶足夠校驗(yàn)信息的CRC校驗(yàn)碼位串。
　　
　　2．4 可能我們會(huì)問那如何選擇G(x)
　　
　　可以說選擇G(x)不是一件很輕易的事。一般我們都使用已經(jīng)被大量的數(shù)據(jù)，時(shí)間檢驗(yàn)過的，正確的，高效的，生成多項(xiàng)式。一般有以下這些：
　　
　　16 bits: (16,12,5,0) [X25 standard]
　　
　　(16,15,2,0) ["CRC-16"]
　　
　　32 bits: (32,26,23,22,16,12,11,10,8,7,5,4,2,1,0) [Ethernet]
　　
　　三: 如何用軟件實(shí)現(xiàn)CRC算法
　　現(xiàn)在我們主要問題就是如何實(shí)現(xiàn)CRC校驗(yàn)，編碼和解碼。用硬件實(shí)現(xiàn)目前是不可能的，我們主要考慮用軟件實(shí)現(xiàn)的方法。
　　
　　以下是對(duì)作者的原文的翻譯：
　　
　　我們假設(shè)有一個(gè)4 bits的寄存器，通過反復(fù)的移位和進(jìn)行CRC的除法，最終該寄存器中的值就是我們所要求的余數(shù)。
　　
　　3 2 1 0 Bits
　　
　　+---+---+---+---+
　　
　　Pop <-- <----- Augmented message（已加0擴(kuò)張的原始數(shù)據(jù)）
　　
　　+---+---+---+---+
　　
　　1 0 1 1 1 = The Poly
　　
　　(注重: The augmented message is the message followed by W zero bits.)
　　
　　依據(jù)這個(gè)模型，我們得到了一個(gè)最最簡單的算法：
　　
　　把register中的值置0.
　　
　　把原始的數(shù)據(jù)后添加r個(gè)0.
　　
　　While (還有剩余沒有處理的數(shù)據(jù))
　　
　　Begin
　　
　　把register中的值左移一位，讀入一個(gè)新的數(shù)據(jù)并置于register的0 bit的位置。

上一篇：編程基礎(chǔ)入門:Java修飾詞的總結(jié)

下一篇：實(shí)際Java編程中的經(jīng)驗(yàn)教訓(xùn)