信源编码

1. 信源符号应编码为
   二进制
   。
2. 平均码长应尽可能短。
3. 消除冗余$\rightarrow$降低比特率。

• 考虑基于字母表的离散无记忆信源：$S = \{s_0, s_1, \ldots, s_k\}$。
• $s_i$的概率：$p_{i}$。
• $s_i$的码长：$l_i$。
• 平均码长，即每个符号的平均比特数：$L = \sum_{k=0}^{K-1} p_k \cdot l_k$。

• $L$可能达到的最小值：$L_{min}$。
• 信源编码效率：$\eta=\frac{L_{min}}{L}$。

• 数据压缩。
  1. 传输前消除冗余信息。
  2. 进行无损数据压缩。
  3. 表示离散无记忆信源输出的信源码，应当能够唯一解码。

任意码字都

不是其他码字前缀

的可变长度信源码。

• 前缀码的特点。
  1. 前缀码能够唯一解码。
  2. 反过来不一定成立：并不是所有唯一可译码都是前缀码。

• 概率之和：$1 = \sum_{k=0}^{K-1} p_k = \sum_{k=0}^{K-1} 2^{-l_k}$。
• 平均码长：$L = \sum_{k=0}^{K-1} p_k \cdot l_k = \sum_{k=0}^{K-1} 2^{-l_k} \cdot l_k$。

1. 按概率从高到低排列符号，将它们作为树的叶节点。
2. 重复以下步骤，直到只剩下一个节点。
   • 选择概率最小的两个节点，给较小者分配0，较大者分配1。反过来也可以，但必须保持一致。
   • 合并两个节点，创建新节点，其概率为两者概率之和。
   • 回到第1步重新排列。
3. 对每个符号，沿叶节点至根节点的路径生成二进制编码。
   • 叶节点对应的比特，是码字的最后一位。

• 方差衡量码长的变化程度。
  $\sigma^2 = \sum_{k=0}^{K-1} p_k (l_k - \overline{L})^2$
• 为避免错误，选择
  方差较大
  的霍夫曼树。
  → 方差较大的树具有更多样的码长，因此能更好地处理错误。

• 方差较大的树能更好地处理错误。