《差错控制》PPT课件.ppt

《《差错控制》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《差错控制》PPT课件.ppt（60页珍藏版）》请在三一办公上搜索。

1、差错控制(信道编码),差错控制的方式 采用检错码的差错控制 采用纠错码的差错控制 不用编码的差错控制 关于帧或分组顺序的差错控制,*,网络基础,数据通信中的实际情况,*,网络基础,通信信道中的噪声,通信信道中的噪声分为热噪声和冲击噪声。热噪声是由传输媒体的电子热运动产生的，其特点是时刻存在，幅度小，干扰强度与频率无关，但频谱很宽，属于随机噪声。由热噪声引起的差错属于一种随机差错。冲击噪声是由外界电磁干扰引起的，与热噪声相比，冲击噪声的幅度较大，是引起差错的主要原因。冲击噪声持续时间与数据传输中每个比特的发送时间相比，可能较长，因而冲击噪声引起的相邻多个数据位出错呈突发性。冲击噪声引起的传输差错

2、称为突发差错。,信道分类,按照噪声或干扰的变化规律，可把信道分为三类：随机信道：恒参高斯白噪声信道是典型的随机信道，其中差错的出现是随机的，而且错误之间是统计独立的。突发信道：具有脉冲干扰的信道，是典型的突发信道。错误是成串成群出现的，即在短时间内出现大量错误。混合信道,*,网络基础,差错产生的原因,在通信过程中出现的传输差错，是由随机差错和突发差错共同构成的，而造成差错可能的原因包括：在数据通信中，信号在物理信道上的线路本身的电气特性随机产生的信号幅度、频率、相位的畸形和衰减；电气信号在线路上产生反射噪声的回波效应；相邻线路之间的串线干扰；大气中的闪电、电源开关的跳火、自然界磁场的变化以及电

3、源的波动等外界因素。,*,网络基础,差错的控制,在数据通信中，原发送信息，不具备抗干扰性能，如果引入冗余度后，就可以使新的码组具有一定的抗干扰能力。例如，两个码元构成四种码组00、01、10、11，无法检错，而使用三个码元，有用码组为000、011、101和110；目前差错控制常采用冗余编码方案，检测和纠正信息传输中产生的错误。冗余编码思想就是：把要发送的有效数据在发送时按照所使用的某种差错编码规则加上控制码（冗余码），当信息到达接收端后，再按照相应的校验规则检验收到的信息是否正确。,差错控制的基本工作方式,前向纠错方式FEC发端发送能够纠正错误的码，收端收到信码后自动地纠正传输中的错误。特点

4、是单向传输，实时性好，但译码设备较复杂。检错重发方式ARQ发端发送检错码，收端收到信码后能够检查出错误。混合纠错方式HEC是FEC和ARQ方式的结合。信息反馈方式IF收端将接收的消息原封不动地送回发端，由发端将反馈信息和原发送信息进行比较，发现错误进行重发，其优点是方法和设备简单，无需纠（检）错编译系统。,*,网络基础,差错控制的基本工作方式,对于不同类型的信道，应采用不同的差错控制技术，否则就将事倍功半。检错重发可用于双向数据通信，前向纠错则用于单向数字信号的传输，例如广播数字电视系统，因为这种系统没有反馈通道。,检错重发（ARQ）,典型系统检错重发方式的原理方框图,常用的检错重发系统有三种

5、，即停发等候重发、返回重发和选择重发。,*,网络基础,检错重发（ARQ）,1、检错重发（ARQ）（1）思路 发送端对数据序列进行分组编码，加入一定的码元使之具有一定的检错能力，成为能够发现错误的码组。接收端收到码组后，按一定规则对其进行有无错误的判别，并把判决结果（应答信号）通过反向信道送回发送端。如有错误，发送端把前面发出的信息重新传送一次，直到接收端认为已正确接收到信息为止。（2）重发方式（3种形式）：停发等候重发返回重发选择重发,*,网络基础,停止等待协议,在停止等待ARQ方式中，发送端在发送完一个数据帧后，要等待接收端返回的应答信息，若应答为确认信息（ACK）时，发送端才可以继续发送下

