【H.264/AVC视频编解码技术详解】八、 熵编码算法（2）：H.264中的熵编码基本方法、指数哥伦布编码

《H.264/AVC视频编解码技术详解》视频教程已经在“CSDN学院”上线，视频中详述了H.264的背景、标准协议和实现，并通过一个实战工程的形式对H.264的标准进行解析和实现，欢迎观看！

“纸上得来终觉浅，绝知此事要躬行”，只有自己按照标准文档以代码的形式操作一遍，才能对视频压缩编码标准的思想和方法有足够深刻的理解和体会！

链接地址：H.264/AVC视频编解码技术详解

GitHub代码地址：点击这里

本节视频免费

1. H.264中的熵编码基本方法

在成功从NAL Unit中获取到语法元素的码流之后，接下来就是对语法元素的码流进行解析。根据我们在前面的博文中所讲述的H.264编码框架图，经过预测、变换量化等步骤后得到的H.264语法元素将通过熵编码器压缩为符合标准的H.264码流。因此，为了还原各个语法元素，必须对码流使用熵编码的解码器进行解码。

在H.264的标准协议中，不同的语法元素指定了不同的熵编码方法。在协议文档中共指定了10种语法元素的描述符，这些描述符表达了码流解析为语法元素值的方法，其中包含了H.264标准所支持的所有熵编码方法：

2. 指数哥伦布编码

同上篇介绍的哈夫曼编码一样，指数哥伦布编码同样属于变长编码(VLC)的一种。指数哥伦布编码同哈夫曼编码最显著的一点不同在于，哈弗曼编码构建完成后必须在传递的信息中加入码字和码元值的对应关系，也就是编码的码表，而指数哥伦布编码则不需要。

(1). 指数哥伦布编码的分类

如上表指出，常用的指数哥伦布编码通常可以分为四类：

• ue(v)：无符号指数哥伦布编码;
• se(v)：有符号指数哥伦布编码；
• me(v)：映射指数哥伦布编码；
• te(v)：截断指数哥伦布编码；

其中无符号指数哥伦布编码ue(v)是其他编码方式的基础，其余几种方法基本可以由ue(v)推导得出。本文先从ue(v)来讲述指数哥伦布算法的原理，而后再看如何推导至其他编码方法。

(2). 无符号指数哥伦布编码ue(v)

ue(v)的码字可以分为三个部分：[prefix] 1 [surfix]。其中前缀码为n个bit长度的0，后缀码为表示实际数值的信息位，信息位的长度为前缀码中0的个数。指数哥伦布编码中前缀和后缀部分的长度根据码元数值来确定：

在上标中编码模板的后缀部分，xx以二进制的形式表示解码后的数值。前缀0的长度以LeadingZeroBits表示，那么解码后数值为：codeNum = 2^LeadingZeroBits - 1 + (xxx)。(xxx)为二进制数值xxx的10进制表示。因此，指数哥伦布编码的码字与码元值的对应关系如下表：

例如，当使用指数哥伦布编码来表示数值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。

又例如，当读取到指数哥伦布码0 0 0 0 1 0 1 0 1时，首先计算前缀0的个数，此处为4，然后越过中间的1，读取后面的0 1 0 1为后缀码。二进制0101表示为十进制为5，因此该指数哥伦布码解码后的数值为2^4-1+5 = 20。

无符号指数哥伦布编码是其余多种变形算法的基础，其余的比如有符号指数哥伦布编码、映射指数哥伦布编码、截断指数哥伦布编码都是由无符号指数哥伦布编码进一步处理得到的。

(3). 有符号指数哥伦布编码

有符号的指数哥伦布编码值是通过无符号的指数哥伦布编码的值通过换算得到的，其语法元素描述符为se(v)。每一个无符号指数哥伦布编码的数值通过固定的换算关系转换为有符号的值，其换算关系为：n = (-1)^(k+1) * Ceil(k/2)。下表表示了有符号和无符号指数哥伦布编码之间的换算关系：

(4). 截断指数哥伦布编码

截断指数哥伦布编码的语法元素描述符为te(v)。当语法元素以te(v)解码时，首先需要判断的是语法元素的取值范围，假定为[0, x], x≥1。根据x的取值情况，语法元素根据下面不同情况进行解析：

