我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:天空彩票 > 端点编码 >

信息论与编码理论-习题答案_姜楠_王健_编著_清华大学doc

归档日期:05-29       文本归类:端点编码      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  第1章 绪论 信源、编码器、信道、干扰、译码器、信宿 香农 通信系统模型 信号是消息的表现形式,是物理的,比如电信号、光信号等。消息是信息的载荷者,是信号的具体内容,不是物理的,但是又比较具体,例如语言、文字、符号、图片等。信息包含在消息中,是通信系统中被传送的对象,消息被人的大脑所理解就形成了信息。 略 第2章 信息的统计度量 少 y的出现有助于肯定x的出现、y的出现有助于否定x的出现、x和y相互独立 FTTTF 2.12比特 依题意,题中的过程可分为两步,一是取出一枚硬币恰好是重量不同的那一枚,设其发生的概率为,由于每枚硬币被取出的概率是相同的,所以 所需要的信息量 二是确定它比其他硬币是重还是轻,设其发生的概率为,则 总的概率 所需要的信息量 设表示“大学生”这一事件,表示“身高1.60m以上”这一事件,则 故 四进制波形所含的信息量为,八进制波形所含信息量为,故四进制波形所含信息量为二进制的2倍,八进制波形所含信息量为二进制的3倍。 故以3为底的信息单位是比特的1.585倍。 (1)J、Z(2)E(3)X (1)两粒骰子向上面的小圆点数之和为3时有(1, 2)和(2, 1)两种可能性,总的组合数为,则圆点数之和为3出现的概率为 故包含的信息量为 (2)小圆点数之和为7的情况有(1, 6), (6, 1), (2, 5), (5, 2), (3, 4), (4, 3),则圆点数之和为7出现的概率为 故包含的信息量为 对于男性,是红绿色盲的概率记作,不是红绿色盲的概率记作,这两种情况各含的信息量为 平均每个回答中含有的信息量为 对于女性,是红绿色盲的概率记作,不是红绿色盲的概率记作,则平均每个回答中含有的信息量为 所以 天平有3种状态,即平衡,左重,左轻,所以每称一次消除的不确定性为,12个球中的不等重球(可较轻,也可较重)的不确定性为:,因为,所以3次测量可以找出该球。 (1)当最后3场比赛麦克胜的次数比大卫多时,麦克最终才能胜,因此 同理 麦克最终比赛结果的熵为 因为胜、负、平这3种结果接近等概,所以该随机变量的熵接近最大熵。 (2)假定大卫最后3场比赛全部获胜,那么麦克也必须全部获胜最后3场比赛最终才能得平,否则就是负。麦克3场比赛全部获胜的可能性是,因此在假定大卫最后3场比赛全部获胜的情况下麦克的最终比赛结果的条件熵是 (1)假定一个家庭里有个女孩,1个男孩,相应的概率是,因此女孩的平均数是,女孩的平均数和男孩的平均数相等。 (2) (1)根据题意,可以得到: ① ② 由式②可以得到: ③ 将式③代入式②得到: ④ 由于的取值必须在0到1之间,由式③和式④可以得到的取值范围在0.9到0.95之间。 (2)就业情况的熵为 它在的取值范围内的曲线)当时,达到最大值,这时,。 假设表示当地的实际天气情况,表示气象台预报的天气情况,表示总是预报不下雨的天气情况。 ,可见气象台预报的确实不好。 但是如果总是预报不下雨的话则会更糟,因为和是相互独立的两个随机变量,即,所以 因此气象台的预报准确率虽然比总是预报不下雨低,但还是传递了一些信息,消除了一些不确定性。 由互信息量的定义 因为,则有 同理,因为,则有 (1)根据熵的极值性,当随机变量等概分布时,随机变量的熵最大。有7个可能取值的随机变量的最大熵为,随机变量不是等概分布,所以。 (2)根据熵的递增性,。 (3) (4)因为随机变量是的函数,所以 假定为最大的概率。根据熵函数的性质,如果,则熵小于2;如果,则只有一种可能:。如果,则有无数个解,其中之一为;如果,则没有解。 第3章 离散信源 p(x2) 5 1 2 (1)87.81bit (2)1.95bit Hmax(X)=1 (1)消息符合的平均熵 (2)自信息量为 (3)(2)中的熵为 因为边沿分布 条件分布概率如下: 0 1 2 0 9/11 1/8 0 1 2/11 3/4 2/9 2 0 1/8 7/9 所以信息熵: 条件熵: 联合熵: 或 可知 解释: (1)信源的条件熵比信源熵少这是由符号之间的相互依存性造成的。 (2)联合熵表示平均每两个信源符号所携带的信息量。平均每一个信源符号所携带的信息量近似为 因此 原因:略去了和之间的依赖性。 由定义,信源的熵 信源的概率分布要求满足,而此题中。即各种可能发生的情况下,概率之和大于“1”。在实际情况下这是不可能发生的。 由题意可知,联合概率分布为 X Y1 0 1 0 1/4 0 1 0 1/4 2 1/4 1/4 X Y2 0 1 0 1/4 0 1 1/4 0 2 0 1/2 Y的分布为 Y1 0 1 P(y1) 1/2 1/2 Y2 0 1 P(y2) 1/2 1/2 所以 由于 所以,第二个实验好。 由定义 由于一阶马尔科夫信源之间的相关性,导致熵减小。 (1)一阶马尔可夫过程的状态转移图如图所示。 一阶马尔可夫过程共有3种状态,每个状态转移到其他状态的概率均为,设状态的平稳分布为,根据 可得,3种状态等概率分布。 一阶马尔可夫信源熵为 信源剩余度为 (2)二阶马尔可夫信源有9种状态(状态转移图略),同样列方程组求得状态的平稳分布为 二阶马尔可夫信源熵为 信源剩余度为 由于在上述两种情况下,3个符号均为等概率分布,所以信源剩余度都等于0。 (1)由题中条件,该信源是离散无记忆信源,对任意和, 其中为中0的个数。 故该信源是平稳的。 (2)由离散无记忆信源的扩展信源的性质 (3) 可能发出的符号有0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111。 状态转移矩阵 故该马尔科夫信源是遍历的。 设 由 即 求得 所以信源熵为 状态转移图略。 (1)状态转移矩阵 则有 可得 整理得 (2)信源的熵 其中状态极限概率 整理得 所以,此信源的熵 (3)信源无记忆,符号的概率分布等于平稳分布。 所以 经比较,可得到。 (4)一阶马尔科夫信源的极值 当且仅当时成立。 当时,; 当时, (1)状态转移矩阵 由 解得 整理得,平稳后信源的概率分布 (2)求信源熵。先求状态极限概率 又因为 可得 信源的熵 (3)求或时的 时 时,即 信源熵表示的是信源的平均不确定性。此题中和表明某一状态转化到另一状态的情况一定发生或一定不发生,即是确定事件,平均不确定性为零,即信源的熵为零。 可知消息的极大熵,此信源的极限熵为 由冗余度计算公式得 (1)由一步转移概率矩阵与二步转移概率矩阵的公式得 (2)设平稳状态,马尔可夫信源性质知,即 求解得稳态后的概率分布 设状态空间S=,符号空间 且 一步转移概率矩阵 状态转移图 设平稳状态,由马尔可夫信源性质有 即 可得 马尔可夫链只与前一个符号有关,则有 消息元的联合概率是 求得一阶马尔可夫信源的不确定性为 组成的字如下: 这种简单语言平均每个码字的长度为 则平均每个字符携带的信息量为 所以,其冗余度为 掷次钱币就使其正面向上的概率为 则有 第4章 离散信道 (1) (2) (3) (4) 假设输入符号取值;输出符号。且。其中,表示单个符号的无差错传输概率,表示单个符号传输的错误概率。信道转移关系如图所示。 则传递概率为 并且 则信道传递矩阵为 信道如图所示 其转移矩阵为这是一个准对称信道,信道容量为 比特/符号 按定理 解释: (1)此信道每个符号平均能够传输的最大信息为0.0817bit。 (2)只有当信道输入符号是等概率分布才能达到这个最大值。 信道传递矩阵为 又知 所以有 故平均互信息量 (1)三元对称理想(无噪声)信道的信道模型如图所示。 (2)三元对称强噪声信道模型如图所示。 由图可知信道1、2的信道矩阵分别为 它们串联后构成一个马尔科夫链,根据马氏链的性质,串联后总的信道矩阵为 传递矩阵为 输入信源符号的概率分布可以写成行向量形式,即 由信道传递矩阵和输入信源符号概率向量,求得输出符号概率分布为 输入符号和输出符号的联合概率分布为 (1) (2) (3)信源和信源的信息熵 (4)信道疑义度 (貌似不对) 噪声熵 (和上者相调) (5)平均互信息 根据公式求互信息量, 而 故应求 。 (1)求联合概率 (2)求边沿概率 (3)求后验概率 (4)求熵 信道传输矩阵如下: 可以看出这是一个对称信道,,那么信道容量为 先求输入端须传输的信息量 再求输出端内传出的信息量。要求信道传出的信息量,必须先求信道容量。由 知 所以 信道容量为,对信道而言内共传输的符号数为15000个。所以输出端传出的信息量为,显然内传出端无法得到输入序列的全部信息。 (1)信道为准对称信道,输入等概率分布时达到信道容量,即。 设输入为 计算输出得 所以 (2)信道仍为准对称信道,输入等概率分布时达到信道容量,即。 设输入为 计算输出得 所以 比较两信道容量,得 依题意,阻值的概率空间为 功率的概率空间 由题意知再设则 由,得 又 所以 通过测阻值可以得到关于瓦数的平均信息量为0.187bit。 (1),由信道传输矩阵与信道的传输符号的概率分布得到信道输入与输出的联合分布矩阵为 有边缘概率 输出符号熵为 条件熵为 (2) 显然。 (1)由信道1的转移概率矩阵可知其为对称信道 所以 因为 所以有信息熵损失,信道有噪声。 (2)由信道2的转移概率矩阵可知其为准对称信道,输入为等概分布时达到信道容量。令此时的输出分布为 所以 因为 所以信道2无噪声。 因为是二元对称信道,根据信源概率分布:, 信道传输概率: 得到输出符号概率分布 根据互信息量的定义,有 (1)这是一个错误传递概率为0.08的二元对称信道,它的信道容量为 (2)每次顾客点菜时提供的信息为 (3)由于需要传递的信息量小于信道容量,因此在这个信道上可以正确传递顾客点菜的信息。 第5章 连续信源和连续信道 略 略 略 第6章 无失线)唯一可译码有:,,。 (2)即时码有:, (3) 同理得 1. (1)此码的码长满足Kraft-McMillan不等式: (2)根据码树图可知,此码是即时码; (3)由于此码是即时码,所以它也是唯一可译码。 2. (1)此码满足Kraft-McMillan不等式: (2)此码不是即时码,因为码字00是码字000的前缀; (3)此码不是唯一可译码,因为码符号序列000000可以译码为00,00,00,也可以译码为000,000。 3. (1)此码满足Kraft-McMillan不等式: (2)根据码树图可知,此码是即时码; (3)由于此码是即时码,所以它也是唯一可译码。 4. (1)此码不满足Kraft-McMillan不等式: (2)因为不满足Kraft-McMillan不等式,所以此码不是即时码; (3)因为不满足Kraft-McMillan不等式,所以此码不是唯一可以码。 5.{01,111,011,00,010,110} (1)此码不满足Kraft-McMillan不等式: (2)此码不是即时码,因为码字01是码字011的前缀; (3)此码是唯一可译码。根据唯一可译码判决准则,我们构造以下的尾随后缀序列: (1) (2) (3)对二重延长消息采用费诺方法编码,结果为 平均码长: 平均信息传输速率 码元0和1的概率分别为 (4)对三重延长消息采用霍夫曼方法编码,结果为 平均码长: 平均信息传输速率 码元0和1的概率分别为 由香农第一定理知 显然当时 此时的信息传输率为 编码后原信源变换成一个新的信源 新信源的信道容量,且在输入信源等概率时达到此容量。 由式知,经过霍夫曼编码后,信心传输率达到信道容量,很难推出此时的信源趋于等概分布,即=。 (1)至少需要二位二进制码元来发送4个等概发生的信息 晴——00,云——01,雨——10,雾——11 (2)4个消息的概率恰好是2的负整数次幂,根据得 晴——2位,云——3位,雨——3位,雾——1位 (3)采用霍夫曼方法得 雾——0,晴——10,云——110,雨——111 它们的平均码长分别为: 第一种情况: 第二种情况: (1)采用霍夫曼编码方法得到最佳二元码为 平均码长: 编码效率 (2)仍采用霍夫曼编码方法求得最佳三元码 平均码长: 编码效率 (1)采用霍夫曼方法进行编码,得 平均码长: 信源熵为 编码效率 (2) 霍夫曼编码后 平均码长: 信源熵为 编码效率 (3)同理可得的最佳二元码,计算平均码长和编码效率。具体步骤略。 霍夫曼编码的结果为: 平均码长: 信源熵为 平均信息传输速率 (1){0,10,11}是概率分布{1/2,1/4,1/4}的Huffman编码。 (2){00,01,10,110}可以被改进为{00,01,10,11}而不丧失其即时可译性,因此原码不是最佳码,因此也就不是一个Huffman编码。 另外,此码中最长的码长只有一个码字,这也和Huffman编码的特性不符。 (3){01,10}可以被改进为{0,1}而不丧失其即使可译性,因此原码不是最佳码,也就不是一个Huffman编码。 4位 (1)不存在 (2)存在{0,1,20,21,220,221,222} (3)不存在 对灰度{0,4,5,6,7}编码为{10,0,2,11,12}, 码{0,010}是唯一可译码,但是它既不满足前缀条件也不满足后缀条件。换句话说,在这个码中,某些码字是另外一些码字的前缀,并且某些码字是另外一些码字的后缀。 (1)我们将品尝次数看作码字的码长,由于只能依次品尝每一瓶酒,所以对于这个题目而言码长只能是1,2,3,4,4这样的分布,所需的平均品尝次数就是平均码长,想要使得平均码长最小,则应该将较短的码长安排给概率较大的符号,因此所需的最小平均品尝次数为 (2)应该首先品尝概率为1/3的那瓶酒。 (3)这个问题可以转化为求取此概率分布的Huffman编码,如图所示 品尝时首先将第一比特为0的酒混合起来品尝,分出好坏后再按照第二比特来混合,直到找到坏酒,因此品尝的平均次数为 (4)根据上述编码,首先应该品尝第一和第二瓶酒的混合,或者第三,四,五瓶酒的混合。由于Huffman编码不是唯一的,所以还存在另外的方案,其对应的编码如下: 概率 1/3 1/4 1/6 1/6 1/12 码字 00 10 11 010 011 在这种方案的指导下,首先应该品尝第一、四、五瓶酒的混合。 序列S F(S) p(S) 码长 码字 计算过程 ( 0 1 --- --- --- b 0.3 0.7 --- --- F((b)=F(()+p(()F(b)=0+1*0.3=0.3 bb 0.51 0.49 --- --- p(bb)=p(b)p(b)=0.7*0.7=0.49 bba 0.51 0.147 --- --- F(bba)=F(bb)+p(bb)F(a)=0.51+0.49*0=0.51 bbaa 0.51 0.0441 5 10001 F(bbaa)=F(bba)+p(bba)F(a)=0.51+0.147*0=0.51 p(bbaa)=p(bba)p(a)=0.147*0.3=0.0441 (0.51)10=(0.100000)2 因此码字为10001 第7章 限失真信源编码 ( 大于 相关性 (1)在题设失真度定义下,失真矩阵是一个方阵,并有 是阶矩阵。 (2)以二进制信源为例 信源符号集 接收符号集 其失真矩阵为 在这种情况下,意味着若把信源信号再现为删除信号时,其失真程度要比再现为其他接收符号的失真程度少一半。 以二进制删除信源为例,,此时 , 则失线个信源符号。 此信源的熵 信源输出的信息传输速率 将此信源输出符号送入二元无噪无损信道中进行传输,此信道每秒钟只传送两个二元符号。此信道的最大信息传输速率 因为 根据有噪信道编码定理(香农第二定理),不论进行任何编码此信源都不可能在此信道中实现无错误地传输,所以信源在此信道中传输会引起错误和失线)若此信源的失真度为汉明失真。因为是二元信源,输入是等概分布,则该信源的信息率失真函数 若当 则此信源在此信道中传输时不会引起错误,也就是不会因信道而增加信源新的失真。总的信源的失真是信源压缩编码所造成的允许失真。 所以有 故 所以,允许信源平均失真时,此信源就可以在此信道中传输。 由已知条件可以求得 (1)达到的信道为 (2)达到的信道为 根据最大失真度的定义,有 而最小平均失真 达到的信道为 达到的信道为 因为有失真,所以不为零。 根据率失真函数的定义域,可以得到 由和可以定出曲线的两个端点。再根据在其定义域内非负、下凸和严格递减,可以得到曲线图如图和图所示。因为的物理意义为满足失真度不大于的最小信息速率,而信息速率一定是非负的,所以整个曲线非负。 允许的失真门限越大,信息速率就可以降得越低,所以曲线)为了使得失线,必须有,即,所以有。 (2)平均失真为 如果失真是有限的,则并且。如果信息率为0,则与统计独立,即。因此,使得信息率为0的平均失线] 010110100 根据极大似然译码规则选择译码函数 又设输入符号为等概率分布 则有 若按下述译码函数计算平均错误概率 得 用极大似然译码规则译码,先写出输入输出的联合概率分布 平均译码错误概率为 (1)信道输入有4个序列,因此 编码后信息传递率为 (2)信道矩阵如下: 因此联合概率分布为 所以有。 (1)根据离散对称信道的性质,其信道容量为 (2)用简单的二次重复码发送符号,按最大似然译码规则设计译码器,译码器输出端的平均错误概率为: ,1101001 0110001 1010011 (1)Hamming(7,4)较验矩阵为 由此可得其伴随式为 由Hamming(7,4)码的伴随式和翻转比特之间的关系如表所示: 伴随式 000 001 010 011 100 101 110 111 翻转的比特 - 由此可知翻转比特是第四个所以正确的接收矢量应该是1100011,译码结果应1100。 (2)根据上面的推理同样可以得到0110110的译码应该是0100。 (3)0100111的译码结果是0100。 (4)1111111的译码结果是1111。 首先构造一个码长为14的线性分组码,并假设采用伴随式译码。 对于N=14个发送比特来说最多两个比特的错误模式有 由于采用伴随码译码,所以每个不同的错误模式必须指定一个不同的伴随式,而对于(14,8)码来说,伴随式是长度为的矢量,共有个因为64 106,所以可以得到结论:不存在能够纠正两个比特错误的(14,8)码。 (1)Hamming码的校验矩阵有行和列。构造方法是将由个码符号组成的非零列矢量按照二进制数由小到大的顺序从左到右依次排列 = (2)由上一问可知生成矩阵为 (3)译码规则为:当接收序列与有效码字之间的距离时将译码为。 (4)译码错误概率为 共有15个这样的噪声矢量,每个噪声矢量与一个非零码字对应。 线性分组码的一致校验矩阵是一个的矩阵,一个码符号序列是码字当且仅当: 由书籍条件可知: 所以有 即两者的伴随式相同。 接收码字的码多项式为 所以接收码字存在错误。 (1)因为所以可以得到两个生成多项式, 我们选择为生成多项式,其生成矩阵为 (2)所有码字为:(000000)(101010)(010101)(111111)。 (3)最小码距为,所以能纠1个比特的错误。

本文链接:http://diverlandya.com/duandianbianma/459.html