差错控制： 通信过程中
- 发现错误
- 纠正错误，
把控制错误率的技术和方法。
数据传输中发生的码元差错，都是由噪声引起的。
噪声分为两大类：
- 信道固有的、持续存在的随机热噪声
热噪声引起的差错称为“随机错”。
随即错的错误码元往往是单个出现的，不连续。
通常把信道的信噪比设计得很大，来减少随机错，因此随机错占比很少。
- 来自外界的、短暂突发的冲击噪声
冲击噪声引起的差错称为“突发错”。
突发错的错误码元通常是连续出现，因为即使持续时间很短的冲击噪声也会使连续多个码元发生错误。
冲击噪声的幅度可能很大，就无法通过提高信噪比来抑制突发错。
突发长度：
突发错中，错误码元的数量（长度）。
突发错在传输差错中占比很高。
4.2.1 差错检测
差错控制的首要任务：差错检测。
差错检测包含了两个方面：
差错控制编码（发方）：
发送前，数据位+冗余位，构成“码字”。差错校验（收方） 检查数据位和冗余位的关系，从而检测错误。
4.2.2 差错控制方法
利用差错控制编码来进行差错控制的方法：
1.自动请求重发，ARQ，Automatic Repeat reQuest
收方检测到差错，就通知发方重发，直到收到正确的码字为止。
优点：
- 码字的冗余位更少
- 检错设备较简单
缺点：
- 信道必须是双向的。（收方才能通知发方）
- 发方必须有重发表
2.前向纠错，Forward Error Correction, FEC
收方不仅能发现错误，还能确定是错误位的位置，进行纠正。
优点：
- 不要求双向信道，
- 发方也不需要重发表。
- 实时性高（不需要重发）
缺点：
- 纠错码比检错码的冗余位更多
- 纠错设备比检错设备复杂。
根据ARQ和FEC，差错控制编码也分为了：
- 检错码
- 纠错码
ARQ差错控制方式是主流，某些场合也会混合使用ARQ和FEC方式。
即，如果码字中的错误位数量在纠正能力范围内，则使用FEC进行纠正，否则使用ARQ请求重发。
编码效率：码字中信息位的比例。
设，信息位\(k\)位，编码时附加冗余位\(r\)位，码字长度为\(n=k+r\)位，编码效率
\(R = k / (k+r) = k/n\)
编码效率R越大，码字传送信息的效率就越高。
4.2.3 奇偶校验码和循环冗余码
1. 奇偶校验码
奇偶校验码：
增加冗余位，使码字中保持奇数或偶数个1的编码方法。
奇偶校验码是一种检错码。
又可分为：
- 垂直奇偶校验码
- 水平奇偶校验码
- 水平垂直奇偶校验码
垂直奇偶校验（纵向奇偶校验）
信道串行发送若干个码元，表示了 n 个二进制位，每 p 位划分为一个段，共分为 q 段，pq矩阵组成了一个位的数据块。
在每一段后添加一个冗余位，称为垂直奇偶校验。
段的长度通常为一个字符的长度，这种称为字符奇偶校验。
偶校验的编码和检测公式：（+为模2运算）
\[ r_{i} = I_{1i} + I_{2i} + \cdots + I_{pi} \]
奇校验的编码和检测公式：（+ 为模2运算）
\[ r_{i} = I_{1i} + I_{2i} + \cdots + I_{pi} + 1 \]
垂直奇偶校验只能检测出奇数个二进制位错误，不能检测偶数个二进制位错误。
突发错误中，奇数位错和偶数位错的发生几率相等，因此垂直奇偶校验的漏检率是 1/2。
垂直奇偶校验还有个优势：发方可以边发边附加冗余位，收方可以边收边校验边去除冗余位。
编码效率：
\(R= p/(p+1)\)
水平奇偶校验（横向奇偶校验）
同样是 pq 数据块，通过在水平方向（q段）给二进制位附加 1 个冗余位，称为水平奇偶校验。
水平奇偶校验的漏检率比垂直奇偶校验低，它可以检测出两种错误：
1.水平方向上（即各段同一位上），奇数个二进制位错误 这点和垂直奇偶校验是一样的。
2.数据块中一个突发长度 \(\le p\) 的突发错。
如果存在突发长度 \(\le p\) 的突发错，必然分布在1个或相邻的2个段上，从水平方向来看，这些错误位分布在连续的行上，且不会重叠（包括跨2个段的情况，首尾不会重叠）。
水平奇偶校验码，可以检测出这不重叠的 p 行错误。
但仅限于一个突发错，如果有多个，则可能在水平方向出现偶数个错误位，造成漏检。
水平奇偶校验编码，要求发收双方都有数据缓冲区，在整个数据块发完和收完后才能进行冗余位的附加、检测、去除操作，比垂直奇偶校验码复杂。
编码效率：
\(R = q/(q+1)\)
水平垂直奇偶校验（纵横奇偶校验）
同时进行水平奇偶校验和垂直奇偶校验，就构成了水平垂直奇偶校验。
同样是 pq 数据块。水平方向上，在 q 列后增加冗余位，在 p 行上增加冗余位。
编码和检测的计算公式：
假设水平方向和垂直方向都采用偶校验。
水平方向
\[ (i是行号，i=1,2,\cdots,p) \\ \\ r_{i,q+1} = I_{i1} + I_{i2} + \cdots + I_{iq} \]
垂直方向
\[ (j是列号， j = 1,2,\cdots,q) \\ \\ r_{p+1,j} = I_{1j} + I_{2j} + \cdots + I_{pj} \]
交叉点：
\[ r_{p+1,q+1} = r_{1,q+1} + r_{2,q+1} + \cdots + r_{p,q+1} + r_{p+1,1}+ r_{p+1,2}+ \cdots + r_{p+1,q} \]
水平垂直奇偶校验能够检测出：
- 3位或3位以下的错误，因为此时至少在某一行或某一列上有一位错
- 奇数位错：这个可以理解，奇偶校验就是可以检测奇数位错
- 突发长度 \(\leq p+1\) 的突发错：垂直/水平奇偶校验，长度\(\leq p\)的突发错可以被检测出来，而在纵横奇偶校验中，可检测的突发长度达到了\(p+1\)，p+1的突发错必然跨段，在某一行中形成偶数个错。又因为跨段的最后一个错，可以被第2个段的列检测，所以p+1是允许的。但如果p+2，则第2列出现偶数错，就会漏检，同时第一列也可能无法被检测出来（除非第一列是奇数错）。
- 部分偶数位错
误码率： 经测量，这种方式的误码率可降至原误码率的百分之一到万分之一。
纵横奇偶校验不仅是检错码，某型情况下也可以作为纠错码使用。
比如当整个数据块中只有一个位错误时，可以通过行检错和列检错，确定出行列坐标。
编码效率： \(R = pq / ((p+1)(q+1))\)
纵横奇偶校验，要求发收双方都有数据缓冲区，在整个数据块发完和收完后才能进行冗余位的附加、检测、去除操作。
2. 循环校验码
奇偶校验码的漏检率太高，所以通常使用另一种漏检率低、便于实现的循环冗余码CRC（cyclic Redundancy Code)。
循环校验码是一种检错码。
前提条件：
- 任何一个 N 位二进制数，都唯一对应一个 “最高位是 (N-1) 次、系数只可能是0和1的”多项式。 比如： 1010111 对应 \(x^6+x^4+x^2+x+1\)，101111 对应 \(x^5+x^3+x^2+x+1\)
具体到校验码中，
\(k\)位信息位对应了\((k-1)\)次多项式 \(K(X)\)，
\(r\)位冗余位对应了 \((r-1)\)次多项式 \(R(X)\)
\(n=(k+r)\)位码字则对应了 \((n-1)\)(即\((k+r-1)\) )次多项式 \(T(X)\)
根据码字的定义，可得： \(T(X) = X^r \cdot K(X) + R(X)\)
发方如何生成码字
问题可以简化为：
已知信息位 \(K(X)\)，如何求冗余位 \(R(X)\) 呢？
需要先了解一下”生成多项式“G(X)。
生成多项式是一个特定的多项式，它的最高项系数恒为1，次数为 \(r\)次，收发双方都事先约定了生成多项式。 发方计算 \(X^r \cdot K(X) / G(X)\)，余数即冗余位 \(R(X)\)。
发方码字 \(T_{send}(X) = K(X) + R(X)\)
需要说明的是：
- 除法中的减法是模2减：即异或减，不借位。因此除法也称为模2除
- 模2除中计算余数时“不计算最高位“：被减数和减数的最高位不做减法，不计入余数。
- 生成多项式 G(X)， 信息位 K(X)，冗余位 R(X) 三者缺一不可。
- 生成多项式一旦变化，冗余位就立刻变化。
收方如何校验码字
收方校验原理：
计算\(T_{rec}(X)/G(X)\) ，若能整除说明传输无差错，若不能整除证明传输有差错。
证明如下：
因为 \(X^r \cdot K(X) = G(X) \cdot Q(X)+ R(X)\) ， 其中\(Q(X)\) 为商。
又，据模2运算规则可知： \(R(X) + R(X) = 0\) 。
因此：
\(X^r \cdot K(X) + R(X) = G(X) \cdot Q(X)\)
\((X^r+ R(X))/ G(X) = Q(X)\)
最终得到：
\(T(X)/G(X) = Q(X)\)
CRC码也会发生漏检
当差错模式也能被生成多项式整除时就会漏检。
分析如下：
首先需要知道：
- 发方码字 + 差错模式 = 收方码字
- 差错模式 = 收方码字 / 生成多项式 说得的余数
- 差错模式记为E(X)
推理如下： 发方码字 \(T_{send}(X)=1011001,1010\)，信息位 \(K(X)=1011001\)，冗余位 \(R(X)=1010\)，传输受到干扰后，收方码字\(T_{rec}(X) = 1011001 ,1100\)。
收方校验时无法整除，会得到差错模式\(E(X)=0110\)。
此时可以发现，1011001，1010 + 0110 = 1011001，1100，
证明： \(T_{send}(X) + E(X) = T_{rec}(X)\)
收方验证码字时，
\[ T_{rec}(X) / G(X) = (T(X) + E(X))/G(X) = T(X)/G(X) + E(X)/G(X) \]
如果 \(E(X) / G(X) =0\)， 则会发生漏检。
为了降低漏检率，生成多项式\(G(X)\)并不是随意选取的，而是需要数学运算得到，常用的CRC码有：
- CRC12
- CRC16(IBM公司)
- CRC16(ITU)
- CRC32
理论证明，CRC码可以检测出下列错误：
1. 所有奇数位错 2. 所有双比特的错 3. 所有小于等于校验位长度的突发错
可以检测哪些错误这部分比较复杂，暂时不管。