H264系列九 热力学熵 信息熵 哈夫曼编码 哥伦布编码
一、阮一峰 熵：宇宙的终极规则
为了理解熵，必须讲一点物理学。
19世纪，物理学家开始认识到，世界的动力是能量，并且提出"能量守恒定律"，即能量的总和是不变的。但是，有一个现象让他们很困惑。物理学家发现，能量无法百分百地转换。比如，蒸汽机使用的是热能，将其转换为推动机器的机械能。这个过程中，总是有一些热能损耗掉，无法完全转变为机械能。一开始，物理学家以为是技术水平不高导致的，但后来发现，技术再进步，也无法将能量损耗降到零。他们就将那些在能量转换过程中浪费掉的、无法再利用的能量称为熵。后来，这个概念被总结成了"热力学第二定律"：能量转换总是会产生熵，如果是封闭系统，所有能量最终都会变成熵。
熵既然是能量，为什么无法利用？它又是怎么产生的？为什么所有能量最后都会变成熵？这些问题我想了很久。物理学家有很多种解释，有一种我觉得最容易懂：能量转换的时候，大部分能量会转换成预先设定的状态，比如热能变成机械能、电能变成光能。但是，就像细胞突变那样，还有一部分能量会生成新的状态。这部分能量就是熵，由于状态不同，所以很难利用，除非外部注入新的能量，专门处理熵。总之，能量转换会创造出新的状态，熵就是进入这些状态的能量。
现在请大家思考：状态多意味着什么？状态多，就是可能性多，表示比较混乱；状态少，就是可能性少，相对来说就比较有秩序。因此，上面结论的另一种表达是：能量转换会让系统的混乱度增加，熵就是系统的混乱度。转换的能量越大，创造出来的新状态就会越多，因此高能量系统不如低能量系统稳定，因为前者的熵较大。而且，凡是运动的系统都会有能量转换，热力学第二定律就是在说，所有封闭系统最终都会趋向混乱度最大的状态，除非外部注入能量。
熵让我理解了一件事，如果不施加外力影响，事物永远向着更混乱的状态发展。比如，房间如果没人打扫，只会越来越乱，不可能越来越干净。
二、知乎大黑旗回答 信息熵与热力学统计物理中的熵有什么区别和联系？
不清楚题主的学科背景，以下回答面向从未系统学习热力学和信息论的朋友，从三个层次讨论“熵”的意义——这其实也是这个概念本身发展的历程。文字有些长，性急的同学可以直接看最后的总结。
一． 熵和永动机——热力学熵的宏观形式
“熵”是一个十分古老的概念，可以上溯至蒸汽时代人们对热机的研究。和热量、温度等其他热力学概念相比，它的确因抽象而难以理解。为避免读者被公式和其它概念吓到，我们从大家喜闻乐见的“永动机”的故事开始。
我们都知道，第一类永动机（即不消耗能源却可以不断对外做功的机器）因为违反能量守恒定律所以是不存在的。但不甘心的工程师们很快又设想出了另一种神奇的机械，被称为第二类永动机。由于它过于神奇，为了理解它，我们必需先研究一艘正常的船。
假设这艘船的动力系统是一座蒸汽机，当它工作的时候，煤在锅炉里燃烧，释放它的化学能变为热能，然后再经卡诺循环转化为船的机械能。而船在航行的时候，又要不断克服水的阻力做功，机械能转化为水的内能。所以在船匀速航行的情况下，煤燃烧释放的能量最终转化为了水的内能（也许表现为使海水的温度上升了一亿亿分之一摄氏度）。而我们为了保持船的航行，只能不断地烧煤。
而如果我有一艘新船，它有一个棒棒的动力系统，能直接从海水里吸收能量，并完全转化为船的机械能。这样一来，我们就能见证一个奇迹：船从海水里获得能量，航行时克服水的阻力做功，又把能量还给海——在这个过程中船和海的总能量没有变多也没有变少，因此丝毫不违反能量守恒定律——然而它不需要烧一粒煤就能环游世界。
这当然是不可能的。但是为了证明这个“不可能”，当时的科学家付出了很多的努力。最终，鲁道夫·克劳修斯发现，任何可以自发进行的过程中，恒温热Q和温度T的比值永远是一个正值。
克劳修斯是德国人，便用德语Entropie命名这个比值，直到几十年后南京大学的胡刚复教授才将这个概念引入国内，并命名为“熵”（意指Q和T的商数）。由定义式我们不难知道，它的量纲是J/K。
熵就像一个固执的沙漏，能量每进行一次转化，它就向前走一点，而它每向前走一点，能量被利用的能力就减少一点。这个过程犹如时间流逝、人的衰老一样不能逆转。这也就是著名的熵增原理：任何孤立系统的总熵不会减少。如果说能量守恒定律限定了能量的数量，那么熵增原理就限定了能量的质量：较优质的能量可以完全转化为较劣质的能量，但较劣质的能量却不可能完全转化为较优质的能量。比如一根简单的电阻丝就能把电能完全转化为热能，但最先进的发电机也不可能把这些热能重新转变为等量的电能。这就是第二类永动机不能实现的原因——机械能是比内能优质的能量，所以直接从海水里吸收热量，并完全转化为船的机械能的装置压根就不存在。
二．熵和有序性——热力学熵的微观形式
1877年，玻尔兹曼提出了著名的玻尔兹曼原理：S=klnΩ。也就是熵的微观形式，其中的k是玻尔兹曼常数，量纲为J/K，由于后面对数项不具量纲，所以玻尔兹曼熵的量纲也是J/K，这是证明它和宏观形式等价的前提。
公式中的Ω是微观状态数，即微观上构型的所有可能的排列数。Ω有时也被理解成“混乱度”，这是合理的。因为作为越有规律的系统，构型就越少，而混乱的系统可以有较多个构型。例如，设想有一组10个硬币，每一个硬币有两面，掷硬币时得到最有规律的状态是10个都是正面或10个都是反面，这两种状态都只有一种构型（排列）。反之，如果是最混乱的情况，有5个正面5个反面，排列构型可以有=252种。（这个例子摘自维基百科）
这也形成了熵最广为人知的理解：熵是系统混乱度（无序程度）的量度。其实，由于宏观系统的Ω是一个天文数字，以至于我们往往无法计算，所以实际应用中熵的微观描述远不如宏观描述常见。但由于我们处在一个看脸的世界，连物理定律也不能例外，这种金光闪闪的表达式和解释比土里土气的宏观描述容易流传太多了（同样可以解释为什么这种东西连幼儿园小朋友都知道）。
其实我觉得玻尔兹曼原理反过来想更令人震撼——对于一个系统，如果某一时刻它的熵确定，那么它可能的微观状态数也是一定的。如果这个系统是整个宇宙的话，这就意味着我们这个世界的可能性也是有限的（尽管非常非常多）……OMG！我要去看女神自拍压压惊了。另外需要注意的是，熵的微观形式是直接和状态数Ω对应的，因此是一个绝对值而非相对值。而由于Ω是自然数，所以熵一定非负；特别的，绝对零度下的晶态物质Ω为1，所以S=kln1=0，这也就是热力学第三定律。
以上两种熵都叫做“热力学熵”，因为它们的等价性已经被证明。
三．熵和信息量——信息熵的意义
信息熵的来历和热力学熵完全不同。把它也叫做“熵”完全是因为香农老爷子当年提出这个概念时参考了热力学熵，并且它的表达式和热力学熵的微观形式非常相似（但和宏观描述看不出任何相似性）的缘故。后来也有人提出了信息熵的其他表述形式，为了方便，下文以最早也最重要的香农熵为准。信息熵的表达式:H=-ElnP(x) 其中E是期望，P(x)是出现的概率（含义下面会提到）。大家发现了吧，它和玻尔兹曼熵表达式S=klnΩ形式完全一样，只有常数上的差别。实际应用中，为了对应二进制数，更常见的是以2为底的形式：，此时结果的量纲为比特。
它的意义非常明确，指观察者对某一事件（结果）的未知程度。举个例子：我要抛一次骰子，在观测到结果之前，骰子六个面向上都有可能，而且概率完全一样（都是1/6).这时，这一事件的信息熵为。现在万能的女神给了我一个提示，这次骰子的结果一定是偶数，于是可能的结果由6种降低为3种，事件的熵也就变成了
。也就是说，当我得到提示后，对于事件结果的不确定性降低了。我们把信息熵降低的量规定为信息量I。上面那条提示对我的信息量是
，正好是1比特，相当于对一个完全未知的命题做一次是非判断需要的信息量。而如果我要得到唯一确定的结果，P(x)就必须等于1，此时的信息熵为零。我们需要得到的信息量就是原本的熵
。
看到这里，聪明的你一定已经可以自己总结出另一个金光闪闪的结论：信息就是负熵。需要特别注意的是，这句话里的“熵”指而且仅指信息熵，试图将这个结论扩大到热力学熵的解释往往都缺乏足够的事实基础，并且含义也经常是含混的。
我们再来看另一个例子：甲乙丙三个实力相当的运动员要进行一次比赛，老王是比赛的裁判和记分员，他必须观察并如实记录三位选手的名次。所以对于他来说，比赛结果有=6种。由于运动员实力相当，每种结果出现的可能性一样，所以结果的熵是
小花是运动员甲的女朋友，她如此爱自己的男友以至于只关心他有没有取得冠军而完全不在意其它选手的成绩。对于小花来讲，比赛的结果只有两种，它的熵大约是0.92（计算略去，大家应该不会对数学计算感兴趣吧）。有的同学会奇怪，这里的熵为什么不是1？原因是由于甲乙丙三个运动员实力相当，所以甲获得冠军的几率只有1/3。也就是说如果小花足够聪明的话，在比赛前就可以知道甲获得冠军的可能比不获得冠军的可能小。这种预期降低了事件的未知程度（熵），也降低了结果对小花的信息量。
老李是比赛场地的管理员，他完全不关心谁胜谁负，而只想等到比赛结束下班回家，那么比赛对他的熵是多少呢？答案是零，因为他只关心比赛有没有结束，而比赛只要一开始就注定会结束，这个结果是唯一确定的。所以老李根本不用观察比赛，只要坐着等就可以了。
这个例子说明对于不同的观察者，由于目的和观测能力的差异，同一个事件的熵也可能是不同的。
我们再回头看老王的记分板，他用三组二进制数记录比赛结果。第一组记录甲的名次，第二组记录乙的名次，第三组记录丙的名次，由于名次有三个可能的值(第1第2第3)，每组二进制数都必需是两位的，所以老王对比赛结果的记录由六位二进制数构成。
老王的儿子小王是一个多才多艺的程序员，他看到了老王的记分板开始了吐槽：由于比赛只有三位选手，只要其中两位选手的名次确定第三位选手的名次也就确定了。因此第三组二进制数完全是没有必要的（我们也称它为冗余），老王只需要四位二进制数就能表示全部的信息。
老王十分羞愧，忙请教小王能否更加简洁。小王想了想，把所有六种可能的结果罗列了出来，并给每种情况赋予了一个代号，比如001表示甲乙丙的结果，010表示甲丙乙的结果……这样老王每次就只需要三位二进制数（3比特）就可以记录原本要6比特才能表示的信息了。这个故事告诉我们，同样的信息用不同形式描述，会产生长度不同的记录（我们称之为消息），因此无损压缩是可能的。这也是清晰度差不多的视频文件有的格式卡成狗有的格式却十分流畅的原因。
故事的最后，老王贪心不足，希望用更短的消息来记录比赛结果，然而多次尝试之后可耻的失败了。这是因为比赛结果的熵是log2(6)，大约是2.58，因此至少需要3位二进制数（3比特）才能描述，即消息不可能比它所包含的信息更短。也就是说无损压缩有其极限，判断这个极限是信息熵的另一个应用。
四、总结
好了，我们现在总结一下，并试着回答题主的问题。
- 1.热力学熵有两个表述，即宏观形式和微观形式，它们的意义和表达式都不同，然而却被证明是等价的。
- 2.热力学熵的宏观描述的直接意义是能量中不能用来做功的那一部分，可以用来描述能量的优劣。
- 3.热力学熵的微观描述直接反映了体系的混乱（无序）程度。
- 4.信息熵（香农熵）描述观测者对未知事件的不确定性，也表示未知事件可能含有的信息量。
那么信息熵和热力学熵有什么区别和联系呢？
首先要说的是，信息熵和热力学熵是完全不同的两个概念。它们形成于不同的理论体系中，无论含义、量纲、研究对象、作用都不相同。据我所知，目前也没有成熟的理论揭示二者有实质上的联系。
那么为什么许多人把这两者联系在一起呢？我想最重要的原因就是二者的数学表达式实在太像了，以至于它们在数学上的性质也很类似，甚至可以把统计力学中研究热力学熵的方法直接移植到信息论中研究信息熵，这导致了“信息热力学”的建立。
其实除了信息熵之外，生态学家和社会学家也借鉴热力学熵，在各自领域中提出了类似概念。
看到有同学在追问，补充几点：
1.我们理解一个概念时不应脱离产生这个概念的并使之发挥作用的理论体系。比如脱离热力学的框架谈热力学熵，或者脱离信息论的框架谈论信息熵在逻辑上都是脆弱的。
2.如果要证明二者是一回事，不能只看形式是否相似，而是要通过严格的理论证明。而做到这一点的前提是必须有一套理论体系能够把二者都包括进去。比如热力学熵的两种形式等价是严格的理论计算证明了的，于是热力学和统计力学也就变成了一门统一的学科。而目前信息论和热力学并没有统一的迹象。
3.前排回答中的某些计算，在我看来很明显是错误的。比如抛硬币的那个例子：原答主计算“抛硬币”系统的玻尔兹曼熵和香农熵，并认为二者是相等的。然而玻尔兹曼公式中的Ω意义很明确，就是微观状态数。它由系统的结构、温度、体积、质量等因素决定，是一个客观的物理量（它的取值不依赖于观测者）。而“抛硬币”是一个抽象的逻辑模型，显然不具有这些性质，因此根本无法计算它的热力学熵。说得更普遍些：你无法计算一个逻辑模型的热力学熵，同样也无法计算热力学系统的信息熵（因为缺乏明确的观测者和观测标准）。这也是为什么说上面第一点很重要的原因。其次，这个计算中该答主将玻尔兹曼常数遗漏了，以至于竟得出了以比特为量纲的“热力学熵”。
4.有人说玻尔兹曼熵是信息熵的上限。这个说法在哲学上也许是正确的，但它目前似乎也只有哲学上的意义。
三、【H.264/AVC视频编解码技术详解】七、 熵编码算法（1）：基础知识
- 熵编码概念
“熵”这一概念原本来自于化学和热力学，用于度量能量退化的指标，即熵越高，物体或系统的做功能力越低。后来香农将这一概念引入到信息论中，用于表示消息的平均信息量。信源的熵通常可以表示信源所发出信息的不确定性，即越是随机的、前后不相关的信息，其熵越高。
在信息论中，香农提出了信源编码定理。该定理说明了香农熵与信源符号概率之间的关系，说明信息的熵为信源无损编码后的平均码字长度的下限。任何的无损编码方法都不可能使编码后的平均码长小于香农熵，只能使其尽量接近。
基于此，对信源进行熵编码的基本思想，是使其前后的码字之间尽量更加随机，尽量减小前后的相关性，更加接近其信源的香农熵。这样在表示同样的信息量时所用的数据长度更短。
（插入参考三分钟学习 | 熵编码）
那什么是熵编码？在信息熵的极限范围内进行编码就是熵编码。例如信息熵算出来是3bit/字符，你用4bit/字符来编码，就是熵编码，你用2bit/字符来编码，就不叫熵编码，因为这种情况下，就失真了嘛。从这里也看以看出，信源熵是编码这个信源平均所需要的最小位数。所以，熵编码是无损压缩。
熵编码有很多种：
- 霍夫曼编码 （Huffman）
- 算术编码
- 行程编码 （RLE）
- 基于上下文的自适应变长编码（CAVLC）
- 基于上下文的自适应二进制算术编码（CABAC）
在实际使用中，常用的熵编码主要有变长编码和算术编码等方法。其中变长编码相对于算术编码较为简单，但平均压缩比可能略低。常见的变长编码方法有哈夫曼编码和香农-费诺编码等。例如JPEG用的是Huffman编码和算术编码，H264用的是CAVLC和CABAC。
- 熵编码的简单实现——哈夫曼编码
戴维·哈夫曼（David·A·Huffman）于1952年在麻省理工学院的罗伯特·费诺的指导下攻读博士学位时，发明了一种基于有序频率二叉树的编码方法，该方法的编码效率超过了他的导师和信息论之父香农的研究成果（香农-费诺编码），因此又称作“最优编码方法”。
哈夫曼编码时变长编码方法的一种，该方法完全依赖于码字出现的概率来构造整体平均长度最短的编码方法。进行哈夫曼编码的关键步骤是建立符合哈夫曼编码规则的二叉树，该树又称作哈夫曼树。
哈夫曼树是一种特殊的二叉树，其终端节点的个数与待编码的码元的个数等同，而且每个终端节点上都带有各自的权值。每个终端节点的路径长度乘以该节点的权值的总和称为整个二叉树的加权路径长度。在满足条件的各种二叉树中，该路径长度最短的二叉树即为哈夫曼树。
在使用哈夫曼编码执行对码元的实际编码过程时，码元的权值可设置为其概率值，那么可以根据其权值来构建哈夫曼树。我们假设使用哈夫曼编码对以下概率的码字进行编码：
| 码字 | 概率 |
|---|---|
| A | 0.1 |
| B | 0.1 |
| C | 0.15 |
| D | 0.2 |
| E | 0.2 |
| F | 0.25 |
根据概率表构建哈夫曼树的过程如下图所示：
image.png
最终我们可以得到如下图所示的哈夫曼树：
image.png
在哈夫曼树构建完成后，便可以得到每一个码元的哈夫曼编码的码字。具体方法是：从哈夫曼树的根节点开始遍历，直至每一个终端节点，当访问某个节点的左子树时赋予码字0，访问右子树时赋予一个码字1（反之亦可），直到遍历到终端节点时这一路径所代表的0和1的串便是该码元的哈夫曼编码码字。
例如上图的哈夫曼树，根节点访问左子树ABCF，赋予码字0；然后再访问左子树ABC，赋予码字0，此时整个码字为00，然后访问右子树得到终端节点C，赋予码字1，此时便可以得到C的哈夫曼编码码字001。以此规律，整个六个元素的码元集合的编码码表为：
| 码字 | 编码 |
|---|---|
| A | 0000 |
| B | 0001 |
| C | 001 |
| D | 10 |
| E | 11 |
| F | 01 |
从这个码表中还可以看出另外一个规律：哈夫曼编码的任意一个码字，都不可能是其他码字的前缀。因此通过哈夫曼编码的信息可以紧密排列连续传输，而不用担心解码时的歧义性。
缺点：
- 数据的概率变化难于实时统计
- Huffman树需要编码传输给解码器（对信源进行哈夫曼编码后，形成一个哈夫曼编码表，解码时，必须参照这一哈夫曼编码表才能正确解码）
- 只有在
时是最优编码（由于哈夫曼编码的依据是信源符号的概率分布，故其编码效率取决于信源的统计特性。当信源符号的概率相等时，其编码效率最低；只有在概率分布很不均匀时，哈夫曼编码才会收到显著效果；当符号出现概率分布为
型时，哈夫曼编码能使平均码长降奥信源熵值H(x)，编码效率为100%）
- 最小码字长度为1比特/符号
四、【H.264/AVC视频编解码技术详解】八、 熵编码算法（2）：H.264中的熵编码基本方法、指数哥伦布编码
指数哥伦布编码同哈夫曼编码最显著的一点不同在于，哈弗曼编码构建完成后必须在传递的信息中加入码字和码元值的对应关系，也就是编码的码表，而指数哥伦布编码则不需要。
1.先看例子，再说概念：
使用指数哥伦布编码来表示数值codeNum = 10，那么其前缀0的长度为prefixLen = floor[log2(codeNum+1)] = 3，因此指数哥伦布码的前缀为 0 0 0。其后缀部分的二进制表示为codeNum+1-2^prefixLen = 11-8 = 3 = b(0 1 1)，因此10的指数哥伦布编码码字为0 0 0 1 0 1 1。
也就是说，哥伦布编码以中间的1为对称轴，前缀全写0，需要先算出一共要写几个0。然后再算后缀的信息位，上面使用的公式暂时先不解释。
看一下怎么还原：当读取到指数哥伦布编码码字为0 0 0 1 0 1 1时，先计算前缀个数是3，然后越过中间的1，得到后缀信息位是二进制的011，也就是十进制的3。那么解码值就是2^3-1+3=10
使用以上技巧再看下20的编码：
codeNum = 20
prefixLen = floor[log2(codeNum+1)] = floor[log2(21)]=4
surfix = codeNum+1-2^prefixLen=20+1-2^4=5=二进制的101
编码值=0000，1，0101(为方便观看，以逗号分隔了)
看一下解码：
前缀4个0，后缀信息位0101，也就是5。所以2^4-1+5=20
2.概念
在H.264的标准协议中，不同的语法元素指定了不同的熵编码方法。在协议文档中共指定了10种语法元素的描述符，这些描述符表达了码流解析为语法元素值的方法，其中包含了H.264标准所支持的所有熵编码方法：
| 语法元素描述符 | 编码方法 |
|---|---|
| b(8) | 8位二进制比特位串，用于描述rbsp_byte() |
| f(n) | n位固定模式比特位串，从最左bit开始计算 |
| u(n) | 使用n位无符号整数表示，由n位bit换算得到 |
| i(n) | 使用n位有符号整数表示，由n位bit换算得到 |
| ue(v) | 使用无符号指数哥伦布编码 |
| se(v) | 使用有符号指数哥伦布编码 |
| te(v) | 使用截断指数哥伦布编码 |
| me(v) | 使用映射指数哥伦布编码 |
| ce(v) | 上下文自适应的变长编码 |
| ae(v) | 上下文自适应的二进制算术编码 |
常用的指数哥伦布编码通常可以分为四类：ue(v)、se(v)、me(v)、te(v)。其中无符号指数哥伦布编码ue(v)是其他编码方式的基础，其余几种方法基本可以由ue(v)推导得出。
3.指数哥伦布编码同哈夫曼编码的比较
指数哥伦布编码同前文中提到的哈夫曼编码都遵循了同一规律，即针对不同的码元分配了bit位长度不同的码字，因此各自都属于变长编码的一种。然而二者仍然具有较大的差别，具体如：
-
哈夫曼编码在编码过程中考虑了信源各个符号的概率分布特性，根据符号的概率分布进行编码，因此对于不同的信源，即使是相同的符号的哈夫曼编码的结果也是不同的；指数哥伦布编码针对不同的信源采用的编码是统一的，因此无论是什么样的输入，输出的编码后的数据都是一致的。
-
由于哈夫曼编码是针对信源特性进行的编码，因此在存储或传输编码后的数据之前必须在前面保存一份码表供解码段重建原始信息使用；而指数哥伦布编码不需要存储任何额外信息就可以进行解码。
-
由于未考虑信源的实际特性，指数哥伦布编码的压缩比率通常比较低，对于有些信息甚至完全没有压缩效果，输出数据比原始数据更大，在这一点上哈夫曼编码作为“最优编码”在效率上更高；然而由于哈夫曼编码运算较指数哥伦布编码更为复杂，且必须保存码表信息增加了传输负荷，也对压缩比率造成了不利影响。
实际上，对于视频压缩这样的需求而言，类似于哈夫曼编码所提供的压缩比率的优势远远不够，而且像H.264等编码标准都不会指望靠这样的方式来提高压缩比率。
在H.264码流结构（如NAL Unit、Slice Header等）的解析中，大多使用定长编码或者指数哥伦布编码实现。而例如预测残差等占据码流大量体积的数据则必须使用压缩率更高的算法，如CAVLC和CABAC等。
