
\section{ Entropy Coder }
\label{entropy}

The coefficient scanner outputs two raw bitstreams for each bitplane which
have some special properties which make them easy to compress.
The more significand bitplanes of the coefficients are almost empty, thus
the corresponding bitstreams have very long runs of $0$-bits. This makes
them easy to compress using a Runlength Coder. The bitstreams describing
the first significand bits of smaller coefficients have similiar properties
but a bit shorter runs.

Runlengths are the written using the Golomb Coder to the compressed stream:

Insignificand bits (the bits of a coefficient after the first significand bit)
are almost random, it doesn't makes sense to spend much energy on trying
to compress them. But some of them -- especially for low frequency 
coefficients -- need to be transmitted in order to prevent a DC offset or low 
frequency color floating. So we write these bits directly into the stream.


\subsection{ The Golomb Coder }

Golomb published in the 70's a coding method to encode runlengths with a 
combination of near optimal huffman codes without going through the huffman
algorithm. This was the base for some arithmetic entropy coders, namely the 
Z- and ZP-Coder which generalize and extend the Golomb coder to improve adaption.
Because of patent issues of Mitsubishi and AT\&T we can't use those derivates.

Instead we use a slightly modified version of the original algorithm. If we 
have a good guess of the range of a number $x$ given by the number of required bits
both on the transmitter and receiver side we encode a number by splitting it in 
two parameters $q$ and $r$:

\begin{eqnarray}
q &=& (x - 1) >> bits     \nonumber\\
r &=& x - 1 - (q << bits) \nonumber
\end{eqnarray}

Now the unary representation of $q$ holds a huffman code for the real number of 
required bits to transmit $r$ binary. And that's exactly what we transmit: the 
unary code of $q$ and the binary code of $r$.

Every time a runlength is encoded we update the average number of bits required
to encode runlengths of this symbol.
 
The Golomb Coder performs well if use it to encode runlengths of 0-runs when the 
lengths of the runs don't differ much or if we have to transmit parameters with 
a known order of magnitude (width/heights/subbitstream lengths/...).



