通信原理教程 第10章 差错控制原理.ppt

第第10章章 差错控制原理差错控制原理v信信道道中中噪噪声声和和干干扰扰的的存存在在，会会使使传传输输信信号号产产生生失失真真，引引起起误误差差。通通常常把把接接收收数数据据与与发发送送数数据据不不一一致致的的现现象象称称为为传传输输差差错错，简简称称为为差错差错。v为为了了提提高高信信息息传传输输的的可可靠靠性性，通通常常要要对对传传输输的的数数据据序序列列进进行行某某种种变变换换，使使原原来来互互不不相相关关的的数数据据序序列列码码元元产产生生某某种种规规律律性性，在在接收端根据这种规律性来检测或纠正传输过程中的错误。接收端根据这种规律性来检测或纠正传输过程中的错误。v不不同同的的变变换换方方法法就就形形成成了了不不同同的的编编码码，不不同同的的编编码码就就产产生生了了不不同的差错控制方法。同的差错控制方法。第第10章章 差错控制原理差错控制原理v10.1差错产生的原因及差错类型差错产生的原因及差错类型v干扰：干扰：脉冲干扰、随机噪声干扰、人为干扰等。脉冲干扰、随机噪声干扰、人为干扰等。v畸变畸变:传输线路本身性能的限制，也会使传输的信号波形畸变。传输线路本身性能的限制，也会使传输的信号波形畸变。v这些影响使接收信号产生差错。这些影响使接收信号产生差错。第第10章章 差错控制原理差错控制原理v噪声类型噪声类型：随机噪声和脉冲噪声。随机噪声和脉冲噪声。v随随机机噪噪声声的的特特点点：时时时时处处处处存存在在，幅幅度度较较小小，频频带带很很宽宽。这这类类噪噪声声引引起起的的差差错错出出现现的的位位置置是是随随机机的的、离离散散的的，前前后后差差错错之间没有什么联系或依赖关系，是一种随机独立差错。之间没有什么联系或依赖关系，是一种随机独立差错。v脉脉冲冲噪噪声声的的特特点点：强强度度大大，其其持持续续时时间间与与数数据据传传输输中中每每比比特特的的时时间间相相比比，可可能能较较长长，引引起起的的错错误误成成串串出出现现，即即无无错错则则已已，有错一片。是一种突发性差错。有错一片。是一种突发性差错。v混合差错：混合差错：随机噪声和脉冲噪声同时出现引起的差错。随机噪声和脉冲噪声同时出现引起的差错。第第10章章 差错控制原理差错控制原理v102差错控制基本原理差错控制基本原理v差差错错控控制制：允允许许在在通通信信过过程程中中产产生生差差错错的的前前提提下下，能能有有效效地地检检测测出出错错误误并并进进行行纠纠正正，从从而而提提高高通通信信质质量量，这这种种方方法法叫叫检检错错与与纠纠错错，统统称称为为差差错错控制。控制。v差错控制方案差错控制方案：v（1）纠纠错错编编码码：传传输输的的数数据据单单元元带带有有足足够够的的冗冗余余信信息息，在在接接收收端端发发现现并并自动纠正传输错误。自动纠正传输错误。v（2）检检错错编编码码：传传输输的的数数据据单单元元仅仅带带有有足足以以使使接接收收端端发发现现差差错错的的冗冗余余信信息，但不能确定错误位置，因而不能纠正错误，只能发现错误。息，但不能确定错误位置，因而不能纠正错误，只能发现错误。v特特点点：纠纠错错编编码码优优越越，但但系系统统复复杂杂，成成本本高高，应应用用场场合合受受限限。检检错错编编码码简单，容易实现，编译码速度快，通过重传纠正错误，常用。简单，容易实现，编译码速度快，通过重传纠正错误，常用。第第10章章 差错控制原理差错控制原理v编编码码产产生生冗冗余余码码元元，冗冗余余码码元元不不受受用用户户控控制制，最最终终也也不不传传送送给给接接收收用用户户，是是系系统统为为减减少少传传输输差差错错而而采采取取的的一一种种处处理理措措施施。信信道道传传输输速速率率一一定定时时，引引入入差差错错控控制制编编码码，降降低低了了用用户户数数据据的的传传输输速速率率。通通过过差差错错控控制制编编码码提提高高系系统统传传输输的的可可靠靠性性是是以以牺牺牲牲数数据据传传输输速速率率为为代代价价换换取取的的。为为什什么么要要在在传传输输数数据据单单元元中中增增加加冗冗余余码码元元呢呢？例例：3位位二二进进制制码码有有8种种不不同同组组合合：000，001，010，011，100，101，110，111。v选选择择4种种作作为为许许用用码码组组，用用来来传传输输信信息息；另另4种种作作为为禁禁用用码码组组。发发000，传传输中变为输中变为001，010，100或或111，就判定发生了错误。不能发现两位错误。，就判定发生了错误。不能发现两位错误。v上上述述编编码码只只能能检检测测错错误误，不不能能纠纠正正错错误误。收收到到100，无无法法判判定定哪哪一一位位发发生生错误造成的。错误造成的。000，110，101三者错一位都可变为三者错一位都可变为100。v选选000，111为为许许用用码码组组，其其余余为为禁禁用用码码组组。收收端端可可以以检检测测两两位位以以下下的的错错误误，或纠正一位错误。或纠正一位错误。第第10章章 差错控制原理差错控制原理v收收到到100，若若认认为为只只有有1位位错错误误，则则可可纠纠正正为为000。111任任何何一一位位错错误误都都不不可可能能变变为为100；若若错错码码不不超超过过两两位位，两两种种可可能能：000错错一一位位变变为为100，或或者者111错两位变为错两位变为100，因而只能检错不能纠纠错。，因而只能检错不能纠纠错。v103分组码的概念分组码的概念v分分组组码码：将将k个个信信息息码码元元划划分分为为一一组组，然然后后由由这这k个个码码元元按按照照一一定定的的规规则则产生产生r个监督码元，从而构成长度个监督码元，从而构成长度nkr的码组的集合。的码组的集合。v分分组组码码表表示示：（n，k），k是是分分组组码码中中信信息息码码位位长长度度，r是是码码组组中中监监督督码码位位长长度度，n n是是编编码码码码组组的的总总长长度度。监监督督码码元元仅仅监监督督本本码码组组中中的的信信息息码码元元。码码距距：两两个个等等长长二二进进制制码码组组之之间间对对应应位位不不同同的的个个数数，用用来来描描述述码码组组之之间间的不同程度，称为汉明（的不同程度，称为汉明（HammingHamming）距离，用距离，用d d表示：表示：第第10章章 差错控制原理差错控制原理v 分分别别为为第第j j个个码码组组和和第第k k个个码码组组的的第第i i位位码码元元；n n为为码码组组长长度度；表表示模示模2 2加。加。v例例:11101:11101与与1001110011之间的码距之间的码距d=3d=3。v最最小小码码距距：一一个个码码组组集集合合中中，任任何何两两个个码码组组间间汉汉明明距距离离的的最最小小值值称称为为该该集集合合的的最最小小码码距距。记记为为d0。码码组组集集合合（000，001，010，011，100，101，110，111），d0=1；码码组组集集合合（000，011，101，110），d0=2；码码组组集合（集合（000，111），），d0=3。v这三个码组集合中，码组集合（这三个码组集合中，码组集合（000，111）的差错控制能力是最强的。）的差错控制能力是最强的。v码组的最小距离越大，差错控制能力就越强。码组的最小距离越大，差错控制能力就越强。第第10章章 差错控制原理差错控制原理v104差错控制编码差错控制编码 v检错码：检错码：能在译码中发现错误的编码；能在译码中发现错误的编码；v纠错码：纠错码：在译码中不仅能发现错误还能自动纠正错误的编码。在译码中不仅能发现错误还能自动纠正错误的编码。v检检错错编编码码和和纠纠错错编编码码无无严严格格界界限限，有有的的纠纠错错编编码码可可用用来来检检错错，有有的的检检错错编码也可用作纠错。编码也可用作纠错。v常用差错控制编码：常用差错控制编码：奇偶校验码、恒比码、正反码、循环冗余校验码等。奇偶校验码、恒比码、正反码、循环冗余校验码等。v1 奇偶校验奇偶校验v（1）原理原理v分为：分为：奇校验编码和偶校验编码。奇校验编码和偶校验编码。v奇奇偶偶校校验验编编码码中中，无无论论信信息息位位有有多多少少位位，校校验验位位只只有有一一位位。码码组组中中“1”的个数为奇数或偶数。的个数为奇数或偶数。v奇校验编码，要满足关系式奇校验编码，要满足关系式第第10章章 差错控制原理差错控制原理v偶校验编码要满足关系式偶校验编码要满足关系式 v上两式中，上两式中，为校验位，其它位为信息位，为校验位，其它位为信息位，表示模表示模2加运算。加运算。v对对于于奇奇校校验验，在在接接收收端端，将将码码组组中中各各位位进进行行模模2加加，若若结结果果为为“1”，就就认认为为传传输输正正确确；若若为为“0”，就就认认为为传传输输有有错错。对对于于偶偶校校验验，在在接接收收端端，将将码码组组中中各各位位进进行行模模2加加，若若结结果果为为“0”，就就认认为为传传输输正正确确；若若为为“1”，就就认认为为传输有错传输有错。v两两者者的的校校验验能能力力相相同同，均均只只能能检检测测出出奇奇数数个个错错误误，对对出出现现的的偶偶数数个个错错误误检检测测不不出出来来。一一般般用用于于检检测测随随机机错错误误。国国际际标标准准化化组组织织ISO规规定定，异异步步传输系统采用偶校验编码方式，同步传输系统采用奇校验编码方式。传输系统采用偶校验编码方式，同步传输系统采用奇校验编码方式。第第10章章 差错控制原理差错控制原理v（2）垂直奇偶校验垂直奇偶校验v也称为字符奇偶校验，在字符代码后面附加一奇偶校验位也称为字符奇偶校验，在字符代码后面附加一奇偶校验位，如图。如图。字符字符012345678b0000000001b1000011110b2001100110b3010101011b4111111111b5111111111b6000000000b7偶偶011010010奇奇100101101第第10章章 差错控制原理差错控制原理v（3）垂直水平奇偶校验垂直水平奇偶校验v也也称称二二维维奇奇偶偶校校验验或或方方阵阵校校验验。该该校校验验方方式式把把信信息息码码组组排排列列成成矩矩阵阵，每每一一码码组组写写成成一一行行，然然后后根根据据奇奇偶偶校校验验原原理理，在在垂垂直直和和水水平平两两个个方方向向同同时时进进行行校验。水平虚线下一行和垂直虚线右一列为校验位校验。水平虚线下一行和垂直虚线右一列为校验位v能检测全部奇数个差错和大部分能检测全部奇数个差错和大部分v偶数个差错。偶数个差错。标出的差错能检标出的差错能检v测出来，测出来，标出的差错同时出现标出的差错同时出现v时则检测不出来，即矩形差错检时则检测不出来，即矩形差错检v测不出来。测不出来。v实现容易，应用广泛。实现容易，应用广泛。第第10章章 差错控制原理差错控制原理v2.恒比码恒比码v“1”的的个个数数与与“0”的的个个数数保保持持不不变变，故故由由此此得得名名。接接收收端端译译码码时时只只需需计计算算接接收收码码组组中中“1”的的个个数数，就就可可以以知知道道传传输输过过程程中中是是否否出出现现了了错错误误。可以检测所有奇数个错误和部分偶数个错误。可以检测所有奇数个错误和部分偶数个错误。5中取中取3恒比码如表。恒比码如表。v优点：简单，实现容易。优点：简单，实现容易。字符字符恒比码恒比码字符字符恒比码恒比码101011610101211001711100310110801110411010910011500111001101第第10章章 差错控制原理差错控制原理v3.正反码正反码 v正正反反码码监监督督码码元元取取决决于于信信息息码码组组中中“1”的的数数目目，或或者者与与信信息息码码元元相相同同（正正码），或者与信息码元相反（反码）。码），或者与信息码元相反（反码）。v以以博博多多码码为为例例，编编码码规规则则：信信息息码码组组中中有有奇奇数数个个“1”时时，监监督督码码与与信信息息码码相相同同；信信息息码码有有偶偶数数个个“1”时时监监督督码码是是信信息息码码的的反反码码。例例如如，信信息息码码为为11001，有有奇奇数数个个“1”，则则监监督督码码亦亦为为11001，发发送送码码组组为为1100111001；信信息息码码为为11101，有有偶偶数数个个“1”，则则监监督督码码为为信信息息码码的的反反码码00010，发发送送码码组组为为1100100010。v接接收收端端将将接接收收的的码码组组中中的的信信息息码码与与监监督督码码模模2加加，得得到到一一个个5单单位位的的合合成成码码组组，由由其其产产生生校校验验码码组组。接接收收码码组组中中的的信信息息码码有有奇奇数数个个“1”，合合成成码码组组就就是是校校验验码码组组；接接收收码码组组中中的的信信息息码码有有偶偶数数个个“1”，合合成成码码组组取取反反为为校校验验码组。根据校验码组中码组。根据校验码组中“1”的数目按下表进行译码判决。的数目按下表进行译码判决。v这种编码方式能纠正这种编码方式能纠正1位错误。位错误。第第10章章 差错控制原理差错控制原理v【例例】接接收收码码组组：0110101101、0101010111、0111010110，判判断断传传输输是是否有错。否有错。v解：解：v1)接接收收码码组组0110101101，信信息息码码中中“1”个个数数为为奇奇数数（3个个），合合成成码码组组为为00000，校验码组亦为，校验码组亦为00000，符合表，符合表中中第第1种类型情况，传输正确。种类型情况，传输正确。类型类型校验码组形式校验码组形式译码判决译码判决1全全“0”传输正确传输正确24个个“1”，1个个“0”校验码中校验码中“0”对应位置的对应位置的1位信息码出错位信息码出错34个个“0”，1个个“1”校验码中校验码中“1”对应位置的对应位置的1位监督码出错位监督码出错4其他其他大于大于1位的传输错误位的传输错误第第10章章 差错控制原理差错控制原理v2)接接收收码码组组0101010111，信信息息码码中中“1”个个数数为为偶偶数数（2个个），合合成成码码组组为为11101，合合成成码码组组取取反反，得得校校验验码码组组00010，符符合合表表中中第第3种种类类型型情情况况，第第4个监督码位出错。个监督码位出错。v3）接接收收码码组组0111010110，信信息息码码中中“1”个个数数为为奇奇数数（3个个），合合成成码码组组为为11000，校校验验码码组组亦亦为为11000，符符合合表表中中第第4种种类类型型情情况况，传传输输产产生生了了多多位位错误。错误。第第10章章 差错控制原理差错控制原理v4.循环冗余校验编码循环冗余校验编码v又称又称CRC码，检错能力强，实现容易，应用广泛。码，检错能力强，实现容易，应用广泛。v从数学的角度讲，所有的数都可以用多项式来表示，例如从数学的角度讲，所有的数都可以用多项式来表示，例如v125=1102+2101+5100v1，2，5为多项式的系数。为多项式的系数。v二进制数二进制数10111，可表示为以，可表示为以x为基的多项式为基的多项式v x4+x2+x+1v系数对应着二进制数系数对应着二进制数10111。v长度为长度为n的二进制序列，与以的二进制序列，与以x为基的为基的n-1次多项式之间具有一一对应的关系。次多项式之间具有一一对应的关系。第第10章章 差错控制原理差错控制原理vn=3:0000v0011v010 xv011 x+1v100 x2v101 x2+1v110 x2+xv111 x2+x+1v长长度度为为n的的码码组组可可用用一一个个x的的n-1次次多多项项式式表表示示，码码组组中中每每位位码码的的数数值值就就是是n-1次多项式中相应的系数值，这个对应多项式称为次多项式中相应的系数值，这个对应多项式称为数据多项式数据多项式。第第10章章 差错控制原理差错控制原理v原理：原理：v将将发发送送数数据据比比特特序序列列作作为为多多项项式式T(x)的的系系数数，选选一一k次次幂幂生生成成多多项项式式G(x)。用用xk乘乘T(x)，得得T(x)x k。然然后后用用G(x)去去除除T(x)x k,得得一一个个余余数数多多项项式式R(x)。将将余余数数多多项项式式加加到到数数据据多多项项式式T(x)之之后后，作作为为发发送送序序列列。收收端端用用同同一一G(x)去去除除接接收收序序列列多多项项式式T(x)xk，得得计计算算余余数数多多项项式式R(x)。若若R(x)与与R(x)相相同同，传输无错；否则传输有错。传输无错；否则传输有错。v校验过程校验过程：a.发端，发端，T(x)乘以乘以xk.意味着将意味着将T(x)对应的数据比特序列左移对应的数据比特序列左移k位。位。b.T(x)xk除以除以G(x),vQ(x)商，商，R(x)余数多项式。余数多项式。vc.将将T(x)xk+R(x)所对应的比特序列作为一个整体发送发送。所对应的比特序列作为一个整体发送发送。vd.收端，对接收序列所对应的多项式收端，对接收序列所对应的多项式T(x)xk进行运算进行运算第第10章章 差错控制原理差错控制原理vR(x)=R(x)，传输正确；传输正确；R(x)R(x),传输有错。传输有错。v实际的实际的CRC校验码生成采用二进制模校验码生成采用二进制模2算法得到。加法不进位，减法不借算法得到。加法不进位，减法不借位，即异或操作。位，即异或操作。v例例:va.发送数据序列发送数据序列110011；vb.G(x)=x4+x3+1，k=4,对应的序列对应的序列11001；vc.发送数据序列左移发送数据序列左移4位为位为1100110000；vd.做除法做除法 第第10章章 差错控制原理差错控制原理v 100001Q（x）vG(x)-11001）1100110000T(x)x kv11001v10000v11001v1001R(x)ve.带有校验的发送序列带有校验的发送序列：v1100111001v发序列发序列校验序列校验序列vf.校验校验，若没有发生差错，接收端收序列能被同一生成多项序列整除，若没有发生差错，接收端收序列能被同一生成多项序列整除第第10章章 差错控制原理差错控制原理vv100001v1101）1100111001v11001v11001v11001v0v5.校验和校验和v也是基于冗余校验。也是基于冗余校验。v将将发发端端数数据据单单元元分分成成长长度度为为n（通通常常是是16）的的比比特特分分段段，这这些些分分段段相相加加，其结果仍然为其结果仍然为n比特长。总和求反，作为校验字段附加到数据单元末尾。比特长。总和求反，作为校验字段附加到数据单元末尾。v过程：过程：第第10章章 差错控制原理差错控制原理v发端发端vl数据单元分成数据单元分成k段，每段段，每段n比特；比特；vl所有段相加求和；所有段相加求和；vl对和取反得校验和；对和取反得校验和；vl将校验字和段附加到数据单元末尾与数据一起发送。将校验字和段附加到数据单元末尾与数据一起发送。v收端收端vl接收数据分成长度为接收数据分成长度为n比特的段；比特的段；vl所有段相加求和；所有段相加求和；vl对和取反；对和取反；vl结果为结果为0，接收数据；否则拒绝。，接收数据；否则拒绝。v例例；发送数据；发送数据1010100100111001，采用，采用8位校验和位校验和。第第10章章 差错控制原理差错控制原理v解：按解：按8位分段，相加求和位分段，相加求和v10101001v+00111001v11100010和和v求反求反00011101校验和校验和v发送比特序列发送比特序列:101010010011100100011101v数据数据校验和校验和v若接收无错，对其分段、求和、取反应为若接收无错，对其分段、求和、取反应为0。v分段求和分段求和v10101001v00111001v和和+00011101v11111111v取反取反00000000第第10章章 差错控制原理差错控制原理v结果为结果为0，传输正确。，传输正确。v若发生多位错误，如变为若发生多位错误，如变为101011111111100100011101，红色红色的为错误位。的为错误位。三段相加三段相加v10101111v11111001v+00011101v111000101v+1进位进位v和和11000110v取反取反00111001v结果不为结果不为0，传输错误，传输错误.v结结论论：若若两两分分段段对对应应位位具具有有相相反反值值的的错错误误，如如变变为为001010011011100100011101，红色红色的为错误位。三段相加的为错误位。三段相加第第10章章 差错控制原理差错控制原理v00101001v10111001v+00011101v11111111和和v取反取反00000000v结果为结果为0，不能检测这种错误。，不能检测这种错误。v校验和能检测所有奇数个错误以及大多数偶数个错误。校验和能检测所有奇数个错误以及大多数偶数个错误。v结结论论：如如果果某某段段中中的的一一个个或或多多个个比比特特被被破破坏坏，并并且且在在下下一一分分段段中中具具有有相相反反值值的的对对应应位位也也被被破破坏坏，这这些些列列的的和和将将不不变变，收收方方将将检检测测不不出出这这些些错错误误。一一个个比比特特的的反反相相被被另另一一分分段段对对应应位位具具有有相相反反值值的的比比特特反反相相所所抵抵消消，该该差差错错是是不可检测的。不可检测的。第第10章章 差错控制原理差错控制原理v6.卷积码卷积码v卷卷积积码码是是一一种种非非分分组组码码，编编码码器器产产生生的的n个个码码元元，不不仅仅取取决决于于这这k位位信信息息码码元元，而而且且还还取取决决于于前前m1个个码码组组。编编码码器器的的输输出出可可以以看看成成是是输输入入信信息息比比特特与编码器响应函数的卷积，故称为卷积码。与编码器响应函数的卷积，故称为卷积码。v卷积码构造简单，性能优越，主要应用于前向纠错（卷积码构造简单，性能优越，主要应用于前向纠错（FEC）。）。v（1）编码编码v符符号号（n n，k,k,，m m），n n为为码码长长，k k为为码码组组中中信信息息位位长长度度，m m为为相相互互关关联联的的码码组组个数。举例说明。个数。举例说明。2v每每输输入入一一个个信信息息位位bi，移移位位寄寄存存器器右右移移一一位位。逻逻辑辑运运算算输输出出为为监监督督位位，紧紧跟跟此此信信息息位位之之后后。监监督督位位由由移移位位寄寄存存器器的的信信息息位位6，3，2，1模模2加加形形成成的的。该该卷卷积积码码的的参参数数为为k1，n2，m6，约约束束长长度度nm12。监监督督位位分分别别插插入在信息位之间的。入在信息位之间的。v v（2)卷积码的图解表示卷积码的图解表示v1)1)树状图树状图v（2 2，1 1，3 3）卷积码编码器。卷积码编码器。第第10章章 差错控制原理差错控制原理第第10章章 差错控制原理差错控制原理vm1，m2为为移移位位寄寄存存器器，起起始始状状态态均均为为0，即即b1b2b3为为000。c1,c2与与b1b2b3之之间的关系为：间的关系为：v c1b1b2b3vc2b1b3vb1输输入入信信息息位位，b2b3移移位位寄寄存存器器存存储储的的以以前前的的信信息息位位。表表中中给给出出了了该该编编码码器器的的状状态态。当当第第1个个信信息息位位为为1时时，即即b11，因因b3b200，故故输输出出c1c211；当当第第2个个信信息息位位仍仍为为1，这这时时b11，b3b201，c1c201，依依此此类类推推。为为保保证证输输入入的的全全部部信信息息位位11010都都能能通通过过移移位位寄寄存存器器，须须在在信信息息位位后后加加3个个0。b111010000b3b20001111001100000c1c21101010010110000状态状态abdcbcaa第第10章章 差错控制原理差错控制原理v仍仍用用a,b,c,d表表示示b3b2的的4种种可可能能状状态态。树树状状图图的的每每一一分分支支代代表表一一位位信信息息比比特特。通通常常规规定定：上上分分支支与与输输入入0相相对对应应，下下分分支支与与输输入入1相相对对应应。存存储储器器初初始始状状态态为为全全0。当当输输入入第第1个个比比特特b1=0时时，输输出出比比特特c1c2=00；b1=1，则则c1c2=11。从从a点点出出发发，b1=0取取上上支支路路；b1=1取取下下支支路路。输输入入第第2个个比比特特时时，移移位位寄寄存存器器右右移移一一位位，根根据据第第一一个个输输入入比比特特的的不不同同，a表表示示b3b2=00，b表表示示b3b2=01，c表表示示b3b2=10，d表表示示b3b2=11。再再输输入入1个个比比特特，随随移移位位寄寄存存器器和和输输入入比比特特的的不不同同，树树状状图图分分成成4条条支支路路。上上支支路路对对应应输输入入0，下下支支路路对对应应于于输输入入1，如如此此继继续续，可可得得树树状状图图。树树状状图图的的每每条条树树叉叉所所标标明明的的码码元元为为输输出出比比特特,每每个个节节点点标标注注的的a，b，c，d为为移移位位寄寄存存器器（b3b2）的的状状态态。从从第第4级级支支路路开开始始树树状状图图开开始始重重复复，上上半半部部与与下下半半部部相相同同。表表明明从从第第4位位输输入入开开始始输输出出码码元元已已与与第第1位位输输入入无无关关，这这正正说说明明（2，1，3）卷卷积积码码的的约约束束长长度度为为nm=23=6的的含含义义。当当输输入入序序列列为为11010时时，树树状状图图上上虚虚线标出了它的轨迹，输出序列为线标出了它的轨迹，输出序列为11010100，结果与上表完全一致。，结果与上表完全一致。第第10章章 差错控制原理差错控制原理v2）网格图网格图v网网格格图图把把树树状状图图中中相相同同的的节节点点合合并并在在一一起起，输输入入比比特特0，用用实实线线表表示示；输输入入比比特特1，用用虚虚线线表表示示。支支路路上上标标注注的的码码元元为为输输出出比比特特，自自上上而而下下4行行节节点点分分别表示别表示a，b，c，d四种状态。四种状态。第第10章章 差错控制原理差错控制原理第第10章章 差错控制原理差错控制原理v【例例】（2，1，3）卷卷积积码码编编码码器器，起起始始状状态态为为a，输输入入比比特特序序列列为为110100，求输出序列和状态变化路径。，求输出序列和状态变化路径。v解解：由由（2 2，1 1，3 3）卷卷积积码码网网格格图图，找找出出编编码码时时网网格格图图中中的的路路径径，可可得得到到输输出序列和状态变化路径。出序列和状态变化路径。第第10章章 差错控制原理差错控制原理v（3）译码译码 v方法：方法：代数解码和概率解码。代数解码和概率解码。v代数解码利用编码本身的代数结构进行译码，不考虑信道的统计特性。代数解码利用编码本身的代数结构进行译码，不考虑信道的统计特性。v概率译码在计算时要利用信道的统计特性。概率译码在计算时要利用信道的统计特性。v门限译码（门限译码（代数译码）对于约束长度较短的卷积码非常有效，设备简单。代数译码）对于约束长度较短的卷积码非常有效，设备简单。v概概率率译译码码目目前前已已成成为为卷卷积积码码最最主主要要的的译译码码方方法法，一一种种比比较较实实用用的的概概率率译译码码维特比译码维特比译码。v1967年年维维特特比比（Viterbi）提提出出的的一一种种译译码码算算法法，简简称称为为VB算算法法，是是对对最最大大似似然然算算法法的的一一种种改改进进。最最大大似似然然算算法法的的基基本本思思想想：把把接接收收序序列列与与所所有有可可能能的的发发送送序序列列比比较较，选选择择一一种种码码距距最最小小的的序序列列作作为为发发送送序序列列。如如果果发发送送一一个个k比比特特序序列列，则则有有2k种种可可能能的的组组合合，计计算算机机应应存存储储这这些些序序列列组组合合，以以便便用用作作比比较较。k较较大大时时，存存储储量量和和计计算算量量就就很很大大，实实现现困困难难。VB算算法法不不是是一一次次比比较较网网格格图图上上所所有有序序列列，而而是是根根据据网网格格图图每每接接收收一一段段就就比比较较一一段段，然然后后挑挑选选并并存存储储码码距距最最小小的的路路径径，最最后后选选择择出出的的路路径径所所对对应应的的序序列列即即为为译译码码器器的的输输出序列。举例说明。出序列。举例说明。第第10章章 差错控制原理差错控制原理v发发送送序序列列11010，为为使使全全部部数数据据通通过过编编码码器器，发发送送序序列列后后加加3个个0，编编码码器器的的输输入入序序列列变变为为11010000。由由前前表表知知，编编码码器器输输出出序序列列为为1101010010110000，移移位位寄寄存存器器的的状状态态转转移移为为abdcbcaa，最最后后回回到到a。如如果果接接收序列有差错，例如变为收序列有差错，例如变为0101011010010001。对照网格图来说明译码过程。对照网格图来说明译码过程。v长长度度为为6，可可选选前前3段段6位位码码的的接接收收序序列列010101作作为为计计算算标标准准。如如果果把把网网格格图图的的起起点点作作为为0级级，则则6位位码码正正好好到到达达第第3级级的的4个个节节点点。由由网网格格图图看看出出，从从0级级起起点点到到第第3级级的的4个个节节点点一一共共有有8条条路路径径。到到达达第第3级级节节点点a的的路路径径有有两两条条：000000和和111011，它它们们与与010101之之间间的的码码距距分分别别为为3和和4，码码距距较较小小的的路路径径称称为为幸幸存存路路径径，保保留留下下来来。同同理理，到到达达第第3级级节节点点b的的两两条条路路径径是是000011和和111000，它它们们与与010101之之间间的的码码距距也也分分别别是是3和和4；到到达达第第3级级节节点点c的的两两条条路路径径是是001110和和110101，它它们们与与010101之之间间的的码码距距分分别别是是4和和1；到到达达第第3级级节节点点d的的两两条条路路径径是是001101和和110110，它它们们与与010101之之间间的的码码距距分分别别是是2和和3。每每个个节节点点各各选选择择一一条条幸幸存存路路径径，分分别别是是000000，000011，110101，001101，它它们们与与010101之之间间的的码码距距分分别别3，3，1，2，这这些些分分别别是是到到达达第第3级级节节点点a，b，c，d的的4条路径。条路径。第第10章章 差错控制原理差错控制原理v到到第第4级级有有8条条路路径径。到到a的的两两条条是是00000000和和11010111，与与接接收收序序列列01010110的的码码距距分分别别是是4和和2，11010111为为幸幸存存路路径径。到到b的的两两条条是是00000011和和11010100；到到c的的两两条条是是00001110和和00110101；到到d的的两两条条是是00110110和和00001101。幸幸存存路路径径分分别别是是11010111，11010100，00001110，00110110。到到第第7级级，到到终终点点a只只能能从从a和和c出出发发。这这样样就就得得到到了了一一条条到到达达终终点点的的幸幸存存路路径径（译码路径）。译码序列为（译码路径）。译码序列为11010000，与发送数据序列一致。，与发送数据序列一致。第第10章章 差错控制原理差错控制原理v10.5差错控制方法差错控制方法v差错控制的目的：通过相应的手段发现传输过程中的错误并加以纠正。差错控制的目的：通过相应的手段发现传输过程中的错误并加以纠正。v1.前向纠错前向纠错v前向纠错前向纠错(FEC)又称自动纠错。又称自动纠错。v发发送送端端对对信信源源数数据据进进行行纠纠错错编编码码，送送信信道道传传输输。接接收收端端对对信信号号译译码码过过程程能能检测传输中产生的错误，并自动加以纠正。检测传输中产生的错误，并自动加以纠正。v优优点点：不不需需要要反反向向信信道道，能能用用于于单单工工通通信信和和一一点点对对多多点点通通信信。译译码码延延迟迟恒恒定，适用于实时通信系统。定，适用于实时通信系统。v缺缺点点：译译码码设设备备复复杂杂，为为了了纠纠正正较较多多的的错错误误，需需要要附附加加较较多多的的冗冗余余码码元元，传输效率低。传输效率低。第第10章章 差错控制原理差错控制原理v2.自动请求重发自动请求重发 v自自动动请请求求重重发发(ARQ)方方法法用用于于检检错错编编码码。接接收收端端通通过过译译码码能能发发现现传传输输错错误误，但但不不知知道道错错误误的的具具体体位位置置，无无法法纠纠正正，采采用用自自动动请请求求重重发发工工作作方方式式。自自动动请求重发也称请求重发也称反馈重发反馈重发。v接接收收端端检检测测传传输输过过程程中中有有无无错错误误，把把检检测测结结果果通通过过反反向向信信道道通通知知发发送送端端。发发送送端端根根据据反反馈馈信信息息把把接接收收端端检检测测判判决决有有错错误误的的数数据据重重发发一一次次。如如果果重重发发数据仍有错，再次重发，直至正确为止。数据仍有错，再次重发，直至正确为止。第第10章章 差错控制原理差错控制原理v编编码码信信号号通通过过正正向向信信道道传传送送到到，与与此此同同时时，还还将将信信源源数数据据送送缓缓存存器器缓缓存存，以备重发。以备重发。v接接收收端端译译码码，检检测测判判决决。如如无无错错，重重发发判判决决器器经经反反向向信信道道送送出出确确认认信信号号ACK，可发下一组数据。可发下一组数据。v发发送送端端收收到到确确认认信信号号后后，重重发发控控制制器器发发指指令令给给信信源源，发发送送下下一一组组数数据据的的。如如译译码码检检测测发发现现有有错错，重重发发判判决决器器经经反反向向信信道道送送出出否否认认信信号号NAK，要要求求重重发发。发发送送端端收收到到NAK后后，重重发发控控制制器器控控制制缓缓存存器器的的数数据据进进入入编编码码器器进进行行编编码码重重发发，并并禁禁止止信信源源输输入入新新的的数数据据。如如接接收收端端译译码码器器检检测测收收到到的的重重发发数数据据仍有错，再重复上过程，直至正确为止。仍有错，再重复上过程，直至正确为止。v自动请求重发纠错的三种方式。自动请求重发纠错的三种方式。v1)停止停止-等待方式等待方式v停停止止-等等待待方方式式是是最最简简单单的的ARQ方方式式。每每发发送送一一个个数数据据分分组组后后，停停止止等等待待接接收收端端的的应应答答信信号号。收收到到确确认认信信号号，发发送送下下一一数数据据分分组组；收收到到否否认认信信号号，重发原数据分组。重发原数据分组。第第10章章 差错控制原理差错控制原理v优点：工作简单，仅需半双工工作，所需缓冲区容量小。优点：工作简单，仅需半双工工作，所需缓冲区容量小。v缺缺点点：等等待待应应答答要要花花费费时时间间，传传输输效效率率低低，高高速速传传输输系系统统或或实实时时性性要要求求高的场合不宜采用此方式。高的场合不宜采用此方式。v2)2)连续重发方式连续重发方式 v可可以以连连续续向向接接收收端端发发送送数数据据，接接收收端端根根据据校校验验结结果果发发回回应应答答信信号号。发发送送端端收收到到否否认认信信号号就就退退回回到到有有错错的的数数据据分分组组，重重发发此此分分组组及及以以后后的的分分组组。接接收收端端丢丢弃弃错错误误的的分分组组以以及及所所有有后后来来收收到到的的分分组组，直直到到错错误误的的分分组组被被正正确接收为止。确接收为止。v优点：优点：当通信性能好，传输错误较少时，该方式传输效率高。当通信性能好，传输错误较少时，该方式传输效率高。v缺点：缺点：缓存器容量要大。缓存器容量要大。第第10章章 差错控制原理差错控制原理v3)选择重发方式选择重发方式 v仅重发出错的分组。仅重发出错的分组。第第10章章 差错控制原理差错控制原理v选选