霍夫曼编码详解 |
您所在的位置：网站首页 › 霍夫曼编码例题及答案 › 霍夫曼编码详解 |
霍夫曼编码详解
|
本专栏包含信息论与编码的核心知识，按知识点组织，可作为教学或学习的参考。markdown版本已归档至【Github仓库：information-theory】，需要的朋友们自取。 文章目录霍夫曼编码最佳变长编码霍夫曼编码霍夫曼编码的步骤例 单符号离散无记忆信源L-Z编码总结霍夫曼编码最佳变长编码最佳码: 对于某一信源和某一码符号集来说,若有一唯一可译码,其平均码长小于所有其他唯一可译码的平均长度。紧致码 香农(Shannon)费诺(Fano）霍夫曼(Huffma )霍夫曼编码在霍夫曼编码算法中, 固定长度的信源输出分组将映射成可变长度的二进制分组。该过程称为定长到变长编码。 其思想是将频繁出现的固定长度序列映射成较短的二进制序列, 而将出现频率较低的固定长度序列映射成较长的二进制序列。 平均码长 \overline{\boldsymbol{K}}=E[L]=\sum_{x \in \Xi} p(x) l(x)一种最优的信源编码方法是信源的平均码长接近或者等于信源的信息熵H(X) 。 霍夫曼编码的步骤将信源消息符号按其出现的概率大小依次排列 p(x_{1}) \geq p(x_{2}) \geq \ldots \geq p(x_{n})取两个概率最小的字母分别配以 0 和 1 两码元, 并将这两个概率相加作为一个新字母的概率, 与未分配的二进 符号的字母重新排队。对重排后的两个概率最小符号重复步骤(2)的过程。不断继续上述过程,直到最后两个符号配以 0 和 1 为止从最后一级开始,向前返回得到各个信源符号所对应的码元序列, 即相应的码字。Example：试为如下信源设计霍夫曼编码 \left[\begin{array}{l} \mathrm{A} \\ P \end{array}\right]=\left[\begin{array}{ccccc} A 1 & A 2 & A 3 & A 4 & A 5 \\ 1 / 2 & 1 / 4 & 1 / 8 & 1 / 16 & 1 / 16 \end{array}\right] 上例中, 平均码长为 \begin{array}{l} \bar{K}=E(L)=1 \times 1 / 2+2 \times 1 / 4+3 \times 1 / 8+2 \times 4 \times 1 / 16 \\ =1.875 \\ H(X)=1.875=E(L) . \end{array}霍夫曼编码的平均码长满足如下不等式 H(X) \leq \overline{\boldsymbol{K}} |
【本文地址】
今日新闻 |
推荐新闻 |