《无线通信与网络课件.ppt》由会员分享，可在线阅读，更多相关《无线通信与网络课件.ppt（38页珍藏版）》请在三一办公上搜索。
1、第8章 编码和差错控制,常用的差错检验方法：奇偶校验和循环冗余检错。常用的纠错方法：海明码,差错控制,差错控制常用自动请求重发ARQ和前向纠错FEC机制来实现,1、奇偶校验 奇偶校验（Parity Detection）是一种最基本的校验方法，其中奇偶校验码是一种检错码。其方法是在面向字节的数据通信中，在每个字节的尾部加上一个校验码，构成一个带有校验位的码组，使得码组中“1”的个数成为偶数（称为偶校验）或者奇数（称为奇校验），并把整个码组一起发送出去。接收端在收到信号后，对每一个码组检查其中“1”的个数是否为偶数（对奇校验则检查“1”的个数是否为奇数），如果检查通过就认为收到的数据正确，否则发回
2、一个信号给发送端，要求重新发送该段数据,例：发送 G（1110001），采用奇校验时，奇偶位为1，即传输11100011。接收器检查接收到的数据的1的个数为奇数，就认为无错误发生。*若其中两位同时发生错误，检测不出错误*只能检错，不能纠错 根据实现过程冗余位添加方法可分为：垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验,水平奇偶校验：为了降低对突发错误的漏检率，可以采用水平奇偶校验（Horizontal Parity Detection）的方法。水平奇偶校验又称为横向奇偶校验，它是对各个信息段的相应位横向进行编码，产生一个奇偶校验冗余位。水平垂直奇偶校验：同时进行水平奇偶校验和垂直奇偶校验就构成
3、了水平垂直奇偶校验，也称为纵横向校验。水平垂直奇偶校验能检测出所有3位或3位以下的错误、奇数位错、突发长度小于等于p+1的突发错误以及很大一部分偶数位错。测量表明，这种方式的编码可使误码率降至原误码率的百分之一到万分之一。,奇偶校验,垂直校验,水平校验,2、循环冗余检错（CRC）利用循环冗余码（CRC，Cyclic Redundancy Code）进行纠错。CRC：假设要传送的信息有k位，则发送端会自动加上r位的校验序列，然后再传送出去，这k+r位数可以被某个事先设定好的数整除。当接收端收到数据后用原先那个设定好的数来除，若没有余数出现，则表示数据传送正确；相反，若有余数出现，则表示数据传送有
4、误。,CRC码检错方法实现过程：将要发送的数据比特序列当做一个多项式f（x)的系数，在发送端用收发双方预先约定的生成多项式G(x)去除，求得一个余数多项式。将余数多项式加到数据多项式之后发送到接收端 在接收端用同样的生成多项式G(x)去除接收数据多项式f(x)，得到计算余数多项式。如果计算余数多项式与接收余数多项式相同，则表示传输无差错；如果计算余数多项式与接收余数多项式不相同，则表示传输有差错，由发送方重发数据，直至正确为止。,CRC生成多项式G(x)由协议规定，目前已有多种生成多项式列入国际标准中，例如：CRC-12 G（x）=x12+x11+x3+x2+x+1 CRC-16 G（x）=x
5、16+x15+x2+1 CRC-CCITT G（x）=x16+x12+x5+1 CRC-32 G（x）=x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1,CRC校验的工作过程：（1）在发送端，将发送数据多项式f(x)xk，其中k为生成多项式的最高幂值，例如CRC-12的最高幂值为12，则发送f（x）x12；对于二进制乘法来说，f（x）x12的意义是将发送数据比特序列左移12位，用来放入余数；,（2）将f（x）xk除以生成多项式G（x），得：式中R（x）为余数多项式；,（3）将f（x）xk+R（x）作为整体，从发送端通过通信信道传送到接收端；（
6、4）接收端对接收数据多项式f（x）采用同样的运算，即：求得余数多项式R(x)；,（5）接收端根据计算余数多项式R(x)是否等于接收余数多项式R(x)，来判断是否出现传输错误。例：已知信息码为1000100101。给定G（x）=x5+x4+x2+1。求CRC 循环校验码。,解：（1）因为已知信息码为：1000100101，所以 f（x）=x9+x5+x2+1（2）f（x）xk=x14+x10+x7+x5 G（x）=x5+x4+x2+1=110101,（3）计算过程：,（4）CRC循环冗余校验码为：1 0 0 0 1 0 0 1 0 1 0 0 0 1 1,3、海明码 是由RHamming在195
7、0年首次提出的，它也是一种可以纠正一位差错的编码，但它的编码效率要比正反码高得多（当信息位足够长时）。基础知识：二进制数表示 二进制逻辑运算 数的表示方法 奇偶校验,奇偶校验码；若信息的位数为kn1位，可表示为an-1an-2a1，加上一位偶校验位a0，构成一个n位的码字an-1a n-2a1 a0。在接收端校验时，可按下列关系式来计算：S=an-1+a n-2+a1+a0（a0 用以凑成偶数个“1”）结果：若S0，则无错，若S1，则有错。上式可称为监督关系式，S称为校正因子。在奇偶校验情况下，只有一个监督关系式，一个校正因子，其取值只有两种（0或l），分别代表了无错和有错两种情况，而不能指出
8、差错所在的位置。,可以增加冗余位，就相应地增加监督关系式和校正因子，就能区分更多的情况。例如，若有两个（2位）校正因子，则其取值就有4种可能：00、01、10或11，就能区分4种不同情况。若其中一种表示无错，另外三种不但可以用来指出有错，还可用来区分错误的情况，如指出是哪一位错等。,一般而言，信息位为k位，增加r位冗余位，构成：nkr位码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中的n个不同位置的一位错，则要求：2r n1或者2r kr1 注:(n=k+r)如果用k4为例来说明，要满足上述不等式，则r3。假设取r3则nkr7，即在4位信息位a6a5a4a3后面加上3位冗余位
9、a2a1a0，构成7位码字a6a5a4a3a2a1a0。,a2、a1和a0分别由4位信息位中某几位半加得到。校验时，a2、a1和a0 就分别和这些位半加构成三个不同的监督关系式。规定：无错时，这三个关系式的值S2、S1和S0全为“0”。若a2错，则S21，而S1 S00；若a1错，则S11，而S2 S00；若a0错，则S01，而S2 S10。,S2 S1 S0这三个校正因子其它4种编码值可用来区分a6a5a4a3一位错，该对应关系可以规定如表13S2S1S0 000 001 010 100 011 101 110 111 错码位置 无 a0 a1 a2 a3 a4 a5 a6由表可见，a2、a
10、4、a5或a6的一位错都应使S21，由此得到监督关系式：S2 a2a4十a5十a6同理还有：S1 a1a3十a5十a6 S0 a0a3十a4十a6,在发送端编码时，信息位a6a5a4和a3的值取决于输入信号，是随机值。冗余位a2a1和a0的值应根据信息位的取值按监督关系式来决定，便上述三式中的S2 S1 和S0 取值为零，即：a2 a4 a5 a6 0a1 a3 a5 a6 0 a0 a3 a4 a6 0由此可求得：a2 a4十a5十a6a1 a3十a5十a6a0 a3十a4十a6已知信息位后，按此三式即可算出各冗余位。,对于各种信息位算出的冗余位如表：,在接收端收到每个码字后，按监督关系式算
11、出S2、S1和S0，若全为“0”则认为无错。若不全为“0”，在一位错的情况下，可查表来判定是哪一位错，从而纠正之。例如码字0010101传输中发生一位错，在接收端收到的为0011101，代入监督关系式：S2 a2a4十a5十a6S1 a1a3十a5十a6S0 a0a3十a4十a6可算得S20、S11和S0 1，,由表：S2S1S0 000 001 010 100 011 101 110 111 错码位置 无 a0 a1 a2 a3 a4 a5 a6可查得S2S1和S0 011对应于a3错，因而可将0011101纠正为0010101。上述海明码的编码效率为47。若K7，按2rk十r1可算得r至少
12、为4，此时编码效率为711。结论：信息位长度越长时编码效率越高。,照例海明码只能纠正一位错，若用下述方法排列可以纠正传输中出现的突发性错误。将连续P个码字排成一个矩阵，每行一个码字，如图所示 信息位 冗余位0 0 0 10 1 11 0 1 0 0 1 01 0 1 1 0 0 10 1 0 0 1 1 0 P个码字组成矩阵0 1 0 0 1 1 0 每行一个字吗1 1 0 1 0 1 01 1 1 1 1 1 10 1 1 0 0 1 1而逐位发送的顺序则是一列一列进行的，图中的顺序为。如果发生突发错长度小于等于P的突发错误，那么在P个码字中每个码字最多有一位差错，正适合由海明码纠正之。,A
13、RQ:自动请求重发,又称反馈重发发送端首先对发送序列（信息码）进行差错编码，生成一个可以检测出错误的校验序列（监督码），然后连同数据一起发送出去；接收端根据校验序列的编码规则判决是否出错，并把判决结果通过反馈通道传回给发送端：,通常处理传输差错的办法如下：肯定确认：接收端收到一个帧后未发现错误，回送一个确认信号，用ACK表示。否定确认：用NAK表示。超时重发(Overtime)：发送端发出一个帧后开始计时，如果在规定的时间内没有收到确认信号（ACK或NAK），则认为发生帧丢失的或确认信号丢失。必须重发。,ARQ技术结合流量控制又分为三种形式：1.停止等待ARQ(Stop_and_Wait)2.
14、返回N帧ARQ(Go_back_N)3.选择重发ARQ(Selective_Retransmit),链路数据传输过程：正常,链路数据传输过程：数据帧出错,链路数据传输过程：数据帧丢失,链路数据传输过程：确认帧丢失,(1)返回N帧ARQ示意图,ACK1,ACK2,NAK3,NAK4,NAK5,NAK6,NAK7,NAK8,NAK9,ACK3,ACK4,ACK5,ACK6,NAK7,提交网络层,提交网络层,丢弃,丢弃,接收端,发送端,回退N帧：N=滑动窗口大小发送端:每收到ACK帧，继续发送新数据每收到NAK帧，回退N帧，即重发出错帧以及其后发送的 N-1 帧数据（不管它们是否正确）,（2）选择性重发ARQ示意图,ACK1,ACK2,NAK3,ACK4,ACK5,NAK6,ACK7,ACK8,ACK9,ACK3,ACK10,NAK6,ACK11,与4、5号帧一起提交网络层,提交网络层,暂存与缓冲区中,暂存与缓冲区中,重传,NAK12,ACK13,NAK14,ACK15,ACK16,ACK17,ACK6,与711号帧一起提交网络层,重传,重传,
