Elias codes are prefix codes for positive, non-zero integers with no assumption or limit to their size.

For codes that include the value 0, see Elias.Natural.

An Elias gamma code consists of the binary expansion of an integer, preceded by the unary encoding of the length of that expansion in zeros.

For example, while the binary expansion of 21 is:

import qualified Codec.Arithmetic.Variety.BitVec as BV
BV.toString $ BV.fromInteger 21
"10101"

its Elias code is:

BV.toString $ enodeGamma 21
"000010101"

where an expansion of \(i\) is always preceeded by \(i-1\) zeros.

An Elias delta code is like an Elias gamma code except that the length is itself coded like a gamma code instead of simply a unary encoding.

For example:

BV.toString $ BV.fromInteger (10^6)
"11110100001001000000"

length "11110100001001000000"
20

is prefixed with the gamma encoding of 20 and loses its leading bit which begins every binary expansion:

BV.toString <$> [encodeGamma 20, BV.fromInteger (10^6)]
["000010100","11110100001001000000"]

BV.toString $ encodeDelta 1000000
"0000101001110100001001000000"

length "0000101001110100001001000000"
28

An Elias omega code is the result of recursively encoding the length of binary expansions in the prefix until a length of 1 is reached. Since binary expansions are written without any leading zeros, a single 0 bit marks the end of the code.

For example:

BV.toString . BV.fromInteger <$> [2,4,19,10^6]
["10","100","10011","11110100001001000000"]

length <$> ["10","100","10011","11110100001001000000"]
[2,3,5,20]

BV.toString $ encodeOmega (10^6)
"1010010011111101000010010000000"

length $ "1010010011111101000010010000000"
31

Notice that, while asymptotically more efficient, omega codes are longer than delta codes until around 1 googol, or 10^100.