資源描述:
《各種校驗(yàn)碼校驗(yàn)算法分析》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、各種校驗(yàn)碼校驗(yàn)算法分析二進(jìn)制數(shù)據(jù)經(jīng)過傳送、存取等環(huán)節(jié),會(huì)發(fā)生誤碼(1變成0或0變成1),這就有如何發(fā)現(xiàn)及糾正誤碼的問題。所有解決此類問題的方法就是在原始數(shù)據(jù)(數(shù)碼位)基礎(chǔ)上增加幾位校驗(yàn)(冗余)位。一、碼距一個(gè)編碼系統(tǒng)中任意兩個(gè)合法編碼(碼字)之間不同的二進(jìn)數(shù)位(bit)數(shù)叫這兩個(gè)碼字的碼距,而整個(gè)編碼系統(tǒng)中任意兩個(gè)碼字的的最小距離就是該編碼系統(tǒng)的碼距。如圖1所示的一個(gè)編碼系統(tǒng),用三個(gè)bit來表示八個(gè)不同信息中。在這個(gè)系統(tǒng)中,兩個(gè)碼字之間不同的bit數(shù)從1到3不等,但最小值為1,故這個(gè)系統(tǒng)的碼距為1。如果任何碼字中一位或多位被顛倒了,結(jié)果這個(gè)碼字就不能與其
2、它有效信息區(qū)分開。例如,如果傳送信息001,而被誤收為011,因011仍是表中的合法碼字,接收機(jī)仍將認(rèn)為011是正確的信息。然而,如果用四個(gè)二進(jìn)數(shù)字來編8個(gè)碼字,那么在碼字間的最小距離可以增加到2,如圖2的表中所示。信息序號(hào)二進(jìn)碼字a2a1a000001001201030114100510161107111圖1信息序號(hào)二進(jìn)碼字a3a2a1a00000011001210103001141100501016011071111圖2注意,圖8-2的8個(gè)碼字相互間最少有兩bit的差異。因此,如果任何信息的一個(gè)數(shù)位被顛倒,就成為一個(gè)不用的碼字,接收機(jī)能檢查出來。例如
3、信息是1001,誤收為1011,接收機(jī)知道發(fā)生了一個(gè)差錯(cuò),因?yàn)?011不是一個(gè)碼字(表中沒有)。然而,差錯(cuò)不能被糾正。假定只有一個(gè)數(shù)位是錯(cuò)的,正確碼字可以是1001,1111,0011或1010。接收者不能確定原來到底是這4個(gè)碼字中的那一個(gè)。也可看到,在這個(gè)系統(tǒng)中,偶數(shù)個(gè)(2或4)差錯(cuò)也無法發(fā)現(xiàn)。為了使一個(gè)系統(tǒng)能檢查和糾正一個(gè)差錯(cuò),碼間最小距離必須至少是“3”。最小距離為3時(shí),或能糾正一個(gè)錯(cuò),或能檢二個(gè)錯(cuò),但不能同時(shí)糾一個(gè)錯(cuò)和檢二個(gè)錯(cuò)。編碼信息糾錯(cuò)和檢錯(cuò)能力的進(jìn)一步提高需要進(jìn)一步增加碼字間的最小距離。圖8-3的表概括了最小距離為1至7的碼的糾錯(cuò)和檢錯(cuò)能力
4、。碼距碼能力檢錯(cuò)?糾錯(cuò)12345670???01???02或12加12加23加23加3圖3碼距越大,糾錯(cuò)能力越強(qiáng),但數(shù)據(jù)冗余也越大,即編碼效率低了。所以,選擇碼距要取決于特定系統(tǒng)的參數(shù)。數(shù)字系統(tǒng)的設(shè)計(jì)者必須考慮信息發(fā)生差錯(cuò)的概率和該系統(tǒng)能容許的最小差錯(cuò)率等因素。要有專門的研究來解決這些問題。二、奇偶校驗(yàn)奇偶校驗(yàn)碼是一種增加二進(jìn)制傳輸系統(tǒng)最小距離的簡(jiǎn)單和廣泛采用的方法。例如,單個(gè)的奇偶校驗(yàn)將使碼的最小距離由一增加到二。一個(gè)二進(jìn)制碼字,如果它的碼元有奇數(shù)個(gè)1,就稱為具有奇性。例如,碼字“10110101”有五個(gè)1,因此,這個(gè)碼字具有奇性。同樣,偶性碼字具有偶
5、數(shù)個(gè)1。注意奇性檢測(cè)等效于所有碼元的模二加,并能夠由所有碼元的異或運(yùn)算來確定。對(duì)于一個(gè)n位字,奇性由下式給出:奇性=a0⊕a1⊕a2⊕…⊕an?奇偶校驗(yàn)可描述為:給每一個(gè)碼字加一個(gè)校驗(yàn)位,用它來構(gòu)成奇性或偶性校驗(yàn)。例如,在圖8-2中,就是這樣做的。可以看出,附加碼元d2,是簡(jiǎn)單地用來使每個(gè)字成為偶性的。因此,若有一個(gè)碼元是錯(cuò)的,就可以分辨得出,因?yàn)槠媾夹r?yàn)將成為奇性。奇偶校驗(yàn)編碼通過增加一位校驗(yàn)位來使編碼中1個(gè)個(gè)數(shù)為奇數(shù)(奇校驗(yàn))或者為偶數(shù)(偶校驗(yàn)),從而使碼距變?yōu)?。因?yàn)槠淅玫氖蔷幋a中1的個(gè)數(shù)的奇偶性作為依據(jù),所以不能發(fā)現(xiàn)偶數(shù)位錯(cuò)誤。再以數(shù)字0的七位
6、ASCII碼(0110000)為例,如果傳送后右邊第一位出錯(cuò),0變成1。接收端還認(rèn)為是一個(gè)合法的代碼0110001(數(shù)字1的ASCII碼)。若在最左邊加一位奇校驗(yàn)位,編碼變?yōu)?0110000,如果傳送后右邊第一位出錯(cuò),則變成10110001,1的個(gè)數(shù)變成偶數(shù),就不是合法的奇校驗(yàn)碼了。但若有兩位(假設(shè)是第1、2位)出錯(cuò)就變成10110011,1的個(gè)數(shù)為5,還是奇數(shù)。接收端還認(rèn)為是一個(gè)合法的代碼(數(shù)字3的ASCII碼)。所以奇偶校驗(yàn)不能發(fā)現(xiàn)。奇偶校驗(yàn)位可由硬件電路(異或門)或軟件產(chǎn)生:偶校驗(yàn)位an?=a0⊕a1⊕a2⊕…⊕an-1,?奇校驗(yàn)位an?=NOT(
7、a0⊕a1⊕a2⊕…⊕an-1)。在一個(gè)典型系統(tǒng)里,在傳輸以前,由奇偶發(fā)生器把奇偶校驗(yàn)位加到每個(gè)字中。原有信息中的數(shù)字在接收機(jī)中被檢測(cè),如果沒有出現(xiàn)正確的奇、偶性,這個(gè)信息標(biāo)定為錯(cuò)誤的,這個(gè)系統(tǒng)將把錯(cuò)誤的字拋掉或者請(qǐng)求重發(fā)。在實(shí)際工作中還經(jīng)常采用縱橫都加校驗(yàn)奇偶校驗(yàn)位的編碼系統(tǒng)--分組奇偶校驗(yàn)碼。現(xiàn)在考慮一個(gè)系統(tǒng),它傳輸若干個(gè)長(zhǎng)度為m位的信息。如果把這些信息都編成每組n個(gè)信息的分組,則在這些不同的信息間,也如對(duì)單個(gè)信息一樣,能夠作奇偶校驗(yàn)。圖4中n個(gè)信息的一個(gè)分組排列成矩形式樣,并以橫向奇偶(HP)及縱向奇偶(VP)的形式編出奇偶校驗(yàn)位。m位數(shù)字橫向奇偶
8、位n個(gè)碼字a1a2…am-1amHP1b1b2…bm-1bmHP2c1c2…cm