奇偶校驗+漢明碼

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

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

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

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

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