Hamming Code

Error-correction code (ECC) 是用來在不可靠或有雜訊的通訊頻道上控制資料錯誤的機制，Hamming code 是其中一種經典的 ECC。

基本概念

Hamming code 的核心思想是在資料中加入 parity bit——每個 parity bit 是某一組 data bits 的奇偶校驗值，讓接收端能驗證資料的正確性。

Parity bit 的數量 $p$ 需滿足：

2^{p} \geq n + p + 1

其中 $n$ 是 data bit 的數量。例如 $n = 4$ 時， $p = 3$ （因為 $2^{3} = 8 \geq 4 + 3 + 1 = 8$ ）。

Parity bit 必須放在 2 的次方的位置：位置 1（ $P_{1}$ ）、位置 2（ $P_{2}$ ）、位置 4（ $P_{4}$ ）……以此類推。以 4 個 data bit 的情形，bit string 的排列為 D7, D6, D5, P4, D3, P2, P1。

Parity Bit 計算

Parity bit $P_{i}$ 負責覆蓋所有 bit location 中第 $i$ 個 bit 為 1 的位置。以 4-bit data 的情形：

$P_{1}$ （位置 1，二進位 001）覆蓋位置 1, 3, 5, 7（ $P_{1}$ , D3, D5, D7）
$P_{2}$ （位置 2，二進位 010）覆蓋位置 2, 3, 6, 7（ $P_{2}$ , D3, D6, D7）
$P_{4}$ （位置 4，二進位 100）覆蓋位置 4, 5, 6, 7（ $P_{4}$ , D5, D6, D7）

以 data 1101（D7=1, D6=1, D5=0, D3=1）為例，使用 even parity 計算：

Bit Designation	D7	D6	D5	P4	D3	P2	P1
Bit Location	7	6	5	4	3	2	1
Binary Location	111	110	101	100	011	010	001
Data Bits	1	1	0	—	1	—	—
Parity Bits	—	—	—	0	—	1	0

$P_{1}$ 覆蓋 D7, D5, D3，其中 1 的個數為 2（偶數），所以 $P_{1} = 0$ 。 $P_{2}$ 覆蓋 D7, D6, D3，1 的個數為 3（奇數）， $P_{2} = 1$ 。 $P_{4}$ 覆蓋 D7, D6, D5，1 的個數為 2， $P_{4} = 0$ 。因此完整傳輸的 bit string 為 1100110。

錯誤偵測與修正

接收端重新計算每個 parity group 的 parity。若 $P_{i}$ 校驗失敗，將對應的位元標為 1，最後把這些位元組合成二進位數字，即為發生錯誤的 bit location，將該位置翻轉便完成修正。

以接收到 1100010（bit 3 被翻轉，正確應是 1100110）為例：

$P_{1}$ group（ $P_{1}$ , D3, D5, D7）：1 的個數為 1，奇數，校驗失敗
$P_{2}$ group（ $P_{2}$ , D3, D6, D7）：1 的個數為 3，奇數，校驗失敗
$P_{4}$ group（ $P_{4}$ , D5, D6, D7）：1 的個數為 2，偶數，校驗正確

$P_{1}$ 和 $P_{2}$ 失敗而 $P_{4}$ 正確，錯誤位置為二進位 011，即位置 3（D3）。翻轉 D3 即可還原正確資料。

even 或 odd parity 的選擇不影響正確性，但 encoding 和 decoding 必須使用相同的選擇

Hamming Code 種類

Parity bits	Total bits	Data bits	Name	Rate
2	3	1	Hamming(3,1)	1/3 ≈ 0.333
3	7	4	Hamming(7,4)	4/7 ≈ 0.571
4	15	11	Hamming(15,11)	11/15 ≈ 0.733
5	31	26	Hamming(31,26)	26/31 ≈ 0.839
6	63	57	Hamming(63,57)	57/63 ≈ 0.905
7	127	120	Hamming(127,120)	120/127 ≈ 0.945
8	255	247	Hamming(255,247)	247/255 ≈ 0.969
9	511	502	Hamming(511,502)	502/511 ≈ 0.982

parity bit 數量越多，data bit 佔總 bit 的比例（code rate）越高，overhead 也越低。

Hamming Code 能力

Hamming code 能做兩件事：

偵測到一個 bit flip 並且修正
偵測到兩個 bit flip 但無法修正

但其同時只能做上述兩件事中的一件事，下面的 SECDED 透過再加入一個 parity bit 解決這個問題

SECDED

在 [7,4] 的基礎上再加入一個 overall parity bit 後成為 [8,4] extended Hamming code，即 SECDED（Single Error Correction, Double Error Detection）。SECDED 能夠同時：

detect 且 correct 單一 bit 錯誤
detect（但無法 correct）雙 bit 錯誤

這個 overall parity bit 計算整串 data 的 1 的數量奇偶性

Chilfox

目錄

D-OS-Ch11ec-Hamming_Code

Hamming Code

基本概念

Parity Bit 計算

錯誤偵測與修正

Hamming Code 種類

Hamming Code 能力

SECDED

關係圖譜

反向連結