信息论2010练习答案

熵 是香农信息论最基本最重要的概念 单符号离散信源一般用随机变量描述 而多符号离散信源一般用 随机矢量 描述 两个相互独立的随机变量的联合自信息量等于 两个自信息量之和 离散平稳无记忆信源 X 的 N 次扩展信源的熵等于离散信源 X 的熵的 N 倍 对于 n 元 m 阶马尔可夫信源 其状态空间共有 nm 个不同的状态 若一离散无记忆信源的信源熵 H X 等于 4 2 对信源进行等长的无失真二进制编码 则 编码长度至少为 5 同时掷两个正常的骰子 各面呈现的概率都为 1 6 则 3 和 6 同时出现 这件事的自信息 量是 log218 1 2 log23 一副充分洗乱的扑克牌 52 张 从中任意抽取 1 张 然后放回 若把这一过程看作离散 无记忆信源 则其信源熵为 52log2 具有一一对应关系的无噪信道的信道容量 C log2n 信道编码定理是一个理想编码的存在性定理 即 信道无失真传递信息的条件是 信息率小 于信道容量 信源的消息通过信道传输后的误差或失真越大 信宿收到消息后对信源存在的不确定性就 越大 获得的信息量就越小 平均失真度的下限取 0 的条件是失真矩阵的 每一行至少有一个零元素 率失真函数对允许允许的平均失真度是 单调递减和连续的 对于离散无记忆信源的率失真函数的最大值是 log2n 信源编码的目的是 提高通信的有效性 对具有 8 个消息的单符号离散无记忆信源进行 4 进制哈夫曼编码时 为使平均码长最短 应增加 2 个概率为 0 的消息 对于香农编码 费诺编码和哈夫曼编码 编码方法惟一的是 香农编码 游程序列的熵 等于 原二元序列的熵 n 位重复码的编码效率是 1 n 若纠错码的最小距离为 dmin 则可以纠正任意小于等于 t 2 1 min d 个差错 单符号离散信源的自信息和信源熵都具有非负性 对 自信息量 条件自信息量和联合自信息量之间有如下关系 jijijiji yxIyIxyIxIyxI 对 自信息量 条件自信息量和互信息量之间有如下关系 ijjjiiji xyIyIyxIxIyxI 对 当随即变量 X 和 Y 相互独立时 条件熵等于信源熵 对 若对一离散信源 熵为 H X 进行二进制无失真编码 设定长码子长度为 K 变长码子 平均长度为K 一般K K 错 信道容量 C 是 I X Y 关于 p xi 的条件极大值 对 离散无噪信道的信道容量等于 log2n 其中 n 是信源 X 的消息个数 错 率失真函数没有最大值 错 率失真函数的最小值是 0 对 信源编码通常是通过压缩信源的冗余度来实现的 对 在编 m m 2 进制的哈夫曼码时 要考虑是否需要增加概率为 0 的码字 以使平均码长 最短 对 在游程编码过程中 0 游程和 1 游程应分别编码 因此 它们的码字不能重复 错 汉明码是一种线性分组码 对 循环码也是一种线性分组码 对 卷积码是一种特殊的线性分组码 错 1 i j是两个码符号 0 1 组成的符号序列 求 i j 之间的汉明距离 解 D i j 2 已知随即变量 X 和 Y 的联合分布如下所示 01 01 83 8 13 81 8 试计算 H X H Y H XY H X Y H Y X I X Y 1 H X 1 H Y 1 2 3 H X Y H XY H Y 1 811 1 0 811 4 H Y X H XY H X 1 811 1 0 811 5 4 在一个袋子里放有 5 个黑球 10 个白球 以摸一个球为一次实验 摸出的球不再放回 去 1 一次实验包含的不确定度 2 第一次实验 X 摸出的是黑球 第二次实验 Y 给出的 不确定度 3 第一次实验 X 摸出的是白球 第二次实验 Y 给出的不确定度 5 两个实验 X 和 Y X x1 x2 x3 Y y1 y2 y3 联合概率 p xiyj pij已经给出 p11 7 24 p12 1 24 p13 0 p21 1 24 p22 1 4 p23 1 24 p31 0 p32 1 24 p33 7 24 1 如果有人告诉你 X 和 Y 的实验结果 你得到的平均信息量是多少 2 如果有人告诉你 Y 的实验结果 你得到的平均信息量是多少 3 在已知 Y 实验结果的情况下 告诉你 X 的实验结果 你得到的平均信息量是多少 Y X 6 黑白传真机的消息源只有黑色和白色两种 即 X 黑 白 一般气象图上 黑色的 出现概率 p 黑 0 3 白色出现的概率 p 白 0 7 1 假设黑白消息前后无关 求信源熵 H X 2 实际上各个元素之间关联 其转移概 率为 P 白 白 0 9143 p 黑 白 0 0857 P 白 黑 0 2 p 黑 黑 0 8 求这个 一阶马尔可夫信源的信源熵 并画出转移图 3 比较两种信源熵的大小 并说明理由 1 bit 符号22 1010 0 3log0 7log0 8813 37 H X P 黑 白 P 黑 P 白 白 P 白 黑白 0 7 0 3 0 70 3 P 黑 黑 P 黑 P 白 黑 P 白 2 根据题意 此一阶马尔可夫链是平稳的 P 白 0 7 不随时间变化 P 黑 0 3 不随 时 间变化 212 222 2 1 log 111 0 9143 0 7log0 0857 0 7log0 2 0 3log 0 91430 08570 2 1 0 8 0 3log 0 8 ij ij ij HXH XXp x y p x y 0 512bit 符号 13 设分组码 n k 中 n 6 n 3 并按下列方程选取字中的码字 求信息序列 a1a2a3 变换成六位的八个码字 并求出编码效率 信息序列 码字 a1a2a3 c1c2 c3c4c5c6 000 000000 001 001011 010 010101 100 100110 011 011110 101 101101 110 110011 111 111000 编码效率 2 32 一阶马尔可夫信源的状态图如图 2 13 所示 信源 X 的符号集为 0 1 2 1 求信源平稳后的概率分布 P 0 P 1 P 2 2 求此信源的熵 3 近似认为此信源为无 记忆时 符号的概率分布为平稳分布 求近似信源的熵 H X 并与进行比较H 01 2 1 p p 2 1 p p 2 p 2 p 2 p 2 p 2 1 p 图2 13 解 根据香农线图 列出转移概率距阵令状态 0 1 2 平稳后的概率分布 1 2 2 21 2 2 21 ppp Pppp ppp 分别为 W1 W2 W3 得到 计算得到 3 1 1i i WPW W 1231 1232 123 1 22 1 22 1 pp p WWWW pp Wp WWW WWW 1 3 1 3 1 3 W W W 由齐次遍历可得 112 3 1 1 loglog 32 21 ii i p p HXWH X WHppp pp 符号 由最大熵定理可知存在极大值 log31 58 H Xbit HX 或者也可以通过下面的方法得出存在极大值 12 1 log 1 1 loglog 1222 1 HXppp pp pppp 又所以当 p 2 3 时 11 2 1 22 1 p pp 01p 0 2 1 p p 1 2 1 p p 0 p 2 3 时 log0 2 1 HXp pp 2 3 p 1 时 log0 2 1 HXp pp 所以当 p 2 3 时存在极大值 且符号 所以 HX max 1 58 HXbit HXH X 8 设有一信源 它在开始时以 p a 0 6 p b 0 3 p c 0 1 的概率发出 X1 如果 X1 为 a 时则 X2 为 a b c 的概率为 1 3 如果 X1 为 b 时则 X