計算機體系結構：海明碼編碼原理與錯誤偵測糾錯實作

海明碼定義

資料校驗編碼。k 位資料位 + r 位冗餘校驗位 = n = k + r 位碼字。可檢測錯誤並定位錯誤位置。

校驗位數計算

條件：2^r - 1 ≥ k + r，取最小整數 r。
範例：k=4 → r=3 (因 2^3-1=7 ≥ 4+3=7)

校驗位位置安排

校驗位置於 2 的冪次方位置：2^0=1、2^1=2、2^2=4、2^3=8...
資料位填入其餘位置。

完整編碼範例：資料 1101

步驟 1：標記位置

位置:  1  2  3  4  5  6  7
      P1 P2 D1 P3 D2 D3 D4
資料:     1  1  0  1

步驟 2：計算校驗位 (XOR 奇偶校驗)

• P1 校驗位置 1,3,5,7：D1⊕D2⊕D4 = 1⊕0⊕1 = 0
• P2 校驗位置 2,3,6,7：D1⊕D3⊕D4 = 1⊕1⊕1 = 1
• P3 校驗位置 4,5,6,7：D2⊕D3⊕D4 = 0⊕1⊕1 = 0

步驟 3：最終海明碼

位置:  1  2  3  4  5  6  7
碼字:  0  1  1  0  0  1  1
→ 0110011 (或寫作 1100110 視端序)

錯誤偵測與糾正 (待續)

接收端重新計算校驗位，結果非零即為錯誤位置碼 (Syndrome)，直接定位錯誤位元並翻轉修正。