只要是學電腦、通訊的人都會碰到漢明碼編碼。
我將以前學過的重新整理...
說真的有些書本、網站寫的會讓人看不懂
文檔下載:
http://www.badongo.com/file/2720504
給有需要的人吧
漢明碼編碼
1.先取 K bits 的檢查碼:M ≦ 2^n ,K = n + 1。如 8 bits 資料,則 8 ≦ 2^3,K = 3 + 1 = 4,檢查位元為 4 bits。則漢明碼編碼為 M + K = 8 + 4 = 12 bits。
2.編定位碼位置,並將資料位元填入;檢查位元以 C0、C1、C2、C3、…的順序,變成
C1(2^0)、C2(2^1)、C4(2^2)、C8(2^3)、…的順序依須補在 P1、P2、P4、P8、…的位元位置。補在 2 的 n 次方位置,由 0 次方起算),以資料 1001,0110 為例。
語法:
位元位置 P12 P11 P10 P9 P8 P7 P6 P5 P4 P3 P2 P1
位置編碼 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001
資料位元 1 0 0 1 0 1 1 0
檢查位元 C8 C4 C2 C1
3.依照位元位置,如有資料位元有 1 者,將位置編碼填入相對位置之下表:以Cn為行做 XOR 取偶同位。
語法:
編碼 檢查位元
位元位置 C8 C4 C2 C1
P1 -- -- -- --
P2 -- -- -- --
P3
P4 -- -- -- --
P5 0 1 0 1
P6 0 1 1 0
P7
P8 -- -- -- --
P9 1 0 0 1
P10
P11
P12 1 1 0 0
"XOR
取偶 0 1 1 0
同位"
4.將完成的XOR偶同位結果,回寫入對應位置C1、C2、C4、C8...。
語法:
位元位置 P12 P11 P10 P9 P8 P7 P6 P5 P4 P3 P2 P1
位置編碼 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001
資料位元 1 0 0 1 0 1 1 0
檢查位元 0 1 1 0
最後將得到的結果為 1001,0011,1010,既為漢明碼之編碼。
--------------------------------------------------
驗證漢明碼,例:1001,0011,1010
語法:
位元位置 P12 P11 P10 P9 P8 P7 P6 P5 P4 P3 P2 P1
位置編碼 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001
資料位元 1 0 0 1 0 0 1 1 1 0 1 0
依照位元位置,如有資料位元有 1 者,將位置編碼填入相對位置:
以Cn為行做 XOR 取偶同位。若為 0000 表示正確。若使有數值,
則表示該位元位置的資料錯誤。而錯誤的位元可以用 not 進行修正。
語法:
驗證 檢查位元
位元位置 C8 C4 C2 C1
P1
P2 0 0 1 0
P3
P4 0 1 0 0
P5 0 1 0 1
P6 0 1 1 0
P7
P8
P9 1 0 0 1
P10
P11
P12 1 1 0 0
"XOR
取偶 0 0 0 0
同位"
------------------------------------------
錯誤時:
假設 P5 有錯誤的漢明碼為 1001,0010,1010,如下做驗證
語法:
位元位置 P12 P11 P10 P9 P8 P7 P6 P5 P4 P3 P2 P1
位置編碼 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001
資料位元 1 0 0 1 0 0 1 0 1 0 1 0
語法:
驗證 檢查位元
位元位置 C8 C4 C2 C1
P1
P2 0 0 1 0
P3
P4 0 1 0 0
P5
P6 0 1 1 0
P7
P8
P9 1 0 0 1
P10
P11
P12 1 1 0 0
"XOR
取偶 0 1 0 1
同位"
經驗證,錯誤位置在 0101,既位元位置 P5 的地方。
補充一下:
1.漢明碼編碼的用途是用在資料的除錯,當發生 1 位元的錯誤時,漢明碼編碼規則可以找出錯誤位置。
並透果適當的軟硬體即可修復錯誤,因此常被用於電腦、通訊系統之中。不過有些課本有寫出漢明碼的
另一種 SEC-DED 版本。至少知道 SEC-DED 版本需要比原來的漢明碼編碼多1位元檢查碼,即 M ≦ 2^n 時
K = n + 2,其他的部份就看不懂了,不曉得是課本爛還是老師不會教。有機會再研究看看漢明碼 SEC-DED
版本。
2.從無錯誤的漢明碼中,取出正確的資料位元,很簡當,只要把檢查位元去除即可。
3.有些課本或是網站教學的編碼排列是從 LSD → MSD 由左至右排列,即 P1、P2、P3…,
跟我的教學的 MSD ← LSD 由右至左排列方向的不同,並不會影響實際編碼及校正的結果,
一樣都能夠找出正確的錯誤位元。只是找的起始位置是,LSD → MSD 由左至右排列方向找起;
而 MSD ← LSD 由右至左排列方向找起。
4.驗證 K 位元的檢查碼的檢查公式,在許多課本上寫的:2^K ≦ M + K +1 或是 2^K -1 ≧ M + K ,取最小的 K …。
但是我用 Excel 做出來的驗證表格發現,公式可以改成 M ≦ 2^n 時 K = n + 1。而 M 代表資料位元的個數
K 則是檢查位元的個數。