基于crc的通信信道傳輸差錯檢測

基于crc的通信信道傳輸差錯檢測

在計算機通信過程中，由于信道上存在的各種因素（例如干擾噪聲和熱噪聲等）的影響，傳輸信號的傳輸受到不同程度的干擾。如果嚴(yán)重，錯誤代碼會導(dǎo)致通信失敗。所以應(yīng)該在接收方檢查所接收的數(shù)據(jù)是否正確,可采用多種檢測方法。其中循環(huán)冗余校驗碼(CRC校驗)是目前在計算機網(wǎng)絡(luò)通信及存儲器等方面應(yīng)用最為廣泛的一種校驗編碼方法,是一種強有力的檢測手段。人們將該技術(shù)用于多處數(shù)據(jù)通信系統(tǒng)中,收到了令人滿意的效果。本文從CRC校驗的教學(xué)原理及匯編語言實現(xiàn)兩方面入手,詳細(xì)介紹了CRC校驗方法。1按位疊加編碼CRC檢錯方法的工作原理是:將要發(fā)送的數(shù)據(jù)比特序列當(dāng)做一個多項式K(X)的系數(shù),在發(fā)送端用收發(fā)雙方預(yù)先約定的生成多項式G(x)去除,求得一個余數(shù)多項式R(x)。將余數(shù)多項式加到數(shù)據(jù)多項式之后(稱為T(X))發(fā)送到接收端。在接收端用同樣的生成多項式G(x)去除接收到的數(shù)據(jù)多項式T′(X),如果除得盡,表明無差錯,即T(X)=T′(X);如果除不盡,表明有差錯,即T(X)≠T′(X);余數(shù)將指明出錯位所在位置。CRC是一種線性分組碼,具有較強的糾錯能力并有許多特殊的代數(shù)性質(zhì),前k位為信息碼元,后r位為校驗碼元,他除了具有線性分組碼的封閉性之外,還具有循環(huán)性。其編碼和譯碼電路很容易用移位寄存器實現(xiàn),因而在FEC系統(tǒng)中得到了廣泛的應(yīng)用。現(xiàn)以圖1為例來說明CRC校驗的教學(xué)原理。(1)首先將欲傳送的比特序列K(X)乘以Xr,其中r為R(x)的位數(shù),其值等于G(x)的位數(shù)減1。(2)將乘得的結(jié)果Xr·K(X)用生成多項式G(x)去除,忽略其商,僅將其余數(shù)R(x)取出,并將其與Xr·K(X)相加,得到T(X),即T(X)=Xr·K(X)+R(x)。(3)需要指出的是:在CRC中,采用了一種以按位加減為基礎(chǔ)的模2運算,不考慮進位和錯位,即通過模2減實現(xiàn)模2除,以模2加將所得余數(shù)拼接在被除數(shù)后面,形成一個能除盡的校驗碼。模2加減即按位加減,相當(dāng)于“異或”,可用異或門硬件邏輯實現(xiàn),當(dāng)然也可用軟件實現(xiàn)。舉例如下:⑤以上T(X)即為將要實際傳送的數(shù)據(jù),圖1(b)表示:用接收端收到的T′(X)(T′(X)=T(X))去除G(X),若除盡,則表示傳輸過程中無錯。圖1(c)表示:若第十位出錯,則余數(shù)就不為0。⑥在接收端某位出錯,則余數(shù)不為0,不同位出錯則余數(shù)不同,余數(shù)代碼與出錯位序號之間有惟一的對應(yīng)關(guān)系。通過上例可求出其余數(shù)與出錯位序號之間的對應(yīng)模式(如表1所示),出錯模式只與CRC碼制和生成多項式有關(guān),而與不同待傳碼字代碼無關(guān)。表1對于(10,6)碼具有一定的通用性,可作為其出錯判別依據(jù)。⑦當(dāng)然,對于其他碼制或選用其他生成多項式,出錯模式有可能不同。表1中列舉了11種情況,一種是正確碼字,除后余數(shù)為0,其余10種是依次有位出錯,余數(shù)不為0,與出錯位序號有惟一的對應(yīng)模式。⑧經(jīng)過進一步的研究,我們發(fā)現(xiàn)了一個有實用價值的規(guī)律:如果有一位出錯,用G(x)除后得到一個不為0的余數(shù),如果對該余數(shù)補0,繼續(xù)除,各次余數(shù)將按表1順序循環(huán),例如第十位出錯,余數(shù)0001,補0后繼續(xù)除,得余數(shù)0010,以后將依次為0100,1000,0011,0110,1100,1011,0101,1010,0111,1110,1111,1101,1001,然后又是0001,呈循環(huán)狀。所以稱之為“循環(huán)”碼。⑨循環(huán)冗余校驗碼的檢錯能力取決于生成多項式的選擇,但并不是任何一個多項式都可以作為G(x),若從檢錯糾錯的目的出發(fā),生成多項式應(yīng)能滿足下列要求:任何一位數(shù)據(jù)發(fā)生錯誤時都應(yīng)使余數(shù)不為0,不同位出錯則余數(shù)不同,余數(shù)代碼與出錯位序號之間最好有惟一的對應(yīng)關(guān)系,并滿足余數(shù)循環(huán)規(guī)律。舉例介紹幾種生成多項式:CRC-12,他具有G(x)=x12+x11+x3+x2+1的形式,由12位冗余位組成。CRC-16,其形式為G(x)=x16+x15+x2+1,由16位冗余位組成。CRC-CCITT,其形式為G(x)=x16+x12+x5+1,由16位冗余位組成。2crc校驗算法在數(shù)據(jù)通信中,采用此校驗方法,可使通信的誤碼率大為降低,確保了數(shù)據(jù)通信的可靠性。在程序編制過程中,高級語言的實現(xiàn)較為容易,在此僅給出8031匯編語言的打包與校驗程序。若是對數(shù)據(jù)實行打包,可將數(shù)據(jù)的一組先增加2B的長度,并將這2B清零,經(jīng)CRC計算后,形成2B的冗余位;在接收方,則直接將此數(shù)據(jù)校驗。程序中R1和R2即為冗余位的高8位和低8位,程序中的一些變量如CNTL,CNTH等可用8031的內(nèi)部寄存器,原始數(shù)據(jù)存于@DPTR所指之處。應(yīng)該指出,我們所采用的通信方式通常為異步方式,而CRC屬于同步方式的一種校驗方法,關(guān)于這一點,可先將數(shù)據(jù)放入RAM中,把每一個存儲單元的數(shù)據(jù)看成是同步傳輸數(shù)字序列的8個位來進行處理。CRC校驗程序如下:(1)設(shè)K(X)=x5+x3+x2+1(101101)G(X)=x4+x+1(10011)G(X)為5位,故R(X)應(yīng)為4位。(2)Xr·K(X)=x4(x5+x3+x2+1)=x9+x7+x6+x4(1011010000)(3)算出Xr·K(X)/G(X),取其余數(shù):R(X)=x3+x2+x(1110)(4)將R(X)與XrK(X)相加得到:T(X)(1011011110)盡管CRC校驗的原理相對簡單,但由于不同系統(tǒng)之間存在性能要求、應(yīng)用環(huán)境等差異,造成了CRC校驗在實際上具有多種不同的形式,例如對編碼和校驗速度的要求常通過直接用硬件實現(xiàn)來解決,在沒有