信息论基础教案-第六章 无失真信源编码

1、第六章第六章 无失真信源编码无失真信源编码信 源信源编码信道编码信 道信 宿信源译码信道译码信源编码：1. 信源适合信道传输2. 无失真传输3. 有效传输减少信源的剩余度第一节第一节 单义可译定理单义可译定理（一）适合信道传输,.,:21qsssS,.,:21raaaX无噪信道编码器,.,:21qsssS,.,:21raaaX信 道raaa21qwww21qqwswsws2211,.,:21qwwwW码字（二）单义可译：1. ),.,2 , 1(),.,2 , 1(qisqiwii码字与信源符号一一对应2. 不同的符号序列不同的码字序列例：1.1101104321ssss1s3s2s4s奇异码

2、2.01001004321ssss非奇异码0 1 0 0 0 0 1 014321sssss0 1 0 0 0 0 1 02334ssss3.111001004321ssss等长码非奇异码0 0 0 1 1 0 1 14321ssss单义可译4.10001001014321ssss非奇异码1 1 0 1 0 0 1 0 0 0单义可译1 0?2s01不即时任何一个码字是其它码字的延长或前缀5.00010010114321ssss非奇异码1 0 1 0 0 1 0 0 0 1单义可译0 12s即时任何一个码字不是其它码字的延长或前缀即 时 码（三）即时码（非延长码）码树1 , 0:X2r 010

3、10100010110110101000 001 010 0110101000 001 010 011一阶节点二阶节点三阶节点r1r2r3（四）单义可译定理定理定理：设信源S的符号集为S：s1,s2,sq，码符号集X:a1,a2,ar，又设码字为W:w1,w2,wq其码长分别为n1,n2,nq。则存在单义可译码的充分必要条件是：q，r，ni(i=1,2,q)满足Kraft不等式，即：qinir11必要性：非用尽：nnnnnnnrrrrrrrq21用尽：nnnnnnnrrrrrrrq21qinir11充分性： qqnnn21121 mm1111111 bbmmbmmrrrrrrmm11111rb

4、rbrbmmmm111rb11122rbrb1112233rbrbrb11111rbrbrbmmmmrb 1)(12brrb)(213bbrrrbrbrbrbrbmmmmm12211单义Kraft不等式非延长码第二节第二节 码率与有效编码码率与有效编码qqqqnwspsnwspsnwsps)()()(22221111平均码长：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第三节第三节 平均码长界限定理平均码长界限定理1log)(log)(rSHnrSH0log)(rnSHqiqiiiiirnspspsp11log)()(log)(qiqiniiiirspspsp11log)()(log)(qiqiniiiirspspsp11log)()(log)(qiinisprspi1)(log)(

8、)()(log1qiinisprspilog1qinir01log rSHnlog)(),.,2 , 1()(qirspini平均码长=下限值最佳码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