海明码编码和校验原理与实现

海明编码与检验原由
以内存为例，如果内存所处的电磁环境比较复杂，或者空间环境下受到带电粒子的打击，那么可能导致电容的充放电或者触发器的翻转（SRAM）。这样会导致存储信息的改变。如果不校验，存储中存储的程序可能不会发挥它应有的作用，甚至会发生严重的后果。

编码的最小距离
任意两组合法代码之间二进制位数的最小差异、编码的纠错、改错能力与编码的最小距离有关。编码的最小距离就是从一种合法代码转化成另外一种合法代码所变化的最小位数。存在如下公式：
$L-1=C+D(D\geq C)$ 汉明码是一种具有纠错能力的编码。其中:

$L:$ 编码的最小距离
$D:$ 检测错误的位数（信息位）
$C:$ 纠正错误的位数（校验位或冗余位）

冗余位
冗余位”是一种二进制位，它被用来添加到需要传输的数据信息中，以确保信息在传输过程中不会发生丢失或者改变。

对于“冗余位”究竟需要多少位这个问题，我们有一个公式可以用来计算：
$2^r\geq m+r+1$ 其中 $r$ 是冗余位， $m$ 为数据位。 $r$ 指的是冗余位究竟需要多少位，而 $m$ 指的是传输的数据的二进制位数。

假设传输的数据的二进制位数是7位，那么冗余位的个数就可以通过上面的公式来计算： $= 2^4 ≥ 7 + 4 + 1$ 因此，我们的至少需要4个二进制位作为“冗余位”。

对比以上两种概念，可看出冗余位等价于纠正错误的位数。

（注意：汉明码默认一串数据只错一位）

奇偶校验位
奇校验： 在奇校验检测方式中，对于需要发送的数据信息比特，检查其中1的个数。如果这串比特中1的个数是奇数，为了保证加上“冗余位“后，””整串数据中1的个数最后为奇数，可想而知，冗余位上应该设置为“0”。如果在没有添加“冗余位”之前，数据比特流中的1的个数为偶数，那么为了最后把1的个数凑成一个奇数，冗余位上应该设置为1。
偶校验： 同理，在偶校验检测方式中，对于需要发送的数据信息比特，仍然检查其中1的个数。如果这串比特中1的个数是奇数，为了保证加上“冗余位“后，””整串数据中1的个数最后为偶数，可想而知，冗余位上应该设置为“1”。如果在没有添加“冗余位”之前，数据比特流中的1的个数为偶数，那么为了最后把1的个数凑成一个偶数，冗余位上应该设置为0。例如（偶校验）：

如果整个代码“1”的个数为奇数，我们就知道有一位数据发生了翻转（因为数据位翻转的位数越多，可能性越小。）如果我们将数据划分成为两组，每组都加一个校验位，那么可以大大缩小确定发生翻转的位数的范围。这种划分方式是没有重叠的，每个分组的数据连在一起就是原来的数据。

但海明码并未使用上述分组原理。

海明码分组原理
汉明码采用的是非划分方式。对于下面这个数据，我们采用汉明码的方式。

将数据分为三组，每组一个校验位，每组四位数据。按照如下方式分组

（注意：上、左、右三个圆分别表示P1、P2、P3组）把表示位置的这个数，转化成二进制数。也就是，

第1个位置，变成第0001个位置；
第2个位置，变成第0010个位置；
第3个位置，变成第0011个位置；
第4个位置，变成第0100个位置；
第5个位置，变成第0101个位置；
第6个位置，变成第0110个位置；
第7个位置，变成第0111个位置；

那么，规定来了，
凡是位置符合这种形式的，XXX1，归到P1；
凡是位置符合这种形式的，XX1X，归到P2；
凡是位置符合这种形式的，X1XX，归到P3；
凡是位置符合这种形式的，1XXX，归到P4；

则上图中：
位置在1、3、5、7的数据进入组P1;
位置在2、3、6、7的数据进入组P2;
位置在4、5、6、7的数据进入组P3;
没有数据进入组P4;

若某个组位置错了将其置为1，没错就是0，则有：

P3	P2	P1	错位的位置号
0	0	0	无差错
0	0	1	1
1	0	1	5
1	1	0	6
1	1	1	7

可以看出P3、P2、P1组成的二进制值就是发生错误的位置。记住规定，在采用汉明码的一串数据中， $2^i$ 的位置上，我们放校验码。

海明码编码和校验实例（以奇校验为例）
编码：
假定数据为：1011001。由于 $2^4 ≥ 7 + 4 + 1$ ，因此需要4位校验位或冗余位。填充冗余位后有：
海明码编码和校验原理与实现

