信息论与纠错编码题库

4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 x2x1x1 x1x1x3 x1x3x1 x3x1x1 x1x2x2 x2x1x2 x2x2x1 x1x2x3 x1x3x2 x2x1x3 x2x3x1 x3x1x2 x3x2x1 x2x2x2 x1x3x3 x3x1x3 x3x3x1 x2x2x3 x2x3x2 x3x2x2 x2x3x3 x3x2x3 x3x3x2 x3x3x3 1011 0100 0011 0010 0001 0000 11111 10100 01111 01110 01101 01100 01011 01010 111011 111010 111001 111000 101011 101010 1111011 1111010 1111001 1111000 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 0.075 0.05 0.05 0.05 0.045 0.045 0.045 0.03 0.03 0.03 0.03 0.03 0.03 0.027 0.02 0.02 0.02 0.018 0.018 0.018 0.012 0.012 0.012 0.008

10.5830.41710.31700.26610.22700.190.1670.150.141a1 0.1250.120.1070.10.090.0890.078a2 0.075a3 0.075a4 0.0750.0660.060.060.057a5 0.05a6 0.05a7 0.05a8 0.045a9 0.045a10 0.0450.0440.040.0380.036a11 0.03a12 0.03a13 0.03a14 0.03a15 0.03a16 0.03a17 0.0270.0240.02a18 0.02a19 0.02a20 0.02a21 0.018a22 0.018a23 0.018a24 0.012a25 0.012a26 0.012a27 0.0081101010101100111001010101010101010编码100110111001011100100001100010100010000011111101000111100111001101011000101101010101010111011111010111100101110001010111010101111011111101011110011111000

平均码长n3=3?0.125+4?0.465+5?0.252+6?0.114+7?0.044=4.49（码元/符号） 信源熵H（

X(3)）=-

m?1?q(xm)logq(xm)=4.46(比特/符号)

=

27(3)(3)编码效率?=

H(X(3))n3logD4.46=0.99

4.49?log2n?0.89?2?0.11?3?2.11码元/符号

??LH(X)3.15??100%?94.1%

nlogD2.11?log3

3.21

（1）两个无前缀变长码的级联定义为

C=C1·C2,即?c1?C1,?c2?C2,c?c1?c2?C 证明：无前缀变长码的级联仍然是无前缀变长码。 （2）考虑以下系统： 设有两个互相独立的信源

?y0y2y4y6y8??x1x3x5x7??X?????和Y= =?1 1 1 1 1? 1111???????q(Y)????q(X)???556356?5???5??3?1??2定义=?k?1??2zzxykk为奇数，k=0,1,2,3,4,5,6,7,8

k为偶数k① {

k}的熵为多少？

}分别设计D=2，D=3的霍夫曼编码，比较编码效率?；

② 对{③ 对{

zxkk}和{y}分别设计D=2，D=3的霍夫曼编码，将它们级联后得到一个新的无前缀变

k长码，并将它们的编码效率与②的结果比较；

④ 验证③中的级联码是否仍然满足香农第一定理。 解： （1）证明：设

c={c,c1112112,……，

c1M}， }， ·

c2={C={

c,c2222,……，·

cc2Mc11·

c221，

c11·

c，

c11c2M，

c12c21，

c12·

c22，

c12·

c2M……}

因为

即cc，c都是无前缀编码，

11i不是

1j的前缀（i!=j），同理

c2i不是

c2j的前缀（i!=j）

故对任意的C=

c·c={c·c121i2j} （ 1

当i取任一值，j 为变量，因为c2为无前缀码，故级联之后的仍为无前缀变长码； 当j取任一值，i 为变量，因为

c为无前缀码，故级联之后的仍为无前缀变长码；

1故 无前缀变长码的级联码仍为无前缀变长码。

（2）①由题知： Z q(Z) 序号 z0 1/10 a3 z1 1/6 a1 z2 1/10 a4 z3 1/6 a2 z4 1/10 a5 z5 1/12 a8 z6 1/10 a6 z7 1/12 a8 z8 1/10 a7

则H（

zk）=–

?8q(zk)logq(zk)=0.862+1.661+0.597=3.12(比特/符号) k?0② 编码图如下：

13/512/5011/314/15013/3021/5111/50编码3/101/614/150a1 1/60110a1 1/62a2 1/61101a2 1/61a3 1/100100a3 1/100a4 1/101011a4 1/102a5 1/100010a5 1/101a6 1/101001a6 1/100a7 1/100000a7 1/102a8 1/1211111a8 1/121a9 1/1201110a9 1/120D=2的霍夫曼编码D=3的霍夫曼编码D=2时，平均码长n1=3?56+4?16=196=3.17（码元/符号） 编码效率

?=

H(Z)3.1n=12.17?log2=0.98422

1logD3D=3时，平均码长n2=2（码元/符号） 编码效率

?=

H(Z)=

3.122n2logD2?log3=0.98425

③ {

xk}和{yk}的编码如下图:

编码222120121110020100