信息论基础与编码(第五章)

5-1 有一信源，它有六种可能的输出，其概率分布如下表所示，表中给出了对应的六种编码C1、C2、C3、C4、C5和C6。

（1） 求这些码中哪些是唯一可译码； （2） 求哪些是非延长码（即时码）；

（3） 对所有唯一可译码求出其平均码长。

消息 概率C1 000 001 010 011 100 101 C2 0 01 011 0111 01111 C3 0 10 110 1110 11110 C4 0 10 C5 1 000 C6 01 001 100 101 110 111 a1 1/2 1/4 1/16 1/16 1/16 1/16 a2 a3 a4 a5 a6 1101 001 1100 010 1001 110 011111 111110 1111 110 解：（1）1,2,3,6是唯一可译码； (2)1,3,6是即时码。

5-2证明若存在一个码长为l1,l2,,lq的唯一可译码，则一定存在具有相同码长的即时码。

证明：由定理可知若存在一个码长为L1,L2,,Lq的唯一可译码，则必定满足kraft不等式

ri1qli由定理44可知若码长满足kraft不等式，则一定存在这样码长的即时码。1。

所以若存在码长L1,L2,,Lq的唯一可译码，则一定存在具有相同码长P（y=0）的即时码。

Ss15-3设信源P(s)p1s2p26s6，pi1。将此信源编码成为r元唯一可p6i1译变长码（即码符号集X{x1,x2,,xr}），其对应的码长为（l1,l2,,l6）=（1，1，2，3，2，3），求r值的最小下限。

解：要将此信源编码成为 r元唯一可译变长码，其码字对应的码长

（l1 ,l2 ,l3, l4,l5, l6）=(1,1,2,3,2,3) 必须满足克拉夫特不等式，即

ri16lir1r1r2r3r2r31

1 / 13

. .

所以要满足

2221 ，其中 r是大于或等于1的正整数。 rr2r3222可见，当r=1时，不能满足Kraft不等式。 当r=2, 1，不能满足

248222261，满足Kraft。 392727Kraft。

当r=3,

所以，求得r的最大值下限值等于3。

5-4设某城市有805门公务和60000门居民。作为系统工程师，你需要为这些用户分配。所有均是十进制数，且不考虑系统中0、1不可用在首位的限制。（提示：用异前缀码概念） （1）如果要求所有公务为3位长，所有居民等长，求居民长度L1 的最小值； （2）设城市分为A、B两个区，其中A区有9000门，B区有51000门。现进一步要求A区的比B区的短1位，试求A区长度L2的最小值。

解：(a) 805门要占用1000个3位数中的805个，即要占用首位为0～ 7的所有数字与以8为首的5个数字。因为要求居民等长， 以9为首的数字5位长可定义10 000个，6位长可定义100 000 个。所以

3L1minL16。或由Craft不等式，有

80510600001018051031解得L1log105.488， 即

60000minL16

(b) 在(a)的基础上，将80为首的数字用于最后5个公务，81～86 为首的6位数用于B区51 000个，以9为首的5位数用于A区9 000 个。所以，minL2式，有80510或8051035。或由Draft不等

900010L25100010(L21)1

3(900051000101)10L21

18051034.859即minL25 解得L2log109000510011122(5-5求概率分布为3,5,5,15,15)的信源的二元霍夫曼码。讨论此码对于概率分布为

11111(,,,,)的信源也是最正确二元码。 5555511122p(s)(,,,,)i解：信源的概率分布为：

3551515

二元霍夫曼码：00，10，11，010，011，码长：2，2，2，3，3

2 / 13

. .

11111(当信源给定时，二元霍夫曼码是最正确二元码。所以对于概率分布为5,5,5,5,5)的信

源，其最正确二元码就是二元霍夫曼码。这二元霍夫曼码一定是三个信源符号的码长为2（码

符号/信源符号），另二个信源符号的码长为3（码符号/信源符号），其平均码长最短。因此，

11122(上述对概率分布为3,5,5,15,15)信源所编的二元霍夫曼码也是概略分布为

11111(,,,,)信源的最正确二元码。 555555-6 设二元霍夫曼码为（00，01，10，11）和（0，10，110，111），求出可以编得这些霍夫曼码的信源的所有概率分布。

解：由题意 假设信源所发出的是个符号的概率为 P(S4)P(S3)P(S2)P(S1) 由霍夫曼编码的特点知：P(S4)P(S3)P(S2)P(S1)1

