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

信息论与编码 第四章习题解答 4 1 计算如下所示离散无记忆信道的容量 习题 4 1 图 解 a 信道概率转移矩阵为 1 1 P 信 道 是 准 对 称 信 道 因 此 在 输 入 为 等 概 分 布 时 达 到 信 道 容 量 即 5 0 1 0 XPXP时达到信道容量 这时 5 05 0 0 YP 1 YP 5 05 0 2 YP 相应的信道容量为 1 0 YXIYXIC 2 0 0 log 0 j jp jp jp 0 0 1 1 1 1 0 0 1 2 1 1 1 0 0 2 2 1 0 5 1 1 0 25 0 25 0 5 0 5 0 0 2 2 1 1 1 1 1 0 0 2 2 3 4 1 4 1 1 1 3 1 3 1 3 1 4 3 4 0 0 2 3 1 1 3 2 1 1 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 c a b e f d 5 05 0 loglog 5 05 0 1 log 1 5 05 0log 1 log 1log 1 b 信道概率转移矩阵为 5 05 00 25 025 05 0 001 P 当5 0 2 0 XPXP 0 XP时 5 0 0 YP 25 0 1 YP 25 0 2 YP 1 0 log 0 0 2 0 j jp jp jpYXI bit 2 0 2 log 2 2 j jp jp jpYXI 1 25 0 5 0 log5 0 25 0 5 0 log5 0 bit 10 1 YXI 所以满足定理 4 2 2 条件 由达到信道容量充要条件可知 信道容量 C 1 bit 次 c 信道转移概率矩阵为 10 10 01 P 信道是对称信道 当输入为均匀分布时 即 3 1 2 1 0 XPXPXP 时 达到信道容量 1log 1 log3log C 1 3log H d 信道转移概率矩阵为 4 3 4 1 0 3 1 3 1 3 1 0 4 1 4 3 P 当5 0 2 0 XpXp 0 1 Xp时 8 3 2 0 YPYP 8 2 1 YP 2 0 0 log 0 0 j jp jp jpYXI 1log 4 1 2log 4 3 4 3 bit 4 3 2 YXI bit 2 0 1 log 1 1 j jp jp jpYXI 8 3 3 1 log 3 1 8 2 3 1 log 3 1 8 3 3 1 log 3 1 6 8 log 3 1 9 8 log 3 2 4 3 bit 所以满足定理 4 2 2 所规定的达到信道容量的充要条件 信道容量为 4 3 C bit 次 e 3 1 3 1 0 3 1 3 1 3 1 3 1 0 3 1 0 3 1 3 1 P 信道是准对称信道 当输入分布为均匀分布时达到信道容量 即 3 1 2 1 0 XpXpXp时达到信道容量 信道容量为 2 0 3 0 log ij jp ijp ijpipC 其中 9 2 2 1 0 YpYpYp 3 1 3 Yp 所以 3 1 3 1 log 9 1 3 9 2 3 1 log 9 1 6 C 2 3 log 3 2 bit 次 f 信道转移概率矩阵 1 1 P 利用方程求逆方法计算信道容量 设 qXp 0 qXp 1 1 10 q 则 1 1 0 0 qqYp 1 1 1 1 qqYp 记 00 log C 11 log C 于是得到 log 1log 1 1 10 H 1log 1 log 1 00 H 解上面方程得 1 1 0 HH 1 1 1 HH 所以 j j C 2log 1 1 1 1 22log HHHH 由 C 0 2 0 1 2 1 解出 1 1 10 q 1 1 1 01 q 4 2 计算如下信道的容量 解 把该信道看成是退化信道 1 C和二元对称信道 2 C的和信道 退化信道 1 C 二元对称信道 2 C 0 0 1 1 1 1 1 2 2 0 0 0 1 1 1 2 2 1 1 习题 4 2 图 退化信道容量为0 1 C 二元对称信道容量为 1 2 HC 所以和信道的容量为 1 21log H C 达到信道容量的输入分布为 CC Xp 1 2 0 1 21 1 H 2 1 XpXp CC 2 25 0 1 21 2 H H 4 3 考虑离散无记忆信道 Y X Z mod 11 其中 3 1 3 1 3 1 3 2 1 Z 0 1 10X 假定 Z 和 X 独立 求 1 信道容量 2 达到信道容量的输入分布 xP 解 信道为对称信道 所以当输入为均匀分布时 即 11 1 iXp 10 1 0 i 时达到信道容量 信道容量为 3 1 3 1 3 1 11logHC 3 11 log bit 次 4 4 用差错率为 的二元对称信道 BSC 构成如下复合信道 1 长度为 N 的级联信道 求该级联信道的容量 N C 并证明0lim N N C 习题 4 4 1 图 级联信道 2 并联输入信道 把输入 X 并联接到各信道 输出是矢量 当N 时并联输 入信道容量趋于 1 BSC BSC BSC X0 X1 X2 XN 习题 4 4 2 图 并联输入信道 习题 4 4 3 图 积信道 3 N 个相同 BSC 的积信道 求这时积信道容量 N C 且证明 N N Clim 证明 1 见例 4 3 2 2 首先因为 2121NN YYYXHXHYYYXI XH 1 bit 所以对任何 N 并联输入信道容量1 N C bit 下面证明当 N时 1 N C bit 我们对输出 N YYY 21 作进一步处理 如下图所示 其中 N i iN NYZ 1 BSC BSC BSC N Y N i i 1 YN Y2 Y1 2 1 ZN Z N X BSC X1 Y1 BSC X2 Y1 BSC XN YN BSC X Y1 BSC Y2 BSC YN 2 1 1 2 1 0 N N N Z Z Z 由于当 X 0 时 i Y是独立 同分布二元随机变量 pXYp i 0 1 pXYp i 1 0 0 pXZE N 0 N pp XZN 1 2 0 利用切比雪夫不等式 1 1 0 0 2 NN P ZXP ZX 0 2 1 XppZP N 0 2 1 XppZP N 2 2 0 2 1 p XZ N 2 2 1 1 pN pp 当 2 1 1 时相应的转移概率图与转移概率矩阵为 aa 110 5 005 00 05 005 0 P 这时为无损信道 容量为 C 1 bit 次 当 a 1 时 相应转移概率图和转移概率矩阵为 5 05 00 05 05 0 P 这时为二元除删信道 容量为 5 05 01 C bit 次 4 14 给定系统带宽为 W 噪声功率谱密度为 0 N 试证明传送一比特信息所需最小能量为 0 693 0 N 瓦 如果要求4000 0 WN S 其中 S 为信号功率 试证明所需的信号能量至 少为此最小值的 482 倍 证明 由 4 6 1 节可知在频带效率 下 每传 1bit 所需能量为 0 12 NEb 其中不等式右边是 b b WTW R1 的增函数 对固定 W 当 b T时 0 这时达到最小值 0 0 min 693 0 limNEE b 设用 b T时间传送 1bit 信息 由 Shannon 公式 0 log11 b Tb S CT W N W bit 得到 WN S WTb 0 1log 1 当4000 0 WN S 时 由于 bb TES 所以 0 5 0 5 0 5 0 5 0 1 2 0 1 Y X 0 5 0 5 0 5 0 5 0 1 1 a a 1 0 Y X WN S N WTNE bb 0 0 0 1log 4000 4000 因此 482 4001log 693 0 4000 0 0 min N N E Eb 4 11 信道输入 输出在实数轴上取值 即 R YXZ Z 为 0 5 0 5 上均匀分 布随机变量 X 的峰值限制为 X 为正整数 求证信道容量为 log 21 C 证明证明 Y 均匀取值为 0 5 0 5 时 H Y有最大值 I X YH YH YX 0 50 5 0 50 5 1 21 log 1 21 log 21 H YZ kogdxdx 即 log 21 C 4 12 有一个叠加噪声的信道 输入 X 是离散随机变量 取值为 1 1 噪声 N 的概率密度 为 1 2 4 0 N n P n n 2 Y 1 X 信道输出 Y X Z 是连续随机变量 求 1 该半连续信道容量 max p x CI X 2 若在信道输出上接一个检测器作为这个信道的一部分 检测器输出变量为 11 01 11 Y ZY Y 输出 mod2YXZ 试求 1 a 时的信道容量 2 a 时的信道容量 解解 max max CI X YH YH YX 令 则 YXZ mod2YY 则使X Y 互信息最大与的互信息X Y 最大是等效的 而Y的输出范围为 aa H Y log 22 log 2 log I X YH YH YX H Z aa a a 不等式成立的条件是 为均匀分布 即 Y 1 2 p ya ya a 1 a 时 1 2 0 2 1 y2 ayaay p y aa X 即此时 max CH YH Y 2 0 max 11 log 2 log 2 2 2 11 log 2 log 2 2 2 log2 log log2 a a aa aa H YH Z a dxa dx aa a dxa dx aa aa aaa aa 2 a 时 3 2 0 32 1 3 ayaay p y aaya X 则 max CH YH Y 2 03 3 max 33 log 2 3 log 2 3 2 2 11 log log 2 2 3 2 42 loglog log2 3 a a aa aa H YH Z adxad aa a dxa dx aa aaa aa aa x 4 15 题的解答需要补充下面的知识 信息论与编码 补充材料 熵功率不等式的证明 在信息论中熵功率不等式具有非常重要的应用 然后证明是非常繁琐 下面我们给 出它的述叙和证明 设 X Y 为另均值独立随机变量 Z X Y 2 X 2 Y 2 Z 为 X Y Z 的功率 方差 相应的熵功率为 2 X 2 Y 2 Z 则有如下不等式成立 22222 YXZYX 1 当 X Y 为正态分布时 上式中的等号成立 随机变量 X 的熵功率定义为 22 2 1 Xh X e e 显然 1 式的右边不等式非常易证明 因为 X 和 Y 独立 所以 222 YXZ 由于熵功率不会大于功率 所以 2222 YXZZ 所以关键是证明 1 式的左边 为此证明如下三条引理 引理 1 令 0 fNXX f 其中X 的分布密度为 xp 0 fN为零均值 方 差为f的正态分布随机变量 则 f f f ff p dx x p df Xdh 2 2 1 2 其中 f p为 f X的概率分布密度 证明 由于 0 fNXX f 所以 dx f xx xp f xp f ff 2 exp 2 1 2 3 对 3 式中f求导得到 2 2 2 1 f ffff x xp f xp 4 由 3 式可知 f xp ff 2 1 f X的微分熵为 ffffff dxxpxpXh log 对 f Xh求关于f的导数得 ff f f ff dxp f p dx f p df Xdh log ff f a dxp f p log0 ff f ff dxp x xp log 2 1 2 2 f f f f f f f p dx x p p x p 2 2 1 log 2 1 f f f f b p dx x p 2 2 1 0 其中 a 由于 f f ff f f dx x xp dx f p 2 2 2 1 f ff x xp 2 1 0 b 因为 dx f xx xxxp f x p f f f f 2 exp 2 1 2 3 由 Schwarz 不等式 2 4 5 2 4 2 2 2 4 exp 2 4 exp dx f f xx xxxp f f xx xp x p f f f f f dx f xx xxxp f p f f f 2 exp 2 2 2 5 e p f f c 3 2 5 c 由于 e f f xx xx f f 2 2 exp 2 2 由 5 式 当 f x 0 f p f f p f p 0 所以0log f f f p x p 从而证明了 f f f ff p dx x p df Xdh 2 2 1 Q E D 对任何分布密度为 xp的随机变量 记 p dx x p p p EXJ 2 2 6 则引理 1 可表示为 f f XJ df XdH 2 1 7 引理 2 X Y 为独立随机变量 YXZ 则 YJYJZJ 111 8 证明 设 X Y 的分布密度分别为 xp yq 则 Z 的分布密度为 dxxzqxpzr 所以 dxxzqxpzr dxxzqxp 因而 dx xp xp zr xzqxp zr zr z xp xp E 其中 z xp xp E 表示在给定 z 条件下的条件期定 同样可得到 z yq yq E zr zr 于是 zr zr baz yq yq b xp xp aE 因而 2 2 2 z yq yq b xp xp aE zr zr ba z yq yq b xp xp aE 2 9 当 zr zr ba yq yq b xp xp a 10 以概率 1 成立时 9 式的等号才成立 而当 X Y 为正态分布时 10 式以概率 1 成 立 所以当 X Y 为正态分布时 9 式的等号成立 9 式二边对 Z 求平均 得到 22 2 rzpxqy abEEab r zp xq y 22 22 pxqy a Eb E p xq y 即 YbJXJaZJba 2 令 XJ a 1 YJ b 1 得到 YJXJZJ 111 Q E D 引理 3 令 tfNXX f 0 tgNYYg 0 其中 X Y 0 tfN和 0 tgN为独立随机变量 tgN 0 0tfN为零均值 方差分别为 tg和 tf 的正态分布 0 lfg ZXYXYNl t 其中 l tf tg t 记 exp 2exp 2 exp 2 fg l h Xh Y s t h Z 11 则 10 s 证明 式 1 1 二边对 t 求导得 2 2 2 fg l Xh Y h Z h fg es teftJ Xeg tJ Y 2 2 fg Xh Y h l eef tg tJ Z 代入不等式 8 得 22 2 fg l h Xh Y fgfg h Z fg ftJ Xg tJ YeJ XeJ Y es t J XJ Y 12 置 2 f h X fte 13a 2 g h Y g te 13b 则 0s t 所以 0ss 下面证明 1 s 由 13a 和 13b 可知 fgl 定义 f X X f F 则 duuxufpfxP FFF 2 2 1 exp 2 1 fXhXh fF log 2 1 当 f时 uufff 所