100模擬 Problem 3-2：漢明碼(Haming Code)

漢明碼(Haming Code)
1. 具有自動偵錯與更正錯誤一個位元的功能，兩個位元有誤只能偵測。
2. m個位元資料，須 r 個同位元查出錯誤。 m+r+1≦2^r
3. 同位元(Parity)放置位置為2^(r-1)
m：資料位元長度 r：檢查位元長度 (2^r) n：總傳送位元數 ( n= m+ r )
舉例來說，如果需要傳送7 個位元 110 0001 資料，則 m = 7，7+4+1 < =2^4，r= 4，n = 7 + 4，
檢查位元需要4 個位元。
同位元檢查，分為兩種，一種為奇同位檢查另一種為偶同位檢查，以偶同位例子來說，
0110110，已經有4 個1，所以偶同位元就填入0，資料加偶同位為01101100。接下來的計算
都用偶同位。
假設，要傳的字元為a，對應到7 個位元的ASCII 為110 0001，則其漢明碼的檢查碼分別為1011
但是要跳過為 1 2 4 8 這幾個位置，如下圖：
位置 1 2 3 4 5 6 7 8 9 10 11
P1 P2 1 P3 1 0 0 P4 0 0 1
目前檢查位元P1 P2 P3 P4 是未知的，需要透過同位元檢查來取得，如下圖：
位置 二進位數字
1 0 0 0 P1
2 0 0 P2 0
3 0 0 1 1
4 0 P3 0 0
5 0 1 0 1
6 0 0 0 0
7 0 0 0 0
8 P4 0 0 0
9 0 0 0 0
10 0 0 0 0
11 1 0 1 1
同位元檢查 1 1 0 1
要注意的是位置3、5、11 為1，所以在二進位數字那邊就要填入0011、0101、1011 其他填0000。
同位元檢查那邊以P1 那一欄來說，那一欄一共有3 個1，所以P1 需要填入1，P2P3P4 以此類
推，字元為a， ASCII 為110 0001，漢明碼P1P2P3P4 檢查碼為1011，最後所傳送的資料為
10111001001。
第 10 頁，共 13 頁
輸入說明：
第1 行的數字n 代表有幾筆字元資料要計算，接下來資料為傳送字元[a-zA-Z0-9]。
輸出說明：
輸出為字元對應的漢明碼P1P2P3P4 檢查碼。
輸入範例：【檔名：in-3-2-1.txt】
3
H
a
m
輸入範例：【檔名：in-3-2-2.txt】
2
c
e
輸出範例：【檔名：out-3-2.txt】
0010
1011
1100
1110
0010