哈夫曼编码的平均码长_哈夫曼编码的平均码长怎么计算

2024年 5月 27日下午7:42 • 激活谷笔记

哈夫曼编码的平均码长_哈夫曼编码的平均码长怎么计算霍夫曼编码平均码长是什么。怎么求？霍夫曼编码的平均码长就是信息熵，因此它同信息熵的计算方法是一样的。霍夫曼编码最佳变长编码最佳码: 对于某一信源和某一码符号集来说,若有一唯一可译码,其平均码长小于所有其他唯一可译码的平均长度。紧致码

霍夫曼编码平均码长是什么。怎么求？
　　霍夫曼编码的平均码长就是信息熵，因此它同信息熵的计算方法是一样的。

　　霍夫曼编码

　　最佳变长编码

　　最佳码: 对于某一信源和某一码符号集来说,若有一唯一可译码,其平均码长小于所有其他唯一可译码的平均长度。紧致码香农(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}}<H(X)+1$

　　如果对长度为n的信源字符序列进行霍夫曼编码(信源的 n 次扩展信源) 而不是对单信源字符的编码, 则有

　　 $H(X^{n}) \leq \overline{\boldsymbol{K}}_{n}<H(X^{n})+1$ 例设单符号离散无记忆信源如下. 要求对信源编二进制霍夫曼码。 $\left[\begin{array}{l} X \\ p(x) \end{array}\right]=\left[\begin{array}{ccccccc} x_{l} & x_{2} & x_{3} & x_{4} & x_{5} & x_{6} & x_{7} \\ 0.20 & 0.19 & 0.18 & 0.17 & 0.15 & 0.10 & 0.01 \end{array}\right] \\$

　　熵 $\begin{array}{l} H(X) \\ \begin{aligned} =-0.2 & \log 0.2-0.19 \log 0.19-0.18 \log 0.18-0.17 \log 0.17 \\ & -0.15 \log 0.15-0.10 \log 0.10-0.01 \log 0.01 \\ = & 2.61 \end{aligned} \end{array} \\$ 平均码长为 $\begin{array}{l} \bar{K}=\sum_{i=1}^{7} p\left(x_{i}\right) K_{i} \\ =0.2 \times 2+0.19 \times 2+0.18 \times 3+0.17 \times 3+0.15 \times 3+0.10 \times 4 +0.01 \times 4=2.72 \end{array} \\$ 编码效率 $\eta=\frac{H(X)}{R}=\frac{H(X)}{\bar{K}}=\frac{2.61}{2.72}=96 \% \\$

　　霍夫曼的编法并不唯一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到可分离码字。不同的码元分配,得到的具体码字不同,但码长 K_i 不变,平均码长也不变,所以没有本质区别;

　　缩减信源时,若合并后的新符号概率与其他符号概率相等，从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。

　　不同的编法得到的码字长度 K_i 也不尽相同。

　　例单符号离散无记忆信源

　　 $[\begin{array}{c} X \\ P(X) \end{array}]=\{\begin{array}{lllll} x_{1}, & x_{2}, & x_{3}, & x_{4}, & x_{5} \\ 0.4 & 0.2 & 0.2 & 0.1 & 0.1 \end{array}\} \\$

　　单符号信源编二进制哈夫曼码,编码效率主要决定于信源熵和平均码长之比。

　　对相同的信源编码, 其熵是一样的, 采用不同的编法, 得到的平均码长可能不同。

　　平均码长越短,编码效率就越高。

　　编法一的平均码长为

　　 $\overline{K_{1}}=\sum_{i=1}^{5} p\left(x_{i}\right) K_{i}=0.4 \times 1+0.2 \times 2+0.2 \times 3+0.1 \times 4 \times 2=2.2 \\$

　　编法二的平均码长为

　　 $\overline{K_{2}}=\sum_{i=1}^{5} p\left(x_{i}\right) K_{i}=0.4 \times 2+0.2 \times 2 \times 2+0.1 \times 3 \times 2=2.2 \\$

　　两种编法的平均码长相同,所以编码效率相同。

　　哪种方法更好?

　　定义码字长度的方差 $\sigma^{2}$ :

　　 $\begin{array}{c} \sigma^{2}=E\left[\left(K_{i}-\bar{K}\right)^{2}\right]=\sum_{i=1}^{5} p\left(x_{i}\right)\left(K_{i}-\bar{K}\right)^{2} \\ \sigma_{1}^{2}=0.4(1-2.2)^{2}+0.2(2-2.2)^{2}+0.2(3-2.2)^{2}+0.1(4-2.2)^{2} \times 2 =1.36 \\ \sigma_{2}^{2}=0.4(2-2.2)^{2}+0.2(2-2.2)^{2} \times 2+0.1(3-2.2)^{2} \times 2=0.16 \end{array} \\$

