信息论与编码原理：信源编码（第三章）

《信息论与编码原理》系统地讲述了信息论与编码的基本理论，共11章，内容包括：信息的基本概念、信源及其信息量、信道及其容量、信息率失真函数、信源编码和信道编码定理、网络信息论以及信源编码和信道编码的理论与方法。这是第一章 信源编码的内容，后续还会发布。

信源编码

• 概念
  • 如果编码结果能够无失真地恢复为编码前的消息，这样的编码就是无失真信源编码
  • 把信源消息符号序列变换成码符号序列的过程
  • 目的：压缩代码长度
  • 信源编码的两种基本途径
    • 均匀化分布：使编码后各个符号出现概率尽可能相同
    • 解除相关性：使编码后使序列的各个符号尽可能地相互独立
  • 术语
    • 码字：变换后的各个新符号串Wj被称为码字
    • 码长：码字Wj的长度（符号数）Lj被称为码长
    • 码元：组成码字Wj的各位代码符号xj称为码元
    • 码：所有的码字的集合称为“码”
    • 编码：全部Sj《---》Wj的映射关系称之为编码
  • 平均码长
    • 
  • 编码效率
    • 
    • 其中H（A）是信源熵
  • 唯一可译码
    • 定义
      • 若码的任意一串有限码符号序列只能被唯一地译成所对应的信源符号序列，则此码称为唯一可译码
    • 分类
      • 即时码
        • 如果在接收端收到一个完整的码字后，就能立即进行译码
      • 非即时码
        • 在接收端收到一个完整码字后，还需等下一个符合码接收后才能判断是否可以译码
  • 码树
    • 对于给定码字的全体集合，可以用r进制码的码树来描述
• 等长码和变长码
  • 等长码
    • 编码中要求所有码字相同
  • 变长码
    • 编码中并不要求所有码字长度都相同
• 等长码信源编码原理
  • 起码要求：唯一可译性
    • 
  • 最佳要求：缩短代码长度
  • 香农等长码编码定理
    • 理论上是能够进行无失真信源编码的
    • 能否实现无失真编码的临界码长是
    • 实现无失真编码的条件的每个字符平均码长L>L0，并且被编序列长度N必须足够大
• 变长编码原理
  • 唯一可译性
  • 结构特征
    • 异前缀性:任一码字都不会是另一码字的前缀。因此不会出现一个码字没收完却被判为其它码字的情况。也叫做非延长性:任一码字都不会是另一码字的延长。因此一个码字一旦收完立刻就能判断,而不必再等待。
  • 码树
    • 设计唯一可译即时码的方法
  • Kraft不等式
    • 
    • 唯一可译码满足的必要条件
    • 不能判断是不是即时码
  • 变长码压缩代码长度原理：概率匹配原则
    • 只要每一码字的长度都等于它所对应的信源符号的自信息(以r为底)，就能使编码最短。
    • 即概率小的用长码，概率大的用短码
  • 香农变长码编码定理
    • 
    • 注意
      • 要做到无失真的信源编码，每个信源符号平均所需最少的r元码个数为信源的熵H(S)。
      • H(S)是无失真信源压缩的极限值。
      • 若编码的平均码长小于信源的嫡值H(S)，则惟一可译码不存在，在译码或反变换时必然要带来失真或差错。
      • 通过对扩展信源进行变长编码，当N→oo时，平均码长→Hr（S)
      • 减少平均码长所付出的代价是增加了编码的复杂性
    • 无失真信源编码的实质
      • 对离散信源进行适当的变换，使变换后形成的新的码符号信源(即信道的输入信源)尽可能为等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，使信道的信息传输率达到信道容量，实现信源与信道理想的统计匹配。
• 最佳码（紧致码）
  • 定义
    • 对于某一个信源和某一符号集来说，满足克拉夫特不等式的唯一可译码可以有多种，在这些唯一可译码中，如果有一种(或几种）码，其平均码长小于所有其他唯一可译码的平均码长，则该码称为最佳码(或紧致码)。
  • 香农编码
    • 直接用概率匹配原则进行单符号信源编码，就叫香农码
    • 缺点：有小数时候不适合
  • 费诺编码
    • 费诺提出一种从根到叶的编码法，先把符号集分成两组，使各组总概率大致相等，每组符号再按概率大体相等的原则继续一分为二，直到每组只有一个符号为止。
  • 霍夫曼编码
    • 霍夫曼编码方法:
      • (1)把信源符号集中的所有符号按概率从小到大排队。
      • (⑵)取概率最小的两个符号作为两片叶子合并到一个节点。
      • (3)视此节点为新符号，其概率等于被合并的两个概率之和，参与 概率排队
      • (4)重复(2)(3)两步骤，直至全部符号都被合并到根。
      • (5)从根出发，对各分枝标记0和1。从根到叶的路径就给出了各个 码字的编码和码长。
    • 此为单符号信源编码的最佳方法
    • 多元霍夫曼编码
      • 多元码可以用多元码树表示。r元码树每个节点分为r个枝叉，编码时，仍然从概率最小的符号开始，每次r个符号合并为一个节点。
      • 二元霍夫曼编码
        • 可以采用N维扩展信源来进行编码。所谓N维扩展信源指以把N个二元符号的符号串当作一个“符号”看待的信源。(如，对001100110010000......序列，每3个符号作为一个待编码分组，就是将001，100，110，010，000.......参照编码后的码字进行编码)
        • N维扩展信源中共有2N个不同的“符号”，由于2N >> r，霍夫曼编码就能发挥威力,大大提高编码效率。
    • 限制
      • Huffman编码只适用于信源符号数目m比码元符号r数目大很多的情况。
  • 字典编码
    • 原理
      • 累积字符，直到字符串与任何字典条目都不匹配。然后将此新字符串定义为新条目，同时将与该字符串对应的条目减去最后一个字符以后进行发送，这个剩下的字符用作下一个要匹配的字符串的第一个字符。
  • 算术编码
    • 分组编码
      • 将信源消息序列分成长度为N的字符组，按组进行编码的方式。
    • 序列编码
      • 直接为整个信源消息序列寻找编码序列的方式。
    • 等长码和变长码的编码，都是“块码”，算术编码属于“流码”，直接把信源发出的非等概序列变换成等概序列。它从全序列出发，考虑符号之间的关系来进行编码。
    • 应用
      • 图像压缩