इलियास डेल्टा कोडिंग

From Vigyanwiki
Revision as of 14:16, 14 December 2023 by Indicwiki (talk | contribs) (9 revisions imported from alpha:इलियास_डेल्टा_कोडिंग)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

इलियास δ कोड या इलियास डेल्टा कोड पीटर इलियास द्वारा विकसित धनात्मक पूर्णांकों को एन्कोड करने वाला सार्वभौमिक कोड है।[1]: 200 

एन्कोडिंग

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

  1. मान लीजिए N= ⌊log2 X⌋; X में 2 की उच्चतम घात हो, इसलिए 2NX < 2N+1 है।
  2. मान लीजिए L = ⌊log2 N+1⌋ N+1 में 2 की उच्चतम घात है, इसलिए 2LN+1 < 2L+1 है।
  3. L शून्य लिखें, उसके पश्चात
  4. N+1 का L+1-बिट बाइनरी प्रतिनिधित्व, उसके पश्चात
  5. X के अग्रणी बिट (अर्थात अंतिम N बिट्स) को छोड़कर सभी है।

उसी प्रक्रिया को व्यक्त करने की समकक्ष विधि है:

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

किसी संख्या का प्रतिनिधित्व करने के लिए , इलियास डेल्टा (δ) का उपयोग किया जाता है। बिट्स[1]: 200 यह अधिक बड़े पूर्णांकों के लिए उपयोगी है, जहां समग्र एन्कोडेड प्रतिनिधित्व के बिट्स कम हो जाते हैं [इलियास गामा कोडिंग का उपयोग करके प्राप्त की जा सकने वाली राशि से] पूर्व अभिव्यक्ति का भाग है।

कोड का उपयोग प्रारंभ होता है:

नंबर 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. 2L के मान के साथ, जो पूर्णांक का प्रथम अंक था, उसे ध्यान में रखते हुए, पूर्णांक के शेष L अंक पढ़ें। इस पूर्णांक को N+1 कहें और N प्राप्त करने के लिए एक घटाएँ।
  3. हमारे अंतिम आउटपुट के पहले स्थान पर जो मान 2N दर्शाता है।
  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();
}

सामान्यीकरण

इलियास डेल्टा कोडिंग शून्य या ऋणात्मक पूर्णांक को कोड नहीं करती है। सभी अऋणात्मक पूर्णांकों को कोड करने की विधि कोडिंग से पहले 1 जोड़ना और फिर डिकोडिंग के पश्चात 1 घटाना है। सभी पूर्णांकों को कोड करने की विधि यह है कि सभी पूर्णांकों (0, 1, −1, 2, −2, 3, −3, ...) को कठोरता से धनात्मक पूर्णांकों (1, 2, 3,) में मैप करके आक्षेप स्थापित किया जाए। कोडिंग से पूर्व 4, 5, 6, 7, ...) यह आक्षेप प्रोटोकॉल बफ़र्स से "ज़िगज़ैग" एन्कोडिंग का उपयोग करके किया जा सकता है (ज़िगज़ैग कोड के साथ भ्रमित न हों, न ही जेपीईजी ज़िग-ज़ैग एन्ट्रॉपी कोडिंग)।

यह भी देखें

संदर्भ

  1. 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.

अग्रिम पठन