📝 前言

在之前的硬件篇系列文章中，我们系统地学习了处理器、存储器、总线、接口和外部设备。有读者可能会问：为什么没有校验码部分？

实际上，校验码属于计算机系统基础知识的数据表示与可靠性范畴，它与硬件紧密相关但并非硬件本身。在计算机系统中，数据在存储（内存/磁盘）和传输（总线/网络）过程中可能因各种干扰而发生错误，校验码正是检测甚至纠正这些错误的关键技术。

对于架构师考试而言，校验码是必考内容，通常涉及基本概念、校验原理、编码/解码方法以及相关计算。本文将系统梳理常见的校验码技术，包括奇偶校验码、海明校验码、循环冗余校验码（CRC），并结合历年真题，帮助你在复习中掌握这一重要知识点。

一、为什么需要校验码？

1.1 数据错误的来源

在计算机系统中，数据在存储和传输过程中可能发生错误，主要原因包括：

• 噪声干扰：电磁干扰、信号反射、串扰等

• 硬件故障：存储介质老化、接触不良、电源波动

• 时序问题：信号延迟、时钟偏移

• 环境因素：温度变化、辐射、震动

1.2 错误类型

1.3 校验码的基本思想

校验码的核心思想是：在原始数据的基础上，按照某种规则添加额外的冗余信息（校验位），使数据之间建立某种数学关系。接收方或读取方通过验证这种关系来判断数据是否出错，甚至定位错误位置并纠正。

基本术语：

• 码字：原始数据 + 校验位构成的完整编码

• 码距（海明距离）：两个码字之间不同位的个数

• 检错能力：能检测出几位错误

• 纠错能力：能纠正几位错误

码距与检错/纠错能力的关系：

• 要检测 e 位错误，码距应满足：d ≥ e + 1

• 要纠正 t 位错误，码距应满足：d ≥ 2t + 1

• 要检测 e 位错误并纠正 t 位错误，码距应满足：d ≥ e + t + 1（其中 e ≥ t）

二、奇偶校验码

2.1 基本原理

奇偶校验码是最简单、最基础的检错码。其原理是：在原始数据末尾增加1位校验位，使得整个码字（数据位+校验位）中“1”的个数为奇数（奇校验）或偶数（偶校验）。

• 奇校验：使码字中1的个数为奇数

• 偶校验：使码字中1的个数为偶数

2.2 编码示例

例：原始数据 1010（4位）

• 奇校验：

• 数据中1的个数为2（偶数），要使总数为奇数，校验位应为1

• 码字：10101（1的个数为3，奇数）

• 偶校验：

• 数据中1的个数为2（偶数），要使总数保持偶数，校验位应为0

• 码字：10100（1的个数为2，偶数）

2.3 检错原理

接收方收到码字后，计算其中1的个数是否符合约定的奇偶性：

• 若符合，则认为数据正确（但可能有偶数位错误无法检测）

• 若不符合，则确定数据出错

2.4 优缺点

2.5 应用场景

• 内存条上的奇偶校验内存（早期PC）

• 串行通信中的简单校验（如UART可配置奇偶校验位）

• 作为更复杂校验码的组成部分

注意：现代内存普遍使用ECC内存（Error-Correcting Code），而非简单的奇偶校验。

三、海明校验码

海明码（Hamming Code）是由理查德·海明于1950年提出的，是一种既能检测错误，又能定位并纠正单比特错误的校验码。

3.1 基本原理

海明码的核心思想是：在数据位之间插入多个校验位，每个校验位负责校验一组特定的数据位。当发生错误时，通过各校验位的校验结果（称为校验和或症状）可以唯一地定位出错位置。

海明码的码距为3，因此可以：

• 检测2位错误

• 纠正1位错误

3.2 校验位位置的确定

对于k位数据位，需要的校验位数量r满足：

text

2^r ≥ k + r + 1

常见对应关系：

3.3 校验位的放置规则

海明码中，校验位被放置在2的幂次位置（第1、2、4、8、16…位），数据位按顺序填充剩余位置。

示例：4位数据位 D1 D2 D3 D4（对应数据位标记为d1~d4），需要3位校验位 P1 P2 P4（放在第1、2、4位），码字共7位，位置编号从1开始：

3.4 校验位的计算方法

