期末试卷_11122_信息论_A_答案.pdfVIP

天津大学试卷专用纸 学院 专业 班 年级 学号 姓名 共 4 页 第 1 页 A 卷 20112012 学年第二学期期末考试试卷 信息论与编码 （A 卷 共 4 页） （考试时间：2012 年 6 月 19 日） 题号 一 二 三 四 五 六 七 成绩 核分人签字 得分 一、单项选择题（共一、单项选择题（共 12 分，共分，共 5 小题，共小题，共 12 空，每空空，每空 1 分）分） 1、以下各组变长码中， C 是非奇异码，但不是唯一可译码； A 是唯一可 译码，但不是前缀码； D 是前缀码。 x10 x10 x10 x11 x201 x211 x210 x200 x3011 x311 x3100 x3010 x40111 x4100 x4111 x4011 （A） （B） （C） （D） 2、对离散i.i.d.信源X进行熵编码，以下方法中， A 和 B （或 B 和 A ）平均 码长的上界为ElH(X)+1； C 平均码长的上界为ElH(X)+2； A 具有 最优性，即平均码长不大于任何其它唯一可译码的平均码长。 （A）Huffman 编码 （B）Shannon-Fano 码 （C）Shannon-Fano-Elias 码 3、离散无记忆信源X经信道 1 传输后得到Y，Y又经信道 2 传输后得到Z，则比较以下各 量的大小关系有：疑义度H(X|Y) A H(X|Z)，互信息I(X; Y) B I(X; Z)，信 道 1 的信道容量C1 B 信道 1 与信道 2 级联信道容量C1-2。 （A） （B） 4、时间离散连续信源X，通过无记忆平稳加性噪声信道，输出Y=X+Z，噪声Z的概率密 度函数为pz(z)，则该信道的转移概率密度函数pY|X(y|x)= A 或B 。 （A）pz(y-x) （B）pz(z) （C）pz(y)/ pz(x) （D）pz(y)- pz(x) 5、平均功率受限的波形信源，通过带宽有限的 AWGN 信道，当带宽趋于无穷大时，信 道容量趋于 B 。 （A）无穷大 （B）1.44 S/N0 bit/s （C）S/N0 bit/s 二、填空题（共二、填空题（共 22 分，共分，共 7 小题，共小题，共 11 空，每空空，每空 2 分）分） 1、某离散i.i.d.信源X熵为H，进行N次扩展，则扩展信源XN的熵H(XN) = NH ；对扩展信 源XN进行Huffman编码，则原信源X平均码长的上界为El 2 log,1 2 0,1 DD D 1 说明：未分两种情况不能给分。 变形但相等的结果不扣分。 说明：B对的。一个随机变量 X 概率密度函数 p(x)里面的 x 仅仅是一个实值参数，表示 X 在 x 附近取值的可能性。本题随机 变量有关系 Y=X+Z，但它们的概率密度函数的参数之间没有这样的关系。pY|X(y|x)是一个关于 x 和 y 的函数，需要与一个自变量为 x 和 y 的函数相等。但因为教材上有这样的式子，老师又没有强调，所以选 B 本次不扣分。 是不 天津大学试卷专用纸 学院 专业 班 年级 学号 姓名 共 4 页 第 2 页 A 卷 三、画图简答题（共三、画图简答题（共 20 分，共分，共 5 小题，每小题小题，每小题 4 分）分） 1、画出反映熵、联合熵、条件熵和互信息之间的相等和不等关系的韦恩（Venn）图，并 写出该图所能反映的各种相等和不等关系； 2、画出二元离散 i.i.d.信源 X= 的熵 H 与概率 p 的关系曲线 H(p)，标出特征 点坐标； pp1 10 3、画出转移概率矩阵的 2 状态一阶平稳Markov信源的状态转移图，其中 p(s2|s1)=1- 1 1 。 4、画出信道传输矩阵p(y|x)=的信道线图，其中p(y2|x1)=1/3。 4/1 0 04/3 3/13/2 01 3/ 41/ 01 10 5、画出二元离散i.i.d.信源X= 在汉明失真矩阵 下的率失真函数曲线 R(D), 标出特征点坐标。 （注：log23=1.6） 4 解答：1. Venn 图及主要关系如下： . 形状1 分 . 6 个标注.1 分 H(X|Y)H(X) 或 H(Y|X)H(Y) 或 I(X;Y)0 .0.5 分 I(X;Y)=H(X)-H(X|Y)（或 H(Y)- H(Y|X)） .0.5 分 H(X,Y)=H(X)+H(Y|X)（或 H(Y)+H(X|Y)） 或 I(X;Y)=H(X)+H(Y)- H(X,Y) .0.5 分 H(X)（或 H(Y)）H(X,Y) 或 H(X|Y)（或 H(Y|X) ）0 或 I(X;Y)H(X)（或 H(Y)）0.5 分 曲线形状.1 分 范围0,1.1 分 坐标(0.5, 1)1 分 坐标轴标题 p-H(p).1 分 4 条个线及概率 .4 分 6 条线及其标注（含 0 线）.3 分 输入输出.1 分 形状.1 分 D 轴交点 0.25.1 分 R(D)轴交点 0.8 或 H(1/4)或 H(3/4).1 分 坐标轴标题 D-R(D).1 分 天津大学试卷专用纸 学院 专业 班 年级 学号 姓名 共 4 页 第 3 页 A 卷 四、编码题（共四、编码题（共 15 分，共分，共 3 小题，每题小题，每题 5 分）分） 五、问答题（共五、问答题（共 12 分，共分，共 3 小题，每题小题，每题 4 分）分） 1、给出离散 i.i.d.信源 X 的数学表示及其熵 H(X)的定义，并结合香农离散信源无失真编 码定理说明 H(X)的意义； 1、离散 i.i.d.信源 X 的概率分布为，对其进行 Huffman 编码，设编码符 号集为0, 1，求各信源符号对应的码字，以图示说明编码过程； 8/32/18/1 321 xxx 2、 离散无记忆信道的数学表示及其信道容量 C 的定义， 并结合香农信道基本定理说明 C 的意义； 2、信源及编码符号集同上，求各信源符号的Shannon-Fano码的码字，写清编码过程的各 个步骤； （注：log23=1.6） 3、给出离散 i.i.d.信源的信息率-失真函数 R(D)的定义，并结合香农限失真编码定理说明 R(D)函数的意义。 3、信源同上，输出消息序列x2 x3 x1，求该序列的算术编码，以图示说明编码过程，结果 以区间表示，区间端点以分数或小数表示即可，无需二进制表示。 答：1. X的符号集为x1 x2 xn，对应的概率分别为p1 p2 pn，.1 分 解答：1. 图示略，三符号依次编码为 11、0、10 或因 0/1 位置不同得到的其它正确的码。 .5 分 2. pi 1/2 3/8 1/8 .1 分 Fi 0 1/2 7/8 .1 分 li 1 2 3 .1 分 ci 0 10 111 .2 分 （若未正确排序，其它过程对，扣 2 分） 3. 图示略，各步编码区间依次为 32 1 57 0,1) , ), 8 816 8 xxx 1 5759 ),) 16 128 .5 分 （若先排序，得 537 , 128 16) ，因没有掌握 Elias 和算术编码的一个重要特点，扣 1 分。区间端点取正确的小数表示或其近似值不扣分。 按x3 x2 x1分割数轴不扣分，结果为 699 , 128 16 1 n i= pi log pi .1 分 H(X)= - 无失真编码定理说明 H(X)是信源做无失真编码时可能做到的最小平均码长。2 分 2. 离散无记忆信道由信道矩阵p(y|x)表示.1 分 容量C = maxp(x) I(X;Y).1 分 信道基本定理说明 C 是信源消息经信道可靠传输时可能达到的最大信息传输率。 .2 分 3. R(D) = minp(y|x) I(X;Y) .1 分 s.t. DD.1 分 限失真编码定理说明R(D)是信源做有失真编码时，在失真不大于D的限制下， )。 ） 可能做到的最小平均码长。.2 分 天津大学试卷专用纸 学院 专业 班 年级 学号 姓名 共 4 页 第 4 页 A 卷 六、计算题（共六、计算题（共 12 分，共分，共 2 小题，每题小题，每题 6 分）分） 七、计算或证明或编程题（共七、计算或证明或编程题（共 7 分，以下分，以下 3 小题任选其小题任选其 一一 ） =)|(xyp 8 3 4 1 4 1 8 1 8 3 4 1 8 1 4 1 8 1 4 1 8 3 4 1 8 1 4 1 4 1 8 3 1、某离散无记忆信道的传输矩阵如下，判断该信道的类型，计算其信道容量，及取得信 道容量时的信源分布。 12341 3111 8448 3111 4848 3111 4848 3111 8448 (), (), (), () (), ( 234 ), (), () 1/10,2/5,21/5,3/10,1/ 4,1/ 4 (| ) 0,1/ p yp yp yp yp xp xp xp xp y x= = 2 1()x + = 2 2 2 22 2 ()( )log ( )d ( )lnd( )dnat 2 2 11 ln(2)nat 22 11 ln(2 e)nat(log (2 e)bit) 22 h Xp xp xx p xxp xx + + = + =+ = 2、 离散i.i.d.信源X= 2 1 0 5 432 aaa 2 2 10 1 1 a ， 通过上述信道传输后输出Y， 求互信息I(X;Y)。 1、 计算均值为0、方差为的正态分布连续随机变量的微分熵。 1、 证明平均功率有限的连续信源的最大熵定理，说明取得最大熵的条件。 1”、写出使用Arimoto-Blahut算法进行信道容量计算的一般步骤。 （注：log23=1.6，log25=2.3）. 解答：1. 弱对称信道。 （行重排列和相等的信道，因没有掌握信道名称扣1分）.2分 C = log|Y|-H(r) =2-H(3/8,1/4,1/4,1/8)=2-1.9=0.1 bit/symbol （或其它正确的近似结果）.3分 当信源均匀（或等概率）分布时取得信道容量，即p(xi)=1/4, i=1,2,3,4。 （使互信息达到信道容量的输入可能不唯一，本题能够使Y均匀分布的X的 分布均可。 ）.1分 2. 输出分布 .2分 H(Y)=1.97 bits/symbol （或其它正确的近似结果）.1分 H(Y|X)=H(r)=1.9 bits/symbol .2分 I(X;Y)=H(Y)-H(Y|X)=0.07 bit/symbol （或其它正确的近似结果）.1分 （本小题也可使用互信息公式直接计算） 解答：1. 2 2 2 () 2 1 ( ) 2 e x p x =.1分 .1分 .3分 （其中=0，可不写）.1分 单位.1分 1. 由Gibbs不等式，对X的两个分布p(x)和q(x)有 p( )log ( )d( )log ( )dxp xxp xq x + x .2分 令 2 2 () 2 x 2 1 ( ) 2 eq x =，可求得 2 2 1 ( )log ( )dlog (2 e) 2 p xq xx + = .2分 故对任意分布p(x)， 2 2 1 ()log (2 e 2 h X) 即X有最大熵 2 2 1 log (2 e) 2 .1分 当X为高斯分布，即p(x)=q(x)以概率1成立时取得最大熵。2分 天津大学试卷专用纸 学院 专业 班 年级 学号 姓名 共 4 页 第 5 页 A 卷 1. A-B算法的一般步骤是: 1) i=0, 初始化) ( )(i px为均匀分布；.1分 2) 计算 ( ) ( ) ( ) (| ) ( ) (| i i i x ( ) ( | ) ) px p y x x y px p y x = ；.1分 3) 计算 ( ) ( ) ( | ) (| )log ( ) i i x ( )( ) (; )( ) ii xy y p y xIX Ypx px (1)( ; )|IX Y =；.1分 4) 若 ( ) |(; ) ii IX Y ( )( ; i X Y ( )( )i ，.1分 5) 则)；.1分 CI= p6) 且取得信道容量的输入分布