Elias gamma編碼
外观
![本页使用了标题或全文手工转换](http://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(页面存档备份,存于互联网档案馆)
|