转载自：https://www.jianshu.com/p/f4f3b0764cec
上篇我们说过，学习描述子是解析h264句法元素的第一步。而在描述子中，除了顺序读取若干比特的b(8)、f(n)、i(n)、u(n)，指数哥伦布编码也是使用频率很高的编解码方法。

因为指数哥伦布编码(Exponential-Golomb)属于熵编码(Entropy encoding)，所以我们先大致介绍一下熵编码，然后再进行细化。

1 熵编码（Entropy encoding）

熵（shang）编码属于无损编码，它听着很高大上，其实简单来说，就是代表了一类编码方法。熵编码包括的编码方法有：香农-范诺编码、霍夫曼编码、算术编码、指数哥伦布编码、CAVLC、CABAC等，这一类编码方法的宗旨，就是找到一种编码，使得码字的平均码长达到熵极限。

具体实施起来就是，对出现概率较大的符号，取较短的码长，而对出现概率较小的符号取较大的码长。这就是熵编码的中心思想，只要我们记住这一点，即使不了解“熵”是指啥，也能掌握上述几种熵编码。

不过我们还是简单介绍一下，“熵”是指啥？

1.1 熵

熵在热力学中，是表示分子状态混乱程度的物理量，这时的熵称为热熵。后来信息论之父香农（C. E. Shannon）把“熵”这一词引入到信息论中，称为“信息熵”，信息越是随机，它的熵值越高。信息熵也是我们在h264这样的数字图像编码中使用的概念。因为我们待编码的图像像素信息、码流的各个句法元素值，其实都属于信息。

而信息熵，就是为了解决信息的量化度量问题，它描述了整个信源的平均信息量。信息熵在我们的熵编码中，表示了信源无损编码后平均码长的下限。所以我们上面才说，熵编码就是为了使编码后，码字的平均码长尽量达到熵极限。而且平均码长越接近熵，说明熵编码的压缩效率越高。

1.2 熵和熵编码

如果第一次接触熵，确实不好理解。因为它不仅涉及到信息学的知识，还有概率论的知识。不过虽然熵不好理解，但是熵编码很好掌握。熵其实就相当于内功，而熵编码是招式。待我们学过熵编码，再来理解熵，就容易多了。

1.3 熵编码分类

为了便于理解，上述说的多个熵编码方法，还可以分为以下两类：

（1）变长编码：香农范诺编码、霍夫曼编码、指数哥伦布编码、CAVLC

（2）算术编码、CABAC等算术编码

而且这些熵编码方法中，在H.264中应用的有：指数哥伦布编码、CAVLC、算术编码、CABAC。

2 指数哥伦布编码（编码过程）

指数哥伦布编码是一种较简单的编码方法，正常来说，它可以拓展至K阶，也即K阶指数哥伦布编码。而在H.264中使用的，是0阶指数哥伦布编码，也即K等于0。下面我们就重点介绍0阶指数哥伦布编码，理解了0阶，K阶自然而然就懂了。

值得注意的是，在H.264中，0阶指数哥伦布编码，对应的描述子是ue(v)。只不过ue(v)代表的是解码过程，而我们下面先从编码开始。

2.1 0阶指数哥伦布编码

这个编码过程如下图所示：

image

0阶指数哥伦布编码过程

图中应该写的很清楚，我们以待编码码号code_num = 3为例：

第一步：将code_num +1, 即3+1 = 4

第二步：将4写为二进制的形式：100

第三步：计算100的比特个数为3，在100前面写（3-1）个0，得到编码码字：00100

并且图中背景为灰色区域，表示连续的码字长度一样，总结起来如下：

image

0阶码号与码字总结

可以看到，码字的结构形式可以表示为，中间比特为1，两端比特个数对称的平衡结构：

[N个0][1][INFO] 或者 [Prefix 前缀][1][Suffix 后缀]

2.2 K阶指数哥伦布编码

由上述的0阶，我们可以轻松拓展至K阶，还是刚才那个步骤，只不过将第一步稍微改变一下：

（1）K阶的第一步：将code_num 加上2^k

（2）将code_num + 2^k 写为二进制的形式

（3） 计算二进制的比特个数 M，并在前面加上M-1个0，得到编码码字。

