The Elias gamma code is a universal code that is used to encode a sequence of positive integers. It is developed by Peter Elias. It is most useful when the upper-bound of integers cannot be determined beforehand.
Formula:
Elias Gamma Coding=Unary(1+floor(log2(x)))+Binary representation of ‘x’ without MSB
Example: Let’s consider an example where we want to decode 0001001,
Apply Step 1: Count the number of '0's from MSB until you reach the first '1' and store the count in K. In our example(0001001) K=3 Apply Step 2: Read 3 more bits including the first '1'=1001 Apply Step 3: Convert the final binary into integer which gives us the original number. Decimal(1001)=9
Stepwise Implementation
Step 1: Count the number of ‘0’s from MSB until you reach the first ‘1’ and store the count in K.
Python3
# define the function def Elias_Gamma_Decoding(x): # convert to list x = list(x) # initialize k to 0 K = 0 while True: # check if k is not 0 in through # list index if not x[K] == '0': break # increment k value K = K + 1 |
Step 2: Consider that ‘1’ as the first digit and read ‘K’ more bits from the current ‘1’
Python3
x = x[K:2*K+1] # Reading K more bits from '1' |
Step 3: Convert the final binary into an integer which gives us the original number.
Python3
# Converting binary to integer for i in range(len(x)): if x[i] == '1': n = n+math.pow(2, i) return int(n) |
Below is the complete implementation of the above approach.
Python3
# import the math module import math # function def Elias_Gamma_Decoding(x): x = list(x) K = 0 while True: if not x[K] == '0': break K = K + 1 # Reading K more bits from '1' x = x[K:2*K+1] n = 0 x.reverse() # Converting binary to integer for i in range(len(x)): if x[i] == '1': n = n+math.pow(2, i) return int(n) # value input x = '0001001' # call the function print(Elias_Gamma_Decoding(x)) |
Output:
9
