2. 奇偶校验（Parity Check）
2.1 基本原理
- 奇校验（Odd Parity）或 偶校验（Even Parity）在原始数据后面 附加 1 位校验位（Parity Bit），使得 整个码字中 1 的个数为奇数（奇校验）或偶数（偶校验）。
- 接收端重新统计 1 的个数，若不符合约定的奇/偶性，则判定出现错误。
优点：实现极其简单，只需异或（XOR）一次即可得到校验位。
缺点：只能检测 奇数个比特错误，对偶数个错误（如两个比特同时翻转）无能为力。
2.2 手算示例（偶校验）
假设要发送的 8 位数据为：
1
|
数据位 D = 1 0 1 1 0 0 1 0
|
- 统计 1 的个数：
1+0+1+1+0+0+1+0 = 4（偶数）。
- 偶校验要求 整体 1 的个数为偶数，所以 校验位 P = 0（不需要再补 1）。
- 发送的码字为
D‖P = 1 0 1 1 0 0 1 0 0（共 9 位）。
接收端检测
- 若在传输中第 3 位被翻转，收到
1 0 0 1 0 0 1 0 0，1 的个数变为 3（奇数） → 检测到错误。
- 若第 3 位和第 5 位同时翻转，收到
1 0 0 1 1 0 1 0 0，1 的个数仍为 4（偶数） → 未检测到错误（偶数错误被掩盖）。
2.3 代码实现（Python）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
def even_parity_bit(data: bytes) -> int:
"""返回 data（字节序列）的偶校验位（0 或 1）。"""
# 统计所有位中 1 的个数
ones = sum(bin(b).count('1') for b in data)
# 偶校验：若 1 的个数为奇数，需要补 1；否则补 0
return ones % 2
def add_even_parity(data: bytes) -> bytes:
"""在 data 末尾添加一个字节的校验位（仅最低位有效）。"""
p = even_parity_bit(data)
# 将校验位放在最低位，其余位填 0
return data + bytes([p])
# 示例
payload = b'\xB2' # 1011 0010
codeword = add_even_parity(payload)
print(f"原始: {payload.hex()}, 校验位: {codeword[-1] & 1}, 码字: {codeword.hex()}")
|
3. 循环冗余校验（Cyclic Redundancy Check, CRC）
3.1 基本原理
CRC 把 待发送的比特序列 看作一个 二进制多项式（系数为 0/1），并 除以 预先约定的 生成多项式（Generator Polynomial），取余数作为 冗余校验码（CRC 码） 附加在数据后面。
-
发送端：
- 把原始数据左移
r 位（r 为生成多项式的阶数，即最高次幂），相当于在低位补 r 个 0。
- 用 模 2 除法（即不进位的二进制除法，等价于 XOR）除以生成多项式，得到余数
R（长度为 r 位）。
- 将
R 附加到左移后的数据后面，形成 发送码字。
-
接收端：
- 对收到的码字同样用相同的生成多项式进行模 2 除法。
- 若余数为全 0，则认为 没有检测到错误；否则判定 出现错误。
检测能力
- 能检测所有 单比特错误、双比特错误、奇数个错误（取决于生成多项式的特性）。
- 能检测所有长度 ≤
r 的 突发错误（即连续错误位数不超过 r）。
- 对于更长的突发错误，检测概率取决于生成多项式，一般非常高（> 99.9%）。
3.2 常用生成多项式
| 标准 |
多项式（十六进制） |
阶数 r |
用途 |
| CRC‑4‑ITU |
x⁴ + x + 1 → 0x3 |
4 |
简单实验 |
| CRC‑8 |
x⁸ + x² + x + 1 → 0x07 |
8 |
1‑Wire、蓝牙 |
| CRC‑16‑CCITT |
x¹⁶ + x¹² + x⁵ + 1 → 0x1021 |
16 |
X.25、PPP |
| CRC‑32 (IEEE 802.3) |
x³² + x²⁶ + x²³ + x²² + x¹⁶ + x¹² + x¹¹ + x¹⁰ + x⁸ + x⁷ + x⁵ + x⁴ + x² + x + 1 → 0x04C11DB7 |
32 |
以太网、ZIP、PNG |
下面用 CRC‑4‑ITU（生成多项式 G(x)=x⁴ + x + 1，二进制 10011）演示一次完整的手算过程。
3.3 手算示例（CRC‑4‑ITU）
原始数据（二进制）：
1
|
D = 1 0 1 1 0 1 1 0 (8 位)
|
生成多项式：
1
|
G = 1 0 0 1 1 (5 位，阶数 r = 4)
|
步骤 1：左移 r 位（在低位补 4 个 0）
1
|
D' = 1 0 1 1 0 1 1 0 0 0 0 0 (12 位)
|
步骤 2：模 2 除法（XOR）求余数
我们用 二进制长除法，每次把最高位对齐后进行 XOR，直到剩余位数 < r+1（即 <5 位）为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
1 0 1 1 0 1 1 0 0 0 0 0 ← 被除数（D'）
÷ 1 0 0 1 1 ← 除数（G）
-------------------------------------------------
1) 对齐最高位（第 1 位是 1），进行 XOR：
1 0 1 1 0 1 1 0 0 0 0 0
⊕ 1 0 0 1 1
-----------------
0 0 1 0 1 1 0 0 0 0 0 (去掉最高位的 0，左移 1 位)
2) 最高位仍为 1（第 3 位），再 XOR：
0 0 1 0 1 1 0 0 0 0 0
⊕ 1 0 0 1 1
-----------------
0 0 0 1 0 1 0 0 0 0 (去掉前导 0)
3) 最高位为 1（第 4 位），再 XOR：
0 0 0 1 0 1 0 0 0 0
⊕ 1 0 0 1 1
-----------------
0 0 0 0 1 1 1 0 0 (去掉前导 0)
4) 最高位为 1（第 5 位），再 XOR：
0 0 0 0 1 1 1 0 0
⊕ 1 0 0 1 1
-----------------
0 0 0 0 0 1 0 1 1 (去掉前导 0)
5) 最高位为 1（第 6 位），再 XOR：
0 0 0 0 0 1 0 1 1
⊕ 1 0 0 1 1
-----------------
0 0 0 0 0 0 1 1 0 (去掉前导 0)
6) 最高位为 1（第 7 位），再 XOR：
0 0 0 0 0 0 1 1 0
⊕ 1 0 0 1 1
-----------------
0 0 0 0 0 0 0 1 1 (余数长度已 <5)
余数 R = **1 1**（实际应补齐到 4 位） → `0011`
|
步骤 3：形成发送码字
把余数 R（4 位）附加到原始数据后面：
1
|
码字 T = D ‖ R = 1 0 1 1 0 1 1 0 0 0 1 1
|
即十进制 0xB6 0x03（如果按字节划分）。
接收端验证
接收端对 T 再次进行同样的模 2 除法：
如果在传输过程中出现了 单比特错误（比如第 2 位被翻转），余数将不为 0，检测成功。
3.4 代码实现（Python）
下面给出一个通用的 位级 CRC 实现，支持任意生成多项式（以整数形式给出）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
def crc_remainder(data: bytes, poly: int, width: int) -> int:
"""
计算 CRC 余数（remainder）。
- data: 待校验的原始字节序列
- poly: 生成多项式（整数形式），最高位必须为 1
- width: 多项式的阶数（即 CRC 位数），比如 CRC-4 => width=4
返回值为 width 位的余数（整数）。
"""
# 把 data 转为一个大的整数（左移 width 位后再加 0）
# 例如 data = b'\xB6' (10110110) -> 0b10110110
# 左移 width 位相当于在低位补 width 个 0
data_int = int.from_bytes(data, 'big')
data_int <<= width
# 生成多项式的位宽（包括最高位 1）
poly_shift = poly.bit_length() - 1 # 例如 0b10011 -> 4
# 进行模 2 除法（XOR）直到被除数的位数 < poly_shift + width
while data_int.bit_length() >= poly_shift + 1:
shift = data_int.bit_length() - (poly_shift + 1)
data_int ^= (poly << shift)
# 此时 data_int 即为余数，确保只保留 width 位
return data_int & ((1 << width) - 1)
def crc_encode(data: bytes, poly: int, width: int) -> bytes:
"""返回 data + CRC（宽度为 width 位）的完整码字（字节序列）。"""
remainder = crc_remainder(data, poly, width)
# 将余数左移到最低位后拼接到原始数据后面
# 这里假设 width <= 8，直接作为一个字节追加；若 width>8 需要更通用的处理
if width <= 8:
return data + bytes([remainder])
else:
# 把 remainder 按宽度拆成若干字节（高位在前）
n_bytes = (width + 7) // 8
return data + remainder.to_bytes(n_bytes, 'big')
def crc_check(frame: bytes, poly: int, width: int) -> bool:
"""检查收到的帧（data+crc）是否无误，返回 True 表示校验通过。"""
# 直接对整个帧做 CRC 计算，若余数为 0 则通过
return crc_remainder(frame, poly, width) == 0
# 示例：使用 CRC-4-ITU (poly=0b10011, width=4)
poly = 0b10011
width = 4
payload = bytes([0b10110110]) # 0xB6
frame = crc_encode(payload, poly, width)
print(f"原始数据: {payload.hex()}, CRC 帧: {frame.hex()}")
# 验证
print("校验通过?" , crc_check(frame, poly, width))
# 演示一次错误：翻转第 2 位
error_frame = bytearray(frame)
error_frame[0] ^= 0b01000000 # 把第 2 位 (从左数) 翻转
print("错误帧:", error_frame.hex())
print("校验通过?" , crc_check(error_frame, poly, width))
|
运行结果（示例）：
1
2
3
4
|
原始数据: b6, CRC 帧: b603
校验通过? True
错误帧: b503
校验通过? False
|
b6（10110110）是原始 8 位数据。03（00000011）是 4 位 CRC（左侧 4 位为 0，实际 CRC 为 0011），拼接后得到 b603。- 当我们把第 2 位翻转后得到
b503，校验不通过，说明 CRC 成功检测到了错误。
3.5 CRC 与奇偶校验的对比
| 项目 |
奇偶校验 |
CRC |
| 实现复杂度 |
极低（一次 XOR） |
较高（循环左移或表查） |
| 检测能力 |
只能检测奇数个错误，无法检测偶数错误 |
能检测单比特、双比特、奇数错误以及长度 ≤ r 的突发错误 |
| 冗余位数 |
1 位 |
r 位（常见 8、16、32 位） |
| 常见应用 |
串口、低速总线、磁盘块校验 |
以太网、USB、存储介质、无线链路、文件压缩等 |
| 误检率 |
0（只要出现奇数错误必检测）但 漏检率 较高（偶数错误不被检测） |
误检率极低（取决于生成多项式），通常 < 10⁻⁵ |
| 适用场景 |
对错误率要求不高、资源受限的系统 |
对可靠性要求高、错误模式复杂的通信链路 |
4. 小结
- 奇偶校验：实现最简单，只用 1 位冗余，能够检测 奇数个错误，但对偶数错误无能为力。适用于 低速、低成本 的场合。
- 循环冗余校验（CRC）：通过 模 2 多项式除法 产生
r 位冗余，能够检测 单比特、双比特、奇数错误 以及 长度 ≤ r 的突发错误，检测能力远强于奇偶校验。常见的 CRC‑8、CRC‑16、CRC‑32 在各种网络协议和存储介质中得到广泛使用。
- 实现要点：
- 选取合适的 生成多项式（决定检测能力）。
- 发送端 左移
r 位后做模 2 除法，余数即 CRC。
- 接收端 同样除法，余数为 0 则认为无误。
- 在软件实现中，常用 查表法（256 条目）或 位移/异或循环 来加速运算。
记录生活