计算机组成原理-学习笔记10-数据校验码
二月 10, 2023
1229
计算机组成原理-学习笔记10-数据校验码
Lecture 10 数据校验码
差错
硬故障
软故障
检错和校正
纠错
基本思想:储存额外信息以进行检错和校正
处理过程:
- 数据输入:使用函数𝑓在𝑀位数据𝐷上生成𝐾位校验码𝐶
- 数据输出:使用函数𝑓在𝑀位数据𝐷’上生成新的𝐾位代码𝐶****” ,并与取出的𝐾位码𝐶****’进行比较
- 没有检测到差错:使用数据𝐷’
- 检测到差错且可以校正:校正数据𝐷’来生成数据𝐷”,并用数据𝐷”
- 检测到差错但无法纠正:报告
奇偶校验码
增加1位校验码来表示数据中1的数量是奇数还是偶数
• 奇校验:使传输的数据(数据位+校验位)中有奇数个1
• 偶校验:使传输的数据(数据位+校验位)中有偶数个1
处理过程
• 假设数据为𝐷 = 𝐷𝑀 … 𝐷2𝐷1
• 数据输入
• 奇校验:𝐶 = 𝐷𝑀 ⊕ ⋯⊕ 𝐷2⊕ 𝐷1 ⊕1
• 偶校验:𝐶 = 𝐷𝑀 ⊕ ⋯⊕ 𝐷2⊕ 𝐷1
• 数据输出
• 奇校验:𝐶′′ = 𝐷′𝑀 ⊕ ⋯⊕ 𝐷′2⊕ 𝐷′1 ⊕1
• 偶校验:𝐶′′ = 𝐷′𝑀 ⊕ ⋯⊕ 𝐷′2⊕ 𝐷′1
• 检错:S = 𝐶′′ ⊕ 𝐶′
• 𝑆 = 0:正确 / 数据中出错的位数为偶数
• 𝑆 = 1:数据中出错的位数为奇数
- 优点:
- 代价低,计算简单
- 缺点:
- 不能发现出错位数为偶数的情形
- 不能校正
- 适用于对较短长度(如1字节)的数据进行检错
海明码
将数据分成几组, 对每一组都使用奇偶校验码进行检错
数据输入:为数据𝐷中每组生成1位校验码, 合并得到𝐾位校验码𝐶
数据输出:为数据𝐷′中每组生成1位校验码, 合并得到新的𝐾位校验码𝐶′′
检错:C’ 与 C’’ 进行异或,生成𝐾位故障字
- 假设最多1位发生错误
- 添加一位校验位可纠错一位,检错两位
考试时画表,每第k位 纠错位为1
最大纠错能力
循环冗余校验
生成多项式:自定义
使用异或除法
基本思想
• 假设数据有M位,左移数据K位(右侧补0),并用K+1位生成多项式除它
(异或?)
• 采用K位余数作为校验码
• 把校验码放在数据(不含补的0)后面,一同存储或传输
校错
• 如果M+K位内容可以被生成多项式除尽,则没有检测到错误
• 否则,发生错误
模2除法:
- 除数首位必为1
- 只需看被除数首位是否为1,为1则商1
- 异或运算
查看评论