第三章-无失真信源编码解析

第3章 无失真离散信源编码习题3.1 设信源1234567()0.20.190.180.170.150.10.01X a a a a a a a P X(1) 求信源熵H (X )； (2) 编二进制香农码；(3) 计算其平均码长及编码效率。

解： (1)()()log ()(.log ..log ..log ..log ..log ..log ..log .).7212222222=-020201901901801801701701501501010010012609 i i i H X p a p a bit symbol(2)a i p (a i ) p a (a i ) k i 码字 a 1 0.2 0 3 000 a 2 0.19 0.2 3 001 a 3 0.18 0.39 3 011 a 4 0.17 0.57 3 100 a 5 0.15 0.74 3 101 a 6 0.1 0.89 4 1110 a 70.010.9971111110(3)()3(0.2+0.19+0.18+0.17+0.15)+40.1+70.01=3.1471i i i K k p a()() 2.609=83.1%3.14H X H X R K3.2 对习题3.1的信源编二进制费诺码，计算其编码效率。

解：a i p (a i ) 编 码 码字 k i a 1 0.2 000 2 a 2 0.19 1 0 010 3 a 3 0.18 1 011 3 a 4 0.17 110 2 a 5 0.15 10 110 3 a 6 0.1 10 1110 4 a 70.011 11114()2(0.2+0.17)+3(0.19+0.18+0.15)+4(0.1+0.01)=2.7471i i i K k p a()() 2.609=95.2%2.74H X H X R K3.3 对习题3.1的信源分别编二进制和三进制赫夫曼码，计算各自的平均码长及编码效率。