　　第二种编码方法的码长方差要小许多。第二种编码方法的码长变化较小, 比较接近于平均码长。

　　第一种方法编出的5个码字有4种不同的码长;第二种方法编出的码长只有两种不同的码长;第二种编码方法更简单、更容易实现,所以更好。

　　结论:

　　在霍夫曼编码过程中,对缩减信源符号按概率由大到小的顺序重新排列时,应使合并后的新符号尽可能排在靠前的位置, 这样可使合并后的新符号重复编码次数减少,使短码得到充分利用。

　　例: 一信源模型如下, 试对信源符号进行 Huffman编码, 并计算平均码长和编码效率。若对其2次扩展信源进行编码, 结果如何

　　 $\left[\begin{array}{l} S \\ p \end{array}\right]=\left[\begin{array}{ccccc} s_{1} & s_{2} & s_{3} & s_{4} & s_{5} \\ 0.4 & 0.2 & 0.2 & 0.1 & 0.1 \end{array}\right] \\$

　　解: (1) 不做扩展, 进行单符号Huffuman编码时编码结果为:

　　 $\begin{array}{ccc}s_{1} & 1 & \\ s_{2} & 01 & H(S)=2.122 b i t / s y m \\ s_{3} & 000 & \bar{l}=2.2 \text { 码元 } / \text { sym } \\ s_{4} & 0010 & \eta=H(S) / \bar{l}=0.965 \\ s_{5} & 0011 & \end{array} \\$

　　（2）二次扩展信源 $\mathrm{S}^{2}$ , 共有 $5^{2}=25$ 个信源符号, 为

　　 $\begin{array}{l} s_{1} s_{1}, s_{1} s_{2}, s_{1} s_{3}, s_{1} s_{4}, s_{1} s_{5}, s_{2} s_{1}, s_{2} s_{2}, s_{2} s_{3}, s_{2} s_{4}, s_{2} s_{5} \\ s_{3} s_{1}, s_{3} s_{2}, s_{3} s_{3}, s_{3} s_{4}, s_{3} s_{5}, s_{4} s_{1}, s_{4} s_{2}, s_{4} s_{3}, s_{4} s_{4}, s_{4} s_{5} \\ s_{5} s_{1}, s_{5} s_{2}, s_{5} s_{3}, s_{5} s_{4}, s_{1} s_{5} \end{array} \\$

　　双应的概率为: $0.16,0.08,0.08,0.04,0.04 \cdots 0.01$ 可得编码结果为

　　 $\begin{array}{l} s_{1} s_{1}(01), s_{4} s_{2}(001), s_{1} s_{3}(1001), s_{1} s_{4}(0001), s_{4} s_{5}(10111), \\ s_{2} s_{1}(1000), s_{2} s_{2}(11001), s_{2} s_{3}(11010), s_{2} s_{4}(111010), s_{2} s_{5}(111011) \\ s_{3} s_{1}(1010), s_{3} s_{2}(11011), s_{3} s_{3}(11100), s_{3} s_{4}(111110), s_{3} s_{5}(111111), \\ s_{4} s_{1}(10110), s_{4} s_{2}(111100), s_{4} s_{3}(000000), s_{4} s_{4}(00001000), s_{4} s_{5}(0000101), \\ s_{5} s_{1}(11000), s_{5} s_{2}(111101), s_{5} s_{3}(000001), s_{5} s_{4}(0000110), s_{5} s_{5}(0000111) \\ \bar{l}=2.16 \text { 码无/sym } \\ \eta=0.982 \end{array} \\$