根据霍夫曼编码的方法，每次概率最小的两个信源符号合并成一个符号，构成新的缩减信源，直至最后只剩两个符号。而且当缩减信源中的所有符号概率相等时，总是将合并的符号放在最上面。所以，对于二元霍夫曼码为（00，01，10，11）来说，每个信源都要缩减一次，所以P(S3)P(S4)要大于P(S1)和P(S2)，这时必有

11P(S1)P(S2),P(S1)

33同理对于二元霍夫曼码为（0，10，110，111）有

11P(S3)P(S4),P(S1)>

33信源概率分布满足以上条件则其霍夫曼编码符合题意。

P(s1)1/2,P(s2)1/4,P(s3)1/8，5-7 设一信源有K=6个符号，其概率分别为：P(s4)P(s5)1/20，P(s6)1/40，对该信源进行霍夫曼二进制编码，并求编码效率。

解：相应的Huffman编码是：{1,01,001,0001,00000,00001}。平均码长=1.95，熵=1.94

H(X)1.940.995 1.95Llog25-8 设信源概率空间为：

Ss1,s2Ps=0.1,0.9，

（1）求HS和信源冗余度；

（2）设码符号为X={0,1}，编出S的紧致码，并求紧致码的平均码长L；

（3）把信源的N次无记忆扩展信源S编成紧致码，试求N=2，3，4，时的平均码长

N3 / 13

. .

LNN； （4）计算上述N=1，2，3，4这四种码的编码效率和码冗余度。 解：（1）信源

Ss1s2Ps0.10.9 其 H2sPsilogPsi0.469 比特/符号

i1剩余度1Hslog20.531=53.1％

（2）码符号X={0,1}，对信源S编紧致码为：s10，s21 其平均码长L=1 码符号/信源符号 (3) 当N=2时

S21s1s1,2s1s2P=,3s3s1,4s2s2i0.01,0.09,0.09,0.81

紧致码（即霍夫曼码）为

4,3,2,1

码字Wi 0 , 10 , 110 , 111 码长li 1 , 2 , 3 , 3

4平均码长LN1N=2Pili0.645 码符号/信源符号

i1N=3时，S3P=

i1,2,3,4,5,6,7,0.13,0.120.9,0.120.9,0.120.9,0.10.92,0.10.92,0.10.92,

对信源S3进行霍夫曼编码，其紧致码为

8,7,6,5,4,3,2,1

码字Wi 0 , 100 , 101 , 110 , 11100 , 11101 , 11110 ,

11111

码长li 1 , 3 , 3 , 3 , 5 , 5 , 5 ,

5

8平均码长 LN1ilN=3Pi0.533 码符号/信源符号

i1N=4时，S4Pi=

4 / 13

80.93. .

0.120.92,0.120.92,0.120.92,

对信源S4进行霍夫曼编码，其紧致码为

1,0.14,9,0.130.9,0.130.9,0.130.9,0.130.9,0.120.92,0.120.92,0.120.92,10,11,0.10.9,0.10.9,0.10.9,0.10.9,33332,3,4,5,6,7,8,12,13,14,15,0.941616,15,14,13,12,11,10,9,

码字Wi 0 , 100 , 101 , 110 , 1110 , 111110 , 1111000 , 1111001,

码长li 1 , 3 , 3 , 3 , 4 , 6 , 7 , 7 ,

8,7,6,5,4,3,2,1

码字Wi 1111010 , 1111011 , 1111110 , 111111101 , 111111110 , 111111111 , 1111111000 , 1111111001

码长li 7 , 7 , 7 , 9 , 9 , 9 , 10 , 10

L平均码长NN1=4Plii116i0.493 码符号/信源符号

N=时，根据香农第一定理，其紧致码的平均码长

NlimLNHs0.469 码符号/信源符号 =

NlogrLLHSHS1码剩余度 1－1r (r=2) LL所以 N=1 编码效率10.469 码剩余度0.531=53.1% N=2 20.727 0.273=27.3% N=3 30.880 0.120=12%

N=4 40.951 0.049=4.9%

从此题讨论可知，对于变长紧致码，当N不很大时，就可以达到高效的无失真信源编码。 5-9设信源空间为：(4) 编码效率 HrSHS (r=2)

s5s6s7s8Ss1s2s3s4 =，码P(s)0.40.20.10.10.050.050.050.05符号为X={0,1,2}，试构造一种三元紧致码。

解：得信源符号 s1 s2 s3 s4 s5 s6 s7 s8 三元紧致码 1 00 02 20 21 22 010 011

5-10 某气象员报告气象状态，有四种可能的消息：晴、云、雨和雾。若每个消息是等概的，那么发送每个消息最少所需的二元脉冲数是多少？又若四个消息出现的概率分别是1/4，1/8，1/8和1/2，问在此情况下消息所需的二元脉冲数是多少？如何编码？

