信息量的概念

信息量：表示该符号所需要的位数。

考虑用 0 和 1 组成的二进制数码为含有 n 个符号的某条消息编码，假设符号 \(a_{j}\) 在整条消息中重复出现的概率为 \(P_{j}\) ，则该符号的信息量定义为：

\[E_{n} = -log_{2}(P_{j})\qquad(0\le P_{j}\le1)\]

信息量表示为以 2 为底的对数，是正值。

举例说明

输入信源字符串：aabbaccbaa

a、b、c 出现的概率分别为 0.5、0.3 和 0.2，他们的信息量分别为：

\[ E_{a} = -\log_{2}0.5 = 1\] \[ E_{b} = -\log_{2}0.3 = 1.737\] \[ E_{c} = -\log_{2}0.2 = 2.322\]

总信息量也即表达整个字符串需要的位数：

\[E = E_{a} \times 5 + E_{b} \times 3 + E_{c} \times 2 = 14.855(bit)\]

等长编码

输入信源字符串：aabbaccbaa

使用等长编码编码该字符串：a-00, b-01, c-10

则该字符串可表示为："00000101001010010000"，需要 20 位二进制数表示。

熵编码的概念

数据压缩的基石是 Shannon 于 1948 年创立的信息论。 Shannon 第一定律（率失真定律）确定了在编码过程中不损失任何信息，即在无损编码条件下数据压缩的理论极限是信息的熵，并指出了如何建立最优数据压缩编码方法。 这类保存信息熵的编码方法统称为熵编码（Entropy coding）, 熵编码结果经解码后可无失真地恢复出原始信息。

假设信源符号集 \(A\ {a_{1},a_{2},...,a_{j}}\)，其中每个元素 \(a_{j}\) 为信源符号。 其中信源产生符号 \(a_{j}\) 这个事件的概率是 \(P_{j}\)，则对每个信源输出的平均信息量为：

\[H(X)=-\sum_{j=1}^{m}p_{j}*\log_{2}p_{j}\] \[\sum_{j=1}^{m}p_{j}=1\]

\(H(X)\) 为信源的平均信息量，或称为 “熵”（entropy）

平均码长的概念

如果对字符 \(a_{j 的}\) 编码长度为 \(L_{j}\)，则信号 L 的平均码长为：

\[L_{avg} = \sum_{j=1}^{m}p_{j}*L_{j}\]

其中 m 为信号中所出现不同字符的个数。

无失真编码定理

• 平均码长 \(L_{avg} \gg H(X)\)：有冗余，不是最佳
• 平均码长 \(L_{avg} \lt H(X)\)：不可能
• 平均码长 \(L_{avg} \approx H(X)\)：最佳编码

熵值是平均码长的下限。

编码的基本思想就是用较少的比特数表示出现概率较大的码源符号，用较多的比特数表示出现概率小的码源符号；

常用编码方式：霍夫曼编码 (Huffman)：数据压缩技术 - Huffman 编码

编码效率的定义

熵 \(H(x)\) 除以平均码长 \(L_{avg}\) 即表示编码效率：

\[H(X) = -\sum_{j=1}^{m}p_{j}*\log_{2}p_{j}\] \[\eta = \frac{H(X)}{L_{avg}}\qquad\eta\le 1\]