夜雨聆风学习资料网 资料列表 开通 VIP 用登录 / 注册 ⌄
PDF

3.3.2纠错编码(海明校验码)_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_02.计算机网络领学班_00.资料_第三章数据链路层

查看资料信息、公开预览和下载状态。

共 13 页PDF · 1.2MB
下载

文档在线预览

公开展示前 7 页
100%
1
《3.3.2纠错编码(海明校验码)_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_02.计算机网络领学班_00.资料_第三章数据链路层》第1页预览
2
《3.3.2纠错编码(海明校验码)_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_02.计算机网络领学班_00.资料_第三章数据链路层》第2页预览
3
《3.3.2纠错编码(海明校验码)_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_02.计算机网络领学班_00.资料_第三章数据链路层》第3页预览
4
《3.3.2纠错编码(海明校验码)_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_02.计算机网络领学班_00.资料_第三章数据链路层》第4页预览
5
《3.3.2纠错编码(海明校验码)_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_02.计算机网络领学班_00.资料_第三章数据链路层》第5页预览
6
《3.3.2纠错编码(海明校验码)_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_02.计算机网络领学班_00.资料_第三章数据链路层》第6页预览
7
《3.3.2纠错编码(海明校验码)_2026考研专业课_202026计算机_202026计算机_2026年王道计算机408_02.计算机网络领学班_00.资料_第三章数据链路层》第7页预览

本文档共 13 页 剩余 6 页未展示,请下载后查阅

下载

文档文本内容

