Elias gamma编码

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

编码

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

1. 令 N=⌊log₂ X⌋ ，故 2^N ≤ X < 2^N+1
2. 输出 N 个零位元
3. 接着输出 X 的二进制表示。

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

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

要对 $x$ 进行编码，以利亚戴尔达码必须使用 $2\lfloor \log _{2}(x)\rfloor +1$ 个位元。

以下为一编码对照表：

数	二进制表示	加玛编码	代表之概率
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. 最终解码为 2^N+M

用途

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

一般化

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

参考项目

• Elias, Peter (March 1975). "Universal codeword sets and representations of the integers". IEEE Transactions on Information Theory 21 (2): 194–203.
• Classical and Quantum Information Theory: An Introduction for the Telecom ...（页面存档备份，存于互联网档案馆）
• A Concise Introduction to Data Compression（页面存档备份，存于互联网档案馆）
• Data Compression: The Complete Reference（页面存档备份，存于互联网档案馆）