差错控制

数据在通信信道中传输时，会受到噪声、干扰、衰减和信号失真的影响，导致接收数据与发送数据不一致。

为了将错误降低到系统允许的范围，需要使用：

Error Control（差错控制）

差错控制的基本思想是：在原始信息中增加一定数量的冗余信息，使接收方能够发现或纠正传输错误。

本节主要内容包括：

1. 差错产生的原因；
2. 随机错误与突发错误；
3. 检错与纠错；
4. 海明码；
5. 循环冗余校验码。

差错控制
│
├─ 差错产生原因
│  ├─ 热噪声
│  ├─ 冲击噪声
│  ├─ 信号失真
│  └─ 串扰
│
├─ 差错类型
│  ├─ 随机错误
│  └─ 突发错误
│
├─ 控制策略
│  ├─ 检错后重传
│  └─ 接收端直接纠错
│
└─ 典型编码
   ├─ 海明码
   └─ CRC循环冗余校验码

Thermal Noise（热噪声）是由电子随机热运动产生的噪声。

主要特点：

• 在通信线路中持续存在；
• 具有较宽的频谱；
• 通常幅度较小；
• 对数据位的影响具有随机性；
• 往往只造成个别位错误；
• 信噪比越高，热噪声引起的错误越少。

热噪声通常引起：

Random Error（随机错误）

Impulse Noise（冲击噪声）是短时间出现、但瞬间幅度很大的干扰。

常见来源包括：

• 雷电；
• 电焊机；
• 电动机启停；
• 电力设备瞬态变化；
• 开关设备；
• 外界突发电磁干扰。

冲击噪声的特点：

• 持续时间短；
• 瞬时幅度大；
• 可能同时影响多个连续数据位；
• 容易形成一串连续错误。

冲击噪声通常引起：

Burst Error（突发错误）

信号幅度、传播速度与相位、频率等参数有关。信号在传输过程中可能出现：

• 幅度失真；
• 相位失真；
• 频率失真；
• 延迟失真；
• 波形畸变。

接收端可能因此错误判断信号状态，从而产生差错。

Crosstalk（串扰）是相邻线路或相邻信道之间发生信号耦合，一个信号对另一个信号产生干扰的现象。

串扰通常具有突发性，也可能导致多个数据位连续出错。

突发错误长度是指从第一个错误位开始，到最后一个错误位结束所覆盖的总位数。

例如：

发送数据：110101101001

接收数据：110'''01011'''1001

突发错误范围内不要求每一位都发生错误。只要第一个错误位与最后一个错误位之间覆盖5位，突发错误长度就是5。

假设：

• 原始信息长度为 k 位；
• 增加 r 位冗余信息；
• 编码后总长度为 n 位。

则：

''n＝k＋r''

其中：

发送方按照确定的算法，根据原始信息计算冗余位，再将信息位与冗余位一起发送。

接收方对收到的数据使用同一算法：

• 若校验结果一致，则认为数据没有检测到错误；
• 若校验结果不一致，则认为数据发生错误；
• 若编码具有纠错能力，还可以进一步确定错误位置。

增加冗余位会降低有效数据比例。

编码效率为：

''η＝k÷(k＋r)''

例如，7位信息增加1位校验位：

''η＝7÷8＝87.5%''

冗余位越多：

• 检错、纠错能力通常越强；
• 传输开销越大；
• 有效数据率越低；
• 编码和译码过程越复杂。

Error Detection（检错）是指接收方能够判断数据发生了错误，但通常不能确定正确数据是什么。

发现错误后，接收方可以请求发送方重新传输。

这种策略称为：

ARQ（Automatic Repeat reQuest，自动重传请求）

发送数据
    ↓
接收端执行校验
    ↓
是否检测到错误？
├─ 否：接收数据
└─ 是：请求发送方重传

Error Correction（纠错）是指接收方不仅知道发生了错误，还能确定错误位置并恢复正确数据。

利用冗余信息在接收端直接完成纠错的技术称为：

FEC（Forward Error Correction，前向纠错）

1950年，理查德·海明研究了利用冗余位检测和纠正代码错误的方法。

Hamming Code（海明码）是一类通过增加多个校验位，实现错误检测和错误定位的线性分组码。

海明码的基本思想是：