本节内容
纠错编码
(海明校验码)
王道考研/CSKAOYAN.COM本节总览
王道考研/CSKAOYAN.COM海明校验码思路简介
奇校验码:整个校验码(有效信息位和校验位)中“1”的个数为奇数。
偶校验码:整个校验码(有效信息位和校验位)中“1”的个数为偶数。
1个校验位之只能携带
2种状态信息(对/错)
偶校验:1010 —> 01010,能发现奇数位错误,但无法确定是哪一位出错。
海明码设计思路:将信息位分组进行偶校验 —> 多个校验位
—>多个校验位标注出错位置
多个校验位能携带多种状态信
息,(对/错,错在哪)
王道考研/CSKAOYAN.COM海明校验码思路简介
海明码设计思路:将信息位分组进行偶校验 —> 多个校验位
—>多个校验位标注出错位置
n+k位中任何一
需要多少校验位?
位都可能出错
信息位+校验位,
共n+k位
2!
≥ n + k + 1
信息位 校验位
2!种状态
n k
1种正确状态
n 1 2-4 5-11 12-26 27-57 58-120
k 2 3 4 5 6 7
王道考研/CSKAOYAN.COM海明码求解步骤
信息位:1010
确定校 确定校
求校验 检错纠
1. 确定海明码的位数: 2! ≥ n + k + 1 验位数 验位的
位的值 错
量 分布
n = 4 —> k = 3
设信息位D D D D (1010),共4位,校验位P P P ,
4 3 2 1 3 2 1
共3位,对应的海明码为H H H H H H H 。
7 6 5 4 3 2 1
2. 确定校验位的分布
H H H H H H H
𝟕 𝟔 𝟓 𝟒 𝟑 𝟐 𝟏
校验位P放在海明位号为2i−1的位置上
i
信息位按顺序放到其余位置
王道考研/CSKAOYAN.COM海明码求解步骤
信息位:1010 3. 求校验位的值 Å:异或
0 Å 0 = 0
1. 确定海明码的位数: 2! ≥ n + k + 1 H :3 —> 0 1 1
3
0 Å 1 = 1
n = 4 —> k = 3 H :5 —> 1 0 1 1 Å 0 = 1
5
1 Å 1 = 0
设信息位D D D D (1010),共4位,校验位P P P , H :6 —> 1 1 0
4 3 2 1 3 2 1 6
共3位,对应的海明码为H H H H H H H 。 相当于偶校验
7 6 5 4 3 2 1 H :7 —> 1 1 1
7
2. 确定校验位的分布 三个分组,分
P =H ÅH ÅH =D ÅD ÅD
1 3 5 7 1 2 4
别进行偶校验
=0Å1Å1=0
H H H H H H H
𝟕 𝟔 𝟓 𝟒 𝟑 𝟐 𝟏 P =H ÅH ÅH =D ÅD ÅD
2 3 6 7 1 3 4
D D D P D P P =0Å0Å1=1
4 3 2 3 1 2 1
P =H ÅH ÅH =D ÅD ÅD
3 5 6 7 2 3 4
1 0 1 0
=1Å0Å1=0
校验位P放在海明位号为2i−1的位置上
i
信息位按顺序放到其余位置
王道考研/CSKAOYAN.COM海明码求解步骤
信息位:1010 3. 求校验位的值
1. 确定海明码的位数: 2! ≥ n + k + 1 H :3 —> 0 1 1
3
n = 4 —> k = 3 H :5 —> 1 0 1
5
设信息位D D D D (1010),共4位,校验位P P P , H :6 —> 1 1 0
4 3 2 1 3 2 1 6
共3位,对应的海明码为H H H H H H H 。
7 6 5 4 3 2 1 H :7 —> 1 1 1
7
2. 确定校验位的分布 三个分组,分
P =H ÅH ÅH =D ÅD ÅD
1 3 5 7 1 2 4
别进行偶校验
=0Å1Å1=0
H H H H H H H
𝟕 𝟔 𝟓 𝟒 𝟑 𝟐 𝟏 P =H ÅH ÅH =D ÅD ÅD
2 3 6 7 1 3 4
D D D P D P P =0Å0Å1=1
4 3 2 3 1 2 1
P =H ÅH ÅH =D ÅD ÅD
3 5 6 7 2 3 4
1 0 1 0 0 1 0
=1Å0Å1=0
4. 纠错
校验位P放在海明位号为2i−1的位置上
i
S =P ÅD ÅD ÅD
1 1 1 2 4
信息位按顺序放到其余位置
S =P ÅD ÅD ÅD
2 2 1 3 4
S =P ÅD ÅD ÅD
3 3 2 3 4
王道考研/CSKAOYAN.COM海明码求解步骤
信息位:1010 3. 求校验位的值
1. 确定海明码的位数: 2! ≥ n + k + 1
P
1
=D
1
ÅD
2
ÅD
4
=0Å1Å1=0
P =D ÅD ÅD =0Å0Å1=1
2 1 3 4
n = 4 —> k = 3 P =D ÅD ÅD =1Å0Å1=0
3 2 3 4
设信息位D D D D (1010),共4位,校验位P P P ,
4 3 2 1 3 2 1 4. 纠错
共3位,对应的海明码为H H H H H H H 。 P
7 6 5 4 3 2 1 1
校验方程:
S
1
=P
1
ÅD
1
ÅD
2
ÅD
4
D
1
D
2
D
2. 确定校验位的分布 S =P ÅD ÅD ÅD 4
2 2 1 3 4
S 3 =P 3 ÅD 2 ÅD 3 ÅD 4 P 2 D 3 P 3
H H H H H H H
𝟕 𝟔 𝟓 𝟒 𝟑 𝟐 𝟏
接收到:1010010
D D D P D P P
4 3 2 3 1 2 1 S =P ÅD ÅD ÅD = 0Å0Å1Å1= 0
1 1 1 2 4 无错
S =P ÅD ÅD ÅD = 1Å0Å0Å1= 0
1 0 1 0 0 1 0 2 2 1 3 4 误
S =P ÅD ÅD ÅD = 0Å1Å0Å1= 0
3 3 2 3 4
校验位P放在海明位号为2i−1的位置上
接收到:1010000
i 低
S =P ÅD ÅD ÅD = 0Å0Å1Å1= 0
1 1 1 2 4 第010
信息位按顺序放到其余位置 S =P ÅD ÅD ÅD = 0Å0Å0Å1= 1
2 2 1 3 4
位出错
S =P ÅD ÅD ÅD = 0Å1Å0Å1= 0
3 3 2 3 4
高
王道考研/CSKAOYAN.COM海明码求解步骤 格式变化
-
信息位:1010 3. 求校验位的值
1. 确定海明码的位数: 2! ≥ n + k + 1
P
1
=D
1
ÅD
2
ÅD
4
=0Å1Å1=0
P =D ÅD ÅD =0Å0Å1=1
2 1 3 4
n = 4 —> k = 3 P =D ÅD ÅD =1Å0Å1=0
3 2 3 4
设信息位D D D D (1010),共4位,校验位P P P , 设信息位D D D D (1010),共4位,校验位P P P ,
4 3 2 1 3 2 1 1 2 3 4 1 2 3
共3位,对应的海明码为H H H H H H H 。 共3位,对应的海明码为H H H H H H H 。
7 6 5 4 3 2 1 1 2 3 4 5 6 7
H H H H H H H
𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕
2. 确定校验位的分布
P P D P D D D
1 2 1 3 2 3 4
H H H H H H H 1 0 1 0
𝟕 𝟔 𝟓 𝟒 𝟑 𝟐 𝟏
D D D P D P P
4 3 2 3 1 2 1 P =D ÅD ÅD =1Å0Å0=1
1 1 2 4
1 0 1 0 0 1 0
P
2
=D
1
ÅD
3
ÅD
4
=1Å1Å0=0
P =D ÅD ÅD =0Å1Å0=1
3 2 3 4
校验位P放在海明位号为2i−1的位置上
i
信息位按顺序放到其余位置
王道考研/CSKAOYAN.COM海明码求解步骤 格式变化
-
信息位:1010 3. 求校验位的值
1. 确定海明码的位数: 2! ≥ n + k + 1
P
1
=D
1
ÅD
2
ÅD
4
=0Å1Å1=0
P =D ÅD ÅD =0Å0Å1=1
2 1 3 4
n = 4 —> k = 3 P =D ÅD ÅD =1Å0Å1=0
3 2 3 4
设信息位D D D D (1010),共4位,校验位P P P , 设信息位D D D D (1010),共4位,校验位P P P ,
4 3 2 1 3 2 1 1 2 3 4 1 2 3
共3位,对应的海明码为H H H H H H H 。 共3位,对应的海明码为H H H H H H H 。
7 6 5 4 3 2 1 1 2 3 4 5 6 7
H H H H H H H
𝟏 𝟐 𝟑 𝟒 𝟓 𝟔 𝟕
2. 确定校验位的分布
P P D P D D D
1 2 1 3 2 3 4
H H H H H H H 1 0 1 1 0 1 0
𝟕 𝟔 𝟓 𝟒 𝟑 𝟐 𝟏
D D D P D P P
4 3 2 3 1 2 1 P =D ÅD ÅD =1Å0Å0=1
1 1 2 4
1 0 1 0 0 1 0
P
2
=D
1
ÅD
3
ÅD
4
=1Å1Å0=0
P =D ÅD ÅD =0Å1Å0=1
3 2 3 4
校验位P放在海明位号为2i−1的位置上
i
信息位按顺序放到其余位置
王道考研/CSKAOYAN.COM补充
海明码的检错、纠错能力: 纠错能力——1位
无法区分到底是1
检错能力——2位
位错还是2位错
P
1
H H H H H H H 校验方程:
𝟕 𝟔 𝟓 𝟒 𝟑 𝟐 𝟏
D D
S
1
=P
1
ÅD
1
ÅD
2
ÅD
4 1 2
D D D P D P P D
4 3 2 3 1 2 1 S =P ÅD ÅD ÅD 4
2 2 1 3 4
1 0 1 0 0 1 0 S 3 =P 3 ÅD 2 ÅD 3 ÅD 4 P 2 D 3 P 3
H H H H H H H H
𝟖 𝟕 𝟔 𝟓 𝟒 𝟑 𝟐 𝟏
S S S = 000 且全体偶校验成功 à 无错误
3 2 1
P D D D P D P P
全 4 3 2 3 1 2 1 S S S ≠ 000 且全体偶校验失败 à 有1位错,纠正即可
3 2 1
1 1 0 1 0 0 1 0 S S S ≠ 000 且全体偶校验成功 à 有2位错,需重传
3 2 1
(需加上“全校验位”,对整体进行偶校验)
王道考研/CSKAOYAN.COM知识回顾
王道考研/CSKAOYAN.COM演讲选段
Richard Hamming
早年,我在攻克一个又一个难题,成功的多,失败的少。可是,周五解决了一个问题回到家里后,
我却并不快活,反而很沮丧。我看到生活就是一个问题接着一个问题又接着另一个问题。
想了相当长一阵子后,我决定以另一种方式干活:你的工作要成为别人工作的基石!于是别人就
会说: "看哪,我站在他的肩膀之上,我看得更远了。"
科学的本质是积累!我再也不去做相互孤立的问题,除非它能代表某一类问题的共性。我决不再
去解决单一的问题。
你要么让人们在你的成果上有所建树,要么别人不得不把你干的活从头再来复制一遍。
王道考研/CSKAOYAN.COM