第5章信源编码 本章学习重点：  信源编码的目的和码的定义。  无失真信源编码定理。  无失真信源编码方法。  常用的无失真信源编码方法。  限失真信源编码定理。  常用的限失真信源编码方法。 5.1知识点 5.1.1信源编码 1. 信源编码 分组码： 信源输出符号序列X=(X1，X2，…，XL)，序列长度为L，X1∈{a1，a2，…，an}； 每个符号序列Xi依照码表映射成一个码字Yi，这种码也称为分组码或块码，Y=(Y1，Y2，…，YK)，Yk∈{b1，b2，…，bm}。 非分组码： 不存在码表。 2. N次扩展码 分组码的N次扩展码： 设信源符号si，i=1，2，…，q，映射为一个固定的码字Wi，i=1，2，…，q，则码αj=(sj1，sj2，…，sjN)映射为Wj=(Wj1，Wj2，…，WjN)的分组码称为原分组码的N次扩展。 3. 分组码的性质 1) 非奇异性 若一种分组码中的所有码字都互不相同，则称此分组码为非奇异码，否则称为奇异码。 分组码是非奇异码只是正确译码的必要条件。 2) 唯一可译性 一个分组码若对于任意有限的整数N，其N阶扩展码均为非奇异的，则称为唯一可译码。 分组码是唯一可译的，这是分组码正确译码的充要条件。 3) 即时码 无须考虑后续的码符号即可以从码符号序列中译出码字，这样的唯一可译码称为即时码。 即时码的条件： 设W1=Wi1Wi2…Wil为一个码字，对于任意的1≤j≤l，称码符号序列的前j个元素Wi1Wi2…Wij为码字Wi的前缀。 唯一可译码成为即时码的充要条件是码组中任何一个码字都不是其他码字的前缀。 5.1.2无失真信源编码 1. 定长编码 离散无记忆信源X P=x1x2…xn p(x1)p(x2)…p(xn)的熵为H(X)，由L个符号组成的平稳序列(X1，X2，…，XL)，可用K个符号(Y1，Y2，…，YK)，yk∈{y1，y2，…，ym}进行定长编码。对于ε>0，δ>0，只要满足KLlogm≥HL(X)+ε，则当L足够大时，必可使译码差错小于δ。 反之，若KLlogm≤HL(X)-2ε，译码差错一定是有限值，且当L足够大时，译码错误概率趋于1。 2. 变长编码 为了能够即时译码，变长码必须是即时码，且变长码一般也要为唯一可译码，所以需要先判断唯一可译码的充要条件。 克拉夫特(Kraft)不等式： 设信源符号集S=(s1，s2，…，sq)，码符号集X=(x1，x2，…，xr)，对信源进行编码，相应的码字W=(W1，W2，…，Wq)，分别对应的码长为l1，l2，…，lq，则唯一可译码存在的充要条件是∑qi=1r-li≤1。 单个符号变长编码定理： 若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式 H(X)logm≤≤H(X)logm+1 离散平稳无记忆序列变长编码定理： 对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式 HL(X)≤≤HL(X)+ε 式中，ε为任意小的正数。 5.1.3无失真信源编码方法 1. 香农编码 香农编码是一种常见的可变长编码，其理论基础是符号的码字长度完全由该符号出现的概率来决定。 2. 哈夫曼编码 哈夫曼编码也是一种常见的可变长编码，依据各符号出现的概率来构造码字，其基本原理是基于二叉树的编码思想，所有可能的输入符号在哈夫曼树上对应为一个节点，节点的位置就是该符号的哈夫曼编码。 3. 算术编码 算术编码是非分组码的编码方法，它从全信源序列出发，考虑符号之间的依赖关系直接对信源符号序列进行编码。 5.1.4限失真信源编码 限失真信源编码定理： 设离散无记忆信源X的信息率失真函数为R(D)，则当信息传输率R>R(D)时，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D+ε，ε为任意小的正数； 反之，若R1，则不存在长度为(1，2，3，3，3，4，4)的二进制唯一可译码。 11. 变长编码的核心问题是寻找紧致码(最佳码)，而哈夫曼编码方法构造的是最佳码。 解答： 对。 12. 算术编码是一种无失真的分组信源编码，其基本思想是将一定精度的数值作为序列的编码，是以另外一种形式实现的最佳统计匹配编码。 解答： 错。算术编码不是统计匹配编码。 13. 即时码的任意一个码字都不是其他码字的前缀部分。 解答： 对。 14. 游程序列的熵(“0”游程序列的熵与“1”游程序列的熵的和)大于或等于原二元序列的熵。 解答： 错。游程序列的熵小于或等于原二元序列的熵。 15. 克拉夫特不等式是唯一可译码的充要条件。 解答： 错。克拉夫特不等式是唯一可译码存在的充要条件。 5.2.4填空题 1. 游程编码比较适用于序列。 解答： 二元。 2. 即时码又称为，有时也称为。 解答： 非延长码； 异前缀码。 3. 唯一可译码可分为两大类，码和码。 解答： 即时码； 非即时码。 4. 无失真的信源中，信源输出由来度量，在有失真的信源中，信源输出由来度量。 解答： H(X)； R(D)。 5. 无失真信源编码的中心任务是编码后的信息传输率压缩接近； 限失真压缩的中心任务是在给定的失真度条件下，信息传输率压缩接近到。 解答： H(X)； H(X)-ε。 6. 若一离散无记忆信源的信息熵H(X)等于2.5bit/符号，对信源进行等长的无失真二进制编码，则编码的长度至少为bit。 解答： 3。 7. 变长无失真信源编码定理，又称为定理，定理说明了只要平均码长信源熵，就可以实现唯一可译码。 解答： 香农第一； 不小于。 5.2.5问答题 1. 简述保真度准则下的信源编码定理及其物理意义。 解答： 保真度准则下的信源编码定理： 设离散无记忆信源X的信息率失真函数为R(D)， 当信息传输率R>R(D)时，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D+ε，ε为任意小的正数； 反之，若R2ANσ2，式中，N为3min内信源符号输出个数； σ2为码长的方差。 N=1003×60×3=6000 由编出的哈夫曼编码可得 σ2=E［K2i］=∑mj=1p(uj)K2j-2U =(0.729×12+0.081×32×3+0.009×52×3+0.001×52)-1.5982 =1.06 则存储器容量M=2×2.332×6000×1.06=372bit 存储器半满为186bit。若信道码率为50bit/s，小于输入信道符号的速率，则3min后存储器中会增加594bit，因而开始时存储器不应到半满，存储器的容量可略小于(372+594)bit=966bit。 注： 本题考查的知识点是5.4.1节哈夫曼编码。题解： (1)哈夫曼编码方法； (2)变长码编码简单的代价是需要存储设备来缓冲码字长度的差异。 14. 若已知一离散信源符号集为： (1) 若U P=abcd 0.50.30.150.05，试 对它进行哈夫曼编码并求编码效率？(2)若该信源的状态转移概率矩阵P=0.30.40.30 0.50.500 0.5000.5 00.50.50，求稳态时符号的出现概率并求信源熵； (3)试设计一个哈夫曼编码，每次对两个信源符号编码，求每个信源符号平均比特数以及编码效率。 解答： (1) 哈夫曼编码结果如表5.14所示。 表5.14题14的哈夫曼编码 符号概率码字 u10.51 u20.300 u30.15010 u40.05011 信源熵H(U)=H(0.5，0.3，0.15，0.05)=1.65bit/符号 平均码长=0.5×1+0.3×2+0.15×3+0.05×3=1.7bit/符号 编码效率η=H(U)=1.651.7=0.97 (2) 该信源的状态转移矩阵P=0.30.40.30 0.50.500 0.5000.5 00.50.50，设状态的稳定分布W=(w1，w2，w3，w4)，则求解方程组W·P=W ∑4i=1wi=1，可得状态的稳定概率为w1=w2=513，w3=213，w4=113。 平稳时符号的出现概率为p1=513，p2=513，p3=213，p4=113。 该信源的信息熵 H(U)=H513，513，213，113=1.76bit/符号 (3) 对两个符号一起进行哈夫曼编码后的结果如表5.15所示。 表5.15题14两个符号一起的哈夫曼编码结果 状态信 源 消 息概率编码 s1u1u10.5×0.5=0.2510 s2u1u20.5×0.3=0.15001 s3u2u10.3×0.5=0.15010 s4u2u20.3×0.3=0.09111 续表 状态信 源 消 息概率编码 s5u1u30.5×0.15=0.0750000 s6u3u10.15×0.5=0.0750001 s7u2u30.3×0.15=0.0451100 s8u3u20.15×0.3=0.0451101 s9u1u40.5×0.05=0.02501110 s10u4u10.05×0.5=0.02501111 s11u3u30.15×0.15=0.0225011000 s12u2u40.3×0.05=0.015011010 s13u4u20.05×0.3=0.015011011 s14u3u40.15×0.05=0.0750110011 s15u4u30.05×0.15=0.07501100100 s16u4u40.05×0.05=0.002501100101 =2×0.25+3×0.15+3×0.09+4×(0.075+0.075+0.045+0.045)+5× (0.025+0.025)+6×(0.0225+0.015+0.015)+7×0.0075+8× (0.0075+0.0025)=3.3275bit/二个二元符号 所以=2=1.66375bit/符号，编码效率η=H(U)=1.64741.66375=0.99。 注： 本题考查的知识点是5.4.1节哈夫曼编码。题解： (1)哈夫曼编码方法进行编码； (2)两个信源符号的哈夫曼编码。 15. 设有一阶马尔可夫信源，信源集合U=uj qj，j=1，2，3，状态集合S=si pi，i=1，2，3，其状态转移概率矩阵P= 03414 01212 100，试求： (1)H(U|S1)、H(U|S2)、 H(U|S3)； (2)对各种状态，分别将U的符号编成最佳变长哈夫曼二进码； (3)求H∞(U)，并证明上述编码方法的平均码长等于H∞(U)。 解答： (1) 该马尔可夫信源的状态稳定概率为可由方程组p1+p2+p3=1 p1=p3 p2=34p1+12p2 p3=14p1+12p2求得， p1=27，p2=37，p3=27，即P(S=s1)=27，P(S=s2)=37，P(S=s3)=27。 H(U|Sj)=-∑3i=1p(U=ui，S=sj)logp(U=ui，S=sj) =-∑3i=1p(U=ui|S=sj)p(S=sj)logp(U=ui，S=sj) 由状态转移矩阵可得 p(U=u1|S=s1)=12，p(U=u2|S=s1)=14，p(U=u3|S=s1)=14 p(U=u1|S=s2)=0，p(U=u2|S=s2)=12，p(U=u3|S=s2)=12 p(U=u1|S=s3)=1，p(U=u2|S=s3)=0，p(U=u3|S=s3)=0 所以， H(U|S1)=-12×27×log12-14×27×log14-14×27×log14=0.42857 H(U|S2)=0-12×37×log12-12×37×log12=0.42857 H(U|S3)=-1×27×log1=0 (2) 各种状态的信源概率分布及相应的哈夫曼编码结果如表5.16所示。其中， P(U=u1)=∑3i=1P(S=si)P(U=u1|S=si)=27×12+37×0+27×1=37 P(U=u2)=∑3i=1P(S=si)P(U=u2|S=si)=27×14+37×12+27×0=27 P(U=u3)=∑3i=1P(S=si)P(U=u3|S=si)=27×14+37×12+27×0=27 表5.16题15的哈夫曼编码 符号概率编出的码字 u13/71 u22/700 u32/701 (3) 极限熵H∞(U)=-37log37+27log27+27log27=1.56bit/符号 平均码长=37×1+27×2+27×2=117=1.57bit/符号 编码效率η=H∞(U)=1.561.57=99% 可以看出，平均码长逼近极限熵H∞(U)。 注： 本题考查的知识点是2.1.3节马尔可夫信源、5.4.1节哈夫曼编码。题解： (1)这是一道综合题，结合了马尔可夫信源和哈夫曼编码； (2)计算马尔可夫信源的稳态概率； (3)采用哈夫曼编码方法进行编码。 16. 离散无记忆信源发出A、B、C三种符号，概率分布分别为5/9、1/3、1/9，应用算术编码方法对序列CABA进行编码，并对结果进行解码。 解答： 先计算三种符号的累积概率，写成二进制后，结果如表5.17所示。其中，小写的p是符号概率，大写的P是累积概率。 表5.17题16的累积概率 符号符号概率p符号概率的 二进制表示符号累积概率P (二进制表示) A5/90.10 B1/30.010.1 C1/90.010.11 按照主教材5.4.2节中关于算术编码的过程描述进行编码，用累积概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S)，用φ表示起始状态为空序列。具体过程如下： 假设起始状态A(φ)=1，C(φ)=0； “C”： C(φC)=C(φ)+A(φ)PC=0+1×0.11=0.11 A(φC)=A(φ)pC=1×0.01=0.01 “CA”： C(CA)=C(C)+A(C)PA=0.11+0.01×0=0.11 A(CA)=A(C)pA=0.01×0.1=0.001 “CAB”： C(CAB)=C(CA)+A(CA)PB=0.11+0.001×0.1=0.1101 A(CAB)=A(CA)pB=0.001×0.01=0.00001 “CABA”： C(CABA)=C(CAB)+A(CAB)PA=0.1101+0.00001×0=0.1101 A(CABA)=A(CAB)pA=0.00001×0.1=0.000001 所以，编出的码字为“1101”。 解码过程： (1) 0.1101位于区间［0.11，1］，所以第一个码字是“C”； (2) 减去累积概率PC，0.1101-0.11=0.0001，乘上加权0.0001×100=0.01，位于区间［0，0.1］，所以第2个码字是“A”； (3) 0.01×10=0.1，位于区间［0.1，0.11］，所以第三个码字是“B”； (4) 0.1-0.1=0，位于区间［0，0.1］，所以第4个码字是“A”。 所以，解码的码序列是“CABA”。 注： 本题考查的知识点是5.4.2节算术编码。题解： 算术码的编码和解码。 17. 一离散无记忆信源{0，1}，符号出现概率分别为： p0=0.3，p1=0.7。已知信源序列为1101110011…，试 ： (1)对此序列进行算术编码； (2)若将0，1符号的概率近似取为p0=0.25，p1=0.75，进行算术编码。 解答： (1) 将概率化为二进制得p1=0.101，p0=0.011，累积概率为P1=0.000，P0=0.101。设起始状态为空序列φ，令A(φ)=1，C(φ)=0。由主教材上关于算术编码的过程描述进行编码，具体过程如下： “1”： C(φ1)=C(φ)+A(φ)P1=0+1×0=0 A(φ1)=A(φ)p1=1×0.101=0.101 “11”： C(11)=C(1)+A(1)P1=0+0.101×0=0 A(11)=A(1)p1=0.101×0.101=0.011001 “110”： C(110)=C(11)+A(11)P0=0+0.011001×0.101=0.001111101 A(110)=A(11)p0=0.011001×0.011=0.001001011 “1101”： C(1101)=C(110)+A(110)P1=0.001111101 A(1101)=A(110)p0=0.000101110111 “11011”： C(11011)=C(1101)+A(1101)P1=0.001111101 A(11011)=A(1101)p1=0.000011101010011 “110111”： C(110111)=C(11011)+A(11011)P1=0.001111101 A(110111)=A(11011)p1=0.000010010010011111 后面的几位可以以此推算出来。 (2) 将概率化为二进制为p1=0.11，p0=0.01，累积概率为P1=0.00，P0=0.11。 “1”： C(φ1)=C(φ)+A(φ)P1=0+1×0=0 A(φ1)=A(φ)p1=1×0.11=0.11 “11”： C(11)=C(1)+A(1)P1=0 A(11)=A(1)p1=0.11×0.11=0.1001 “110”： C(110)=C(11)+A(11)P0=0+0.1001×0.11=0.011011 A(110)=A(11)p0=0.1001×0.01=0.001001 “1101”： C(1101)=C(110)+A(110)P1=0.011011 A(1101)=A(110)p0=0.00011011 “11011”： C(11011)=C(1101)+A(1101)P1=0.011011 A(11011)=A(1101)p1=0.0001010001 “110111”： C(110111)=C(11011)+A(11011)P1=0.011011 A(110111)=A(11011)p1=0.000011110011 以此类推，后面各位可以计算出来。 注： 本题考查的知识点是5.4.2节算术编码。题解： (1)符号概率和累积概率的意义； (2)算术编码的编解码过程。 18. 对题17中的第二种编码结果，利用比较法写出算术码的译码过程。 解答： 算术码的译码可通过比较编码后的数值大小来进行，即判断码字落在哪个区间就可以得出一个相应的符号序列。 因为C(110111)=0.0011011<0.11，所以译出第一个符号为“1”； 去掉被乘概率因子(加权)： 0.0011011×10=0.011011<0.1，译出第二个符号为“1”； 再去掉被乘概率因子(加权)： 0.0011011×100=0.11011，在区间［0.11，1］内，所以译出第三个符号是“0”； 去掉累积概率： 即0.11011-0.11=0.00011，再去掉被乘概率因子(加权)： 0.00011×1000=0.11，属于区间［0.11，1］，所以译出第四个符号为“0”； 去掉累积概率： 0.11-0.11=0.0，0.0×8=0.0<0.11，所以译出第五个符号为“1”； 同理，译得第六、七个符号为11； 所以，译出的序列S*=1100111=S。 注： 本题考查的知识点是5.4.2节算术编码。题解： (1)算术码的解码过程； (2)算术码的译码所需参数较少，且不像哈夫曼编码那样需要一个很大的码表。 图5.4题19的状态转移图 19. 一阶马尔可夫信源符号集X∈{a1，a2，a3}，状态集S∈{s1，s2，s3}，状态转移如图5.4所示，某状态下发出符号的概率标在相应的线段旁。试： (1)求H(X|s1)、H(X|s2)和H(X|s3)； (2)对各种状态，分别把X的符号编成最佳变长二进制码； (3)求H(X)。 解答： (1) 由图5.1可得状态转移矩阵P= ［P(sj|si)］=03414 01212 100，符号条件概率矩阵P(aj|si)=121414 01212 100。 各状态下的条件熵为 H(X|s1)=∑ip(ai|s1)logp(ai|s1)=32bit/符号 H(X|s2)=∑ip(ai|s2)logp(ai|s2)=1bit/符号 H(X|s3)=∑ip(ai|s3)logp(ai|s3)=0bit/符号 (2) 用哈夫曼编码对各种状态进行编码。对状态s1编出的哈夫曼编码如表5.18所示。 表5.18题19的哈夫曼编码 符号概率编出的码字 a11/20 a21/410 a31/411 对状态s2编出的哈夫曼编码如表5.19所示。 表5.19题19的哈夫曼编码 符号概率编出的码字 a11/20 a21/21 a30不编码 对状态s3编出的哈夫曼编码如表5.20所示。 表5.20题19的哈夫曼编码 符号概率编出的码字 a110 a20不编码 a30不编码 (3) 设各状态的稳定概率满足方程组 p(s1)=p(s3) p(s2)=34p(s1)+12p(s2) p(s3)=14p(s1)+12p(s2) ∑3i=1p(si)=1 ，求解该方程组可得p(s1)=p(s3)=27，p(s2)=37，则信源的极限熵 H∞(X)=∑ip(si)H(X|si)=27×32+37×1+27×0=67bit/符号 注： 本题考查的知识点是2.1.3节马尔可夫信源、2.3.2节离散有记忆信源的序列熵以及5.4.1节哈夫曼编码，是一道综合题。题解： (1)由状态转移图得到状态转移矩阵和符号转移矩阵； (2)马尔可夫信源的极限熵计算方法； (3)用哈夫曼编码方法进行编码。 20. 在电视信号中，亮度信号的黑色电平为0，白色电平为L。用均匀分割来量化其样值，要求峰功率信扰比大于50dB，求每样值所需的量化比特数。 解答： 设电视信号的电平在［0，L］区间均匀分布，即p(x)=1L，050。将W=Δ212 和Δ=Ln代入，得log1012n2>5。 设量化比特数为b，则2b=n，要求log1012×22b>5，可得b>6.5。所以，每样值所需的量化比特数为7bit。 注： 本题考查的知识点是5.4.5节矢量量化编码。题解： 由峰功率信扰比=信号峰功率/量化噪声功率，计算得到量化级数，而后得到量化比特数。 21. 设信源为S p(s)=s1s2…s6 p1p2…p6，将此信源编码作为r元唯一可译变长码，要求对应的码长为(K1，K2，K3，K4，K5，K6)=(1，1，2，3，2，3)，求r的最佳下限值。 解答： 要将此信源编码成为r元的唯一可译变长码，其码字对应的码长(K1，K2，K3，K4，K5，K6)=(1，1，2，3，2，3)必须满足克拉夫特不等式： ∑6i=1r-Ki=r-1+r-1+r-2+r-3+r-2+r-3≤1 即2r+2r2+2r3≤1，其中，r是大于或等于1的正整数。 当r=1和2时，∑6i=1r-Ki>1，不能满足克拉夫特不等式。 当r=3时，∑6i=1r-Ki=2627<1，能满足克拉夫特不等式。 所以，r的最佳下限值为r=3。 注： 本题考查的知识点是5.1节编码的概念。题解： 满足克拉夫特不等式是唯一可译码的必要条件。 22. 某通信系统使用文字字符共10000个，据长期统计，使用频率占80%的共有500个，占90%的有1000个，占99%的有4000个，占99.9%的7000个。试： (1)求该系统使用的文字字符的熵； (2)请给出该系统的一种信源编码方法并作简要评价。 解答： (1) 10000个文字字符中，使用频率占80%的有500个，则这500个文字字符共出现了8000次，平均每个字符出现了8000500=16次，即这500个字符每个字符出现的概率 p1=1610000=1.6×10-4。 同理，使用频率90%的有1000个，减去使用频率80%的500个，有500个字符出现频率为10%，在10000个字符中出现的次数为1000次，平均每个字符出现了1000500=2次，这500个字符中每个字符出现的概率p2=210000=2×10-4。 类似地，可以得到余下90%~99%的3000个字符每个字符出现的概率p3=9003000×10000=3×10-5； 99%~99.9%的3000个字符每个字符出现的概率p4=903000×10000=3×10-6； 99.9%~100%的3000个字符每个字符出现的概率p5=103000×10000=13×10-6。 根据熵的定义，这10000个文字字符的熵 H(X)=-500(p1log2p1+p2log2p2)-3000(p3log2p3+p4log2p4+p5log2p5) =0.8log0.8500-0.1log0.1500-0.09log0.093000-0.009log0.0093000- 0.001log0.0013000=10.2bit/字符 (2) 可以使用哈夫曼编码的方法对该系统的信源进行编码，为使压缩效果理想，可以使用扩展信源的方法。 注： 本题考查的知识点是2.2节离散信源熵和互信息、5.4.1节哈夫曼编码。题解： (1)本题不需要考虑字符间的关系，只需紧扣熵的定义计算文字字符熵； (2)有了统计概率，哈夫曼编码是较好的选择。 23. 信源符号X的概率空间为X P=x1x2 0.10.9，如每次两个符号一起编码，试写出 哈夫曼编码，并求平均码长和编码效率。 解答： 哈夫曼编码的参考编码结果为 0，11，100，101(哈夫曼编码并不唯一) 平均码长=0.81+0.09×2+0.1×3=1.29bit/两个符号=0.645bit/符号。 编码效率η=H(X)=H(0.1，0.9)0.645=0.470.645=0.73。 注： 本题考查的知识点是5.4.1节哈夫曼编码。题解： (1)得到X的二次扩展信源； (2)利用哈夫曼编码方法进行编码。 24. 一通信系统传送的符号只有3个，使用概率分别为0.2、0.3和0.5，但传送时总是以3个符号为一个字，故该系统的信源编码以字为基础并采用二进制哈夫曼编码。根据字的概率大小，编码结果为： 概率在(0，0.020］区间，采用6 bit； 在(0.020，0.045］区间，采用5bit； 在(0.045，0.100］区间，采用4bit； 在0.100以上的区间，采用3bit。求该种信源编码的效率。 解答： 假设该系统传输的三个符号分别为a，b和c，且pa=0.2，pb=0.3，pc=0.5。下面对每个字，即3个符号可能出现的情况加以讨论，结果如表5.21所示。 表5.21题24的符号和编码 字(3个符号)概率概率所在区间编 码 位 数种数 aaa0.23=0.008(0，0.020］61 bbb0.33=0.027(0.020，0.045］51 ccc0.53=0.125(0.100，1.00］31 2个a、1个b0.22×0.3=0.012(0，0.020］63 2个a、1个c0.22×0.5=0.02(0.020，0.045］63 2个b、1个a0.32×0.2=0.018(0，0.020］63 2个b，1个c0.32×0.5=0.045(0.020，0.045］53 2个c，1个a0.52×0.2=0.05(0.045，0.100］43 2个c，1个b0.52×0.3=0.075(0.045，0.100］43 1个a，1个b，1个c0.2×0.3×0.5=0.03(0.020，0.045］56 平均码长 =0.008×6+0.027×5+0.125×3+(0.012×6+0.02×6+0.018×6+ 0.045×5+0.05×4+0.075×4)×3+0.03×5×6 =4.533bit/字 H(X)=-∑si=1pilogpi×3=(-0.2log20.2-0.3log20.3-0.5log20.5)×3 =4.455bit/字 该信源编码的效率η=H(X)=4.4554.533=0.983。 注： 本题考查的知识点是5.4.1节哈夫曼编码。题解： (1)变长码的平均码长计算； (2)哈夫曼编码效率的计算。 25. 设有一个无记忆信源X发出符号A和B，已知p(A)=14，p(B)=34。试： (1)计算该信源熵； (2)设该信源改为发三重序列消息的信源，采用哈夫曼编码方法对其进行编码，求平均信息传输速率。 解答： (1) 该离散无记忆信源的熵为H(X)=H14，34=0.811bit/符号。 (2) 三重序列消息信源的哈夫曼编码结果如表5.22所示。 表5.22题25的哈夫曼编码结果 三重序列消息概率编码 BBB27/640 BAA9/64100 BAB9/64101 ABB9/64110 AAB3/6411100 ABA3/6411101 BAA3/6411110 AAA1/6411111 编码的平均长度K2=2764+964×3×3+364×5×3+164×5=2.46875码元/三重符号。 因为信源是无记忆的，所以三重符号的熵H(X)=3H(X)。 平均传输速率R2=H(X)2=0.9855bit/时间。 注： 本题考查的知识点是5.4.1节哈夫曼编码。题解： (1)三重序列消息信源； (2)哈夫曼编码及其编码效率的计算。 26. 已知离散无记忆信源S P(s)=s1s2s3s4s5s6 0.30.20.150.150.10.1，试： (1)求信源熵H(S)； (2)进行哈夫曼编码，并求平均码长和编码效率； (3)哈夫曼编码是否唯一？如果不唯一，哪种编码方法更佳？ 解答： (1) 该信源的熵H(S)=H(0.3，0.2，0.15，0.15，0.1，0.1)=2.47bit/符号。 (2) 哈夫曼编码结果如表5.23所示。 表5.23题26的哈夫曼编码结果 符号概率编码 s10.300 s20.201 s30.15010 s40.15011 s50.1110 s60.1111 平均码长=0.3×2+0.2×2+0.15×3+0.1×3+0.1×3=2.5二进制码元/符号。 编码效率η=H(S)=2.472.5=0.988。 (3) 由于按照概率大小顺序排队方法的不唯一，所以哈夫曼编码不唯一。将新合并的等概率消息排列到上支路(即大概率位置)，能充分利用短码，缩短码长的方差，即编出的码更接近于等长码，这种编码方法更佳。 注： 本题考查的知识点是5.4.1节哈夫曼编码，题解： 二进制哈夫曼编码及其编码效率的计算。 27. 已知一个信源X 包含8个符号消息，其概率分布为 X P(x)=ABCDEFGH 0.10.180.40.050.060.10.070.04。 (1) 信源每秒发出一个符号，求该信源的熵及信息传输速率； (2) 对这8个符号作二进制码元的哈夫曼编码，写出各个代码组，并求出编码效率。 解答： (1) 该信源的熵 H(X)=H(0.1，0.18，0.4，0.05，0.06，0.1，0.07，0.04)=2.55bit/符号 信源每秒发出一个符号，则信息传输速率为R=2.55bit/s。 (2) 哈夫曼编码结果如表5.24所示。 表5.24题27的哈夫曼编码结果 符号概率编码 C0.40 B0.18110 A0.1100 F0.11110 G0.071010 E0.061011 D0.051110 H0.0411111 平均码长 =0.4+0.18×3+0.1×3+0.1×4+0.07×4+0.06×4+0.05×5+0.04×5 =2.61码元/符号。 编码效率η=H(X)=2.552.61=0.978。 注： 本题考查的知识点是5.4.1节哈夫曼编码。题解： 二进制哈夫曼编码及其编码效率的计算。 28. 信源符号X有6种字母，概率分别为(0.32，0.22，0.18，0.16，0.08，0.04)，试： (1)求符号熵H(X)； (2)用哈夫曼编码编成二进制变长码，计算其编码效率； (3)当译码差错小于10-3的定长二进制码要达到(2)中的效率时，估计要多少信源符号一起编码才能达到？ 解答： (1) H(X)=H(0.32，0.22，0.18，0.16，0.08，0.04)=2.352bit/符号。 (2) 二进制哈夫曼编码的结果如表5.25所示。 表5.25题28的哈夫曼编码结果 符号概率编码 x10.3200 x20.2210 x30.1811 x40.16010 x50.080110 x60.040111 平均码长=(0.32+0.22+0.18)×2+0.16×3+(0.08+0.04)×4=2.4码元/符号 编码效率η=H(X)=2.3522.4=0.98。 (3) 由编码效率η=H(X)H(X)+ε=2.3522.352+ε=0.98可得ε=0.048，代入L≥σ2(x)ε2δ，知如采用定长编码，需要L≥σ2(x)ε2δ=2.29×105位信源符号一起编码才能达到0.98的编码效率。 注： 本题考查的知识点是5.4.1节哈夫曼编码。题解： (1)二进制哈夫曼编码及其编码效率的计算； (2)定长编码与变长编码的比较。 29. 现有一幅已经离散化后的图像，图像的灰度量化分成8级，如表5.26所示。表中数字为相应像素上的灰度级。另有一个无噪无损二元信道，单位时间内传输100个二元符号。试回答以下问题： (1)统计此图像的像素点数。(2)不考虑图像的统计特性，并采用二元定长码，计算每个像素需要的码元数； 将此图像通过给定的信道传输，计算传送完这幅图像所需的时间。(3)若考虑图像的统计特性，将像素的灰度值作为信源，写出信源的概率分布函数，计算出信源熵。(4)对此灰度级进行哈夫曼最佳二元编码，列出编码码表，计算每个像素需要的码元数、编码效率及其冗余度； 若将此图像通过给定的信道传输，计算传送完这幅图像所需的时间。(5)这幅图像是否可以进一步压缩到小于信源熵H(X)，说明理由。 表5.26题29的表 1111111111 1111111111 1111111111 1111111111 2222222222 2222222333 3333333444 4444444555 5555666666 7777788888 解答： (1) 该图像的像素点数共有10×10=100个。 (2) 若不考虑统计特性，因为有8个灰度级，采用二元定长码，故每个像素需要3个二元码，100个像素需要300个二元码，单位时间内传输100个二元符号，需要3s传完。 (3) 若考虑图像的统计特性，这100个像素点灰度的概率分布为 X P(X)= 12345678 401001710010100101007100610051005100 则信源熵H(X)=-∑8i=1p(xi)logp(xi)=2.572bit/灰度级。 (4) 对灰度级进行哈夫曼编码，结果如表5.27所示。 表5.27题29的哈夫曼编码 灰度级概率编码 10.41 20.17001 30.10000 40.10001 50.070100 60.060101 70.050110 80.050111 平均码长=2.63二元码/灰度级。 编码效率η=H(X)=2.5722.63=0.978。 冗余度r=1-0.978=0.022。 此图像经过给定信道传输，需要2.63s。 (5) 这幅图像可以进一步压缩。因为前面的编码是按无记忆编码的，没有考虑像素之间的记忆性，实际上像素之间是有依赖性的，可以看作m阶马尔可夫信源，从而得到极限熵H∞(X)，是所有熵中最小的。 注： 本题是一道综合题，考查2.2.2节离散信源熵、5.2.1节定长编码和5.4.1节哈夫曼编码。题解： (1)离散信源熵的计算； (2)信源编码方法； (3)信息传输的概念。 30. 已知信源的协方差矩阵Φu=101 010 101，试求： 最佳正交变换矩阵A和变换后的协方差矩阵Φx。 解答： 先计算信源的协方差矩阵Φu的特征值。特征方程为 |Φu-λΙ|=1-λ01 01-λ0 101-λ=(1-λ)(-λ)(2-λ)=0 可得Φu的三个特征值为λ1=2，λ2=1，λ3=0。 最佳正交变换后的协方差矩阵为Φx=200 010 000，设此时的最佳正交变换矩阵为A=［ξ1ξ2ξ3］，则 Φuξ1=λ1Ι101 010 101ξ1=2ξ1ξ1=12 0 12 Φuξ2=λ2Ι101 010 101ξ2=ξ2ξ2=0 1 0 Φuξ3=λ3Ι101 010 101ξ3=0ξ3=12 0 -12 所以，最佳正交变换矩阵A=12012 010 120-12。 注： 本题考查的知识点是5.4.7节变换编码。 题解： (1)由变换前信号的协方差矩阵的特征根得变换后的协方差矩阵； (2)利用线性代数求正交变换矩阵。 31. 设信源协方差矩阵Φu=abb0 ba0b b0ab 0bba，试用DFT变换计算Φx。 解答： 由DFT的变换公式得 Φx=ADF·Φu·A *TDF =121111 1-i-1+i 1-11-1 1+i-1-iabb0 ba0b b0ab 0bba×121111 1+i-1-i 1-11-1 1-i-1+i =a+2b000 0(a-b)00 00a0 000a-b 注： 本题考查的知识点是5.4.7节变换编码。题解： (1)DFT变换矩阵； (2)变换前后的协方差矩阵。 32. 若仍应用31题中的协方差矩阵Φu值，变换采用沃尔什哈达马变换，试求Φx，并与31题的结果相比较。 解答： 由沃尔什哈达马变换公式得 Φx=AWH(4)ΦuAWH(4)T =121111 1-11-1 11-1-1 1-1-11abb0 ba0b b0ab 0bba×121111 1-11-1 11-1-1 1-1-11 =a+2b000 0a00 00a0 000a-2b 可以看出，与31题的结果作比较，两矩阵在形式上都是对角阵，只是对角线上的元素不同。 注： 本题考查的知识点是5.4.7节变换编码。题解： (1)哈达马变换矩阵； (2)变换前后的协方差矩阵。 33. (1)若用DCT对第31题中的信源进行变换，试求变换后的协方差矩阵； (2)若 信源的协方差矩阵Φu=ab0b bab0 0bab b0ba，试求变换后的协方差矩阵。 解答： (1) DCT变换矩阵ADCT(4)=121111 cd-d-c 1-1-11 d-cc-d，其转置 ATDCT(4)=121c1d 1d-1-c 1-d-1c 1-c1-d，其中，c=2cosπ8，d=2cos3π8。 Φx=ADCTΦuATDCT=121111 cd-d-c 1-1-11 d-cc-d·abb0 ba0b b0ab 0bba×121c1d 1d-1-c 1-d-1c 1-c1-d =a+2b000 012a(c2+d2)00 00a-2b0 00012a(c2+d2) 将c和d的值代入后得： Φx=a+2b000 0a00 00a-2b0 000a。 (2) 由题意，协方差矩阵变为Φu=ab0b bab0 0bab b0ba，则 Φx=ADCTΦuATDCT=121111 cd-d-c 1-1-11 d-cc-dab0b bab0 0bab b0ba×121c1d 1d-1-c 1-d-1c 1-c1-d =144a+8b000 02a(c2+d2)-2b(c2+d2)+4bcd02b(d2-c2) 004a0 02b(d2-c2)02a(c2+d2)-2b(c2+d2)+4bcd 将c和d代入，得Φx=a+2b000 0(a-b)+0.707b0-0.708b 00a0 0-0.708b0a-b-0.707b。 注： 本题考查的知识点是5.4.7节变换编码。题解： (1)DCT变换矩阵； (2)变换后，信号的协方差矩阵的对角性。 34. 若已知信源的协方差矩阵Φu=abbb babb bbab bbba，试求： (1)由KL变换所得输出协方差矩阵Φx； (2)用哈尔变换求输出的协方差矩阵Φx。 解答： (1) 设KL变换的变换矩阵 A=1000 0100 0010 0001，因为A是正交的，所以有 aiΦuaTi=λi，其中，λ1=(1000)Φu1 0 0 0=a，λ2=(0100) Φu0 1 0 0=a，λ3=(0010)Φu 0 0 1 0=a，λ4=(0001)Φu 0 0 0 1=a。 此时，Φx=AΦuAT=a a a a。 (2) 设哈尔变换的变换矩阵AHr(4)=121111 11-1-1 2-200 002-2，则 Φx=AHrΦuATHr =14a+3ba+3ba+3ba+3b a-ba-bb-ab-a 2(a-b)2(b-a)00 002(a-b)2(b-a)·1120 11-20 1-102 1-10-2 =a+3b000 0a-b00 00a-b0 000a-b 注： 本题考查的知识点是5.4.7节变换编码。题解： KL变换。