• 将校验位放置在特定位置；
• 每个校验位检查一组数据位；
• 不同数据位参加不同的校验组合；
• 接收端根据校验失败的组合计算错误位置；
• 将错误位取反即可完成单比特纠错。

一个码字中二进制1的数量称为：

Hamming Weight（海明重量）

例如：

''10110100''

其中有4个1，因此：

''海明重量＝4''

两个等长码字在对应位置上不同的位数称为：

Hamming Distance（海明距离）

可通过按位异或计算：

码字A：10110110

码字B：10011100

异或值：00101010

异或结果中有3个1，因此：

''d(A,B)＝3''

其中：

XOR（Exclusive OR，异或）的运算规则是：

一个编码系统中，任意两个合法码字之间海明距离的最小值称为：

Minimum Hamming Distance（最小海明距离）

通常记作：

''d_min''

最小海明距离决定了编码能够检测和纠正多少位错误。

如果最小海明距离为 d_min，则最多能够保证检测：

''d_min－1''

位错误。

若要保证检测 s 位错误，需要满足：

''d_min≥s＋1''

例如：

如果要保证纠正 t 位错误，需要满足：

''d_min≥2t＋1''

最大保证纠错位数为：

''t_max＝⌊(d_min－1)÷2⌋''

其中 ⌊x⌋ 表示向下取整。

一个长度为 n 的二进制码字，可以看成 n 维超立方体中的一个顶点。

两个码字之间的海明距离，就是两个顶点之间需要改变的最少坐标数量。

如果两个合法码字的距离为 d：

• 小于或等于 d－1 位的错误可以被检测；
• 小于 d÷2 位的错误可以被纠正。

纠错的本质是将接收到的错误码字判断为距离最近的合法码字。

7位ASCII数据增加1位奇偶校验后形成8位码字。

这些合法码字之间的最小海明距离为2，因此：

• 可以检测所有1位错误；
• 不能纠正1位错误；
• 不能保证发现所有2位错误。

ASCII（American Standard Code for Information Interchange，美国信息交换标准代码）

设：

• 原始数据有 m 位；
• 增加 k 位校验位；
• 编码后总长度为 n＝m＋k。

对于单比特纠错，每一个有效码字需要区分：

• n个单比特错误位置；
• 1种没有错误的情况。

因此，一个有效码字需要对应：

''n＋1''

种可识别状态。

由于 k 位校验位可以表示 2^k 种状态，所以必须满足：

''2^k≥n＋1''

代入 n＝m＋k：

''2^k≥m＋k＋1''

也可以写成：

''m＋k＋1≤2^k''

这就是单比特纠错海明码校验位数量的基本条件。

对于 m 位数据，有：

''2^m''

个有效信息。

每个有效码字需要表示：

• 1种无错误状态；
• n种单比特错误状态。

总共需要：

''2^m(n＋1)''

个可区分码字。

长度为 n 的二进制码字共有：

''2^n''

种可能，因此：

''2^m(n＋1)≤2^n''

因为：

''n＝m＋k''

所以：

''n＋1≤2^k''

最终得到：

''m＋k＋1≤2^k''

给定数据位 m 后，从较小的 k 开始尝试：

''2^k≥m＋k＋1''

取满足条件的最小 k。

例如，8位数据：

尝试 k＝3：

''2³＝8''

''8＋3＋1＝12''

''8<12''，不满足。

尝试 k＝4：

''2⁴＝16''

''8＋4＋1＝13''

''16≥13''，满足。

因此，8位数据至少需要4位海明校验位。

海明码把校验位放在序号为2的整数次幂的位置：

• 第1位：2⁰＝1
• 第2位：2¹＝2
• 第4位：2²＝4
• 第8位：2³＝8
• 第16位：2⁴＝16

其余位置用于存放数据位。

以11位码字为例：

其中：

• P1、P2、P4、P8是校验位；
• D1～D7是数据位。

把每个位置编号写成二进制数：

一个位置参加哪些校验，由其二进制编号中哪些位为1决定。

例如，第6位：

''6＝0110₂''

其2位和4位为1，因此第6位参加：

• P2校验；
• P4校验；
• 不参加P1和P8校验。

第9位：

''9＝1001₂''

其1位和8位为1，因此第9位参加：

• P1校验；
• P8校验。

教材示例的原始数据为：

