信息论与编码复习总结.pdf

信息论与编码理论复习资料信息论与编码理论复习资料 By 疯狂阿德 第一章 绪论 考点 信息 消息 信号的区别 通信系统模型 香农 1 信息 消息 信号的区别 信息 指事物运动的状态或存在方式的不确定性的描述 消息 包含信息的语言 文字 图像等 信号 信息的物理体现 在通信系统中 实际传输的是信号 但实质内容是信息 信息包含在信号中 信号是信息 的载体 通信的结果是消除或部分消除不确定性 从而获得信息 2 通信系统模型 通信系统模型 信源 信息输出的源 分离散信源和模拟信源 信宿 信息归宿之意 意即收信者或用户 是信息传送的终点或目的地 信道 传送信息的物理媒介 密钥源 产生密钥 k 的源 信号 x 经过 k 的加密运算后 就把明文 x 变换为密文 y 一般地说 通信系统的性能指标主要是有效性 可靠性 安全性和经济性 除了经济性外 这些指标正是信息论的研究对象 信源编码 信源编码器的作用 一 将信源发出的信息变换成基带信号 二 压缩冗余度 提高效率 有效性 信道编码 在信源编码器输出的代码组上有目的地增加一些监督码元 使之具有检错和纠 错能力 信道译码器具有检错和纠错能力 它能将在其检错或纠错能力范围内的错传码元 检测出来并加以纠正 以提高传输信息的可靠性 信道编码包括调制解调和纠错检错编译 码 信道中的干扰通常使通信质量下降 对于模拟信号 表现在受到的信号的信噪比下降 对于数字信号就是误码率增大 信道编码的主要方法是增大码率或频带 即增大所需的信 道容量 这恰与信源编码相反 3 香农 他在 1941 年至 1944 年对通信和密码进行深入研究 并用概率论的方法研究通信系统 揭示了通信系统传递的对象就是信息 并对信息给以科学的定量描述 提出了信息熵的概 念 还指出通信系统的中心问题是在噪声下如何有效而可靠地传送信息 而实现这一目标 的主要方法是编码等 这一成果于 1948 年在 贝尔系统技术杂志 以 通信的数学理论 为题公开发表 次年 他又在同一杂志上发表了 噪声下的通信 香农因此成为信息论的 奠基人 简答题 一 信源编码与信道编码的区别 答 信源编码是压缩信源发出的信息的冗余度 是为了提高信息传输的有效性 而信 道编码是在信源编码器输出的代码组上有目的地增加了一些监督码元 增大了信息的 冗余度 以提高传输信息的可靠性 二 能否将三种码 信源编码 信道编码 密码 合成一种码进行编译 答 提高有效性必须去掉信源符号中的冗余部分 此时信道误码会使接收端不能恢复原 来的信息 也就是必须相应提高传送的可靠性 不然会使通信质量下降 反之 为了可靠而采用信道编码 往往需扩大码率 也就降低了有效性 安全性也有 类似情况 编成密码 有时需扩展码位 这样就降低有效性 有时也会因失真而使授权用户无法 获得信息 必须重发而降低有效性 或丢失信息而降低可靠性 从理论方面来说 若能把三种码合并成一种码来编译 即同时考虑有效 可靠和安全 可使编译码器更理想化 在经济上可能也更优越 这种三码合一的设想是当前众所关心的课题 但因理论上和技术上的复杂性 要 取得有用的结果 还是相当困难 第二章 信源与信息熵 考点 自信息 概率空间 样本空间 某事物各种可能出现的不同状态 先验概率 p xi 选择符号 xi作为消息的概率 对 xi 的不确定性可表示为先验概率 p xi 的倒数的某一函数 自信息 后验概率 p xi yj 接收端收到消息 yj后而发送端发的是 xi 的概率 设离散信源 X 其概率空间为 如果知道事件 xi已发生 则该事件所含有的信息量定义为 I xi 含义 当事件 xi发生以前 表示事件 xi 发生的不确定性 当事件 xi发生以后 表示事件 xi所含有的信息量 I xi 的特性 21 21 n n xpxpxp xxx P X log ii xpxI 21 21 n n xpxpxp xxx P X 1 log i i xP xI 1 log 1 log jii ji yxpxP yxI I xi 是非负值 当 p xi 1 时 I xi 0 当 p xi 0 时 I xi I xi 是先验概率 p xi 的单调递减函数 即 当 p x1 p x2 时 I x1 I x2 两个独立事件的联合信息量等于它们分别的信息量之和 即统计独立信源的信息量等于它们分别的信息量之和 一个出现概率接近于 1 的随机事件 发生的可能性很大 所以它包含的不确定度就很 小 一个出现概率很小的随机事件 很难猜测在某个时刻它能否发生 所以它包含的不确 定度就很大 若是确定性事件 出现概率为 1 则它包含的不确定度为 0 联合自信息量 两个消息 xi yj同时出现的联合自信息量 注意 当 xi yj相互独立时 有 p xiyj p xi p yj 那么就有 I xiyj I xi I yj xiyj所包含的不确定度在数值上也等于它们的自信息量 条件自信息量 在事件 yj出现的条件下 随机事件 xi发生的条件概率为 p xi yj 则它的条件自信息量定 义为条件概率对数的负值 信源 产生消息 符号 消息序列和连续消息的来源 产生随机变量 随机序列和随机过程的源 log jiji yxpyxI log jiji yxpyxI 在通信系统中收信者在未收到消息以前对信源发出什么消息是不确定的 是随机 的 所以可用随机变量 随机序列或随机过程来描述信源输出的消息 或者说用 一个样本空间及其概率测度 概率空间来描述信源 信源的基本特性 具有随机不确定性 香农信息论的基本点 一 用随机变量和随机矢量来表示信源 二 用概率论和随机过程来研究信息 信源的分类 连续信源 指发出在时间和幅度上都是连续的消息 模拟消息 的信源 离散信源 指发出在时间和幅度上都是离散分布的离散消息的信源 离散无记忆信源 所发出的各个符号是相互独立的 发出的符号序列中的各个符号之间没 有统计关联性 各个符号的出现概率是它自身的先验概率 发出单个符号的信源 指信源每次只发出一个符号代表一个消息 发出符号序列的信源 指信源每次发出一组含二个以上符号的符号序列代表一个消息 信源的描述 6 16 16 16 16 16 1 654321 xxxxxx P X 离散有记忆信源 所发出的各个符号的概率是有关联的 发出符号信源的有记忆信源 用信源发出的一个符号序列的整体概率 即联合概率 反映有 记忆信源的特征 发出符号序列的马尔可夫信源 一个符号出现的概率只与前面一个或有限个符号有关 而不 依赖更前面的那些符号 不确定度 定义 随机事件的不确定度在数量上等于它的自信息量 两者的单位相同 但含义却不相同 具有某种概率分布的随机事件不管发生与否 都存在不确定度 不确定度表征了该事件的特性 而自信息量是在该事件发生后给予观察者的信息量 平均自信息 平均不确定度 信源熵 公式一定要记住 H X 平均信息量 称为信源 X 的熵 信源熵 香农熵 离散信源熵 H X 平均不确定度 平均信息量 平均自信息量 定义 信源的平均不确定度 H X 为信源中各个符号不确定度的数学期望 即 单位为比特 符号或比特 符号序列 信息熵 从平均意义上来表征信源的总体信息测度的一个量 自信息 指某一信源发出某一消息所含有的信息量 所发出的消息不同 它们所含有的信息量也就不同 自信息 I xi 是一个随机变量 不能用它来作为整个信源的信息测度 信源熵具有以下三种物理含意 信息熵 H X 表示信源输出后 每个离散消息所提供的平均信息量 信息熵 H X 表示信源输出前 信源的平均不确定性 信息熵 H X 反映了变量 X 的随机性 条件熵 H x y H x Y 在给定 yj条件下 xi的条件自信息量为 I xi yj X 集合的条件熵 H X yj 为 i ii i ii xpxpxIxpXH log ji i jij yxIyxpyXH 在给定 Y 即各个 yj 条件下 X 集合的条件熵 H X Y 条件熵是在联合符号集合 X Y 上的条件自信息量的联合概率加权统计平均值 条件熵 H X Y 表示已知 Y 后 X 的不确定度 相应地 在给定 X 即各个 xi 条件下 Y 集合的条件熵 H Y X 定义为 联合熵 H X Y H X Y H X H Y X 联合熵是联合符号集合 X Y 上的每个元素对 xi yj 的自信息量的概率加权统计平均值 联合熵 H X Y 表示 X 和 Y 同时发生的不确定度 H XY 与与 H X H X Y 之间的关系之间的关系 H X Y H X H Y X H X Y H Y H X Y 单符号序列 马尔科夫信源 m 阶马尔科夫信源 了解 马尔科夫信源 一类相对简单的离散平稳信源 该信源在某一时刻发出字母的概率除与该 信源有关外 只与此前发出的有限个字母有关 ji ij ji jiji ij jj j j yxIyxp yxIyxpypyXHypYXH log ij ij ji ij ij ji xypyxp xyIyxpXYH log ji ij ji ji ij ji yxpyxp yxIyxpYXH m 阶马尔科夫信源 信源输出的某一符号的概率只与以前的 m 个符号有关 而与更前面的 符号无关 马氏链的基本概念 一阶马尔科夫信源 若把有限个字母记作一个状态 S 则信源发出某一字母的概率除与该字母有关外 只与该时刻信源所处的状态有关 信源将来的状态及其送出的字母将只与信源现在的状态有关 而与信源过去的状 态无关 令 si xi1 xi2 xim xi1 xi2 xim a1 a2 an 状态集 S s1 s2 sQ Q nm 信源输出的随机符号序列为 x1 x2 x i 1 x i 信源所处的随机状态序列为 s1 s2 si 1 si 例 二元序列为 01011100 考虑 m 2 Q nm 22 4 s1 00 s2 01 s3 10 s4 11 变换成对应的状态序列为 s2 s3 s2 s4 s4 s3 s1 状态转移图 状态转移概率 设信源在时刻 m 处于 si状态 它在下一时刻 m 1 状态转移到 sj的转移概率为 pij m p Sm 1 sj Sm si p sj si pij m 基本转移概率 一步转移概率 若 pij m 与 m 的取值无关 则称为齐次马尔可夫链 pij p Sm 1 sj Sm si p S2 sj S1 si pij具有下列性质 pij 0 若信源处于某一状态 si 当它发出一个符号后 所处状态就变了 任何时候信源处于 什么状态完全由前一时刻的状态和发出符号决定 系统在任一时刻可处于状态空间 S s1 s2 sQ 中的任意一个状态 状态转移时 转移概率矩阵 符号条件概率矩阵 121121 321 LLLL L xxpxxpxxpxp xxxxp j ij p1 QQQ Q ij pp pp sspP 1 111 QnQ n ij pp pp sxpP 1 111 符号条件概率到状态转移概率的转换 如在状态 01 时 出现符号 0 则将 0 加到状态 01的 后面 再将第一位符号 0 挤出 转移到状态 10 互信息 I X Y 定义为 xi的后验概率与先验概率比值的对数 互信息 I xi yj 表示接收到某消息 yj后获得的关于事件 xi的信息量 平均互信息定义 Y 未知 X 的不确定度为 H X Y 已知 X 的不确定度变为 H X Y 信息 先验不确定性 后验不确定性 不确定性减少的量 条件互信息条件互信息 我们定义在已知事件 zk的条件下 接收到 yj后获得关于某事件 xi的条件互信息 平均互信息与各类熵的关系平均互信息与各类熵的关系 log 2 i ji ji xp yxp yxI log log log j ij ji ji i ji ji yp xyp ypxp yxp xp yxp yxI ijjjiiji xyIyIyxIxIyxI YXHXHYXI log log log kjki kji kj kij ki kji kji zypzxp zyxp zyp zxyp zxp zyxp zyxI 熵只是平均不确定性的描述 不确定性的消除 两熵之差 才等于接收端所获得的信息量 获得的信息量不应该和不确定性混为一谈 维拉图维拉图 H X Y 信道疑义度 损失熵 信源符号通过有噪信道传输后所引起的信息量的损失 信源 X 的熵等于接收到的信息量加上损失掉的信息量 H Y X 噪声熵 散布熵 它反映了信道中噪声源的不确定性 输出端信源 Y 的熵 H Y 等于接收到关于 X 的信息量 I X Y 加上 H Y X 这完全是由于信 道中噪声引起的 收发两端的熵关系收发两端的熵关系 XYHYHXH XYHYH YXHXHYXI YHXHXYH YXHYHXYHXHXYH 离散序列信源熵 简单 当信源无记忆时 信源的序列熵 若又满足平稳特性 即与序号 l 无关时 信源的序列熵 平均每个符号 消息 熵为 连续信源熵 无穷大 简单考 冗余度 冗余度 多余度 剩余度 表示信源在实际发出消息时所包含的多余信息 冗余度 信源符号间的相关性 相关程度越大 信源的实际熵越小 信源符号分布的不均匀性 等概率分布时信源熵最大 对于有记忆信源 极限熵为 H X 这就是说我们需要传送这一信源的信息 理论上只需要传送 H X 即可 但必须掌握信源全 部概率统计特性 这显然是不现实的 实际上 只能算出 Hm X 那么与理论极限值相比 就要多传送 Hm X H X 为了定量地描述信源的有效性 定义 L l iiiii iii lL L xpxpxpxpxp xxxpp 1 321 21 X L l l i L l ii n i ii XHxpxp xpxpH ll L log log 1 X L L l i pxpp l 1 X XLHH X 1 XHH L HL XX 数据处理定理 了解 数据处理定理 当消息通过多级处理器时 随着处理器数目增多 输入消息与输出消息间的平均互信息 量趋于变小 数据处理定理说明 当对信号 数据或消息进行多级处理时 每处理一次 就有可能损失一部分信息 也就是说数据处理会把信号 数据或消息变成更有用的形式 但是绝不会创造 出新的信息 这就是所谓的信息不增原理 计算偏多 概念较少 第三章 信道与信道容量 考点 信道容量 信道容量 C 最大的信息传输率 单位时间的信道容量 无噪无损等特殊信道容量 对于一般信道 信道容量计算相当复杂 我们只讨论某些特殊类型的信道 离散信道可分成 无干扰 无噪 信道 无噪无损信道 有噪无损信道 无噪有损信道 有干扰无记忆信道 有干扰有记忆信道 无噪无损信道无噪无损信道 输入和输出符号之间有确定的一一对应一一对应关系 max YXIC i ap max 1 YXI T C i ap 3 2 1 1 0 ji ji ji bapabp jiij 噪声熵 H Y X 0 损失熵 H X Y 0 无噪有损信道无噪有损信道 多个输入变成一个输出 n m YHXHYXI nYXIC i ap 2 log max 有噪无损信道有噪无损信道 一个输入对应多个输出 n m 接收到符号 Y 后 对发送的 X 符号是完全确定的 噪声熵 H Y X 0 损失熵 H X Y 0 对称信道 XHYHYXI max max YHYXIC i ap YHXHYXI max max XHYXIC i ap 对称离散信道 对称性 每一行都是由同一集 q1 q2 qm 的诸元素不同排列组成 输入对称 每一列都是由 p1 p2 pn 集的诸元素不同排列组成 输出对称 信道矩阵 若输入符号和输出符号个数相同 都等于 n 且信道矩阵为 此信道称为强对称信道 均匀信道 信道矩阵中各列之和也等于 1 p n p n p n p p n p n p n p p P 1 11 1 1 1 11 1 2 1 3 1 6 1 6 1 2 1 3 1 3 1 6 1 2 1 3 1 3 1 6 1 6 1 6 1 6 1 3 1 3 1 PP 7 0 1 0 1 0 2 0 2 0 7 0 3 1 6 1 3 1 6 1 6 1 6 1 3 1 3 1 PP 对称信道对称信道 H Y H WP W P 1 log 1 log ppH pp pp pp ppYH H Y X H p I X Y 1 H p 容量公式 串联信道 loglog log log pHpppp abpabp abpabpapXYH ij j ij ij ij iji 1 pH pHppHXYHYHYXI 准对称信道 会算 一般 DMC 不管 准对称信道 转移概率矩阵 P 是输入对称而输出不对称 将信道矩阵 P 的列划分成若干个互不相交的子集 mk 由 mk为列组成的矩阵 P k是对称矩 阵 它们满足对称性 所以 P1所对应的信道为准对称信道 准对称信道 6 1 6 1 3 1 3 1 3 1 6 1 6 1 3 1 3 1 6 1 3 1 6 1 6 1 6 1 3 1 3 1 1 P 1 0 1 0 7 02 0 2 07 0 7 0 1 0 1 0 2 0 2 0 7 0 2 P 第四章 信息率失真函数 考点 失真矩阵 信道矩阵 失真函数 d xi yj 描述失真大小的函数 失真矩阵 将所有的 d xi yj 排列起来 用矩阵表示为 ji ji ji yx yx yxd 0 0 1 111 mnn m badbad badbad d 平均矩阵 将失真函数的数学期望称为平均失真 第五章 信源编码 j jiiji i badabpapD 考点 定长编码优缺点 各种编码 同等重要 算术编码 考的不难 例题 思想核心 编码的定义 编码的定义还需要看课本 光看 PPT 有点看不懂 克劳夫特不等式 m 是进制数 n 是信源符号数 P80 该不等式是惟一可译码存在的充要条件 而不是惟一可译码的充要条件 话说这 句话还着实让我纠结了好一阵 后来在打算在群上求助的时候突然发现前半句比后半句多 出个 存在 好吧 定长编码优缺点 优点 只要 这种编码器一定可以做到几乎无失真 也就是收端的译码 差错概率接近于零 条件是所取的符号数 L 足够大 缺点 定长编码的信息传输效率极低 编码长度很长 效率低 信源编码与信道编码的区别 信源编码 以提高通信有效性为目的的编码 通常通过压缩信源的冗余度来实现 采用的一般方法是压缩每个信源符号的平 均比特数或信源的码率 即同样多的信息用较少的码率传送 使单位时间内传送 的平均信息量增加 从而提高通信的有效性 信道编码 是以提高信息传输的可靠性为目的的编码 通常通过增加信源的冗余度来实现 采用的一般方法是增大码率 带宽 与信源 编码正好相反 1 1 n i Ki m XHK L 码字平均长度 信息率 编码效率 最佳码 对于某一信源和某一码符号集来说 若有一唯一可译码 其平均码长小于所有其 他唯一可译码的平均长度 紧致码 香农 Shannon 费诺 Fano 哈夫曼 Huffma 香农编码 香农第一定理指出 选择每个码字的长度 Ki满足下式 或 log2 p xi Ki 1 log2 p xi 就可以得到这种码 这种编码方法称为香农编码 二进制香农码的编码步骤如下 将信源符号按概率从大到小的顺序排列 p a1 p a2 p an 确定满足下列不等式的整数 Ki log2 p ai Ki 1 log2 p ai n i ii KapK 1 m L K R L log R XH 用 Pi表示第 i 个码字的累加概率 将 Pi用二进制表示 并取小数点后 Ki位作为符号 ai的编码 看 PPT 香农编码例题 费诺编码 费诺编码属于概率匹配编码 编码步骤如下 将概率按