海明 校驗(yàn) 碼數(shù)據(jù) 校驗(yàn) 碼

《海明 校驗(yàn) 碼數(shù)據(jù) 校驗(yàn) 碼》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、海明校驗(yàn)碼數(shù)據(jù)校驗(yàn)碼版權(quán)聲明:轉(zhuǎn)載時(shí)請(qǐng)以超鏈接形式標(biāo)明文章原始出處和作者信息及本聲明海明校驗(yàn)碼數(shù)據(jù)校驗(yàn)碼摘要:在計(jì)算機(jī)網(wǎng)絡(luò)與通信及計(jì)算機(jī)內(nèi)部常涉及到數(shù)據(jù)通信，為了保證傳輸?shù)臄?shù)據(jù)的正確性，常涉及到傳輸數(shù)據(jù)的校驗(yàn)與糾錯(cuò)，本文旨在歸納比較各種常用的數(shù)據(jù)校驗(yàn)碼，達(dá)到對(duì)數(shù)據(jù)校驗(yàn)的進(jìn)一步認(rèn)識(shí)了解，便于在實(shí)際中運(yùn)用。數(shù)據(jù)校驗(yàn):計(jì)算機(jī)系統(tǒng)中的數(shù)據(jù)，在讀寫(xiě)、存取和傳送的過(guò)程中可能產(chǎn)生錯(cuò)誤。為了減少和避免這類錯(cuò)誤，一方面是精心設(shè)計(jì)各種電路，提高計(jì)算機(jī)硬件的可靠性，另一方面是在數(shù)據(jù)編碼上找出路，即采用某種編碼方法，通過(guò)少量的附加電路，使之能發(fā)現(xiàn)某些錯(cuò)誤，甚至能確定出錯(cuò)位置，進(jìn)

2、而實(shí)現(xiàn)自動(dòng)改錯(cuò)的能力。通俗的說(shuō)，就是為保證數(shù)據(jù)的完整性，用一種指定的算法對(duì)原始數(shù)據(jù)計(jì)算出的一個(gè)校驗(yàn)值。接收方用同樣的算法計(jì)算一次校驗(yàn)值，如果和隨數(shù)據(jù)提供的校驗(yàn)值一樣，就說(shuō)明數(shù)據(jù)是完整的。編碼糾錯(cuò)理論:任何一種編碼是否具有檢測(cè)能力和糾錯(cuò)能力，都與編碼的最小距離有關(guān)。所謂的編碼最小距離是指在一種編碼系統(tǒng)中，任意兩組合法碼之間的最少二進(jìn)制位數(shù)的差異。數(shù)據(jù)校驗(yàn)碼:數(shù)據(jù)校驗(yàn)碼是一種常用的帶有發(fā)現(xiàn)某些錯(cuò)誤或自動(dòng)改錯(cuò)能力的數(shù)據(jù)編碼方法。常用的數(shù)據(jù)校驗(yàn)碼:一，奇偶校驗(yàn)碼:奇偶校驗(yàn)碼是一種開(kāi)銷最小，能發(fā)現(xiàn)數(shù)據(jù)代碼中一位出錯(cuò)情況的編碼。常用于存儲(chǔ)器讀寫(xiě)檢查，或ASCII字符

3、傳送過(guò)程中的檢查。實(shí)現(xiàn)原理:使碼距(兩個(gè)碼組對(duì)應(yīng)位上數(shù)字的不同位的個(gè)數(shù)稱為碼組的距離,簡(jiǎn)稱碼距)由增加到2。實(shí)現(xiàn)的具體方法:通常為一個(gè)字節(jié)補(bǔ)充一個(gè)二進(jìn)制位，稱為校驗(yàn)位，用設(shè)置校驗(yàn)位的值為0或1，使字節(jié)的8位和該校驗(yàn)位含有1值的個(gè)數(shù)為奇數(shù)或偶數(shù)。在使用奇數(shù)個(gè)1的方案進(jìn)行校驗(yàn)時(shí)，稱為奇校驗(yàn);反之，稱為偶校驗(yàn)。例如ASCII碼使7位或8位二進(jìn)制數(shù)組合來(lái)表示128或256種可能的字符。標(biāo)準(zhǔn)ASCII碼也叫基礎(chǔ)ASCII碼，使用7位二進(jìn)制數(shù)來(lái)表示所有的大寫(xiě)和小寫(xiě)字母，數(shù)字0到9、標(biāo)點(diǎn)符號(hào)，以及在美式英語(yǔ)中使用的特殊控制字符。在標(biāo)準(zhǔn)ASCII中，其最高位(b7)用作

