数据校验码
数据在计算机内部计算，存取和传输过程中会出现差错。
解决方案：采取数据验错和校正措施
纠错：存储额外的信息以进行检验和校正
处理过程：
- 数据输入：在原数据中使用函数f生成K位校验码C’
- 数据输出：在接收到的数据中使用函数f生成新的K位校验码C’’
- C’与C’'进行比较，
- 没有差错则直接使用收到的数据
- 有差错且可以校正：校正数据；
- 有差错且不可以校正：报告
奇偶校验码
增加一位校验码表示数据中1的数量是奇数还是偶数
- 奇校验：使传输的数据中有奇数个1（1的数量为奇数个时校验码为0）
- 偶校验：使传输的数据中有偶数个1（1的数量为偶数个时校验码为0）
优点：代价低；缺点：发现错误后不能校正
适用于对较短长度（如1字节）的数据进行检错
海明码
将数据分成几组，对每一组都使用奇偶校验码进行检错
在双方都生成校验码后用异或生成K位故障字
假设最多一位发生错误，并且可能的差错以及每一种的种类为：
- 数据中有一位错：M
- 校验码中有一位错：K
- 没错：1
如果能够检错，那么 校验码的长度应该满足：（M为数据的位数）
故障字的作用：每种取值都能反映一种情形（数据出错/校验码出错/未出错）
- 全部是0：没有检测到错误
- 有且仅有1位是1：错误发生在校验码中的某一位，不需要纠正
- 有多位为1：错误发生在数据中的某一位，将𝐷′中对应数据位取反即可纠正（得到𝐷"）
假设数据位为8位，则校验码的布局：
数据位的划分：
规律：校验码总是占据每个单个位是1的情况，并且每个校验位监听的数据位中的数据就是数据位的故障字中位于校验码的故障字为1的那一位为1的情况下的所有故障字所对应的数据位。即：假设C1的故障字为0001，那么C1监听的所有数据就是第四位为1的所有数据，即0011、0101、0111、1001、1011、1101、1111
位安排：将位设置在与其故障字相同的位置（即从低位到高位分别为0001、0010、0011…1111这几个故障字所对应的内容）
示例：
码距和纠错理论
码距：同一编码中，任意两个合法编码之间不同二进制数位数的最小值
假设0000、0001都是合法编码，那么码距为1（两个数只相差最后一位）
假设0000、0011是合法编码，但是0010或者0001都不是合法编码，那么码距就是为2，因为两个合法编码之间差了两位
假设𝐿是码距， 𝐷是检错位数， 𝐶是纠错位数，那么纠错就需要满足：
- 奇偶校验的码距是2， 1位能检错，不能纠错
- 海明码的码距是3，1位能检错和纠错
补充：SEC-DED
在海明码的基础上添加了额外的校验位
循环冗余校验码
奇偶校验码中的问题：
- 额外成本很大
- 要求将数据分成字节
循环冗余校验：
- 适用于以流格式存储和传输大量数据
- 用数学函数生成数据和校验码之间的关系
假设数据有M位，左移数据K位（右侧补0），并用K+1位生成多项式除它**(模2运算)**，得到K位余数作为校验码。校验码放在数据码的后面
校错：如果M+K位数据可以被生成多项式除尽，那么没有错误。否侧有错
模2运算：如果中间余数的最高位是0那么表明可除，上商1，然后将中间余数与除数两者对应位进行异或操作得到下一个中间余数；如果最高位为0那么不可除，上商0，并且与全0进行异或操作得到中间余数
示例：
