Elias gamma编码

以利亚加玛码（Elias gamma code）是一种用于正整数之通用编码。该码由Peter Elias发明。此编码常被用于无法事先得知上界之正整数。

编码

对于待编码正整数 X≥1：

  1. 令 N=⌊log2 X⌋ ，故 2N ≤ X < 2N+1
  2. 输出 N 个零比特
  3. 接着输出 X 的二进制表示。

另一个等价的编码方式为：

  1. 输出 N 的一进位表示
  2. 将余下的 N 个比特接在上述之后。

要对   进行编码，以利亚戴尔达码必须使用   个比特。

以下为一编码对照表：

数 二进制表示 加玛编码 代表之概率
1 = 20 + 0 1 1 1/2
2 = 21 + 0 1 0 0 1 0 1/8
3 = 21 + 1 1 1 0 1 1 1/8
4 = 22 + 0 1 00 00 1 00 1/32
5 = 22 + 1 1 01 00 1 01 1/32
6 = 22 + 2 1 10 00 1 10 1/32
7 = 22 + 3 1 11 00 1 11 1/32
8 = 23 + 0 1 000 000 1 000 1/128
9 = 23 + 1 1 001 000 1 001 1/128
10 = 23 + 2 1 010 000 1 010 1/128
11 = 23 + 3 1 011 000 1 011 1/128
12 = 23 + 4 1 100 000 1 100 1/128
13 = 23 + 5 1 101 000 1 101 1/128
14 = 23 + 6 1 110 000 1 110 1/128
15 = 23 + 7 1 111 000 1 111 1/128
16 = 24 + 0 1 0000 0000 1 0000 1/512
17 = 24 + 1 1 0001 0000 1 0001 1/512

解码

以利亚加玛码之解码遵循下列步骤：

  1. 读取并计数零比特直到第一个一比特出现，假设共有 N 出现
  2. 从第一个一比特之后，再读取 N 个比特，并将之还原成十进制正整数，令之为 M
  3. 最终解码为 2N+M

用途

以利亚加玛码最常见之用途为待编数之上界未知时，或是压缩小数值较大数值频繁之资料。以利亚加玛码可做为以利亚戴尔达码之一部分。

一般化

以利亚加玛码并不适用于零或负整数。一个一般化的方式是在最左侧先加一个一比特，解码时再行扣掉。另一个方法是在编码前将所有整数映射至正整数，例如：(0, 1, −1, 2, −2, 3, −3, ...) 对应至 (1, 2, 3, 4, 5, 6, 7, ...)。

参考项目