[科普中國]-以利亞加瑪碼

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

編碼對(duì)于待編碼正整數(shù):

1.令，故

2.輸出N個(gè)零比特

3.接著輸出X的二進(jìn)制表示

另一個(gè)等價(jià)的編碼方式為：

1.輸出 N 的一進(jìn)位表示

2.將余下的 N 個(gè)比特接在上述之后

要對(duì)X進(jìn)行編碼，以利亞戴爾達(dá)碼必須使用個(gè)比特。

以下為一編碼對(duì)照表：

|| ||

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

1.讀取并計(jì)數(shù)零比特直到第一個(gè)一比特出現(xiàn)，假設(shè)共有N出現(xiàn)

2.從第一個(gè)一比特之后，再讀取 N 個(gè)比特，并將之還原成十進(jìn)制正整數(shù)，令之為 M

3.最終解碼為

用途以利亞加瑪碼最常見之用途為待編數(shù)之上界未知時(shí)，或是壓縮小數(shù)值較大數(shù)值頻繁之?dāng)?shù)據(jù)。以利亞加瑪碼可做為以利亞戴爾達(dá)碼之一部分。

一般化以利亞加瑪碼并不適用于零或負(fù)整數(shù)。一個(gè)一般化的方式是在最左側(cè)先加一個(gè)一比特，解碼時(shí)再行扣掉。另一個(gè)方法是在編碼前將所有整數(shù)映射至正整數(shù)，例如：(0, 1, ?1, 2, ?2, 3, ?3, ...) 對(duì)應(yīng)至 (1, 2, 3, 4, 5, 6, 7, ...)。

本詞條內(nèi)容貢獻(xiàn)者為:

王沛 - 副教授、副研究員 - 中國科學(xué)院工程熱物理研究所