汉明码实现原理
汉明码（Hamming Code）是广泛用于内存和磁盘纠错的编码。汉明码不仅可以用来检测转移数据时发生的错误，还可以用来修正错误。（要注意的是，汉明码只能发现和修正一位错误，对于两位或者两位以上的错误无法正确和发现）。
汉明码的实现原则是在原来的数据的插入k位数据作为校验位，把原来的N为数据变为m（m = n +k）位编码。其中编码时要满足以下原则：
这就是Hamming不等式，汉明码规定，我们所得到的m位编码的2^k ( k>=0 && 2^k < m)位上插入特殊的校验码，其余位把源码按顺序放置。
汉明码的编码规则如下：
汉明码编码实例
以10101编码为例，创建一个汉明码编码的空间，并且把源码填入编码的对应位中中，_ _ 1 _ 0 10 _ 1，并留出校验码位（校验位先设为0）。（因为2^4 - 1>= 5+4 && 2^3 - 1 < 5+ 3所以需要4位校验码）
汉明码校验错误实例
我们以上面的编码为例，假设我们现在收到的编码为001101001，我们可以发现汉明码的第8位与原来的汉明码001101011不同，那我们怎么找出这个第8位的错误编码呢？
算法很简单，我们只要在算汉明码校验位的算法的上再算一遍，就得到了汉明码的校验方法，比如计算001101001对应的2^k位。
我们把上述结果反着排列，得到1000，即十进制的8，根据汉明码的校验规则，编码出错的地方即在第8位，我们把第8位的0换成1，即可得原来的编码001101011。
上述的例子是出现在2^k的校验位上的，如果出现在非2^k位上，得到的结果也是一样的，比如：
假设收到的编码为001100011，即第6位出了错误，我们根据规则
我们把上述结果反着排列，得到0110，即十进制的6，根据汉明码的校验规则，编码出错的地方即在第6位，我们把第6位的0换成1，即可得原来的编码001101011。
汉明码的编码和校验的C++实现
通过原理，我们可以很简单地实现汉明码的编码和校验代码
编码：
auto cal(size_t sz)->decltype(auto)
{
decltype(sz) k = ;
decltype(sz) cur = ;
while (cur - < sz + k )
{
cur <<= ;
k++;
}
return k;
}
bool encode(const string &s, string &d)
{
d.clear();
auto k = cal(s.size());
d.resize(s.size() + k);
for (decltype(d.size()) i = , j = , p = ; i!= d.size();i++)
{
if ((i + ) == pow(,p) && p < k)
{
d[i] = '';
p++;
}
else if (s[j] == '' || s[j] == '')
d[i] = s[j++];
else
return false;
}
for (auto i = ; i != k;i++)
{
int count = ,index = << i;
for (auto j = index - ; j < d.size() ;j += index)
for (auto k = ; k!= index && j < d.size(); k++, j++)
count ^= d[j] - '';
d[index - ] = '' + count;
}
return true;
}
解码与校验：
auto antiCal(size_t sz)->decltype(auto)
{
decltype(sz) k = ;
decltype(sz) cur = ;
while (cur < sz)
{
cur <<= ;
k++;
}
return k;
} auto decode(string &s, string &d)->decltype(auto)
{
s.clear();
auto k = antiCal(d.size());
s.resize(d.size() - k); decltype(d.size()) sum = ;
for (decltype(k) p = ;p != k;p++)
{
int pAnti = ;
decltype(k) index = << p;
for (decltype(d.size()) i = index - ;i < d.size(); i+=index)
{
for (auto j = ; j < index && i < d.size(); i++, j++)
pAnti ^= d[i] - '';
}
sum += pAnti << p;
}
if (sum != )
d[sum - ] = (- (int)(d[sum - ] - '')) + ''; for (decltype(d.size()) i = , p = ,j = ; i != d.size(); i++)
{
if ((i + ) == ( << p) && p < k)
p++;
else
s[j++] = d[i];
} return sum;
}
测试样例：
int main()
{
string source, dest;
while (cin >> source)
{
if (encode(source,dest))
{
cout << "Source: " <<source << endl;
cout << "Dest: " << dest << endl;
}
size_t index;
cout << "----input error index : ";
cin >> index;
auto k = dest.size();
if (index != && index <= dest.size())
dest[index - ] = ( - (int)(dest[index - ] - '')) + '';
cout << "Code " << dest <<endl;
auto ret = decode(source,dest);
if (ret == )
{
cout << "Source: " <<source << endl;
cout << "Dest: " <<dest << endl;
}
else
{
cout << "Error index "<< ret << endl;
cout << "Corret source: " <<source << endl;
cout << "Corret dest: " <<dest << endl;
}
cout << endl;
}
return ;
} Source:
Dest:
----input error index :
Code
Error index
Corret source:
Corret dest: 001101011 Source:
Dest:
----input error index :
Code
Error index
Corret source:
Corret dest: 1111001101010100101010101111110101101 Source:
Dest:
----input error index :
Code
Source:
Dest: