基于crc的通信信道傳輸差錯(cuò)檢測(cè)

基于crc的通信信道傳輸差錯(cuò)檢測(cè)

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