3-3纠1位错的海明码在线视频

各位好

检查出错误来了之后呢

我们有两种处理的方法

一种是纠错

一种是检错

今天我们要来学一种纠错码

叫纠1位错的海明码

首先要搞清楚

我们要传输m位数据

冗余位r应该是多少

才能够纠正出1位错来呢

假设在一个编码系统里面

编码后的码字位数是n

则n等于m+r

因为要传输的数据位是m位

那么这个通信系统需要传输的

正确的码字个数应该是2的m次方

而全部码字的个数是2的n次方

如果每个正确码字发生1位错

能够被纠错

至少发生1位错不会跳变成

另外一个正确的码字

如果N位码字的每一位

都发生一次跳变

变成一个错误的码字

那么每一个码字

至少需要n+1个码字来表示它

所以下面这个式子成立

再把这个不等式变换一下

就可以计算出冗余位r来了

根据这个公式

可以计算出传输m位数据

至少需要的冗余位数r

比如说传输位数是5位

也就是说m等于5

那么通过这个公式

计算出冗余位r等于4

也就是说需要四位冗余位

海明纠错码

它是1950年就提出来了

它的方法是这样的

每一个码字

就是包括数据位和冗余位的码字

从左到右编号

最左边是第一位、第二位、第三位

一直数下去

凡是编号为2的乘幂的位是校验位

比如说1、2、4、8、16、32

这样的位都叫做校验位

除了校验位

剩下的那些位

比如说3、5、6、7、9、10、11

这样的位呢就是数据位

每一个数据位

就是我们要待传输的数据

直接填进去的

而校验位呢

它可以设置

它的设置的依据是这样的

包括它自己在内的

一些位的集合的奇偶值

也就是说采用奇校验或者偶校验

具体地来看

我们把某一个数据位的编号

展开成2的乘幂的和

那么每一项所对应的位

即为该数据位的校验位

收方的时候它会使用

反过来

校验位的校验集合

也包含这个数据位

比如说第11位

我们把它的序号11 编号11展开

展开成1+2+8

这1、2、8都是校验位

展开成校验位的编号的和

29也可以展开成1+4+8+16

那么展开了之后呢

我们再反过来看

校验位1它被哪些数据位展开过

它被所有的奇数位所展开过

所以校验位1的校验集合

就是所有的奇数位

包含它自己在内

同样地

校验位2的校验集合

就是2、3、6、7、10、11位

因为这些位它的编号展开了之后

都包含2

如果说刚才那个描述比较抽象的话

我们可以用这个表格来解释

比如说我们要传输的数据是7位

我们通过公式计算

得到它的冗余位是四位

那么总共的N位码字

应该是7+4

11位

那么我们把这11位的码字呢

按照从左到右进行编号

分别是1、2、3、4 一直到11位

然后呢我们在这个表格里边

把每一个编号都展开

1就展开为1

2就展开为2

3呢可以展开为1+2

所有的编号都按照展开成

校验位的和

校验位呢有哪些呢

1、2、4、8

就是2的乘幂

就是2的0次方 2的1次方

2的2次方 2的3次方

2的4次方这样的

展开了之后呢

在表格里面的每一行

就是一个校验的集合

比如说第一行

第一行就是校验位1

它的校验集合

包括1、3、5、7、9、11

这样的所有的奇数位

而校验位2它的校验集合呢

就是2、3、6、7、10、11

校验位4它的校验集合就是

4、5、6、7

校验位8它的校验集合

8、9、10、11

现在我们用一个实例来看一下

我们的发方怎样来进行编码的

假如说我们待传输的数据是

1 0 0 1 0 0 0

m等于7

使用偶校验

现在呢我们要看一下编码之后

我们纠1位的错的海明码

应该是个什么样子

根据公式计算得到冗余位r等于4

那么编码后的码字

它的位数我们就确定下来

等于7+4 11位

现在呢我们把要传输的数据

1 0 0 1 0 0 0

