当前课程知识点:计算机网络 > 第三章:数据链路层 > 3.3 纠1位错的海明码 > Video
各位好
检查出错误来了之后呢
我们有两种处理的方法
一种是纠错
一种是检错
今天我们要来学一种纠错码
叫纠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位错的海明码的基本的方法
是这样的
发送方根据校验集合
来填充校验位
数据位直接填入数据
而接收方是根据校验集合
来判定校验位是否出错
出错位的编号
累加到计数器上
所有的校验位检查完成之后
通过读取计数器的值
来确定码字中出错的那一位的编号
进行纠正
-本课程简介
--课程组织
-1.1 为什么要学习计算机网络?
-1.2 互联网络发展史
--Video
--互联网络发展史
-1.3 常用的基本概念
--Video
--常用的基本概念
-1.4 参考模型(重点)
--Video
--参考模型
-1.5 参考模型相关的概念
--Video
--数据如何传输
-1.6 本课程的组织
--Video
--课程组织
-附录1:思考题
--html
-附录2:术语中英对照表
--html
-附录3:伦敦奥运会开幕式之Tim Berners Lee
--附录说明
-第一章 概述--章节测试
-附录4:本章的无背景乐的视频
--1-4参考模型
--关于附录4的说明
-2.1 数据通信的理论基础
--Video
-2.2 有导向的传输介质
--Video
--有导向的传输介质
-2.3复用技术
--Video
--复用技术
-2.4调制技术
--Video
--调制技术
-2.5公共交换电话网络
--Video
--公共交换电话网络
-2.6物理层设备
--Video
--物理层设备
-附录1:思考题
--html
-附录2:术语中英对照表
--html
-附录3:光纤熔接
--Video
-附录4:海底光缆
--附录说明
--外部链接
-第二章 物理层--章节测试
-附录5:本章的无背景乐的视频
--2-3复用技术
--2-4调制技术
--关于附录5的说明
-3.1 数据链路层概述
--Video
--数据链路层概述
-3.2 差错处理概述
--Video
--差错处理概述
-3.3 纠1位错的海明码
--Video
--纠1位错的海明码
-3.4 检错码
--Video
--检错码
-3.5基本数据链路协议1~3
--Video
-3.6 滑动窗口协议
--Video
--滑动窗口协议
-3.7 回退n帧
--Video
--回退n帧
-3.8 选择性重传
--Video
--选择性重传
-附录1:思考题
--html
-附录2:术语中英对照表
--html
-第三章:数据链路层--章节测试
-附录3:本章的无背景乐的视频
--3-4检错码
--3-6 滑窗协议
--3-7 回退n帧
--关于附录3的说明
-4.1 MAC子层概述
--Video
--MAC子层概述
-4.2 ALOHA协议
--Video
--ALOHA协议
-4.3 CSMA协议
--Video
--CSMA协议
-4.4 以太网概述
--Video
--以太网概述
-4.5 以太网帧格式
--Video
--以太帧格式
-4.6 二层交换的基本格式
--Video
-4.7 生成树协议
--Video
--生成树协议
-4.8 虚拟局域网
--Video
--虚拟局域网
-4.9 二层设备
--Video
--二层设备
-附录1:思考题
--html
-附录2:术语中英对照表
--html
-第四章 介质访问控制子层--章节测试
-附录3:本章的无背景乐的视频
--4-9 二层设备
--关于附录3的说明
-5.1 网络层引言
--Video
--网络层引言
-5.2 IP地址
--Video
--IP地址
--子网规划实例
-5.3 子网规划
--Video
--子网规划
-5.4 IP寻址
--Video
--IP寻址
-5.5 IP分组
--Video
--IP分组
-5.6 什么是IPv6?
--Video
--什么是IPv6?
-5.7 IPv6地址
--Video
--IPv6地址
-5.8 IPv6分组
--Video
--IPv6分组
-5.9 IPv6过渡技术
--Video
--IPv6过渡技术
-5.10 路由从何而来?
--Video
--路由如何而来
-5.11 距离矢量路由选择协议
--Video
-5.12 路由信息协议RIP
--Video
--RIP
-5.13 RIP为什么衰落?
--Video
-5.14 链路状态路由选择LS
--Video
-5.15 单区域OSPF
--Video
-5.16 无类域间路由 CIDR
--Video
--CIDR
-5.17 网络地址翻译 NAT
--Video
--NAT
-5.18 互联网控制消息协议 ICMP
--Video
--ICMP
-5.19 地址解析协议 ARP
--Video
--ARP
-5.20 拥塞控制
--Video
--拥塞控制
-5.21 流量整形
--Video
--流量整形
-附录1:思考题
--html
-附录2:术语中英对照表
--html
-第五章 网络层--章节测试1
-第五章 网络层--章节测试2
-第五章主观测试题
-附录3:本章的无背景乐的视频
--5-2_IP地址
--5-3_子网规划
--5-4_IP寻址
--5-5_IP分组
--5-9过渡技术
--5-21流量整形
-6.1 传输层概述
--Video
--传输层概述
-6.2 用户数据报协议 UDP
--Video
-6.3 通信模型
--Video
--通信模型
-6.4 TCP数据段
--Video
--TCP数据段
-6.5 TCP三次握手建立连接
--Video
-6.6 TCP连接释放
--Video
--TCP连接释放
-6.7 TCP传输策略
--Video
--TCP传输策略
-6.8 TCP拥塞控制
--Video
--TCP拥塞控制
-6.9 TCP定时器等
--Video
--TCP定时器等
-附录1:思考题
--html
-附录2:术语中英对照表
--html
-第六章 传输层--章节测试
-附录3:本章的无背景乐的视频
--6-1传输层概念
--6-2UDP
--6-3通信模型
-linux
-windows
-7.1 应用层概述
--Video
--应用层概述
-7.2 域名系统 DNS 概述
--Video
-7.3 DNS之域名解析
--Video
--域名解析
-7.4 电子邮件 e-mail
--Video
-7.5 万维网 WWW
--Video
--万维网 WWW
-7.6 其它应用
--Video
--其它应用
-附录1:思考题
--html
-附录2:术语中英对照表
--html
-第七章 应用层--章节测试
-附录3: 本章无背景音乐的视频
--7-4_电子邮件
--7-6_其它应用