6、一个数据帧；若应答为不确认帧（NAK）时，发送端需要重发这个数据帧。停止等待ARQ协议非常简单，由于是一种半双工的协议，因此系统的通信效率低。,*,网络基础,连续ARQ协议,工作原理发送方发完一帧后，不必停下来等待对方的应答，可以连续发送若干帧；如果在发送过程中收到接收方的肯定应答，可以继续发送；若收到对其中某一帧的否认帧，则使用某种ARQ方式重发数据；优点连续发送提高了信道利用率；连续ARQ协议包括选择ARQGo-Back-N ARQ,*,网络基础,ARQ,*,网络基础,选择ARQ与Go-Back-N的比较,采用选择ARQ方式时，由于接收到的数据帧有可能是乱序的，因此，接收端必须提供足够的缓

7、存先将每个数据帧保存下来，然后对数据帧重新排序。但由于该方式仅重发出错的数据帧，因此，信道利用率高。对于Go-Back-N方式，接收到的数据帧是按顺序排列的，因而接收端不需要太多的缓存，但由于发送端要将出错数据之后的已发送数据帧重新发送，致使信道利用率相对较低。,*,网络基础,*,网络基础,三种重发方式的比较,*,网络基础,ARQ的优缺点,（3）ARQ的优缺点需反向信道，实时性差。编码效率较高。译码设备较简单。,*,网络基础,前向纠错（FEC）,2、前向纠错（FEC）思路前向纠错系统中，发送端的信道编码器将输入数据序列变换成能够纠正错误的码，接收端的译码器根据编码规律检验出错误的位置并自动纠正

8、。优点：不需要反向信道，实时性好。缺点：1、所选择的纠错码必须与信道的错码特性密切配合，否则很难达到降低错码率的要求；2、为了纠正较多的错码，译码设备复杂；3、要求附加的监督码也较多，传输效率较低。,*,网络基础,混合纠错检错（HEC）,思路混合纠错检错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端发出同时具有检错和纠错能力的码，接收端收到码后，检查错误情况，如果错误少于纠错能力，则自行纠正；如果干扰严重，错误很多，超出纠正能力，但能检测出来，则经反向信道要求发端重发。优缺点混合纠错检错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷。,*,网络基础,例1：某数据通信系

9、统采用停发等候重发的差错控制方式，请在下图的“？”处填入ACK、NAK或码组号。,*,网络基础,例2：某数据通信系统采用选择重发的差错控制方式，发送端要向接收端发送7个码组（序号06），其中1号码组出错，请在下图中的空格里填入正确的码组号。,*,网络基础,例3：某数据通信系统采用返回重发的差错控制方式，发送端要向接收端发送8个码组（序号07），其中1号码组出错，请在下图中的空格里填入正确的码组号。,差错控制编码的分类,按照差错控制编码的用途：检错码、纠错码和纠删码。按照信息码元和监督码元之间的函数关系：线性码和非线性码。按照对信息元处理方式的：分组码和卷积码。按照码组中信息码元在编码前后是否相

10、同：系统码和非系统码。按照纠（检）错误的类型：纠（检）随机错误码、纠（检）突发错误码和既能纠（检）随机错误同时又能纠（检）突发错误码。按照每个码元的取值：二进码和多进码。,差错控制编码的基本原理,差错编码的基本思想是在被传输信息中增加一些冗余码，利用附加码元和信息码元之间的约束关系加以校验，以检测和纠正错误，增加冗余码的个数可增加纠检错能力。,信息码元、监督码元,信息码元又称信息序列或信息位，这是发端由信源编码后得到的被传送的信息数据比特，通 常以k表示。监督码元又称监督位或附加数据比特，这是为了检纠错码而在信道编码时加入的判断数据位。通常以r表示，即为：n=k+r或r=nk经过分组编码后的码

11、又称为(n,k)码，即表示总码长为n位，其中信息码长(码元数)为k位，监督码长(码元数)为r=nk。通常称其为长为n的码字(或码组、码矢)。,许用码组与禁用码组,信道编码后的总码长为n，总的码组数应为2n个。其中被传送的信息码组 有2k个，通常称为许用码组；其余的码组共有2n-k个，不传送，称为禁用码组。,编码效率,发端误码控制编码的任务正是寻求某种规则从总码组中选出许用码组；而收端译码的 任务则是利用相应的规则来判断及校正收到的码字符合许用码组。通常又把信息码元数目k 与编码后的总码元数目(码组长度)n之比称为信道编码的编码效率或编码速率，表示为：R=k/n=k/k+r 其中，k是信息元的个

