【视频编解码·学习笔记】9. 熵编码算法：指数哥伦布编解码程序
一、解码程序：
整体思路：
- 在数据流中从左向右读取每一个二进制数据
- 记录前缀连零的个数\(m\)，遇到1停止记录。并提取后缀信息位（信息位长度与前缀0个数相同）
- 将后缀二进制转换成十进制数\(k\)
- 解码数值：\(decodeNum = 2^m – 1 + k\)
- 重复步骤1-4，直到数据序列结束
新建一个VS工程，定义数据类型：
typedef unsigned char UINT8;
定义一个数组用来存储待解码的数据：
UINT8 strArray[6] = { 0xA6, 0x43, 0x98, 0xE2, 0x04, 0x8A };
1. 提取每一位二进制函数：
需要三个参数：待解码数据序列buf，解码到第几个字节bytePosition，第几位bitPosition （都是从左向右数的，每个字节自第一位bitPosition=0，最后一位bitPosition=7）
static int get_bit_at_position(UINT8 *buf, UINT8 &bytePosition, UINT8 &bitPosition){UINT8 mask = 0, val = 0;// mask用来表示提取第几位的数据，eg:0001 0000，表示提取第5位的数据mask = 1 << (7 - bitPosition);// 将当前字节数据与mask进行按位与运算，只保留那一位上的数据，整体数据!=0表明那一位数据为1// val保存bytePosition上，第bitPosition的值val = ((buf[bytePosition] & mask) != 0);// 如果读到字节末尾，修改两个Position的值if (++bitPosition > 7){bytePosition++;bitPosition = 0;}return val;}
2. 解码部分：
参照公式：\(decodeNum = 2^m – 1 + k\)，\(m\)为前面0的个数，\(k\)为后缀二进制对应十进制的值
static int get_uev_code_num(UINT8 *buf, UINT8 &bytePosition, UINT8 &bitPosition){assert(bitPosition < 8);UINT8 val = 0, prefixZeroCount = 0; //存储每一位的数值； 前缀0的个数int prefix = 0, surfix = 0, decodeNum = 0;//统计前缀0的个数while (true){val = get_bit_at_position(buf, bytePosition, bitPosition);if (val == 0){prefixZeroCount++;}else{break;}}// 表示计算公式中 2^m - 1 部分prefix = (1 << prefixZeroCount) - 1;// 计算后缀中二进制转十进制部分 kfor (size_t i = 0; i < prefixZeroCount; i++){val = get_bit_at_position(buf, bytePosition, bitPosition);surfix += val*(1 << (prefixZeroCount - i - 1));}decodeNum = prefix + surfix;return decodeNum;}
3. 修改主函数
int _tmain(int argc, _TCHAR* argv[]){UINT8 strArray[6] = { 0xA6, 0x43, 0x98, 0xE2, 0x04, 0x8A };UINT8 bytePosition = 0, bitPosition = 0;// 保存bit数据长度UINT8 dataLengthInBits = sizeof(strArray) * 8;// 保存解码后的数据int decodeNum = 0;while ((bytePosition * 8 + bitPosition) < dataLengthInBits){decodeNum = get_uev_code_num(strArray, bytePosition, bitPosition);printf("ExpColumb codeNum = %d\n", decodeNum);}return 0;}
运行结果如下：
二、编码程序：
定义待编码数组，及编码后存储的数组：
UINT8 oriNumArray[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; // 带编码数组UINT8 encodeArray[6] = { 0 }; // 存储指数哥伦布编码后的结果
整体思路：
以codeNum = 13为例，
① 前缀0的个数：\(prefixLen = floor[log_2(codeNum+1)] = 3\)；
② 中间添加一个 1
③ 后缀部分的二进制：\(codeNum+1-2^{prefixLen} = 14-8 = 6 = b(1 1 0)\)
因此13的指数哥伦布编码码字为0 0 0 1 1 1 0。
1. 编码部分：
与解码部分相同，使用了bytePosition和bitPosition表示写入位置。
【使用按位或的方式，按位写入每一位数据】
例如：该写某一字节code的第五位，这一个字节为 1101 0000，要在第五位上写入1（0同理），
创建一个mask -> 0000 1000，将code这个字节与mask进行按位或运算，即可将1写入到第五位上
code | mask = 1101 1000
static void encode_uev_array(UINT8 *encodeArray, UINT8 codeNum, UINT8 &bytePosition, UINT8 &bitPosition){// 前缀0int preZeroLen = floor(log(codeNum + 1) / log(2));bitPosition = bitPosition + preZeroLen;if (bitPosition > 7){bytePosition++;bitPosition = bitPosition % 8;}// 中间1UINT8 mask = 1 << (7 - bitPosition);encodeArray[bytePosition] = encodeArray[bytePosition] | mask;if (++bitPosition > 7){bytePosition++;bitPosition = 0;}// 后缀二进制int surDecNum = codeNum + 1 - pow(2, preZeroLen);dec_to_bin(encodeArray, surDecNum, bytePosition, bitPosition, preZeroLen);}
2. 十进制转二进制：
static void dec_to_bin(UINT8 *encodeArray, UINT8 decNum, UINT8 &bytePosition, UINT8 &bitPosition, int preZeroLen){if (preZeroLen == 0){return;}// 转换二进制用的maskUINT8 maskBin = 1 << (preZeroLen - 1);// 按位写数据用的maskUINT8 maskVal;UINT8 val = 0;// 写入二进制后缀for (size_t i = 0; i < preZeroLen; i++){val = (decNum & maskBin ? 1 : 0);maskVal = val << (7 - bitPosition);encodeArray[bytePosition] = encodeArray[bytePosition] | maskVal;if (++bitPosition > 7){bytePosition++;bitPosition = 0;}maskBin = maskBin >> 1;}}
3. 主函数：
UINT8 encodeArray[6] = { 0 };UINT8 bytePosition = 0, bitPosition = 0;UINT8 oriNumArray[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };UINT8 oriNumLen = sizeof(oriNumArray) / sizeof(UINT8);for (size_t i = 0; i < oriNumLen; i++){encode_uev_array(encodeArray, oriNumArray[i], bytePosition, bitPosition);printf("%d \n", bitPosition);*/}for (size_t k = 0; k < 6; k++){printf("%x ", encodeArray[k]);}
运行结果如下，与第一部分中待解码数组中数据相同，证明编解码部分程序能正确执行。
版权声明：本文为shuofxz原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。