计算机网络导论 数据链路层 LLC 检测与纠错 差错

差错控制分为 检测、纠正；

d汉明距离：两个码之间位不同的个数

检测

检测s个 dmin = s+1 s=dmin-1
纠错

纠正t个 dmin = 2t+1 t=(dmin-1)/2

编码C（n，k） n码字=k数据字+r冗余

线性块编码：任意两个有效编码异或得到的仍是有效编码
大部分都是线性块编码

简单奇偶校验：增加一位，使码字1个数为奇数（奇校验）/偶数（偶校验）
C（k+1，k） dmin=2 只能检验一位差错

二维奇偶校验：每行每列一个校验码 i+j+1（i行j列）
C（k+i+j+1，k）

汉明编码 dmin=3 检测2 纠错1
选择一个m>=3 r=m n=2^m-1 k=n-m

循环冗余校验CRC
除法为模二除法
除数r+1位，被除数 数据字补r个0，获得余数，余数加上被除数即为码字
若接收方将码字除除数，余数为0则无差错
多项式表示法

除数：
单个位差错：至少两项 x0=1
两个独立位差错：x^t+1 t~(0,n-1)
奇数个差错：因子x+1
突发性差错：L<=r 都会被检测

因特网校验和

1. 按16位分组
2. 相加
3. 最高进位下移
4. 取反码