The original work by C Shannon is "A mathematical theory of communication." Bell System Tech. J., 27: 379-423, 623-656 (1948). [I need to read this!]
The starting point for the equation in the last post is Shannon's entropy. H is the entropy, which is a function of the probability distribution p_i...p_n, where p is the probability. Here we use log base 2.
We can see how the essential parts of the coding theorem come if we consider a binary system. That is, we have something occurring with probability p, or not with 1-p. The plot of this function is shown, with the maximum at p = 1/2.
Think about flipping a fair coin. The probability of heads is 1/2, and tails is also 1/2. In such a case, the entropy is exactly 1. What does that mean? When the probability is 1/2 for something to occur in a problem that has only two options, we are going to gain the maximum amount of information after the measurement or "flip." Or another way to put it, for such a fair coin toss, there's a maximal amount of uncertainty in what will happen before the flip. You'll really only know if it's heads or tails after tossing the coin.
Another way to think about the entropy, in an operational sense (from QCQI), is that it's a measure of the resources needed to store information. In the fair coin toss, you need 1 coin. I'm not too sure about this interpretation though.
How does the entropy have this form? I'm not ready to give a rigorous review, though if you think from statistical mechanics, the entropy comes out to be of the form -k*ln(x), where k is Boltzmann's and x is the number of states, or the probability of a certain configuration. An intuitive justification offered in QCQI is that the information carried in a certain event must be 1) function only of the probability of the event 2) smooth function (infinitely differentiable) of the probability 3) I(pq) = I(p) + I(q) when p, q > 0. This leads to a log function.
