信息论

这是一篇关于信息论的思维导图，包括：第一章概论、第二章信源与信息嫡、第三章信道容量、第四章率失真理论、第五章数据压缩。

信息论

• 概论
  • 香农——奠基人
  • 概念
    • 信息（抽象），消息（图像文字），信号（电信号）
    • 编码问题
      • 信源编码
        • 1.将消息转换为进制码元，形成基带信号 2.压缩冗余度，提高通信系统传输信息的效率
      • 信道编码
        • 检错或纠错，提高传输信息的可靠性
      • 加密编码
        • 提高安全性
• 第二章 信源与信息熵
  • DMS离散无记忆信源
    • 输出离散且独立（放回）
  • 自信息self Information
    • 公式
    • 性质
      • 概率越大，自信息越小，包含的不确定度越小
      • 若p=1，则I=0 若p=0，则I=∞
        • 独立时可加性
    • 单位：bit
  • 熵Entropy
    • 公式
    • 即平均自信息量或平均不确定度
    • 单位：bit/sig
    • 越趋向1或0，H越小
    • 性质
      • 非负性≥0
      • 当pi=1，H=0
        • 若等概率，则熵最大H=logr
      • 对称性：顺序不固定
      • 凸Convex性质
        • 是概率向量的凸函数
  • 联合熵Joint Entropy
    • 联合信息
    • 性质
      • H(Y,X)=H(X,Y)
      • 若XY独立，则HX,Y)=H(X)+H(Y)
  • 条件熵Conditional Entropy
    • 公式
      • p(x,y)=p(x)*p(y|x)
    • 性质
    • 意义
      • H(X|Y)
        • 收到Y，对于输入端X存在的不确定性称为疑义度，代表了在信道中损失的信息，又称损失熵
      • H(Y|X)
        • 发出X后，对Y仍然存在的平均不确定度，又称作噪声熵
  • 互信息Mutual Information
    • 公式
    • 从Y中得到X的信息量（交集）
      • 接收到Y后对X的不确定度减少的量
    • XY相互独立时（不相关），I=0
    • 性质
      • 非负性
    • 定理
      • • 对于固定信道，平均互信息量是信源概率分布的凸函数，且存在最大值
        • 对于固定信源，平均互信息量是信道的凹函数，且存在最小值
• 第三章 信道容量
  • 离散无记忆信道DMC
    • 转移概率 transition probabilities
      • • • 矩阵Matrix：行为输入，列为输出
  • 信道容量
  • 简单离散信道
    • 无损信道Ioseless channel
      • H(X|Y)=0
        • 已知Y，完全可知X
      • 信道容量（r为输入个数）
      • 转移概率每列只有一个非0元素
    • 无噪信道noiseless channel
      • H(Y|X)=0
        • 当已知X，完全确定Y
      • 信道容量
      • 转移概率非0即1，且每行只有一个1
    • 无噪无损信道
      • H(Y|X)=0且H(X|Y)=0
      • 一对一
      • 信道容量（r为行数输入符号个数）
  • 对称信道 Symmetric Channel
    • 条件
      • 任意行都是由第一行置换，任意列都是由第一列置换
    • 性质
      • 若输入的X为等概率分布，则输出Y也是等概率分布
    • 信道容量
      • • s为输出符号集个数(列数)
    • 二进制对称信道
    • 强对称信道
    • 准对称信道Quansi-symmetric Channel(DMC)
      • 定义
        • 行满足置换条件，列不满足置换条件
      • 信道容量
        • 当输入分布为等概率分布时，互信息达到最大值，即信道容量
        • 将转移概率矩阵划成若干（r）个互不相交的对称子集
          • • • 例子
      • 二进制丢失信道Binary erasure channel（BEC）
        • 两个输入，三个输出，其中一个输出为丢失输出
        • 信道容量
          • C=1-p
      • 弱对称信道Weakly symmetric channel
        • 任意行为首行置换，所有列的和相等
