Elias gamma編碼

以利亞加瑪碼(Elias gamma code)是一種用於正整數之通用編碼。該碼由Peter Elias發明。此編碼常被用於無法事先得知上界之正整數。

編碼

編輯

對於待編碼正整數 X≥1:

  1. N=⌊log2 X⌋ ,故 2NX < 2N+1
  2. 輸出 N 個零位元
  3. 接着輸出 X二進位表示。

另一個等價的編碼方式為:

  1. 輸出 N 的一進位表示
  2. 將餘下的 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

以利亞加瑪碼之解碼遵循下列步驟:

  1. 讀取並計數零位元直到第一個一位元出現,假設共有 N 個零位元出現
  2. 從第一個一位元之後,再讀取 N位元,並將之還原成十進位正整數,令之為 M
  3. 最終解碼為 2N+M

用途

編輯

以利亞加瑪碼最常見之用途為待編數之上界未知時,或是壓縮小數值較大數值頻繁之資料。以利亞加瑪碼可做為以利亞戴爾達碼之一部分。

一般化

編輯

以利亞加瑪碼並不適用於零或負整數。一個一般化的方式是在最左側先加一個一位元,解碼時再行扣掉。另一個方法是在編碼前將所有整數對映至正整數,例如:(0, 1, −1, 2, −2, 3, −3, ...) 對應至 (1, 2, 3, 4, 5, 6, 7, ...)。

參考項目

編輯