差错控制

差错控制的目的和任务：发现和纠正计算机通信错误以提高信息的传输质量。
主要涉及的问题：一是如何检测出错误；二是发现错误后，如何进行纠正。
1、差错的特性及差错控制方式
差错监测和控制技术：在计算机通信系统中产生差错以后，一定要采取措施来监测和纠正错误，将错误控制在允许的最小范围内。
1、差错的特性
传输中出现的错误种类：
随机错：由信道固有的、持续存在的随机热噪声引起的。
一般是孤立的；由它导致的错误通常较少。
突发错：通常是由外界特定的瞬间的冲击噪声引起。
常出现连续比特的错误，影响面较大；是传输中产生差错的主要原因。
突发长度：从突发错发生的第一个码元到连续有错的最后一个码元间的所有码元的个数。
突发错比随机错传输的效率较高；突发错的检错和纠错要比随机错困难。
2、误码率（又称比特差错率）：用来衡量通信线路传输信息的质量，记为Pe。 Pe = 发生差错的码元数 / 接收的总码元数
在数据通信中，不同业务、不同信道的误码率是不同的：
例如：中速的电话系统误码率一般在10-4—10-6之间；广域网的误码率一般在10-7—10-8之间；而局域网的误码率一般在10-9—10-11之间。
降低误码率的两种办法：
改善物理信道：降低通信线路自身的误码率，受经济上和技术上的限制难以得到理想的结果。
采取差错控制：核心的技术是编码。
差错控制编码：将发送之前在数据块中加入冗余信息的过程。
两种基本策略：
检错码：使编码只具有检错的功能，即接收方只能判断收到的数据块中是否有错，但有错时不能确切知道错误的位置，因而不能纠正错误 ；
纠错码：使编码具有一定的纠错功能。即接收方不仅能知道收到的数据块中是否有错，而且能知道错在什么地方，然后将出错的二进制位按位取反。
3、 差错控制方式
自动请求重发方式ARQ：采用检错码；需有双向信道来传送收方的反馈信息；在发方要有数据缓冲区来存放已发出的数据；实现简单、传输效率高，是数据通信中常用的差错控制方式。
前向纠错方式FEC：采用纠错码；不需要反向信道和数据缓冲区；由于纠错码使用更多的冗余位，故纠错设备比检错设备复杂。
2、常用的简单差错控制编码
1、 奇偶校验码——最基本、最常用、最简单的检错码
编码规则：在信源输出的信息码后面附加一个校验元，使得码组中“1”的个数是奇数或偶数；在接收端再检测“1”的个数，根据是否与发送端原则相符判断传送中是否出现错码。
若传送的信息有n_-1个码元C_n-1 C_n-2……C₂C₁，校验位为C₀，则： 奇校验方程为：C_n-1+C_n-2+……+C₂+C₁ +C₀=1； 偶校验方程为：C_n-1+C_n-2+……+C₂+C₁ +C₀=0。（其中+表示模2加运算）
特点：奇偶校验能查出传输中任意奇数个错，但不能发现偶数个错误。
适合：在信道干扰不严重和码长n不大的时，尤其适于检测随机偶发的错误。
2、 二维奇偶校验码
1）、垂直奇偶校验（又称为纵向奇偶校验、字符奇偶校验）
原理：把要发送的信息码元按定长m比特分为若干段，每段纵向排列，对每列的信息元进行奇偶校验，得到的校验元附在每列后面，传输时按列的次序传输 。

编码效率：R=m/(m+1)。
特点：能查出垂直列上的奇数位差错，不能查出偶数位差错；由于突发错出现奇数位错误码元与出现偶数位错误码元的概率各半，因此垂直奇偶校验只能查出50％突发性错误。
2）、水平奇偶校验（又称为横向奇偶校验）
原理：把要发送的信息码元按定长m比特分为若干段，然后每段纵向排列，共计n行，对每行的信息元进行奇偶校验，得到的校验元附在每行后面；传输时也按列的次序传输。
编码效率：R=n/(n+1)。

