Elias gamma coding

Created: 2023-06-20T01:16:11-05:00

Return to the Index

This card pertains to a resource available on the internet.

Encodes a number with 2*floor(log2(x))+1 bits.

Does not encode zeroes or negative numbers. You need ZigZag encoding for that.

Mostly only useful when the majority of values you will encode equal or less than the number fifteen--which can be stored in a buffer where values of less than eight bits can be kept. Values above fifteen require more than 8 bits, so they are less efficient than storing whole bytes.

N: the highest power of two that contains the number to be encoded, called X.

Encoding

• Calculate N with floor(log2(X))
• Write N zeroes
• Write the bits of the number being encoded

If a number falls in to the N=2 bucket, that means you append two zeroes and then the number.

Decoding

• Count the zero bits until the first 1, assign to N
• Read the remaining N bits (the first 1 bit is included in the count represented by N)
• Add 2^N and the remaining N bits

Tunables

N is the highest power of 2 contained within X.

Examples

To encode the number 5, this is encoded in binary as `101`. Since this falls in to the N=2 bucket the Gamma encoding is `00101`.