As well as the basic form of Huffman coding, Huffman’s algorithm can also be used to encode streams to deliver compression as well as coding (at a cost of codes being not *immediately* decipherable).

Once again, with thanks to Information and Coding Theory, here’s a brief explanation.

With Huffman coding we can directly code a binary symbol stream where .

But with *encoding* we can produce a code for where is arbitrary, e.g.

So let us assume (e.g. we are transmitting a very dark image via our fax machine) that the probability of and for

Then we have the following probability distributions:

:

:

:

:

:

:

:

:

We can now compute the average word length in the Huffman code – by simply adding the probabilities of the newly created ‘joint’ symbols:

Which obviously looks like the opposite of compression! But, of course we are encoding three symbols, so the actual word length per symbol becomes , in other words somewhat less than 1.

###### Related articles

- A blast from the past: Huffman coding (cartesianproduct.wordpress.com)
- Characteristic functions and the Lévy’s continuity theorem (maikolsolis.wordpress.com)