信息论与纠错编码题库

12/31/3x1 1/3x3 1/3x5 1/6x7 1/61010101编码1/311100100x1 1/3x3 1/3x5 1/6x7 1/610210编码102120X的D=2霍夫曼编码13/52/52/5y0 1/5y2 1/5y4 1/5y6 1/5y8 1/5Y的D=2霍夫曼编码10101010X的D=3霍夫曼编码1

编码100100111110y0 1/5y2 1/5y4 1/5y6 1/5y8 1/53/52编码1010222120210Y的D=3霍夫曼编码

根据级联的定义易知，级联后的新变长码的霍夫曼编码为： 序号k 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

X·Y x1·y0 x1·y2 x1·y4 x1·y6 x1·y8 x3·y0 x3·y2 x3·y4 x3·y6 x3·y8 x5·y0 x5·y2 x5·y4 x5·y6 x5·y8 D=2霍夫曼编码 1110 1101 1100 11111 11110 1010 1001 1000 10111 10110 0110 0101 0100 01111 01110 D=2编码码长 4 4 4 5 5 4 4 4 5 5 4 4 4 5 5 D=3霍夫曼编码 11 10 122 121 120 01 00 022 021 020 211 210 2122 2121 2120 D=3编码码长 2 2 3 3 3 2 2 3 3 3 3 3 4 4 4 概率 1/15 1/15 1/15 1/15 1/15 1/15 1/15 1/15 1/15 1/15 1/30 1/30 1/30 1/30 1/30

16 17 18 19 20 x7·y0 x7·y2 x7·y4 x7·y6 x7·y8 200010 0001 0000 00111 00110 4 4 4 5 5 201 200 2022 2021 2020 3 3 4 4 4 1/30 1/30 1/30 1/30 1/30 H(X·Y)= –

q(xk?y)logq(xk?y)=4.24(比特/符号) ?kkk?1D=2时，平均码长n1=4?3222+5?==4.4（码元/符号） 555=

编码效率

?1=

H(X?Y)n1logD4.24=0.96364

4.4?log2编码效率比②所得的编码效率0.98422低； D=3时，平均码长n2=2?48344+3?+4?==2.93（码元/符号） 15151515=

编码效率

?2=

H(X?Y)n2logD4.24=0.91302

2.93?log3编码效率比②所得的编码效率0.98425低。 （4） 当D=2时，n1=4.4，

H(X?Y)4.24==4.24

logDlog2故满足

H(X?Y)H(X?Y)+1，即满足香农第一定理； ?n1<

logDlogDH(X?Y)4.24==2.68

logDlog3当D=3时，n2=2.93，

故满足

H(X?Y)H(X?Y)+1，即满足香农第一定理； ?n2<

logDlogD