每个校验位负责校验一组特定的数据位，分组规则是：

• 将位置编号写成二进制形式，凡是该二进制位为1的校验位都参与校验该位。

以7位海明码（4位数据 + 3位校验位）为例，分组如下：

编码步骤：

1. 将数据位填入对应位置（校验位位置暂时空出）。

2. 对于每个校验位，计算其所负责的所有数据位的异或和（偶校验），使得该组（包括校验位自身）中“1”的个数为偶数。

示例：数据位 D1 D2 D3 D4 = 1011（即 D1=1，D2=0，D3=1，D4=1）。 数据位在码字中的位置：

• D1 → 位置3

• D2 → 位置5

• D3 → 位置6

• D4 → 位置7

计算各校验位：

• P1（负责位置3、5、7的数据位）：D1 ⊕ D2 ⊕ D4 = 1 ⊕ 0 ⊕ 1 = 0  为使包含P1的组（位置1,3,5,7）总1个数为偶数，P1应取 0。

• P2（负责位置3、6、7的数据位）：D1 ⊕ D3 ⊕ D4 = 1 ⊕ 1 ⊕ 1 = 1  为使包含P2的组（位置2,3,6,7）总1个数为偶数，P2应取 1。

• P4（负责位置5、6、7的数据位）：D2 ⊕ D3 ⊕ D4 = 0 ⊕ 1 ⊕ 1 = 0  为使包含P4的组（位置4,5,6,7）总1个数为偶数，P4应取 0。

完整码字（位置1~7）：

最终码字：0110011

3.5 检错与纠错原理

接收方收到码字后，重新计算每个校验组（包括校验位本身）的异或和，得到校验和（症状字）S1、S2、S4。若全为0，则无错；否则，由 S4 S2 S1 组成的二进制数即为出错的位置。

错误模拟

假设在传输过程中，位置5（D2）从0翻转为1，接收方收到的码字变为：

0110111（即位置5变为1）

现在重新计算各组的异或和：

• S1（位置1,3,5,7）：P1 ⊕ D1 ⊕ D2 ⊕ D4 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1  （计算过程：0⊕1=1，1⊕1=0，0⊕1=1）

• S2（位置2,3,6,7）：P2 ⊕ D1 ⊕ D3 ⊕ D4 = 1 ⊕ 1 ⊕ 1 ⊕ 1 = 0  （1⊕1=0，0⊕1=1，1⊕1=0）

• S4（位置4,5,6,7）：P4 ⊕ D2 ⊕ D3 ⊕ D4 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1  （0⊕1=1，1⊕1=0，0⊕1=1）

症状字：S4 S2 S1 = 101（二进制），即十进制的 5，准确指出了错误发生在第5位。

将第5位取反（1→0），即可恢复原始码字 0110011，再从中提取数据位（位置3,5,6,7）得到正确的数据 1011。

3.6 海明码总结

3.7 拓展：海明码的改进

扩展海明码：增加一位全校验位，使码距增加到4，可检测2位错误并纠正1位错误，或检测3位错误。

四、循环冗余校验码（CRC）

CRC（Cyclic Redundancy Check）是一种检错能力极强的校验码，广泛应用于数据通信和存储系统中。

4.1 基本原理

CRC基于多项式除法的思想：

• 将二进制数据看作一个多项式，系数为0或1

• 发送方和接收方约定一个生成多项式G(x)

• 发送方在数据末尾添加校验位，使得整个码字多项式能被G(x)整除

• 接收方用同样的G(x)去除接收到的码字，若余数为0，则认为传输正确；否则出错

4.2 编码步骤

1. 确定生成多项式：如CRC-16、CRC-32等

2. 数据扩展：在原始数据后面添加r个0，r为生成多项式的最高次幂

3. 模2除法：用扩展后的数据除以生成多项式，得到余数（r位）

4. 发送码字：原始数据 + 余数（替换之前添加的0）

模2除法特点：

• 不借位减法，实际上是异或运算

• 每一步看被除数最高位，如果为1则进行异或，如果为0则直接下移

4.3 示例

假设数据为 1010，生成多项式 G(x) = x^3 + x + 1，即二进制 1011（最高次幂3，所以校验位3位）。

1. 数据后加3个0：1010000

2. 用 1010000 除以 1011（模2除法）：

