1、1/30第第8章章 差错控制原理差错控制原理n8.1 差错产生的原因及其差错类型差错产生的原因及其差错类型n8.2 差错控制基本原理差错控制基本原理n8.3 差错控制编码差错控制编码n8.4 差错控制方法差错控制方法2/30第第8章章 差错控制原理差错控制原理n差错：差错：通常把接收数据与发送数据不一致的现通常把接收数据与发送数据不一致的现象称为传输差错，简称为差错。象称为传输差错，简称为差错。3/308.1 差错产生原因及差错类型差错产生原因及差错类型n干扰：干扰：脉冲干扰、随机噪声干扰、人为干扰等。脉冲干扰、随机噪声干扰、人为干扰等。n噪声噪声两类：随机噪声和脉冲噪声。两类：随机噪声和脉冲
2、噪声。n随机噪声：随机噪声：时时处处存在，幅度较小，频带宽。差错时时处处存在，幅度较小，频带宽。差错是随机的、离散的，是一种随机独立差错。是随机的、离散的，是一种随机独立差错。n脉冲噪声脉冲噪声：强度大，差错成串出现，即无错则已，有：强度大，差错成串出现，即无错则已，有错一片。是一种突发性差错。错一片。是一种突发性差错。n混合差错：上两种噪声同时引起的差错。混合差错：上两种噪声同时引起的差错。4/308.1 差错产生原因及差错类型差错产生原因及差错类型 5/308.2 差错控制基本原理差错控制基本原理n差错控制：差错控制：在通信过程中产生错误时，能有效地检测出错误，并进行在通信过程中产生错误时
3、，能有效地检测出错误，并进行纠正，这种方法叫检错与纠错，统称为差错控制。纠正，这种方法叫检错与纠错，统称为差错控制。n差错控制方案差错控制方案：n（1）纠错编码：）纠错编码：传输的数据单元带有足够的冗余信息，在接收端发传输的数据单元带有足够的冗余信息，在接收端发现并自动纠正传输错误。现并自动纠正传输错误。n（2）检错编码）检错编码：传输的数据单元仅带有足以使接收端发现差错的冗：传输的数据单元仅带有足以使接收端发现差错的冗余信息，但不能确定错误位置，因而不能纠正错误，只能发现错误。余信息，但不能确定错误位置，因而不能纠正错误，只能发现错误。n第一种方案优越，但系统复杂，成本高，应用场合受限。第一
4、种方案优越，但系统复杂，成本高，应用场合受限。n第二种方案简单，容易实现，编译码速度快，通过重传纠正错误，常第二种方案简单，容易实现，编译码速度快，通过重传纠正错误，常用。用。6/3082 差错控制基本原理差错控制基本原理n为什么要在传输的数据单元中增加冗余码元呢？例：为什么要在传输的数据单元中增加冗余码元呢？例：n三位二进制码有八种不同组合，三位二进制码有八种不同组合，n000，001，010，011，100，101，110，111。n选择选择四种四种作为作为许用码组许用码组，用来传输信息；另四种作为，用来传输信息；另四种作为禁禁用码组用码组。发送。发送000，传输中变为，传输中变为001，
5、010或或100。就判。就判定发生了错误。变为定发生了错误。变为111禁用码组。也判定发生了错禁用码组。也判定发生了错误。不能发现两位错误。误。不能发现两位错误。n上述编码只能检测错误，不能纠正错误。收到上述编码只能检测错误，不能纠正错误。收到100，无，无法判定哪一位码发生错误造成的。法判定哪一位码发生错误造成的。000，110，101三三者错一位都可变为者错一位都可变为100。7/3082 差错控制基本原理差错控制基本原理n例例:选选两个许用码组两个许用码组，000，111，其余为禁用，其余为禁用码组。收端可以检测两位以下的错误，或纠正一码组。收端可以检测两位以下的错误，或纠正一位错误。位
6、错误。n当收到当收到100时，若认为只有一位错误，则可以纠时，若认为只有一位错误，则可以纠正为正为000。111任何一位错误都不可能变为任何一位错误都不可能变为100；若错码不超过两位，若错码不超过两位，两种两种可能：可能：000错一位变为错一位变为100，或者，或者111错两位变为错两位变为100，因而只能检错，因而只能检错不能纠错。不能纠错。8/308.3 差错控制编码差错控制编码n检错码：检错码：能在译码中发现错误的编码；能在译码中发现错误的编码；n纠错码：纠错码：在译码中不仅能发现错误还能自在译码中不仅能发现错误还能自动纠正错误的编码。动纠正错误的编码。0021aaann9/308.3
7、 差错控制编码差错控制编码n1 奇偶校验（奇偶校验（奇校验编码和偶校验编码）奇校验编码和偶校验编码）n偶校验编码：无论信息位有多少位，校验位只有一位，码偶校验编码：无论信息位有多少位，校验位只有一位，码组中组中“1”的个数为偶数，要满足关系式的个数为偶数，要满足关系式n n在收端，将码组中各位进行模在收端，将码组中各位进行模2加，结果为加，结果为“1”，有错误；，有错误；为为“0”，无错。，无错。n奇校验编码：码组中校验位只有一位，码组中奇校验编码：码组中校验位只有一位，码组中“1”的个数的个数为奇数，要满足关系式为奇数，要满足关系式n n两者的校验能力相同，只能检测出奇数个错误，不能检测两者
8、的校验能力相同，只能检测出奇数个错误，不能检测偶数个错误。偶数个错误。0021aaann1021aaann10/308.3 差错控制编码差错控制编码n（1）垂直奇偶校验垂直奇偶校验n（字符奇偶校验）在字（字符奇偶校验）在字符代码后面附加一奇偶符代码后面附加一奇偶校验位校验位，如图。如图。字符 012345678b0000000001b1000011110b2001100110b3010101011b4111111111b5111111111b6000000000b7偶011010010奇10010110111/308.3 差错控制编码差错控制编码n（2）垂直水平奇偶校验垂直水平奇偶校验n能检测
9、全部奇数个差错和大能检测全部奇数个差错和大部分偶数个差错。部分偶数个差错。n标出的差错能检测出来。标出的差错能检测出来。n标出的差错同时出现时则标出的差错同时出现时则检测不出来，即矩形差错检检测不出来，即矩形差错检测不出来。测不出来。n标出的错误可以得到纠正。标出的错误可以得到纠正。n实现容易，应用广泛。实现容易，应用广泛。12/308.3 差错控制编码差错控制编码n2 循环冗余校验码循环冗余校验码 (CRC码)n检错能力强，实现容易，应用广泛。检错能力强，实现容易，应用广泛。n从数学的角度讲，所有的数都可以用多项式来表示，从数学的角度讲，所有的数都可以用多项式来表示，n例如例如 n 125=
10、1102+2101+5100n 1，2，5 多项式的系数。多项式的系数。n二进制数二进制数10111，可表示为以，可表示为以x为基的多项式为基的多项式n x4+x2+x+1n系数对应着二进制数系数对应着二进制数10111。n长度为长度为n的二进制序列，与以的二进制序列，与以x为基的为基的n-1次多项式之间具次多项式之间具有一一对应的关系。有一一对应的关系。13/308.3 差错控制编码差错控制编码n 0 0 0 0 n=3:n 0 0 1 1n 0 1 0 xn 0 1 1 x+1n 1 0 0 x2n 1 0 1 x2+1n 1 1 0 x2+x n 1 1 1 x2+x+1n长度为长度为n
11、的码组可用一个的码组可用一个x的的n-1次多项式表示，码组中次多项式表示，码组中每位码的数值就是每位码的数值就是n-1次多项式中相应的系数值，这个对次多项式中相应的系数值，这个对应的多项式就称为应的多项式就称为数据多项式数据多项式。14/308.3 差错控制编码差错控制编码n原理：原理：n将发送数据比特序列作为多项式将发送数据比特序列作为多项式T(x)的系数，选定一的系数，选定一k次次幂的生成多项式幂的生成多项式G(x)。用。用x k乘乘T(x)，得，得T(x)xk。n然后用然后用G(x)去除去除T(x)xk,得一个余数多项式得一个余数多项式R(x)。将余数。将余数多项式加到数据多项式多项式加
12、到数据多项式T(x)之后，作为发送序列。之后，作为发送序列。n收端用同一收端用同一G(x)去除接收序列多项式去除接收序列多项式T(x)x k，得计算余得计算余数多项式数多项式R(x)。如果。如果R(x)与与R(x)相同，传输无错；否则相同，传输无错；否则传输有错。传输有错。)()()()()(xGxRxQxGxxTk15/308.3 差错控制编码差错控制编码n校验过程校验过程：a 发端，发端，T(x)乘以乘以xk.意味着将意味着将T(x)对应的数据比特对应的数据比特 序列左移序列左移K位。位。b T(x)xk 除以除以G(x),n Q(x Q(x)商，商，R(xR(x)余数多项式。余数多项式。
13、n c c 将将T(x)xT(x)xk k+R(x+R(x)所对应的比特序列作为一个整体发所对应的比特序列作为一个整体发 送发送。送发送。n d d 收端，对接收序列所对应的多项式收端，对接收序列所对应的多项式T(x)xT(x)xk k 进行运进行运算算)()()()()(xGxRxQxGxxTk16/308.3 差错控制编码差错控制编码n R(x)=R(x)，传输正确；，传输正确；R(x)R(x),传输有错。传输有错。n实际的实际的CRC校验码生成采用二进制模校验码生成采用二进制模2算法得到。算法得到。n加法不进位，减法不借位，即异或操作。加法不进位，减法不借位，即异或操作。n例例:na 发
14、送数据序列发送数据序列 110011；nb G(x)=x 4+x 3+1，k=4,对应的序列对应的序列 11001；nc 发送数据序列左移发送数据序列左移4位为位为 1100110000；nd 做除法做除法 )()()()()(xGxRxQxGxxTk17/308.3 差错控制编码差错控制编码n 1 0 0 1 1 0 0 0 0 T(x)x k n 1 1 0 0 1 n 1 0 0 0 0 n 1 1 0 0 1 n 1 0 0 1 R(x)ne 带有校验的发送序列带有校验的发送序列：n 110011 1001n 发序列发序列 校验序列校验序列nf 校验校验若没有发生差错，接收端收序列能被
15、同一生成多项若没有发生差错，接收端收序列能被同一生成多项序列整除序列整除18/308.3 差错控制编码差错控制编码n 1 0 0 0 0 1n 1 1 0 1）1 1 0 0 1 1 1 0 0 1n 1 1 0 0 1n 1 1 0 0 1n 1 1 0 0 1n 0n3 校验和校验和n也是基于冗余校验。也是基于冗余校验。n发端将数据单元分成长度为发端将数据单元分成长度为n（通常是（通常是16）的比特分段，）的比特分段，这些分段相加，其结果仍然为这些分段相加，其结果仍然为n比特长。比特长。n总和求反，作为校验字段附加到数据单元的末尾。总和求反，作为校验字段附加到数据单元的末尾。19/308.
16、3 差错控制编码差错控制编码n发端发端n数据单元分成数据单元分成k段，每段段，每段n比特；比特；n所有段相加求和；所有段相加求和；n对和取反得校验和；对和取反得校验和；n将校验字和段附加到数据单元末尾与数据一起发送。将校验字和段附加到数据单元末尾与数据一起发送。n收端收端n接收数据分成长度为接收数据分成长度为n比特的段；比特的段；n所有段相加求和；所有段相加求和；n对和取反；对和取反；n结果为结果为0，接收数据；否则拒绝。，接收数据；否则拒绝。n例例；发送发送16位数据位数据10101001 00111001，采用，采用8位校验和。位校验和。20/308.3 差错控制编码差错控制编码n解：将数
17、据按解：将数据按8位分段，相加求和位分段，相加求和n 1 0 1 0 1 0 0 1n +0 0 1 1 1 0 0 1n 1 1 1 0 0 0 1 0 和和 n求反求反 0 0 0 1 1 1 0 1 校验和校验和 n发送比特序列发送比特序列:10101001 00111001 00011101n 数据数据 校验和校验和n接收无差错，对其分段、求和、取反应为接收无差错，对其分段、求和、取反应为0。n分段求和分段求和n 1 0 1 0 1 0 0 1n 0 0 1 1 1 0 0 1n 和和 +0 0 0 1 1 1 0 1n 1 1 1 1 1 1 1 1n 取反取反 0 0 0 0 0
18、0 0 021/308.3 差错控制编码差错控制编码n结果为结果为0，传输正确。，传输正确。n若发生多位错误，如变为若发生多位错误，如变为10101111 11111001 00011101，红色红色的为错误位。三段相加的为错误位。三段相加 n 1 0 1 0 1 1 1 1n 1 1 1 1 1 0 0 1n +0 0 0 1 1 1 0 1 n 1 1 1 0 0 0 1 0 1n +1 进位进位 n 和和 1 1 0 0 0 1 1 0n 取反取反 0 0 1 1 1 0 0 1n结果不为结果不为0，传输错误，传输错误.n结论：结论：若两分段对应位具有相反值的错误，如变为若两分段对应位具
19、有相反值的错误，如变为00101001 10111001 00011101，红色红色的为错误位。三段相加的为错误位。三段相加22/308.3 差错控制编码差错控制编码n 0 0 1 0 1 0 0 1n 1 0 1 1 1 0 0 1n +0 0 0 1 1 1 0 1 n 1 1 1 1 1 1 1 1 和n取反取反 0 0 0 0 0 0 0 0 n结果为结果为0，不能检测这种错误。，不能检测这种错误。n校验和能检测所有奇数个错误以及大多数偶数个错误。校验和能检测所有奇数个错误以及大多数偶数个错误。n结论：结论：如果某一段中的一个或多个比特被破坏，并且在下一个分段如果某一段中的一个或多个比
20、特被破坏，并且在下一个分段中具有相反值的对应位也被破坏，这些列的和将不变，因此收方将中具有相反值的对应位也被破坏，这些列的和将不变，因此收方将检测不出这些错误。一个比特的反相被另一个分段对应位具有相反检测不出这些错误。一个比特的反相被另一个分段对应位具有相反值的比特反相所抵消，该差错是不可检测的。值的比特反相所抵消，该差错是不可检测的。23/308.4 差错控制方法差错控制方法 n1 前向纠错前向纠错(FEC)n 又称自动纠错，原理如图。又称自动纠错，原理如图。n优点：不需要反向信道，能用于单工通信，也可用于一优点：不需要反向信道，能用于单工通信，也可用于一 点对多点通信。点对多点通信。n 延
21、迟恒定，适用于实时通信系统。延迟恒定，适用于实时通信系统。n缺点：复杂，传输效率低。缺点：复杂，传输效率低。24/308.4 差错控制方法差错控制方法 n2 自动请求重发自动请求重发(ARQ)n也称反馈重发，原理如图。也称反馈重发，原理如图。n工作过程工作过程:n发端：发端：信源数据经编码器编码后，通过正向信道发送信源数据经编码器编码后，通过正向信道发送端。缓存以备重发。端。缓存以备重发。25/308.4 差错控制方法差错控制方法 n收端：收端：译码，检测判决。如无错，送出译码，检测判决。如无错，送出ACK。n n发端收到发端收到ACK后，重发控制器发指令给信源，进行下后，重发控制器发指令给信
22、源，进行下 一组数据的发送。一组数据的发送。n如译码检测有错，送如译码检测有错，送NAK，重发。，重发。n发端收到发端收到NAK后，重发控制器控制缓存器的数据进入编后，重发控制器控制缓存器的数据进入编码器进行编码重发，并禁止信源输入新的数据。码器进行编码重发，并禁止信源输入新的数据。26/308.4 差错控制方法差错控制方法 n方法：方法：n（1）停止等待方式）停止等待方式n每发送一个分组后，就停止等待应答信号。收到确认信每发送一个分组后，就停止等待应答信号。收到确认信号，就发下一个分组；收到否认信号，重发。号，就发下一个分组；收到否认信号，重发。n优点：优点：简单，所需缓冲区容量小。简单，所
23、需缓冲区容量小。n缺点：缺点：效率低，不宜高速或实时性要求高的场合。效率低，不宜高速或实时性要求高的场合。27/308.4 差错控制方法差错控制方法 （2）连续重发方式）连续重发方式n 可连续发送数据。发端收到可连续发送数据。发端收到NAK就退回到有错的码就退回到有错的码组，重发此码组及以后的码组。每个码组一个序号。组，重发此码组及以后的码组。每个码组一个序号。28/308.4 差错控制方法差错控制方法（3）选择重发方式）选择重发方式n发端仅重发接收出错的码组。发端仅重发接收出错的码组。n优点：系统效率高。优点：系统效率高。29/308.4 差错控制方法差错控制方法n3 FEC/ARQ混合方式
24、混合方式nFEC与ARQ的结合。30/308.4 差错控制方法差错控制方法4 交织方式交织方式n 把待发送数据序列按行排成一个把待发送数据序列按行排成一个m x n的矩阵，然后按列顺序传的矩阵，然后按列顺序传送。收端恢复原矩阵，而后按行进行译码。对于长度为送。收端恢复原矩阵，而后按行进行译码。对于长度为m的突发的突发错误，每行只分到错误，每行只分到个突发错误，即把长度为个突发错误，即把长度为m的错误分配到了的错误分配到了m行中。如果原来每行编码只能纠正单个随机错误，交织后就能纠正行中。如果原来每行编码只能纠正单个随机错误，交织后就能纠正长度为长度为m的突发错误；如果原来每行编码能纠正的突发错误；如果原来每行编码能纠正t个随机错误，交个随机错误，交织后则能纠正织后则能纠正tm的突发错误；如果原来每行编码能纠正长度为的突发错误；如果原来每行编码能纠正长度为的突发错误，交织后能纠正长度的突发错误，交织后能纠正长度m的突发错误。的突发错误。n 利用交织将码长扩大了利用交织将码长扩大了m倍，故把长为倍，故把长为m的突发错误分散到了的突发错误分散到了m个个n长码组中，使每行码组只有长度为长码组中，使每行码组只有长度为的突发错误，提高了抗突发的突发错误，提高了抗突发干扰能力。干扰能力。
