查看“︁Elias gamma編碼”︁的源代码

{{多個問題|
{{Notability Unreferenced |time=2015-07-29T21:34:02+00:00}}
{{Disputed|time=2022-12-22T21:37:57+00:00}}
{{Rough translation|time=2022-12-22T21:37:57+00:00}}
}}
{{TA
|G1=IT
|G2=通訊學
|G3=Math
}}
'''以利亞加瑪碼'''（Elias gamma code）是一種用於[[自然数|正整數]]之通用[[編碼]]。該碼由Peter Elias發明。此編碼常被用於無法事先得知上界之正整數。

== 編碼 ==
對於待編碼正整數 ''X''≥1：
# 令 ''N''=&lfloor;log<sub>2</sub> ''X''&rfloor; ，故 2<sup>''N''</sup> ≤ ''X'' < 2<sup>''N''+1</sup>
# 輸出 ''N'' 個零[[位元]]
# 接著輸出 ''X'' 的[[二进制|二進位]]表示。

另一個等價的編碼方式為：
# 輸出 ''N'' 的一進位表示
# 將餘下的 ''N'' 個位元接在上述之後。

要對 <math>x</math> 進行編碼，以利[[亞戴爾達碼]]必須使用 <math>2 \lfloor \log_2(x) \rfloor  + 1</math> 個[[位元]]。

以下為一編碼對照表：

{| class=wikitable
! 數 !! 二進位表示 !! 加瑪編碼 !! 代表之機率
|-
| 1 = 2<sup>0</sup> + 0 || <code>1</code> || <code>1</code> || 1/2
|-
|colspan=4|
|-
| 2 = 2<sup>1</sup> + ''0'' || <code>1&thinsp;0</code> || <code>0&thinsp;1&thinsp;0</code> || 1/8
|-
| 3 = 2<sup>1</sup> + ''1'' || <code>1&thinsp;1</code> || <code>0&thinsp;1&thinsp;1</code> || 1/8
|-
|colspan=4|
|-
| 4 = 2<sup>2</sup> + ''0'' || <code>1&thinsp;00</code> || <code>00&thinsp;1&thinsp;00</code> || 1/32
|-
| 5 = 2<sup>2</sup> + ''1'' || <code>1&thinsp;01</code> || <code>00&thinsp;1&thinsp;01</code> || 1/32
|-
| 6 = 2<sup>2</sup> + ''2'' || <code>1&thinsp;10</code> || <code>00&thinsp;1&thinsp;10</code> || 1/32
|-
| 7 = 2<sup>2</sup> + ''3'' || <code>1&thinsp;11</code> || <code>00&thinsp;1&thinsp;11</code> || 1/32
|-
|colspan=4|
|-
| 8 = 2<sup>3</sup> + ''0'' || <code>1&thinsp;000</code> || <code>000&thinsp;1&thinsp;000</code> || 1/128
|-
| 9 = 2<sup>3</sup> + ''1'' || <code>1&thinsp;001</code> || <code>000&thinsp;1&thinsp;001</code> || 1/128
|-
| 10 = 2<sup>3</sup> + ''2'' || <code>1&thinsp;010</code> || <code>000&thinsp;1&thinsp;010</code> || 1/128
|-
| 11 = 2<sup>3</sup> + ''3'' || <code>1&thinsp;011</code> || <code>000&thinsp;1&thinsp;011</code> || 1/128
|-
| 12 = 2<sup>3</sup> + ''4'' || <code>1&thinsp;100</code> || <code>000&thinsp;1&thinsp;100</code> || 1/128
|-
| 13 = 2<sup>3</sup> + ''5'' || <code>1&thinsp;101</code> || <code>000&thinsp;1&thinsp;101</code> || 1/128
|-
| 14 = 2<sup>3</sup> + ''6'' || <code>1&thinsp;110</code> || <code>000&thinsp;1&thinsp;110</code> || 1/128
|-
| 15 = 2<sup>3</sup> + ''7'' || <code>1&thinsp;111</code> || <code>000&thinsp;1&thinsp;111</code> || 1/128
|-
|colspan=4|
|-
| 16 = 2<sup>4</sup> + ''0'' || <code>1&thinsp;0000</code> || <code>0000&thinsp;1&thinsp;0000</code> || 1/512
|-
| 17 = 2<sup>4</sup> + ''1'' || <code>1&thinsp;0001</code> || <code>0000&thinsp;1&thinsp;0001</code> || 1/512
|}

== [[解碼]] ==
以利亞加瑪碼之解碼遵循下列步驟：
# 讀取並計數零位元直到第一個一位元出現，假設共有 ''N'' 個零位元出現
# 從第一個一位元之後，再讀取 ''N'' 個[[位元]]，並將之還原成十進位[[自然数|正整數]]，令之為 ''M''
# 最終解碼為 2<sup>''N''</sup>+''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.
*[https://books.google.com.tw/books?id=m1u2eo5WweYC&pg=PA181&dq=Elias+gamma+code&hl=zh-TW&sa=X&ei=piWZVbxNhLGYBdvKttAI&ved=0CC0Q6AEwAg#v=onepage&q=Elias%20gamma%20code&f=false Classical and Quantum Information Theory: An Introduction for the Telecom ...]{{Wayback|url=https://books.google.com.tw/books?id=m1u2eo5WweYC&pg=PA181&dq=Elias+gamma+code&hl=zh-TW&sa=X&ei=piWZVbxNhLGYBdvKttAI&ved=0CC0Q6AEwAg#v=onepage&q=Elias%20gamma%20code&f=false |date=20150706075250 }}
*[https://books.google.com.tw/books?id=mnpeizY0btYC&pg=PA31&dq=Elias+gamma+code&hl=zh-TW&sa=X&ei=piWZVbxNhLGYBdvKttAI&ved=0CDUQ6AEwAw#v=onepage&q=Elias%20gamma%20code&f=false A Concise Introduction to Data Compression]{{Wayback|url=https://books.google.com.tw/books?id=mnpeizY0btYC&pg=PA31&dq=Elias+gamma+code&hl=zh-TW&sa=X&ei=piWZVbxNhLGYBdvKttAI&ved=0CDUQ6AEwAw#v=onepage&q=Elias%20gamma%20code&f=false |date=20150706110455 }}
*[https://books.google.com.tw/books?id=ujnQogzx_2EC&pg=PA761&dq=Elias+gamma+code&hl=zh-TW&sa=X&ei=piWZVbxNhLGYBdvKttAI&ved=0CB0Q6AEwAA#v=onepage&q=Elias%20gamma%20code&f=false Data Compression: The Complete Reference]{{Wayback|url=https://books.google.com.tw/books?id=ujnQogzx_2EC&pg=PA761&dq=Elias+gamma+code&hl=zh-TW&sa=X&ei=piWZVbxNhLGYBdvKttAI&ved=0CB0Q6AEwAA#v=onepage&q=Elias%20gamma%20code&f=false |date=20150706070708 }}
<br/>
{{压缩方法}}
[[Category:数字]]
[[Category:无损压缩算法]]