Elias delta coding

*קידוד דלתא של אליאס* או *קידוד דלתא אליאס* הוא קוד אוניברסלי לקידוד מספרים שלמים חיוביים, שפותח על ידי פיטר אליאס.

קידוד[עריכה]

בכדי לקדד מספר X ≥ 1:

נקבע N = ⌊log₂ X⌋; החזקה הגבוהה ביותר של 2 ב-X, כך ש-2^N ≤ X < 2^N+1.
נקבע L = ⌊log₂ N+1⌋ החזקה הגבוהה ביותר של 2 ב-N+1, כך ש-2^L ≤ N+1 < 2^L+1.
כתובת L אפסים, אחריהם
ייצוג בינארי של L+1 ביטים של N+1, ואחריו
כל הביטים של X מלבד הביט המוביל (כלומר ה-N ביטים האחרונים).

דרך שקולה לבטא את אותו תהליך:

הפרדת X לחזקה הגבוהה ביותר של 2 שהוא מכיל (2^N) וה-N ספרות הבינארי הנותרות.
קידוד N+1 בעזרת Elias gamma coding.
הוספת ה-N ספרות הבינארי הנותרות לייצוג זה של N+1.

כדי לייצג מספר $x$, קידוד דלתא של אליאס (δ) משתמש ב-$ \lfloor \log_2(x) \rfloor + 2 \lfloor \log_2 (\lfloor \log_2(x) \rfloor +1) \rfloor + 1$ ביטים. זה שימושי למספרים שלמים גדולים מאוד, שבהם סך הביטים בייצוג המקודד מסתיים בפחות ממה שניתן להשיג בשימוש ב-Elias gamma coding, בזכות החלק $\log_2 (\lfloor \log_2(x) \rfloor +1)$ של הביטוי הקודם.

מספר	N	N+1	קידוד δ	הסתברות מושרית
1 = 2⁰	0	1	`1`	1/2

2 = 2¹ + '0'	1	2	`0 1 0 0`	1/16
3 = 2¹ + '1'	1	2	`0 1 0 1`	1/16

4 = 2² + '0'	2	3	`0 1 1 00`	1/32
5 = 2² + '1'	2	3	`0 1 1 01`	1/32
6 = 2² + '2'	2	3	`0 1 1 10`	1/32
7 = 2² + '3'	2	3	`0 1 1 11`	1/32

8 = 2³ + '0'	3	4	`00 1 00 000`	1/256
9 = 2³ + '1'	3	4	`00 1 00 001`	1/256
10 = 2³ + '2'	3	4	`00 1 00 010`	1/256
11 = 2³ + '3'	3	4	`00 1 00 011`	1/256
12 = 2³ + '4'	3	4	`00 1 00 100`	1/256
13 = 2³ + '5'	3	4	`00 1 00 101`	1/256
14 = 2³ + '6'	3	4	`00 1 00 110`	1/256
15 = 2³ + '7'	3	4	`00 1 00 111`	1/256

16 = 2⁴ + '0'	4	5	`00 1 01 0000`	1/512
17 = 2⁴ + '1'	4	5	`00 1 01 0001`	1/512

לפענח מספר שלם שמקודד בקידוד דלתא של אליאס:

קרא וספור אפסים מהזרם עד שתגיע לאחד. קרא לספירת אפסים זו L.
תחשב את האחד שהגעת אליו כספרה הראשונה של מספר שלם, עם ערך 2^L, קרא את ה-L ספרות הנותרות של המספר. קרא למספר שלם זה N+1, וחסר אחד כדי לקבל N.
שים אחד במקום הראשון בפלט הסופי שלנו, מייצג את הערך 2^N.
קרא והוסף את ה-N ספרות הבאות.

דוגמא: 001010011 1. 2 אפסים מובילים ב-001 2. קרא 2 ביטים נוספים כלומר 00101 3. פענח N+1 = 00101 = 5 4. קבל N = 5 − 1 = 4 ביטים נותרים לקוד השלם כלומר '0011' 5. המספר המקודד = 2⁴ + 3 = 19

קוד זה יכול להתאים לאפס או למספרים שליליים באותו אופן שתואר ב-Elias gamma coding.

דוגמאות קוד[עריכה]

קידוד[עריכה]

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;

        len = 1 + floor(log2(num));  // calculate 1+floor(log2(num))
        lengthOfLen = floor(log2(len)); // calculate floor(log2(len))

        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();
}

פענוח[עריכה]

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();
}

הכללות[עריכה]

תבנית:See also קידוד דלתא של אליאס אינו מקדד אפס או מספרים שליליים. דרך אחת לקדד את כל המספרים הלא שליליים היא להוסיף 1 לפני הקידוד ולחסר 1 אחרי הפענוח. דרך אחת לקדד את כל המספרים היא להקים התאמה חד-חד-ערכית, ממספרים שלמים (0, 1, -1, 2, -2, 3, -3, ...) למספרים שלמים חיוביים בלבד (1, 2, 3, 4, 5, 6, 7, ...) לפני הקידוד. התאמה זו יכולה להתבצע בעזרת קידוד ה-"ZigZag" מ-Protocol Buffers (לא לבלבל עם Zigzag code, או עם קידוד האנטרופיה הזיגזאג של JPEG).