說明 :
所謂的Hamming code 主要是一種偵測法，它利用資料流中插入一些驗證碼的方式來做一個檢查和驗算。
先取 K bits 的檢查碼：M ≦ 2^n ，K = n + 1。如 8 bits 資料，則 8 ≦ 2^3，K = 3 + 1 = 4，檢查位元為 4 bits。則漢明碼編碼為 M + K = 8 + 4 = 12 bits。
漢明碼編碼的用途是用在資料的除錯，當發生 1 位元的錯誤時，漢明碼編碼規則可以找出錯誤位置。
並透果適當的軟硬體即可修復錯誤，因此常被用於電腦、通訊系統之中。不過有些課本有寫出漢明碼的另一種 SEC-DED 版本。至少知道 SEC-DED 版本需要比原來的漢明碼編碼多1位元檢查碼，即 M ≦ 2^n 時K = n + 2，其他的部份就看不懂了，不曉得是課本爛還是老師不會教。有機會再研究看看漢明碼 SEC-DED 版本。
接下來，我們來用例題來講解，其實這樣會比較清楚。
Ex: Assume that sender sends the dataword 10101101 please find
- the hamming code (H3 H2 H1 H0)
- the codeword
Step1. 建立表格
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
※為什麼有12呢? 明明codeword才8bit而已，那是因為，你還得加上hamming code(h3 h2 h1 h0 ) 所以我們一開始建立的表格要是12格。
Step2.Hamming code 插入的地方通常是2的次方，所以在表格上，2的次方的地方要留下來給Hamming code填
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
H0 |
H1 |
|
H2 |
|
|
|
H3 |
|
|
|
|
Step3.接下來，我們把題目的8bit填進去
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
|
1 |
|
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
|
H0 |
H1 |
|
H2 |
|
|
|
H3 |
|
|
|
|
Step4.接下來，我們將bit數為1的地方，轉成二進制。
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
|
|
1 |
|
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
|
H0 |
H1 |
0011 |
H2 |
|
0110 |
|
H3 |
1001 |
1010 |
|
1100 |
Step5.將這些轉成二進制的地方( 紅色字 )，拿出來做XOR運算。
※XOR運算，直式相加，
如果結果是偶數 (比如說第一行 10100 加起來 = 2 )則為0
如果結果是奇數 (比如說第二行 11010 加起來 = 3 )則為1
則出來的答案就是Hamming code，然後我們將答案反者填回去表格(0101填回去)
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
|
H0 |
H1 |
0011 |
H2 |
|
0110 |
|
H3 |
1001 |
1010 |
|
1100 |
於是我們得出解答
- the hamming code : 1010
- 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
Step1.一樣，我們先把表格建立出來
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
為什麼是10格? 因為1101110101是已經加入hamming code的碼，所以我們有10bit。
Step2.將1101110101填入表格，並且將有1的地方都轉成2進制
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
|
0011 |
0010 |
|
0100 |
0101 |
0110 |
|
1000 |
|
1010 |
Step3.接下來，我們將這些做XOR運算
結果出來的是0110 ，這代表有錯誤，因為如果用hamming code解回去，其結果要為0000。
Step4.
所以我們將0110轉10進制，得出6，6的意思就是代表第六bit有錯誤，於是我們回到表格
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
0011 |
0010 |
|
0100 |
0101 |
0110 |
|
1000 |
|
1010 |
將第6bit從1改成0
於是我們答案就出來了
Ans :
A)which bit is incorrect : the sixth
B)the correct hamming code: 1101100101
基本上看到這邊的人還算有毅力了，接下來，我們寫點跟hamming 有關的 code吧 !
1. convert any base-10 number into binary number
下面是答案!!! 有種別看~~~~~~~~~~~~~~~~~~~~~~~
#include <iostream>
using namespace std;
int conver(int x ,char *bit)
{
int n = 0 ;
while (x > 0 )
{
bit[n++] = x & 0x01;
x >>= 1;
}
return (n); //Return Length
}
void DBG_Print(char * bit, int n)
{
for (n--;n>=0 ;n--)
printf("%d",bit[n]);
printf("\n");
}
int main()
{
int x ,nLenX;
char bit[32];
cin>>x ;
nLenX= conver(x,bit);
DBG_Print(bit,nLenX);
}
2. 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.
class Solution
{
public :
int hammingDistance (int x , int y)
{
int dist = 0 , n = x ^ y ;
while (n)
{
++dist;
n &= n-1;
}
return dist;
}
};
留言列表
Linux (2)
{{ article.title }}