Hamming漢明碼
利用資料流中插入一些驗證碼的方式來做一個檢查和驗算。
1.取 K bits 的檢查碼(K為正整數)
2.M ≦ 2^n(小於或等於資料位原長度)
3.K = n + 1
例如:8 bits 資料,則 8 ≦ 2^3,K = 3 + 1 = 4,檢查位元為 4 bits。則漢明碼編碼長度為 M + K = 8 + 4 = 12 bits。
Ex: Assume that sender sends the dataword 10101101 please find
1.the hamming code (H3 H2 H1 H0)
2.the codeword
例題: 假設發送端送出資料字組為10101101,請找出
1.漢明碼 (H3 H2 H1 H0)
2.編碼字組
Step1. 建立表格。
得加上hamming code(h3 h2 h1 h0 ) 所以一開始建立的表格要是12格。
Step2.Hamming code 插入的地方是2的次方,所以在表格上,2的次方的地方留下來給Hamming code填寫。
2^0=1、2^1=2、2^2=4、2^3=8
Step3.把題目的8bit填進去。
Step4.bit數為1的地方,轉成二進制。
第二列綠色1轉為二進位。
Step5.將這些轉成二進制的地方( 紅色字 ),做XOR運算。
XOR運算,直式相加(多個位元),維持偶數個1。
出來的答案就是Hamming code,將答案依H代號位置填回去表格(0101填回去)
得出解答
1.the hamming code : 1010
2.the codeword : 011001011101
表格填入過程如下:
由接收到的編碼找出有無錯誤
Ex2. Assume that the receiver receives the codeword 1101110101 hamming code , please find A)which bit is incorrect B)the correct codeword
編碼為10位元的漢明碼 1101110101。
Step1.表格建立,10格。
Step2.將1101110101填入表格。
將位元=1的地方都轉成2進制。(此表1的二進位有誤)
Step3.做XOR運算。
結果出來的是0110 ,這代表有錯誤,因為如果用hamming code解回去,其結果要為0000。
這個不是0的數字就是錯誤位元的位置,0110=6、代表第六個位元錯了。
漢明距
The Hamming distance between two integers is the number of positions at which the corresponding bits are different.
Given two integers x and y, calculate the Hamming distance.
Note:
0 ≤ x, y < 231.
Example:
Input: x = 1, y = 4
Output: 2
Explanation:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑
The above arrows point to positions where the corresponding bits are different.
參考文獻