10.数据校验码

1. 错误(Error)

数据在计算机内部进行计算、存取和传送过程中，由于元器件故障或噪音干扰等原因，会出现差错

1. 分类：
   1. 硬故障：永久性的物理故障，以至于受影响的存储单元不能可靠地存储数据，成为固定的“1”或“0”故障，或者在0和1之间不稳定地跳变
      1. 由恶劣的环境、制造缺陷和旧损引起
   2. 软故障：随机非破坏性事件，它改变了某个或某些存储单元的内容，但没有损坏机器
      1. 由电源问题或α粒子引起

2. 纠错（Error Correction）

1. 基本思想：存储额外的信息以进行检错和校正
2. 处理过程
   1. 数据输入：使用函数𝑓在𝑀位数据𝐷上生成𝐾位校验码𝐶
   2. 数据输出：使用函数𝑓在𝑀位数据𝐷’上生成新的𝐾位代码𝐶” ，并与取出的𝐾位码𝐶’进行比较
      1. 没有检测到差错：使用数据𝐷’
      2. 检测到差错且可以校正：校正数据𝐷’来生成数据𝐷”，并用数据𝐷”
      3. 检测到差错但无法纠正：报告

2.1 奇偶校验码

适用于对较短长度（如1字节）的数据进行检错

1. 基本思想：增加1位校验码来表示数据中1的数量是奇数还是偶数

   1. 奇校验：使传输的数据（数据位+校验位）中有奇数个1。1的数量为奇数个，校验码为0。
   2. 偶校验：使传输的数据（数据位+校验位）中有偶数个1。1的数量为偶数个，校验码为0。

2. 处理过程：

   

   

3. 优点：代价低（只需要1位额外数据，计算简单）

4. 缺点：

   1. 不能发现出错位数为偶数的情形
   2. 发现错误后不能校正

2.2 海明码

1. 基本思想：将数据分成几组，对每一组都使用奇偶校验码进行检错。某些组的校验码出现错误，就说明同时出现在这些组的某位出现了错误。

2. 处理过程（将𝑀位数据分成𝐾组 ）：

   1. 数据输入：为数据𝐷中每组生成1位校验码，合并得到𝐾位校验码𝐶
   2. 数据输出：为数据𝐷′中每组生成1位校验码，合并得到新的𝐾位校验码𝐶′′
   3. 检错：将校验码𝐶′′和取出的校验码C’ 按位进行异或，生成𝐾位故障字（syndrome word）

3. 校验码长度（也就是分为几组，k）

   1. 假设最多1位发生错误

   2. 可能的情况：

      1. 数据中有1位出现错误：M
      2. 校验码中有1位出现错误：𝐾
      3. 没有出现错误：1

   3. 2^𝐾^ ≥ 𝑀 + 𝐾 + 1：根据𝑀求出最小的k。

      1. 解释：校验码的每一个取值，都代表一种情况。
      2. 故障字的情况：
         1. 全部是0：没有检测到错误
         2. 有且仅有1位是1：错误发生在校验码中的某一位，不需要纠正
         3. 有多位为1：错误发生在数据中的某一位，将𝐷′中对应数据位取反即可纠正（得到𝐷”）

      

2.3 循环冗余校验

可见：[Git为了保护我们的屎山，悄悄做了什么努力？

Sa1i3ri](https://sa1i3ri.github.io/posts/校检和/)

适用于以流格式存储和传输大量数据

用数学函数生成数据和校验码之间的关系

1. 基本思想：

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

2. 校错

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

3. 示例：