以利亞加瑪碼(Elias gamma code)是一種用於正整數之通用編碼。該碼由Peter Elias發明。此編碼常被用於無法事先得知上界之正整數。
編碼
對於待編碼正整數 X≥1:
令 N=⌊log2 X⌋ ,故 2N ≤ X N+1
輸出 N 個零位元
接著輸出 X 的二進位表示。
另一個等價的編碼方式為:
輸出 N 的一進位表示
將餘下的 N 個位元接在上述之後。
要對 x 進行編碼,以利亞戴爾達碼必須使用 2 \lfloor \log_2(x) \rfloor + 1 個位元。
以下為一編碼對照表:
解碼
以利亞加瑪碼之解碼遵循下列步驟:
讀取並計數零位元直到第一個一位元出現,假設共有 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.
*[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 ...]
*[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]
*[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]
评论 (0)