Make it equal

If you have a set of symbols then the most efficient way of using them is to make sure that the average amount of information per symbol is maximised.

From our discussion so far it  should now be clear that the way to do this is to ensure that each symbol is used equally often – but how?

The answer is to use a code that forces the symbols to occur equally often even if they don’t!

Consider the standard alphabet and divide it into two groups of letters so that the probability of a letter belonging to either group is the same i.e. 0.5. To do this we have to include a mix of likely and not so likely letters to get the right probability. Now with this division of the alphabet we can begin to construct our code by using a zero to indicate that the letter is in the first group and a one to indicate that it is in the second group.

Clearly the first bit of our code has an equal chance of being a one or a zero and we can continue on in this way by sub-dividing each of the two groups into equally likely subsets and assigning 0 to one of them and a 1 to the other.

Now when we receive a set of data bits we use them one after another to find which group the letter is in much like a well known “yes/no” question and answer game.

Each group is equally likely and hence each symbol used in the code is also equally likely (only 8 letters shown).

This code was invented by Shannon and Fanno and named after them. If you can construct such a code it is optimal in the sense that each symbol in the code carries the maximum amount of information. The problem is that you can’t always divide the set into two equally probable groups – not even approximately!

There is a better code.

<ASIN:0198538030>

<ASIN:0470028610>