如果要验证一下，则将k=0代入上述步骤，就可以得到0阶编码的码字。比如以K=0、K=1、K=2或K=3举例如下：

image

K阶指数哥伦布编码举例

表中x即为上述的待编码码号code_num。

3 指数哥伦布编码（解码过程）

讲过了编码过程，我们就从解码过程考虑考虑，这一过程描述在h264协议的9.1节，这也是我们今天的重点。因为H.264中的描述子，代表了解码过程。所以下面我们就以描述子为主线，依次介绍H.264中的4个指数哥伦布编码描述子：ue(v)、se(v)、me(v)、te(v)。

3.1 ue(v)

在h264中，ue(v)就代表了0阶指数哥伦布编码，通常被称为无符号指数哥伦布编码。对比我们上述的0阶编码过程，我们可以反过来研究研究解码过程。如下图：

image

ue(v)解码

如图，如果我们仔细观察推理，就会发现码字和code_num之间，有以下公式：

codeNum = 2^{leadingzerobits} − 1 + read_bits( leadingZeroBits )

其中leadingZeroBits为中间1前面，0的个数。所以在解码的时候，如果遇到描述子为ue(v)，则可以先数0的个数，数到1为止，其中0的个数即为leadingZeroBits。而公式中的read_bits( leadingZeroBits )，则为从中间1开始，往后顺序数leadingZeroBits个比特位。

利用上述公式，就可以计算出codeNum的值。

所以上表的解码过程为：

image

ue(v)解码过程

当描述子为ue(v)时，codeNum的值即为语法元素的值。

3.2 se(v)

se(v)也称有符号指数哥伦布编码，所以当描述子为se(v)时，它的输出有可能为负。而且当描述子为se(v)时，它的输入为上述过程解析出来的codeNum。意思是什么呢？如果遇到se(v)，需要先调用ue(v)，得出codeNum的值。然后调用se(v)的解析过程，se(v)的输出即为语法元素的值。

image

se(v)的计算过程

如上表所示，表中第一列codeNum为输入，第二列为输出。计算公式则为：

语法元素值 = (−1)^k+1 Ceil( k÷2 )

式中Ceil为向上取整，k为codeNum的值，代入即可计算出语法元素的值。

3.3 me(v)

me(v)也称映射指数哥伦布编码，听着很高大上，其实就是拿着codeNum的值去查表。而且在H.264中，只有语法元素coded_block_pattern的值，是使用me(v)解析的。

而且当句法元素ChromaArrayType的值为1或2时，查表a。ChromaArrayType的值为0或3时，查表b。当宏块预测模式为Intra_4x4（帧内4x4）、Intra_8x8（帧内8x8）或者Inter（帧间编码）时，输出的coded_block_pattern的值也不同。

部分a表如下：

image

me(v) 表（a）部分数据

注意输入为codeNum，输出为coded_block_pattern的值。

3.4 te(v)

te(v)也称截断（舍位）指数哥伦布编码，之所以这么说呢，是因为它的编码分为两段。在H.264协议中，只有7.3.5.1节的宏块预测和7.3.5.2节的子宏块预测中，使用这种模式编码，我们先看看它的编码过程。

3.4.1 te(v)编码过程

编码时：

如果语法元素的值为0，则编码为1，如果语法元素值为1，则编码为0，此时占用1个比特位。

如果语法元素的值大于1，则使用ue(v)进行编码。

3.4.2 te(v)解码过程

知道了编码过程，解码过程就好理解了。解码时，需要先判断语法元素值的取值范围的上限，其中取值范围为[0，x]。

如果上限值x大于1，那么te(v)的输出，也即语法元素的值，和ue(v)的输出相同。

否则上限值x等于1，那么te(v)的输出，也即语法元素的值，等于读入下一位比特值的取反，也即：

b = read_bits( 1 )

codeNum = !b

其中codeNum为te(v)输出值，也即语法元素值。

4 总结

其实由上面的分析，就可以看出，指数哥伦布编码的压缩率其实是比较低的，有时候甚至没有压缩效果。所以指数哥伦布编码在H.264中，主要应用在部分语法元素的编解码和二值化（将语法元素的值转为二进制），而在h264中压缩比比较高的熵编码方法，是还未介绍的CAVLC和CABAC。