5 / 13

. .

解： 第一种情况：需要二元脉冲数两个，可表示四种状态，满足我们的要求。

第二种情况：我们采用霍夫曼可编为1/2编为 1；1/4编为01，1/8编为000和001，脉冲数显然。

5-11 若某一信源有N个符号，并且每个符号等概率出现，对这信源用最正确霍夫曼码进行二元编码，问当N2i和N2i＋（i是正整数）时，每个码字的长度等于多少？平均码长是多少？

解：当N2(i正整数)时用霍夫曼编码方法进行最正确编码，由于每个符号是等概率分布的，所以每个符长应相等，这样平均码长最短，而且信源符号个数正好等于2i，则满足： q22，所以每个码字的码长lii,Li。

当N2i个1时，因为每个符号等概率分布出现，所以每个符号的码长也应该基本相等，但现在信源符号个数不是正好等于2i，所以必须有两个信源符号的码长延长一位码长，这样平均码长最短。

i所以N2i1时21个码字的码长为lii，其余2个码字的码长为i1。平均码长

liiLi2。 i215-12 若有一信源

Ss1,s2P(s)0.8,0.2 每秒钟发出2.66个信源符号。将此信源的输出符号送入某一个二元信道中进行传输（假设

信道是无噪无损的），而信道每秒钟只传递2个二元符号。试问信源不通过编码能否直接与信道连接？若通过适当编码能否在此信道中进行无失真传输？若能连接，试说明如何编码并说明原因。

解：信源

H(s)P(si)logP(si)ss1,s2，其信源熵 i1P(s)0.8,0.20.722比特/符号2而其每秒钟发出2.66个信源符号，所以信源输出的信息速率为：

Rt2.66H(s)2.660.722符号秒比特/符号

1921.比特/秒送入一个二元无噪无损信道，此信道的最大信息传输率（信道容量）C1比特/符号。

而信道每秒钟只传输两个二元符号，所以信道的最大信息传输速率为：

Ct2C比特/符号符号/秒2比特秒可见：RtCt。

根据无噪信道编码定理（即无失真信源编码定理），因RtCt。所以总能对信源的输出进行

6 / 13

. .

适当的编码，使此信源能在此信道中进行无失真地传输。如果对信源不进行编码，直接将信源符号s1以“0”符号传送，s2以“1”符号传送，这时因为信源输出为2.66（二元信源符号/秒），大于2（二元信道符号/秒），就会使信道输入端造成信源符号的堆积，信息不能按时发送出去。所以，不通过编码此信源不能直接与信道连接。若要连接，必须对信源的输出符号序列进行编码，也就是对此信源的N次扩展信源进行编码。但扩展次数越大，编码越复杂，设备的代价也越大，所以尽量使扩展的次数N少，而又能使信源在此信道中无失真传输。先考虑N2，并对二次扩展信源进行霍夫曼编码，得：

s2s1s1,s1s2,s2s1,s2s2P(ss)0.64,0.16,0.16,0.04ij 二元霍夫曼码

0,10,110,111

得：

L21.56二元符号/二个信源符号L=0.78二元符号/信源符号二次扩展编码后，送入信道的传输速率为：

0.782.66二元符号信源符号信源符号/秒 2.075 二元符号/秒>2二元符号/秒所以，必须考虑N3即对三次扩展信源进行霍夫曼编码，得：

s3s1s1s1,s1s1s2,s1s2s1,s2s1s1,s1s2s2,s2s1s2,s2s2s1,s2s2s2 P(sisjsk)0.512,0.128,0.128,0.128,0.032,0.032,0.032,0.008二元霍夫曼码1,000,001,010,01100,01101,01110,01111

得：

L32.184二元符号/三个信源符号L=0.728二元符号/信源符号

三次扩展码后，送入信道额传输速率为：

0.7282.66二元符号信源符号信源符号/秒 1.9365 二元符号/秒<2二元符号/秒此时，就可以在信道中进行无失真传输了。

5-13 现有一幅已离散量化后的图像，图像的灰度量化分成8级，如下表所示。表中数字为相应像素上的灰度级。

1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 1 1 1 1 2 7 / 13

. .

2 3 4 5 7 2 3 4 5 7 2 3 4 5 7 2 3 4 5 7 2 3 4 5 7 2 3 4 5 8 2 3 4 6 8 2 3 4 6 8 2 3 4 6 8 2 3 4 6 8 另有一无噪无损二元信道，单位时间（秒）传输100个二元符号。

（1）现将图像通过给定的信道传输，不考虑图像的任何统计特性，并采用二元等长码，问需多长时间才能传送完这幅图像？

