信息論基礎(chǔ)教案-第六章 無失真信源編碼

1、第六章第六章 無失真信源編碼無失真信源編碼信 源信源編碼信道編碼信 道信 宿信源譯碼信道譯碼信源編碼：1. 信源適合信道傳輸2. 無失真?zhèn)鬏?. 有效傳輸減少信源的剩余度第一節(jié)第一節(jié) 單義可譯定理單義可譯定理（一）適合信道傳輸,.,:21qsssS,.,:21raaaX無噪信道編碼器,.,:21qsssS,.,:21raaaX信 道raaa21qwww21qqwswsws2211,.,:21qwwwW碼字（二）單義可譯：1. ),.,2 , 1(),.,2 , 1(qisqiwii碼字與信源符號(hào)一一對(duì)應(yīng)2. 不同的符號(hào)序列不同的碼字序列例：1.1101104321ssss1s3s2s4s奇異碼

2、2.01001004321ssss非奇異碼0 1 0 0 0 0 1 014321sssss0 1 0 0 0 0 1 02334ssss3.111001004321ssss等長(zhǎng)碼非奇異碼0 0 0 1 1 0 1 14321ssss單義可譯4.10001001014321ssss非奇異碼1 1 0 1 0 0 1 0 0 0單義可譯1 0?2s01不即時(shí)任何一個(gè)碼字是其它碼字的延長(zhǎng)或前綴5.00010010114321ssss非奇異碼1 0 1 0 0 1 0 0 0 1單義可譯0 12s即時(shí)任何一個(gè)碼字不是其它碼字的延長(zhǎng)或前綴即 時(shí) 碼（三）即時(shí)碼（非延長(zhǎng)碼）碼樹1 , 0:X2r 010

3、10100010110110101000 001 010 0110101000 001 010 011一階節(jié)點(diǎn)二階節(jié)點(diǎn)三階節(jié)點(diǎn)r1r2r3（四）單義可譯定理定理定理：設(shè)信源S的符號(hào)集為S：s1,s2,sq，碼符號(hào)集X:a1,a2,ar，又設(shè)碼字為W:w1,w2,wq其碼長(zhǎng)分別為n1,n2,nq。則存在單義可譯碼的充分必要條件是：q，r，ni(i=1,2,q)滿足Kraft不等式，即：qinir11必要性：非用盡：nnnnnnnrrrrrrrq21用盡：nnnnnnnrrrrrrrq21qinir11充分性： qqnnn21121 mm1111111 bbmmbmmrrrrrrmm11111rb

4、rbrbmmmm111rb11122rbrb1112233rbrbrb11111rbrbrbmmmmrb 1)(12brrb)(213bbrrrbrbrbrbrbmmmmm12211單義Kraft不等式非延長(zhǎng)碼第二節(jié)第二節(jié) 碼率與有效編碼碼率與有效編碼qqqqnwspsnwspsnwsps)()()(22221111平均碼長(zhǎng)：qiiinspn1)(碼符/信符qiiispspSH1)(log)()(bit/信符nSHR)(bit/信符碼符/信符=bit/碼符碼率n有效性qiiinspn1)(iinsp)(iinsp)(nHuffman碼：例1：1 . 01 . 02 . 02 . 04 . 0:

5、 54321sssssPX1 , 0:X1 . 0:1 . 0:2 . 0:2 . 0:4 . 0:54321sssss014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016 . 04 . 00111w012w0003w00104w00115wqS :) 1(:1 rqS) 1(2:2rqS) 1(3:3rqS) 1( rqr例2：08. 014. 016. 018. 020. 024. 0: 654321ssssssPX2 , 1 , 0:X) 1( rq2) 13(260)(:11sps3) 13(2700. 0:08. 0:14. 0:16. 0:18. 0

6、:20. 0:24. 0:1654321sssssss01222. 024. 020. 018. 016. 001254. 024. 022. 001211w002w013w024w205w216w227w1 . 0:1 . 0:2 . 0:2 . 0:4 . 0:54321sssss014 . 02 . 02 . 02 . 0014 . 04 . 02 . 0016 . 04 . 00111w012w0003w00104w00115w2 . 2)(1qiiinspn碼符/信符1 . 0:1 . 0:2 . 0:2 . 0:4 . 0:54321sssss014 . 02 . 02 . 02

7、. 0014 . 04 . 02 . 0016 . 04 . 001111w012w003w1014w1005w2 . 2)(1qiiinspn碼符/信符)(22nnEiw51222136. 1)()(iiiiWnnspnnE51222216. 0)()(iiiiWnnspnnE第三節(jié)第三節(jié) 平均碼長(zhǎng)界限定理平均碼長(zhǎng)界限定理1log)(log)(rSHnrSH0log)(rnSHqiqiiiiirnspspsp11log)()(log)(qiqiniiiirspspsp11log)()(log)(qiqiniiiirspspsp11log)()(log)(qiinisprspi1)(log)(

8、)()(log1qiinisprspilog1qinir01log rSHnlog)(),.,2 , 1()(qirspini平均碼長(zhǎng)=下限值最佳碼ririririiiSHspsprspsprSH11)()(log)(log)(log)(log)(),.,2 , 1()(qirspini),.,2 , 1()(logqinspiir),.,2 , 1()(logqinspiir1)(log)(logiriirspnsp)(log)(1logiriirsprnsp)()(1inisprrspirsprspinii)()(qiiqinqiirsprspi111)()(rrqini1111)(log)(logiriirspnspqiiqiiriiiqiqiirispspspnspspsp1111)()(log)()()(log)(1log)(log)(rSHnrSHNNSSSS211log)(log)(rSHnrSHNNNNrNSHNnrNSHNNN1log)(log)(rSHnNlog)(limNSSSS211log)(log)(rSHnrSHNNrNSHNnrNSHN1log)(l