1011 ) 1010000              1011      (对齐前4位，商1)              ----               0010     (第一次余数，下拉下一位0)                 000     (商0，直接下拉)               00100     (第二次余数，下拉下一位0)                 000      (商0，直接下拉)               001000    (第三次余数，下拉下一位0)                  1011    (对齐后4位，商1)                  ----                   0011   (最终余数)

最终余数为011（3位）

1. 发送码字：原始数据 + 余数 = 1010011

接收方用 1010011 除以 1011，余数为0则正确。

4.4 CRC的检错能力

CRC的检错能力取决于生成多项式的选择。一般来说：

• 能检测出所有单比特错误

• 能检测出所有双比特错误（如果生成多项式适当）

• 能检测出所有奇数位错误

• 能检测出所有长度不超过r位的突发错误（r为校验位位数）

• 对于长度超过r位的突发错误，漏检概率约为1/2^r

4.5 常用CRC标准

4.6 CRC的硬件实现

CRC非常适合硬件实现，可以使用线性反馈移位寄存器（LFSR）快速计算。

五、三种校验码对比

六、校验码在计算机系统中的应用

6.1 内存中的校验

• 奇偶校验内存：每字节附加1位校验位，只能检测奇数位错误，服务器领域已被ECC取代

• ECC内存：使用海明码或更先进的纠错码（如Reed-Solomon），可纠正单比特错误，检测多比特错误

6.2 存储设备中的校验

• 硬盘：每个扇区通常有ECC校验（如50字节数据+几十字节ECC）

• SSD：NAND Flash每页有ECC校验，主控实时检测纠正

• 光盘：CIRC（交叉交织里德-所罗门码）纠错

6.3 通信协议中的校验

• 以太网：帧尾部有CRC-32校验

• USB：CRC-16/CRC-5

• TCP/IP：首部校验和（但IP首部校验和是简单的16位累加和，不是CRC）

• Wi-Fi：CRC-32

6.4 RAID中的校验

RAID 3/4/5/6使用异或校验或更复杂的Reed-Solomon码实现数据冗余。

七、历年考点与真题举例

题型一：奇偶校验基本概念

例题1：采用奇校验，若接收方收到的数据为1010110（含校验位），则以下判断正确的是（ ）

A. 数据正确 B. 数据错误 C. 可能正确也可能错误 D. 无法判断

解析：奇校验要求1的个数为奇数。1010110中1的个数为4（偶数），所以一定出错。但注意，如果是偶数位错误，可能检测不出，但这里已知是接收到的数据，我们只能判断奇偶性。正确答案是 B。

例题2：奇偶校验码只能检测（ ）位错误。

A. 1 B. 2 C. 奇数 D. 偶数

解析：奇偶校验只能检测奇数位错误，无法检测偶数位错误。正确答案是 C。

题型二：海明码计算

例题3：对于8位数据，采用海明码校验，需要多少位校验位？

解析：由公式 2^r ≥ k + r + 1，k=8，尝试r=4：2^4=16，8+4+1=13，满足。r=3：2^3=8，8+3+1=12，8<12不满足。所以需要 4 位校验位。

例题4：采用海明码，接收方收到的码字为0011011（位置1~7，偶校验），已知发送的数据位为4位，问是否有错？若有，请纠正。

解析：

• 7位码字，4位数据，3位校验位（位置1、2、4）

• 将码字填入：位置1=0,2=0,3=1,4=1,5=0,6=1,7=1

• 计算校验和：  S1 = P1(1)⊕D1(3)⊕D2(5)⊕D4(7) = 0⊕1⊕0⊕1 = 0  S2 = P2(2)⊕D1(3)⊕D3(6)⊕D4(7) = 0⊕1⊕1⊕1 = 1  S4 = P4(4)⊕D2(5)⊕D3(6)⊕D4(7) = 1⊕0⊕1⊕1 = 1

• S4S2S1 = 110二进制 = 6，表示位置6出错

• 将位置6取反：原来为1，改为0

• 纠正后的码字：0011001

• 数据位在位置3,5,6,7：位置3=1,5=0,6=0,7=1 → 数据为 1001（注意顺序：D1位置3，D2位置5，D3位置6，D4位置7）

题型三：CRC计算

例题5：采用CRC校验，生成多项式为G(x)=x^3+x+1（1011），若待发送的数据为1101，求CRC校验码。

