Perfect ending for entropy coding

Finitely odd numbers

Here we use the ideas of Matt Timmermans and David A. Scott.

In the above, we derived a method for generating an infinite stream of bits representing a real number that encodes our symbols. If the stream of symbols is finite, we want to end the stream of bits. We do this by picking a so called finitely odd number, these numbers:

\begin{aligned} &\mathtt{0.00000000000000}… \\ &\mathtt{0.10000000000000}… \\ &\mathtt{0.01000000000000}… \\ &\mathtt{0.11000000000000}… \\ &\mathtt{0.00100000000000}… \\ &\mathtt{0.01100000000000}… \\ &\mathtt{0.10100000000000}… \\ &\mathtt{0.11100000000000}… \\ &\mathtt{0.00010000000000}… \\ &\phantom{\mathtt{0.000100}}⋮ \end{aligned}

Note that they are not sorted as ordinary real numbers, they are rather sorted in a form of shortlex order. This is important to us because we want to encode the stream of symbols as the shortest possible bit string.

We store the first available finitely odd number that uniquely encodes the sequence of symbols. This means the number we pick must be in the final interval. But this number will also be in the final interval of all the prefixes of our current symbol sequence. To solve this problem we do the following:

• On start we set the current ending to e = \mathtt{0.0000}… and reserve E = ∅.
• Every time we encode a symbol we:
  • Reserve the previous ending: Set E' = E ∪ \set{e}.
  • Set e' to the first number in \delim[{h, l}) and not in E'.
• On end we write e.

Ending a bit streams

At any point in encoding, the written bit stream can be sorted in four states:

\begin{aligned} …\mathtt{0}⁻ & \\ …\mathtt{0}⁺ & \\ …\mathtt{1}⁻ & \\ …\mathtt{1}⁺ & \\ \end{aligned}

Where ⁺ denotes that we can add a carry and ⁻ means we can not. The empty bit stream, the initial state, can be considered part of \mathtt{1}⁻.

To do. Insert state diagram.

Besides any potential bits to output, we can also decide to trigger the carry or not. To denote endings we leave off the infinite tail of zeros and prefix a \mathtt{1.} if we want to trigger the carry and \mathtt{0.} if we don't. The ordered sequence of valid endings for each state are:

The situation for \mathtt{0}⁻ and \mathtt{1}⁻ are identical. The sequence for \mathtt{0}⁺ and \mathtt{1}⁺ only differs in the first entry. With the exception of the first two items in \mathtt{1}⁺, these sequences are simply the finitely odd numbers, directly or shifted to the left once.

The endings also need to fall in the range \delim[{h, l}), further trimming the set of possibilities.

Updating and pruning the reserved set

The set E can currently only grow, and does so with one entry for every symbol. As we start outputting bits and carries we need to update the set. Assume the set only contains valid entries, then for each of the ten possible transitions we do the following:

1. Writing a carry, \mathtt{0}⁺ → \mathtt{1}⁻:

   \mathtt{0}⁺	→	\mathtt{1}⁻
   \mathtt{0.}
   \mathtt{1.}		\mathtt{0.}
   \mathtt{0.1}
   \mathtt{1.1}		\mathtt{0.1}
   \mathtt{0.01}
   \mathtt{0.11}
   \mathtt{1.01}		\mathtt{0.01}
   \mathtt{1.11}		\mathtt{0.11}
   \mathtt{0.001}
   \;\;⋮		\;\;⋮

2. Writing a carry, \mathtt{1}⁺ → \mathtt{0}⁻:

   \mathtt{1}⁺	→	\mathtt{0}⁻
   \mathtt{1.}		\mathtt{0.}
   \mathtt{0.}
   \mathtt{0.1}
   \mathtt{1.1}		\mathtt{0.1}
   \mathtt{0.01}
   \mathtt{0.11}
   \mathtt{1.01}		\mathtt{0.01}
   \mathtt{1.11}		\mathtt{0.11}
   \mathtt{0.001}
   \;\;⋮		\;\;⋮

3. Writing a zero, \mathtt{0}⁻ → \mathtt{0}⁺:

   \mathtt{0}⁻	→	\mathtt{0}⁺
   \mathtt{0.}		\mathtt{0.}
   \mathtt{0.1}
   \mathtt{0.01}		\mathtt{0.1}
   \mathtt{0.11}
   \mathtt{0.001}		\mathtt{0.01}
   \mathtt{0.011}		\mathtt{0.11}
   \mathtt{0.101}
   \mathtt{0.111}
   \mathtt{0.0001}		\mathtt{0.001}
   \;\;⋮		\;\;⋮

