2021年计算机组成原理xu3.ppt

数据校验码基本特征
---发现错误，。
常用的数据校验码三种：
奇偶校验码、海明校验码、循环冗余校验码(CRC)
实现校验码的基本原理：
在普通编码的基础上增加一些冗余码，能够在正常
合法码发生错误时，即变成非法码时，通过检测编
码的合法性发现错误甚至纠正错误
编码(原数据+校验位) 传输(码字)解码 校验纠错
码距的概念（最小码距） ：
码距是指任意两个合法码之间二进制位存在排列变化的
最小位数。仅有一位不同，称(最小码距)为1
码距为一时，无检错能力。一个合法码变另合法码
2021/1/16
1
计算机组成原理xu3
从另一个角度说，检错纠错还是要有硬件开销的
检错纠错，也是有能力限度的。某些错误能检出，
不是所有的错误都能检出。
奇偶校验码
1，原理
对已有码距为一编码增加一位，使码距为二。所增加的
一位---校验位。总体编码空间增大一倍。任一个合法编
码的任一位发生错变(1->0,0->1)都会变成一个非法码。
2，方法
考察二进制编码中，数值位和校验位总体(码字)各位取值
为1位数的奇偶性。
2021/1/16
2
计算机组成原理xu3
3，实现
(1) 奇校验: 数据位取值为1的位数和校验位凑为奇数。
(2) 偶校验: 数据位取值为1的位数和校验位凑为偶数。
（应用中确定其一种。）
设码字9位，数据8位校验1位 高位校验位
　 数据 　　 奇校验的编码 　　 偶校验的编码
00000000 　　　100000000 　　　　000000000

01010100 　　　001010100 　　　　101010100

01111111 　　　001111111 　　　　101111111

11111111 　　　111111111 　　　　011111111
2021/1/16
3
计算机组成原理xu3
4 奇偶校验码的逻辑实现
+
奇较验 偶校验 出错指示
+
+
+
+
+
+
+
同左侧电路
编码电路
译码电路
P (校验位)
八位数据位
D7 D6 D5 D4 D3 D2 D1 D0
p
异或门
2021/1/16
4
计算机组成原理xu3
5, 实际应用特点 开销最小。不能纠错，内存读写
ASCII码传输，并行数据传输，发现奇数个错变
海明校验码
1，原理
对已有码距为一的编码增加几个检验位。用这些校验位
来定位各编码中任一位错变。同时发现任两位的错变
但不能定位了，也就不能纠错了。
DDDDDDDD PPPPP
* 校验位需求量分析
k 为数据位数(二进制)，r 为校验位数
r 位可编码不同信息2r个，其中一个编码用于表示未出错
2021/1/16
5
计算机组成原理xu3
可用来定位错误的信息编码有 2r – 1– r 个。
要定出有k位的数据中某位错变
显然，要满足这个不等式 2r – 1– r ≥ k
含义是对每一位的错变都有至少一个专门交验位编码
即： 2r ≥k+ r + 1
若要校正一位错，发现两位错，r 和 k 的关系：
2r-1 ≥k+ r （ 海明不等式）
k 与 r 具体对应关系 p107
2, 海明码的基本编码方法（k 个数据位，r个校验位）
*合理地用k个数据位的不同组合形成r个校验位。使任一位出错时都会影响r个校验位中不同的校验位组合变化，从而定位错误。
* 有时两位同时出错和某一位的出错对校验组合的影响相同
必须区别出来。
2021/1/16
6
计算机组成原理xu3
3，八数据位海明码的构成
k = 8, r = 5
数据位：D8 D7 D6 D5 D4 D3 D2 D1
校验位：P5 P4 P3 P2 P1
码字：　P5 D8 D7 D6 D5 P4 D4 D3 D2 P3 D1 P