信息论与编码

教材：信息论基础教程（第3版） 李梅 北京邮电大学出版社。信息论与编码知识点梳理，包括信息的度量、信源及信源熵、信道及信道容量、无失真信源编码、有噪信道编码等。适用于通信、电子信息等专业的学生。

信息论与编码

• 第1章：绪论
  • 信息的概念
  • 信息论的研究对象、目的和内容
• 第2章：信息的度量
  • 1. 自信息和互信息
    • 1.1. 自信息
      • 定义
        • 该事件发生概率的对数的负值
      • 例
    • 1.2. 互信息
      • 通信系统模型
        • 设X为信源发出的离散消息集合；Y为信宿收到的离散消息集合
        • 信源发出的消息，经过有噪声的信道传递到信宿
        • 先验概率：信源发出消息xi的概率p(xi)
        • 后验概率：信宿收到消息yj后推测信源发出xi的概率，即条件概率
      • 互信息定义
        • • 含义1：表示事件yj出现前后关于事件xi的不确定性减少的量
          • 含义2：事件yj出现后信宿获得的关于事件xi的信息量
      • 讨论p
        • 1. 统计独立，即
          • 则
        • 2. 大小关系
          • 若
            • 则
          • 若
            • 则
        • 3. 若
      • 例
        • 算先验后验概率，再求比值取对数
  • 2. 平均自信息
    • 2.1. 平均自信息
      • 自信息：随机变量，指信源发出的某一消息所含有的信息量。不同的消息，它们所含有的信息量也就不同。
      • 平均自信息（信息熵/信源熵/香农熵/无条件熵/熵函数/熵）
      • 信息熵的单位
        • 以2为底，单位为比特/符号
        • 以e为底，单位为奈特/符号
        • 以10为底，单位为哈特莱/符号
      • 信息熵的意义
        • 信源的信息熵是从整个信源的统计特性来考虑的
        • 它是从平均意义上来表征信源的总体特性的
        • 对于某特定的信源，其信息熵只有一个
        • 不同的信源因统计特性不同，其信息熵也不同
      • 概率空间
        • 一个随机变量的样本空间和样本空间中的元素对应的概率
        • 例
    • 2.2. 熵函数的性质
      • 1. 对称性
        • • 熵只与随机变量(信源)的总体统计特性有关
          • 如果某些信源的统计特性相同（含有的符号数和概率分布相同），那么这些信源的熵就相同
      • 2. 确定性
        • H(1,0)=H(1,0,0)=H(1,0,0,0)=…=H(1,0, …,0)=0
        • 证明
          • 定性分析：在概率空间中，只要有一个事件是必然事件，那么其它事件一定是不可能事件，因此信源没有不确定性，熵必为0
          • 定量：...
      • 3. 非负性
        • 证明
        • 离散信源的熵满足非负性，而连续信源的熵可能为负。
      • 4. 扩展性
        • 增加一个概率接近于零的事件，信源熵保持不变
      • 5. 连续性
        • 信源概率空间中概率分量的微小波动，不会引起熵的变化
      • 6. 递增性 （递推性）
        • • 证明
        • 例
      • 7. 上凸性
        • 熵函数上凸性定义
        • 补充
          • 凸函数 （对一元函数）
            • 定义
            • 证明f(x)是上凸函数
              • 1. 满足定义式
              • 2. f' (x) 单调递减
              • 3. f''(x)≤0
              • 满足其一即可
          • Jensen不等式
            • 定义
            • 证明：数学归纳法
          • 香农辅助定理
            • 定义
            • 证明
          • 上凸性几何意义
            • • 在上凸函数的任两点之间画一条割线，函数总在割线的上方.
              • 上凸函数在定义域内的极值必为最大值，这对求最大熵很有用
        • 熵函数上凸性证明
      • 8. 极值性 （最大离散熵定理）
        • 定义
        • 证明：条件极值
    • 2.3. 联合熵与条件熵
      • 随机变量X和Y的联合分布为p(xiyj)，则这两个随机变量的联合熵定义为
        • • 联合熵表示对于二维随机变量的平均不确定性
      • 随机变量X和Y的条件熵定义为
        • 条件熵表示已知一个随机变量时，对另一个随机变量的平均不确定性
        • • 注意第一行log前后括号内不一样
      • 总结
      • 例
      • 各种熵之间的关系
        • H(XY)=H(X)+H(Y|X)=H(Y)+H(X|Y)
        • 推导照片
        • 不等式证明：小-大，利用log上凸性
  • 3. 平均互信息
    • 3.1. 平均互信息的概念
      • 平均交互信息量/交互熵
      • 平均互信息与各类熵的关系
    • 3.2. 平均互信息的性质
    • 3.3. 数据处理定理
      • 平均条件互信息
      • 平均联合互信息
        • 关系
      • 数据处理定理
        • 定理
          • 如果随机变量 X，Y，Z 构成一个马尔可夫链，则有以下关系成立：
          • 等号成立的条件分别是对于任意的 x，y，z
