信息论与编码技术+(冯桂+林其伟+陈东华+著)+清华大学出版社+课后答案.pdf

Chap1 思考题与习题 参考答案参考答案 1 1 信息论与编码技术研究的主要内容是什么 信息论是一门应用概率论 随机过程 数理统计和近代代数的方法 来研究广义的信息传输 提取 和处理系统中一般学科 编码技术研究的主要内容是如何既可靠又有效地传输信息 1 2 简述信息理论与编码技术的发展简史 1948 年香农在贝尔系统技术杂志上发表了两篇有关 通信的数学理论 的文章 在这两篇论文中 他用概率论测度和数理统计的方法系统地讨论了通信的基本问题 得出了及格重要而带有普遍意义的结 论 并由此奠定了现代信息论的基础 从 1948 年开始 信息论的出现引起了一些有名的数学家如柯尔洛夫 A Feinstein J Wolfowitz 等 人的兴趣 他们将香农已得到的数学结论做了进一步的严格论证和推广 使这一理论具有更为坚实的数 学基础 在研究香农信源编码定理的同时 另外一部分科学家从事寻找最佳编码 纠错码 的研究工作 并 形成一门独立的分支 纠错码理论 1959 年香农发表了 保真度准则下的离散信源编码定理 首先提出了率失真函数及率失真信源 编码定理 从此 发展成为信息率失真编码理论 香农 1961 年的论文 双路通信信道 开拓了网络信息论的研究 现在 信息理论不仅在通信 计算机以及自动控制等电子学领域中得到直接的应用 而且还广泛地 渗透到生物学 医学 生理学 语言学 社会学 和经济学等领域 1 3 简述信息与消息 信号的定义以及三者之间的关系 信息就是事物运动的状态和方式 就是关于事物运动的千差万别的状态和方式的知识 用文字 符号 数据 语言 音符 图像等能够被人们感觉器官所感知的形式 把客观物质运动和 主观思维活动的状态表达出来成为消息 把消息变换成适合信道传输的物理量 这种物理量称为信号 它们之间的关系是 消息中包含信息 是信息的载体 信号携带消息 是消息的运载工具 1 4 简述一个通信系统包括的各主要功能模块及其作用 通信系统主要分成下列五个部分 1 信息源 信源是产生消息和消息序列的源 2 编码器 编码是把消息变换成信号的措施 3 信道 信道是指通信系统把载荷消息的信号从甲地传到乙地的媒介 4 译码器 译码就是把信道输出的编码信号 已叠加了干扰 进行反变换 5 信宿 信宿是消息传送的对象 即接收消息的人或机器 1 5 你有没有接触与考虑过信息与信息的测度问题 你如何理解这些问题 略 1 6 什么是事物的不确定性 不确定性如何与信息的测度发生关系 由于主 客观事物运动状态或存在状态是千变万化的 不规则的 随机的 所以在通信以前 收信 者存在 疑义 和 不知 即不确定性 用数学的语言来讲 不确定就是随机性 具有不确定性的事件就是随机事件 因此 可运用研究随 机事件的数学工具 概率论和随机过程来测度不确定性的大小 1 7 试从你的实际生活中列举出三种不同类型的通信系统模型 并说明它们的信源 信道结构 写出 它们的消息字母表 输入与输出字母表及它们的概率分布与条件概率分布 略 1 8 在你日常生活中出现过哪些编码问题 能否用编码函数给以描述 略 Chap2 思考题与习题 参考答案 2 1 同时扔一对均匀的骰子 当得知 两骰子面朝上点数之和为 2 或 两骰子面朝上点数之和为 8 或 两 骰子面朝上点数是 3 和 4 时 试问这三种情况分别获得多少信息量 解解 同时扔一对均匀的骰子 可能呈现的状态数有 36 种 各面呈现的概率为 1 6 所以 36 种中任何一 种状态出现的概率都是相等 为 1 36 1 设 两骰子面朝上点数之和为 2 为事件 A 在 36 种情况中 只有一种情况 即 1 1 则 2 1 36 log log 365 17 P A I AP A 比特 2 设 两骰子面朝上点数之和为 8 为事件 B 在 36 种情况中 有六种情况 即 5 3 3 5 2 6 6 2 4 4 则 2 5 36 36 log log2 85 5 P B I BP B 比特 3 设 两骰子面朝上点数是 3 和 4 为事件 C 在 36 种情况中 有两种情况 即 3 4 和 4 3 则 2 2 36 log log 184 17 P C I CP C 比特 2 2 同时掷两个均匀的骰子 也就是各面呈现的概率都是 1 6 求 1 事件 3 和 5 同时出现 的自信息量 2 事件 两个 l 同时出现 的自信息量 3 两个点数之和 即 2 3 12 构成的子集 的熵 4 事件 两个骰子点数中至少有一个是 1 的自信息量 解解 同时掷两个均匀的骰子 也就是各面呈现的概率都是 1 6 总共有 36 种可能的状态 每 种状态出现的概率都是 1 36 1 设 3 和 5 同时出现 为事件 A 则在 36 种状态中 有两种可能的情况 即 5 3 和 3 5 则 2 2 36 log log 184 17 P A I AP A 比特 2 设 两个 l 同时出现 为事件 B 则在 36 种状态中 只有一种可能情况 即 1 1 则 2 1 36 log log 365 17 P B I BP B 比特 3 设两个点数之和构成信源 Z 它是由两个骰子的点数之和组合 即 Z Y X 得 23456789101112 1 362 363 364 365 366 365 364 363 362 361 36 1 Z P z P z 22222 222 log 468106 log 36 log 2log 3log 4log 5log 6 3636363636 261210 log 36 log 3log 5 363636 5 17 1 8963 274 Z H ZP zP z 比特 2 4 在这 36 种状态中 至少有一个是 1 的状态共有 11 种 每种状态都是独立出现的 每种状态初点 的概率都是 1 36 设 两个点数中至少有一个是 1 为事件 C 则 2 11 36 11 log log1 71 36 P C I CP C 比特 2 3 设离散无记忆信源 1234 012 3 81 41 41 8 Xaaaa p x 3 其发出的消息为 202 120 130 213 001 203 210 110 321 010 021 032 011 223 210 求 1 此消息的自信息是多少 2 在此消息中平均每个符号携带的信息量是多少 解解 1 因为离散信源是无记忆的 所以它发出的消息序列中各个符号是无依赖的 统计独立的 因 此 此消息的自信息就等于各个符号的自信息之和 则可得 112 222 332 442 33 0 log loglog1 45 88 1 1 log loglog 4 2 4 1 2 log loglog 4 2 4 1 3 log loglog 8 3 8 I aP a I aP a I aP a I aP a 比特 比特 比特 比特 此消息中共有 14 个符号 0 13 个符号 1 12 个符号 2 和 6 个符号 3 则此消息的自 信息是 123 14 0 13 1 12 2 6 3 14 1 415 13 2 12 26 3 87 71 II aI aI aI a 比特 4 2 此消息中共有 45 个信源符号 携带了 87 81 比特信息量 因此 此消息中平均每个符号携带的信 息量为 2 87 81 451 95 I 比特 2 4 有一个二元信源 计算该信源的熵 01 0 90 1 X p x 解 解 根据公式得该信源的熵为 22 0 log 0 1 log 1 0 9 log 0 90 1 log 0 1 0 4689 H XP xP xP xP x 比特 符号 2 5 设信源 123456 0 20 190 180 170 160 17 Xaaaaaa p x 求该信源的熵 并解释为什么在本题中 H X log6 不满足信源熵的极值性 解解 根据公式得信源熵为 log log 0 2log0 20 19log0 190 18log0 18 0 17log0 170 16log0 160 17log0 17 2 65 x ii i H XP xP x PP 比特 符号 由离散信源熵的特性可知 其有一个最大值 等概分布时达到最大值 最大值为 log q log 6 2 58 比特 符号 现在 H X log 6 不满足信源熵的极值性 这是因为 我们讨论的信源的 概率空间应该是一个完备集 即 6 1 1 i i P 而在本题当中 6 1 1 071 i i P 不是完备集 所以不满足 信源熵的极值性 2 6 每帧电视图像可以认为是由 3 10 5 个像素组成 每个像素均是独立变化 若每个像素可取 128 个 不同的亮度电平 并设亮度电平等概率出现 问每帧图像含有多少信息量 若有一广播员在约 10000 个汉字的字汇中选 1000 个字来口述此电视 图像 试问广播员描述此图像所广播的信息量是多少 假设汉字字汇是等概率分布 并彼此无依赖 若 要恰当地描述此图像 广播员在口述中至少需用多少汉字 解解 1 亮度电平等概出现 即每个像素亮度信源为 128 12128 1 1 1 1281 128 1 128 i i i Xaaa P a P a 则每个像素亮度含有的信息量为 2 log 1287 H X 比特 符号 一帧图像每个像素均是独立变化的 则每帧图像信源就是离散亮度信源的无记忆 N 次扩展信 源 得到每帧图像含有的信息量为 56 3 10 2 1 10 N H XNH XH X 比特 每帧 2 同 1 中 汉字字汇信源为 10000 1210000 1 1 1 100001 10000 1 10000 i i i Xbbb P b P b 则每个汉字含有的信息量为 2 log 1000013 29 H Y 比特 字 广播员口述电视图像是从此汉字字汇信源中独立的选取 1000 个字来描述的 所以广播员描述此帧 图像所广播的信息量为 44 2 1000log 101 329 10 N H YNH Y 比特 千字 3 若广播员仍从此汉字字汇信源 Y 中独立选取汉字来描述电视图像 每次口述一次汉字含有的信息 量是 H Y 每帧电视图像含有的信息量是 则广播员口述次图像至少需要使用的汉字数为 N H Y 6 5 2 1 10 1 58 10158000 13 29 N H X H Y 字 2 7 为了传输一个由字母 A B C D 组成的符号集 把每个字母编码成两个二元码脉冲序列 以 00 代表 A 01 代表 B 10 代表 C 11 代表 D 每个二元码脉冲宽度为 5ms 1 不同字母等概率出现时 计算传输的平均信息速率 2 若每个字母出现的概率分别为 1 5 1 4 1 4 3 10 试计算传输的平均信息速率 解解 1 不同字母等概率出现时 符号集的概率空间为 1 41 41 41 4 i XABCD P a 平均每个字母含有的信息量为 2 log 42 H X 比特 符号 现在用两个二元码脉冲代表一个字母 每个二元码脉冲宽度为5ms 则每个字母占用 210tms 一秒内可以传输的字母个数为 1 100 n t 字母 秒 则传输的平均信息率为 200 RnH X 比特 秒 2 字母出现概率不同时 根据题意可以其概率空间为 4 1 1 1 5 1 41 43 10 i i i XABCD P a P a 此时每个字母含有的平均自信息量为 4 1 log 1113 log5log4log4log 54410 1 985 ii i H XP aP a 比特 符号 10 3 同 1 其传输的平均信息速率为 2 1 985 10 RnH X 比特 秒 2 8 试问四进制 八进制脉冲所含的信息量是二进制脉冲的多少倍 解 解 二进制脉冲当中 共可以表示两种不同信息 假设两种不同信息等概分布 则每个二进制脉冲的信 息量为 1 2 1 log log 222 xpI 比特 脉冲 同理 在四进制脉冲当中 共可以表示四种不同信息 假设四种不同信息等概分布 则每个四进制脉冲 含有的信息量为 2 4 1 log log 224 xpI 比特 脉冲 同理 在八进制脉冲当中 共可以表示八种不同信息 假设八种不同信息等概分布 则每个八进制脉冲 含有的信息量为 3 8 1 log log 228 xpI 比特 脉冲 从上可知 四进制脉冲所含的信息量是二进制脉冲的 2 倍 八进制脉冲所含的信息量是二进制脉冲的 3 倍 2 9 国际摩尔斯电码用点和划的序列发送英文字母 划 用持续三个单位的电流脉冲表示 点 用持续一个单位的电流脉冲表示 其中 划 出现的概率是 点 出现概率的 1 3 计算 1 点和划的信息量 2 电码信源的平均信息量 解解 1 根据题意 3 1 划点 xpxp 而 1 划 点 xpxp 完备集 所以 4 1 4 3 划 点 xpxp 点 含有的信息量为 4 3 logp x logI 221 0 415 比特 划 含有的信息量为 2 4 1 log log 222 xpI 比特 2 电码信源的平均信息量为 4 3 log 4 3 4 1 log 4 1 log 22 2 1 2 i ii xpxpXH2 415 比特 符号 2 10 某一无记忆信源的符号集为 0 1 已知 0 1 4 1 3 4 pp 1 求信源的熵 2 由 100 个符号构成的序列 求某一特定的序列 例如有个 0 和100个 1 的自信息 量的表达式 m m 3 计算 2 中的序列的熵 解解 1 信源熵为 2 222 1 1133 log loglog0 811 4444 ii i H Xp xp x 比特 符号 2 2 4 1 log 0 log 0 22 xpxI 比特 415 0 4 3 log 1 log 1 22 xpxI 比特 自信息量表达式为 1 100 0 xImxImI41 5 1 585m 比特 3 因为是无记忆信源 所以序列中 100 个符号相互独立 为 100 次扩展信源 其熵为 100 100 81 1 H XH X 比特 符号序列 2 11 一个随机变量 x 的概率密度函数 p xkx 02xV 试求该信源的相对熵 解解 信源的相对熵也就是信源的差熵 根据其定义式得 2 2 2 0 2 22 2 0 2 log log 2 11 log 022 2 log 2 ln2 R h Xp xp x dx kxkxdx kk ln2 xkxx kdx kx k kkBit 自由度 2 12 给定语音信号样值x的概率密度为 1 2 x p xe x 1 要 66 1046 3 101log 100 1 1log n s P P WC bit s 2 6 6 6 log 1 3 46 10 log 1 5 3 46 10 1 338 101 338 s n P CWbit s P W WHzMH z 3 6 66 log 1 3 46 10 0 5 10log 1 3 46 10 120 s n s n s n P CWbit s P P P P P Chap4 思考题与习题 参考答案参考答案 4 1 设无记忆信源 1 0 1 1 3 1 3 1 3 X p x 接收符号集AY 1 2 1 2 失真矩阵 12 11 21 D 试求 和及达到 时的转移概率矩阵 DmaxDminDmaxDmin 解 max 1122114 min min 3333333 Uv P u d u D 而最小平均失真 3 min 1 1 min 1 1 11 3 iij i Pd uuD max 达到的信道为 D 10011 10 01101 10011 ji P u 或 达到的信道为 minD 10 1010 11 01 10 22 0101 01 ji P u 或 4 2 已知二元信源 0 1 1 X p xpp 以及失真矩阵 01 10 ij d 试求 1 2 3 DminDmaxR D 解 1 min 00 1 0pp D 达到的信道为一个一一对应的无噪信道 所以 R 0 I U V H U H p Dmin 2 最大允许失真度为 max min min 1 U P u d upp D 如果p1 2 1 p maxD 3 因为是二元对称信源 所以 0R DH pH DDp 4 4 设一个四元等概信源 接收符号集为 0123 0 50 50 50 5 X p x 0 1 2 3 Y A 失真矩阵 定义为 求及信源的 0111 1011 1101 1110 D maxmin DD R D函数 并作出率失真函数曲线 取4到5个点 解 最大允许失真度为 max 13 min min 1 1 4 U P u d upp r D 最小允许失真度 min 0 D 因为是四元对称信源 又是等概率分布 所以根据r元离散对称信源可得 3 log4 Dlog3 H D 0D 4 R D 3 0 D 4 为画出其曲线 取 D 0 R D 2 1 D R D 1 2583 8 1 D R D 0 7925 4 1 D R D 0 7952 2 3 D R D 0 2075 5 比特 符号 比特 符号 比特 符号 比特 符号 3 D R D 0 4 比特 符号 比特 符号 得如图所示的R D 曲线图 4 5 某二元信源 其失真矩阵定义为 01 0 50 5 X p x 0 0 a D a 求该信源的 和 max D min D R D函数 解 最大允许失真度为 max 1111 min min 0 1 2222 U a P u d uaa D 2 最小允许失真度 min 0 D 我们引进一个 反向 试验信道 设反向信道的信道矩阵为 1 1 DD P DD 可计算得 11 0 1 22 PP 因为0 0 2 DP1 2 4 6 具有符号集U u0 u1 的二元信源 信源发生概率为 p u0 p p u1 1 p 信道如 下图所示 接收符号集V v 01p 0 v1 转移概率为 00 q v u1 11 1q v uq 发出符号与接收符 号的失真 d u0 v0 d u1 v1 0 d u1 v0 d u0 v1 1 1 计算平均失真D 2 率失真函数 R D 的最大值是什么 当 q 为什么值时可达到该最大值 此时平均失真 D 是多 大 3 率失真函数 R D 的最小值是什么 当 q 为什么值时可达到该最小值 此时平均失真 D 是多 大 4 画出 R D D 的曲线 解 1 1 UV DP ud up q 2 根据题4 5 可知R D 的最大值为H p 此时q 0 平均失真D 0 3 R D 的最大值为0 此时q 1 平均失真D 1 p 4 7 设连续信源X 其概率密度分布为 2 a x a p xe 失真度为 试求此信源的 d x yxy R D函数 解 解 令xy 1 2 1 2 2 s s ss s s d s Dd s e ge e e 求出 s g 的傅立叶变换 2 22 2 2 3 4 jw s s wd Q wP wP w s g Ge sw w s 得 求式 4 的傅立叶反变换 又根据式 2 得 2 3 2 5 6 22 a xa x p yp xyxy a p yee p D a D 所以 2 1 loglog 2 2 L s R DDh uh ae g R eD 当 5 式大于零时 2 1 loglog 2 2 R Dae eD 4 8 利用 R D的性质 画出一般 R D的曲线并说明其物理意义 试问为什么 R D是非负且非增 的 解 物理意义 D是允许的失真度 R D 是对应于D的一个确定信息传输率 对于不同的允许失真D R D 就不同 R D 的非负性 根据 R D 的定义知 R D 是在一定的约束条件下 平均互信息 I U V 的极小值 已知 I U V 是非负的 其下限值为零 由此可得 R D 也是非负的 它的下限值也为零 R D 的非增性也是容易理解的 因为允许的失真度越大 所要求的信息率可以越小 根据 R D 的 定义 它是在平均失真度小于或等于允许失真度 D 的所有信道集合 BD 中 去 I U V 的最小值 当允 许失真度 D 扩大 那么 BD 的集合也扩大 当然仍包含原来满足条件的所有信道 这时再扩大的 BD 集 合中找 I U V 的最小值 显然是或者最小值不变 或者变小 所以 R D 是非增的 4 9 设有矢量信源 其各分量 XN kk 0 2 kK 12 是K个独立的随机变量 失真 试证 在此条件下 K k kkKK xxxxxxxxd 1 2 2121 R D D k k k K log 1 2 2 1 其中 Dk k kk 当 当 2 22 满足 DD k k K 1 证明 min m m R DI X X 1 11 11 1 1 2 1 1 max log 0 1 2 mm mmm mm a m iii ii mm b m ii ii m i i m c i i md i i Ihh hh hh i I i R D XXX XX xx xx x xx x x D 其中 2 i E i X D X 上式推导中 a 熵计算的链法则 b 条件减少使熵增大 c 率失 真函数定义 d 高斯变量的率失真函数 式中有两个不等号 其中 b 1 m m iii i qq x xx x 当时 等号成立 c 当每个时 等号成立 2 0 ii i N DX 所以式 1 的等号是可以达到的 进一步对于各分量分配失真量使速率进一步减小 即求 1 2 1 1 minmax log 0 2 m i i m i i D R D D D 利用拉格朗日乘子寻找最佳失真分配方案 为此构成目标函数 2 11 1 log 2 mm i i ii J D D D 对微分且令之为零 得 iD 1 1 0 2 i i J D D m D D 或 这表示当失真分配给各分量时 最佳分配方案是每个分量等失真 但这仅当 2 min i i D m 时 才可行 当某个分量的 2 i 小于 D m 时就不行了 必须利用 K T 条件来解 即选 使 2 2 0 1 1 2 0 ii i ii J D D D D 所以 R D D k k k K log 1 2 2 1 其中 Dk k kk Ct 根据信道编码定理 不论进行任何编码此信源不可能在此信道中实现无错误地传输 所以信源在此 信道中传输会引起错误和失真 2 若设此信源的失真度为汉明失真 因为是二元信源 输入是等概率分布 所以信源的信息率 失真函数 R D 1 H D 比特 信源符号 Rt D 2 66 R D 比特 秒 若当 Ct Rt D 则此信源在此信道中传输时不会引起错误 也就是不会因信道而增加信源新的失真 总的信源的失 真是信源压缩编码所造成的允许失真 D 所以有 2 2 66 1 H D 2 66H D 0 66 H D 0 2481 故 D 0 0415 允许信源平均失真 D0 0415 时 此信源就可以在此信道中传输 Chap5 思考题与习题 参考答案 5 1 将下表所列的信源进行六种不同的二进制编码 试问 消息 概率 C1C2C3C4C5C6 a1 a2 a3 a4 a5 a6 1 2 1 4 1 16 1 16 1 16 1 16 000 001 010 011 100 101 0 01 011 0111 01111 011111 0 10 110 1110 11110 111110 0 10 1101 1100 1001 1111 1 000 001 010 110 110 01 001 100 101 110 111 1 这些码中哪些是唯一可译码 2 哪些码是非延长码 即时码 3 对所有唯一可译码求出其平均码长和编码效率 解 解 1 C1 C2 C3 C6是唯一可译码 2 C1 C3 C6是非延长码 即时码 3 唯一可译码平均码长为 1 q ii i Lp s l 所以 1 3cL 码符号 信源符号 2 2 125cL 码符号 信源符号 3 2 125cL 码符号 信源符号 5 2cL 码符号 信源符号 1 0 667 c H S L 2 0 94 c 3 0 94 c 6 0 8 c 5 2 下面的码是否是即时码 是否是惟一可译码 1 2 1111 1110 1101 1100 10 0 C 1101 1011 1110 110 10 0 C 解 解 1 是即时码 唯一可译码 2 不是即时码 也不是唯一可译码 5 3 判断是否存在满足下列要求的即时码 如果有 试构造出一个这样的码 1 r 2 长度 1 3 3 3 4 4 2 r 3 长度 1 l 2 2 3 3 3 3 r 5 长度 1 1 1 1 l 8 9 4 r 5 长度 1 l 1 1 2 2 2 3 3 4 解 解 1 满足 构造的码字 1 011 010 001 0000 0001 2 满足 构造的码字 0 1 20 21 220 221 222 3 不满足 4 满足 构造的码字 0 1 2 3 40 41 42 440 441 4440 5 4 已知信源的各个消息分别为字母 A B C D 现用二进制码元对消息字母作信源编码 A 00 xy B 01 xy C 10 x y D 11 x y每个二进制码元的传输时间为 5ms 计算 1 若各个字母以等概率出现 计算在无扰离散信道上的平均信息传输速率 2 若各个字母的出现概率分别为 P A 1 5 P B 1 4 P C 1 4 P D 3 10 再计算在无扰离散 信道上的平均信息传输速率 3 若字母消息改用四进制码元作信源编码 码元幅度分别为 0V 1V 2V 3V 码元的传输时 间为 10ms 重新计算 1 和 2 两种情况下的平均信息传输速率 解 1 P A P B P C P D 1 4 H X 4 1 4 log4 2 比特 信源符号 L 4 1 4 2 2 码符号 信源符号 Rt H X t L 2 2 5 10 2 20 比特 秒 2 H X 1 5 log 1 5 1 4 log 1 4 1 4 log 1 4 3 10 log 3 10 1 9855 比特 信源符 号 L 2 1 5 2 1 4 2 1 4 2 3 10 2 码符号 信源符号 Rt H X t L 1 9855 2 5 10 2 19 855 比特 秒 3 a P A P B P C P D 1 4 H X 4 1 4 log4 4 1 比特 信源符号 L 4 1 4 1 1 码符号 信源符号 Rt H X t L 1 1 10 10 2 10 比特 秒 5 5 若消息符号 对应概率分布和二进制编码如下 消 息 符 号 a0a1a2a3 i p 1 2 1 4 1 8 1 8 编码 0 10 110111 试求 1 消息符号熵 2 各个消息符号所需的平均二进制码个数 3 若各个消息符号之间相互独立 求编码后对应的二进制码序列中出现 0 和 1 的无条件概率 0 p 和 1 p 以及码序列中的一个二进制码的熵 并求相邻码间的条件概率 11 p 01 p 10 p 0 0 p 解 1 H X 1 2 log 1 2 1 4 log 1 4 1 8 log 1 8 1 8 log 1 8 1 75 比特 信源符号 2 L 1 1 2 2 1 4 3 1 8 3 1 8 2 码符号 信源符号 3 0 p p 0 a0 p a0 p 0 a1 p a1 p 0 a2 p a2 p 0 a3 p a3 1 1 2 1 2 1 4 1 3 1 8 0 1 8 2 3 0 p p 0 a0 p a0 p 0 a1 p a1 p 0 a2 p a2 p 0 a3 p a3 1 1 2 1 2 1 4 1 3 1 8 0 1 8 2 3 1 p p 1 a0 p a0 p 1 a1 p a1 p 1 a2 p a2 p 1 a3 p a3 0 1 2 1 2 1 4 2 3 1 8 1 1 8 1 3 H X 2 3 log 2 3 1 3 log 1 3 0 9183 比特 信源符号 p 1 1 p a2 2 p a3 p a3 p a2 p a3 p a3 1 8 2 1 8 1 8 1 8 1 8 1 8 13 32 p 0 1 p a1 p a2 p a3 p a0 p a1 p a1 p a2 p a2 1 2 1 8 1 8 1 2 1 2 1 2 1 8 1 8 61 64 p 1 0 p a0 p a1 p a0 p a2 p a0 p a3 p a1 p a2 p a3 p a1 p a2 p a3 21 64 p 1 0 p a0 p a0 p a0 p a1 p a0 p a2 1 2 1 2 1 4 1 2 1 8 1 2 7 16 5 6 某信源有 8 个符号 概率分别为 l 2 l 4 1 8 1 16 1 32 1 64 1 128 1 128 试编成这样的码 000 001 010 011 100 101 110 111 的码 求 1 信源的符号熵 H X 2 出现一个 1 或一个 0 的概率 3 这种码的编码效率 4 相应的香农码和费诺码 5 该码的 编码效率 1238 a a aa 解 解 1 bit 信源符号 8 log1 984 ii i H Xpp 2 每个信源使用 3 个二进制符号 出现 0 的次数为 出现 1 的次数为 所以 P 0 P 1 3 因为3K 所以 0 661 4 相应的香农编码 信 源 符 号 xi 符 号 概 率 pi 累 加 概 率 Pi Logp xi 码长 Ki 码字 x1 1 2 0 1 1 0 x2 1 4 0 5 2 2 10 x3 1 8 0 75 3 3 110 x4 1 16 0 875 4 4 1110 x5 1 32 0 938 5 5 11110 x6 1 64 0 969 6 6 111110 x7 1 128 0 984 7 7 1111110 x8 1 128 0 992 7 7 11111110 相应的费诺码 信源符 号 xi 符 号 概 率 pi 第一次 分组 第二次 分组 第三次 分组 第四次 分组 第五次 分组 第六次 分组 第 七 次 分组 二元码 x1 1 2 0 0 x2 1 4 0 10 x3 1 8 0 110 x4 1 16 0 1110 x5 1 32 0 11110 x6 1 64 0 111110 x7 1 128 0 1111110 x8 1 128 1 1 1 1 1 1 1 11111110 5 香农码和费诺码相同 平均码长为 码符号 信源符号 编码效率为 1 5 7 设无记忆二元信源 概率为 0 p 0 005 1 p 0 995 信源输出的二元序列在长为 L 100 的信源 序列中只对含有 3 个或小于 3 个 0 的各信源序列构成一一对应的一组定长码 1 求码字所需的最小长度 2 考虑没有给予编码的信源序列出现的概率 该定长码引起的错误概率 P 是多少 解 解 1 信源序列中含有 3 个或小于 3 个 0 的各信源序列个数有 0123 100100100100 MCCCC 1 100 4950 161700 166750 对 M 个信源序列进行无失真的二元等长编码 必须 17 35 21667502 l M 所以所需的码长的最小长度 18l 2 496459559999100100 1000110001100011001 PCP PCP PCP PCP 110019929823973 1000100011000110001 10 0017CPCP PCP PCP P 5 8 已知符号集合为无限离散消息集合 它们出现的概率分别为 123 x xx 1 1 2p x 2 1 4p x 3 1 8p x 1 2i i p x 1 用香农编码方法写出各个符号消息的码字 2 计算码字的平均信息传输速率 3 计算信源编码效率 解 1 pi 累加概率为 Pi 累加概率分别为 符号 x1 x1 x2 x3 x4 x5 x6 x7 概率 1 2 1 4 1 8 1 16 1 32 1 64 1 128 1 256 累加 概率 0 0 5 0 75 0 8750 9380 9690 984 0 992 码长 1 2 3 4 5 6 7 8 二 元码 0 10 110 1110 11110111110111111011111110 2 信源的信息量为 平均码长为 码字的平均信息传输率为 R bit 码 3 编码效率 R 100 5 9 某信源有 6 个符号 概率分别为 3 8 1 6 l 8 l 8 1 8 1 12 试求三进码元 0 1 2 的费诺 码 并求出其编码效率 解 解 信源符号 概率 编码 码字 码长 X13 8 0 0 1 X21 6 0 10 2 X31 8 1 1 11 2 X41 8 0 20 2 X51 8 1 21 2 X61 12 2 2 22 2 H X 3 8 log 3 8 1 6 log 1 6 1 8 log 1 8 1 8 log 1 8 1 8 log 1 8 1 12 log 1 12 2 3852 三进制单位 信源符号 H3 X H X 1 5850 2 3852 1 5850 1 5049 三进制单位 信源符号 L 3 8 1 1 6 2 1 8 2 1 8 2 1 8 2 1 12 2 1 625 码符号 信源符号 H3 X L 1 5049 1 625 92 61 5 10 对下面给定的概率分布和基数 找出一个霍夫曼编码 1 0 2 0 1 0 1 0 3 0 1 0 2 2 3 4 5 Pa rb rc r d r i 解 解 1 a 00 10 11 011 0100 0101 b 00 01 02 10 11 12 c 00 01 10 11 12 13 d 1 00 01 02 03 04 5 11 若某一信源有N个符号 并且每个符号均以等概出现 对此信源用最佳霍夫曼二元编码 问当 N 2i和N 2i l i为正整数 时 每个码字的长度等于多少 平均码长是多少 解 当N 2i时 根据已知条件 每个符号码长应相等 这样平均码长最短 而且信源符号个数正好 等于 2i 则满足 q 222 l q l 所以每个码字的码长 i li Li 当N 2i l时 每个符号等概率出现 同时每个符号码长应基本相等 但现在信源符号个数不是正好 等于 所以必须有两个信源延长一位码长 这样平均码长最短 2l 所以N 2i l时 N 2i l个码字的码长为 i li 其余两个码字的码长为i 1 平均码长 2 21 i Li 5 12 设有离散无记忆信源 P X 0 37 0 25 0 18 0 10 0 07 0 03 1 求该信源符号熵 H X 2 用霍夫曼编码编成二元变长码 计算其编码效率 3 要求译码错误小于l0 3 采用定长二元码要达到 2 中的霍夫曼编码效率 问需要多少个信源符号 连在一起编码 解 1 H X 2 信源符号 xi 符 号 概 率 pi 编码过程 编码 码 长 x1 0 37 0 37 0 37 0 38 0 621 00 2 x2 0 25 0 25 0 25 0 37 0 38 01 2 x3 0 18 0 18 0 20 0 25 11 2 x4 0 10 0 10 0 18 100 3 x5 0 07 0 10 1010 4 x6 0 03 1011 4 3 自信息的方差为 6 22 1 log iii i D I sppH X 0 37 log0 37 2 0 25 log0 25 2 0 18 log0 18 2 0 1 log0 1 2 0 07 log0 07 2 0 03 log0 03 2 5 7646 2 2 1 i D I s N HX 2 5 7646 0 5822 1 3382 1 0 582 2 l0 3 6242 5 13 令 C 为均匀概率分布 1 1 1 nnnP 的一个二元霍夫曼编码 并假设 C 中码字的长度分别 是 令 其中12 i l2kna a 1 试证明在 P 的所有即时编码中 C 具有最小的总码字长度 i Tl 2 试证明 C 中至少有两个码字具有最大长度上 i lLmax 3 试证明 Kraft 不等式和 1 1 il r 4 试证明对所有的 i 都有或Lli 1 Lli 5 令 u 是长度为 L 1 的码字的个数 v 是长度为 L 的码字的个数 试用 a 与 k 来表示出 u v L 证明 1 信源共有 1个符号 并且为等概率分布 设码C为此信源的二元霍夫曼码 各码字的码长为 根据定理已知 信源给定时二元霍夫曼码一定是最佳即时码 即所有可能的即 时码中它是平均码长最短的码 若设C 2kna 2a i l 是任意其他即时码 根据霍夫曼码的最佳性则有 L CL C 设码C的总码长T 因为pi 1 n 所以 11 L ClT i nn i 设任意其他即时码C 的总码长T 并设各码字的长度为 有 i l 11 i i L ClT nn 所以得 11 TT nn TT 得 i i T l 为最短 2 3 由 2 证明已知 当 a 1 时 时 所有码字 i 的码长 2kn i l1Lk 则克拉夫不等式为 22 11 22 2 kk ii llkk ii r 1 当 a 2 时 时 所有码字 i 的码长 1 2kn i l1Lk 则克拉夫不等式为 11 22 11 11 22 2 kk ii llkk ii r 1 1x 当 1 a 2 时 1 11 2 2 22 2122 ii nn llkkkkk ii rxxx 即证 1 1 i n l i r 4 5 L k 1 1 1 1 2 2 2 22 21 kkk kk k vav vav va 1 1 得 1 1 2 2 2 k k va unva 5 14 信源符号 X 有 7 种字母 概率为 0 32 0 22 0 18 0 16 0 08 0 04 1 求符号熵 H X 2 用香农编码法编成二进制变长码 计算其编码效率 3 用费诺编码法编成二进制变长码 计算其编码效率 4 用霍夫曼编码法编成二进制变长码 计算其编码效率 5 用霍夫曼编码法编成三进制变长码 计算其编码效率 6 若用逐个信源符号来编定长二进制码 要求不出差错译码 求所需要的每符号的平均信息 率和编码效率 解 解 1 信源熵 H X 0 32 log0 32 0 22 log0 22 0 18 log0 18 0 16 log0 16 0 08 log0 08 0 04 log0 04 2 352 比特 信源符号 2 香农编码 信源符号 xi 符号概率 pi 累加概率 Pi Logp xi 码长 Ki 码字 x1 0 32 0 1 644 2 00 x2 0 22 0 32 2 184 3 010 x3 0 18 0 54 2 474 3 100 x4 0 16 0 72 2 644 3 101 x5 0 08 0 88 3 644 4 1110 x6 0 04 0 96 4 644 5 11110 平均码长 码符号 信源符号 0 877 编码效率 3 费诺编码 信源符 号 xi 符号概 率 pi 1 2 3 4 编码 码长 x1 0 32 0 00 2 x2 0 22 0 1 01 2 x3 0 18 0 10 2 x4 0 16 0 110 3 x5 0 08 0 1110 4 x6 0 04 1 1 1 1 1111 4 平均码长 码符号 信源符号 编码效率 0 979 4 哈夫曼编码 信源符号 xi 符 号 概 率 pi 编码过程 编码 码 长 x1 0 32 0 32 0 38 0 40 0 601 01 2 x2 0 22 0 22 0 32 0 38 0 40 10 2 x3 0 18 0 18 0 22 0 32 11 2 x4 0 16 0 16 0 18 000 3 x5 0 08 0 12 0010 4 x6 0 04 0011 4 平均码长 码符号 信源符号 编码效率 0 979 5 三进制霍夫曼编码 x1 1 x2 01 x3 02 x4 000 x5 001 x6 002 H3 X H X 1 5850 2 352 1 5850 1 4839 三进制单位 信源符号 L 0 32 1 0 22 2 0 18 2 0 16 3 0 08 3 0 04 3 1 58 码符号 信源符号 H3 X L 94 3 6 定长二进制编码 即7 3qr 3L 所以平均信息率 0 783 H X R L 比特 编码效率 78 3 H X L 5 15 已知一信源包含 8 个消息符号 其出现的概率为 P X 0 1 0 18 0 4 0 05 0 06 0 1 0 07 0 04 则求 1 该信源在每秒钟内发出 1 个符号 求该信源的熵及信息传输速率 2 对这 8 个符号作霍夫曼编码 写出相应码字 并求出编码效率 3 采用香农编码 写出相应码字 求出编码效率 4 采用费诺编码 写出相应码字 求出编码效率 解 1 信源熵 H X 0 1 log0 1 0 18 log0 18 0 4 log0 4 0 05 log0 05 0 06 log0 06 0 1 log0 1 0 07 log0 07 0 04 log0 04 2 552 比特 信源符号 信息传输速率 2 552bit s 2 信 源 符 号 xi 符 号 概 率 pi 编码过程 编码 码长 x1 0 4 0 4 0 4 0 4 0 4 0 4 0 6 1 1 x2 0 18 0 18 0 18 0 19 0 230 270 4 001 3 x3 0 1 0 1 0 13 0 18 0 190 23 011 3 x4 0 1 0 1 0 1 0 13 0 18 0000 4 x5 0 07 0 09 0 1 0 1 0100 4 x6 0 06 0 07 0 09 0101 4 x7 0 05 0 06 00010 5 x8 0 04 00011 5 3 香农编码 信 源 符 号 xi 符 号 概 率 pi 累 加 概 率 Pi Logp xi 码长 Ki 码字 x1 0 4 0 1 322 2 00 x2 0 18 0 4 2 474 3 011 x3 0 1 0 58 3 322 4 1001 x4 0 1 0 68 3 322 4 1010 x5 0 07 0 78 3 837 4 1100 x6 0 06 0 85 4 059 5 11011 x7 0 05 0 91 4 322 5 11101 x8 0 04 0 96 4 644 5 11110 平均码长 4 费诺编码 信源符 号 xi 符号概 率 pi 码 码长 x1 0 4 0 00 2 x2 0 18 0 1 01 2 x3 0 1 0 100 3 x4 0 1 0 1 101 3 x5 0 07 0 1100 4 x6 0 06 0 1 1101 4 x7 0 05 0 1110 4 x8 0 04 1 1 1 1 1111 4 5 16 有一信源包含 9 个符号 概率分别为 1 4 l 4 l 8 1 8 1 16 1 16 1