4、奇偶校驗(yàn)位;具體的實(shí)現(xiàn)代碼:#includemain(){inti,j,count=0,e=0,f=0,g,m,n;chara[100][100];scanf(%d%d,n,m);getchar();//用來(lái)消除回車for(i=0;i{scanf(%s,a[i]);a[i][m]='[message]';}for(i=0;i{for(j=0;j{if(a[i][j]=='1')count++;}if(count%2==1){e++;count=0;}for(j=0;j{for(i=0;i{if(a[i][j]=='1')count++;}if(count

5、%2==1){f++;count=0;}g=ef?e:f;printf(e=%df=%dg=%d,e,f,g);}二，循環(huán)冗余校驗(yàn)碼(CRC)CRC(cyclicredundancycheck)碼可以發(fā)現(xiàn)并糾正信息存儲(chǔ)或傳送過(guò)程中連續(xù)出現(xiàn)的多位錯(cuò)誤，因此在磁介質(zhì)存儲(chǔ)和計(jì)算機(jī)之間通信方面得到廣泛應(yīng)用。CRC碼用到模2運(yùn)算:1)模2加減:0+1=1;0+0=0;1+0=1;1+1=0;2)模2乘:按模2加求部分積之和;3)模2除:按模2減求部分余數(shù);實(shí)現(xiàn)原理:生成CRC碼:CRC碼是用多項(xiàng)式M(x)*xr除以稱為G(x)(產(chǎn)生校驗(yàn)的多項(xiàng)式又稱為生成多項(xiàng)式)所

6、得余數(shù)作為校驗(yàn)位的(模2運(yùn)算)。為了得到r位余數(shù)(校驗(yàn)位)，G(x)必須是r+1位。CRC的譯碼與糾錯(cuò):接收到的循環(huán)校驗(yàn)碼用約定的生成多項(xiàng)式G(x)去除，如果碼字無(wú)誤則余數(shù)應(yīng)為0，如有一位出錯(cuò)，則余數(shù)不為0，不同位數(shù)出錯(cuò)余數(shù)不同。對(duì)照相應(yīng)的出錯(cuò)模式可以找到相應(yīng)的出錯(cuò)位。適用范圍:CRC-12碼通常用來(lái)傳送6-bit字符串;CRC-16及CRC-CCITT碼則用是來(lái)傳送8-bit字符。CRC-32:硬盤(pán)數(shù)據(jù)，網(wǎng)絡(luò)傳輸?shù)葢?yīng)用例子:rar,以太網(wǎng)卡芯片、MPEG解碼芯片中三，海明校驗(yàn)碼由RichardHamming于1950年提出、目前還被廣泛采用的一種很有效

7、的校驗(yàn)方法，是只要增加少數(shù)幾個(gè)校驗(yàn)位，就能檢測(cè)出二位同時(shí)出錯(cuò)、亦能檢測(cè)出一位出錯(cuò)并能自動(dòng)恢復(fù)該出錯(cuò)位的正確值的有效手段，后者被稱為自動(dòng)糾錯(cuò)。基本思想:將有效信息按某種規(guī)律分成若干組，每組安排一個(gè)校驗(yàn)位，做奇偶測(cè)試，就能提供多位檢錯(cuò)信息，以指出最大可能是哪位出錯(cuò)，從而將其糾正。實(shí)質(zhì)上，海明校驗(yàn)是一種多重校驗(yàn)。具體實(shí)現(xiàn):生成有效碼;步驟一:求校驗(yàn)位數(shù)k;設(shè)欲檢測(cè)的二進(jìn)制代碼為n位，為使其具有糾錯(cuò)能力，需增加k位檢測(cè)位，組成n+k位的代碼。為了能準(zhǔn)確對(duì)錯(cuò)誤定位及指出代碼沒(méi)錯(cuò)，新增添的檢測(cè)位數(shù)k應(yīng)滿足:2k=n+k+1;由此公式可由的欲檢測(cè)的二進(jìn)制代碼位數(shù)n求得

8、相應(yīng)的所需的校驗(yàn)位數(shù)k;步驟二:求被送代碼(有效信息)所在的位置設(shè)n+k位代碼自