格伦布编码

无损数据压缩方法

格伦布编码(英语: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,能标示商数编码位元的结束。

参考来源