Elias Delta Decoding in Python

Namachila 13 hours ago

0 0 2 minutes read

In this article, we are going to implement Elias Delta Decoding using python.

Peter Elias devised the Elias delta code, which is a universal system for encoding positive integers.

Syntax:

Elias Delta Encoding(X)= Elias Gamma encoding (1+floor(log2(X))) + Binary representation of X without MSB.

Approach:

Import required libraries and read the encoded binary string from the user.
Read/Count the number of zero’s from the most significant bit until you see the first ‘1’ and store it in a variable named ‘L’

Syntax:

L=0
while True:
   if not x[L] == '0':
       break
   L= L + 1

Consider that ‘L’ as 1st digit and read L more bits and drop all bits until current L bit.
Take out the remaining bits and prepend ‘1’ in the Most significant bit.

Syntax:

x.insert(0,’1′)

Convert the final binary into integer which gives us the original number.

Example:

Let the input encoded string is 01111

Step1: Read/Count the number of zeros from most significant bit until you see the first ‘1’ and store it in ‘L’ until you see the first ‘1’

In our case, L=1

Step2: Consider that ‘1’ as first digit read L more bits (1 more bit) and drop everything.

~~011~~11= 11

Step3: Takeout the remaining bits and prepend with ‘1’ in MSB.

111

Step4: Convert the final binary string into integer which gives us 7.

Below is the implementation.

Example 1: Example to produce Elias Delta Decoding value corresponding to some value.

Python3

import math 
  
  
def Elias_Delta_Decoding(x): 
    x = list(x) 
    L = 0
    while True: 
        if not x[L] == '0': 
            break
        L = L + 1
          
    # Reading L more bits and dropping ALL     
    x = x[2*L+1:]   
      
    # Prepending with 1 in MSB 
    x.reverse() 
    x.insert(0, '1')   
    n = 0
      
    # Converting binary to integer 
    for i in range(len(x)):   
        if x[i] == '1': 
            n = n+math.pow(2, i) 
    return int(n) 
  
  
x = '01111'
print(Elias_Delta_Decoding(x)) 

Output:

Example 2: Example to produce Elias Delta Decoding value corresponding to some value.p

Python

import math 
  
def  Elias_Delta_Decoding(x): 
    x = list(x) 
    L=0
    while True: 
        if not x[L] == '0': 
            break
        L= L + 1
      
    # Reading L more bits and dropping ALL 
    x=x[2*L+1:]  
      
    # Prepending with 1 in MSB 
    x.insert(0,'1')  
    x.reverse() 
    n=0
      
    # Converting binary to integer 
    for i in range(len(x)):  
        if x[i]=='1': 
            n=n+math.pow(2,i) 
    return int(n) 
  
x = '0111100'
print(Elias_Delta_Decoding(x))