Elias delta coding

ईलियस डेल्टा कोड या ईलियस डेल्टा एन्कोडिंग एक प्राकृतिक कोड है जो धनात्मक पूर्णांकों को एन्कोड करता है और इसे पीटर ईलियस ने विकसित किया था।

एन्कोडिंग

एक संख्या X ≥ 1 को एन्कोड करने के लिए:

1. N = ⌊log₂ X⌋; X में उच्चतम शक्ति 2 को लें, इस तरह कि 2^N ≤ X < 2^N+1.
2. L = ⌊log₂ N+1⌋ N+1 में उच्चतम शक्ति 2 को लें, इस तरह कि 2^L ≤ N+1 < 2^L+1.
3. L ज़ीरो लिखें, इसके बाद
4. L+1-बिट द्विआधारी प्रतिनिधित्व N+1 का, इसके बाद
5. X के सभी बिटों को छोड़कर आगे के बिट (यानी, अंतिम N बिट)।

एक समान तरीका 같ी प्रक्रिया को व्यक्त करने के लिए:

1. X को उसके भीतर उच्चतम शक्ति 2 (2^N) और बाकी N द्विआधारी अंकों में अलग करें।
2. N+1 को ईलियस गामा कोडिंग के साथ एन्कोड करें।
3. इस N+1 के प्रतिनिधित्व में बाकी N द्विआधारी अंकों को जोड़ें।

एक संख्या $x$ को प्रदर्शित करने के लिए, ईलियस डेल्टा (δ) $\lfloor \log _{2}(x)\rfloor +2\lfloor \log _{2}(\lfloor \log _{2}(x)\rfloor +1)\rfloor +1$ बिट्स का उपयोग करता है। यह अत्यधिक बड़े पूर्णांकों के लिए उपयोगी है, जहां समग्र एन्कोड किया गया प्रतिनिधित्व के बिट अंततः ईलियस गामा कोडिंग का उपयोग करके जो प्राप्त हो सकता है, उससे कम हो जाते हैं, क्योंकि $\log _{2}(\lfloor \log _{2}(x)\rfloor +1)$ पूर्व अभिव्यक्ति के हिस्से के कारण।

कोड शुरू होता है, $\gamma '$ के बजाय $\gamma$ का उपयोग करते हुए:

संख्या	N	N+1	δ एन्कोडिंग	निहित प्रायिकता
1 = 20	0	1	1	1/2
2 = 21 + 0	1	2	0 1 0 0	1/16
3 = 21 + 1	1	2	0 1 0 1	1/16
4 = 22 + 0	2	3	0 1 1 00	1/32
5 = 22 + 1	2	3	0 1 1 01	1/32
6 = 22 + 2	2	3	0 1 1 10	1/32
7 = 22 + 3	2	3	0 1 1 11	1/32
8 = 23 + 0	3	4	00 1 00 000	1/256
9 = 23 + 1	3	4	00 1 00 001	1/256
10 = 23 + 2	3	4	00 1 00 010	1/256
11 = 23 + 3	3	4	00 1 00 011	1/256
12 = 23 + 4	3	4	00 1 00 100	1/256
13 = 23 + 5	3	4	00 1 00 101	1/256
14 = 23 + 6	3	4	00 1 00 110	1/256
15 = 23 + 7	3	4	00 1 00 111	1/256
16 = 24 + 0	4	5	00 1 01 0000	1/512
17 = 24 + 1	4	5	00 1 01 0001	1/512

एक ईलियस डेल्टा-एन्कोड किए गए पूर्णांक को डिकोड करने के लिए:

1. स्ट्रीम से ज़ीरो पढ़ें और गिनें तब तक कि आप पहले एक तक न पहुंचें। इस ज़ीरो की गिनती को L कहें।
2. पहुंचे गए एक को एक पूर्णांक के पहले अंक के रूप में मानें, जिसका मूल्य 2^L हो, और पूर्णांक के बाकी L अंकों को पढ़ें। इस पूर्णांक को N+1 कहें, और एक को घटाकर N प्राप्त करें।
3. अपने अंतिम आउटपुट के पहले स्थान पर एक लाएं, जो मूल्य 2^N का प्रतिनिधित्व करता है।
4. आगे के N अंकों को पढ़ें और जोड़ें।

उदाहरण:

001010011
1. 001 में 2 आगे के ज़ीरो
2. 2 और बिट को पढ़ें यानी 00101
3. डिकोड N+1 = 00101 = 5
4. N = 5 − 1 = 4 बाकी बिट पूर्ण कोड के लिए यानी '0011'
5. एन्कोड किया गया संख्या = 24 + 3 = 19

इस कोड को शून्य या नकारात्मक पूर्णांकों तक सामान्यीकृत किया जा सकता है जैसा कि ईलियस गामा कोडिंग में वर्णित है।

उदाहरण कोड

एन्कोडिंग

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

सामान्यीकरण

इन्हें भी देखें: Variable-length quantity#Zigzag encoding

ईलियस डेल्टा कोडिंग शून्य या नकारात्मक पूर्णांकों को कोड नहीं करता है। सभी धनात्मक पूर्णांकों को कोड करने का एक तरीका कोड करने से पहले 1 जोड़ना और डिकोड करने के बाद 1 घटाना है। सभी पूर्णांकों को कोड करने का एक तरीका एक बिजेक्शन सेट अप करना है, जो पूर्णांकों (0, 1, −1, 2, −2, 3, −3, ...) को क्रमशः धनात्मक पूर्णांकों (1, 2, 3, 4, 5, 6, 7, ...) में मैप करता है कोड करने से पहले। यह बिजेक्शन "ZigZag" encoding from Protocol Buffers का उपयोग करके किया जा सकता है (जिसे Zigzag code, या JPEG Zig-zag entropy coding से उलझना नहीं है)।

देखें भी

• ईलियस गामा (γ) कोडिंग
• ईलियस ओमेगा (ω) कोडिंग
• Golomb-Rice code

और पठनीय

• "URR: Universal representation of real numbers". New Generation Computing 1 (2): 205–209. June 1983. doi:10.1007/BF03037427. ISSN 0288-3635. https://www.researchgate.net/publication/220619145_URR_Universal_Representation_of_Real_Numbers. अभिगमन तिथि: 2018-07-09.  (NB. The Elias δ code coincides with Hamada's URR representation.)

---

 Facebook Page

 Follow us on Twitter !

Read or create/edit this page in another language

• Elias delta coding in English