Elias delta coding

Elias δ kodlama veya Elias delta kodlama, Peter Elias tarafından geliştirilen pozitif tam sayıları kodlayan bir evrensel koddur.^[1]^:200

Kodlama[değiştir]

Bir sayı X ≥ 1 kodlanması için:

N = ⌊log₂ X⌋; X deki en yüksek 2'nin kuvveti olsun, böylece 2^N ≤ X < 2^N+1.
L = ⌊log₂ N+1⌋; N+1 deki en yüksek 2'nin kuvveti olsun, böylece 2^L ≤ N+1 < 2^L+1.
L sıfır yazın, ardından
L+1-bit ikili temsili N+1, ardından
X in ilk biti hariç tüm bitleri (yani son N biti) yazın.

Aynı işlemi daha açık bir şekilde ifade etmek için:

X i, içerdiği en yüksek 2'nin kuvveti (2^N) ile geri kalan N ikili rakamlarına ayırın.
N+1 ile Elias gamma kodlama yapın.
Bu N+1 temsiline kalan N ikili rakamları ekleyin.

Bir sayı $x$ i Elias delta (δ) kodlamak için, $\lfloor \log _{2}(x)\rfloor +2\lfloor \log _{2}(\lfloor \log _{2}(x)\rfloor +1)\rfloor +1$ bit kullanılır.^[1]^:200 Bu, çok büyük tam sayılar için kullanışlıdır, çünkü genel kodlanmış temsilin bitleri, $\log _{2}(\lfloor \log _{2}(x)\rfloor +1)$ kısmı nedeniyle [ Elias gamma kodlama kullanarak elde edilebilecek bit sayısından daha az olur.

Kodlama şu şekilde başlar, $\gamma '$ yerine $\gamma$ kullanılarak:

Sayı	N	N+1	δ kodlama	İmplike olasılık
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

Bir Elias delta kodlu tam sayıyı çözmek için:

Akıştan ilk birine kadar sıfırları okuyun ve sayın. Bu sıfır sayısını L olarak adlandırın.
İlk bir rakam olarak kabul edilen bu bir sayının 2^L değerini temsil eden bir sayının sonraki L rakamını okuyun. Bu sayıyı N+1 olarak adlandırın ve bir azaltarak N elde edin.
Son çıktımızın ilk yerine bir yazın, 2^N değerini temsil edin.
Sonraki N rakamını okuyup ekleyin.

Örnek:

001010011
1. 001'deki 2 başında sıfır
2. 00101 için 2 bit daha oku
3. decode N+1 = 00101 = 5
4. N = 5 − 1 = 4 kalan bit tam kod için i.e. '0011'
5. kodlanan sayı = 2⁴ + 3 = 19

Bu kod, Elias gamma kodlama de açıklanan yollarla sıfır veya negatif tam sayılara genelleştirilebilir.

Örnek Kod[değiştir]

Kodlama[değiştir]

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

Kod Çözme[değiştir]

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

Genelleştirmeler[değiştir]

Elias delta kodlama sıfır veya negatif tam sayıları kodlamaz. Tüm olumsuz tam sayıları kodlamak için bir yol, kodlama öncesinde 1 eklemek ve sonrasında 1 çıkarmaktır. Tüm tam sayıları kodlamak için bir yol, tüm tam sayıları (0, 1, −1, 2, −2, 3, −3, ...) kesinlikle pozitif tam sayılara (1, 2, 3, 4, 5, 6, 7, ...) eşleştiren bir karşılıklılık kurmaktır. Bu eşleştirme, Protocol Buffers'dan "ZigZag" kodlama (Zigzag kodu veya JPEG Zig-zag entropi kodlama ile karıştırılmamalıdır) ile yapılabilir.

Kaynaklar[değiştir]

Şablon:Kaynakça/styles.css sayfası içerik yok.

↑ ^1,0 ^1,1 Elias, Peter (March 1975). "Universal codeword sets and representations of the integers". IEEE Transactions on Information Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349.

İlgili okumalar[değiştir]

Hamada, Hozumi (June 1983). "URR: Universal representation of real numbers". New Generation Computing. 1 (2): 205–209. doi:10.1007/BF03037427. ISSN 0288-3635. Erişim tarihi: 2018-07-09. (Not: Elias δ kodu Hamada'nın URR temsiline denk gelir.)