Elias gamma編碼

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

 編碼 
對於待編碼正整數 X≥1：
 令 N=⌊log2 X⌋ ，故 2N ≤ X < 2N+1
 輸出 N 個零位元
 接著輸出 X 的二進位表示。

另一個等價的編碼方式為：
 輸出 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

 解碼 
以利亞加瑪碼之解碼遵循下列步驟：
 讀取並計數零位元直到第一個一位元出現，假設共有 N 個零位元出現
 從第一個一位元之後，再讀取 N 個位元，並將之還原成十進位正整數，令之為 M
 最終解碼為 2N+M

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

 一般化 
以利亞加瑪碼並不適用於零或負整數。一個一般化的方式是在最左側先加一個一位元，解碼時再行扣掉。另一個方法是在編碼前將所有整數映射至正整數，例如：(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

Category:数字
Category:无损压缩算法