第04章-差错控制与校验.讲述.ppt

第4章差错控制与校验,4.1差错控制技术,信号在物理信道中进行传输存在差错。差错产生的原因噪声。信号在传输过程中受到的噪声干扰有两种：信道固有的白噪声，引起的差错称为随机差错，引起的某位码元的差错是孤立的，与前后码元没有关系，白噪声所引起的差错可以通过提高信道的信噪比而减小。外界因素引起的冲击噪声，外界因素包括太阳黑子、电子风暴、电源抖动或电磁干扰等。冲击噪声呈突发状，它所引起的差错称为突发差错。冲击噪声幅度可能相当大，不能靠提高信号的幅度来避免冲击噪声造成的差错。冲击噪声虽然持续时间较短，但在一定的数据速率下，仍然会影响到一串码元。,第4章差错控制与校验,为减少传输差错，提高传输质量，可以采取以下措施：改善通信线路的质量，降低误码率；采用差错控制技术检测错误，纠正错误，把差错限制在尽可能小的允许范围内。最常用的是差错控制编码。在发送数据之前，先按照某种规则在数据位之外附加上一定的冗余位后再发送，称为差错控制编码过程。接收端收到编码后，利用相同的规则对信息位和冗余位之间的关系进行检测，判断传输过程中是否发生差错。对于发生的错误有两种处理方法：检错法和纠错法。检错法是检测传输信息的改变，当检测到错误时，将该信息丢弃，同时通知发送者，重发该信息。纠错法是当检测到错误时，接收方纠正错误而无须重发，发送者并不知道该信息在传送中出现差错了。相应的差错控制技术有两种：反馈重发技术和前向纠错技术。,第4章差错控制与校验,1.反馈重发技术首先在发送端将信息进行检错编码，然后将检错码经信道发送至接收端。接收端译码后判断是否有错，若有错，要求发送端重传，直至传送正确；若无错，则发送无错确认信号给发送端。2.前向纠错技术首先在发送端将信息进行纠错编码，然后将纠错码经信道发送至接收端，接收端译码后若发现错误则自动纠正错误，而不需要重传信息，但是该方法比较复杂，实现比较困难。,第4章差错控制与校验,4.2.1奇偶校验奇偶校验(ParityChecking)是最简单的校验方式。奇偶校验是将数据分组，每一组数据后附加一个校验位，使得该组数据(包括校验位)中1的个数为偶数(偶校验)或奇数(奇校验)。奇偶校验分为3种：垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验。水平奇偶校验是以一组字符中对应位作为校验单元进行奇偶校验。奇偶校验位与数据一起发送到接收方，接收方检测奇偶校验位，对于偶校验，若接收方发现1的个数为奇数，则说明发生了错误。若在传输中有两个比特位受干扰被改变，如两个0变成了两个1，那么校验结果仍然和原来一样，实际是发生的错误没有检测出来。垂直奇偶校验是对一组字符各对应位（垂直方向）加校验位构成校验单元，检错效果高于水平奇偶校验。,4.2检错码,第4章差错控制与校验,水平垂直奇偶校验是将前面两种校验方式相结合而成的。例如每7个字符作为一组，其校验方式见教材P37表4.1(以偶校验为例)。用这种校验方式可以检测出更多的差错，但是只有在所有列都发送完毕后，错误才能够完全检测出来，而且接收方可能不知道哪个列是不正确，只有重发所有列，对于单个错误，会给通信设备增加很大负担。网络通信中常用的循环冗余校验是一种高效、可靠的方法。,第4章差错控制与校验,4.2.2循环冗余校验码循环冗余校验码(CRC，CyclicRedundancyCode)是采用多项式的编码方式，这种方法把要发送的数据看成是一个多项式的系数，数据为bn-1bn-2bb(其中为0或1)，则其对应的多项式为bn-1Xn-1+bn-2Xn-2+bX+b例如：数据“10010101”可以写为多项式X+X+X+1。循环冗余校验方法的原理如下：(1)设要发送的数据对应的多项式为P(x)。(2)发送方和接收方约定一个生成多项式G(x)，设该生成多项式的最高次幂为r。(3)在数据块的末尾添加r个0，则其相对应的多项式为M(x)=XrP(x)。（左移r位）,第4章差错控制与校验,(4)用M(x)除以G(x)，获得商Q(x)和余式R(x)，则M(x)=Q(x)G(x)+R(x)。(5)令T(x)=M(x)+R(x)，采用模2运算，T(x)所对应的数据是在原数据块的末尾加上余式所对应的数据得到的。(6)发送T(x)所对应的数据。(7)设接收端接收到的数据对应的多项式为T(x)，将T(x)除以G(x)，若余式为0，则认为没有错误，否则认为有错。即若T(x)=T(x)，则T(x)/G(x)=(Q(x)G(x)+R(x)+R(x)/G(x)=(Q(x)G(x)/G(x)=Q(x)余式为0。若T(x)T(x)，余式不为0。,第4章差错控制与校验,循环冗余校验的过程的举例见教材P38P39。常用的标准生成多项式有以下几种：CRC-ITU:G(x)=x16+x12+x+1CRC-12:G(x)=x12+x11+x+x+x+1CRC-16:G(x)=x16+x15+x+1CRC-32:G(x)=x32+x26+x23+x22+x16+x12+x11+x10+x+x+x+x+x+x+1,第4章差错控制与校验,纠错码与检错码相比功能更强。检错码只能检测到错误，而纠错码不仅能检测出错误，而且还可以检测出哪位发生了错误并进行纠正。纠错码有很多种，如：海明码，卷积码及BCH码等。下面只介绍海明码。4.3.1海明码的组成海明码也是由数据位及校验位组合而成的，但它的数据位和校验位是交叉排列的。设要发送的数据为mmmmmmmm，则海明码为ABmCmmmDmmmm，其中A、B、C、D为校验位。各位所对应的编号分别为1到12，例如，m的编号为3，D的编号为8，校验位所对应的编号均为2的幂次。将每个数据位的编号用校验位编号的和来表示，即3=2+15=4+16=4+27=4+2+19=8+110=8+211=8+2+112=8+4上面各式决定了每个数据位由哪个校验位进行校验。见表4.2。,4.3纠错码,第4章差错控制与校验,表4.2数据位与校验位编号,可以得出：A是编号为3、5、7、9、11的数据位(即m0、m1、m3、m4、m6)的校验位。B是编号为3、6、7、10、11的数据位(即m0、m2、m3、m5、m6)的校验位。C是编号为5、6、7、12的数据位(即m1、m2、m3、m7)的校验位。D是编号为9、10、11、12的数据位(即m4、m5、m6、m7)的校验位。在这里每个校验位的值都是根据奇校验或者偶校验规则求出的。,第4章差错控制与校验,4.3.2纠错原理在接收方有一个出错计数器，首先将其置0，接收到数据后对每个校验位及其所对应的数据位进行校验，如果出错就将该校验位的编码加入到出错计数器，最后根据出错计数器的值就可以确定是哪位出错，然后将该位数据取反即可。例如：要发送的数据为“10101100”，海明码为“AB1C010D1100”，按偶校验规则进行校验，可得A=0，B=1，C=1，D=0，即“011101001100”，将其发送到接收端，若因某种原因第5位数据由“0”变为“1”，则在接收端对第一个校验位A进行检查时可以发现有问题，将该校验位的编码“1”加到出错计数器中，然后对第二个校验位进行检查，没