第5章 信道編碼

1、第第5章章 信道編碼信道編碼第第5章章 信道編碼信道編碼理解理解n次擴(kuò)展信道的聯(lián)合漸近均分性次擴(kuò)展信道的聯(lián)合漸近均分性理解香農(nóng)第二定理理解香農(nóng)第二定理理解線性分組碼的糾錯(cuò)原理理解線性分組碼的糾錯(cuò)原理掌握漢明碼的編碼和譯碼掌握漢明碼的編碼和譯碼教學(xué)內(nèi)容和要求教學(xué)內(nèi)容和要求第第5章章 信道編碼信道編碼5.1 聯(lián)合漸近均分性定理聯(lián)合漸近均分性定理1、n次擴(kuò)展信道的聯(lián)合漸進(jìn)均分性次擴(kuò)展信道的聯(lián)合漸進(jìn)均分性例例11 . 09 . 0)X(P9 . 01 . 01 . 09 . 0)X/Y(P二次擴(kuò)展信道相關(guān)符號序列的概率分布特點(diǎn)二次擴(kuò)展信道相關(guān)符號序列的概率分布特點(diǎn)第第5章章 信道編碼信道編碼二次擴(kuò)展信

2、源的概率二次擴(kuò)展信源的概率01. 009. 009. 081. 0)X(P201. 0)11(P99. 009. 0281. 0)10(P)01(P)00(P信源符號序列概率分布特點(diǎn)信源符號序列概率分布特點(diǎn)72. 009. 081. 0)01(P)00(P第第5章章 信道編碼信道編碼二次擴(kuò)展信道的信道矩陣二次擴(kuò)展信道的信道矩陣81. 009. 009. 001. 009. 081. 001. 009. 009. 001. 081. 009. 001. 009. 009. 081. 0)X/Y(P22第第5章章 信道編碼信道編碼二次擴(kuò)展信宿的概率二次擴(kuò)展信宿的概率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信宿符號序列概率分布特點(diǎn)信宿符號序列概率分布特點(diǎn)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信源信宿聯(lián)合符號序列概率分布特點(diǎn)信源信宿聯(lián)合符號序列概率分布特點(diǎn)第第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、聯(lián)合漸進(jìn)均分性定理、聯(lián)合漸進(jìn)均分性定理定理定理典型序列中的符號序列為典型集記)X(Axxxniiin21任意給定任意給定 0，當(dāng)，當(dāng)n足夠大，

7、足夠大，n次擴(kuò)展信源的典型序次擴(kuò)展信源的典型序列滿足列滿足N, 2 , 1i ,i ,i)X(H)xxx(Plogn1n21iiin21第第5章章 信道編碼信道編碼典型序列中的符號序列為典型集記)Y(Ayyynjjjn21同樣的同樣的和和n，n次擴(kuò)展信宿的典型序列滿足次擴(kuò)展信宿的典型序列滿足M, 2 , 1j ,j , j)Y(H)yyy(Plogn1n21jjjn21聯(lián)合典型序列序列中的符號為典型集記)XY(Ayyyxxxnjjjiiin21n21n次擴(kuò)展信道的聯(lián)合典型序列滿足次擴(kuò)展信道的聯(lián)合典型序列滿足第第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，當(dāng)，當(dāng)n1足夠大足夠大由大數(shù)定理由大數(shù)定理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，當(dāng)，當(dāng)n2足夠大足夠大由大數(shù)定理由大數(shù)定理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，當(dāng)，當(dāng)n3足夠大足夠大由大數(shù)定理由大數(shù)

10、定理1)yx(PlogE)yx(Plogn1P)XY(H)yyyxxx(Pn1Pkkkkn21n21jin1kjijjjiii，三式同時(shí)成立取)n,n,nmax(n321第第5章章 信道編碼信道編碼推論推論1的概率為典型序列記n21n21iiiiiixxx)xxx(P的概率為典型序列n21n21jjjjjjyyy)yyy(P的概率為聯(lián)合典型序列n21n21n21n21jjjiiijjjiiiyyyxxx)yyyxxx(P)X(Hniii)X(Hn2)xxx(P2n21)Y(Hnjjj)Y(Hn2)yyy(P2n21)XY(Hnjjjiii)XY(Hn2)yyyxxx(P2n21n21第第5章章

11、 信道編碼信道編碼推論推論2的數(shù)量為典型序列記n21iiinxxx)X(A的數(shù)量為聯(lián)合典型序列n21n21jjjiiinyyyxxx)XY(A)X(Hnn)X(Hn2)X(A2)1 ()Y(Hnn)Y(Hn2)Y(A2)1 (的數(shù)量為典型序列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 香農(nóng)第二定理香農(nóng)第二定理1、平均譯碼錯(cuò)誤概率、平均譯碼錯(cuò)誤概率最小錯(cuò)誤概率準(zhǔn)則下的平均譯碼錯(cuò)誤概率最小錯(cuò)誤概率準(zhǔn)則下的平均譯碼錯(cuò)誤概率定義定義信宿收到信宿收到y(tǒng)j按最大后驗(yàn)概率判斷信源發(fā)送按最大后驗(yàn)概率判斷信源發(fā)送x*xi之一之一譯碼譯碼最小錯(cuò)誤概率準(zhǔn)則最小錯(cuò)誤概率準(zhǔn)則第第5章章 信道編碼

14、信道編碼表示表示M, 2 , 1j*x)y( fN, 2 , 1i)y/x(Pmax)y/*x(Pjjiij則如果平均譯碼錯(cuò)誤概率平均譯碼錯(cuò)誤概率信宿收到信宿收到y(tǒng)j的譯碼錯(cuò)誤概率的譯碼錯(cuò)誤概率)y/*x(P1Pjej第第5章章 信道編碼信道編碼平均譯碼錯(cuò)誤概率平均譯碼錯(cuò)誤概率*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章章 信道編碼信道編碼最大似然準(zhǔn)則下的平均譯碼錯(cuò)誤概率最大似然準(zhǔn)則下的平均譯碼錯(cuò)誤概率最大似然準(zhǔn)則最大似然準(zhǔn)則定義定義信

15、宿收到信宿收到y(tǒng)j按最大轉(zhuǎn)移概率判斷信源發(fā)送按最大轉(zhuǎn)移概率判斷信源發(fā)送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最大似然準(zhǔn)則等同于最小錯(cuò)誤概率準(zhǔn)則最大似然準(zhǔn)則等同于最小錯(cuò)誤概率準(zhǔn)則第第5章章 信道編碼信道編碼平均譯碼錯(cuò)誤概率平均譯碼

16、錯(cuò)誤概率*xxM1jiji*xxM1jji*xxM1jjijeiii)x/y(P)x(P)yx(P)y/x(P)y(PP第第5章章 信道編碼信道編碼2、香農(nóng)第二定理、香農(nóng)第二定理定理定理信道的信道容量為信道的信道容量為C，對，對n次擴(kuò)展信道進(jìn)行信道編次擴(kuò)展信道進(jìn)行信道編碼，對任意給定的碼，對任意給定的 0，只要碼率，只要碼率R C，當(dāng)，當(dāng)n足足夠大，平均譯碼錯(cuò)誤概率夠大，平均譯碼錯(cuò)誤概率Pe C，無論，無論n多大，平均譯碼錯(cuò)誤概率多大，平均譯碼錯(cuò)誤概率Pe 第第5章章 信道編碼信道編碼正定理正定理n2liiicccn的碼字隨機(jī)產(chǎn)生碼長為當(dāng)當(dāng)n足夠大，隨機(jī)產(chǎn)生的碼字為等概率的典型序列，足夠大，隨

17、機(jī)產(chǎn)生的碼字為等概率的典型序列，數(shù)量為數(shù)量為2nH(X)，選取其中，選取其中2nR個(gè)作為許用碼，其余為個(gè)作為許用碼，其余為禁用碼禁用碼發(fā)生譯碼錯(cuò)誤的兩種情況發(fā)生譯碼錯(cuò)誤的兩種情況不構(gòu)成聯(lián)合典型序列與*cccyyyn2ln2liiijjj構(gòu)成聯(lián)合典型序列以外的與n2ln2ln2liiiiiijjjccc*cccyyy調(diào)整信源概率調(diào)整信源概率P(X)，使，使I(X;Y)=C第第5章章 信道編碼信道編碼不失一般性，記不失一般性，記E1*表示第一種情況，表示第一種情況，Ei 表示第二表示第二種情況種情況 i=2,2nR平均譯碼錯(cuò)誤概率平均譯碼錯(cuò)誤概率nRnR22ii1221e)E(P)E(P)EEE(

18、PP nRnRnnj2j1jni2i1in21n2122i3)Y;X( I n22i)XY(Ayyycccjjjiii2)yyy(P)ccc (P第第5章章 信道編碼信道編碼3CRn3CnnR22i3Cn22) 12(2nR3CR只要eP當(dāng)當(dāng)n足夠大足夠大第第5章章 信道編碼信道編碼5.3 費(fèi)諾不等式與香農(nóng)第二定理的逆定理費(fèi)諾不等式與香農(nóng)第二定理的逆定理1、費(fèi)諾不等式、費(fèi)諾不等式n次擴(kuò)展信道的損失熵次擴(kuò)展信道的損失熵H(Xn/Yn)與平均譯碼錯(cuò)誤概與平均譯碼錯(cuò)誤概率率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，數(shù)量為，數(shù)量為2nR的任意碼字，如果的任意碼字，如果R C，當(dāng)當(dāng)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章章 信道編碼信道編碼香農(nóng)第二定理表明了平均譯碼錯(cuò)誤概率任意小的香農(nóng)第二定理表明了平均譯碼錯(cuò)誤概率任意小的信道編碼的存在性，明確了信道容量信道編碼的存在性，明確了信道容量C是信道編碼是信道編碼的碼率上界的碼率上界香農(nóng)界香農(nóng)界第第5章章 信道編碼信道編碼5.4 糾錯(cuò)與線性分組碼的編碼原則糾錯(cuò)與線性分組碼的編碼原則1、糾錯(cuò)、糾錯(cuò)信道編碼信道編碼通過在發(fā)送端增加冗余使消息出現(xiàn)傳輸錯(cuò)誤時(shí)由通過在發(fā)送端增加冗余使消息出現(xiàn)傳輸錯(cuò)誤時(shí)由接收端自動(dòng)進(jìn)行糾正接收端自動(dòng)進(jìn)行糾正糾錯(cuò)糾錯(cuò)

25、第第5章章 信道編碼信道編碼2、n重復(fù)碼重復(fù)碼例例199. 001. 001. 099. 0)X/Y(P信源等概率時(shí)的平均譯碼錯(cuò)誤概率信源等概率時(shí)的平均譯碼錯(cuò)誤概率第第5章章 信道編碼信道編碼最大似然準(zhǔn)則譯碼最大似然準(zhǔn)則譯碼收到收到y(tǒng)1時(shí)時(shí)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收到收到y(tǒng)2時(shí)時(shí)第第5章章 信道編碼信道編碼平均譯碼錯(cuò)誤概率平均譯碼錯(cuò)誤概率01. 0)01. 001. 0 (21)x/y(P)x(P

26、)x/y(P)x(P)x/y(P)x(PP212121*xx21jijiei通信系統(tǒng)中一般要求平均譯碼錯(cuò)誤概率的數(shù)量級通信系統(tǒng)中一般要求平均譯碼錯(cuò)誤概率的數(shù)量級10-6 -10-9第第5章章 信道編碼信道編碼三重復(fù)碼三重復(fù)碼消息重復(fù)三次消息重復(fù)三次x1=0c1=000，x2=1c2=111三次擴(kuò)展信源的子信源，三次擴(kuò)三次擴(kuò)展信源的子信源，三次擴(kuò)展信宿展信宿三次擴(kuò)展信道的子信道三次擴(kuò)展信道的子信道9703. 00098. 00098. 0000099. 00098. 0000099. 0000099. 0000001. 0000001. 0000099. 0000099. 00098. 0000

27、099. 00098. 00098. 09703. 0)X/Y(P331第第5章章 信道編碼信道編碼最大似然準(zhǔn)則譯碼最大似然準(zhǔn)則譯碼收到收到y(tǒng)1=000時(shí)時(shí)000c*c)000( f2 , 1i9703. 0000001. 0 ,9703. 0max)c/000(Pmax*)c/000(P1ii收到收到y(tǒng)2=001時(shí)時(shí)000c*c)001( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/001(Pmax*)c/001(P1ii第第5章章 信道編碼信道編碼收到收到y(tǒng)3=010時(shí)時(shí)000c*c)010( f2 , 1i0098. 0000099. 0 ,0098. 0

28、max)c/010(Pmax*)c/010(P1ii收到收到y(tǒng)4=011時(shí)時(shí)111c*c)011( f2 , 1i0098. 00098. 0 ,000099. 0max)c/011(Pmax*)c/011(P2ii收到收到y(tǒng)5=100時(shí)時(shí)000c*c)100( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/100(Pmax*)c/100(P1ii第第5章章 信道編碼信道編碼收到收到y(tǒng)6=101時(shí)時(shí)111c*c)101( f2 , 1i0098. 00098. 0 ,000099. 0max)c/101(Pmax*)c/101(P2ii收到收到y(tǒng)7=110時(shí)時(shí)11

29、1c*c)110( f2 , 1i0098. 00098. 0 ,000099. 0max)c/110(Pmax*)c/110(P2ii收到收到y(tǒng)8=111時(shí)時(shí)111c*c)111( f2 , 1i9703. 09703. 0 ,000001. 0max)c/111(Pmax*)c/111(P2ii第第5章章 信道編碼信道編碼三重復(fù)碼三重復(fù)碼通過在發(fā)送端增加冗余使消息出現(xiàn)一通過在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯(cuò)誤時(shí)由接收端進(jìn)行糾正位傳輸錯(cuò)誤時(shí)由接收端進(jìn)行糾正糾錯(cuò)糾錯(cuò)000)100( f000)010( f000)001( f000)000( f111)111( f111)110( f111)

30、101( f111)011( f第第5章章 信道編碼信道編碼平均譯碼錯(cuò)誤概率平均譯碼錯(cuò)誤概率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章章 信道編碼信道編碼重復(fù)重復(fù)n次次n重復(fù)碼重復(fù)碼10e8e7e5e105P11n10P9n104P7n10P5n，n重復(fù)碼的碼長為原來的重復(fù)碼的碼長為原來的n倍倍編碼效率為編碼效率為1/n第第5章章 信道編碼信道編碼需要找的需要找的“好碼好碼”足

31、夠小的平均譯碼錯(cuò)誤概率足夠小的平均譯碼錯(cuò)誤概率Pe較高的編碼效率較高的編碼效率第第5章章 信道編碼信道編碼3、線性分組碼及其編碼原則、線性分組碼及其編碼原則線性分組碼線性分組碼定義定義具有恒定碼字長度和消息長度，消息相加后的編具有恒定碼字長度和消息長度，消息相加后的編碼等同于各自編碼相加的糾錯(cuò)碼碼等同于各自編碼相加的糾錯(cuò)碼表示表示(n,k)其中其中n為碼字長度，為碼字長度，k為消息長度，為消息長度，n-k為為校驗(yàn)長度校驗(yàn)長度第第5章章 信道編碼信道編碼例例2(4,3)偶校驗(yàn)碼偶校驗(yàn)碼0110c011x0101c010 x0011c001x0000c000 x443322111111c111x1

32、100c110 x1010c101x1001c100 x88776655100110100011cc1001100101001xx6262第第5章章 信道編碼信道編碼碼距和最小碼距碼距和最小碼距2k個(gè)碼字構(gòu)成的碼表中，任意兩個(gè)碼字之間的碼距個(gè)碼字構(gòu)成的碼表中，任意兩個(gè)碼字之間的碼距(漢明距離漢明距離)定義定義任意兩個(gè)碼字對應(yīng)位上不同碼元的個(gè)數(shù)任意兩個(gè)碼字對應(yīng)位上不同碼元的個(gè)數(shù)表示表示ji ,2 , 2 , 1j , icc)c ,c (ddkn1ljijiijll第第5章章 信道編碼信道編碼例例3(4,3)偶校驗(yàn)碼中碼字偶校驗(yàn)碼中碼字c2和和c3之間的碼距之間的碼距d230101c0011c3

33、22ccd41l3223ll第第5章章 信道編碼信道編碼2k個(gè)碼字構(gòu)成的碼表中，碼字之間的最小碼距個(gè)碼字構(gòu)成的碼表中，碼字之間的最小碼距定義定義所有碼字之間碼距的最小值所有碼字之間碼距的最小值表示表示ji ,2 , 2 , 1j , idmindkijj , imin第第5章章 信道編碼信道編碼線性分組碼的編碼原則線性分組碼的編碼原則例例4(3,1)線性分組碼線性分組碼三次擴(kuò)展信源中三次擴(kuò)展信源中8個(gè)可能的碼字個(gè)可能的碼字111c011c110c010c101c001c100c000c84736251第第5章章 信道編碼信道編碼8個(gè)可能的碼字構(gòu)成的碼表中，任意兩個(gè)碼字之間個(gè)可能的碼字構(gòu)成的碼表

34、中，任意兩個(gè)碼字之間的碼距的碼距1dddddddddddd8786756584734362425131212dddddddddddd7685746483538252327161413dddd54637281第第5章章 信道編碼信道編碼如果選取其中如果選取其中c1=000，c8=111為許用碼，其余為禁為許用碼，其余為禁用碼用碼三重復(fù)碼三重復(fù)碼2個(gè)碼字構(gòu)成的碼表中個(gè)碼字構(gòu)成的碼表中3dmind81min99. 001. 001. 099. 0)X/Y(P及信源等概率條件下的平均譯碼錯(cuò)誤概率及信源等概率條件下的平均譯碼錯(cuò)誤概率在信道在信道4e103P第第5章章 信道編碼信道編碼如果選取其中如果選取

35、其中c2=001，c7=110為許用碼，其余為禁為許用碼，其余為禁用碼用碼2個(gè)碼字構(gòu)成的碼表中個(gè)碼字構(gòu)成的碼表中3dmind27min99. 001. 001. 099. 0)X/Y(P及信源等概率條件下及信源等概率條件下在信道在信道第第5章章 信道編碼信道編碼x=0c2=001，x=1c7=110三次擴(kuò)展信源的子三次擴(kuò)展信源的子信源，三次擴(kuò)展信宿信源，三次擴(kuò)展信宿三次擴(kuò)展信道的子信道三次擴(kuò)展信道的子信道0098. 09703. 0000099. 00098. 0000099. 00098. 0000001. 0000099. 0000099. 0000001. 00098. 0000099.

36、 00098. 0000099. 09703. 00098. 0)X/Y(P332第第5章章 信道編碼信道編碼最大似然準(zhǔn)則譯碼最大似然準(zhǔn)則譯碼收到收到y(tǒng)1=000時(shí)時(shí)001c*c)000( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/000(Pmax*)c/000(P2ii收到收到y(tǒng)2=001時(shí)時(shí)001c*c)001( f2 , 1i9703. 0000001. 0 ,9703. 0max)c/001(Pmax*)c/001(P2ii第第5章章 信道編碼信道編碼收到收到y(tǒng)3=010時(shí)時(shí)110c*c)010( f2 , 1i0098. 00098. 0 ,0000

37、99. 0max)c/010(Pmax*)c/010(P7ii收到收到y(tǒng)4=011時(shí)時(shí)001c*c)011( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/011(Pmax*)c/011(P2ii收到收到y(tǒng)5=100時(shí)時(shí)110c*c)100( f2 , 1i0098. 00098. 0 ,000099. 0max)c/100(Pmax*)c/100(P7ii第第5章章 信道編碼信道編碼收到收到y(tǒng)6=101時(shí)時(shí)001c*c)101( f2 , 1i0098. 0000099. 0 ,0098. 0max)c/101(Pmax*)c/101(P2ii收到收到y(tǒng)7=11

38、0時(shí)時(shí)110c*c)110( f2 , 1i9703. 09703. 0 ,000001. 0max)c/110(Pmax*)c/110(P7ii收到收到y(tǒng)8=111時(shí)時(shí)110c*c)111( f2 , 1i0098. 00098. 0 ,000099. 0max)c/111(Pmax*)c/111(P7ii第第5章章 信道編碼信道編碼通過在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯(cuò)誤時(shí)通過在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯(cuò)誤時(shí)由接收端進(jìn)行糾正由接收端進(jìn)行糾正糾錯(cuò)糾錯(cuò)001)101( f001)011( f001)001( f001)000( f110)111( f110)110( f110)100

39、( f110)010( f第第5章章 信道編碼信道編碼平均譯碼錯(cuò)誤概率平均譯碼錯(cuò)誤概率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個(gè)碼字構(gòu)成的碼表中個(gè)碼字構(gòu)成的碼表中2dmind71min99. 001. 001. 099. 0)X/Y(P及信源等概率條件下及信源等

40、概率條件下在信道在信道第第5章章 信道編碼信道編碼x=0c1=000，x=1c7=110三次擴(kuò)展信源的子三次擴(kuò)展信源的子信源，三次擴(kuò)展信宿信源，三次擴(kuò)展信宿三次擴(kuò)展信道的子信道三次擴(kuò)展信道的子信道0098. 09703. 0000099. 00098. 0000099. 00098. 0000001. 0000099. 0000001. 0000099. 0000099. 00098. 0000099. 00098. 00098. 09703. 0)X/Y(P333第第5章章 信道編碼信道編碼最大似然準(zhǔn)則譯碼最大似然準(zhǔn)則譯碼收到收到y(tǒng)1=000時(shí)時(shí)000c*c)000( f2 , 1i9703

41、. 0000099. 0 ,9703. 0max)c/000(Pmax*)c/000(P1ii收到收到y(tǒng)2=001時(shí)時(shí)000c*c)001( f2 , 1i0098. 0000001. 0 ,0098. 0max)c/001(Pmax*)c/001(P1ii第第5章章 信道編碼信道編碼收到收到y(tǒng)3=010時(shí)時(shí)110c*c)010( f000c*c)010( f2 , 1i0098. 00098. 0 ,0098. 0max)c/010(Pmax*)c/010(P71ii或收到收到y(tǒng)4=011時(shí)時(shí)110c*c)011(f000c*c)011(f2 , 1i000099. 0000099. 0 ,

42、000099. 0max)c/011(Pmax*)c/011(P71ii或收到收到y(tǒng)5=100時(shí)時(shí)110c*c)100( f000c*c)100( f2 , 1i0098. 00098. 0 ,0098. 0max)c/100(Pmax*)c/100(P71ii或第第5章章 信道編碼信道編碼收到收到y(tǒng)6=101時(shí)時(shí)110c*c)101( f000c*c)101( f2 , 1i000099. 0000099. 0 ,000099. 0max)c/101(Pmax*)c/101(P71ii或收到收到y(tǒng)7=110時(shí)時(shí)110c*c)110( f2 , 1i9703. 09703. 0 ,000099

43、. 0max)c/110(Pmax*)c/110(P7ii收到收到y(tǒng)8=111時(shí)時(shí)110c*c)111( f2 , 1i0098. 00098. 0 ,000001. 0max)c/111(Pmax*)c/111(P7ii第第5章章 信道編碼信道編碼通過在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯(cuò)誤時(shí)通過在發(fā)送端增加冗余使消息出現(xiàn)一位傳輸錯(cuò)誤時(shí)不能完全由接收端進(jìn)行糾正不能完全由接收端進(jìn)行糾正110)111( f110)110( f110/000)100( f110/000)010( f000)001( f000)000( f110/100)101( f110/100)011( f第第5章章 信道編碼信

44、道編碼平均譯碼錯(cuò)誤概率平均譯碼錯(cuò)誤概率*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章章 信道編碼信道編碼線性分組碼檢錯(cuò)糾錯(cuò)的充要條件線性分組碼檢錯(cuò)糾錯(cuò)的充要條件線性分組碼線性分組碼(n,k) 檢檢e位錯(cuò)并同時(shí)糾

45、位錯(cuò)并同時(shí)糾t位錯(cuò)的充要條位錯(cuò)的充要條件件1tedmin檢一位錯(cuò)并同時(shí)糾一位錯(cuò)的充要條件檢一位錯(cuò)并同時(shí)糾一位錯(cuò)的充要條件3dmin第第5章章 信道編碼信道編碼5.5 漢明碼漢明碼漢明碼漢明碼最小碼距最小碼距dmin=3的線性分組碼的線性分組碼設(shè)設(shè)(n,k)漢明碼的碼字漢明碼的碼字kiiiiiii2 , 2 , 1icccccccn2k1kk21為校驗(yàn)位，校驗(yàn)長度為為校驗(yàn)位，校驗(yàn)長度為n-kn2k1kiiiccc其中其中 為消息位，消息長度為為消息位，消息長度為kk21iiiccckk2211iiiiiixc ,xc ,xc一般第第5章章 信道編碼信道編碼1、漢明碼的編碼、漢明碼的編碼編碼步驟編

46、碼步驟構(gòu)造滿秩的構(gòu)造滿秩的(n-k)n校驗(yàn)矩陣校驗(yàn)矩陣HkTii2 , 2 , 1iHrsri第第i個(gè)接收碼字，個(gè)接收碼字，1n向量向量si第第i個(gè)接收碼字的誤碼標(biāo)志，個(gè)接收碼字的誤碼標(biāo)志，1(n-k)向量向量1n2kn其中0HcHrscrTiTiiii ，取當(dāng)ci第第i個(gè)發(fā)送碼字，個(gè)發(fā)送碼字，1n向量向量第第5章章 信道編碼信道編碼設(shè)滿秩的設(shè)滿秩的kn生成矩陣生成矩陣GGI G)kn(kkk一般kii2 , 2 , 1iGxcxi第第i個(gè)發(fā)送消息，個(gè)發(fā)送消息，1k向量向量由生成矩陣由生成矩陣G與校驗(yàn)矩陣與校驗(yàn)矩陣H之間之間GHT=0求出求出G即可即可編碼編碼第第5章章 信道編碼信道編碼例例1

47、(3,1)漢明碼漢明碼構(gòu)造滿秩的構(gòu)造滿秩的23校驗(yàn)矩陣校驗(yàn)矩陣H所有所有2維非零列向量構(gòu)成校驗(yàn)矩陣維非零列向量構(gòu)成校驗(yàn)矩陣H，如，如101110H1n4222kn其中第第5章章 信道編碼信道編碼設(shè)滿秩的設(shè)滿秩的13生成矩陣生成矩陣Ggg1 G3200110110gg1 GH32T由0g10gg3321g1g32 111 G第第5章章 信道編碼信道編碼2 , 1ixxx 111xGxccc ciiiiiiiii321111c1x000c0 x2211最小碼距最小碼距3dmind12min(3,1)漢明碼漢明碼三重復(fù)碼能檢一位錯(cuò)并同時(shí)糾一位三重復(fù)碼能檢一位錯(cuò)并同時(shí)糾一位錯(cuò)錯(cuò)(3,1)漢明碼的碼長為

48、原來的漢明碼的碼長為原來的3倍倍編碼效率為編碼效率為1/3第第5章章 信道編碼信道編碼例例2(7,4)漢明碼的編碼漢明碼的編碼構(gòu)造滿秩的構(gòu)造滿秩的37校驗(yàn)矩陣校驗(yàn)矩陣H所有所有3維非零列向量構(gòu)成校驗(yàn)矩陣維非零列向量構(gòu)成校驗(yàn)矩陣H，如，如101010111001101111000H1n8223kn其中第第5章章 信道編碼信道編碼設(shè)滿秩的設(shè)滿秩的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