信息论与编码理论习题解第二章-信息量和熵2.1解: 平均每个符号长为:1544.0312.032=⨯+⨯秒 每个符号的熵为9183.03log 3123log 32=⨯+⨯比特/符号所以信息速率为444.34159183.0=⨯比特/秒2.2 解: 同步信号均相同不含信息,其余认为等概,每个码字的信息量为 3*2=6 比特； 所以信息速率为600010006=⨯比特/秒2.3 解:(a)一对骰子总点数为7的概率是366 所以得到的信息量为 585.2)366(log 2= 比特 (b) 一对骰子总点数为12的概率是361 所以得到的信息量为 17.5361log 2= 比特 2.4 解: (a)任一特定排列的概率为!521,所以给出的信息量为 58.225!521log 2=- 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为13521313521344!13C A =⨯所以得到的信息量为 21.134log 1313522=C 比特.2.5 解:易证每次出现i 点的概率为21i,所以比特比特比特比特比特比特比特398.221log 21)(807.1)6(070.2)5(392.2)4(807.2)3(392.3)2(392.4)1(6,5,4,3,2,1,21log )(2612=-==============-==∑=i i X H x I x I x I x I x I x I i ii x I i2.6 解: 可能有的排列总数为27720!5!4!3!12= 没有两棵梧桐树相邻的排列数可如下图求得， Y X Y X Y X Y X Y X Y X Y X Y图中X 表示白杨或白桦，它有⎪⎪⎭⎫⎝⎛37种排法，Y 表示梧桐树可以栽种的位置，它有⎪⎪⎭⎫⎝⎛58种排法，所以共有⎪⎪⎭⎫ ⎝⎛58*⎪⎪⎭⎫⎝⎛37=1960种排法保证没有两棵梧桐树相邻，因此若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为1960log 27720log 22-=3.822 比特 2.7 解: X=0表示未录取，X=1表示录取； Y=0表示本市，Y=1表示外地；Z=0表示学过英语，Z=1表示未学过英语，由此得比特比特比特)01(log )01()0()00(log )00()0()(8113.04log 4134log 43)()(02698.04110435log 104354310469log 10469)1()01(log )01()0()00(log )00()0;(104352513/41)522121()0(/)1())11()1,10()10()1,00(()01(104692513/43)104109101()0(/)0())01()0,10()00()0,00(()00()(4512.04185log 854383log 83)1()01(log )01()0()00(log )00()0;(8551/4121)0(/)1()10()01(8351/43101)0(/)0()00()00()(,251225131)1(,2513100405451)10()1()00()0()0(,54511)1(,51101432141)10()1()00()0()0(,41)1(,43)0(222222222222+=====+=======+==+======+========⨯⨯+========+=========⨯⨯+========+=========+======+========⨯=========⨯=========-===⨯+====+======-===⨯+⨯====+=========x y p x y p x p x y p x y p x p X Y H X H c x p z x p z x p x p z x p z x p z X I z p x p x y p x y z p x y p x y z p z x p z p x p x y p x y z p x y p x y z p z x p b x p y x p y x p x p y x p y x p y X I y p x p x y p y x p y p x p x y p y x p a z p y z p y p y z p y p z p y p x y p x p x y p x p y p x p x p2.8 解:令{}{}R F T Y B A X ,,,,==，则比特得令同理03645.0)()(5.0,02.03.0)2.05.0(log 2.0)()2.05.0(log )2.05.0()2.03.0(log )2.03.0(5.0log 5.03.0log 3.0)5log )1(2.02log )1(5.0log )1(3.05log 2.0log 3.02log 5.0(2.0log 2.0)2.05.0(log )2.05.0()2.03.0(log )2.03.0()()();()(2.0)(,2.05.0)(2.03.0)1(3.05.0)()()()()(5.0max 2'2222223102231022222==∴==+-=---++-+=-+-+-+++-----++-=-===-=+=-⨯+=+==p p I p I p pp p I p p p p p p p p p p p p p p X Y H Y H Y X I p I R P p F P pp p B P B T P A P A T P T P2.9 & 2.12解:令X=X 1,Y=X 1+X 2,Z=X 1+X 2+X 3, H(X 1)=H(X 2)=H(X 3)= 6log 2 比特 H(X)= H(X 1) = 6log 2 =2.585比特 H(Y)= H(X 2+X 3)=6log 61)536log 365436log 364336log 363236log 36236log 361(2222222+++++ = 3.2744比特 H(Z)= H(X 1+X 2+X 3)=)27216log 2162725216log 2162521216log 2162115216log 2161510216log 216106216log 21663216log 2163216log 2161(222222222++++++= 3.5993比特 所以H(Z/Y)= H(X 3)= 2.585 比特 H(Z/X) = H(X 2+X 3)= 3.2744比特 H(X/Y)=H(X)-H(Y)+H(Y/X) = 2.585-3.2744+2.585 =1.8955比特H(Z/XY)=H(Z/Y)= 2.585比特 H(XZ/Y)=H(X/Y)+H(Z/XY) =1.8955+2.585 =4.4805比特 I(Y;Z)=H(Z)-H(Z/Y) =H(Z)- H(X 3)= 3.5993-2.585 =1.0143比特 I(X;Z)=H(Z)-H(Z/X)=3.5993- 3.2744 =0.3249比特 I(XY ;Z)=H(Z)-H(Z/XY) =H(Z)-H(Z/Y)=1.0143比特 I(Y;Z/X)=H(Z/X)-H(Z/XY) = H(X 2+X 3)-H(X 3) =3.2744-2.585 =0.6894比特 I(X;Z/Y)=H(Z/Y)-H(Z/XY) =H(Z/Y)-H(Z/Y) =02.10 解:设系统输出10个数字X 等概,接收数字为Y,显然101)(101)()()(919===∑∑==i j p i j p i Q j w i iH(Y)=log10比特奇奇奇奇偶18log 81101452log 211015)(log)()()(log )()(0)(log ),()(log ),()(22,2222=⨯⨯⨯⨯+⨯⨯⨯=--=--=∑∑∑∑∑∑∑≠====x y p x y p x p x x p x x p x p x y p y x p x y p y x p X Y H x y x i y x y x所以I(X;Y)= 3219.2110log 2=-比特2.11 解:（a ）接收前一个数字为0的概率 2180)0()()0(==∑=i i i u p u q wbits p pw u p u I )1(log 11log )0()0(log )0;(2212121-+=-==（b ）同理 418)00()()00(==∑=ii iu p u q wbits p p w u p u I )1(log 22)1(log )00()00(log )00;(24122121-+=-== （c ）同理 818)000()()000(==∑=ii iu p u q wbits p p w u p u I )1(log 33)1(log )000()000(log )000;(28132121-+=-== （d ）同理 ))1(6)1(()0000()()0000(4226818p p p p u p u q w ii i+-+-==∑=bitsp p p p p p p p p p w u p u I 42264242268142121)1(6)1()1(8log ))1(6)1(()1(log )0000()0000(log )0000;(+-+--=+-+--==2.12 解:见2.9 2.13 解: (b))/()/()/(1log)()/(1log)()/()/(1log)()/(1log)()/(XY Z H X Y H xy z p xyz p x y p xyz p xy z p x y p xyz p x yz p xyz p X YZ H x y z xyzxyzxyz+=+===∑∑∑∑∑∑∑∑∑∑∑∑(c))/()/(1log)/()()/(1log)/()()/(X Z H x z p xy z p xy p xy z p xy z p xy p XY Z H xyzxyz=≤=∑∑∑∑∑∑（由第二基本不等式） 或)1)/()/((log )/()()/()/(log)/()()/(1log)/()()/(1log)/()()/()/(=-⨯≤=-=-∑∑∑∑∑∑∑∑∑∑∑∑xy z p x z p e xy z p xy p xy z p x z p xy z p xy p x z p xy z p xy p xy z p xy z p xy p X Z H XY Z H xyzxyzxyzxyz（由第一基本不等式）所以)/()/(X Z H XY Z H ≤(a))/()/()/()/()/(X YZ H XY Z H X Y H X Z H X Y H =+≥+等号成立的条件为)/()/(x z p xy z p =,对所有Z z Y y X x ∈∈∈,,,即在给定X 条件下Y 与Z 相互独立。

第二章 信息量和熵2.2 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的信息速率。

解：同步信息均相同，不含信息，因此 每个码字的信息量为 2⨯8log =2⨯3=6 bit因此，信息速率为 6⨯1000=6000 bit/s2.3 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7; (b) 12。

问各得到多少信息量。

解：(1) 可能的组合为 {1，6},{2，5},{3，4},{4，3},{5，2},{6，1})(a p =366=61得到的信息量 =)(1loga p =6log =2.585 bit (2) 可能的唯一，为 {6，6})(b p =361得到的信息量=)(1logb p =36log =5.17 bit2.4 经过充分洗牌后的一副扑克（52张），问：(a) 任何一种特定的排列所给出的信息量是多少？(b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？解：(a) )(a p =!521信息量=)(1loga p =!52log =225.58 bit (b) ⎩⎨⎧⋯⋯⋯⋯花色任选种点数任意排列13413!13)(b p =1352134!13A ⨯=1352134C 信息量=1313524log log -C =13.208 bit2.9 随机掷3颗骰子，X 表示第一颗骰子的结果，Y 表示第一和第二颗骰子的点数之和，Z 表示3颗骰子的点数之和，试求)|(Y Z H 、)|(Y X H 、),|(Y X Z H 、)|,(Y Z X H 、)|(X Z H 。

解：令第一第二第三颗骰子的结果分别为321,,x x x ，1x ，2x ，3x 相互独立，则1x X =，21x x Y +=，321x x x Z ++=)|(Y Z H =)(3x H =log 6=2.585 bit )|(X Z H =)(32x x H +=)(Y H=2⨯(361log 36+362log 18+363log 12+364log 9+365log 536)+366log 6=3.2744 bit)|(Y X H =)(X H -);(Y X I =)(X H -[)(Y H -)|(X Y H ]而)|(X Y H =)(X H ，所以)|(Y X H = 2)(X H -)(Y H =1.8955 bit或)|(Y X H =)(XY H -)(Y H =)(X H +)|(X Y H -)(Y H而)|(X Y H =)(X H ，所以)|(Y X H =2)(X H -)(Y H =1.8955 bit),|(Y X Z H =)|(Y Z H =)(X H =2.585 bit)|,(Y Z X H =)|(Y X H +)|(XY Z H =1.8955+2.585=4.4805 bit2.10 设一个系统传送10个数字，0，1，…，9。

可变长无失真信源编码定理一、概述可变长无失真信源编码定理是信息论的核心概念之一，它是由美国数学家香农（Claude Shannon）于1948年首次提出。

该定理主要探讨了信源编码的极限性能，为无失真编码提供了理论基础。

可变长无失真信源编码定理不仅在理论上有重要意义，而且在数据压缩、网络传输和存储系统等领域有着广泛的应用价值。

二、定理内容可变长无失真信源编码定理的主要内容是：对于任意给定的离散无记忆信源，存在一种可变长编码方式，使得编码后的平均码长小于或等于信源的熵，从而实现无失真编码。

换句话说，如果信源的熵为H，那么存在一种编码方式，使得编码后的平均码长L满足L ≤ H。

三、证明过程证明可变长无失真信源编码定理的过程较为复杂，涉及到概率论和信息论的基本知识。

以下是证明过程的大致步骤：1.定义信源的熵：信源的熵是信源输出随机变量的不确定性度量，定义为所有可能符号的概率加权和。

如果信源有n个符号，每个符号出现的概率为p1, p2, ..., pn，则信源的熵H定义为H = - Σ (pi * log2(pi))，其中i=1,2,...,n。

2.构造一个可变长度编码表：根据信源的概率分布，构造一个可变长度编码表，使得出现概率较大的符号对应较短的码字，反之亦然。

假设码字长度按照字典序排列，第i个码字的长度为log2(1/pi)，其中i=1,2,...,n。

3.计算平均码长：根据可变长度编码表，计算所有可能符号的平均码长。

平均码长等于所有码字长度的概率加权和，即L = Σ(log2(1/pi) * pi)，其中i=1,2,...,n。

4.证明平均码长小于或等于信源熵：利用不等式性质和概率分布的性质，推导出平均码长L满足L ≤H。

关键在于利用概率分布的不均匀性，通过调整码字长度来最小化平均码长。

5.构造一个解码函数：为了实现无失真解码，需要构造一个解码函数，使得每个码字能够唯一地还原为原始符号。

解码函数可以采用查表法或类似算法实现。

无失真编码与保真度准则下的信源编码比较无失真编码和保真度编码是两种不同的信源编码方法。

无失真编码是一种编码方法，其中编码的输出与其输入完全相同，即没有信息损失。

保真度编码是一种编码方法，其中编码输出与输入之间具有某种度量，通常用于指定被编码信源的相关度量。

在无失真编码中，被编码的信源通常通过重复信源符号来实现。

例如，在串行传输系统中，数据被重复多次，以确保接收方能够正确地接收数据。

虽然这种方法可以确保完全输送原始信源，但它有几个限制。

首先，它需要更多的带宽，因为数据需要被重复发送多次。

其次，它并不适用于所有类型的数据，特别是当数据非常长或不规则时，这种方法会变得非常昂贵和低效。

与此不同的是，保真度编码的目标是在尽可能减少带宽和存储空间的情况下，最大限度地保留原始信源的信息。

通过使用保真度准则，可以将信源表示为某种度量形式。

这些度量通常包括信号功率、功率频谱分布、自相关函数和互相关函数等。

保真度编码通常使用一些高级编码技术，如哈夫曼编码、熵编码和维纳滤波器等。

这些编码方法都源于信息论和通信工程领域的数学理论。

通过这些编码技术，保真度编码可以提高信源的压缩效率，同时最大程度地保留信源的信息。

当比较无失真编码和保真度编码时，无失真编码通常比较简单，但需要更多的带宽和存储空间。

而保真度编码则需要更复杂的算法和技术，但可以在尽可能减少带宽和存储空间的情况下保留更多的原始信息。

综上所述，在处理信源编码问题时，需要综合考虑多个方面，包括数据类型、带宽和存储空间要求等。

无失真编码适用于对带宽和存储空间要求不是很高的应用，例如音频、图片和视频的传输。

保真度编码适用于对存储空间和带宽要求较高的应用，例如用于数字通信系统的压缩算法。