第7章数据传输

1、第第7章章 数据传输数据传输第第7章章 数据传输数据传输第第7章章 数据传输数据传输7.1 纠错与线性分组码的编码原则纠错与线性分组码的编码原则1、纠错、纠错信道编码信道编码通过在发送端增加冗余使消息出现传输错误时由通过在发送端增加冗余使消息出现传输错误时由接收端进行纠正接收端进行纠正纠错纠错第第7章章 数据传输数据传输2、n重复码重复码99. 001. 001. 099. 0)X/Y(P)X/Y(PX/Y1：二元对称信道例求信源等概率时的平均译码错误概率求信源等概率时的平均译码错误概率第第7章章 数据传输数据传输最大似然准则译码最大似然准则译码收到收到y1时时11i1i1x*x)y( f2

2、, 1i99. 001. 0 ,99. 0max)x/y(Pmax*)x/y(P22i2i2x*x)y( f2 , 1i99. 099. 0 ,01. 0max)x/y(Pmax*)x/y(P收到收到y2时时第第7章章 数据传输数据传输平均译码错误概率平均译码错误概率01. 0)01. 001. 0 (21)x/y(P)x(P)x/y(P)x(P)x/y(P)x(PP212121*xx21jijiei 通信系统中一般要求平均译码错误概率的数量级通信系统中一般要求平均译码错误概率的数量级10-6 -10-9第第7章章 数据传输数据传输三重复码三重复码消息重复三次消息重复三次x1=0c1=000，

3、x2=1c2=111三次扩展信源的子信源，三次扩三次扩展信源的子信源，三次扩展信宿展信宿三次扩展信道的子信道三次扩展信道的子信道9703. 00098. 00098. 0000099. 00098. 0000099. 0000099. 0000001. 0000001. 0000099. 0000099. 00098. 0000099. 00098. 00098. 09703. 0)X/Y(P331第第7章章 数据传输数据传输最大似然准则译码最大似然准则译码收到收到y1=000时时000c*c)000( f2 , 1i9703. 0000001. 0 ,9703. 0max)c/000(Pma

4、x*)c/000(P1ii收到收到y2=001时时000c*c)001( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/001(Pmax*)c/001(P1ii第第7章章 数据传输数据传输收到收到y3=010时时000c*c)010( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/010(Pmax*)c/010(P1ii收到收到y4=011时时111c*c)011( f2 , 1i0098. 00098. 0 ,000099. 0max)c/011(Pmax*)c/011(P2ii收到收到y5=100时时000c*c)100( f2

5、, 1i0098. 0000099. 0 ,0098. 0max)c/100(Pmax*)c/100(P1ii第第7章章 数据传输数据传输收到收到y6=101时时111c*c)101( f2 , 1i0098. 00098. 0 ,000099. 0max)c/101(Pmax*)c/101(P2ii收到收到y7=110时时111c*c)110( f2 , 1i0098. 00098. 0 ,000099. 0max)c/110(Pmax*)c/110(P2ii收到收到y8=111时时111c*c)111( f2 , 1i9703. 09703. 0 ,000001. 0max)c/111(P

6、max*)c/111(P2ii第第7章章 数据传输数据传输三重复码三重复码通过在发送端增加冗余使消息出现一通过在发送端增加冗余使消息出现一位传输错误时由接收端进行纠正位传输错误时由接收端进行纠正纠错纠错000)100( f000)010( f000)001( f000)000( f111)111( f111)110( f111)101( f111)011( f第第7章章 数据传输数据传输平均译码错误概率平均译码错误概率4181716141252322212103)000099. 06000001. 02(21)c/y(P)c/y(P)c/y(P)c/y(P)c (P)c/y(P)c/y(P)c

7、/y(P)c/y(P)c (P*cc81jijiei)c/y(P)c (PP第第7章章 数据传输数据传输重复重复n次次n重复码重复码10e8e7e5e105P11n10P9n104P7n10P5n，n重复码的码长为原来的重复码的码长为原来的n倍倍编码效率为编码效率为1/n第第7章章 数据传输数据传输需要找的需要找的“好码好码”足够小的平均译码错误概率足够小的平均译码错误概率Pe较高的编码效率较高的编码效率第第7章章 数据传输数据传输3、线性分组码及其编码原则、线性分组码及其编码原则线性分组码线性分组码具有恒定码字长度和消息长度，消息相加后的编具有恒定码字长度和消息长度，消息相加后的编码等同于各

8、自编码相加的纠错码，用码等同于各自编码相加的纠错码，用(n,k)表示表示其中其中n为码字长度，为码字长度，k为消息长度，为消息长度，n-k为校验长度为校验长度第第7章章 数据传输数据传输例例2：(4,3)偶校验码偶校验码0110c011x0101c010 x0011c001x0000c000 x443322111111c111x1100c110 x1010c101x1001c100 x88776655100110100011cc1001100101001xx6262第第7章章 数据传输数据传输码距和最小码距码距和最小码距2k个码字构成的码表中，任意两个码字之间的码距个码字构成的码表中，任意两个

9、码字之间的码距(汉明距离汉明距离)任意两个码字对应位上不同码元的任意两个码字对应位上不同码元的个数，用个数，用dij表示表示ji ,2 , 2 , 1j , icc)c ,c (ddkn1ljijiijll第第7章章 数据传输数据传输例例3：(4,3)偶校验码中码字偶校验码中码字c2和和c3之间的码距之间的码距d230101c0011c322ccd41l3223ll第第7章章 数据传输数据传输2k个码字构成的码表中，码字之间的最小码距个码字构成的码表中，码字之间的最小码距所有码字之间码距的最小值，用所有码字之间码距的最小值，用dmin表示表示ji ,2 , 2 , 1j , idmindkij

10、j , imin第第7章章 数据传输数据传输线性分组码的编码原则线性分组码的编码原则例例4：(3,1)线性分组码线性分组码三次扩展信源中三次扩展信源中8个可能的码字个可能的码字111c011c110c010c101c001c100c000c84736251第第7章章 数据传输数据传输8个可能的码字构成的码表中，任意两个码字之间个可能的码字构成的码表中，任意两个码字之间的码距的码距1dddddddddddd8786756584734362425131212dddddddddddd7685746483538252327161413dddd54637281第第7章章 数据传输数据传输如果选取其中如果

11、选取其中c1=000，c8=111为许用码，其余为禁为许用码，其余为禁用码用码三重复码三重复码2个码字构成的码表中个码字构成的码表中3dmind81min99. 001. 001. 099. 0)X/Y(P及信源等概率条件下的平均译码错误概率及信源等概率条件下的平均译码错误概率在信道在信道4e103P第第7章章 数据传输数据传输如果选取其中如果选取其中c2=001，c7=110为许用码，其余为禁为许用码，其余为禁用码用码2个码字构成的码表中个码字构成的码表中3dmind27min99. 001. 001. 099. 0)X/Y(P及信源等概率条件下及信源等概率条件下在信道在信道第第7章章 数据

12、传输数据传输x=0c2=001，x=1c7=110三次扩展信源的子三次扩展信源的子信源，三次扩展信宿信源，三次扩展信宿三次扩展信道的子信道三次扩展信道的子信道0098. 09703. 0000099. 00098. 0000099. 00098. 0000001. 0000099. 0000099. 0000001. 00098. 0000099. 00098. 0000099. 09703. 00098. 0)X/Y(P332第第7章章 数据传输数据传输最大似然准则译码最大似然准则译码收到收到y1=000时时001c*c)000( f2 , 1i0098. 0000099. 0 ,0098.

13、 0max)c/000(Pmax*)c/000(P2ii收到收到y2=001时时001c*c)001( f2 , 1i9703. 0000001. 0 ,9703. 0max)c/001(Pmax*)c/001(P2ii第第7章章 数据传输数据传输收到收到y3=010时时110c*c)010( f2 , 1i0098. 00098. 0 ,000099. 0max)c/010(Pmax*)c/010(P7ii收到收到y4=011时时001c*c)011( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/011(Pmax*)c/011(P2ii收到收到y5=100时时

14、110c*c)100( f2 , 1i0098. 00098. 0 ,000099. 0max)c/100(Pmax*)c/100(P7ii第第7章章 数据传输数据传输收到收到y6=101时时001c*c)101( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/101(Pmax*)c/101(P2ii收到收到y7=110时时110c*c)110( f2 , 1i9703. 09703. 0 ,000001. 0max)c/110(Pmax*)c/110(P7ii收到收到y8=111时时110c*c)111( f2 , 1i0098. 00098. 0 ,00009

15、9. 0max)c/111(Pmax*)c/111(P7ii第第7章章 数据传输数据传输通过在发送端增加冗余使消息出现一位传输错误时通过在发送端增加冗余使消息出现一位传输错误时由接收端进行纠正由接收端进行纠正纠错纠错001)101( f001)011( f001)001( f001)000( f110)111( f110)110( f110)100( f110)010( f第第7章章 数据传输数据传输平均译码错误概率平均译码错误概率4282725232767472717103)000099. 06000001. 02(21)c/y(P)c/y(P)c/y(P)c/y(P)c (P)c/y(P)

16、c/y(P)c/y(P)c/y(P)c (P*cc81jijiei)c/y(P)c (PP第第7章章 数据传输数据传输如果选取其中如果选取其中c1=000，c5=100为许用码，其余为禁为许用码，其余为禁用码用码2个码字构成的码表中个码字构成的码表中1dmind51min99. 001. 001. 099. 0)X/Y(P及信源等概率条件下及信源等概率条件下在信道在信道第第7章章 数据传输数据传输x=0c1=000，x=1c5=100三次扩展信源的子三次扩展信源的子信源，三次扩展信宿信源，三次扩展信宿三次扩展信道的子信道三次扩展信道的子信道000099. 00098. 00098. 09703

17、. 0000001. 0000099. 0000099. 00098. 0000001. 0000099. 0000099. 00098. 0000099. 00098. 00098. 09703. 0)X/Y(P333第第7章章 数据传输数据传输最大似然准则译码最大似然准则译码收到收到y1=000时时000c*c)000( f2 , 1i9703. 00098. 0 ,9703. 0max)c/000(Pmax*)c/000(P1ii收到收到y2=001时时000c*c)001( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/001(Pmax*)c/001(P1

18、ii第第7章章 数据传输数据传输收到收到y3=010时时000c*c)010( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/010(Pmax*)c/010(P1ii收到收到y4=011时时000c*c)011( f2 , 1i000099. 0000001. 0 ,000099. 0max)c/011(Pmax*)c/011(P1ii收到收到y5=100时时100c*c)100( f2 , 1i9703. 09703. 0 ,0098. 0max)c/100(Pmax*)c/100(P5ii第第7章章 数据传输数据传输收到收到y6=101时时100c*c)101

19、( f2 , 1i0098. 00098. 0 ,000099. 0max)c/101(Pmax*)c/101(P5ii收到收到y7=110时时100c*c)110( f2 , 1i0098. 00098. 0 ,000099. 0max)c/110(Pmax*)c/110(P5ii收到收到y8=111时时100c*c)111( f2 , 1i000099. 0000099. 0 ,000001. 0max)c/111(Pmax*)c/111(P5ii第第7章章 数据传输数据传输通过在发送端增加冗余使消息出现一位传输错误时通过在发送端增加冗余使消息出现一位传输错误时不能完全由接收端进行纠正不能

20、完全由接收端进行纠正000)011( f000)010( f000)001( f000)000( f100)111( f100)110( f100)101( f100)100( f第第7章章 数据传输数据传输平均译码错误概率平均译码错误概率*cc81jijiei)c/y(P)c (PP01. 0)0098. 02000099. 04000001. 02(21)c/y(P)c/y(P)c/y(P)c/y(P)c (P)c/y(P)c/y(P)c/y(P)c/y(P)c (P181716151545352515第第7章章 数据传输数据传输线性分组码的编码线性分组码的编码选取许用码选取许用码线性分组

21、码的编码原则线性分组码的编码原则保证最小码距足够大保证最小码距足够大第第7章章 数据传输数据传输线性分组码检错纠错的充要条件线性分组码检错纠错的充要条件线性分组码线性分组码(n,k) 检检e位错并同时纠位错并同时纠t位错的充要条位错的充要条件件1tedmin检一位错并同时纠一位错的充要条件检一位错并同时纠一位错的充要条件3dmin第第7章章 数据传输数据传输7.2 汉明汉明码码汉明码汉明码最小码距最小码距dmin=3的线性分组码的线性分组码设设(n,k)汉明码的码字汉明码的码字kiiiiiii2 , 2 , 1icccccccn2k1kk21为校验位，校验长度为为校验位，校验长度为n-kn2k

22、1kiiiccc其中其中 为消息位，消息长度为为消息位，消息长度为kk21iiiccckk2211iiiiiixc,xc,xc一般第第7章章 数据传输数据传输1、汉明码的编码、汉明码的编码编码步骤编码步骤构造满秩的构造满秩的(n-k)n校验矩阵校验矩阵HkTii2 , 2 , 1iHrsri第第i个接收码字，个接收码字，1n向量向量si第第i个接收码字的误码标志，个接收码字的误码标志，1(n-k)向量向量1n2kn其中0HcHrscrTiTiiii，取当ci第第i个发送码字，个发送码字，1n向量向量第第7章章 数据传输数据传输设满秩的设满秩的kn生成矩阵生成矩阵GGI G)kn(kkk一般ki

23、i2 , 2 , 1iGxcxi第第i个发送消息，个发送消息，1k向量向量由生成矩阵由生成矩阵G与校验矩阵与校验矩阵H之间之间GHT=0求出求出G即可即可编码编码第第7章章 数据传输数据传输例例1：(3,1)汉明码的编码汉明码的编码构造满秩的构造满秩的23校验矩阵校验矩阵H所有所有2维非零列向量构成校验矩阵维非零列向量构成校验矩阵H，如，如101110H1n4222kn其中第第7章章 数据传输数据传输设满秩的设满秩的13生成矩阵生成矩阵Ggg1 G3200110110gg1 32TGH由0g10gg3321g1g32 111 G 第第7章章 数据传输数据传输2 , 1ixxx 111xGxcc

24、c ciiiiiiiii321111c1x000c0 x2211最小码距最小码距3dmind12min(3,1)汉明码汉明码三重复码能检一位错并同时纠一三重复码能检一位错并同时纠一位错位错(3,1)汉明码的码长为原来的汉明码的码长为原来的3倍倍编码效率为编码效率为1/3第第7章章 数据传输数据传输例例2：(7,4)汉明码的编码汉明码的编码构造满秩的构造满秩的37校验矩阵校验矩阵H所有所有3维非零列向量构成校验矩阵维非零列向量构成校验矩阵H，如，如101010111001101111000H1n8223kn其中第第7章章 数据传输数据传输设满秩的设满秩的47生成矩阵生成矩阵G4746453736

25、35272625171615ggg1000ggg0100ggg0010ggg0001G第第7章章 数据传输数据传输000000000000111011101001110010100ggg1000ggg0100ggg0010ggg0001474645373635272625171615TGH由0gg10gg0ggg171517161716151g1g0g171615第第7章章 数据传输数据传输0gg0gg10ggg272527262726251g0g1g272625000000000000111011101001110010100ggg1000ggg0100ggg0010ggg000147464

26、5373635272625171615TGH由第第7章章 数据传输数据传输0gg10gg10ggg373537363736350g1g1g373635000000000000111011101001110010100ggg1000ggg0100ggg0010ggg0001474645373635272625171615TGH由第第7章章 数据传输数据传输0gg0gg0ggg1474547464746451g1g1g474645000000000000111011101001110010100ggg1000ggg0100ggg0010ggg0001474645373635272625171615

27、TGH由第第7章章 数据传输数据传输1111000011010010100101100001G第第7章章 数据传输数据传输16, 2 , 1ixxxxxxxxxxxxx1111000011010010100101100001xxxxGxccccccc c421431432432143217654321iiiiiiiiiiiiiiiiiiiiiiiiii第第7章章 数据传输数据传输0111100c0111x0110011c0110 x0101010c0101x0100101c0100 x0011001c0011x0010110c0010 x0001111c0001x0000000c0000 x8

28、8776655443322111111111c1111x1110000c1110 x1101001c1101x1100110c1100 x1011010c1011x1010101c1010 x1001100c1001x1000011c1000 x161615151414131312121111101099第第7章章 数据传输数据传输任意两个码字之间的码距任意两个码字之间的码距4ccd71l2112ll3ccd71l3113ll4ccd71l16151516ll最小码距最小码距ji ,16, 2 , 1j , i3dmindijj , imin第第7章章 数据传输数据传输(7,4)汉明码能检一位错并同时纠一位错汉明码能检一位错并同时纠一位错(7,4)汉明码的码长为原来的汉明码的码长为原来的7/4倍倍编码效率为编码效率为4/7第第7章章 数据传输数据传输2、汉明码的译码、汉明码的译码译码步骤译码步骤检错检错误码标志误码标志si0HrscrTiiii，当当出现一位传输错误当出现一位传输错误kTii2, 2, 1iHrs第第7章章 数据传输数据传输ccccccc rrrrrrr r765432176