奇偶校驗(yàn)+漢明碼

1、奇/偶校驗(yàn)（ECC ）是數(shù)據(jù)傳送時(shí)采用的一種校正數(shù)據(jù)錯(cuò)誤的一種方式，分為奇校驗(yàn)和偶校 驗(yàn)兩種。奇偶校驗(yàn)位是一個(gè)表示給定位數(shù)的二進(jìn)制數(shù)中1的個(gè)數(shù)是奇數(shù)還是偶數(shù)的二進(jìn)制數(shù)。奇偶 校驗(yàn)位是最簡(jiǎn)單的錯(cuò)誤檢測(cè)碼。奇偶校驗(yàn)位有兩種類型：偶校驗(yàn)位與奇校驗(yàn)位。如果一組給 定數(shù)據(jù)位中1的個(gè)數(shù)是奇數(shù)，那么偶校驗(yàn)位就置為1，從而使得總的1的個(gè)數(shù)是偶數(shù)；如 果給定一組數(shù)據(jù)位中1的個(gè)數(shù)是偶數(shù)，那么奇校驗(yàn)位就置為1，使得總的1的個(gè)數(shù)保持奇 數(shù)不變。如果是采用奇校驗(yàn)，在傳送每一個(gè)字節(jié)的時(shí)候另外附加一位作為校驗(yàn)位，校驗(yàn)位在數(shù)據(jù)位前 面，當(dāng)實(shí)際數(shù)據(jù)中“1”的個(gè)數(shù)為偶數(shù)的時(shí)候，這個(gè)校驗(yàn)位就是“1”，否則這個(gè)校驗(yàn)位就是 “0”，這

2、樣就可以保證傳送數(shù)據(jù)滿足奇校驗(yàn)的要求。在接收方收到數(shù)據(jù)時(shí)，將按照奇校驗(yàn)的 要求檢測(cè)數(shù)據(jù)中“ 1”的個(gè)數(shù)，如果是奇數(shù)，表示傳送正確，否則表示傳送錯(cuò)誤。同理偶校驗(yàn)的過程和奇校驗(yàn)的過程一樣，只是檢測(cè)數(shù)據(jù)中“1”的個(gè)數(shù)為奇數(shù)。推理偶校驗(yàn)：當(dāng)實(shí)際數(shù)據(jù)中“1”的個(gè)數(shù)為偶數(shù)的時(shí)候，這個(gè)校驗(yàn)位就是“0”，否則這個(gè)校 驗(yàn)位就是“1”，這樣就可以保證傳送數(shù)據(jù)滿足偶校驗(yàn)的要求。在接收方收到數(shù)據(jù)時(shí)，將按照 偶校驗(yàn)的要求檢測(cè)數(shù)據(jù)中“1”的個(gè)數(shù)，如果是偶數(shù)個(gè)“1”，表示傳送正確，否則表示傳送 錯(cuò)誤。奇校驗(yàn)的英文簡(jiǎn)寫ODD。當(dāng)計(jì)算機(jī)存儲(chǔ)或移動(dòng)數(shù)據(jù)時(shí)，可能會(huì)產(chǎn)生數(shù)據(jù)位錯(cuò)誤，這時(shí)可以利用漢明碼來檢測(cè)并糾錯(cuò)， 簡(jiǎn)單的說，漢明碼是

3、一個(gè)錯(cuò)誤校驗(yàn)碼碼集，由Bell實(shí)驗(yàn)室的R.W.Hamming發(fā)明，因此定名 為海明碼。與其他的錯(cuò)誤校驗(yàn)碼類似，漢明碼也利用了奇偶校驗(yàn)位的概念，通過在數(shù)據(jù)位后面增加一些 比特，可以驗(yàn)證數(shù)據(jù)的有效性。利用一個(gè)以上的校驗(yàn)位，漢明碼不僅可以驗(yàn)證數(shù)據(jù)是否有效， 還能在數(shù)據(jù)出錯(cuò)的情況下指明錯(cuò)誤位置。進(jìn)行奇偶校驗(yàn)的方法是先計(jì)算數(shù)據(jù)中1的個(gè)數(shù)，通過增加一個(gè)0或1（稱為校驗(yàn)位），使1的 個(gè)數(shù)變?yōu)槠鏀?shù)（奇校驗(yàn)）或偶數(shù)（偶校驗(yàn)）。例如，數(shù)據(jù)1001總共是4個(gè)比特位，包括2個(gè)1， 1的數(shù)目是偶數(shù)，因此，如果是偶校驗(yàn)，那么增加的校驗(yàn)位就是一個(gè)0，反之，增加一個(gè)1 作為校驗(yàn)位。通過“異或”運(yùn)算來實(shí)現(xiàn)偶校驗(yàn)，“同或”運(yùn)算來