优点：检错能力强，不仅能检验出水平方向上每行的奇数位错，而且还能检测出突发长度≤m位的所有突发错。
缺点：发送方和接收方都必须设置缓冲区，且产生检验码、检查检验码的逻辑也比较复杂。
3）、 水平垂直奇偶校验
原理：是水平和垂直两个方向的奇偶校验的结合，又称纵横奇偶检验和方阵奇偶校验。
编码效率：R=mn/[(m+1)(n+1)]。

特点：可检测出所有3位或3位以下的错误、水平或垂直方向上的奇数个错误、突发长度＜m的突发性错误以及部分偶数位错误，即它可检测出除了互相补偿的偶数位错以外的所有差错；当差错位数为1位时能纠正差错。
3、循环冗余码(Cyclic Redundancy Code，CRC)
——又称为多项式码，是一种在计算机网络和数据通信中使用得最广泛的检错码。
1、循环冗余码(CRC)原理及运算规则
基本原理：给定一个k比特的帧或信息，发送装置产生一个n比特校验位，称为帧校验序列FCS，使得产生的这个由k+n比特组成的码字可被某个预定的整数相除，然后接受装置将收到的码字除以同样的数，当没有余数时，则认为没有错误。
基本运算规则：模2运算，即异或运算，加法不进位，减法不借位。

定义：T——待传输的k+n比特信息位，一般n<k;
M——k比特，T的前k比特，要传送的信息位；
R——n比特，T的后n比特，要传送的检验码；
P——n+1比特特征值，这是待除的数，即特征多项式。
求冗余码的方法：令M·2n除以P的余数为R。
证明：只需证明T是能被P整除的，则基本原理成立；
由定义可知，T = M·2n+R；
由于M·2n除以P的余数为R，则有 (M·2n)/P = Q+R/P (Q为商，R为余数)，
且有 T/P = (M·2n)/P+R/P = Q+R/P+R/P，
因为任何二进制数加上其本身的模2运算为0，则有 T/P=Q。
因此T是能被P整除的，即R可用作FCS。
推理：简单地将k比特信息M左移n个比特（即乘以2n），即M·2n，除以P得到的余数R即为帧校验序列FCS。
执行过程：在发送端由M和R构成传输信息T；在接收端，接收装置再将收到的T除以P，如无余数，即 T=T，则说明无误码，再将后n位FCS检验位去掉。
2、生成多项式 P(x)
形式：
CRC-12: P(x)=x¹²+x¹¹+x³+x²+x+1 CRC-16: P(x)=x¹⁶+x¹⁵+x²+1 CRC-CCITT: P(x)=x¹⁶+x¹²+x⁵+1 3、CRC码产生过程 ①将数据M变成多项式M(x)。例如，M为111001，则M(x)=x⁵+x⁴+x³+1； ②将M(x)左移n位，得到一个新的多项式xⁿ·M(x)； ③用模2除法，将xⁿ·M(x)除以P(x)得到余数R(x)，与②中的码xⁿ·M(x)和起来得到T(x)，即T(x)=xⁿ·M(x)+R(x)。 ④接收方收到T(x)后与P(x)相除，若余数为0，则表示无错码，同时去掉T(x)后n比特检验位。 4、例如：M为110，G(x)=x⁴+x³+x²+1, 求T(x)。 由题意得： G = 11101 M·2⁴ = 1100000 用1100000除以11101，商Q为101，余数R为1001，则R(x)= x³+1； 而又有M(x)·x⁴ = x⁶+x⁵，则T(x) = M(x)·x⁴+ R(x) = x⁶+x⁵+x³+1，相应的码为1101001。 5、 CRC码的特点 ①可以检验出所有单比特错误； ②可以检验出所有双比特错误（条件为P(x)具有三项因式）； ③可以检验出任何奇数个差错（条件为P(x)包含因式(x+1)）； ④可以检验出任何长度小于FCS长度的突发错误； ⑤大多数较大的突发错误。