# 纠错

两种存储错误：

1. 硬故障：永久性物理故障

2. 软故障：随机非破坏性，改变了某个或某些存储单元的内容，但没有损坏机器

# 基本思想

存储额外的信息以进行检错和校正

# 处理过程

使用函数在数据上生成校验码。传输完成后再生成一次，比较差错

# 常用的数据校验码

# 奇偶校验码

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

• 奇校验：使传输的数据 **（数据位 + 校验位）中有奇数 ** 个 1

• 偶校验：使传输的数据 **（数据位 + 校验位）中有偶数 ** 个 1

传输完成后，根据校验类型生成校验码，比较是否相同。

检错：S=𝐶′′⊕𝐶′

𝑆=0：正确 / 数据中出错的位数为偶数

𝑆=1：数据中出错的位数为奇数

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

# 海明码

• 基本思想：将数据分成几组，对每一组都使用奇偶校验码进行检错

• 处理过程：

  • 分组：将𝑀位数据分成𝐾组

  • 数据输入：为数据𝐷中每组生成 1 位校验码，合并得到𝐾位校验码𝐶

  • 数据输出：为数据𝐷′中每组生成 1 位校验码，合并得到新的𝐾位校验码𝐶′′

  • 检错：将校验码𝐶′′和取出的校验码 C’按位进行异或，生成𝐾位故障字 （syndrome word）

• 故障字的作用

  • 故障字是两个校验码按位异或生成的结果

  • 规则：

    • 全部是 0：没有检测到错误

    • 有且仅有 1 位是 1：错误发生在校验码中的某一位，不需要纠正

    • 有多位为 1：错误发生在数据中的某一位，将𝐷′中对应数据位取反即可纠正

海明码通过在原始数据中插入额外的校验位，使得接收方可以检测并纠正 1 位错误（单比特错误），并检测 2 位错误

# 构造过程

1. 确定校验位的数量

   • 给定数据位的长度为 k，校验位的数量为 r，总长度为 n=k+r。

   • 校验位 r 的数量需满足以下关系： $2^r≥n+1=k+r+1$

   • 例如：如果 k=4（数据位长度），则 r=3 满足条件（2^3=8≥4+3+1）。

2. 确定校验位的位置

   • 校验位插入到数据位中，使其位于指数为 2 的幂的位置（即第 1、2、4、8... 位）。

   • 其他位置存放数据位。

3. 生成校验位

   • 每个校验位负责对特定位置的比特进行校验，位置由 二进制表示决定

   • 例如：校验位 $P_i​$ 负责检查所有位置的二进制表示中第 i 位为 1 的数据位。

   • 一般是偶校验

# 实例

# 码距和纠错理论

# 码距

同一编码中，任意两个合法编码之间不同二进制数位数的最小值

• {0000, 0001, 0010, 0011} 码距为 1

• {0000, 0011} 码距为 2

# 纠错理论

𝑳−𝟏=𝑫+𝑪, 𝑫≥𝑪

𝐿是码距，𝐷是检错位数，𝐶是纠错位数

• 奇偶校验的码距是 2，1 位能检错，不能纠错

• 海明码的码距是 3，1 位能检错和纠错（海明码能 2 位检测 0 位纠错吗？可以）

# 循环冗余校验 CRC

通过将数据看作一个二进制多项式，并对其进行特定的多项式除法运算来生成一个校验值。

数据视为二进制多项式

• 数据位序列被视为一个二进制多项式。例如，数据 1101 对应多项式： $x^3+x^2+1$，每个比特对应多项式的系数。

生成多项式要求最低位和最高位为 1.

# 计算过程

1. 确定生成多项式。如 1011（$G(x)=x^3+x+1$）

2. 在数据后面添加 0，0 的个数为生成多项式的阶数。

3. 对新的数据进行模 2 除法，等价于依次进行异或运算。直到产生余数，即校验码。（余数应比生成多项式少一位）

4. 将校验码加在原来的数据后面，发送。接收方再次进行模 2 除法，检验校验位。