跳转到内容

格伦布编码

维基百科,自由的百科全书

格伦布编码(英语:Golomb coding)是一种无失真资料压缩方法,由数学家所罗门·格伦布在1960年代提出。其优点为易于编码与解码,另外对于拥有几率分布为几何分布的资料,格伦布编码是最佳的前缀码,且能无限逼近该资料的,目前广泛用于无损影像压缩

编码的建立

[编辑]

令输入值为正整数,参数值为正整数 ,输出值格伦布码为 ,其中 由两种编码组合而成,

一进制编码,截断二进制编码

计算

一进制编码,截断二进制编码即可得到

格伦布-莱斯编码中的商数指示了所在区块,而指示所在区块内部的位置。如上图,对整数 做格伦布-莱斯编码, 代表区块、 表示区块内部位置、 为参数,每个区块的大小皆相等且长度为 ,特别注意当编码方式为格伦布-莱斯编码时,即 的整数次方,所有编码长度相等。

参数 伯努利过程的函数,其中伯努利过程的参数 定义为 ,则 的所在区间为此伯努利过程中位数-1到中位数+1之间。如下式:

足够大时,我们可以将其表示成,

格伦布编码主要是针对非负整数进行编码,但也可以使用重叠(Overlap)与交错(Interleave)扩展至对所有整数进行编码。令一串用于编号的数列,(0,1,2,...),给予非负整数偶数编号,给予负整数奇数编号,使得排列方式如下,(0,-1,1,-2,2,...),即非负整数 映射,负整数 映射

莱斯编码

[编辑]

莱斯编码(Rice coding,由Robert F. Rice所提出),为一种前缀码,归属于格伦布编码的子集合,参数 的整数次方,即 。此种特例未必是所有格伦布编码中的最佳编码方式,但由于目前电脑为二进制运算,莱斯编码能快速且有效地以二进制运算实现。

性质

[编辑]

格伦布编码为一种范氏霍夫曼编码

算法

[编辑]
  1. 选择参数
  2. 待编码数值为 ,计算:
    1. 商数:
    2. 余数:
  3. 编码
    1. 商数编码,对 进行一进制编码,得到
    2. 余数编码,对 进行截断二进制编码,得到
    3. 合并,
  4. 输出

范例

[编辑]

M = 10。则 .

商数编码
q 输出位元
0 0
1 10
2 110
3 1110
4 11110
5 111110
6 1111110
N
余数编码
r 偏移 二进制 输出位元
0 0 0000 000
1 1 0001 001
2 2 0010 010
3 3 0011 011
4 4 0100 100
5 5 0101 101
6 12 1100 1100
7 13 1101 1101
8 14 1110 1110
9 15 1111 1111

选择42作为编码时,42会被拆成 ,编码为11110010,而商数编码尾数必为0,能标示商数编码位元的结束。

参考来源

[编辑]