12、数，r为校验码个数。这是衡量纠错码性能的一个重要指标，一般情况下，监督位越多(即r越大)，检纠错能力越 强，但相应的编码效率也随之降低了,码长、码重、码距,编码码组的码元总位数称为码组的长度，简称码长。码组中，“1”码元的数目称为码组的重量，简称码重。两个等长码组之间对应位上码元不同的数目称为这两个码组的距离，简称码距。码距又称汉明距。通常用d表示。各码组之间距离最小值称为最小码距，通常用d0表示。,*,网络基础,最小码距与检纠错能力的关系,在一个码组内为了检测e个误码，要求最小码距应满足：d0 e1 在一个码组内为了纠正t个误码，要求最小码距应满足：d0 2t1 在一个码组内为了纠正t个误码

13、，同时能检测e个误码(et)，要求最小码距应满足：d0 et1；,*,网络基础,差错编码,差错检测编码：奇偶校验码；水平垂直奇偶校验码；恒比码CRC循环冗余码等；差错纠错编码：汉明码；卷积码；,*,网络基础,奇偶校验码,采用奇偶校验法，在每个字符的数据位传输之前，先检测并计算奇偶校验位，然后将其附加在后；根据采用的奇偶校验位是奇数还是偶数，推出一个字符包含“1”的数目，接收机重新计算收到字符的奇偶校验位，并确定该字符是否出现传输差错；若每个字符只采用一个奇偶校验位时，只能发现单个比特差错，如果有两个或两个以上比特出错，奇偶校验位无效；异步传输和面向字符的同步传输均采用奇偶校验技术；多用于计算机

14、内部数据校验。,*,网络基础,循环冗余码CRC,CRC是一种较为复杂的校验方法，它先将要发送的信息数据与一个通信双方共同约定的数据进行除法运算，并根据余数得出一个校验码，然后将这个校验码附加在信息数据帧之后发送出去。接收端接收数据后，将包括校验码在内的数据帧再与约定的数据进行除法运算，若余数为“0”，就表示接收的数据正确，若余数不为“0”，则表明数据在传输的过程中出错。,*,网络基础,循环冗余校验码(CRC)所谓循环码是这样一组代码,其中任一有效码字经过循环移位后得到的码字仍然是有效码字,不论是右移或左移,也不论移多少位。例如,若(a n-1 a n-2 a1 a0)是有效码字,则(a n-2

15、 a n-3 a0 a n-1),(a n-3 a n-4 a n-1 a n-2),等都是有效码字。循环冗余校验码是一种循环码,它有很强的纠错检错能力,而且硬件实现很容易,在局域网中有广泛的应用。它所约定的校验规则是：让校验码能为某一约定代码所除尽；如果除得尽，表明代码正确；如果除不尽，余数将指明出错位所在位置。,*,网络基础,CRC校验码编码过程取k位信息码，再将其左移r位，得到k+r位二进制码；用生成码去模2除（异或）该二进制码，得到r为余数。该余数即为所得校验码；将该校验码加在原信息码后，就构成待传输的k+r位CRC码（信息码加校验码）。,模2运算:用模2运算进行加法时不进位，减法和加

16、法是一样的。例如：111110100101,*,网络基础,CRC码的译码过程接收端译码要求有两个：检错和纠错。检错：原理和操作都很简单。以生成多项式G(x)对应的代码去模2除收到的代码，即T(x)对应的代码，若余数为0，则说明传输过程无差错，否则有差错。,*,网络基础,编码：信息序列1001001对应的码多项式为K(x)x6+x3+1xr.K(x)x9+x6+x3，对应的代码为1001001000(相当于信息码左移3位)选 生成多项式G(x)x3+x2+1，对应的码多项式为1101,应用举例,*,网络基础,余数,运算演示：,*,网络基础,编码结果：得到检验序列111。因此传输的代码序列为100

17、1001111,码多项式为T(x)。译码：如收到的代码为1001001111，则用其除以生成多项式对应的代码1101，得余数为0(读者自己验证)。说明信息在传输过程中没错，将最后的r位校验位码“111”去掉，就得到信息码1001001。,*,网络基础,译码并纠错：若收到的T(x)代码为1001001101，按原过程计算，将其除以生成多项式对应的代码1101，得余数为10(如下页)。这就说明传输有差错，差错e(x)=x，其代码为10。将其纠正1001001101+10=1001001111,*,网络基础,运算演示：,*,网络基础,纠错依据：更换不同值的M(x)可以证明,出错模式只与码制和选用的