• 若x>1，解析方法同ue(v)相同；
• 若x=1，语法元素值等同于下一位bit值的取反。

(5). 映射指数哥伦布编码

映射指数哥伦布编码的描述符为me(v)，适用于预测模式为Intra_4x4, Intra_8x8或Inter的宏块的coded_block_pattern的编码。me(v)的映射方式并无指定的换算公式，通常由查表的方式进行。下表为H.264 spec文档的表9-4的一部分：

三. 指数哥伦布编码同哈夫曼编码的比较

指数哥伦布编码同前文中提到的哈夫曼编码都遵循了同一规律，即针对不同的码元分配了bit位长度不同的码字，因此各自都属于变长编码的一种。然而二者仍然具有较大的差别，具体如：

1. 哈夫曼编码在编码过程中考虑了信源各个符号的概率分布特性，根据符号的概率分布进行编码，因此对于不同的信源，即使是相同的符号的哈夫曼编码的结果也是不同的；指数哥伦布编码针对不同的信源采用的编码是统一的，因此无论是什么样的输入，输出的编码后的数据都是一致的。
2. 由于哈夫曼编码是针对信源特性进行的编码，因此在存储或传输编码后的数据之前必须在前面保存一份码表供解码段重建原始信息使用；而指数哥伦布编码不需要存储任何额外信息就可以进行解码。
3. 由于未考虑信源的实际特性，指数哥伦布编码的压缩比率通常比较低，对于有些信息甚至完全没有压缩效果，输出数据比原始数据更大，在这一点上哈夫曼编码作为“最优编码”在效率上更高；然而由于哈夫曼编码运算较指数哥伦布编码更为复杂，且必须保存码表信息增加了传输负荷，也对压缩比率造成了不利影响。

实际上，对于视频压缩这样的需求而言，类似于哈夫曼编码所提供的压缩比率的优势远远不够，而且像H.264等编码标准都不会指望靠这样的方式来提高压缩比率。因此在实际的视频编码方法中使用的是指数哥伦布编码，但是只作为少数的辅助语法元素的编码以及多数语法元素的二值化方法。真正贡献了高压缩比还需要后面详述的CAVLC和CABAC等。

四. 0阶无符号指数哥伦布编码的实现Demo

程序代码如下：

// ExpColum.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <assert.h>

typedef unsigned char UINT8;

static int get_bit_at_position(UINT8 *buf, UINT8 &bytePotion, UINT8 &bitPosition)
{
    UINT8 mask = 0, val = 0;

    mask = 1 << (7 - bitPosition);
    val = ((buf[bytePotion] & mask) != 0);
    if (++bitPosition > 7)
    {
        bytePotion++;
        bitPosition = 0;
    }

    return val;
}

static int get_uev_code_num(UINT8 *buf, UINT8 &bytePotion, UINT8 &bitPosition)
{
    assert(bitPosition < 8);
    UINT8 val = 0, prefixZeroCount = 0;
    int prefix = 0, surfix = 0;

    while (true)
    {
        val = get_bit_at_position(buf, bytePotion, bitPosition);
        if (val == 0)
        {
            prefixZeroCount++;
        }
        else
        {
            break;
        }
    }
    prefix = (1 << prefixZeroCount) - 1;
    for (size_t i = 0; i < prefixZeroCount; i++)
    {
        val = get_bit_at_position(buf, bytePotion, bitPosition);
        surfix += val * (1 << (prefixZeroCount - i - 1));
    }

    prefix += surfix;

    return prefix;
}

int _tmain(int argc, _TCHAR* argv[])
{
    UINT8 strArray[6] = { 0xA6, 0x42, 0x98, 0xE2, 0x04, 0x8A };
    UINT8 bytePosition = 0, bitPosition = 0;
    UINT8 dataLengthInBits = sizeof(strArray) * 8;

    int codeNum = 0;
    while ((bytePosition * 8 + bitPosition) < dataLengthInBits)
    {
        codeNum = get_uev_code_num(strArray, bytePosition, bitPosition);
        printf("ExpoColumb codeNum = %d\n", codeNum);
    }

    return 0;
}

该例程的详细解读请观看视频教程：H.264/AVC视频编解码技术详解