chp02-chp06老师手写的习题答案.pdf

20110102 习题答案 chp02 chp06 doc Created by SongNa 习题答案 第 1 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 2 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 3 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 4 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 5 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 6 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 7 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 8 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 9 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 10 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 11 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 12 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 13 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 14 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 15 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 16 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 17 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 18 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 19 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 答案 答案 5 6 1 我们将品尝次数看作码字的码长 由于只能一次品尝每一瓶酒 所以对于这个题目而言码长只 能是 1 2 3 4 4 这样的分布 所需的平均品尝次数就是平均码长 要想使得平均码长最小 则 应该将较短的码长安排给概率较大的符号 因此所需的最小平均品尝次数为 5 1 111117 123442 3466123 ii i l p 33 2 这个问题可以转化为求取此概率分布的 Huffman 编码 如下图 概率 1 3 1 4 1 6 1 6 1 12 码字 00 01 11 100 101 品尝是首先将第一比特为 0 的酒混合起来品尝 分出好坏后再按照第二比特来混合 知道找到坏酒 因此平均品尝次数为 5 1 1111127 222332 34661212 ii i l p 25 由于上述编码 首先应该品尝第一和第二瓶酒的混合 或者品尝第三 四 五瓶酒的混合 由于霍夫曼编码不是唯一的 所以还存在另外的方案 其对应的编码如下 概率 1 3 1 4 1 6 1 6 1 12 码字 00 10 11 010 011 在这种方案指导下 首先应该品尝第一 四 五瓶酒的混合 5 7 解 解 根据已知条件可以得到联合随机变量 根据已知条件可以得到联合随机变量 X1 X2 X3 的概率分布如下表所示 的概率分布如下表所示 x1x2x3 联合概率联合概率 p x1x2x3 x1x2x3 联合概率联合概率 p x1x2x3 000 1 4 100 1 4 第 20 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 001 1 12 101 1 12 010 1 8 110 1 8 011 1 24 111 1 24 则根据霍夫曼编码算法得到编码结果如下表所示 则根据霍夫曼编码算法得到编码结果如下表所示 x1x2x3 码字 x1x2x3 码字 000 01 100 10 001 0000 101 0001 010 001 110 110 011 1110 111 1111 平均码长 L 1 24 2 6 6 3 3 3 4 2 2 1 1 2 75 码符号 信源符号 5 8 Kraft McMillan 不等式不等式 1 1 i q l i r 对于 000 10 00 11 1 此码满足 Kraft McMillan 不等式 2 此码不是即时码 因为码字 00 是码字 000 的前缀 3 此码不是唯一可译码 因为码符号序列 000000 可以译码为 00 00 00 也可以译码为 000 000 对于 100 101 0 11 1 此码满足 Kraft McMillan 不等式 2 根据码树图可知 此码是即时码 3 由于此码是即时码 所以它也是唯一可译码 对于 01 100 011 00 111 1010 1011 1101 1 此码不满足 Kraft McMillan 不等式 2 因为不满足 Kraft McMillan 不等式 此码不是即时码 3 因为不满足 Kraft McMillan 不等式 此码不是唯一可译码 第 21 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 对于 01 111 011 00 010 110 1 此码满足 Kraft McMillan 不等式 2 此码不是即时码 因为码字 01 是码字 011 的前缀 3 此码是唯一可译码 根据唯一可译码判决准则 构造其尾随后缀集 F 1 0 11 10 其中 没有和码字相同的元素 习题习题 1 具体的编码过程图 具体的编码过程图 第 22 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 第 23 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 1 信源 X 对应的平均码长为 2 72 编码效率为 95 9 信源 Y 对应的平均码长为 2 33 编码 效率为 99 3 2 信源 X 对应的平均码长为 3 14 编码效率为 83 1 信源 Y 对应的平均码长为 2 89 编码 效率为 80 1 3 信源 X 对应的平均码长为 2 74 编码效率为 95 2 信源 Y 对应的平均码长为 2 33 编码 第 24 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 效率为 99 3 4 从信源 X 和 Y 的三种不同编码方法可以看出 霍夫曼编码平均码长最短 编码效率最高 香农编码所得平均码长最长 其编码效率最差 而费诺码居中 霍夫曼码其编码时短码得到充分利用 而且一定是概率大的信源符号对应于短码 概率小的 信源符号对应于长码 所以 其平均码长最短 香农编码方法虽然概率大的符号其码长短 概率小的符号其码长长 但它短码没有被充分利 用 所以 其平均码长增大 费诺码也是一种较好的编码方法 如信源 Y 的费诺码与霍夫曼码的编码效率一样好 而信 源 X 的费诺码的编码效率比其霍夫曼码的编码效率降低极少 这是因为信源 Y 在费诺码编 码过程中分两大组时 概率和 相差不多 为 0 49 和 0 51 而信源 X 在编码过程中每次分 两组时 其 概率和 相差较远 第一次为 0 57 和 0 43 第二次上面分组为 0 2 和 0 37 习题习题 2 解 对于三元霍夫曼码 要使短码得到充分利用 必须信源符号个数 q 要满足 q r 1 r 现在 r 3 若 3 时 q 9 所以需要增加一个概率为 0 的符号 信源 S 的三元霍夫曼码为 习题习题 3 解 1 根据 MH 码表可得 该扫描行的 MH 码为 64 白 9 白 7 黑 11 白 18 黑 1600 白 19 白 EOL 11011 10100 00011 01000 0000001000 010011010 0001100 000000000001 2 编码后该行总比特数为 58 位 3 这一行编码压缩比为 1728 58 29 8 第 25 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 答案 答案 6 2 解 解 由于本离散信道的输入符号的先验概率 P xi 不是等概率分布 所以对于最小错误概率准则必须根 据联合概率 P xiyj 的大小来选择 可写出对应的联合概率分布为 111 4612 111 24812 11 12248 ij p x y 1 3 按照最小错误概率准则 选择每一列当中最大的概率对应的输入符 号为译码规则 所以确定的译码规则是 11213 F yx F yx F yx 对应的平均错误概率为 11111111 2412824121224 Eij Y Xa PP xy 对于最大似然译码准则 可以直接从信道矩阵的传递概率中选择每列最大的概率对应的输入符号为 译码函数 所以 按最大似然译码准则确定的译码规则是 11223 F yx F yx F yx3 对应的平均错误概率为 1111111 241262412122 Eij Y Xa PP E P x y 习题习题 1 答案 答案 1 此码的最小距离 dmin 3 2 此二元码的码字个数 M 4 码长 n 5 所以码率 R log4 5 2 5 比特 码符号 3 采用最小距离译码准则 即将接收序列译成与其码距为最小的码字 接收序列 10000 与码 字 10010 距离为 1 与其他码字距离都大于 1 所以同理 10000 译成 10010 01100 译成 11100 00100 译成 11100 或 00111 任一个 4 因为此码 dmin 3 2 1 1 即 e 1 所以 此码能纠正所有发生一位码元的随机错误 习题习题 2 答案 答案 1 因为码字数M 8 2k 23 所以k 3 n 6 为 6 3 线性分组码 2 生 成 矩 阵 G 为 k 3 行 n 6 列 的 矩 阵 由 k 3 个 线 性 独 立 的 码 字 组 成 故 k 1 0 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 GI Q 第 26 页 共 27 页 20110102 习题答案 chp02 chp06 doc Created by SongNa 3 由生成矩阵可得一致校验矩阵 r 0 1 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 T HQI 习题习题 3 答案 答案 1 设码字 C c7c6c5c4c3c2c1c0 另 c7 m1 c6 m2 c5 m3 c4 m4 由此将一致校验方程改写为 37647643 27547542 17657651 06546540 0 0 0 0 cccccccc cccccccc cccccccc cccccccc 先将方程组改写为方程的等号右边为 0 I 可以写成矩阵相乘的形式 7 6 5 4 3 2 1 0 1 101 10000 101 101000 1 1 1000100 01 1 100010 c c c c c c c c 由此可得则其一致校验矩阵为 r 1 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 0 0 1 HP 可直接写出生成矩阵为 k 1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0