信息论与编码考试试卷

信息论与编码考试试卷

2012——2013学年 第一学期

课程名称：信息论与编码

试卷形式：开卷□闭卷□

试题 得分 一 二 三 四 五 六 七 八 总分 常用对数：log23?1.585

一、 选择题（共10分，每小题2分）

x2x3x4??X??x1、有一离散无记忆信源X，其概率空间为????1，??P??0.50.250.1250.125?则其无记忆二次扩展信源的熵H(X2)=( )

A、1.75比特/符号； B、3.5比特/符号； C、9比特/符号； D、18比特/符号。

0000??P(y1/x1)P(y2/x1)?，00P(y/x)P(y/x)002、信道转移矩阵为?3242???000P(y5/x3)P(y6/x3)??0?其中P(yj/xi)两两不相等，则该信道为

A、一一对应的无噪信道 B、具有并归性能的无噪信道 C、对称信道

D、具有扩展性能的无噪信道

3、设信道容量为C，下列说法正确的是：（ ） A、互信息量一定不大于C

B、交互熵一定不小于C C、有效信息量一定不大于C D、条件熵一定不大于C

4、在串联系统中，有效信息量的值（ ） A、趋于变大 B、趋于变小 C、不变 D、不确定

5、若BSC信道的差错率为P，则其信道容量为：（ ） A、

H?p?

p??1?plog2??1?p?p??? ??B、

C、

1?H?p?

D、?Plog(P)

二、 填空题（20分，每空2分）

1、 (7,4)线性分组码中，接受端收到分组R的位数为____ ，伴随式S可能的值有____ 种,差错图案e的长度为 ，系统生成矩阵Gs为____ 行的矩阵，系统校验矩阵Hs为____ 行的矩阵，Gs和Hs满足的关系式是 。

2、 一张1024×512像素的16位彩色BMP图像能包含的最大信息

量为 。

3、 香农编码中,概率为P(xi)的信源符号xi对应的码字Ci的长度Ki应

满

足

不

等

式 。

?0.250.50.25??，则它是 信0.250.250.53、设有一个信道，其信道矩阵为 ?????0.50.250.25??道（填对称，准对称），其信道容量是 比特/信道符号。

?X??x1x2?三、（20分）????，通过一个干扰信道，接受符号集为??P(X)??0.50.5?Y??y1?1?4y2?，信道转移矩阵为??3??43?4?? 1?4??试求（1）H(X),H(Y),H(XY);（7分） (2) H(Y|X),H(X|Y);（5分） (3) I(Y;X)。（3分） (4)该信道的容量C（3分）

（5）当平均互信息量达到信道容量时，接收端Y的熵H（Y）。（2分） 计算结果保留小数点后2位,单位为比特/符号。

四、（9分）简述平均互信息量的物理意义，并写出对应公式。

五、（10分）假设英文字母表(n=26),密钥k=abc，当明文m=familycome时，使用Vigenere密码算法后得到的密文c=？请写出具体的步骤。

六、（10分）设有离散无记忆信源，其概率分布如下：

?x?X??1????1?P(X)???2x214x3x411816x5132x6164x7??1? 64??对其进行费诺编码，写出编码过程，求出信源熵、平均码长和编码效率。

七、信道编码（21分）

?1?0现有生成矩阵Gs???0??0010000100001110111101?0?? 1??1?

1. 求对应的系统校验矩阵Hs。（2分）

2. 求该码字集合的最小码字距离d、最大检错能力lmax 、最大纠错能力t max 。（3分）

3. 填写下面的es表 （8分） e 0000000 0000001 0000010 0000100 0001000 0010000 0100000 1000000

4. 画出该码的编码电路 （4分）

s ?。4. 现有接收序列为r?(1100100)，求纠错译码输出c（4分）

试题答案

一、 选择题（每题2分，共10分） 1、B 2、D 3、C 4、B 5、A

二、 填空题（每空2分，共20分） 1、 7,8,7,4,3,GsHsT=0或则HsGsT=0。 2、 8M bit。

3、 ?log2P(xi)?Ki??log2P(xi)?1

4、 对称，0.085比特/信道符号。 三、（15分）

