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.
01111= 11Step3: 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:
7
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)) |
Output:
28
