0.13 Coding  (Page 4/22)

The base of the logarithm can be any (positive) number. The most common choice is base 2, in which case the measurementof information is called bits . Unless otherwise stated explicitly, all logs in this chapter are assumed to be base 2.

Suppose there are $N=3$ symbols in the alphabet, which are transmitted with probabilities $p\left(x_1\right)=1/2$ , $p\left(x_2\right)=1/4$ , and $p\left(x_3\right)=1/4$ . Then the information conveyed by receiving $x_1$ is 1 bit, since

Similarly, the information conveyed by receiving either $x_2$ or $x_3$ is $I\left(x_2\right)=I\left(x_3\right)=log\left(4\right)=2$ bits.

Suppose that a length $m$ binary sequence is transmitted, with all symbols equally probable. Thus $N=2^m$ , $x_i$ is the binary representation of the $i$ th symbol for $i=1,2,...,N$ , and $p\left(x_i\right)=2^{-m}$ . The information contained in the receipt of any given symbol is

There is an alternative definition of information (in common usage in the mathematical logic and computerscience communities) which defines information in terms of the complexity of representation,rather than in terms of the reduction in uncertainty. Informally speaking, this alternative defines thecomplexity (or information content) of a message by the length of the shortest computer program thatcan replicate the message. For many kinds of data, such as a sequence of random numbers, the two measuresagree because the shortest program that can represent the sequence is just a listing of thesequence. But in other cases, they can differ dramatically. Consider transmitting the first million digits of thenumber $\pi$ . Shannon's definition gives a large information content (as in [link] ), while the complete sequence can, in principle, be transmittedwith a very short computer program.

Redundancy

All the examples in the previous section presume that there is no relationshipbetween successive symbols. (This was the independence assumption in [link] .) This section shows by example that real messages often have significantcorrelation between symbols, which is a kind of redundancy. Consider the following sentence from Shannon's paper A Mathematical Theory of Communication :