（2）若考虑图像的统计特性（不考虑图像的像素之间的依赖性），求这图像的信源熵

H(S)，并对每个灰度级进行霍夫曼最正确二元编码，问平均每个像素需用多少二元码符号

来表示？这时需多少时间才能传送完这幅图像？

（3）从理论上简要说明这幅图像还可以压缩，而且平均每个像素所需的二元码符号数可以小于H(S)比特。

解：（1）3秒。（2）2.59秒。

5-14设某无记忆二元信源，概率p1=P(1)=0.1，p0=P(0)=0.9，采用下述游程编码方案:第一步，根据0的游程长度编成8个码字，第二步，将8个码字变换成二元变长码，如下表所示：

信源符号序列 1 01 001 0001 00001 000001 0000001 00000001 00000000 中间码 S0 S1 S2 S3 S4 S5 S6 S7 S8 二元码字 1000 1001 1010 1011 1100 1101 1110 1111 0 （1） 试问最后的二元变长码是否是唯一可译码； （2） 试求中间码对应的信源序列的平均长度L1；

（3） 试求中间码对应的变长码二元码码字的平均长度L2；

（4） 计算比值L2/L1，解释它的意义，并计算这种游程编码的编码效率； （5） 若用霍夫曼编码，对信源的四次扩展信源进行直接编码，求它的平均码长L(对

8 / 13

. .

应于每一个信源符号)，并计算编码效率，试将此方法与游程编码方法进行比较；

（6） 将上述游程编码方法一般化，可把2s1个信源序列(上例中s=3)变换成二元变长码，即2s个连零的信源序列编为码字0，而其他信源序列都编成s+1位的码字.若信源输出零的概率为p0，求L2/L1的一般表达式，并求p0=0.995时s的最正确值。