解析：

• 数据1101，加3个0得1101000

• 模2除法：

1101000 1011   （对齐） — 0110000（异或结果）   1011  （右移一位） — 001110（余数）

逐步计算： 第一步：1101 XOR 1011 = 0110，下移一位0得01100 第二步：01100的最高位0，直接下移一位得11000 第三步：11000 XOR 1011 = 1110，下移一位0得11100 第四步：11100 XOR 1011 = 1110？不对，11100对齐1011：11100 XOR 1011 = 1110？11100最高位1，对齐1011：11100 XOR 1011 = 1110？我们写清楚：

11100 1011 对齐

01110（异或结果）

所以余数为011？还有一位？实际上我们做了三次异或，最后余数应为011？我们继续：

11100 XOR 1011 = 01110（这是中间结果），还有一位0没下移？我们最好列竖式：

      1101000 除数   1011       1011    (对齐前四位)       —-        0110   (异或结果，下移一位0)         1100  (现在被除数是1100)         1011  (对齐)         —-         0111  (异或结果，下移一位0)          1110 (现在被除数是1110)          1011 (对齐)          —-          0101 (异或结果，下移一位0)           101 (现在被除数是101，不够除，余数为101)

所以余数为101，CRC校验码为101，发送码字为1101101。

例题6：接上题，接收方收到1101101，用G(x)=1011校验，余数应为多少？说明什么？

解析：

• 1101101 ÷ 1011，计算后余数为0，说明传输正确。

题型四：综合应用

例题7：某通信系统要求误码率低于10^-9，采用CRC-32校验，问漏检概率约为多少？

解析：CRC-32的漏检概率约为1/2^32 ≈ 2.33×10^-10，满足要求。

八、实践问题与解决方案

8.1 问题：内存偶尔出现随机错误

现象：服务器偶尔崩溃，日志中无明确错误，但内存测试发现零星错误。

分析：可能是宇宙射线或硬件老化导致的软错误。

解决方案：

• 启用BIOS中的ECC内存支持（需硬件支持）

• 更换为ECC内存

• 对于非ECC内存，可运行内存测试软件（Memtest86+）确认是否有硬件故障

8.2 问题：网络传输偶尔数据包损坏

现象：文件传输偶尔失败，下载的压缩包解压报错。

分析：以太网有CRC-32校验，损坏包会被丢弃，但如果网卡或交换机故障，可能产生错误。

解决方案：

• 检查网线、接口是否接触良好

• 更新网卡驱动

• 在应用层增加校验（如TCP有校验和，但可靠性不如CRC）

• 使用更可靠的传输协议（如TCP本身有校验，UDP需要应用层自己加校验）

8.3 问题：存储介质数据腐坏

现象：长期存储的文件偶尔打不开，或打开后内容错误。

分析：硬盘/SSD/光盘长期存放可能发生位翻转。

解决方案：

• 使用支持校验的文件系统（如ZFS、Btrfs）

• 定期校验重要数据并备份

• 存储时添加额外校验信息（如PAR2恢复卷）

• 对于重要数据，采用RAID存储（但RAID不能代替备份）

九、复习建议与记忆口诀

9.1 知识体系梳理

校验码复习主线： 为什么需要校验码（错误来源、检错/纠错概念、码距）     ↓ 奇偶校验（原理、优缺点、只能检奇数错）     ↓ 海明码（校验位数量公式、位置规则、分组、检错纠错）     ↓ CRC（多项式表示、模2除法、生成多项式、检错能力）     ↓ 三种校验码对比及应用场景

9.2 记忆口诀

校验码分类：

奇偶校验最简单，一位校验检奇数 海明码来纠一位，分组校验找位置 CRC检错能力强，多项式除法来帮忙

海明码位置公式：

校验位在2的幂，其他位置放数据 分组按二进制位，哪组有错位可知

CRC口诀：

数据后面加零头，除以多项式得余数 余数替换零头位，接收端除零即正确

9.3 高频考点

结语

校验码是计算机系统中保障数据可靠性的重要技术，从简单的奇偶校验到强大的CRC，每种校验码都有其适用场景。作为架构师，理解这些技术的原理和特点，能够在系统设计中选择合适的校验机制，确保数据的完整性和可靠性。