按照顺序填到

第3、5、6、7、9、10 11位上面

接下来就要决定

第1、2、4、8

这四个校验位它的取值

到底应该是0还是1了

先来看第1个校验位

它的校验集合是所有的奇数位

对应的值是1 0 1 0 0

数下来总共有两个1

是偶数个1了

所以我们的校验位

第一个校验位只能够填入0

再看第二个校验位

它的校验集合是2、3、6、7、10、11位

对应的值分别是1 0 1 0 0

数下来1的个数是两个

是偶数了

所以校验位2也只能够填入0

再来看校验位4

对应的校验集合是

第4、5、6、7位

对应的值分别是0 0 1

总共只有一个1

是奇数

现在我们的条件是要采用偶校验

所以我们的校验位4

需要填入一个1

保证我们1的个数是两个

是偶数个

同样的道理

校验位8需要填入0

最后

发送方就得到了编码后的码字是

0 0 1 1 0 0 1 0 0 0 0

发送方纠1位错的海明码

我们知道是如何来工作的

那么接收方是如何来纠错的呢

纠错的过程是这样的

首先接收方将差错计数器置于0

也就是说一个Counter等于0

当码字到达接收端之后

接收端逐个检查各个校验位

它的奇偶性

如果发现某一个校验位

和它检测的集合的奇偶性不正确

就将该校验位的编号

加到差错计数器Counter里面

最后所有的校验位都检查完成之后

检查这个计数器Counter它的值

如果Counter等于0

就表明传输的过程里头没有错

如果Counter不等于0

就代表它出了错

哪一位出错呢

Counter的值是多少

就表明是哪一位出了错

举一个例子来看

有一个系统

采用了纠1位错的海明码

采用偶校验

传输的数据位数是7位

冗余位是4位

现在接收方收到的码字如下

0 0 1 1 1 0 0 0 1 0 0

那么接下来接收方就是这样做

逐个去检查每个校验位

首先它把计数器Counter等于0

先看第一位的校验位

第一位的校验位

是所有的奇数位

它数一下1的个数

1的个数是3

那么是奇数个

现在我们采用的是偶校验

所以第一个校验位错了

它把1这个编号加到Counter上

接下来再数第二位校验位

它的校验集合里边数下来

1的个数是1个

也是错的

所以把第二位的校验位它的编号2

也加到Counter上面

第四位校验集合

数下来1的个数是两个

偶数个 正确

第八位校验集合

1的个数是1个

错了

把8加到Counter上面

最后得到Counter的值是11

所以接收方就可以根据这个

判断出这个码字是错的

而且出错的位数是第11位

那么第11位现在的码字是0

我们直接把它改为1

就恢复出正确的码字来了

纠1位错的海明码

可以纠单个的错误

但是有的时候一个尖峰电压

可能导致产生一些突发错误

我们可以利用这个纠1位错的海明码

来纠正这样的突发错误

怎么做呢

我们可以把连续的K个码字

按行排列成矩阵

排列成一行一行的

发送数据的时候呢

我们按列来发送码字

每列呢K位

如果一个突发性的错误的长度

是K位或者小于K位

那么在K个码字中

就是在行

在K个码字中

至多只有一位受到影响

也就是说只有一位发生了错误

正好可以用这个纠1位错的海明码

来纠正错误

这是非常巧妙的一个方法

注意

能够纠正的突发错误的个数

一定是小于等于

发送矩阵的行数K的

如果说你这个突发错误太多了

多到已经超过了这个矩阵的行数

那么也纠正不出来了

小结一下

纠1位错需要的冗余位

跟数据位m的关系

可以用这个式子来描述

纠1位错的海明码的基本的方法

是这样的

发送方根据校验集合

来填充校验位

数据位直接填入数据

而接收方是根据校验集合

来判定校验位是否出错

出错位的编号

累加到计数器上

所有的校验位检查完成之后

通过读取计数器的值

来确定码字中出错的那一位的编号

进行纠正