以利亞戴爾達碼

以利亞戴爾達碼（Elias delta code）是一種用於正整數之通用編碼。該碼由Peter Elias發明。

基本介紹

• 中文名：以利亞戴爾達碼
• 外文名：Elias delta code
• 作用：用於正整數之通用編碼。
• 發明者：Peter Elias

編碼介紹

對於待編碼正整數X≥1：

1. 令N=⌊log₂X⌋，故2≤X< 2
   
2. 令L=⌊log₂N+1⌋，故2≤N+1 < 2
   
3. 輸出L個零比特，接著輸出
   
4. N+1之L+1比特二進制數，接著輸出
   
5. X的最後N個比特。
   

另一個等價的編碼方式為：

1. 將X分區成小於其之最大二的次方 (2) 和餘下的N個比特之和
   
2. 將N+1進行以利亞加瑪編碼
   
3. 將餘下的N個比特接在上述之後。
   

要對 進行編碼，以利亞戴爾達碼必須使用 個比特。

以下為一編碼對照表如圖一所示：

圖一

一般化

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

解碼介紹

以利亞戴爾達碼之解碼遵循下列步驟：

1. 讀取並計數零比特直到第一個一比特出現，假設共有出現
   
2. 從第一個一比特之後，再讀取個比特，並將已讀取之 2+1 個比特還原成十進制正整數。假設該正整數為N+1
   
3. 再讀取N個比特並將之還原成十進制正整數，令之為M
   
4. 最終解碼為 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();}