计算机组成原理-学习笔记10-数据校验码

Lecture 10 数据校验码

差错

硬故障

软故障

检错和校正

纠错

基本思想：储存额外信息以进行检错和校正

处理过程：

• 数据输入：使用函数𝑓在𝑀位数据𝐷上生成𝐾位校验码𝐶
• 数据输出：使用函数𝑓在𝑀位数据𝐷’上生成新的𝐾位代码𝐶****” ，并与取出的𝐾位码𝐶****’进行比较
  • 没有检测到差错：使用数据𝐷’
  • 检测到差错且可以校正：校正数据𝐷’来生成数据𝐷”，并用数据𝐷”
  • 检测到差错但无法纠正：报告

image-20221110174316858

奇偶校验码

image-20230225211413511

增加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位发生错误
• 添加一位校验位可纠错一位，检错两位
• image-20230225211715803

image-20230225211758389

考试时画表，每第k位 纠错位为1

image-20230225211840717

最大纠错能力

image-20230225212940790

循环冗余校验

生成多项式：自定义

使用异或除法

基本思想

• 假设数据有M位，左移数据K位（右侧补0），并用K+1位生成多项式除它
(异或？)
• 采用K位余数作为校验码
• 把校验码放在数据（不含补的0）后面，一同存储或传输

校错

• 如果M+K位内容可以被生成多项式除尽，则没有检测到错误
• 否则，发生错误

模2除法：

• 除数首位必为1
• 只需看被除数首位是否为1，为1则商1
• 异或运算