　　结论：N 越大, 编码效率越大。某DMS信源如式: $\left[\begin{array}{l}\mathrm{X} \\ \mathrm{P}\end{array}\right]=\left[\begin{array}{ccc}x_{1} & x_{2} & x_{3} \\ 1 / 2 & 1 / 3 & 1 / 6\end{array}\right]$ , 则其二次扩展信源为 $\begin{array}{l} {\left[\begin{array}{c} X^{2} \\ P \end{array}\right]} =\left[\begin{array}{ccccccccc} x_{1} x_{1} & x_{1} x_{2} & x_{1} x_{3} & x_{2} x_{1} & x_{2} x_{2} & x_{2} x_{3} & x_{3} x_{1} & x_{3} x_{2} & x_{3} x_{3} \\ 1 / 4 & 1 / 6 & 1 / 12 & 1 / 6 & 1 / 9 & 1 / 18 & 1 / 12 & 1 / 18 & 1 / 36 \end{array}\right] \end{array} \\$ 请分别对DMS信源: $\left[\begin{array}{l}\mathrm{X} \\ \mathrm{p}\end{array}\right]=\left[\begin{array}{ccc}x_{1} & x_{2} & x_{3} \\ 1 / 2 & 1 / 3 & 1 / 6\end{array}\right]$ , 及其二次扩展信源进行二进制霍夫曼编码，并计算平均码长。 DMS信源: 。平均码长 =1.5 扩展信源: $\begin{array}{ccccccccc}x_1 x_1 & x_1 x_2 & x_1 x_3 & x_2 x_1 & x_2 x_2 & x_2 x_3 & x_3 x_1 & x_3 x_2 & x_3 x_3 \\ 1 / 4 & 1 / 6 & 1 / 12 & 1 / 6 & 1 / 9 & 1 / 18 & 1 / 12 & 1 / 18 & 1 / 36 \\ 01 & 111 & 001 & 110 & 100 & 1000 & 1011 & 0011 & 0010\end{array}$ 平均码长 =107 / 36; 平均每符号码长 =107 / 72=1.486; 该信源信息熵 =1.459 bit/sym。

　　L-Z编码

　　将信源序列分成一系列以前未出现而且最短的字符串或词组。如，将信源序列列1011010100010…分成1，0，11，01，010，00，10，..注意，每个词组具有如下性质:每个词组有一个前缀在前面出现过;每个词组的长度比其前缀长一个字符。对词组进行如下编码:给出前缀在词组序列中的位置号和最后一个字符的值。L-Z编码先将信源分成不等长的词组然后编码。

　　设c(n)为信源序列所分成的词组的个数，那么描述词组的前缀的位置需要logc(n) bit, 而词组的最后一个符号需要1bit。上例中，词组的个数为7，那么描述词组的前缀的位置需要3bit。所对应的编码序列为（000，1)，（000，0)(001，1) , (010，1) ,（100，0) , (010，0)，(001，0)。其中每个括号内的第一个数字表示该词组的前缀的位置序号，第二个数字是该词组的最后一个符号。

　　L-Z算法主要包括两步:将序列分组，计算词组个数c(n)和描述前缀的位置需要的比特数logc(n);对每个词组，计算前缀位置，构成码字。前缀位置的编码可以是等长码，也可以是变长码。通常在起始位置需要的位数少，而随着词组序号的增长，前缀位置的编码的位数也不断增加。L-Z编码一般用在信源序列长度较大是才有效。

　　总结

　　编码的基本概念无失真信源编码:译码错误概率任意小。香农无失真信源编码定理:存在压缩编码的极限。霍夫曼编码:是一种最优的信源编码，某些信源概率分布条件下，可以达到香农信源编码的极限。

　　参考文献：Proakis, John G., et al. Communication systems engineering. Vol. 2. New Jersey: Prentice Hall, 1994.Proakis, John G., et al. SOLUTIONS MANUAL Communication Systems Engineering. Vol. 2. New Jersey: Prentice Hall, 1994.周炯槃. 通信原理（第3版）[M]. 北京：北京邮电大学出版社, 2008.樊昌信, 曹丽娜. 通信原理（第7版） [M]. 北京：国防工业出版社, 2012. 本专栏包含信息论与编码的核心知识，按知识点组织，可作为教学或学习的参考。markdown版本已归档至【Github仓库：information-theory】，需要的朋友们自取。或者【AIShareLab】sigusoft 信息论也可。

激活谷谷主为您准备了激活教程，为节约您的时间请移步至置顶文章：https://sigusoft.com/99576.html

新闻管理系统毕业设计怎么写好_新闻管理系统毕业设计怎么写好一点

上一篇 2024年 5月 27日下午7:36

对比人脸相似度的软件_对比人脸相似度的软件有哪些

下一篇 2024年 5月 27日

王兆飞的博客有哪些

王兆飞的博客有哪些这两天一位大神级人物在知乎和微博迅速走红甚至占领了微博热门排行榜他走红的原因是因为他特殊的人生遭遇有网友把这位知乎答主传奇的人生做了一下纪录得到了如下的人生轨迹1970年：出生1984年：奥运会中国代表团运动员19

激活谷笔记 2024年 5月 17日
医学上dds是什么意思啊_医学上dds是什么意思啊

