计算机网络与数据通信.ppt

计算机网络与数据通信,第4章 差错控制与校验,4.1 差错控制技术,差错的定义 通过通信信道后接收的数据与发送的数据不一致的现象称为传输差错 差错产生的原因 数据信号与噪声的叠加导致接收电路在电平判决时出现错误,4.1 差错控制技术,差错控制技术差错控制编码 发送端：在发送数据之前，先按照某种规则在数据位之外附加上一定的冗余位后再发送，称为差错控制编码过程。 接收端：收到编码后，利用相同的规则对信息位和冗余位之间的关系进行检测，判断传输过程中是否发生差错。,差错类型及解决办法,4.1 差错控制技术,传输错误处理方法,反馈重发技术,停等协议： 发送方发送一块数据后， 就停止发送动作，开始计时，等待接收方的反馈结果。 发送方仅当收到正确的接收确认之后，才继续发送后继块数据； 如果接到否定确认，或者计时器超时，重新传送本数据块。 特点 半双工方式进行通信 控制简单，易于实现。 传输效率低。,反馈重发技术,滑动窗口协议： 发送方一次连续发送多块数据（称为窗口尺寸）； 接收方对每块数据进行差错分析，如果发现错误，立即反馈给发送方； 接收方可对接收到的多个正确的数据块进行一次性确认； 发送方根据反馈的结果，重发指定的数据块，或重发指定数据块及其之后的所有数据块。 特点： 通信双方以全双工方式进行通信 控制复杂。 传输效率高。尤其对信道质量好、差错率低的情况。,4.2 检错码,4.2.1 奇偶校验 将数据分组，每一组数据后附加一个校验位，使得该组数据(包括校验位)中1的个数为偶数(偶校验)或奇数(奇校验)。 三种方式： 垂直奇偶校验 水平奇偶校验 水平垂直奇偶校验,不能完全检测突发错误：两个相同值的比特位同时变为相反的值,只有在所有列都发送完毕后，错误才能够完全检测出来，而且接收方可能不知道哪个列是不正确，只有重发所有列，对于单个错误，会给通信设备增加很大负担,垂直奇偶校验,编码规则 对一组字符各对应位（垂直方向）加校验位构成校验单元,水平奇偶校验,编码规则 以一组字符中对应位（水平方向）作为校验单元进行奇偶校验,水平垂直奇偶校验,编码规则 将前面两种校验方式相结合而成,4.2 检错码,4.2.2 循环冗余校验码（CRC） 把要发送的数据看成是一个多项式的系数 数据为bn-1bn-2b1b0 (其中为0或1)，则其对应的多项式为 bn-1Xn-1+bn-2Xn-2+b1X+b0 例如： 数据“10010101”可以写为多项式X+X 4 +X 2 +1。,循环冗余校验方法的原理,(1) 设要发送的数据对应的多项式为P(x)。 (2) 发送方和接收方约定一个生成多项式G(x)，设该生成多项式的最高次幂为r。 (3) 在数据块的末尾添加r个0，则其相对应的多项式为M(x)=XrP(x)。（左移r位） (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)+2R(x) /G(x) 余式为0。 若T(x)T(x)，余式不为0。,例：信息码:110011 生成码:11001,循环冗余校验方法举例,循环冗余校验方法举例,已知：信息码:110011 信息多项式:K(X)=X5+X4+X+1 生成码:11001 生成多项式:G(X)=X4+X3+1(r=4) 求：循环冗余码和码字。 解：1)(X5+X4+X+1)*X4的积是 X9+X8+X5+X4 对应的码是1100110000。 2)积G(X)(按模二算法)。 由计算结果知冗余码是1001， 码字就是1100111001。 1 0 0 0 0 1Q(X) G(x)1 1 0 0 1 )1 1 0 0 1 1 0 0 0 0F(X)*Xr 1 1 0 0 1 ， 1 0 0 0 0 1 1 0 0 1 1 0 0 1R(X)(冗余码),循环冗余校验方法举例,4.3 纠错码,检错码只能检测到错误，而纠错码不仅能检测出错误，而且还可以检测出哪位发生了错误并进行纠正。 纠错码有很多种，如：海明码，卷积码及BCH码等。,4.3.1 海明码的组成,4.3.1 海明码的组成 由数据位及校验位组合而成的 ，但它的数据位和校验位是交叉排列的 设要发送的数据为mm1m2m3m4m5m6m7，则海明码为AB mCm1m2m3Dm4m5m6m7，其中A、B、C、D为校验位。 各位所对应的编号分别为1到12，校验位所对应的编号均为2的幂次 将每个数据位的编号用校验位编号的和来表示，即 3=2+1 5=4+1 6=4+2 7=4+2+1 9=8+1 10=8+2 11=8+2+1 12=8+4,4.3.1 海明码的组成,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.3.2 纠错原理,在接收方有一个出错计数器，首先将其置0 接收到数据后对每个校验位及其所对应的数据位进行校验，如果出错就将该校验位的编码加入到出错计数器， 最后根据出错计数器的值就可以确定是哪位出错，然后将该位数据取反即可。,4.3.2 纠错原理举例,例如：要发送的数据为“10101100”，海明码为“AB1C010D1100”，按偶校验规则进行校验，可得A=0，B=1，C=1，D=0，即“011101001100”，将其发送到接收端，若因某种原因第5位数据由“0”变为“1”，则在接收端对第一个校验位A进行检查时可以发现有问题，将该校验位的编码“1”加到出错计数器中，然后对第二个校验位进行检查，没有发现错误，再对第三个校验位C进行检查，又发现错误，将该校验位的编码“4”加到出错计数器中，最后对第四个校验位进行检查没有错误。此时，出错计数器的值为“5”，说明第5位有错，将第5位数据取反，就可得到正确的数据。,4.3.2 纠错原理举例,011101001100,011111001100,A C,出错计数器值为