Expand description
Elias ω code.
Elias γ and δ codes encode a number n by storing the binary representation of n + 1, with the most significant bit removed, prefixed by its length in unary or γ code, respectively. Thus, δ can be seen as adding one level of recursion in the length representation with respect to γ. The ω code encodes the length of the binary representation of n + 1 recursively.
The implied distribution for the ω code is difficult to write analytically, but essentially it is as close as possible to ≈ 1/x (as there is no code for that distribution).
The ω code is easier to describe the format of a code, rather than the encoding algorithm.
A codeword is given by the concatenation of blocks b₀ b₁ … bₙ 0,
where each block bᵢ is a binary string starting with 1 and b₀ = 10
or 11. One can interpret the highest bit of each block as a continuation
bit, and the last 0 as a terminator of the code.
The condition for a valid codeword is that the value represented by each block, incremented by one, is the length of the following block, except for the last block.
The value associated with a codeword is 0 if the code is 0, and otherwise
the value of the last block, decremented by one.
For example, 1110010, which is formed by the blocks 11, 1011, and 0,
represents 10.
As discussed in the codes module documentation, to make the
code readable in the little-endian case, rather than reversing the bits of
the blocks, which would be expensive, we simply rotate by one on the left
each block, with the result that the most significant bit of the block is
now the first bit in the stream, making it possible to check for the
presence of a continuation bit. For example, in the little-endian case, the
code for 10 is 0011111, which is formed by the blocks 11, 0111, and
0.
§References
Peter Elias. “Universal codeword sets and representations of the integers”. IEEE Transactions on Information Theory, 21(2):194−203, March 1975.
Traits§
- Omega
Read - Trait for reading ω codes.
- Omega
Write - Trait for writing ω codes.
Functions§
- len_
omega - Returns the length of the ω code for
n.