''1001011''

将7个数据位依次放入：

''3、5、6、7、9、10、11''

号位置。

P1检查：

''1、3、5、7、9、11''

不考虑P1本身，数据位为：

''1、0、1、0、1''

其中有3个1。

若采用偶校验，为使1的总数成为偶数：

''P1＝1''

P2检查：

''2、3、6、7、10、11''

不考虑P2本身，数据位为：

''1、0、1、1、1''

其中有4个1，已经是偶数，因此：

''P2＝0''

P4检查：

''4、5、6、7''

不考虑P4本身，数据位为：

''0、0、1''

其中有1个1，因此：

''P4＝1''

P8检查：

''8、9、10、11''

不考虑P8本身，数据位为：

''0、1、1''

其中有2个1，因此：

''P8＝0''

最终海明码为：

''10110010011''

假设码字：

''10110010011''

在传输过程中第6位由0变成1，接收结果为：

''10110110011''

接收端按照相同规则进行偶校验：

形成校验结果：

''P8 P4 P2 P1＝0110₂''

转换为十进制：

''0110₂＝6''

也可以直接将出错校验位编号相加：

''2＋4＝6''

因此可以确定：

''第6位发生错误''

将第6位取反：

''1→0''

即可恢复原码字。

各校验结果组成的二进制数称为：

Syndrome（伴随式或校验综合）

• Syndrome为0：未检测到错误；
• Syndrome不为0：其数值指出单比特错误的位置。

普通海明码的最小距离通常为3，因此：

• 可以纠正1位错误；
• 可以检测2位错误；
• 但普通译码器如果直接按单错处理，可能把双比特错误误判成另一位置的单比特错误。

增加一个全局奇偶校验位后，可构成：

SECDED（Single Error Correction, Double Error Detection，单错纠正、双错检测）

其能力为：

• 纠正所有单比特错误；
• 检测所有双比特错误；
• 不能纠正双比特错误。

Cyclic Code（循环码）是一类具有循环性质的线性分组码。

如果一个码字是合法码字，那么将其循环左移或循环右移任意位后，得到的码字仍然是合法码字。

例如，若：

''a_(n-1) a_(n-2) … a₁ a₀''

是合法码字，则其循环移位结果也是合法码字：

''a_(n-2) a_(n-3) … a₀ a_(n-1)''

循环码便于使用移位寄存器和异或门实现。

CRC（Cyclic Redundancy Check，循环冗余校验）是一种基于循环码和模2多项式除法的检错方法。

CRC的主要特点：

• 检错能力强；
• 特别适合检测突发错误；
• 数学基础严谨；
• 容易使用硬件实现；
• 广泛应用于局域网和数据链路协议；
• 通常只负责检错，不直接纠错。

发送端：

1. 选择生成多项式；
2. 在原始数据后补0；
3. 执行模2除法；
4. 取得余数作为CRC校验码；
5. 将原始数据与CRC余数组成发送码字。

接收端：

1. 用相同生成多项式除接收到的完整码字；
2. 如果余数为0，则未检测到错误；
3. 如果余数不为0，则判定传输出现错误。

原始数据D
    ↓
末尾补r个0
    ↓
除以生成多项式G
    ↓
得到r位余数R
    ↓
原始数据＋余数
    ↓
发送

CRC使用：

Modulo-2 Arithmetic（模2运算）

其特点：

• 加法等同于异或；
• 减法也等同于异或；
• 不产生进位；
• 不发生借位。

因此：

''1＋1＝0''

''1－1＝0''

''0－1＝1''

在CRC运算中，加法和减法均可使用XOR实现。

多项式乘以 x，相当于二进制码左移一位。

多项式乘以 x^r，相当于二进制码末尾补 r 个0。

一个二进制码字可以表示为一个系数属于0或1的多项式。

例如：

''00101011''

从最高非零位开始对应：

''x⁵＋x³＋x＋1''

因为：

因此：

''00101011 ↔ x⁵＋x³＋x＋1''

CRC使用的除数称为：

Generator Polynomial（生成多项式）

通常记作：

''G(x)''

如果生成多项式最高次数为 r，则：

• CRC校验码长度为 r 位；
• 生成多项式的二进制表示长度为 r＋1 位。

设：

