第四讲 数据校验码
纠错
存储额外的信息以进行检错和校正
处理过程
- 数据输入：使用函数𝑓在𝑀位数据𝐷上生成𝐾位校验码C
- 数据输出：使用函数𝑓在𝑀位数据𝐷’上生成新的𝐾位代码𝐶”，并与取出的𝐾位码𝐶’进行比较
在信息传输过程中, D和C都可能出错
奇偶校验码
增加1位校验码来表示数据中1的数量是奇数还是偶数
输入数据:
奇校验: C=𝐷𝑀⊕⋯⊕𝐷2⊕𝐷1⊕1 奇数个1时为0
偶校验: 𝐶=𝐷𝑀⊕⋯⊕𝐷2⊕𝐷1 偶数个1时为0
输出数据:
奇校验: 𝐶”=𝐷’𝑀⊕⋯⊕𝐷’2⊕𝐷’1⊕1
偶校验: 𝐶”=𝐷’𝑀⊕⋯⊕𝐷’2⊕𝐷’1
检错：S=𝐶′′⊕𝐶′
- 𝑆=0：正确/数据中出错的位数为偶数
- 𝑆=1：数据中出错的位数为奇数
适用于对较短长度(如1字节)的数据进行检错
海明码
将数据分成几组，对每一组都使用奇偶校验码进行检错
处理过程
- 将𝑀位数据分成𝐾组
- 数据输入：为数据𝐷中每组生成1位校验码，合并得到𝐾位校验码C
- 数据输出：为数据𝐷′中每组生成1位校验码，合并得到新的𝐾位校验码𝐶′′
- 检错：将校验码𝐶′′和取出的校验码C’ 按位进行异或，生成𝐾位故障字
校验码的长度应为多少(应该分为多少组)
要能覆盖所有情况
- 数据中有1位出现错误：M
- 校验码中有1位出现错误：K
- 没有出现错误：1
所以2^𝐾 ≥𝑀+𝐾+1
故障字的作用: 每种取值都反应一种情形（数据出错/校验码出错/未出错）
规则
- 全部是0：没有检测到错误
- 有且仅有1位是1：错误发生在校验码中的某一位，不需要纠正
- 有多位为1：错误发生在数据中的某一位，将𝐷′中对应数据位取反即可纠正（得到𝐷”）
具体怎么做
- 列出K位故障字共2^K种选择的表格
- 根据规则分配情形(相当于分组了)
- 根据分组计算每一位海明码的值
- 根据故障字中, 表示校验码出错的位置, 将海明码填入原数据的固定位置中
- 检错时如果出现数据位错误直接取反即可, 如果是校验码出错不用管
循环冗余校验
海明码问题
- 额外成本很大
- 要求将数据分成字节
循环冗余校验
- 适用于以流格式存储和传输大量数据
- 用数学函数生成数据和校验码之间的关系
基本思想
- 假设数据有M位，左移数据K位（右侧补0），并用K+1位生成多项式除它(模2运算)
- 采用K位余数作为校验码
- 把校验码放在数据（不含补的0）后面，一同存储或传输
检错
- 如果M+K位内容可以被生成多项式除尽，则没有检测到错误
- 否则，发生错误
生成多项式: 率先选择好的一个数
模2运算
准备数据：假设数据有M位，生成多项式有K+1位。将数据左移K位（右侧补0），得到一个新的数据序列。
初始化：将生成多项式对齐到数据的最高位。
按位除法：
如果当前数据的最高位是1，则将生成多项式与当前数据的最高位对齐部分进行异或运算。
如果当前数据的最高位是0，则跳过异或运算，直接将生成多项式右移一位。
将生成多项式右移一位，继续下一位的运算。
重复步骤3，直到处理完所有数据位。
余数：最后剩下的K位就是校验码。
易错题目