4. Writing a zero, \mathtt{0}⁺ → \mathtt{0}⁺:

   \mathtt{0}⁺	→	\mathtt{0}⁺
   \mathtt{0.}		\mathtt{0.}
   \mathtt{1.}
   \mathtt{0.1}		\mathtt{1.}
   \mathtt{1.1}
   \mathtt{0.01}		\mathtt{0.1}
   \mathtt{0.11}		\mathtt{1.1}
   \mathtt{1.01}
   \mathtt{1.11}
   \mathtt{0.001}		\mathtt{0.01}
   \;\;⋮		\;\;⋮

5. Writing a zero, \mathtt{1}⁻ → \mathtt{0}⁺:

   \mathtt{1}⁻	→	\mathtt{0}⁺
   \mathtt{0.}		\mathtt{0.}
   \mathtt{0.1}		\mathtt{1.}
   \mathtt{0.01}		\mathtt{0.1}
   \mathtt{0.11}		\mathtt{1.1}
   \mathtt{0.001}		\mathtt{0.01}
   \mathtt{0.011}		\mathtt{0.11}
   \mathtt{0.101}		\mathtt{1.01}
   \mathtt{0.111}		\mathtt{1.11}
   \mathtt{0.0001}		\mathtt{0.001}
   \;\;⋮		\;\;⋮

6. Writing a zero, \mathtt{1}⁺ → \mathtt{0}⁺:

   \mathtt{1}⁺	→	\mathtt{0}⁺
   \mathtt{1.}
   \mathtt{0.}		\mathtt{0.}
   \mathtt{0.1}		\mathtt{1.}
   \mathtt{1.1}
   \mathtt{0.01}		\mathtt{0.1}
   \mathtt{0.11}		\mathtt{1.1}
   \mathtt{1.01}
   \mathtt{1.11}
   \mathtt{0.001}		\mathtt{0.01}
   \;\;⋮		\;\;⋮

7. Writing a one, \mathtt{0}⁻ → \mathtt{1}⁻:

   \mathtt{0}⁻	→	\mathtt{1}⁻
   \mathtt{0.}
   \mathtt{0.1}		\mathtt{0.}
   \mathtt{0.01}
   \mathtt{0.11}		\mathtt{0.1}
   \mathtt{0.001}
   \mathtt{0.011}
   \mathtt{0.101}		\mathtt{0.01}
   \mathtt{0.111}		\mathtt{0.11}
   \mathtt{0.0001}
   \;\;⋮		\;\;⋮

8. Writing a one, \mathtt{0}⁺ → \mathtt{1}⁺:

   \mathtt{0}⁺	→	\mathtt{1}⁺
   \mathtt{0.}
   \mathtt{1.}		\mathtt{1.}
   \mathtt{0.1}		\mathtt{0.}
   \mathtt{1.1}
   \mathtt{0.01}
   \mathtt{0.11}		\mathtt{0.1}
   \mathtt{1.01}		\mathtt{1.1}
   \mathtt{1.11}
   \mathtt{0.001}
   \;\;⋮		\;\;⋮

9. Writing a one, \mathtt{1}⁻ → \mathtt{1}⁻:

   \mathtt{1}⁻	→	\mathtt{1}⁻
   \mathtt{0.}
   \mathtt{0.1}		\mathtt{0.}
   \mathtt{0.01}
   \mathtt{0.11}		\mathtt{0.1}
   \mathtt{0.001}
   \mathtt{0.011}
   \mathtt{0.101}		\mathtt{0.01}
   \mathtt{0.111}		\mathtt{0.11}
   \mathtt{0.0001}
   \;\;⋮		\;\;⋮

10. Writing a one, \mathtt{1}⁺ → \mathtt{1}⁺:

    \mathtt{1}⁺	→	\mathtt{1}⁺
    \mathtt{1.}		\mathtt{1.}
    \mathtt{0.}
    \mathtt{0.1}		\mathtt{0.}
    \mathtt{1.1}
    \mathtt{0.01}
    \mathtt{0.11}		\mathtt{0.1}
    \mathtt{1.01}		\mathtt{1.1}
    \mathtt{1.11}
    \mathtt{0.001}
    \;\;⋮		\;\;⋮

We observe that the transitions preserve the order!