• 数据多项式为 D(x)；
• 生成多项式为 G(x)；
• 生成多项式次数为 r；
• 商多项式为 Q(x)；
• 余数多项式为 R(x)。

对数据多项式补 r 个0，相当于：

''x^rD(x)''

执行模2除法：

''x^rD(x)＝Q(x)G(x)＋R(x)''

其中：

''deg R(x)<r''

实际发送的码字为：

''F(x)＝x^rD(x)＋R(x)''

由于模2运算中的加法和减法相同，所以：

''F(x)''

能够被：

''G(x)''

整除。

接收端计算：

''F(x)÷G(x)''

正确情况下余数应为0。

假设：

• 原始数据为 M；
• 生成多项式的二进制码为 P；
• P的最高次数为 r。

计算步骤：

1. 在原始数据后补 r 个0；
2. 使用生成多项式对应的二进制数进行模2长除；
3. 模2减法使用异或，不借位；
4. 得到长度不超过 r 位的余数；
5. 不足 r 位时在左侧补0；
6. 用余数替换原来补入的 r 个0；
7. 得到最终发送码字。

表达式为：

''发送码字＝原始数据＋CRC余数''

教材示例使用：

''D＝00101011''

对应数据多项式：

''D(x)＝x⁵＋x³＋x＋1''

生成多项式采用CRC-CCITT：

''G(x)＝x¹⁶＋x¹²＋x⁵＋1''

生成多项式二进制形式为：

''1 0001 0000 0010 0001''

十六进制形式通常简写为：

''1021H''

因为生成多项式次数为16，所以在原始数据后补16个0：

''00101011 0000000000000000''

进行模2长除后，教材得到余数：

''9509H''

因此，16位CRC校验和为：

''9509H''

其中：

• H表示Hexadecimal，即十六进制；
• 9509H的二进制形式为 1001010100001001。

最终发送的数据形式为：

''00101011 1001010100001001''

CRC可以使用以下电路实现：

• 移位寄存器；
• 异或门；
• 反馈回路。

使用：

LFSR（Linear Feedback Shift Register，线性反馈移位寄存器）

实现CRC时：

1. 先将寄存器清零；
2. 数据逐位输入移位寄存器；
3. 移出的位通过反馈线路参与异或；
4. 数据全部输入后，再输入与校验位数量相同个数的0；
5. 最终寄存器内容就是CRC余数。

生成多项式中系数为1的项，决定反馈异或连接的位置。

CRC-CCITT的生成多项式为：

''G(x)＝x¹⁶＋x¹²＋x⁵＋1''

因此其硬件反馈路径与：

• 第16次项；
• 第12次项；
• 第5次项；
• 常数项；

相对应。

设正确发送码字为：

''F(x)''

传输过程中产生的错误多项式为：

''E(x)''

接收到的码字为：

''H(x)＝F(x)＋E(x)''

因为正确码字 F(x) 能被 G(x) 整除：

• 如果 H(x)不能被G(x)整除，说明检测到错误；
• 如果 H(x)能被G(x)整除，则校验余数为0。

需要注意：

如果错误多项式 E(x) 恰好也能被 G(x) 整除，则：

''H(x)''

仍能被 G(x) 整除，此时错误无法被CRC检测。

因此，CRC不能检测所有理论上可能的错误，但合适的生成多项式可以使漏检概率非常低。

CRC检错能力取决于生成多项式 G(x)。

如果 G(x)至少包含两个非零项，即不是单项式，则可以检测所有单比特错误。

教材表述为：

如果生成多项式的项数大于1，可以检测所有单比特错误。

如果 G(x)含有因子：

''x＋1''

则能够检测所有奇数个位发生的错误。

如果CRC校验位长度为 r，则可以检测所有长度：

''≤r''

的突发错误。

对于长度为 r＋1 的突发错误，绝大多数也能够被检测。

更长的突发错误也具有较高的检出概率。

CRC-CCITT（Consultative Committee for International Telegraph and Telephone CRC，国际电报电话咨询委员会循环冗余校验）

''G(x)＝x¹⁶＋x¹²＋x⁵＋1''

常见十六进制表示：

''1021H''

''G(x)＝x¹⁶＋x¹⁵＋x²＋1''

''G(x)＝x¹²＋x¹¹＋x³＋x²＋x＋1''

