差错检测和纠正
比特级差错检测和纠正
- 对从一个节点发送到另一个物理上邻接节点的链路层帧，提供比特错误的检测和纠正；
- 发送方对数据比特序列D，附加检测和纠正比特序列EDC；
- 接收方根据接收的数据比特序列D'和检测和纠正比特序列EDC'判断并纠正比特错误；
- 即使采用差错检测技术，仍旧可能存在未检出比特差错；
前向纠错(Forward Error Correction,FEC)
- 接收方检测和纠正差错的能力；
奇偶校验
- 对d比特的数据序列D，附加1位校验比特；
-
偶校验方案
发送方选择校验位的值使得d+1位比特序列中1的个数为偶数；
接收方检测d+1位比特序列中的1个数是否为偶数，非偶数则认为出错； -
奇校验方案
发送方选择校验位的值使得d+1位比特序列中1的个数为奇数；
接收方检测d+1位比特序列中的1个数是否为奇数，非奇数则认为出错；
- 奇偶校验可检出所有奇数个比特差错的情况；
- 若单个比特差错的概率低，且各个比特的差错事件独立，则奇偶校验是可接受的；
- 事实上，差错经常以突发的方式聚集，即各个比特的差错事件是不独立的；
二维奇偶校验
- 将d位数据序列划分为i行j列矩阵，对每行每列计算奇偶校验值，共i+j+1个奇偶校验比特；
- 对单比特差错，二维奇偶校验可定位出错的行列并纠正之；
事实上，发生在不相关行列上的多个单比特差错也可纠正； - 二维奇偶校验可以检测同一分组中两个比特差错的任意组合；
检验和技术(checksum)
- 将d比特的数据序列视为多个k比特整数构成的序列
- 基本方法是将序列中的多个k比特整数相加，并用总和作为差错检验比特；
- 常用于运输层
因特网检验和
- 将数据序列视为16比特的整数序列并求和，将和的反码作为因特网检验和；
- 接收方将整个数据序列（原数据和检验和）视为16比特整数序列并求和取反码，若结果全1则认为无差错；
- TCP和UDP中，对所有字段（分组头和分组载荷）计算检验和
XTP协议对首部和整个分组（分组头和分组载荷）分别计算检验和
检验和技术特点
- 检验和的分组开销小，处理速度快
差错保护能力相对弱（相对CRC弱） - 运输层差错检验用软件实现，故偏好检验和这样简单且快速的差错检测方案；
循环冗余检测(Cyclic Redundancy Check,CRC)
- 常用于链路层
- 也称多项式编码，将发送的比特串视为系数为0，1的多项式；
- 收发双方协商r+1比特模式，称为生成多项式G；
- 对d比特数据序列D，发送方选择r比特附加数据R，得到d+r比特模式，且该d+r位模式在模2算术下能被G整除；
- 接收方用G除接收到的d+r位序列，若余数为0则认为数据无误；
CRC计算
- 采用模2算术，加法不进位，减法不借位，加减等同于亦或；
乘除同常规的二进制算法，可用移位实现； - 余数R的计算：
- 生成多项式G由相关标准定义，包括8，12，16，32位的G；
链路层协议往往采用CRC-32，使用32位的G
CRC特点
- 能检测小于r+1位的比特差错；
- 适当假设下，以概率
检测到大于r+1位的差错；
- 能检测任何奇数个比特差错；