4、實(shí)現(xiàn)奇校驗(yàn)。單個(gè)比特位的錯(cuò)誤可以通過計(jì)算1的數(shù)目是否正確來檢測(cè)出來，如果1的數(shù)目錯(cuò)誤，說明有 一個(gè)比特位出錯(cuò)，這表示數(shù)據(jù)在傳輸過程中受到噪音影響而出錯(cuò)。利用更多的校驗(yàn)位，漢明 碼可以檢測(cè)兩位碼錯(cuò)，每一位的檢錯(cuò)都通過數(shù)據(jù)中不同的位組合來計(jì)算出來。校驗(yàn)位的數(shù)目 與傳輸數(shù)據(jù)的總位數(shù)有關(guān)，可以通過漢明規(guī)則進(jìn)行計(jì)算：d+p+1=2的p次方d表示傳輸數(shù)據(jù)位數(shù)目，p表示校驗(yàn)位數(shù)目。兩部分合稱漢明碼字，通過將數(shù)據(jù)位與一個(gè)生 成矩陣相乘，可以生成漢明碼字。針對(duì)4位數(shù)據(jù)的漢明碼編碼示意圖漢明碼是一個(gè)在原有數(shù)據(jù)中插入若干校驗(yàn)碼來進(jìn)行錯(cuò)誤檢查和糾正的編碼技術(shù)。以典型 的4位數(shù)據(jù)編碼為例，漢明碼將加入3個(gè)校驗(yàn)碼，從而使

5、實(shí)際傳輸?shù)臄?shù)據(jù)位達(dá)到7個(gè)(位)， 它們的位置如果把上圖中的位置橫過來就是：數(shù)據(jù)位1 2 3 4 5 6 7代碼P1 P2 D8 P3 D4 D2 D1說明第1個(gè)漢明碼第2個(gè)漢明碼第1個(gè)數(shù)據(jù)碼第3個(gè)漢明碼第2個(gè)數(shù)據(jù)碼第3個(gè)數(shù)據(jù)碼第4個(gè)數(shù)據(jù)碼注：Dx中的x是2的整數(shù)幕(下面的幕都是指整數(shù)幕)結(jié)果，多少幕取決于碼位，D1是0 次幕，D8是3次幕，想想二進(jìn)制編碼就知道了。另外，漢明碼加插的位置也是有規(guī)律的。 以四位數(shù)據(jù)為例，第一個(gè)漢明碼是第一位，第二個(gè)是第二位，第三個(gè)是第四位，1、2、4都 是2的整數(shù)幕結(jié)果，而這個(gè)幕次數(shù)是從0開始的整數(shù)。這樣我們可以推斷出來，漢明碼的 插入位置為 1 (20 (注：20 表示 2 的 0 次幕)、2 (21)、4 (22)、8 (23)、16 (24)、32 (25)編碼原理：現(xiàn)以數(shù)據(jù)碼1101為例講講漢明碼的編碼原理，此時(shí)D8=1、D4=1、D2=0、D1=1，在 P1編碼時(shí)，先將D8、D4、D1的二進(jìn)制碼相加，結(jié)果為奇數(shù)3,漢明碼對(duì)奇數(shù)結(jié)果編碼為1, 偶數(shù)結(jié)果為0 （奇數(shù)位。若奇數(shù)結(jié)果編碼為0.偶數(shù)結(jié)果為1,則叫偶數(shù)位），因此P1值為1, D8+D2+D1=2，為偶數(shù)，那么P2值為0，D4+D2+D1=2，為偶數(shù)，P3值為0。這樣，參照 上文的位置表，漢明碼處理的結(jié)果就是1010101。在這個(gè)4