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