数据通信原理第3章.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,信号在物理信道中传输时，线路本身电气特性造成的随机噪声、信号幅度的衰减、频率和相位的畸变以及各种外界因素等都会造成信号的失真。,信号失真会使传输过程中产生比特差错：,1,可能会变成,0,，而,0,也可能变成,1,。,在一段时间内，传输错误的比特占所传输比特总数的比率称为误码率,BER(Bit Error Rate),。,误码率与信噪比有很大的关系。,为了保证数据传输的可靠性，在计算机网络传输数据时，必须采用各种,差错控制技术。,第,3,章 差错控制,1,第,3,章 差错控制,3.1,差错控制基本概念,1.,概念,：,差错控制是在数据通信过程中发现或纠正差错并把差错限制在尽可能小的允许范围内的方法和技术。,2.,基本思路,：,发送端,：在被传送的信息码序列的基础上，按照一定的规则加入若干“监督码元”后进行传输，这些加入的码元与原来的信息码序列之间存在着某种确定的约束关系。该过程称为差错控制编码过程。,接收端,：检验信息码元与监督码元之间的既定的约束关系，如该关系遭到破坏，则在接收端可以发现传输中的错误，乃至纠正错误。该过程为检验过程。,用纠,(,检,),错来控制差错的方法来提高数据通信系统的可靠性是以牺牲有效性为代价换取的。,2,3.,差错分类,信号在传输中的差错除了外界因素外，都是由,噪声,引起的。,随机噪声：,包括热噪声、散弹噪声和传输媒介引起的噪声等；随机噪声导致传输中的随机差错；随机差错又称独立差错，它是指那些独立地、稀疏地和互不相关地发生的差错，也就是随机差错引起的某位码元的差错时孤立的，与前后码元没有关系。,脉冲噪声：,指突然发生的噪声，这种噪声包括雷电、电源开关等引起的瞬态电信号变化。它是产生差错的主要原因。脉冲噪声幅度大，持续时间短，但在一定的数据速率条件下，仍会影响到一串码元。脉冲噪声呈突发状，由其引起的错差称为突发差错。突发差错是指一串串，甚至是成片出现的差错，差错之间有相关性，差错出现是密集的。,第,3,章 差错控制,3,4.,差错控制方式,在数据通信系统中，差错控制方式一般可以分为,4,种类型，如图,3-1,所示。,图,3-1 4,种类型差错控制方式,第,3,章 差错控制,4,（,1,）检错重发,检错重发简称（,ARQ,：自动重发请求）。这种差错控制方式在发送端对数据序列进行分组编码（如数据帧），加入一定多余码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后按一定的规则进行有无差错的判决并把判决结果通过反向信道送回发送端，如有差错，发送端把前面发出的信息重新传送一次，直到接收端认为正确接收到信息为止。能够实现差错检测和差错恢复以及流量控制的功能。,处理传输差错的重发技术有,：差错检测技术；确认帧技术；否认帧技术；差错重发技术；超时重发技术。,在具体实现检错重发系统时,通常有,3,种形式,即停等,ARQ,、退后,N,帧,ARQ,和选择重发,ARQ,。,第,3,章 差错控制,Stop-and-Wait ARQ,基本思路：,停等,ARQ,是指发送端发送一帧数据并启动定时器，不能继续发送后续帧，而是等待接收方的确认帧或否认帧。接收端收到数据帧后经过检验如果没有发现差错，则向发送方返回一确认帧（,ACK,），再处理数据帧并交给上层，发送端收到,ACK,后认为该帧数据成功传输，取出下一帧再发送；如果接收方经过检验，发现有差错，则向发送端返回一否认帧（,NAK,），并丢弃出错帧，发送端 收到,NAK,则认为传输出差错，则取出缓冲区里原来的数据进行重发,。,Stop-and-Wait ARQ,分为四种情况讨论：,a.,数据在传输的过程中没有出现差错；,b.,数据在传输过程中出现差错；,c.,数据帧丢失情况；,d.,确认帧（否认帧）丢失的情况。,Stop-and-Wait ARQ,发,收,ACK0,正确,发,收,NAK0,错误,重发,发,收,重发,超时重发,正确,发,收,重发,正确,ACK0,超时重发,正确,重复帧,(1),(2),(3),(4),如何处理？,0,1,0,0,0,0,0,0,Stop-and-Wait ARQ,停等,ARQ,的特点：,a.,方法设计简单，容易实现；,b.,数据帧越短，占空比越大，信道利用率越低；数据越长，,占空比越小，信道利用率越高，但是出错的概率越大，会出现多,次重传，因此传输效率低。,发送端每发送一帧数据都要有一个等待时间，称为占空时间。占,空时间与传输一帧数据的全部时间的比值，称为占空比。,c.,停等,ARQ,是牺牲传输效率来获得通信的可靠性。,连续,ARQ,基本思路：,发送端连续地发送一系列的数据帧，而暂时不需要等待前面所发数据帧的确认便发送下一帧。连续,ARQ,把等待时间利用起来，传输效率大大提高。,传输信道是不可靠的，如果已经连续发送到链路上的数据帧中，某一帧数据发生了差错或丢失，在发送端发现已近出现差错之前，很多后续帧就会达到接收端，接收端应当丢弃出错数据帧，同时还必须保证发送顺序交给上层，因此，接收端对后续正确的数据帧处理方式决定了发送端的重发机制，可将,连续的,ARQ,分为退后,N,帧的,ARQ,和选择性重发,ARQ,。,Go-back-N Frame ARQ,0,1,2,3,1,2,3,4,5,发,6,W,T,=7,0,1,2,3,1,2,3,4,5,收,6,W,R,=1,丢弃,等待,1,号帧,交上层处理,(1),接收的数据帧通过差错检测发现帧错误,一般地，当差错检测发现第,I,帧错误，则接收方给出否认帧信息，并丢弃出错帧及后续帧。发送方退回到第,I,帧，重发第,I,帧及,I,帧的后续帧。,0,1,2,3,4,1,2,3,4,发,5,W,T,=7,0,1,2,3,4,1,2,3,4,收,5,W,R,=1,丢弃,等待,1,号帧,交上层处理,超时间隔,超时重发,(2),当传输的数据帧丢失,Go-back-N Frame ARQ,0,1,2,3,4,1,2,3,4,发,5,W,T,=7,0,1,2,3,4,1,2,3,4,收,5,W,R,=1,丢弃重复帧,交上层处理,超时间隔,超时重发,退后,N,帧,ARQ,的链路利用率是否一定比停等,ARQ,高？,(3),当接收方发出的确认帧丢失,Go-back-N Frame ARQ,Selective Reject,ARQ,0,1,2,3,1,4,5,6,7,发,0,W,T,1,0,1,2,3,1,4,5,6,7,收,0,W,R,1,暂存缓存,等待,1,号帧,一起交上层处理,ACK3,(1),接收的数据帧通过差错检测发现帧错误,(2),当传输的数据帧丢失,0,1,2,3,4,1,5,6,7,发,0,W,T,1,0,1,2,3,4,1,5,6,7,收,0,W,R,1,暂存,等待,1,号帧,超时间隔,超时重发,一起交上层处理,Selective Reject,ARQ,(3),当接收方发出的确认帧丢失,0,1,2,3,4,1,5,6,7,发,0,W,T,=7,0,1,2,3,4,1,5,6,7,收,0,W,R,=1,丢弃重复帧,超时间隔,超时重发,Selective Reject,ARQ,5,4.,差错控制方式,（,2,）前向纠错,前向纠错系统中,发送端的信道编码器将输入数据序列变换成能够纠正错误的码,接收端的译码器根据编码规律检验出错误的位置并自动纠正。,特点：,不需要反馈信道，适合于只能提供单向信道的场合；,自动纠错，不需要检错重发，延时小，实时性好；,选择的纠错码必须与信道的错误特性密切配合，否则难以到达降低误码率的要求；需要的译码设备复杂；监督元多，传输效率低；,第,3,章 差错控制,5,4.,差错控制方式,（,3,）混合纠错,检错,混合纠错检错方式是前向纠错方式和检错重发方式的结合。发送端发出同时具有检错和纠错能力的数据码，接收端都到数据码后，如果错误小于纠错能力，则自行纠错；如果干扰严重，误码较大，大于了纠错能力，但能检测出来，则经反向信道要求发送端重发。,特点：,实时性和译码复杂性是向前纠错码和检错重发的折中。,第,3,章 差错控制,5,4.,差错控制方式,（,4,）信息反馈,信息反馈方式,(,简称,IRQ),又称回程校验。接收端把收到的数据序列全部由反向信道送回发送端，发送端比较发送的数据序列与收到的数据序列，从而发现是否有错，如果发现有错则将出错的数据序列进行重发，直到没有发现错误为止。,特点：,设备简单，不需要检错，纠错的译码器；,可靠性高，信道利用率低，实时性差；,发送端需要较大的存储容量。,第,3,章 差错控制,1.,检错和纠错的原理,纠错编码之所以具有检错和纠错能力,是因为在信息码之外附加了监督码。监督码不荷载信息,它的作用是用来监督信息码在传输中有无差错,对用户来说是多余的,最终也不传送给用户,但它提高了传输的可靠性。但是,监督码的引入,降低了信道的传输效率。一般来说,引入监督码元越多,码的检错、纠错能力越强,但信道的传输效率下降也越多。,2,.,码距与检错和纠错能力,码重,:,在信道编码中,定义码组中非零码元的数目为码组的重量。,码距,:,把两个码组中对应码位上具有不同二进制码元的位数定义为两码组的距离,.,6,3.2,检错和纠错的基本概念,第,3,章 差错控制,7,汉明,(Hamming),距离,:,在一种编码中,任意两个许用码组间距离的最小值,即码组集合中任意两元素间的最小距离。,例如：,(7,3),码共有,8,个合法编码：,000 001 010 011 100 101 110 111,则：最小的距离是：？,第,3,章 差错控制,3.,码的检错纠错能力与最小码距的数量关系,:,要发现,d,位错误，其编码的汉明距离至少为：,d+1,要纠正,d,位,t,错误，其编码的汉明距离至少为：,2t+1,在一个码组内能纠正,t,位错码,同时能检测,d,个错码（,dt,）,则要求最小码距至少为,d+t+1,若,d,AB,=3,，则有：,若,d,AB,=5,，则有：,A,B,A,A”,A,B,A,A”,若发生,1,位错，,d,AB,=2,，显然错！,若发生,2,位错，,d,A”B,=1,，显然错！采用“就近恢复”原则,若发生,3,位错，,A B,，不知错！,第,3,章 差错控制,7,4.,编码效率,编码效率是指一个码组中信息位所占的比重,用,R,来表示。,其中，,k,为信息位长度，,n,为编码的总长度，,n-k,为监督元的长度。,第,3,章 差错控制,8,5.,纠错编码的分类,(1),按码组的功能分,有检错码和纠错码。,(2),按监督码与信息码元之间的关系分,有线性码和非线性码。,(3),按照对信息码元处理方法的不同分,有分组码和卷积码。,(4),按照信息码元在编码前后是否保持原来的形式不变,可划分为系统码和非系统码。,（,5,）按纠正差错的类型,可分为纠正随机错误的码和纠正突发错误的码。,（,6,）按照每个码元取值来分,可分为二进制码与多进制码。,第,3,章 差错控制,9,1.,奇偶监督码,(1),基本概念,这是一种最简单的检错码,又称奇偶校验码。其编码规则是先将所要传输的数据码元分组,在每组数据后面附加一位监督位,使得该组码连同监督位在内的码组中的,“1”,的个数为偶数,(,称为偶校验,),或奇数,(,称为奇检验,),在接收端按同样的规律检查,如发现不符就说明产生了差错,但是不能确定差错的具体位置,即不能纠错。,3.3,简单的差错控制编码,第,3,章 差错控制,10,在偶校验时有,:,信息码与监督码合在一起“,1”,的个数是偶数,在奇校验时有,:,信息码与监督码合在一起“,1”,的个数是奇数,(2),检错能力,(1,）只能检测奇数个错误，而不能检测出偶数个错误。,（,2,）适合检测随机差错,。,第,3,章 差错控制,2,、,水平一致校验码,水平一致校验码将信息码元先以适当长度划分成小组，各小组按行排列，对各行的信息元进行奇偶校验，得到的校验元附在每行的后面。,注意：通常能查出不大于列长个比特的错误。,1 0 1 0 1 1,0 1 1 0 0 0,1 0 0 0 0 1,1 1 0 1 1 0,0 0 1 0 0 1,通常使用偶校验：,第,3,章 差错控制,11,3.,水平垂直奇偶监督码,(1),基本概念,水平垂直奇偶监督码,是将水平奇偶监督码推广到二维奇偶监督码,又称行列监督码和方阵码。它的方法是在水平监督基础上对方阵中每一列再进行奇偶校验。,第,3,章 差错控制,1 0 1 0 1 1,0 1 1 0 0 0,1 0 0 0 0 1,1 1 0 1 1 0,0 0 1 0 0 1,1 0 1 1 0 1,注意：,能查出所有奇数个比特的错误。,能查出部分偶数个比特的错误。,具有一定的纠错能力。,将数据码中“,1”,的个数以确定的冗余比特数表示，并与数据码一起构成校验码。,如：数据码“,10011”,中有三个“,1”,，则校验码为：,10011,011,4,、,群计数码,第,3,章 差错控制,例如：,(7,3),码的合法编码有八个：,000,0000,100,1110,001,1101,011,1010,111,0100,110,1001,101,0011,010,0111,5.,（,n,k,）码：,即：数据码为：,k,位，冗余码为,(n-k,）位，,则：其合法编码有,2,k,个。,12,汉明码是,1950,年由美国贝尔实验室提出来的，是第一个设计用来纠正错误的线性分组码，汉明码及其变型已广泛应用于数字通信和数据存储系统中作为差错控制码。,1.,纠错码的监督位与码组长度的关系,若码长为 信息位数为 ，则监督位数 。如果希望用 个监督位构造出 个监督关系式来指示一位错码的种可能位置，则要求,3.4,汉明,(Hamming),码,第,3,章 差错控制,13,2.(7,4),汉明码,设分组码,(),中 ,4,。为了纠正一位错码，要求监督位数 。若取 ，则 。我们 用表示这,7,个码元，用 表示三个监督关系式中的校正子，则 的值与错码位置的对应关系可以规定如表,4-4,所列，,错码位置,0 0 0,无错,0 0 1,0 1 0,1 0 0,0 1 1,1 0,1,1 1 0,1 1 1,第,3,章 差错控制,14,构成监督关系，,在发送端编码时，信息位 和 的值决定于输入信号。而监督位 和 应根据信息位的取值按监督关系来确定，,按照上述监督关系所构成的线性分组码就是,(7,4),汉明码。,第,3,章 差错控制,3.7,位信息的汉明码,将码字的每一位从左向右编号，最左边为第一位；,凡是编号为,2,的乘幂的位均是校验位，其余为数据位；,将任一数据位的编号按,2,的最大乘幂展开成和式，和式中每一项所对应的位均是该数据位的校验位。,每个校验位连同所负责的数据位一起构成偶校验。,例如：求,ASCII,字符“,a”,的,Hamming,编码？,第,3,章 差错控制,2 3 4 5 6 7 8 9 10 11,A B 1 C 1 0 0 D 0 0 1,A A A A A,有,A=1,B B B B B B=0,C C C C=1,D D D,D=1,因此，“,a”,的汉明编码为：,10,1,1,100,1,001,第,3,章 差错控制,Hamming,译码,在收端设一个差错计数器并置“,0”,，收到汉明码后，逐个检查各校验位及其负责的数据位的偶校验特性，若被破坏，则将该校验位的序号累加到计数器。待所有校验位检查完后，若计数器的值为,0,，则传输正确，否则，计数器的值即为出错的位。,2 3 4 5 6 7 8 9 10 11,A B 1 C 1 0 0 D 0 0 1,A A A A A,有,A=1,B B B B B B=0,C C C C=1,D D D,D=1,0,第,3,章 差错控制,3.5,循环冗余校验码（,Cyclic Redundancy Code,）,1.,循环码的循环特性及多项式表示,1.,循环码的循环特性,:,循环码是一种线性分组码，且为系统码，即前,k,位为信息位，后,r,位为监督位，它除了具有线性分组码的一般性质外，还具有循环性，所谓循环性,就是循环码中任一许用码组经过循环移位后（将最右端的码元移至左端，或反之）所得到的码组仍为它的一许用码组。,如果：,C=Cn-1Cn-2.C1C0,是合法的,则 ：,C=Cn-2.C1C0,Cn-1,也是合法的,第,3,章 差错控制,2.,循环码的码的多项式表示,为了便于用代数理论来研究循环码，把码组长度为,n,的码组与,n-1,多项式建立一一对应关系，即把码组中各码元当作一个多项式的系数,如：数据码字：,1010101,则：码字多项式：,x,6,+x,4,+x,2,+1,第,3,章 差错控制,3.CRC,编码方法,设：,要发送的信息码字多项式为：,M(x),双方协议规定的生成多项式为：,G(x),通信系统中，常见的生成多项式标准有：,CRC,12=,x,12,+,x,11,+,x,3,+,x,2,+,x,1,+1,CRC,16=,x,16,+,x,15,+,x,2,+1,CRC-32=x,32,+x,26,+x,23,+x,22,+x,16,+x,12,+x,11,+x,10,+x,8,+x,7,+x,5,+x,4,+x,2,+1,CRC,CCITT =x,16,+x,12,+x,5,+1,编码步骤：,(1),用生成多项式的最高位乘以,M(x),：,x,n-k,M(x),(2),用,(1),的结果除以,G(x),(3),所得余数,R(x),即为,CRC,的冗余码。,第,3,章 差错控制,根据题意有：,x,n-k,M(x)=x,4,(x,2,+x)=x,6,+x,5,x,4,+x,3,+x,2,+1,x,6,+x,5,x,4,+x,3,+x,2,+1,x,2,+1,x,6,+x,5,+x,4,+x,2,X,4,+x,2,x,3,+1,则：冗余码,R(x),为：,1001,1 1 0 0 0 0 0,1 1 1 0 1,11101,1 0 1,1 0 1 0 0,1 1 1 0 1,1 0 0 1,例如：对于,(7,3),码，若数据码字为,110,，,G(x),是,x,4,+x,3,+x,2,+1,求其冗余校验码。,第,3,章 差错控制,x,n-k,M(x),G(x),=Q(x),余数为：,R(x),x,n-k,M(x)=Q(x)G(x)+R(x),有：,x,n-k,M(x)+R(x)=Q(x)G(x),CRC,校验码：编码后的数据流,4.CRC,译码方法,第,3,章 差错控制,设：,收到的信息码字多项式为：,H(x),双方协议规定的生成多项式为：,G(x),则：,H(x),G(x),能除尽，传输正确,否 则，传输错误,若传输正确，则,H(x)=Q(x)G(x),Q(x)G(x),G(x),显然是可以除尽的，反之，除不尽,第,3,章 差错控制,