以利亞戴爾達碼(Elias delta code)是一種用於正整數之通用編碼。該碼由Peter Elias發明。
基本介紹
- 中文名:以利亞戴爾達碼
- 外文名:Elias delta code
- 作用:用於正整數之通用編碼。
- 發明者:Peter Elias
編碼介紹,一般化,解碼介紹,示例代碼,解碼,編碼,
編碼介紹
對於待編碼正整數X≥1:
- 令N=⌊log2X⌋,故2≤X< 2
- 令L=⌊log2N+1⌋,故2≤N+1 < 2
- 輸出L個零比特,接著輸出
- N+1之L+1比特二進制數,接著輸出
- X的最後N個比特。
另一個等價的編碼方式為:
- 將X分區成小於其之最大二的次方 (2) 和餘下的N個比特之和
- 將N+1進行以利亞加瑪編碼
- 將餘下的N個比特接在上述之後。
要對 進行編碼,以利亞戴爾達碼必須使用 個比特。
以下為一編碼對照表如圖一所示:
一般化
以利亞戴爾達碼並不適用於零或負整數。一個一般化的方式是在最左側先加一個一比特,解碼時再行扣掉。另一個方法是在編碼前將所有整數映射至正整數,例如:(0, 1, −1, 2, −2, 3, −3, ...) 對應至 (1, 2, 3, 4, 5, 6, 7, ...)。
解碼介紹
以利亞戴爾達碼之解碼遵循下列步驟:
- 讀取並計數零比特直到第一個一比特出現,假設共有出現
- 從第一個一比特之後,再讀取個比特,並將已讀取之 2+1 個比特還原成十進制正整數。假設該正整數為N+1
- 再讀取N個比特並將之還原成十進制正整數,令之為M
- 最終解碼為 2+M
示例代碼
解碼
void eliasDeltaDecode(char* source, char* dest)
{
BitReader bitreader(source);
IntWriter intwriter(dest);
while (bitreader.hasLeft())
{
int num = 1;
int len = 1;
int lengthOfLen = 0;
while (!bitreader.inputBit()) // potentially dangerous with malformed files.
lengthOfLen++;
for (int i = 0; i < lengthOfLen; i++)
{
len <<= 1;
if (bitreader.inputBit())
len |= 1;
}
for (int i = 0; i < len-1; i++)
{
num <<= 1;
if (bitreader.inputBit())
num |= 1;
}
intwriter.putInt(num); // write out the value
}
bitreader.close();
intwriter.close();
}
編碼
void eliasDeltaEncode(char* source, char* dest)
{
IntReader intreader(source);
BitWriter bitwriter(dest);
while (intreader.hasLeft())
{
int num = intreader.getInt();
int len = 0;
int lengthOfLen = 0;
for (int temp = num; temp > 0; temp >>= 1) // calculate 1+floor(log2(num))
len++;
for (int temp = len; temp > 1; temp >>= 1) // calculate floor(log2(len))
lengthOfLen++;
for (int i = lengthOfLen; i > 0; --i)
bitwriter.outputBit(0);
for (int i = lengthOfLen; i >= 0; --i)
bitwriter.outputBit((len >> i) & 1);
for (int i = len-2; i >= 0; i--)
bitwriter.outputBit((num >> i) & 1);
}
bitwriter.close();
intreader.close();
}