lecture-2-3x.ppt

Lecture 2-3
数据校验码
2/22/2018
1
苏州大学计算机工程系
数据校验码
检错和纠错如图所示。
通过函数f 对数据进行计算,以产生一种代码,代码和数据都被存储,因此如果原来数据字长为M位,校验码长为K位,则实际存储的字长应该是M+K位。
当原先存储的字读出时,这个代码用于检错和纠错,在M位数据中产生一组新的K位代码,与取出的代码进行比较:
结果一致,无差错,取出的数据位传送出去;
检测到差错,并可以纠正,数据位和纠错位一起送入纠正器,然后产生一组正确的M位数据位;
检测到差错,但无法纠正,报告出错
2/22/2018
2
苏州大学计算机工程系
奇偶校验码
编码方法:
不管数据位长度多少,校验位只有一位。
数据位和校验位一起所含“1”的个数,只能是奇数,称为奇校验。
数据位和校验位一起所含“1”的个数,只能是偶数,称为偶校验。
例:数据奇校验的编码偶校验的编码
00000000 100000000 000000000
01010100 001010100 101010100
01111111 001111111 101111111
校验:对奇校验,如接收端收到是偶码,表示传送有误,因此可发现一位错(奇位错)
2/22/2018
3
苏州大学计算机工程系
1位纠错海明码(原理)
海明校验码不仅能发现出错,而且还能指出哪一位出错。
设有R位校验位,则共有0到2R-1个共2R个组合。若用0表示无差错,则剩余2R-1个值表示有差错,并指出错在第几位。由于差错可能发生在K个数据位中或R个校验位中,因此有:
2R–1R+K
2/22/2018
4
苏州大学计算机工程系
海明校验码(校验位数)
海明码需要几位校验码?
k—数据位的位数 r—校验位的位数
数据位k与校验位r的关系:2r ≥ k+r+1
数据位k 校验位r 总位数n
1 2 3
2~4 3 5~7
5~11 4 9~15
12~26 5 17~31
27~57 6 33~63
58~120 7 65~127
2/22/2018
5
苏州大学计算机工程系
海明校验码(校验位置)
校验位和数据位是如何排列的
校验位排列在 2i–1 (i =0,1,2,…)的位置上
例:有一个BCD码为D4D3D2D1,由此生成一个海明码
7 6 5 4 3 2 1
D4 D3 D2 P3 D1 P2 P1
22 21 20
有一字节的信息需生成海明码
D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P2 P1
8 4 2 1
2/22/2018
6
苏州大学计算机工程系
校验位取值公式及计算举例
海明码的校验位Pi和数值位Di的关系
例:BCD码为1011
P3= D4⊕D3 ⊕D2
0 = 1 ⊕ 0 ⊕ 1
P2= D4 ⊕D3 ⊕D1
0 = 1 ⊕ 0 ⊕ 1
P1 = D4 ⊕D2 ⊕D1
1 = 1 ⊕ 1 ⊕ 1 最后海明码为1010101
7
6
5
4
3
2
1
22
D4
D3
D2
P3
21
D4
D3
D1
P2
20
D4
D2
D1
P1
2/22/2018
7
苏州大学计算机工程系
1位纠错海明码的实现
把M+K=m个数据=>HmHm-1...H2H1(海明码),每个校验位Pi在海明码中被分配在2i-1位置上。
Hi由多个校验位校验:每个海明码的位号要等于参与校验它的几个检验位的位号之和。
尽量增大合法码的码距。
举例:M=8,K=4,则海明码为:
H12H11H10H9H8H7H6H5H4H3H2H1
P4,P3,P2,P1根据规则,分别对应于:H8,,H4 ,, H2 ,, H1
这样,P1=M1  M2  M4  M5  M7
P2=M1  M3  M4  M6  M7
P3=M2  M3  M4  M8
P4=M5  M6  M7  M8
2/22/2018
8
苏州大学计算机工程系
1位纠错海明码的实现(续)
P1=M1  M2  M4  M5  M7
P2=M1  M3  M4  M6  M7
P3=M2  M3  M4  M8
P4=M5  M6  M7  M8
12
11
10
9
8
7
6
5
4
3
2
1
20
M7
M5
M4
M2
M1
P1
21
M7
M6
M4
M3
M1
P2
22
M8
M4
M3
M2
P3
23
M8
M7
M6
M5
P4
2/22/2018
9
苏州