• 第3章：信源及信源熵
  • 信源的分类及其数学模型
    • 信源：消息（符号）、消息序列（符号序列）以及时间连续的消息的来源
    • 信源的主要问题
      • 如何描述信源的输出（信源的建模问题）
      • 怎样确定信源产生的信息量、产生信息的速率
      • 信源编码 （第五章）
    • 分类
      • 根据信源发出的消息序列中的消息，统计特性是否保持不变
        • 平稳信源
        • 非平稳信源
      • 根据信源发出的单个消息取值是离散值还是连续值
        • 离散信源
        • 连续信源
      • 根据信源发出的消息之间是否有统计依赖关系
        • 记忆信源
          • 马尔可夫信源
        • 无记忆信源
  • 离散单符号信源
    • 定义：输出离散取值的单个符号的信源
    • 离散单符号信源 的概率空间
    • 信源的平均自信息（信息熵）
      • 表示离散单符号信源的平均不确定性
  • 离散多符号信源
    • 预备知识
      • 定义：实际信源输出往往是符号序列，称为离散多符号信源
      • 离散多符号信源可以用随机矢量/随机变量序列来描述
      • 平均符号熵
        • 极限熵
    • 离散平稳无记忆信源
    • 离散平稳有记忆信源
    • 马尔可夫信源
      • 引入：青蛙跳荷叶
      • 定义
        • 马尔可夫信源是一类相对简单的有记忆信源。信源在某一时刻发出某一符号的概率，除与该符号有关外，只与此前发出的有限个符号有关。
      • 熵率
      • 马尔科夫链
        • • 有限状态马尔可夫链
            • 状态空间 S={s1,s2,⋯,sj }有限
          • 可数无穷状态的马尔可夫链
            • 状态空间S={s1,s2,⋯}是无穷集合
        • 状态转移概率
          • 描述马氏链最重要的参数
          • • 经过n-m步，状态从si转变到sj
          • 性质
          • 一步转移概率
          • k步转移概率
        • 齐次马尔科夫链
          • 时齐马尔可夫链/齐次马尔科夫链/具有平稳转移概率的马尔可夫链
          • 定义：马氏链状态转移概率与起始时刻无关，即对任意m有
          • pij：当前是i，下一步j，一步转移概率，与时间无关（常用）
          • 转移概率矩阵描述
            • • p12：当前状态1，向状态2转变的概率
          • 状态转移图描述
        • 由条件概率到状态转移概率
          • 例
            • ？
      • 性质
        • 遍历性
          • 也称各态历经性
          • 若干时刻后，其他各个状态都有可能到达
          • 稳定的马尔科夫信源一定具有各态历经性
          • 推论
        • 矩阵计算
          • • W^(0)：初始时刻处于各个状态概率（一行j列）
            • W^(1)：走一步后处于各个状态概率（一行j列）
            • P：状态转移矩阵，j行j列
            • n个P相乘，随着n变大，P内各个元素越来越接近，最终得到稳定的状态分布
              • 推导（以第一列为例）
        • 定理1
          • 可以用过状态转移概率来求稳定的状态分布
          • （走200步和走201步没区别）
        • 定理2
          • 若存在有限大小的正整数n，使得p^n的所有矩阵元素都不为0，则该马尔科夫链存在稳定的状态分布
    • 信源的相关性和剩余度
  • 连续信源