18、G(x)有关,与 M(x)代码值无关。据此可作为该种码制的纠错依据。,(7,4)制CRC码的出错模式表(G(x)=1011),*,网络基础,CRC码的特点CRC码是面向数据帧编码检错；理论证明，循环冗余检验码能够检验出：全部奇数个错、全部偶数位错和全部小于、等于冗余位数的突发性错误；理论证明,余数代码与出错位序号之间有唯一的对应关系，据此，CRC有纠错功能；一旦G(x)选定，CRC码对帧内有(r+1)bit出错时无法纠错；使用CRC技术只能做到无差错接受(不包括丢失帧),可靠传输需加上确认重传机制。,*,网络基础,由以上分析可知，只要选择足够的冗余位，就可以使得漏检率减少到任意小的程度。广泛使

19、用的生成码多项式主要有以下四种：CRC12x12+x11+x3+x2+x+1 CRC16x16+x15+x2+(IBM公司)CRC16x16+x12+x5+(ITU-T)CRC32X32+x26+x23+x22+x16+x11+x10+x8+x7+x5+x4+x2+x+1,3.线性分组码,线性分组码的定义和特点线性分组码，是指信息码元与监督码元之间的关系可以用一组线性方程来表示的分组码，即在（n，d）分组码中，每一个监督码元都是码组中某些信息码元按模2和而得到的，线性分组码是一类重要的纠错码，应用很广。,汉明码,汉明码是一类常见的线性分组码，是一种能够纠正单个错误的完备码。要纠正码组中的单个错

20、误，则要求与单个错误图样对应的伴随式各不相同，且不能为全零。若码长为n，监督码元的个数为r，则要求2r-1n。码组为汉明码时取等号。即用来纠正单个错误时，汉明码所用的监督码元个数最少，效率最高。,循环码,循环码是另一类重要的线性分组码，它除了具有线性码的一般性质外，还具有循环性，即循环码组中任一码组循环移位所得的码组仍为该循环码中的一许用码组。,CRC码的原理,如果有r个校验码元，其中每一个校验码元是该码元组中某些信息码元的模2和，由此组成的一组长为n=k+r的码，称为线性码，假定我们构成(n=7,k=3)这样的线性码，若已知三个信息码元为C6、C5和C4，而校验码元C3、C2、C1和C0是未

21、知的。校验码元与信息码元间的关系是根据以下四个线性关系式确立的。,CRC码的原理,CRC码的原理,按上页编出的线性码,CRC码的原理,当我们从表中任意挑选出两个码组时，将对应比特按模2相加，所得到的新码组仍然是上页表中的某一码组。这说明由8个码字组成的线性码具有封闭性。封闭性是线性码的一个重要特性。,CRC码的原理,假设待传送的数据 M（k bit）。我们在M的后面再添加供差错检测用的 r bit 冗余码一起发送。用二进制的模 2 运算进行 2r 乘 M 的运算，这相当于在 M 后面添加 r 个 0。得到的(k+r)bit 的数除以事先选定好的长度为(r+1)bit 的数 G，得出商是 Q 而

22、余数是 R，余数 R 比除数 G 至少要少1 个比特。,例子,设 M=1010001101，r=5,G=110101，模 2 运算的结果是：商 Q=1101010110，余数R=01110。将余数 R 作为冗余码添加在数据 M 的后面发送出去，即发送的数据是101000110101110，或 2rM+R。,例子,1101010110 Q 商 除数 P 110101 101000110100000 2nM 被除数 110101 111011 110101 111010 110101 111110 110101 101100 110101 110010 110101 01110 R 余数,采用纠错码的差错控制,Hamming于1950年在美国贝尔实验室提出了海明码，是第一个用来纠错的线性码，被广泛地应用在数据通信和数据存储系统的差错控制中。所谓海明校验实质上是奇偶校验，是分组奇偶校验。,海明校验码,PP21P3000P4101分组编码，设发送与接收双方均采用奇校验，则P1=0，P2=1，P3=1，P4=1发送端发送的比特流为,