对于第一组来说（1,3,5,7,9,11位为一组）：1的个数为4个，偶数个，因此①号应该为1。这样1的个数最后才能保证为奇数。
同理，对于第二组来说（2,3,6,7，10,11位1组）：1的个数为3个，已经是奇数了，因此②号应该是0。
对于第三组来说（4,5,6,7位一组），1的个数为1个，因此，③号应该是0。
对于第4组来说（8,9,10,11为一组），1的个数为2个，因此，④应该为1。
最后，总的汉明码就构造完毕了，如下所示：

校验：
上面，我们已经完成了“汉明码”的编码，那么，汉明码又是如何发现错误以及改正错误的呢？
假设，第“5”号位上的“0”在传输过程中变成了“1”，接收方收到的数据则为：10111010101。

汉明码通过检查每一小组的“奇校验”，来确定是否发生了错误。
首先第一组（1,3,5,7,9,11位）：1的个数为6位，不再是奇数个了，因此，我们可以断定，这一组中肯定有某个数据发生了错误，但不能确定是哪一位上发生了错误。为了达到“奇校验”，我们必须补1个1来达到奇数个1。
接下来，我们检查第二组（2,3,6,7，10,11），1的个数为3位，仍然满足“奇校验”，因此我们也可以断定这一组中没有任何一位数据发生了改变。所以，我们只需要补0。
我们继续检查第三组（4,5,6,7），1的个数为2个，不在满足“奇校验”，因此，我们可以断定，这一组中也有数据发生改变。为了达到“奇校验”，我们必须补1个1来达到奇数个1。
我们检查第4组（8,9,10,11位），1的个数为3位，满足“奇校验”，因此没有发生改变。所以我们只需要补0。
如下图所示：

最后得出来的二进制数是：0101，我们会神奇地发现，0101就是10进制5的二进制表现，因此，我们可以准确的知道，5号位上发生了数据的改变，我们只要对5号位进行置反操作即可。最后，接收方就可以修改成为正确的数据啦。

海明码编码和校验实例（以偶校验为例）
编码（通常汉明编码是以偶校验进行编码的）：
假定数据为：10011010，由于 $2^4 ≥ 8 + 4 + 1$ ，因此需要4位校验位或冗余位。填充冗余位后有：
_ _1_001_1010
分组情况如下：
组数是这样的：
P1: 1,3,5,7,9… 检验奇数位
P2: 2,3,6,7,10,11… 检验两个，跳过两个，检验两个，跳过两个
**P3: 4,5,6,7,12,13,14,15…**检验4个，跳过4个
**P4: 8,9,10,11,12,13,14,15…**检验8个，跳过8个
由于进行偶校验，要求每个组中1的个数是偶数，因此有：

第1组检验位为 1,3,5,7,9,11:
? _ 1 _ 0 0 1 _ 1 0 1 0. 看看1，3，5，7，9，11位，发现正好是偶数个1，所以校验位1设为0就行了:
0 _ 1 _ 0 0 1 _ 1 0 1 0
第2组检验位为 2,3,6,7,10,11:
0 ? 1 _ 0 0 1 _ 1 0 1 0. 发现是奇数个1，于是设置校验位2为1，这样算上校验位的1，恰好是偶数个0 1 1 _ 0 0 1 _ 1 0 1 0
第3组检验位为 4,5,6,7,12:
0 1 1 ? 0 0 1 _ 1 0 1 0. 发现是奇数个1，于是设置校验位4为 0 1 1 1 0 0 1 _ 1 0 1 0
第4组检验位为 8,9,10,11,12:
0 1 1 1 0 0 1 ? 1 0 1 0. 发现是偶数个1，于是设置校验位8为 0 1 1 1 0 0 1 0 1 0 1 0
最后配置好的汉明码： 011100101010.

校验：
如我们传送的011100101010，但接收到的是011100101110 （第10位出现错误）。

出错位可以这样确定：
对接受到的汉明码011100101110 进行每一个校验码的验算，即它所在的组（包括它，与之前不同的是，之前校验码是待定的，现在已经有值了）的1的个数应该是偶数个，这就暗示我们将要覆盖这个值（实际上并不是，仅仅是验算）的新校验码应该是0才对，但是由于接收到的有错误，我们在验算中发现有的校验位要填1。

这里，验算后发现第2个和第8个校验位要填1，那么错误的数据位就是2+8=10。

海明码编码和校验实现（C++\C）

海明码编码和校验原理与实现

相关推荐