Elias Delta Encoding in Python

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

Syntax:

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

Implementation

First, we are going to implement Elias delta Encoding, Before writing code for Elias Delta Encoding.

Step 1:

• Import log, floor functions from the math library to perform logarithmic operations.
• Fetch input k from user to encode in Elias Gamma.
• Using floor and log functions in the math module, find 1+floor(log2(X) and store it in variable N.
• Find the unary coding of N, using (N-1)*’0’+’1′ which gives us a binary string with ‘1’ in a least-significant bit and N-1 ‘0’s in the remaining Most significant bits.

Example: Elias Gamma encoding for some value

Step 2:

• Create a function that takes the input X and gives the result as a Binary representation of X without MSB.
• Using “{0:b}”.format(k) find the binary equivalent of k and store it in a variable named binary.
  • The prefix zero just specifies which argument of format() should be used to fill the {}.
  • b specifies that the argument should be converted to binary form.
• Return the string binary[1:] which is a Binary representation of X without MSB.

Example: Binary Representation without MSB

Now we are going to write code for Elias Delta Encoding

Step 3:

• Fetch input k from user to encode in Elias Delta.
• Using floor and log functions in the math module, find 1+floor(log2(k).
• Pass the result of 1+floor(log2(k) to Elias Gamma encoding function.

Example: Elias Delta Encoding for some value

Step 4:

• Get the result of Elias Gamma encoding and Binary representation of k without MSB
• Concatenate both the results and print them on the console

Complete code to produce Elias Delta Encoding for some integer value

Output:

00100110