以利亞加瑪碼

以利亞加瑪碼

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

基本介紹

  • 中文名:以利亞加瑪碼
  • 外文名:Elias gamma code
  • 發明人:Peter Elias
編碼,解碼,用途,一般化,

編碼

對於待編碼正整數
:
1.令
,故
2.輸出N個零比特
3.接禁紙謎著輸出X的二進制表示
另一個等價的編碼姜乎放宙方式為:
1.輸出 N 的一進位表示
2.將余放立仔下的 N 個比特接在上述之後
要對X進行編碼,以利亞戴乃堡爾達碼必須使用
個比特。
以下為一編碼對照表:
二進制表局晚達示
加瑪編碼
代表之機率
1 = 2+ 0
1
1
1/2
2 = 2+0
1 0
0 1 0
1/8
3 = 2+1
1 1
0 1 1
1/8
4 = 2+0
1 00
00 1 00
1/32
5 = 2+1
1 01
00 1 01
1/32
6 = 2+2
1 10
00 1 10
1/32
7 = 2+3
1 11
00 1 11
1/32
8 = 2+0
1 000
000 1 000
1/128
9 = 2+1
1 001
000 1 001
1/128
10 = 2+2
1 010
000 1 010
1/128
11 = 2+3
1 011
000 1 011
1/128
12 = 2+4
1 100
000 1 100
1/128
13 = 2+5
1 101
000 1 101
1/128
14 = 2+6
1 110
000 1 110
1/128
15 = 2+7
1 111
000 1 111
1/128
16 = 2+0
1 0000
0000 1 0000
1/512
17 = 2+1
1 0001
0000 1 0001
1/512

解碼

以利亞加瑪碼之解碼遵循下列步驟:
1.讀取並計數零比特直到第一個一比特出現,假設共有N出現
2.從第一個一比特之後,再讀取 N 個比特,並將之還原成十進制正整數,令之為 M
3.最終解碼為

用途

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

一般化

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

相關詞條

熱門詞條

聯絡我們