信息论与编码第2章习题解答.pdf

第二章习题解答分为两部分 第二章习题解答分为两部分 PartA 1 11 页 1 2 3 4 5 8 9 18 19 22 24 25 PartB 12 17 页 5 另解 6 10 11 12 20 1 信息论与编码 第二章习题解答 2 1 A村有一半人说真话 10 3 人总说假话 10 2 人拒绝回答 B村有 10 3 人诚实 一半 人说谎 10 2 人拒绝回答 现随机地从 A村和 B村抽取人 p 为抽到 A村人的概 率 1 p 为抽到 B村人的概率 问通过测试某人说话的状态平均能获得多少关于该 人属于哪个村的信息 通过改变 p 求出该信息的最大值 解 用 X 表示随机抽取人所属的村别 Y 表示说话的状态 则 X 和 Y 之间的关系图如下 所示 1 BPAP 1 3 0 5 0 1 ApApyP 1 5 0 3 0 2 ApApyP 2 0 1 2 0 2 0 3 ApApyP 3 1 log i ii ypypYH BXYHBPAXYHAPXYH 2 0 3 0 5 0 H 0 5log0 50 3log0 30 2log0 21 485 bit XYHYHYXI 由对称性 当5 0 BPAP时 互信息最大 这时 0 4log0 40 4log0 40 2log0 21 522H Y bit 所以 0 037I X YH YH Y X bit 2 2 一个无偏骰子 抛掷一次 如果出现 1 2 3 4 点 则把一枚均匀硬币投掷一次 如果骰子出现 5 6 点 则硬币投掷二次 求硬币投掷中正面出现次数对于骰子出 现点数所提供的信息 A B X Y y1说真话 y2撒谎 y3拒绝回答 0 3 0 3 0 5 0 2 0 2 0 5 2 解 令 1 xX 表示掷骰子出现 1 2 3 4 点 2 xX 表示出现 5 6 点 Y 表示出现 硬币正面的次数 于是 X 和 Y 具有如下关系图 3 2 1 xXP 3 1 2 xXP 12 5 0 yYP 2 1 1 yYp 2 1 2 yYp 所以 XYHYHYXI 3 1 3 2 12 1 2 1 12 5 21 xXYHxXYHH 4 1 2 1 4 1 3 1 2 1 2 1 3 2 12 1 2 1 12 5 HHH 0 158 bit 2 3 在某中学有 4 3 学生通过了考试 4 1 学生没有通过 在通过考试的同学中 10 有自行 车 而没有通过的学生中 50 有自行车 所有有自行车的同学都加入了联谊会 无自行车的同学中仅有 40 加入联谊会 a 通过询问是否有自行车 能获得多少关于学生考试成绩的信息 b 通过询问是否参加联谊会 能获得多少关于学生成绩的信息 c 如果把学生成绩情况 自行车拥有情况和是否参加联谊会用三位二进数字传 输 问每位数字携带多少信息 解 X 表示学生有无通过考试 Y 表示学生有无自行车 Z 表示学生有无参加联谊会 X Y Z 之间的关系图 x1 x2 X Y y0 无正面 y1 1 次正面 y2 2 次正面 1 2 1 4 1 2 1 4 1 2 x1 x2 通过 没通过 y1 有车 y2 无车 0 1 0 5 0 9 0 5 X Y z1 参加 z2 没参加 1 0 4 0 6 Z 3 75 0 1 xP 25 0 2 xP 2 0 1 yP 8 0 2 yP 52 0 1 zP 48 0 2 zP 46 0 11 xzP 54 0 12 xzP 7 0 21 xzP 3 0 22 xzP a XYHYHYXI 5 0 5 0 25 0 9 0 1 0 75 0 8 0 2 0 HHH 0 12 bit b XZHZHZXI 0 52 0 48 0 75 0 46 0 54 0 25 0 7 0 3 HHH 0 03 bit c 第一位数字携带信息为 0 75 0 25 0 811H XH bit 在已知第一位数字下 第二位数字携带信息为 5 0 5 0 25 0 9 0 1 0 75 0 HHXYH 0 602 bit 在已知前二位数字下 第三位数字携带信息为 YZHYXZH 因为 X Y Z 6 0 4 0 8 0 1 2 0HH 6 0 4 0 8 0 H 0 777 bit 2 4 随机掷三颗骰子 以 X 表示第一颗骰子抛掷的结果 以 Y 表示第一颗和第二颗骰子 抛掷之和 以 Z 表示三颗骰子的点数之和 试求 H X Y H Y X H Z X Y H X Z Y 和 H Z X 解 设第一颗骰子结果为 X1 第二颗骰子结果为 X2 第二颗结果为 X3 则 X1 X2 X3 是独立同分布随机变量 1 XX 21 XXY 321 XXXZ X 和 Y 的事件空间和对应概率为 123456 1 61 61 61 61 61 6 X p x 4 23456789101112 12345654321 3636363636363636363636 Y p y 所以 1232 log 62 585H XH XH XH X bit log 21 i y ii yPyPXXHYH 3 274 bit 3 2 585H Z YH XH X bit YHXYHXHYXH 2 YHXHXH 2YHXH 1 896 bit 2 2 585H Y XH XH X bit 3 2 585H Z X YH XH X bit 23 3 274H Z XH XXH Y bit H X Z YH X YH Z X Y 1 896 2 585 4 481 bit 2 5 设一个系统传送 10 个数字 0 1 2 9 奇数在传送时以 0 5概率等可能地 错成另外的奇数 而其他数字总能正确接收 试求收到一个数字后平均得到的信 息量 解 X 表示发送数字 Y 表示接收到数字 YXI log xy p x y p x y p x 0 125 在上式求和中 使0 yxp的输入 输出对 x y 可分为 3 类 8 8 6 6 4 4 2 2 0 0 1 S 9 9 7 7 5 5 3 3 1 1 2 S 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 X Y 1 0 5 5 7 9 5 9 3 9 1 9 9 7 5 7 3 7 1 7 9 5 7 5 3 5 1 5 9 3 7 3 5 3 1 3 9 1 7 1 5 1 3 1 3 S 1 0 00 log 0 0 5 log Syx Xp YX yxp xp yxp yxp 6609 110log5 0 1 0 1 log1 05 5805 05log25 0 1 0 5 0 log05 05 log 2 Syx xp yxp yxp 3 1 31 log 3 1 20 log Syx Xp YXp YXp xp yxp yxp 08 0 1 0 125 0 log0125 020 所以 2 3214I X Y bit 2 8 定义 1 YXHYXIYXYXS 为随机变量 X 和 Y之间的相似 度 证明 a 0 S X Y 1 b S X X 1 c 当 X 和 Y 统计独立时 S X Y 0 证明 a 因为 0 0 YXHYXI 所以 0 I X Y S X Y H X Y 又 I X Y S X Y H X Y 1 XYHXH YXHXH b 1 XH XH XXH XXI XXS c 若 X 和 Y 统计独立 则 XHYXH 所以 0 0 YXHYXH YXI YXS 6 2 9 若三个随机变量 X Y Z 有 X Y Z 成立 其中 X 和 Y 独立 试证 a H X H Z b H Y H Z c H X Y H Z d I X Z H Z H Y e I X Y Z H Z f I X Y Z H X g I Y Z X H Y h I X Y Z H X Z H Y Z 证明 因为 ZYX 所以 kikii p ZzXxp YzxXx 所以对给定 i xX 有 ii H Z XxH YXx 所以 XYHXZH 因为YX 独立 所以 H X Y ZH ZH X Y ZH X YH Z X Y H X Y c ZHYHXHYXH b H ZH XH YH X Y Z XZYHZXHYHXH ZXHYHXH ZXIYH 所以 YHZH 同理 a XHZH d ZXIYHZH e ZHXYZHZHZXYI f XHYZXHXHYZXI g YHXZYHXYHXZYI h ZXHYZXHZXHZYXI ZYH 7 2 18 令 U是非负整数集合 事件 k U的概率为 kp 且 0 k Akkp 试求 H U 达到最大的分布 kp 解 利用拉格朗日乘子法 引入参数 1 和 2 求如下目标函数的最大值 12 000 ln k kkk Jpp kp kp kkp k 其中 1 和 2 由约束条件 0 1 k p k 和 0 k k p kA 来待定 ln 21 0 kp e kppJ k k k 1 21 0 kp e kp k k 当1 21 kp e k 时上式等号成立 也就达到目标函数 J的最大值 这时 k ekp 21 2 1 0 k 由约束条件 1 00 21 k k k eekp Akeekkp k k k 00 21 设 21 21 eAeA 即 A A AA A A 2 2 21 2 1 1 1 1 解出 A A A A A 1 1 1 12 所以达到最大熵的分布为 k A A A kp 1 1 1 2 1 0 k 8 2 19 设 X 是 1 1 上的均匀分布随机变量 试求 XHC 2 XHC 解 0 2 1 xp 1 1 1 1 x x dxxpxpXHc log 1log2 2 1 log 2 1 2 bit 令 Y X2 则 0 2 1 yyp 0 1 0 1 y y 所以 dyypypYHC log 1 0 11 ln ln21 22 dy yy nat 2 22 一个二状态平稳马尔可夫信源 输出为 X0 X1 X2 信源状态转移矩阵为 5 2 5 3 10 9 10 1 P 对任何 n 求 12 1 n H X XX n 和 121 Nn XXXXH 解 由于信源是一阶平稳马尔可夫过程 所以 121211 11 nnn H X XXH XH XXH XX nn 121 11 n H XH XX nn 1 121 21 1 1 nnn H Xn H XXXX H XXn 由状态转移矩阵可以画出状态转移图如下 S0 S1 0 1 0 9 0 6 0 4 9 稳态状态概率满足下面方程 010 0 1 0 3 P SP SP S 011 0 9 0 2 P SP SP S 01 1P SP S 解出状态概率为 01 0 4 0 6P SP S 因为 0 0 469H X S bit 1 0 971H X S bit 所以 210011 H XXP S H X SP S H X S 0 77 bit 由于无条件输出符号概率为 01 0 0 1 0 6 0 4pP SP S 01 1 0 9 0 4 0 6pP SP S 所以 1 0 97H X bit 从而 12 10 971 0 77 n n H X XX nnn bit 1 2 3 n 121 0 97bit1 0 77bit1 nnn n H XXXX n 2 24 一阶马尔可夫信源的状态图如图所示 信源符号集为 0 1 2 并定义pp 1 a 求信源平稳概率分布 2 1 0 ppp b 求此信源的熵 c 近似认为此信源为无记忆时 符号概率分布等于平稳分布 求此近似信源的 熵 H X 并与 H进行比较 d 对一阶马尔可夫信源 p 取何值时 H取最大值 又当 p 0 和 p 1 时结果如 何 习题 2 24 图 2 0 1 p p p 2 p 2 p 2 p 2 p 2 p 2 p 10 解 a 稳态分布满足 0 1 2 0 22 0 1 2 1 22 0 1 2 2 22 0 1 2 1 pp p pppp pp pp ppp pp ppp pp ppp 由方程对称性 显然解为 3 1 2 1 0 ppp b 在状态 S i 条件下的条件熵为 2 loglog p pppiSXH i 0 1 2 则信源熵率 2 0 2 loglog i p pppiSXHiSpH c 当信源作为无记忆时 信源输出符号 i 的概率为 3 0 j jSixpjSpixp 3 1 i 0 1 2 所以近似无记忆信源熵为 log3loglog 2 p H XHppp d 当时 3 2 p H达到极大值为log3 bit 当 p 0 时 0 H bit 当 p 1 时 1H bit 2 25 一阶马尔可夫信源的状态转移图如图所示 信源 X 的符号集为 0 1 2 1 求平稳后信源的概率分布 2 求信源的熵 H 3 求当 p 0 和 p 1 时的信源熵 并说明理由 11 习题 2 25 图 解 1 平稳后信源状态分布 p 0 p 1 p 2 满足 1 2 1 0 2 0 2 1 2 1 0 1 0 ppp ppppp ppppp ppppp 解出状态稳态分布为 3 1 2 1 0 ppp 2 在状态 S i 条件的条件熵为 ppppiSXHloglog i 0 1 2 2 0 loglog i ppppiSXHipH 3 当 P 0 1 0 H 这时信源无不确定性 p 0 时表示信源输出常数 p 1 时表示信源周期地输出 0 1 2 0 1 2 p pp p p p 2 5 题另解 I X YH YH YX n n p xn p yn p y xnp xnp y xnp xn 为偶数 为奇数 0 1 0 1 log0 13 32 H Yb it H Y XH Y XP XH Y XP X 偶数偶数奇数奇数 00 5 0 5log0 540 125log0 125 1 bit 3 32212 322 bit I X YH YH YX 2 6 对任意概率分布的随机变量 试证明下述三角不等式成立 a H X YH Y ZH XZ H X YH Y ZH X YH Y Z H X YH Y ZH X Z 提示 H X YH Y ZH X YH Y Z H X YH Y ZH X YH Y ZH Z H X ZH X Z H X ZH ZH X Z 其中 第二个不等式是由于本题 a 和函数 x f x xH Z 的单调递增性 证明 证明 a H X YH Y ZH X Y ZH Y ZH X Y Z 而 H X Y ZH XZH YX Z 0H YX Z H X YH Y ZH XZ b H X YH X YH YH Z Y H X YH Y ZH Z H Y ZH Y ZH ZH X Y 又 x f x xH Z 0 2 H Z fx xH Z 单调递增 f x H X YH Y ZH X YH Y Z H X YH Y ZH X YH Y ZH Z H X ZH X Z H X ZH ZH Z 2 10 令X是离散随即变量 Yg X 是的函数 求证X H XH Y 证明 证明 Y是X的函数 1P YX 0H YX 又 H X YH XH YXH YH X Y H YH X YH X H XH Y 2 11 试证明 如 则是 0H YX YX的函数 也就是对一切使的 仅 有一个可能的 0p x x y取值 具有 0p x y 证明 证明 若 则对任意使的 0H YX 0p x xi有 0H Y xi 由熵的非负性可知 log 0H Y xp y xp y x iii i 或 0p y xi 1p y xi 也就是任何使的 0p x xi 都有确定的y取值 2 12 令 1 X和 2 X为分别定义在字符表 1 2 m 1 和 1 m n 2 上的 2 个 离散随机变量 它们的分布函数为和 现构造随机变量 1 p i 2 pi 1 1 2 Xa X Xa 以概率 以概率 a 试用 和a来表示 1 H X 2 H XX的熵 H X b 在上求a H X的极大值 证明 12 222 H XH X H X 解 解 a 由熵的可加性可得 1 12 H XaH Xa H XH a 1 log 1 log 1 12 aH Xa H Xaaaa b loglog 1 0 12 dH X H XH Xaa da 解得 121 22 0 1 1212 1222 H XH XH X aa H XH XH XH X 而 2 11 0 2 1 ln2ln2