计算机通信技术第3.3章节常用差错控制编码方法.pptVIP

3.3 常用差错控制编码方法;;3.3.1 奇偶校验编码 ;公式表示：设码组长度为n，表示为（an-1,an-2……,a1,c0）其中前n-1位为信息位，第n位c0为监督位 ①奇校验：an-1⊕an-2⊕……⊕a1⊕c0=1即c0= an-1⊕an-2⊕……⊕a1⊕1 ②偶校验：an-1⊕an-2⊕……⊕a1⊕c0=0 即c0= an-1⊕an-2⊕……⊕a1;特点： 无论信息位为多少位，监督位只有一位。 只能检测信息码组中奇数个错误，对偶数个错误无能为力；;实例;水平奇偶校验 ;实例;特点 ：发送端是按列发送码元，而不是按码组（行）发送码元，因此可把本来可能集中发生在一码组中的突发错误分散到方阵中的各个码组，同时又作为整个方阵的行监督； 可以发现某一行上所有奇数个错误及长度不大于方阵行数的突发错误。 ;3.3.2 方阵校验码; X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X ;实例 ;特点： 可以检测出某行某列上的奇数个错误和长度不大于行（列）数的突发错误。 可以检测出某行或某列上偶数个错误 不能纠正差错数正好是4的倍数且位置在行列矩阵/子矩阵的4个顶点上的差错 ;失效！！！ ;3.3.3 恒比码(定比码) ;3.3.4 正反码_能简单纠错的编码;2.解码方法： (1)将接收到信息码与监督码按相应的码位模2加（异或），得到一个新的5位码组。 (2)根据接收到的信息码中“1”的个数： if“1”的个数为奇数，则取新5位码组为校验码组 if“1”的个数为偶数，则取新5位码组的反码为校验码组;正反码判决表;实例：;（1） 编码：11010（信息码）11010（监督码）→11010 11010（正反码） （2） 解码： ①接收端11010 11010 ②接收端10010 11010 ③接收端11010 01010 ④接收端10000 11010 判断： ;;;;; 3.3.5 循环冗余校验编码（CRC） ;CRC校验基本思想 ;奇偶校验对一个字符校验一次，适合异步通讯；而CRC对一个数据块（frame）校验一次，适合同步通讯。在串行同步通信中，几乎都使用这种校验方法。如磁盘信息的读/写等。;CRC码生成和校验基本分为三步： 第一步：在数据单元(k位）的末尾加上r个0。r是一个比预定除数的比特位数(r十1)少1的数。 第二步：采用二进制除法将新的加长的???据单元（k+r位)除以除数。由此除法产生的余数就是循环冗余码校验码。;第三步：用从第二步得到的r个比特的CRC码替换数据单元末尾附加的r个0。如果余数位数小于r，最左的缺省位数为0。如果除法过程根本未产生余数（也就是说，原始的数据单元本身就可以被除数整除）那么以r个0作为CRC码替换余数所在的位置。产生的比特模式正好能被除数整除。 ;CRC码校验： 到达接收方的数据单元首先到达的是数据，然后是CRC校验码。接收方将整个数据串当作一个整体去除以用来产生循环冗余校验余数的同一个除数。 如果数据串无差错地到达接收方，循环冗余校验器将产生余数0。因此数据单元将通过检验。如果在传输中数据单元被改变，除法将产生非零余数，因此数据单元将通不过检验。;循环冗余码生成器采用模2除法。下图显示了这一过程。 CRC校验器的功能完全像发生器一样，当收到附加了CRC码的数据后，做同样的模2 除法。如果余数是全0，则将CRC码丢弃，接受数据。否则，丢弃收到的数据。 ;?;;CRC校验码的生成器和校验器; 任何一个二进制数序列可以和一个只含有0和1两个系数的代数多项式建立起一一对应的关系。因此，用来求CRC码的那个除数通常用多项式来表示。原因如下： 代数多项式很短 可以通过多项式来进行概念的数学证明。 ;多项式;多项式 二进制序列实例;码多项式运算法则: 二进制码多项式的加减运算为⊕模2加运算，即两个码多项式相加时，对应项系数进行模2加减。 乘除运算与普通多项式类似； 模2加减：即各位做不带进位、借位的按位加减。这种加减运算实际上就是逻辑上的异或运算。即加法和减法等价。;生成多项式G(x): 求CRC码时所用的“除数”所对应的多项式叫生成多项式。 在串行通信中通常使用下列三种生成多项式G（X）来产生CRC码。 CRC-16：G(x)=X16+X15+X2+1，美国二进制同步系统中采用。 CRC-CCITT：G(x)=X16+X12+X5+1，CCITT推荐。 CRC-32：G(x)=X32+X26+X23+X22+ X16+X12+ X11+X10+X8+1X7+ X5