[計概]Hamming Code 漢明碼

這次要說的是漢明碼，這東西完全沒印象，大概以前讀書時想說帶過就好，不會考也不會用到。

Hamming code is a set of error-correction codes that can be used to detect and correct the errors that can occur when the data is moved or stored from the sender to the receiver.

就是一種錯誤檢查碼，在資料中插入一些檢查碼，看看傳輸過程中有沒有發生錯誤

Hamming code要多長？
公式：2^k ≥ N+k+1，N:資料長度，k: Hamming code長度

直接看題目會比較好理解

EX: 一個二進位值為10101111的8 bits位元組，以偶數同位的漢明碼予以編碼， 以下何者為正確的編碼後二進位值?

Step 1. 先求Hamming code長度
根據上面提到的公式，2^k ≥ 8+k+1，可以求出k=4
也就是說加上Hamming code之後會有12 bits

Step 2. 畫張表格
有12 bits，所以畫12格

重點：Hamming code要填在2的冪次的位置，所以這個例子1、2、4、8格要留空，接著再將原先的值填入表格

Step 3. 求Hamming code
畫一個計算用的圖，將Hamming code的bit欄位由大到小排列，然後將bit數為1的欄位轉成二進制寫出來

將上面紅色的值做XOR運算，其實只要看1有幾個就可以算出來，
偶數個1則為0，奇數個1則為1

現在可以知道我們的Hamming code是0001

Step 4. 將Hamming code填入表中
對照算式上面的欄位，依序將值填入8、4、2、1欄

由此可知，編碼後的二進制值為101001001111

現在來看編碼後的值要怎麼糾錯並改正

EX: 一個漢明碼編碼後的值為1101110101， 請問哪個bit有錯誤，並將其更正

Step 1. 畫張表格
有10 bits，那就畫10格

Step 2. 把bit為1的欄位轉成二進制，做XOR運算

求出來的值為0110，也就是6，表示第6個bit有錯誤
如果沒錯誤的話，求出的值會是0000

Step 3. 更正
將原先數值的第6個bit由1改成0 (反之亦然)
1101110101 -> 1101100101

這兩題算是基本的漢明碼題目，過程不難，但計算上不能大意，一個地方算錯、目小看錯就整題葬送了