以利亞加瑪碼

以利亞加瑪碼（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, ...)。