以利亞加瑪碼（Elias gamma code）是一種用於正整數之通用編碼。該碼由Peter Elias發明。此編碼常被用於無法事先得知上界之正整數。
基本介紹
- 中文名：以利亞加瑪碼
- 外文名：Elias gamma code
- 發明人：Peter Elias
編碼,解碼,用途,一般化,
編碼
對於待編碼正整數
:
1.令
，故
2.輸出N個零比特
3.接著輸出X的二進制表示
另一個等價的編碼方式為：
1.輸出 N 的一進位表示
2.將餘下的 N 個比特接在上述之後
要對X進行編碼，以利亞戴爾達碼必須使用
個比特。
以下為一編碼對照表：
| 數 | 二進制表示 | 加瑪編碼 | 代表之機率 |
|---|---|---|---|
1 = 2+ 0 | 1 | 1 | 1/2 |
2 = 2+0 | 1 0 | 0 1 0 | 1/8 |
3 = 2+1 | 1 1 | 0 1 1 | 1/8 |
4 = 2+0 | 1 00 | 00 1 00 | 1/32 |
5 = 2+1 | 1 01 | 00 1 01 | 1/32 |
6 = 2+2 | 1 10 | 00 1 10 | 1/32 |
7 = 2+3 | 1 11 | 00 1 11 | 1/32 |
8 = 2+0 | 1 000 | 000 1 000 | 1/128 |
9 = 2+1 | 1 001 | 000 1 001 | 1/128 |
10 = 2+2 | 1 010 | 000 1 010 | 1/128 |
11 = 2+3 | 1 011 | 000 1 011 | 1/128 |
12 = 2+4 | 1 100 | 000 1 100 | 1/128 |
13 = 2+5 | 1 101 | 000 1 101 | 1/128 |
14 = 2+6 | 1 110 | 000 1 110 | 1/128 |
15 = 2+7 | 1 111 | 000 1 111 | 1/128 |
16 = 2+0 | 1 0000 | 0000 1 0000 | 1/512 |
17 = 2+1 | 1 0001 | 0000 1 0001 | 1/512 |
解碼
以利亞加瑪碼之解碼遵循下列步驟：
1.讀取並計數零比特直到第一個一比特出現，假設共有N出現
2.從第一個一比特之後，再讀取 N 個比特，並將之還原成十進制正整數，令之為 M
3.最終解碼為
用途
以利亞加瑪碼最常見之用途為待編數之上界未知時，或是壓縮小數值較大數值頻繁之數據。以利亞加瑪碼可做為以利亞戴爾達碼之一部分。
一般化
以利亞加瑪碼並不適用於零或負整數。一個一般化的方式是在最左側先加一個一比特，解碼時再行扣掉。另一個方法是在編碼前將所有整數映射至正整數，例如：(0, 1, −1, 2, −2, 3, −3, ...) 對應至 (1, 2, 3, 4, 5, 6, 7, ...)。
