Elias gamma编码
![本页使用了标题或全文手工转换](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() |
以利亚加玛码(Elias gamma code)是一种用于正整数之通用编码。该码由Peter Elias发明。此编码常被用于无法事先得知上界之正整数。
编码
对于待编码正整数 X≥1:
另一个等价的编码方式为:
- 输出 N 的一进位表示
- 将馀下的 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 |
以利亚加玛码之解码遵循下列步骤:
用途
以利亚加玛码最常见之用途为待编数之上界未知时,或是压缩小数值较大数值频繁之资料。以利亚加玛码可做为以利亚戴尔达码之一部分。
一般化
以利亚加玛码并不适用于零或负整数。一个一般化的方式是在最左侧先加一个一位元,解码时再行扣掉。另一个方法是在编码前将所有整数映射至正整数,例如:(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(页面存档备份,存于互联网档案馆)
|