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.
Steps in Encoding:
To encode a number X,
- Find the largest N, with
(greater power of 2).
- Encode N using Unary coding(i.e N zeroes followed by a one).
- Append the integer
using N digits in Binary.
(greater power of 2).
using N digits in Binary.
Example: Let’s consider an example where we want to encode 10,
We can represent 10 as:
.
Step1: Here, largest N = 3
Step2: N(=3) in Unary followed by a one = 0001
Step3: Now Representation of 2 in Binary using N(=3) digits = 010
So, Elias gamma encoding of 10 = 0001010
Below is the implementation of the above approach.
# Python3 implementation from math import log log2 = lambda x: log(x, 2) def Unary(x): return (x-1)*'0'+'1' def Binary(x, l = 1): s = '{0:0%db}' % l return s.format(x) def Elias_Gamma(x): if(x == 0): return '0' n = 1 + int(log2(x)) b = x - 2**(int(log2(x))) l = int(log2(x)) return Unary(n) + Binary(b, l) print(Elias_Gamma(10)) |
Output:
0001010