• 第四章 率失真理论
  • 失真越大，信息率越小，传输效率越高
  • 失真度量Distortion measure
    • 失真函数
      • 汉明失真
      • 平方误差失真
        • • 用于连续源
    • 失真矩阵
    • 平均失真
      • • 序列失真
  • 信息率失真函数 Information rate distortion function
    • 信源编码器的作用
      • 使编码后所需的信息传输率R尽量小
    • 如果给出一个失真的限制值D，在平均失真＜D的条件下，可以选择一种编码方法（一种假想信道）使信息率R尽可能小。
    • 第一步
      • 满足失真条件的信道集合（D允许实验信道）
    • 第二步
      • PD中寻找一种信道，使R最小
        • D允许信道PD中，可以寻找一种信道pij，使给定的信源p(xi)经过此信道传输后，互信息I(X；Y)达到最小。该最小的互信息就称为信息率失真函数R(D)
        • D越大，I越小
    • 性质
      • R(D)
        • 失真矩阵每行至少一个为0，每列最多只有一个0
          • Dmin=0
          • R(Dmin)=R(0)=H(X)
        • Dmax使R(D)=0的最小值
          • R(Dmax)=0
          • R(D)=0，I(X,Y)=0，即X,Y相互独立
        • 下凹性连续性
          • 单调递减
• 第五章 数据压缩
  • 基础码字
    • 定长码：固定长度的码 变长码：码中的码字长短不一
    • 非奇异码：信源符号和码字一一对应 奇异码：两个不同信源符号对那个的码字相同
    • 唯一可译码：任意有限长的码元序列，只能被唯一的分割成一个个的码字
    • 非即时码：接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码。 即时码：接收到收到一个完整码字后，能立即译码
      • 即时码判断：任意一个码字都不是其他码字的前缀部分
  • 码树和不等式
    • 满树
      • 对于D进制的码树，r级节点有Dr个；
      • 如果指定某个r级节点为终端节点并表示一个信源符号的码 字，相应的码字即为从树根到此端点的分枝标号序列，长度 为r，且为即时码
    • 唯一可译码性质——Kraft 不等式
      • • D为进制
        • l为码长
  • 最优码
    • 期望码长expected length
      • • 单位bit
    • 即时码的期望码长一定大于等于码的熵
      • 取等号
        • 最优码
    • 最优码性质
    • 最优码，是有最短期望长度的即时码
      • 码长越短，概率越大
      • 两个最长码字具有相同码长
      • 最长码字只有最后一位不同
  • 霍夫曼编码方法Huffman Code
    • 最优码中最优
    • 步骤
      • 1.根据概率将信源符号按照降序排序
      • 2.把最小概率的两个符号形成一个新的节点
        • 概率相加
        • 分别附0和1
      • 3.再次进行排序，重复，只剩一个节点
    • 平均码长编码效率
      • R=H(X)/L
    • 霍夫曼编码非唯一，即时码，无失真，分组码
      • 分组码：每一个符号对应一个码字
    • 出现相同概率时，排序时一般将新合并的概率放在上面
    • 码方差
    • 优点
      • 哈夫曼码的编码方法保证了概率大的符号对应于短码， 概率小的符号对应于长码，充分利用了短码，效率最高;
      • 任何一个码字都不是其他码字的前缀，从而保证了哈夫 曼码是即时码
  • 香农编码Shannon codes
    • 累积分布，没哈夫曼短
    • H≤L≤H+1
    • 分组码
  • 费诺编码Fano codes
    • 分组码无失真
    • 次优
  • 算术编码Arithemetic coding
    • 非分组码
      • 无密码表
    • 累计迭代
  • 都是唯一可译码，只有算术编码不是分组码
• 第六章-信道编码
  • The definition of channel coding（信道编码的定义）
    • 在通道中编码数据的一种方法是添加冗余位转换为信息位，以降低错误率。
  • random coding（随机编码）
  • Linear Block Code（线性分组码）
    • Fundamental of Linear Block Code（线性分组码的基础）
      • • 信息空间
        • 码空间
        • 分组码就是进来的和出去的，一一对应。
      • 码率：coder rate
        • R=k*log2(q)/n=klbq/n
    • Generator Matrix and check matrix（生成矩阵和校验矩阵）
      • 生成矩阵
        • • G是k行n列
        • 系统矩阵
          • • 系统代码的前k位被称为信息位，后n-k位被称为检查位
      • 校验矩阵
      • 例题：
        • • 解：
            • • 分别将信息组中的数代入到m中，计算码字。
            • • 系统码集就是把生成矩阵前面部分，经过行变换为单位矩阵，再用该矩阵利用映射关系求解的码集。
            • • 第一种方法：H乘x的转置=0
              • 第二种方法：x乘H的转置=0
            • • 第二个是m1
              • 前三位只要将开关搭在图示位置，就可直接输出不用经过加法器。
  • Convolutional code（卷积码）
    • 定义：
      • • 输出，不但与之前的输入相关，还与之后的输入相关。