海明碼（Hamming Code）

基本概念

• 對(duì)于連續(xù)比特的檢驗(yàn)有檢錯(cuò)和糾錯(cuò)兩種形式

  檢錯(cuò)編碼：

• 奇偶校驗(yàn)碼
• CRC冗余碼

但是對(duì)于檢錯(cuò)編碼不能找到出錯(cuò)的位置，因此這里介紹一種糾錯(cuò)編碼：海明碼

• 海明碼：

  • 能夠檢查出錯(cuò)位和糾正出錯(cuò)位
  • 其特點(diǎn)為，檢查偶數(shù)位，糾正奇數(shù)位

• 海明不等式：

  2 ^ r - 1 >= k + r

  • r：冗余信息位
  • k：數(shù)據(jù)信息位

基本步驟

• 根據(jù)傳輸?shù)臄?shù)據(jù)和海明不等式得到需要的冗余位個(gè)數(shù)：

  例如：

  ∵ data = 101101【6位即k = 6】

  ∴ 需要的最小冗余碼個(gè)數(shù)位2 ^ r - r >= 7 ==> r = 4

  ∴ 需要4位冗余位

• 將數(shù)據(jù)碼填入正確的位置并留出冗余碼的位置

  冗余碼的位置均為2^i --> 1,2,4,8…

  因此冗余碼對(duì)應(yīng)的數(shù)據(jù)位均只有1位1，其余位均為0，且1的位置逐次升高

  數(shù)據(jù)位置0001【1】0010【2】0011【3】0100【4】0101【5】0110【6】0111【7】1000【8】1001【9】1010【10】

  信息（k）/冗余?	r1	r2	k1	r3	k2	k3	k4	r4	k5	k6
  數(shù)值			1		0	1	1		0	1

• 通過冗余碼的數(shù)據(jù)位置，填充數(shù)組

  一個(gè)冗余碼控制多個(gè)相應(yīng)位置

  每個(gè)冗余碼控制信息位對(duì)應(yīng)位置位1的數(shù)據(jù)位置【由于冗余碼的填充位置為2^i決定】：

  例：

  ? r1 = 0001最低位為1，因此所有數(shù)據(jù)位置最低位為1的位置均受其控制【0011（k1）,0101(k2),0111(k4),1001(k5)】

  填充方法：

  r1 ⊕ k1 ⊕ k2 ⊕ k4 ⊕ k5 = 0 ==> r1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 = 0 ==> r1 = 0

  數(shù)據(jù)位置0001【1】0010【2】0011【3】0100【4】0101【5】0110【6】0111【7】1000【8】1001【9】1010【10】

  信息（k）/冗余?	r1	r2	k1	r3	k2	k3	k4	r4	k5	k6
  數(shù)值	0	0	1	0	0	1	1	1	0	1

• 對(duì)于接收方的校驗(yàn)：

  • 對(duì)于所有檢驗(yàn)位均再次對(duì)應(yīng)異或運(yùn)算：

    例：

    【表格種第五為發(fā)生了錯(cuò)誤】

    重新查看校驗(yàn)碼：

    r1 ⊕ k1 ⊕ k2 ⊕ k4 ⊕ k5 = 1(P1)

    r2 ⊕ k1 ⊕ k3 ⊕ k4 ⊕ k6 = 0(P2)

    r3 ⊕ k2 ⊕ k3 ⊕ k4 = 1(P3)

    r4 ⊕ k5 ⊕ k6 = 0(P4)

    P4P3P2P1 = 0101 = 5即第5位發(fā)生錯(cuò)誤

    數(shù)據(jù)位置0001【1】0010【2】0011【3】0100【4】0101【5】0110【6】0111【7】1000【8】1001【9】1010【10】

    信息（k）/冗余?	r1	r2	k1	r3	k2	k3	k4	r4	k5	k6
    數(shù)值	0	0	1	0	1	1	1	1	0	1

• 將錯(cuò)誤位取反即糾錯(cuò)結(jié)束

總結(jié)

以上是生活随笔為你收集整理的纠错编码【海明码】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。