漢明碼是Richard Hamming于1950年提出的。是目前廣泛采用的一種有效的校驗碼域庇，其中，主存的ECC(Error Correcting Code)采用的就是類似的校驗碼赠摇。
基本原理
將有效的信息按某種規(guī)律分成若干組货徙，每組安排一個校驗位，做奇偶測試晨仑，就能提供多位檢錯信息褐墅，以指出最大可能是哪位出錯，從而將其糾正洪己。實質(zhì)上妥凳，漢明校驗碼是一種多重校驗。
----摘自百度百科
這個分組的思想有點不是很理解答捕。
在有效信息位種中加入幾個校驗位形成漢明碼逝钥，使碼距比較均勻的增大，并把漢明碼的每一個二進制位分配到幾個奇偶校驗組中拱镐。
以下使用P代表校驗位艘款，H代表漢明碼，D代表原始信息位沃琅，N位信息位的位數(shù)哗咆，K位校驗位的位數(shù)。
則N與K的關(guān)系為2^(K-1) >=N+K+1,如下表:
| N | K |
|---|---|
| 1~3 | 4 |
| 4~10 | 5 |
| 11~25 | 6 |
| 26~56 | 7 |
| 57~119 | 8 |
分組原則
- 信息位和校驗位之和為m,每個校驗位Pi在漢明碼中被分到位號為2^(i-1)的位置上益眉，其余各位為信息位
- 漢明碼每一位Hi有多個校驗位校驗晌柬，其關(guān)系是被校驗的每一位位號等于校驗它的各校驗位的位號之和，即漢明碼的實質(zhì)是參與校驗的各校驗位權(quán)之和郭脂。 這句話理解起來有點別扭年碘，看下面例子。
- 在增大碼距時展鸡，應(yīng)使所有編碼的碼距盡量均勻地增大屿衅，以保證對所有代碼的檢測能力平衡的提高
例子
編碼
假設(shè)原始數(shù)據(jù)信息位的位數(shù)為8，那么他需要的K值位5娱颊，即需要有5個校驗位傲诵，組成的漢明碼的位數(shù)為13.再根據(jù)校驗位的分配原則凯砍，組成的漢明碼如下：
|位|13| 12| 11 |10| 9| 8| 7 |6| 5| 4| 3| 2| 1|
|-|-|-|-|-|-|-|-|-|-|-|-|-|
|漢明碼|P5| D8| D7| D6 | D5| P4| D4| D3| D2| P3| D1| P2| P1|
P5本來應(yīng)該是放在第16位的，但是由于生成的漢明碼位數(shù)為13所以它就被挪到的第13位了拴竹。
那么怎么確定校驗?zāi)匚蝰茫孔畛跻怖_我許久。
先看一個表格：
其中H的下標代表在漢明碼中的位置栓拜，也是P4P3P2P1組成的-十進制數(shù)
| P5 | P4 | P3 | P2 | P1 | H | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | H1 | P1 | |
| 0 | 0 | 1 | 0 | H2 | P2 | |
| 0 | 0 | 1 | 1 | H3 | D1 | |
| 0 | 1 | 0 | 0 | H4 | P3 | |
| 0 | 1 | 0 | 1 | H5 | D2 | |
| 0 | 1 | 1 | 0 | H6 | D3 | |
| 0 | 1 | 1 | 1 | H7 | D4 | |
| 1 | 0 | 0 | 0 | H8 | P4 | |
| 1 | 0 | 0 | 1 | H9 | D5 | |
| 1 | 0 | 1 | 0 | H10 | D6 | |
| 1 | 0 | 1 | 1 | H11 | D7 | |
| 1 | 1 | 0 | 0 | H12 | D8 | |
| 1 | 1 | 0 | 1 | H13 | P5 |
校驗位Pi的偶校驗結(jié)果就是:
P1 = D1 ^ D2 ^ D4 ^ D5 ^ D7
P2 = D1 ^ D3 ^ D4 ^ D6 ^ D7
P3 = D2 ^ D3 ^ D4 ^ D8
P4 = D5 ^ D6 ^ D7 ^D8
如果是奇校驗的話上面的結(jié)果取反就是了座泳。
那么還有P5呢？上面的結(jié)果中幕与，D4挑势，D7出現(xiàn)了3次，而D1啦鸣，D2潮饱，D3，D5诫给，D6香拉，D8僅出現(xiàn)了2次，為了使其各個信息位在校驗中均勻的出現(xiàn)校驗中狂，從而定義P5 = D1 ^ D2 ^ D3 ^ D5 ^ D6 ^D8,這樣凫碌，每一位信息位都均勻的出現(xiàn)在3個Pi值得形成關(guān)系中，當任意一位信息位變化的時候都會引起3個P值得變化胃榕，即合法漢明碼的碼距為4 (前面都懂盛险，這個碼距為4有點想不明白)
這就是編碼了。
現(xiàn)在再來看看這句話
漢明碼每一位Hi有多個校驗位校驗勋又，其關(guān)系是被校驗的每一位位號等于校驗它的各校驗位的位號之和苦掘，即漢明碼的實質(zhì)是參與校驗的各校驗位權(quán)之和。
P1楔壤，P2鸟蜡，P3，P4挺邀，P5的位數(shù)分別為1,2,4,8,13
D1的漢明碼位數(shù)為3，3 = 2 + 1所以D1會被P1跳座，P2兩個校驗位所校驗端铛。
| 漢明碼的信息位 | 漢明碼的位數(shù) | 被校驗位 | 說明 |
|---|---|---|---|
| D1 | 3 = 1 + 2 | P1,P2 | D1信息位會被校驗位P1，P2所校驗疲眷。 |
| D2 | 5 = 1 + 4 | P1,P3 | |
| D3 | 6 = 2 + 4 | P2,P3 | |
| D4 | 7 = 1 + 2 +4 | P1,P2,P3 | |
| D5 | 9 = 1+ 8 | P1,P4 | |
| D6 | 10 = 2 + 8 | P2,P4 | |
| D7 | 11 = 1 + 2 +8 | P1,P2,P4 | |
| D8 | 12 = 4 + 8 | P3,P4 |
根據(jù)偶校驗結(jié)果以及上應(yīng)該就清楚了禾蚕。
校驗
將收到的漢明碼進行偶校驗(當然也可以進行奇校驗，前提是前面編碼的時候使用的是奇校驗)
S1 = P1 ^ D1 ^ D2 ^ D4 ^ D5 ^ D7
S2 = P2 ^ D1 ^ D3 ^ D4 ^ D6 ^ D7
S3 = P3 ^ D2 ^ D3 ^ D4 ^ D8
S4 = P4 ^ D5 ^ D6 ^ D7 ^D8
S5 = P5 ^ D1 ^ D2 ^ D3 ^ D5 ^ D6 ^D8
漢明碼出錯情況:
記錄 S = S5 S4 S3 S2 S1
- S為00000時代表無錯
- 有一位不為0,表明某一校驗位出錯或者三位漢明碼(信息位和校驗位)同時出錯
- 兩位不為0狂丝，表明兩位漢明碼同時出錯换淆，此時只能發(fā)現(xiàn)錯誤無法確定錯誤的位置
- 3位不為0哗总，表明一位信息位出錯或者3位校驗位同時出錯
- 4/5位不為0，表明出錯情況嚴重倍试，系統(tǒng)可能出現(xiàn)故障讯屈，應(yīng)檢查系統(tǒng)硬件的正確性
以上結(jié)果分析基于偶校驗。
|漢明碼||P5| D8| D7| D6 | D5| P4| D4| D3| D2| P3| D1| P2| P1|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|出錯位號||H13| H12| H11 |H10|H9| H8| H7 |H6| H5| H4| H3| H2|H1|
||S5|1|1|0|1|1|0|0|1|1|0|1|0|0|
||S4|0|1|1|1|1|1|0|0|0|0|0|0|0|
||S3|0|1|0|0|0|0|1|1|1|1|0|0|0|
||S2|0|0|1|1|0|0|1|1|0|0|1|1|0|
||S1|0|0|1|0|1|0|1|0|1|0|1|0|1|
