第5章 信道编码

1、第第5章章 信道编码信道编码第第5章章 信道编码信道编码理解理解n次扩展信道的联合渐近均分性次扩展信道的联合渐近均分性理解香农第二定理理解香农第二定理理解线性分组码的纠错原理理解线性分组码的纠错原理掌握汉明码的编码和译码掌握汉明码的编码和译码教学内容和要求教学内容和要求第第5章章 信道编码信道编码5.1 联合渐近均分性定理联合渐近均分性定理1、n次扩展信道的联合渐进均分性次扩展信道的联合渐进均分性例例11 . 09 . 0)X(P9 . 01 . 01 . 09 . 0)X/Y(P二次扩展信道相关符号序列的概率分布特点二次扩展信道相关符号序列的概率分布特点第第5章章 信道编码信道编码二次扩展信

2、源的概率二次扩展信源的概率01. 009. 009. 081. 0)X(P201. 0)11(P99. 009. 0281. 0)10(P)01(P)00(P信源符号序列概率分布特点信源符号序列概率分布特点72. 009. 081. 0)01(P)00(P第第5章章 信道编码信道编码二次扩展信道的信道矩阵二次扩展信道的信道矩阵81. 009. 009. 001. 009. 081. 001. 009. 009. 001. 081. 009. 001. 009. 009. 081. 0)X/Y(P22第第5章章 信道编码信道编码二次扩展信宿的概率二次扩展信宿的概率0324. 01476. 014

3、76. 06724. 081. 009. 009. 001. 009. 081. 001. 009. 009. 001. 081. 009. 001. 009. 009. 081. 001. 009. 009. 081. 0)X/Y(P)X(P)Y(P2222第第5章章 信道编码信道编码0324. 0)11(P9676. 01476. 026724. 0)10(P)01(P)00(P信宿符号序列概率分布特点信宿符号序列概率分布特点5248. 01476. 06724. 0)01(P)00(P第第5章章 信道编码信道编码0081. 009. 009. 0)01/11(P)01(P)0111(P0

4、009. 001. 009. 0)01/10(P)01(P)0110(P0729. 081. 009. 0)01/01(P)01(P)0101(P0081. 009. 009. 0)01/00(P)01(P)0100(P0081. 001. 081. 0)00/11(P)00(P)0011(P0729. 009. 081. 0)00/10(P)00(P)0010(P0729. 009. 081. 0)00/01(P)00(P)0001(P6561. 081. 081. 0)00/00(P)00(P)0000(P信源信宿联合符号序列概率分布特点信源信宿联合符号序列概率分布特点第第5章章 信道编码

5、信道编码0081. 081. 001. 0)11/11(P)11(P)1111(P0009. 009. 001. 0)11/10(P)11(P)1110(P0009. 009. 001. 0)11/01(P)11(P)1101(P0001. 001. 001. 0)11/00(P)11(P)1100(P0081. 009. 009. 0)10/11(P)10(P)1011(P0729. 081. 009. 0)10/10(P)10(P)1010(P0009. 001. 009. 0)10/01(P)10(P)1001(P0081. 009. 009. 0)10/00(P)10(P)1000(P

6、第第5章章 信道编码信道编码0037. 00001. 00009. 04)1110(P)1101(P)1100(P)1001(P)0110(P9963. 00081. 060729. 046561. 0)1111(P)1011(P)1000(P)0111(P)0100(P)0011(P)1010(P)0101(P)0010(P)0001(P)0000(P5832. 00729. 06561. 0)0001(P)0000(P第第5章章 信道编码信道编码2、联合渐进均分性定理、联合渐进均分性定理定理定理典型序列中的符号序列为典型集记)X(Axxxniiin21任意给定任意给定 0，当，当n足够大，

7、足够大，n次扩展信源的典型序次扩展信源的典型序列满足列满足N, 2 , 1i ,i ,i)X(H)xxx(Plogn1n21iiin21第第5章章 信道编码信道编码典型序列中的符号序列为典型集记)Y(Ayyynjjjn21同样的同样的和和n，n次扩展信宿的典型序列满足次扩展信宿的典型序列满足M, 2 , 1j ,j , j)Y(H)yyy(Plogn1n21jjjn21联合典型序列序列中的符号为典型集记)XY(Ayyyxxxnjjjiiin21n21n次扩展信道的联合典型序列满足次扩展信道的联合典型序列满足第第5章章 信道编码信道编码M, 2 , 1j ,j , jN, 2 , 1i ,i ,

8、i)XY(H)yyyxxx(Plogn1n21n21jjjiiin21n21第第5章章 信道编码信道编码n1kiiiiiii)x(Plogn1)x(P)x(P)x(Plogn1)xxx(Plogn1kn21n21)x(PlogE)x(Plog)x(P)X(H)X(HkkkiN1iiik第第5章章 信道编码信道编码取取nn1，当，当n1足够大足够大由大数定理由大数定理1)x(PlogE)x(Plogn1P)X(H)xxx(Pn1Pkkn21in1kiiii第第5章章 信道编码信道编码n1kjjjjjjj)y(Plogn1)y(P)y(P)y(Plogn1)yyy(Plogn1kn21n21)y(

9、PlogE)y(Plog)y(P)Y(H)Y(HkkkjM1jjjk第第5章章 信道编码信道编码取取nn2，当，当n2足够大足够大由大数定理由大数定理1)y(PlogE)y(Plogn1P)Y(H)yyy(Pn1Pkkn21jn1kjjjj第第5章章 信道编码信道编码n1kjijijijijjjiii)yx(Plogn1)yx(P)yx(P)yx(Plogn1)yyyxxx(Plogn1kknn2211n21n21)yx(PlogE)yx(Plog)yx(P)YX(H)XY(HkkkkkkjiN1iM1jjijikk第第5章章 信道编码信道编码取取nn3，当，当n3足够大足够大由大数定理由大数

10、定理1)yx(PlogE)yx(Plogn1P)XY(H)yyyxxx(Pn1Pkkkkn21n21jin1kjijjjiii，三式同时成立取)n,n,nmax(n321第第5章章 信道编码信道编码推论推论1的概率为典型序列记n21n21iiiiiixxx)xxx(P的概率为典型序列n21n21jjjjjjyyy)yyy(P的概率为联合典型序列n21n21n21n21jjjiiijjjiiiyyyxxx)yyyxxx(P)X(Hniii)X(Hn2)xxx(P2n21)Y(Hnjjj)Y(Hn2)yyy(P2n21)XY(Hnjjjiii)XY(Hn2)yyyxxx(P2n21n21第第5章章

11、 信道编码信道编码推论推论2的数量为典型序列记n21iiinxxx)X(A的数量为联合典型序列n21n21jjjiiinyyyxxx)XY(A)X(Hnn)X(Hn2)X(A2)1 ()Y(Hnn)Y(Hn2)Y(A2)1 (的数量为典型序列n21jjjnyyy)Y(A第第5章章 信道编码信道编码)XY(Hnn)XY(Hn2)XY(A2)1 (第第5章章 信道编码信道编码推论推论33)Y;X( I n)XY(Ayyyxxxjjjiii3)Y;X( I n2)yyy(P)xxx(P2 )1 (nnj2j1jni2i1in21n21 第第5章章 信道编码信道编码)Y(Hn)X(Hnmaxn)Y(H

12、n)X(Hnn)XY(Ayyyxxxjjjmaxiiimax)XY(Ayyyxxxjjjiii22)XY(A22)XY(A)yyy(P)xxx(P)yyy(P)xxx(Pnnj2j1jni2i1in21n21nnj2j1jni2i1in21n21 3)Y;X( I n)Y(Hn)X(Hn)XY(Hn2222第第5章章 信道编码信道编码)Y(Hn)X(Hnminn)Y(Hn)X(Hnn)XY(Ayyyxxxjjjminiiimin)XY(Ayyyxxxjjjiii22)XY(A22)XY(A)yyy(P)xxx(P)yyy(P)xxx(Pnnj2j1jni2i1in21n21nnj2j1jni2

13、i1in21n21 3)Y;X( I n)Y(Hn)X(Hn)XY(Hn2)1 (222)1 (第第5章章 信道编码信道编码3)Y;X( I n)XY(Ayyyxxxjjjiii3)Y;X( I n2)yyy(P)xxx(P2)1 (nnj2j1jni2i1in21n21 第第5章章 信道编码信道编码5.2 香农第二定理香农第二定理1、平均译码错误概率、平均译码错误概率最小错误概率准则下的平均译码错误概率最小错误概率准则下的平均译码错误概率定义定义信宿收到信宿收到yj按最大后验概率判断信源发送按最大后验概率判断信源发送x*xi之一之一译码译码最小错误概率准则最小错误概率准则第第5章章 信道编码

14、信道编码表示表示M, 2 , 1j*x)y( fN, 2 , 1i)y/x(Pmax)y/*x(Pjjiij则如果平均译码错误概率平均译码错误概率信宿收到信宿收到yj的译码错误概率的译码错误概率)y/*x(P1Pjej第第5章章 信道编码信道编码平均译码错误概率平均译码错误概率*xxM1jjijM1jjjN1iM1jjijM1jjjM1jjM1jjjei)y/x(P)y(P)y/*x(P)y(P)y/x(P)y(P)y/*x(P)y(P)y(P)y/*x(P1)y(PP第第5章章 信道编码信道编码最大似然准则下的平均译码错误概率最大似然准则下的平均译码错误概率最大似然准则最大似然准则定义定义信

15、宿收到信宿收到yj按最大转移概率判断信源发送按最大转移概率判断信源发送x*xi之一之一译码译码表示表示M, 2 , 1j*x)y( fN, 2 , 1i)x/y(Pmax*)x/y(Pjijij则如果第第5章章 信道编码信道编码)y(P)x(P)x/y(Pmax)y/x(Pmax)y(P*)x(P*)x/y(P)y/*x(Pjiijijiijjj)x(P)x/y(Pmax*)x(P*)x/y(Piijij信源等概率条件下信源等概率条件下)x/y(Pmax*)x/y(Pijij最大似然准则等同于最小错误概率准则最大似然准则等同于最小错误概率准则第第5章章 信道编码信道编码平均译码错误概率平均译码

16、错误概率*xxM1jiji*xxM1jji*xxM1jjijeiii)x/y(P)x(P)yx(P)y/x(P)y(PP第第5章章 信道编码信道编码2、香农第二定理、香农第二定理定理定理信道的信道容量为信道的信道容量为C，对，对n次扩展信道进行信道编次扩展信道进行信道编码，对任意给定的码，对任意给定的 0，只要码率，只要码率R C，当，当n足足够大，平均译码错误概率够大，平均译码错误概率Pe C，无论，无论n多大，平均译码错误概率多大，平均译码错误概率Pe 第第5章章 信道编码信道编码正定理正定理n2liiicccn的码字随机产生码长为当当n足够大，随机产生的码字为等概率的典型序列，足够大，随

17、机产生的码字为等概率的典型序列，数量为数量为2nH(X)，选取其中，选取其中2nR个作为许用码，其余为个作为许用码，其余为禁用码禁用码发生译码错误的两种情况发生译码错误的两种情况不构成联合典型序列与*cccyyyn2ln2liiijjj构成联合典型序列以外的与n2ln2ln2liiiiiijjjccc*cccyyy调整信源概率调整信源概率P(X)，使，使I(X;Y)=C第第5章章 信道编码信道编码不失一般性，记不失一般性，记E1*表示第一种情况，表示第一种情况，Ei 表示第二表示第二种情况种情况 i=2,2nR平均译码错误概率平均译码错误概率nRnR22ii1221e)E(P)E(P)EEE(

18、PP nRnRnnj2j1jni2i1in21n2122i3)Y;X( I n22i)XY(Ayyycccjjjiii2)yyy(P)ccc (P第第5章章 信道编码信道编码3CRn3CnnR22i3Cn22) 12(2nR3CR只要eP当当n足够大足够大第第5章章 信道编码信道编码5.3 费诺不等式与香农第二定理的逆定理费诺不等式与香农第二定理的逆定理1、费诺不等式、费诺不等式n次扩展信道的损失熵次扩展信道的损失熵H(Xn/Yn)与平均译码错误概与平均译码错误概率率Pe之间满足之间满足) 12log(P)P(H)Y/X(HnReenn定理定理第第5章章 信道编码信道编码 M1jM1jM1jj

19、jjiiijjjiii*xxxxxxM1jM1jM1jjjjiiijjjiiiN1iN1iN1iM1jM1jM1jjjjiiijjjiiinn12nn21n21n21n21ni2i1ini2i1i12nn21n21n21n2112n12nn21n21n21n21)yyy/*xxx(Plog)yyy*xxx(P)yyy/xxx(Plog)yyyxxx(P)yyy/xxx(Plog)yyyxxx(P)Y/X(H第第5章章 信道编码信道编码 M1jM1jM1jjjjiiie*xxxxxxM1jM1jM1jjjjiiie12nn21n21ni2i1ini2i1i12nn21n21)yyy*xxx(PP

20、)yyyxxx(PP注意到第第5章章 信道编码信道编码eenReenReeeeenReePlogP12PlogP) 12log(PPlogPPlogP) 12log(P)P(HeM1jM1jM1jjjjiiinRe*xxxxxxM1jM1jM1jjjjiiiPlog)yyy*xxx(P12Plog)yyyxxx(P12nn21n21ni2i1ini2i1i12nn21n21 第第5章章 信道编码信道编码) 12log(P)P(H)Y/X(HnReenn M1jM1jM1jjjjiiijjjiii*xxxxxxM1jM1jM1jjjjiiijjjiii12nn21n21n21n21ni2i1in

21、i2i1i12nn21n21n21n21)yyy/*xxx(Plog)yyy*xxx(P)yyy/xxx(Plog)yyyxxx(PeM1jM1jM1jjjjiiinRe*xxxxxxM1jM1jM1jjjjiiiPlog)yyy*xxx(P12Plog)yyyxxx(P12nn21n21ni2i1ini2i1i12nn21n21 第第5章章 信道编码信道编码)yyy /*xxx(PPlog)yyy*xxx(P) 12)(yyy/xxx(PPlog)yyyxxx(Pn21n2112nn21n21n21n21ni2i1ini2i1i12nn21n21jjjiiieM1jM1jM1jjjjiiin

22、Rjjjiiie*xxxxxxM1jM1jM1jjjjiii 1)yyy /*xxx(PP )yyy*xxx(P 1) 12)(yyy/xxx(PP )yyyxxx(Pn21n2112nn21n21n21n21ni2i1ini2i1i12nn21n21jjjiiieM1jM1jM1jjjjiiinRjjjiiie*xxxxxxM1jM1jM1jjjjiii )yyy*xxx(PP)yyy(P)yyyxxx(P12P)yyy(Pn21n2112nn21n21n21ni2i1ini2i1i12nn21jjjiiiM1jM1jM1jejjjjjjiii*xxxxxxM1jM1jM1jnRejjj 第

23、第5章章 信道编码信道编码0PPPPPPP12Peeeeeee*xxxxxxnReni2i1ini2i1i) 12log(P)P(H)Y/X(HnReenn第第5章章 信道编码信道编码2、逆定理、逆定理对于长度为对于长度为n，数量为，数量为2nR的任意码字，如果的任意码字，如果R C，当当n足够大，有足够大，有C)11 (nnR2log)X(HnRnnC)Y/X(HC)11 (n)Y/X(H)X(H)Y;X( InnnnnnnC)11 (R取第第5章章 信道编码信道编码1)P(He注意到C)11 (nP1nRP12logP1) 12log(P1) 12log(P)P(H)Y/X(HC1neen

24、RenRenReenn第第5章章 信道编码信道编码C)11 (C1Pne，即使C)11 (n1C1C)11 (n1C1nPe第第5章章 信道编码信道编码香农第二定理表明了平均译码错误概率任意小的香农第二定理表明了平均译码错误概率任意小的信道编码的存在性，明确了信道容量信道编码的存在性，明确了信道容量C是信道编码是信道编码的码率上界的码率上界香农界香农界第第5章章 信道编码信道编码5.4 纠错与线性分组码的编码原则纠错与线性分组码的编码原则1、纠错、纠错信道编码信道编码通过在发送端增加冗余使消息出现传输错误时由通过在发送端增加冗余使消息出现传输错误时由接收端自动进行纠正接收端自动进行纠正纠错纠错

25、第第5章章 信道编码信道编码2、n重复码重复码例例199. 001. 001. 099. 0)X/Y(P信源等概率时的平均译码错误概率信源等概率时的平均译码错误概率第第5章章 信道编码信道编码最大似然准则译码最大似然准则译码收到收到y1时时11i1i1x*x)y( f2 , 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时时第第5章章 信道编码信道编码平均译码错误概率平均译码错误概率01. 0)01. 001. 0 (21)x/y(P)x(P

26、)x/y(P)x(P)x/y(P)x(PP212121*xx21jijiei通信系统中一般要求平均译码错误概率的数量级通信系统中一般要求平均译码错误概率的数量级10-6 -10-9第第5章章 信道编码信道编码三重复码三重复码消息重复三次消息重复三次x1=0c1=000，x2=1c2=111三次扩展信源的子信源，三次扩三次扩展信源的子信源，三次扩展信宿展信宿三次扩展信道的子信道三次扩展信道的子信道9703. 00098. 00098. 0000099. 00098. 0000099. 0000099. 0000001. 0000001. 0000099. 0000099. 00098. 0000

27、099. 00098. 00098. 09703. 0)X/Y(P331第第5章章 信道编码信道编码最大似然准则译码最大似然准则译码收到收到y1=000时时000c*c)000( f2 , 1i9703. 0000001. 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(P1ii第第5章章 信道编码信道编码收到收到y3=010时时000c*c)010( f2 , 1i0098. 0000099. 0 ,0098. 0

28、max)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 , 1i0098. 0000099. 0 ,0098. 0max)c/100(Pmax*)c/100(P1ii第第5章章 信道编码信道编码收到收到y6=101时时111c*c)101( f2 , 1i0098. 00098. 0 ,000099. 0max)c/101(Pmax*)c/101(P2ii收到收到y7=110时时11

29、1c*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(Pmax*)c/111(P2ii第第5章章 信道编码信道编码三重复码三重复码通过在发送端增加冗余使消息出现一通过在发送端增加冗余使消息出现一位传输错误时由接收端进行纠正位传输错误时由接收端进行纠正纠错纠错000)100( f000)010( f000)001( f000)000( f111)111( f111)110( f111)

30、101( f111)011( f第第5章章 信道编码信道编码平均译码错误概率平均译码错误概率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/y(P)c/y(P)c (P*cc81jijiei)c/y(P)c (PP第第5章章 信道编码信道编码重复重复n次次n重复码重复码10e8e7e5e105P11n10P9n104P7n10P5n，n重复码的码长为原来的重复码的码长为原来的n倍倍编码效率为编码效率为1/n第第5章章 信道编码信道编码需要找的需要找的“好码好码”足

31、够小的平均译码错误概率足够小的平均译码错误概率Pe较高的编码效率较高的编码效率第第5章章 信道编码信道编码3、线性分组码及其编码原则、线性分组码及其编码原则线性分组码线性分组码定义定义具有恒定码字长度和消息长度，消息相加后的编具有恒定码字长度和消息长度，消息相加后的编码等同于各自编码相加的纠错码码等同于各自编码相加的纠错码表示表示(n,k)其中其中n为码字长度，为码字长度，k为消息长度，为消息长度，n-k为为校验长度校验长度第第5章章 信道编码信道编码例例2(4,3)偶校验码偶校验码0110c011x0101c010 x0011c001x0000c000 x443322111111c111x1

32、100c110 x1010c101x1001c100 x88776655100110100011cc1001100101001xx6262第第5章章 信道编码信道编码码距和最小码距码距和最小码距2k个码字构成的码表中，任意两个码字之间的码距个码字构成的码表中，任意两个码字之间的码距(汉明距离汉明距离)定义定义任意两个码字对应位上不同码元的个数任意两个码字对应位上不同码元的个数表示表示ji ,2 , 2 , 1j , icc)c ,c (ddkn1ljijiijll第第5章章 信道编码信道编码例例3(4,3)偶校验码中码字偶校验码中码字c2和和c3之间的码距之间的码距d230101c0011c3

33、22ccd41l3223ll第第5章章 信道编码信道编码2k个码字构成的码表中，码字之间的最小码距个码字构成的码表中，码字之间的最小码距定义定义所有码字之间码距的最小值所有码字之间码距的最小值表示表示ji ,2 , 2 , 1j , idmindkijj , imin第第5章章 信道编码信道编码线性分组码的编码原则线性分组码的编码原则例例4(3,1)线性分组码线性分组码三次扩展信源中三次扩展信源中8个可能的码字个可能的码字111c011c110c010c101c001c100c000c84736251第第5章章 信道编码信道编码8个可能的码字构成的码表中，任意两个码字之间个可能的码字构成的码表

34、中，任意两个码字之间的码距的码距1dddddddddddd8786756584734362425131212dddddddddddd7685746483538252327161413dddd54637281第第5章章 信道编码信道编码如果选取其中如果选取其中c1=000，c8=111为许用码，其余为禁为许用码，其余为禁用码用码三重复码三重复码2个码字构成的码表中个码字构成的码表中3dmind81min99. 001. 001. 099. 0)X/Y(P及信源等概率条件下的平均译码错误概率及信源等概率条件下的平均译码错误概率在信道在信道4e103P第第5章章 信道编码信道编码如果选取其中如果选取

35、其中c2=001，c7=110为许用码，其余为禁为许用码，其余为禁用码用码2个码字构成的码表中个码字构成的码表中3dmind27min99. 001. 001. 099. 0)X/Y(P及信源等概率条件下及信源等概率条件下在信道在信道第第5章章 信道编码信道编码x=0c2=001，x=1c7=110三次扩展信源的子三次扩展信源的子信源，三次扩展信宿信源，三次扩展信宿三次扩展信道的子信道三次扩展信道的子信道0098. 09703. 0000099. 00098. 0000099. 00098. 0000001. 0000099. 0000099. 0000001. 00098. 0000099.

36、 00098. 0000099. 09703. 00098. 0)X/Y(P332第第5章章 信道编码信道编码最大似然准则译码最大似然准则译码收到收到y1=000时时001c*c)000( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/000(Pmax*)c/000(P2ii收到收到y2=001时时001c*c)001( f2 , 1i9703. 0000001. 0 ,9703. 0max)c/001(Pmax*)c/001(P2ii第第5章章 信道编码信道编码收到收到y3=010时时110c*c)010( f2 , 1i0098. 00098. 0 ,0000

37、99. 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时时110c*c)100( f2 , 1i0098. 00098. 0 ,000099. 0max)c/100(Pmax*)c/100(P7ii第第5章章 信道编码信道编码收到收到y6=101时时001c*c)101( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/101(Pmax*)c/101(P2ii收到收到y7=11

38、0时时110c*c)110( f2 , 1i9703. 09703. 0 ,000001. 0max)c/110(Pmax*)c/110(P7ii收到收到y8=111时时110c*c)111( f2 , 1i0098. 00098. 0 ,000099. 0max)c/111(Pmax*)c/111(P7ii第第5章章 信道编码信道编码通过在发送端增加冗余使消息出现一位传输错误时通过在发送端增加冗余使消息出现一位传输错误时由接收端进行纠正由接收端进行纠正纠错纠错001)101( f001)011( f001)001( f001)000( f110)111( f110)110( f110)100

39、( f110)010( f第第5章章 信道编码信道编码平均译码错误概率平均译码错误概率4282725232767472717103)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/y(P)c/y(P)c (P*cc81jijiei)c/y(P)c (PP第第5章章 信道编码信道编码如果选取其中如果选取其中c1=000，c7=110为许用码，其余为禁为许用码，其余为禁用码用码2个码字构成的码表中个码字构成的码表中2dmind71min99. 001. 001. 099. 0)X/Y(P及信源等概率条件下及信源等

40、概率条件下在信道在信道第第5章章 信道编码信道编码x=0c1=000，x=1c7=110三次扩展信源的子三次扩展信源的子信源，三次扩展信宿信源，三次扩展信宿三次扩展信道的子信道三次扩展信道的子信道0098. 09703. 0000099. 00098. 0000099. 00098. 0000001. 0000099. 0000001. 0000099. 0000099. 00098. 0000099. 00098. 00098. 09703. 0)X/Y(P333第第5章章 信道编码信道编码最大似然准则译码最大似然准则译码收到收到y1=000时时000c*c)000( f2 , 1i9703

41、. 0000099. 0 ,9703. 0max)c/000(Pmax*)c/000(P1ii收到收到y2=001时时000c*c)001( f2 , 1i0098. 0000001. 0 ,0098. 0max)c/001(Pmax*)c/001(P1ii第第5章章 信道编码信道编码收到收到y3=010时时110c*c)010( f000c*c)010( f2 , 1i0098. 00098. 0 ,0098. 0max)c/010(Pmax*)c/010(P71ii或收到收到y4=011时时110c*c)011(f000c*c)011(f2 , 1i000099. 0000099. 0 ,

42、000099. 0max)c/011(Pmax*)c/011(P71ii或收到收到y5=100时时110c*c)100( f000c*c)100( f2 , 1i0098. 00098. 0 ,0098. 0max)c/100(Pmax*)c/100(P71ii或第第5章章 信道编码信道编码收到收到y6=101时时110c*c)101( f000c*c)101( f2 , 1i000099. 0000099. 0 ,000099. 0max)c/101(Pmax*)c/101(P71ii或收到收到y7=110时时110c*c)110( f2 , 1i9703. 09703. 0 ,000099

43、. 0max)c/110(Pmax*)c/110(P7ii收到收到y8=111时时110c*c)111( f2 , 1i0098. 00098. 0 ,000001. 0max)c/111(Pmax*)c/111(P7ii第第5章章 信道编码信道编码通过在发送端增加冗余使消息出现一位传输错误时通过在发送端增加冗余使消息出现一位传输错误时不能完全由接收端进行纠正不能完全由接收端进行纠正110)111( f110)110( f110/000)100( f110/000)010( f000)001( f000)000( f110/100)101( f110/100)011( f第第5章章 信道编码信

44、道编码平均译码错误概率平均译码错误概率*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第第5章章 信道编码信道编码线性分组码的编码线性分组码的编码选取许用码选取许用码线性分组码的编码原则线性分组码的编码原则保证最小码距足够大保证最小码距足够大第第5章章 信道编码信道编码线性分组码检错纠错的充要条件线性分组码检错纠错的充要条件线性分组码线性分组码(n,k) 检检e位错并同时纠

45、位错并同时纠t位错的充要条位错的充要条件件1tedmin检一位错并同时纠一位错的充要条件检一位错并同时纠一位错的充要条件3dmin第第5章章 信道编码信道编码5.5 汉明码汉明码汉明码汉明码最小码距最小码距dmin=3的线性分组码的线性分组码设设(n,k)汉明码的码字汉明码的码字kiiiiiii2 , 2 , 1icccccccn2k1kk21为校验位，校验长度为为校验位，校验长度为n-kn2k1kiiiccc其中其中 为消息位，消息长度为为消息位，消息长度为kk21iiiccckk2211iiiiiixc ,xc ,xc一般第第5章章 信道编码信道编码1、汉明码的编码、汉明码的编码编码步骤编

46、码步骤构造满秩的构造满秩的(n-k)n校验矩阵校验矩阵HkTii2 , 2 , 1iHrsri第第i个接收码字，个接收码字，1n向量向量si第第i个接收码字的误码标志，个接收码字的误码标志，1(n-k)向量向量1n2kn其中0HcHrscrTiTiiii ，取当ci第第i个发送码字，个发送码字，1n向量向量第第5章章 信道编码信道编码设满秩的设满秩的kn生成矩阵生成矩阵GGI G)kn(kkk一般kii2 , 2 , 1iGxcxi第第i个发送消息，个发送消息，1k向量向量由生成矩阵由生成矩阵G与校验矩阵与校验矩阵H之间之间GHT=0求出求出G即可即可编码编码第第5章章 信道编码信道编码例例1

47、(3,1)汉明码汉明码构造满秩的构造满秩的23校验矩阵校验矩阵H所有所有2维非零列向量构成校验矩阵维非零列向量构成校验矩阵H，如，如101110H1n4222kn其中第第5章章 信道编码信道编码设满秩的设满秩的13生成矩阵生成矩阵Ggg1 G3200110110gg1 GH32T由0g10gg3321g1g32 111 G第第5章章 信道编码信道编码2 , 1ixxx 111xGxccc ciiiiiiiii321111c1x000c0 x2211最小码距最小码距3dmind12min(3,1)汉明码汉明码三重复码能检一位错并同时纠一位三重复码能检一位错并同时纠一位错错(3,1)汉明码的码长为

48、原来的汉明码的码长为原来的3倍倍编码效率为编码效率为1/3第第5章章 信道编码信道编码例例2(7,4)汉明码的编码汉明码的编码构造满秩的构造满秩的37校验矩阵校验矩阵H所有所有3维非零列向量构成校验矩阵维非零列向量构成校验矩阵H，如，如101010111001101111000H1n8223kn其中第第5章章 信道编码信道编码设满秩的设满秩的47生成矩阵生成矩阵G474645373635272625171615ggg1000ggg0100ggg0010ggg0001G第第5章章 信道编码信道编码000000000000111011101001110010100ggg1000ggg0100ggg

49、0010ggg0001GH474645373635272625171615T由0gg10gg0ggg171517161716151g1g0g171615第第5章章 信道编码信道编码000000000000111011101001110010100ggg1000ggg0100ggg0010ggg0001GH474645373635272625171615T由0gg0gg10ggg272527262726251g0g1g272625第第5章章 信道编码信道编码000000000000111011101001110010100ggg1000ggg0100ggg0010ggg0001GH4746453

50、73635272625171615T由0gg10gg10ggg373537363736350g1g1g373635第第5章章 信道编码信道编码000000000000111011101001110010100ggg1000ggg0100ggg0010ggg0001GH474645373635272625171615T由0gg0gg0ggg1474547464746451g1g1g474645第第5章章 信道编码信道编码1111000011010010100101100001G第第5章章 信道编码信道编码16, 2 , 1ixxxxxxxxxxxxx1111000011010010100101100001xxxxGxccccccc c42143143