《第4章无失真信源编码》由会员分享，可在线阅读，更多相关《第4章无失真信源编码（11页珍藏版）》请在金锄头文库上搜索。
1、第 4 章 无失真信源编码一、例题：【例 4.1】设一个离散无记忆信源的概率空间为123411118842ssssSP采用两种信源编码方案编出的码字如表4.1 所示。表 4.1 例 4.1 两种信源编码方案信源符号概率方案一的码字方案二的码字1s1/8 00 000 2s1/8 01 001 3s1/4 10 01 4s1/2 11 1 试问方案一和方案二的码字哪个有效性较好？解： 信源熵( )1.75H Sbit/符号，所以，方案一编码后每个码元载荷的平均信息量为0.875bit，即编码后的信息传输率875.0Rbit/码元。方案二编码后每个码元载荷的平均信息量为 1bit，即编码后的信息传
2、输率1Rbit/码元。由于每个二进制码元所能携带的最大信息量为1bit，所以方案二是一种最佳编码。可见通过信源编码， 新信源尽可能等概地使用各个码符号，消除了原始信源各符号出现概率的不均匀性，从而提高信息传输的有效性。【例 4.2】设一个离散无记忆信源的概率空间为123411118842ssssSP若对该信源采取等长二元编码，要求编码效率9 .0，允许译码错误概率510，试计算需要的信源序列长度N为多少？解： 信源熵为111( )2log8log 4log21.75842 Sbit/符号自信息量的方差22212222( )log( )1111112logloglog1.750.68758844
3、22qii iSppH S因为编码效率9.0，可得10.1944HS可得2 6 225()0.68751.819 100.194410SN所以，信源序列长度达到610819.1以上，才能实现给定的要求，这在实际中是很难实现的。因此等长编码没有实际意义，实际中一般都采用变长编码。【例 4.3】设离散无记忆信源的概率空间为123144ssSP信源熵为134( )log 4log0 811443 S.bit/符号如果采用二元定长编码：120,1ss。这时平均码长/1L二元码符号信源符号所以，编码效率1( )0.811H SL如果对长度2N的信源序列进行变长编码，如表4.2 所示。表 4.2 例 4.
4、3 中2N时信源序列的变长编码信源序列i()iP变长码1 1ss12ss21s s22s s9/16 3/16 3/16 1/16 0 10 110 111 此时，信源序列的平均码长2/2716L二元码符号信源序列则单个符号的平均码长2/27232LL二元码符号信源符号所以对长度为2 的信源序列进行变长编码，编码后的编码效率2( )0.961H SL如果对信源采取等长二元编码，要求编码效率96.0，允许译码错误概率510，可以算出：当信源序列长度达到71013.4以上，才能满足给定的要求。而采用变长码，只需要信源序列长度2N编码效率就可达到0.961，而且可实现无失真信源编码。用同样的方法进一
5、步将信源序列的长度增加，对3N，4N的序列， 可得编码效率为0.991,0.98543显然，随着信源序列的长度增加，编码效率越来越接近1，编码后信道的信息传输率也越来越接近无噪无损二元信道的信道容量，实现信源与信道的匹配。【例 4.4】对于二元码，即2r，如果4q，12L，22L，32L，42L，是否存在这样的唯一可译码和即时码？解： 因为22221222221iq Li所以满足克拉夫特不等式，则一定可以构成至少一种具有这样码长的唯一可译码和即时码。【例 4.5】已知信源共6 个符号消息，其概率空间为123456 ( )0.20.190.180.170.150.11SssssssP S试进行香
6、农编码。解：下面以消息5s为例来介绍香农编码。计算5log()log0.152.74p，取整数53L作为5s的码长。计算1234,s s s s的累加概率，有45 10.20.190.180.170.74k kPp将 0.74 变换成二进制小数102(0.74)(0.1011110)，取小数点后面三位101 作为5s的代码。其余消息的代码可以用相同的方法计算得到，如表4.3 所示。表 4.3 例 4.5 中的香农编码信息符号is符号概率()iP s累加概率iPlog( )iP s码字长度iL码字iW1s0.20 0 2.34 3 000 2s0.19 0.20 2.41 3 001 3s0.1
7、8 0.39 2.48 3 011 4s0.17 0.57 2.56 3 100 5s0.15 0.74 2.74 3 101 6s0.11 0.89 3.18 4 1110 信源熵：1( )( )log()2.61qii iH SP sP sbit/符号平均码长：1()30.8940.113.11qii iLP s L码元 /符号编码效率：( )2.610.8393.11H SL【例 4.6】某离散无记忆信源共有8 个符号消息，其概率空间为12345678 0.400.180.100.100.070.060.050.04SssssssssP试进行霍夫曼编码，并计算编码后的信息传输率和编码效率
8、。解：编码过程如图4.1 所示01011.000.600.370.23010.19010.13010.0901010.040.050.060.070.100.100.180.40s1s2s3s4s5s6s7s8图 4.1 例 4.6 的霍夫曼编码信源熵：1( )( )log()2.55qii iH SP sP sbit/符号平均码长：1()qii iLP s L2.61码元 /符号信源符号码字码长s11 1 s2001 3 s3011 3 s40000 4 s50100 4 s60101 4 s700010 5 s800011 5 编码效率：( )2.550.9972.61H SL【例 4.7
9、】某离散无记忆信源共有5 个符号消息，其概率空间为12345 0.40.20.20.10.1SsssssP两种霍夫曼编码分别如图4.2 和图 4.3 所示。01011.00.60.201010.4s1s2s3s4s50.40.20.20.10.1图 4.2 例 4.7 第一种霍夫曼编码01011.00.60.201010.4s1s2s3s4s50.40.20.20.10.1图 4.3 例 4.7 第二种霍夫曼编码第一种霍夫曼编码的平均码长1 1()2.2qii iLP s L码元 /符号信源符号码字码长s100 2 s210 2 s311 2 s4010 3 s5011 3 信源符号码字码长s
10、11 1 s201 2 s3000 3 s40010 4 s50011 4 码方差12221()()()0.16qLiii iELLP sLL第二种霍夫曼编码的平均码长2 1()2.2qii iLP s L码元 /符号码方差22221()()()1.36qLiii iELLP sLL可见，两种码有相同的平均码长和编码效率，但第一种霍夫曼编码的码方差比第二种霍夫曼编码的码方差小许多，所以第一种霍夫曼编码的质量较好。从此例可以看出，进行霍夫曼编码时， 应把合并后的概率总是放在其他相同概率的信源符号之上，以得到码方差最小的码。【例 4.8】设离散无记忆信源的概率空间为12 0.70.3SssP， 对
11、信源进行N次扩展，采用霍夫曼编码。当N = 1，2，3，时的平均码长和编码效率为多少？解：（1）N = 1 时，将1s编成 0，2s编成 1，则11L又因为信源熵1()( )log()0.8816qii iH SP sP sbit/符号所以1 1( )0.8816H SL（2）N = 2 时，编码过程如下2S概率霍夫曼编码1 1ss0.49 1 12ss0.21 01 2 1s s0.21 000 22s s0.09 001 所以21 0.492 0.213 (0.210.09)1.81L则20.9052L所以2( )0.9740.905H S（3）N = 3 时，有32.726L则30.90
12、93L所以3( )0.9700.909H S（4）N = 时，由香农第一定理可知，必然存在唯一可译码，使lim( )N rNLHSN而霍夫曼编码为最佳码，即平均码长最短的码，故lim( )( )0.8816N rNLHSH SN即lim1NN【例 4.9】已知离散无记忆信源12345 0.40.30.20.050.05SsssssP其三元霍夫曼编码如图4.4 所示，四元霍夫曼编码如图4.5 所示。并计算编码效率。010.320121.0s1s2s3s4s50.40.30.20.050.05图 4.4 三元霍夫曼编码010.12011.0s1s2s3s4s50.40.30.20.050.05 2
13、3s6s7003图 4.5 四元霍夫曼编码信源熵：1( )()log()1.95qii iH SP sP sbit/符号三元霍夫曼编码的平均码长：1()1.3qii iLP s L码元 /符号信源符号码字码长s10 1 s21 1 s320 2 s421 2 s522 4 信源符号码字码长s10 1 s21 1 s32 1 s430 2 s531 2 s632 2 s733 2 所以，三元霍夫曼编码的编码效率：( )1.950.947log1.3log3H SLr四元霍夫曼编码的平均码长：1()1.1qii iLP s L码元 /符号所以，四元霍夫曼编码的编码效率()1.950.886log1
14、.1 log 4H SLr【例 4.10】某离散无记忆信源共有8 个符号消息，其概率空间为12345678 0.400.180.100.100.070.060.050.04SssssssssP试进行费诺编码，并计算编码后的信息传输率和编码效率。解：费诺编码步骤如表4.4 所示表 4.4 例 4.10 的费诺编码信源符号概率第一次分组第二次分组第三次分组第四次分组所得码字码长s10.40 0 0 00 2 s20.18 0 1 01 2 s30.10 1 0 0 100 3 s40.10 1 0 1 101 3 s50.07 1 1 0 0 1100 4 s60.06 1 1 0 1 1101
15、4 s70.05 1 1 1 0 1110 4 s80.04 1 1 1 1 1111 4 信源熵：1( )( )log()2.55qii iH SP sP sbit/符号平均码长：1()2.64qii iLP s L码元 /符号编码效率：( )2.550.9662.64H SL未编码时，信息效率为max()( )2.550.85( )log3H SH SHSq。可见，经过编码后，信息效率得到了明显的改进。二、讨论题：1、为了做到既有效又可靠地传输信息，编码一般如何进行？2、编码后信息传输率和编码信息率的含义是否相同？3、如何理解香农第一定理？它和无失真定长信源编码定理有何联系？三、思考题：1、平均码长、编码后信息传输率和编码效率有什么关系？2、克拉夫特不等式的含义是什么？3、最佳码有哪些性质？4、霍夫曼编码的步骤是什么？5、霍夫曼编码得到的码是否是唯一的？如何衡量编码的质量？