医学上dds是什么意思啊_医学上dds是什么意思啊药物的传递系统（DDS）药物传递系统（DDS）的概念出现在20世纪70年代初，80年代开始成为制剂研究的热门课题。60年代生物药剂学和药物动力学的崛起可以测定药物在体内的吸收、分布、代谢和排泄的定量关系，以及药物的生物利用度。药物在体内过程的研究结果为新剂型的开发研究提供了科学依据

激活谷笔记 2024年 5月 31日
fft频谱分析有什么用_fft频谱分析作用

fft频谱分析有什么用_fft频谱分析作用用FFT对信号作频谱分析x1n=[ones(1,4)];M=8;xa=1:(M/2);xb=(M/2):-1:1;x2n=[xa,xb];x3n=[xb,xa];x1k8=

激活谷笔记 2024年 5月 24日
激活谷笔记

anaconda安装为什么这么慢_anaconda安装卡在setting up

anaconda安装为什么这么慢_anaconda安装卡在setting upAnaconda安装（过程详细）在本文开始之前，祝大家新年快乐，心想事成，事事顺利！一、前言Anaconda是一个开源的Python发行版本，用来管理Python相关的包，安装Anaconda可以很方便的切换不同的环境，使用不同的深

2024年 5月 16日
Datagrip激活2024.1.3(DataGrip 2024.1.3)

Datagrip激活2024.1.3(DataGrip 2024.1.3)

激活谷笔记 2024年 6月 7日
激活谷笔记

劲客一公里油耗几毛钱_劲客一公里油耗几毛钱正常吗

劲客一公里油耗几毛钱_劲客一公里油耗几毛钱正常吗日产劲客油耗多少钱一公里？尼桑劲客真实油耗测试日产劲客油耗多少钱一公里？尼桑劲客真实油耗测试日产劲客工信部油耗2020款和2019款、1.5L手动版劲客工信部综合工况油耗7.7L。2020款和2019

2024年 5月 24日
激活谷笔记

ubuntu和linux安装哪一个更好_fedora和ubuntu哪个好

ubuntu和linux安装哪一个更好_fedora和ubuntu哪个好你应该选择 Ubuntu 还是 Fedora？选择 Ubuntu 还是 Fedora？它们的区别是什么？哪一个更好？你应该使用哪一个？看看这篇对比 Ubuntu 和 Fedora 的文章吧。 Abhishek Prakash（作者）Ubuntu 和 Fedora 都

2024年 5月 16日
ple是什么意思翻译_puiple是什么意思翻译

ple是什么意思翻译_puiple是什么意思翻译Paper tube 的翻译是：纸管中文翻译英文意思，翻译英语翻译结果1翻译结果2翻译结果3翻译结果4翻译结果5翻译结果1.mytext’)” class=’d_copy’复制译文.mytext’)” 编辑译文.mytext’,’ggrd’);” 朗读译文返回顶部纸管翻译结

激活谷笔记 2024年 5月 28日
激活谷笔记

b树与红黑树的区别_b+树红黑树区别

b树与红黑树的区别_b+树红黑树区别B树、B+树、红黑树1、B树B树属于多叉树又名平衡多路查找树（查找路径不只两个）规则：（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；（2）子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，

2024年 5月 30日
vscode是什么写的_用vscode写一个html页面

vscode是什么写的_用vscode写一个html页面Code editing. Redefined.Meet IntelliSense. Go beyond syntax highlighting and autocomplete with IntelliSense, which provi

激活谷笔记 2024年 5月 15日
c面向对象和面向过程的区别是什么

c面向对象和面向过程的区别是什么“这里是云端源想IT，帮你轻松学IT”嗨~ 今天的你过得还好吗？每个人都有一个觉醒期但觉醒的早晚决定个人的命运- 2023.08.09 -Java语言是一种面向对象的程序设计语言，而面向对象思想是一种程序设计思想，我们在面向对象思想的指引下，使用Java语言去设计、开发计算机程序。这里的对象泛指现

激活谷笔记 2024年 5月 19日
stm32串口连接不上_stm32串口没反应

stm32串口连接不上_stm32串口没反应电脑接上stm32没有串口(stm32串口连接不上)1. stm32串口连接不上可以，事实现在，现在任何一款单片机，只要是普通的UART，不是485方式的，都是全双工通信的，所谓全双工通信，就是既能接受，同时也能发送，所以，你没有必要担心这个问题，当然，如果你外接了485芯片，那

激活谷笔记 2024年 5月 23日

哈夫曼编码的平均码长_哈夫曼编码的平均码长怎么计算

相关推荐