解: (1) 根据唯一可译码的判断方法可知，最后的二元变长码是非延长码(即时码，所以它是唯一可译码。

(2) 因为信源是二元无记忆信源，所以有P(si)= P(si1) P(s2)…P(sin) 其中 si =( si1 si2…sin) si1, si2,…sin{0,1}

已知p1=P(1)=0.1， p0=P(0)=0.9，可求得信源符号序列的概率P(si)。根据编码，可排出以下表

信源符号序列 1 01 001 0001 00001 000001 0000001 00000001 00000000 根据表可计算 L1=

i08序列的概率P(si) 0.1 0.09 0.081 0.0729 0.06561 0.059049 0.0531441 0.04782969 0.43046721 8信源符号序列长度l1i 1 2 3 4 5 6 7 8 8 中间码 S0 S1 S2 S3 S4 S5 S6 S7 S8 二元码码长l2i 4 4 4 4 4 4 4 4 4 P(Si)l1i≈5.6953 信源符号/中间码 P(Si)l2i≈2.7086 二元码/中间码

i0(3) 根据表计算 L2=(4)

L2≈0.4756 二元码/信源符号 L1此值为每个信源符号所需的二元码符号数，也就是无记忆二元信源采用游程编码后每个二元信源符号所需的平均码长。

可计算无记忆二元信源的信息熵

2H(S) =-i1P(Si)logP(Si)≈0.4690 比特/信源符号

所以，这种游程编码的效率

η=

H(S)≈0.986≈98.6 % L2/L19 / 13

. .

(其中因为二元编码所以Hr(S)=H(S))

(5)若对无记忆二元信源的次扩展信源直接进行霍夫曼编码，可得 S 0000 0001 0010 0100 1000 0011 0101 0110 4P(si) 0.6561 0.0729 0.0729 0.0729 0.0729 0.0081 0.0081 0.0081 16码字Wi 0 110 100 101 1110 111110 1111000 1111001 码长li 1 3 3 3 4 6 7 7 S 1001 1010 1100 0111 1011 1101 1110 1111 4P(si) 0.0081 0.0081 0.0081 0.0009 0.0009 0.0009 0.0009 0.0001 码字Wi 1111010 1111011 1111110 111111100 111111101 111111110 1111111110 1111111111 码长li 7 7 7 9 9 9 10 10 L4=

i1P(Si)li≈1.9702 二元码/4个信源符号

得 L=0.4926 二元码/信源符号 编码效率η=

H(S)≈0.952≈95.2 % L此编码效率低于游程编码方法。这是因为霍夫曼码只考虑N=4(固定值)时进行压缩，使概率大的对应于短码，概率小的对应于长码。但无记忆二元信源符号“0”出现的概率p0很大，所以在信源输出序列中符号“0”连续出现的概率较大，而连续出现符号“1”的概率极小。游程编码正是考虑了这些特性，使N较长(N=8)的连续出现的符号“0”序列压缩成一个二元码符号。所以，游程编码的编码效率较高。当然，当N很大时(N=8)霍夫曼编码效率会提高，但其编码方法没有游程编码方法来得简单。 (6) 一般游程编码方法是将2+1个信源序列中一个2个连续为零的序列编成码字0，而其他信源序列编成码长为s+1的码字，所以根据表中类似计算可得

2ss

s

L1=

i1i1ip1p02 2sp0s其中p0为信源中符号“0”出现的概率， p1为符号“1”出现的概率，有p0+ p1=1。

展开上式，得

22L1 = p0+2p1 p0+3 p1p0+…+2sp1p0s12+2sp0

ss

2 =(1- p0)[(1+2 p0+3p0+…+2sp0212)]+2sp0

ss2 =(1+2p0+3p0+…+2sp02s12322+2sp0)-( p0+2p0+3p0+…+2sp0)

s2 =(1+ p0+p0+…+p02s1) 10 / 13

. .

2

1p0

=

1p0

s

根据表中类似计算，得

2sL2=(s+1)

i1ip1p012 p02ss

得

2 =(s+1) [(1- p0)(1+ p0+p0+…+p022 =(s+1)(1-p0)+p0 2 =1+s(1-p0)

sss12)]+p0

sL2的一般表达式为 L1L21p0s(1p0) L==2sL11p0当p0=0.995， p1=0.005时，求s的最正确值，也就是求s取某值时L最短。可采用将L对s求偏导来解，但所得为超越方程，所以我们采用数值求解方法。 令 s=2 2=4 L=0.262

ss=3 2s=8 L=0.1422 s=4 2s=16 L=0.0849 s=5 2s=32 L=0.0587 s=6 2s=64 L=0.482 s=7 2s=128 L=0.0456 s=8 2s=256 L=0.0469

所以得最正确

当p0=0.995时二元信源的信息熵

H(S) = H(0.995) ≈0.0454 比特/信源符号

可见，当s=7时，L已极接近H(S)，编码效率达到99.5%

5-15有两个信源X和Y如下：

x2x3x4x5x6x7Xx1P(x)0.20.190.180.170.150.10.01

y2y3y4y5y6y7y8y9Yy1P(y)0.490.140.140.070.070.040.020.020.01

（1）分别用霍夫曼码编成二元变长唯一可译码，并计算编码效率； （2）分别用香农编码法编成二元变长唯一可译码，并计算编码效率； （3）分别用费诺编码法编成二元变长唯一可译码，并计算编码效率； （4）从X，Y两种不同信源来比较这三种编码方法的优缺点。 5-16 将幅度为3.25V、频率为800Hz的正弦信号输入采样频率为8000Hz采样保持器后，通过一个如题图5-16所示量化数为8的中升均匀量化器。试画出均匀量化器的输出波形。

11 / 13

. .

输出/V4321-4-3-2-101-1-2-3-4234输入/V

题图 5-16

5-17 已知某采样时刻的信号值x的概率密度函数p(x)如题图5-17所示，将x通过一个量化数为4的中升均匀量化器得到输出xq。试求：

（1） 输出xq的平均功率SE[xq];

（2） 量化噪声exqx的平均功率NqE[e]； （3） 量化信噪比S/Nq。

22p(x)1x101

题图 5-17

5-18 在CD播放机中，假设音乐是均匀分布，采样频率为44.1kHz，采用16比特的中升均匀量化器进行量化。试确定50分钟音乐所需要的比特数，并求量化信噪比S/Nq。 5-19 采用13折线A律非均匀量化编码，设最小量化间隔为，已知某采样时刻的信号值x=635。

（1）试求该非均匀量化编码c，并求其量化噪声e；

（2）试求对应于该非均匀量化编码的12位均匀量化编码c。

5-20 将正弦信号x(t)sin(1600t)输入采样频率为8kHz采样保持器后通过13折线A律非均匀量化编码器，设该编码器的输入围是[-1,1]。试求在一个周期信号值

12 / 13

'. .

xisin(0.2i)，i0,1,,9的非均匀量化编码ci，i0,1,,9。

5-21将正弦信号x(t)0.25sin(400t)输入采样频率为4kHz采样保持器后通过差分脉冲编码调制器，设该调制器的初始值dq00，x00，采用码长为4的均匀量化编码，量化间隔=0.03125。试求在半个周期信号值xi0.25sin(0.1i)，i0,1,,9的差分脉冲编码c'i和量化值xi，i0,1,,9。

13 / 13