• 第4章：信道及信道容量
  • 信道分类
    • 1. 按输入/输出信号的幅度和时间特性
    • 2. 按输入/输出之间的记忆性
      • 无记忆信道
        • 信道在某时刻的输出只与信道该时刻的输入有关而与信道其他时刻的输入、输出无关
      • 有记忆信道
    • 3. 根据信道的输入/输出是否是确定关系
      • 有噪声信道
      • 无噪声信道
    • 4. 根据信道的统计特性是否随时间改变
      • 平稳信道
        • 恒参信道、时不变信道，如卫星通信
      • 非平稳信道
        • 变参信道、时变信道，如移动通信
    • 5. 根据输入/输出的个数
      • 单用户信道
      • 多用户信道
  • 离散单符号信道及其信道容量
    • 1. 离散单符号信道的数学模型
      • 信道的数学模型为{X, P(Y|X),Y}
      • 例
        • 二元对称信道
        • 二元删除信道
      • 离散信道常用的概率关系
        • 联合概率
        • 输出符号概率
        • 后验概率
      • 信道疑义度H(X|Y)
      • 平均互信息
      • 例
      • 后验熵：条件熵的“条件”（如H(X|Y)的Y）取特定值
    • 2. 信道容量的概念
      • 信息传输率R：即平均互信息I
      • 信息传输速率Rt：I/t
      • 信道容量C：I的最大值
        • 相应的输入概率分布被称为最佳输入分布
      • 例
        • 信道矩阵：即先验概率矩阵
    • 3. 几种特殊信道的信道容量
      • 无损信道
        • 有噪无损信道，一个输入对应多个输出
        • 先验概率P(Y|X)
          • 如p(x1|y1)=1，p(x2|y1)=p(x3|y1)=0，即输出y1只有可能是输入x1
          • • 后验概率非0即1，则损失熵为0
        • 后验概率、联合概率
      • 无噪信道
        • 无噪有损信道，它是一个输出对应多个输入
        • 先验概率P(Y|X)
          • • 先验概率非0即1
      • 无噪无损信道
        • 输入输出一一对应（交叉一下看起来更有一般性）
        • 先验概率P(Y|X)
    • 4. 离散对称信道的信道容量
      • 定义
        • 行对称信道
          • 信道矩阵P中每行都是第一行的排列
        • 对称信道
          • 信道矩阵中每行都是第一行的排列，并且每列都是第一列的排列
        • 准对称信道
          • 虽然不是对称信道，但是信道矩阵可以按列分为一些对称的子阵
            • 此知识点以后4567条，除两个输入，都不考
        • 强对称信道
          • （略）
      • 定理
        • 对称信道当输出概率分布为等概的情况下达到信道容量
    • 5. 一般离散信道的信道容量
      • 信道容量
      • 约束条件
      • 求信道容量即求I(X;Y)对信源概率分布P(X)的条件极值
      • 由β求C
      • 例
        • 四个输入
        • 两个输入：单一变量，直接求导
    • 6. 信道容量定理
      • I(X;Y) 达到信道容量的充要条件是输入分布 p(xi) 满足：
    • 7. 信道容量的迭代算法
      • 计算机运算
  • 离散多符号信道及其信道容量
    • 离散多符号信道
      • 离散无记忆信道 (DMC, discrete memoryless channel)
        • 定义：在任意时刻信道的输出只与此时刻信道的输入有关，而与其他时刻的输入和输出无关
        • 输入、输出随机序列的长度为 的离散无记忆平稳信道通常称为离散无记忆信道的N次扩展信道
      • 多符号：以矢量形式表示
      • 定理
        • 联合起来的平均互信息，小于等于各个时刻平均互信息的和
        • 信源也无记忆时，等号成立
    • 独立并联信道
    • 级联信道
  • 组合信道
  • 连续信道
  • 波形信道
• 第5章：无失真信源编码
  • 信源编码的相关概念
    • 信源的统计剩余度与什么因素有关
      • 无记忆信源中，符号概率分布的非均匀性
      • 有记忆信源中，符号间的相关性及符号概率分布的非均匀性
    • 信源编码器模型
    • N次扩展码
    • 奇异性
      • 若一个码中所有码字互不相同，则称为非奇异码；否则为奇异码
        • （都一样就是奇异码）
    • 唯一可译性
      • 若任意一串有限长的码符号序列只能被唯一地译为对应的信源符号序列，则称此码为唯一可译码
      • 应当满足的条件
        • 码字与信源符号一一对应
      • 奇异码：一定不是唯一可译码
      • 非奇异码：要求等长，才是唯一可译码
        • 非等长
        • 等长
    • 即时码
      • 某个唯一可译码在接收到一个完整的码字时无需参考后续的码符号就能立即译码
      • 唯一可译码成为即时码的充要条件
        • 其中任何一个码字都不是其他码字的前缀
      • 构造方法
        • • r=2（分支为2）
        • • 将所有的码字都安排在终端节点上就可以得到即时码
          • 每个中间节点都正好有r个分枝的树称为整树（满树）
          • 所有终端节点的阶数都相等的树为完全树
  • 定长码和定长信源编码定理
    • 唯一可译定长码存在的条件
      • • （必要不充分）
    • 定长信源编码定理
      • 编码信息率
      • 编码效率
        • • H(S)：离散无记忆信源的熵
          • N：信源的长
          • r：r种码元
          • l：码长
  • 变长码和变长信源编码定理
    • Kraft定理
      • 即时码存在的充要条件是
        • q：符号数
        • r：进制数
        • li：第i个码的码长
    • McMillan定理
      • 唯一可译码存在的充要条件是
    • 推导
      • n1：第一阶码元数量
    • 变长唯一可译码判别方法
      • 例
        • 方法：码字相互切割，构造新的尾随后缀
        • 结论：F5中包含了C中的元素，因此该变长码不是唯一可译码。
      • 停止条件
        • 尾随后缀没有新的码字
        • 没有新的尾随后缀出现了
    • 紧致码平均码长界限定理
      • 平均码长
        • • 码符号/信源符号
      • 紧致码/最佳码
        • 对于给定的信源和码符号集，若有一个唯一可译码，其平均长度 L 小于所有其他唯一可译码
        • 码长达下界，效率最高
      • 紧致码平均码长界限定理
    • 香农第一定理 （变长无失真信源编码定理）
      • 推广到一般离散信源
      • 信息传输率（码率）
      • 编码效率
        • • 换底公式可推
  • 变长码的编码方法
    • 香农码 (Shannon Code)
      • 编码步骤
      • 例
        • • S5码字：
    • 霍夫曼码 (Huffman Code)
      • 紧致码，最佳码
        • 压缩效率最高
      • 步骤
        • 1. 将符号按几率从大到小排列
        • 2. 把最小几率的两个符号合并（加一起）
        • 3. 上面的编码0，下面的编码1
      • 例
        • S：符号数目
        • q：原符号数目
        • r：缩减到r元编码
        • L：平均码长
      • 码字不是惟一的
        • 分配“0”或“1”码元是任意的
        • 若合并后的概率与其他概率相等，这几个概率的次序可任意排列
      • r元霍夫曼码：补上i个码元
        • • theta可调，正整数即可
        • 例
    • 费诺码 (Fano Code)
      • 编码步骤
    • 三种编码方法比较
      • 香农码唯一，霍夫曼码费诺码不唯一
      • 霍夫曼码最佳
    • 游程编码
      • 结尾码/组合基干码
    • 算术编码
      • 编码
        • • F(11)=F(1)+p(1)F(1)
        • • 码长，上取整
      • 译码
    • LZW编码
      • 编码
        • • 一旦形成新码字，就把除了最后一位之外的旧码字输出
      • 译码
        • 前面词条的全部+后面词条的第一个
          • 如：7(CB)，不是7(CBA)
  • 实用的无失真信源编码方法