解：(1)由已知条件得p(X=0)=1/2,p(X=1)=1/2…………………… （2分）

p(Y=0)=1/2,p(Y=1)=1/2……………………（2分）

因此

H（X）=1比特/符号……………………………………（1分） H（Y）=1比特/符号……………………………………（1分） H（XY）=1.811比特/符号…..…………………………（1分）

比特/符号（2.5分） （2）H(Y/X)?H(XY)?H(X)?0.811? H(X/Y)H(XY?)H(Y?)0.比8特11符号/2.5分） （

（3）I(X;Y)?H(X)?H(X/Y)?H(Y)?H(Y/X)?0.189比特/符号（3分） （4）该信道为对称信道，根据对称信道的信道容量公式得：

34??1C?log2m?H?q1,q2??1??log24?log2??0.189bit/signal（3分）

43??4（5）该信道为对称信道，当平均互信息量达到信道容量时，信宿呈等概分布，其熵为：

H（Y）= log 2 m =1比特/符号（2分） 四、（10分） 答：

1、I(X;Y)?H(X)?H(XY) （1分）

平均互信息量是收到Y前、后关于X的不确定度减少的量，即由Y获得的关于X的平均信息量。 （2分）

2、I(X;Y)?H(Y)?H(YX) （1分）

平均互信息量是发送X前、后，关于Y的平均不确定度减少的量。（2分） 3、I(X;Y)?H(X)?H(Y)?H(XY)

（1分）

平均互信息量等于通信前、后，整个系统不确定度减少的量。（2分） 五、(10分)答：费杰尔密码算法的过程是： 设密码k＝k1k2k3…kd，明文与密文字母表中均包含了n个字母，又设明文m＝m1m2…，

密文为c＝c1c2…，则ci=mi+ki(mod n)。

则，明文为m=familycome，k=abc，加密之后的结果为： m1=f->5，k1=a->0，c1=5+0(mod 26)=5->f 1分 m2=a->0,k2=b->1,c2=0+1(mod 26)=1->b 1分 m3=m->12,k3=c->2,c3=12+2(mod 26)=14->o 1分 m4=i->8,k4=a->0,c4=8+0(mod 26)=8->i 1分 m5=l->11,k5=b->1,c5=11+1(mod 26)=12->m 1分 m6=y->24,k6=c->2,c6=24+2(mod 26)=0->a 1分 m7=c->2,k7=a->0,c7=2+0(mod 26)=2->c 1分 m8=o->14,k8=b->1,c8=14+1(mod 26)=15->p 1分 m9=m->12,k3=c->2,c9=12+2(mod 26)=14->o 1分 m10=e->4,k3=a->0,c10=4+0(mod 26)=4->e 1分 结果为：fboimacpoe

六、（10分）解：（1）编码如下表所示 （7分）

x p(xi) 码字 x 0.5 0 0 x 0.25 10 110 1110 11110 111110 1111111 x 0.125 0.0625 10.03125 0 x x 01x 0.015625 0.015625 x （2）平均码长

11111163K??1??2??3??4??5??6?2??1.97比特/符号（1分）

24816326432信源熵H(X)???p(x)logii?172p(xi)?63?1.97比特/符号……………（1分） 32编码效率??H(X)H(X)H(X)???1……………………………….（1分） RKKlog2mL?1101100???七、解：（1）Hs??1110010?………………………………..（2分）

?1011001???(2) 最小码距d=3，最大检错能力lmax=2，最大纠错能力 tmax=1…………….（3分） (3)

e 0000000 0000001 0000010 0000100 0001000 0010000 0100000 1000000 s 000 001 010 100 101 011 110 111

（8分） 计算接收到的序列r?(1100100)对应的伴随式

s?rHT?(101)

（2分）

对应的e为（0001000）纠错译码输出为

c?r?e?(1100100)?(0001000)?(1101100)………………………..（2分）

编码电路 (4分)

(m0, m1, m2, 3 m2 m1 m0 mt=0,(c0, c1, c2, c3 ,c4, c5, t=4,c6 c5 c4

本文来源：https://www.bwwdw.com/article/c8t2.html