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.
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.
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.
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:
Given that the binary code for 27 is 5 digits, the unary code for this will be five 0s followed by a 1. So the result will be 000001.
Finally, we’ll combine the two, and the result will be 0000011101. This is known as the gamma code.
Now let's code the encoding function:
def elias_gamma_encode(n):if n <= 0:raise ValueError("Input must be a positive integer")binary_repr = bin(n)[2:]unary_code = "0" * (binary_repr) + "1"gamma_code = unary_code + binary_reprreturn gamma_code
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.
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:
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
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.
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_reprreturn gamma_codedef 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 usagenumber = 2encoded = elias_gamma_encode(number)decoded = elias_gamma_decode(encoded)print("Original Number: " , number)print("Encoded: " , encoded)print("Decoded: ", decoded)
Free Resources