• 第6章：有噪信道编码
  • 信道编码的相关概念
    • 概述
      • 目标：提高通信的可靠性
      • 信道编码：增加一些冗余信息，使其有数学规律
      • 信道译码：去掉冗余符号
    • 译码规则对错误概率的影响
    • 译码规则
    • 两种重要的译码规则
      • 最大后验概率 = 最小错误概率准则
        • 信道概率矩阵变成联合概率矩阵，然后在每一列中挑出最大的
          • p(x1)乘第一行，p(x2)乘第二行
        • 用PXY
      • 极大似然译码准则
        • 输入符号等概率时，与上一种准则等价
        • 用PY|X
    • Fano不等式
      • • 红点：PE最小值
    • 简单重复编码
      • 加监督元/校验元
        • 0变000，译码时001,010,100都译成000，实现自动纠正一位错误
      • 增加重复次数n，可使 减小很多，但信息传输率R也减少很多。
    • 汉明距离
      • 计算公式
        • • 相同位异或，然后相加（实际上就是有多少位不同）
        • 例
      • 码的最小距离
        • 在二元码C中，任意两个码字之间的汉明距离的最小值，被称为码C的最小距离
        • 例
  • 有噪信道编码定理
    • 香农第二定理
      • 设有一离散无记忆平稳信道，其信道容量为C，只要待传送的信息传输率R<C，当码长 n 足够大时，则至少存在一种编码，使译码错误概率任意小
    • 有噪信道编码逆定理
    • 结论
      • 信道容量是在信道中可靠传输信息的最大信息传输率
  • 纠错编码
    • 纠检错的工作方式
      • 1. 反馈重传(ARQ)
      • 2. 前向纠错(FEC)
      • 3. 混合纠错
    • 纠错码
      • 分类
        • 分组码
          • 线性码
            • 码字 = 校验元(监督元) + 信息元
            • 校验元与信息元呈线性关系
          • 非线性码
        • 树码
      • 基本概念
        • 汉明重量：非0位的个数
        • 线性分组码的封闭性：两个码字相加得到的结果依然属于线性分组码
        • 两个码字的汉明距离 = 一个码字（二者相加）的汉明重量
          • 相加，其实就是异或
        • (5,2)线性分组码
          • 生成矩阵G：编码
            • 前面是单位矩阵E
          • 监督矩阵H：译码
            • 传输无误
              • C：(许用)码字
            • 传输有误
              • R：传输端得到的码字
              • 若≠0，则R为禁用码字
              • 结论：
                • E=(0,0,1,0,0)
            • 伴随式译码
              • 例1
              • 例2
                • 错误图样E
                  • 挑选最小的E作译码，得到C_hat = R + E
                • C_hat矩阵不要求，挑最小的即可
      • 线性分组码
        • 1. 对于（n，k）线性分组码，设dmin为码的最小距离则
        • 2. 具有检测l个错误的充要条件
        • 3. 具有纠正 u 个错误，同时可以发现l个错误的充分必要条件