''G(x)＝x³²＋x²⁶＋x²³＋x²²＋x¹⁶＋x¹²＋x¹¹＋x¹⁰＋x⁸＋x⁷＋x⁵＋x⁴＋x²＋x＋1''

CRC-32广泛应用于局域网及其他计算机网络。

必须掌握：

• 热噪声通常产生随机错误。
• 冲击噪声通常产生突发错误。
• 检错只能发现错误，纠错可以确定并恢复错误。
• 海明距离是两个等长码字对应位置不同的位数。
• 海明重量是码字中二进制1的数量。
• 检测 s 位错误要求 d_min≥s＋1。
• 纠正 t 位错误要求 d_min≥2t＋1。
• 单比特纠错海明码满足 2^k≥m＋k＋1。
• 海明码校验位放在1、2、4、8等位置。
• 一个数据位参加哪些校验，由其位置编号的二进制形式决定。
• 校验综合的二进制数直接指出单比特错误位置。
• CRC是Cyclic Redundancy Check的缩写。
• CRC使用模2除法，加法和减法均为异或。
• 生成多项式为 r 次时，CRC余数为 r 位。
• 发送端用余数替换数据后补的 r 个0。
• 接收端使用相同生成多项式进行除法校验。
• 接收余数为0表示未检测到错误，而不是绝对保证没有错误。
• r位CRC可以检测所有长度不超过r的突发错误。
• CRC-32广泛应用于局域网。

• 能检测1位错误不等于能纠正1位错误。
• 最小海明距离为2时只能保证检出1位错误，不能纠正。
• 纠正1位错误至少要求最小海明距离为3。
• 海明距离不是码字中1的数量；后者是海明重量。
• 海明码公式中的校验状态要包含“无错误”状态。
• 校验位数量应取满足公式的最小整数。
• 海明码校验位编号是1、2、4、8，不是第1、2、3、4位连续放置。
• CRC生成多项式的次数等于校验位数量。
• r次生成多项式的二进制形式有r＋1位。
• CRC模2减法不借位，本质上是异或。
• CRC余数不足规定长度时，应在左侧补0。
• CRC校验余数为0只表示没有检测到错误。
• CRC通常用于检错，不能直接指出错误位的位置。
• 生成多项式必须由通信双方事先约定。
• 多项式二进制表示中的最高位和最低位不能随意省略。

已知数据位 m：

1. 从 k＝1开始尝试；
2. 计算 2^k；
3. 计算 m＋k＋1；
4. 找到第一个满足 2^k≥m＋k＋1 的 k。

1. 按原校验规则重新计算各校验组；
2. 正确记为0，错误记为1；
3. 按照 P8、P4、P2、P1 的顺序组合；
4. 将所得二进制数转换为十进制；
5. 十进制数就是错误位置；
6. 将该位置取反完成单比特纠错。

1. 确定生成多项式的最高次数 r；
2. 在数据后补 r 个0；
3. 使用生成多项式执行模2长除；
4. 每次减法使用异或；
5. 得到 r 位余数；
6. 将余数附加到原数据后形成发送码字。

1. 用相同生成多项式除完整接收码字；
2. 余数非0：检测到错误；
3. 余数为0：未检测到错误。

差错控制
│
├─ 差错原因
│  ├─ 热噪声 → 随机错误
│  ├─ 冲击噪声 → 突发错误
│  ├─ 信号失真
│  └─ 串扰
│
├─ 控制策略
│  ├─ 检错
│  │  └─ ARQ请求重传
│  └─ 纠错
│     └─ FEC直接恢复
│
├─ 海明码
│  ├─ 海明距离
│  ├─ d_min决定检错纠错能力
│  ├─ 2^k≥m＋k＋1
│  ├─ 校验位位于1、2、4、8
│  └─ Syndrome指出错误位置
│
└─ CRC
   ├─ 循环码
   ├─ 模2多项式除法
   ├─ 生成多项式G(x)
   ├─ 余数作为校验码
   ├─ 接收端重新计算余数
   └─ 擅长检测突发错误

• 多路复用技术
• 扩频技术
• 局域网
• 返回第1章首页

软考 网络规划设计师 计算机网络 数据通信 差错控制 海明码 海明距离 CRC 循环冗余校验 模2运算 检错 纠错 ARQ FEC