What is Elias gamma coding and how can we implement it in Python?

The Elias gamma code is a technique used in information theory to represent nonnegative integers. Its optimal use is when we wish to represent small integers with shorter codes and larger integers with longer codes, which helps achieve compression. This technique is used when coding integers where the upper bound is unknown beforehand.

Comparison with binary coding

Binary coding is much more straightforward to implement than Elias gamma. However, it is not space-efficient as it requires a fixed number of bits for any number. For example, in a 16-bit encoding, a smaller number like 4 and a larger number like 12345 would use 16 bits. Whereas Elias gamma coding provides a way to represent numbers in variable bit lengths, smaller numbers take fewer bits to encode.

Components of Elias gamma code

The Elias gamma code for a positive integer ‘n’ consists of two parts:

Unary code encodes the number of leading zeros in ‘n’ as a sequence of 0s followed by a 1.
Binary code encodes the remaining binary representation of ‘n’ without the leading 0s.

Encoding a number

Let’s first look at the given example to understand the concept:

Let’s encode the number 27:

First, we’ll take the binary representation of 27, which is 11011
Next, we’ll take the unary code. The formula to get the unary code is as follows:

In this code, we are doing the following:

Lines 1–3: We define the function and write an if condition to check if the number is positive.
Line 5: We use the bin() built-in function to convert the number to a binary number and store it in the variable binary_repr.
Line 7: We calculate the unary code using the formula described above and store it in the unary_code variable.
Lines 9–11: Here, we calculate the gamma code by combining the binary and unary codes and store it in the gamma_code variable after we which we return it from the function.

Decoding a number

Now let’s decode this binary back to 27, to do so:

We’ll split the unary code, which is 000001, and the binary code, which is 11011.
We’ll convert the binary back to 27.

Python code for decoding a Elias gamma encoded number is given below:

Here's a brief explanation of the code:

Line 2: This line finds the position of the first occurrence of 1 in the code using the find() function and stores it in the idx variable.
Line 4: We use slicing to extract the unary code from the gamma string. This line extracts the digits from the beginning up to and including the first 1 from the gamma code.
Line 5: We slice the code from the idx + 1 position to the end of the string to get the binary code.
Lines 7–9: We use the int() function to convert the binary to an integer and store the result in the value variable, and then we return it.

Implementation of Elias gamma coding

Let's combine the above functions and see how we can implement the full code in Python:

def elias_gamma_encode(n):
    if n <= 0:
        raise ValueError("Input must be a positive integer")
    binary_repr = bin(n)[2:]
    unary_code = "0" * len(binary_repr)  + "1"
    gamma_code = unary_code + binary_repr
    return gamma_code
def elias_gamma_decode(code):
    idx = code.find("1")
    unary_code = code[:idx + 1]
    binary_code = code[idx + 1:]
    value = int(binary_code, 2)
    return value
# Example usage
number = 2
encoded = elias_gamma_encode(number)
decoded = elias_gamma_decode(encoded)
print("Original Number: " , number)
print("Encoded: " , encoded)
print("Decoded: ",  decoded)