Information Theory was created by C.E.Shannon in the late 1940s. The management of Bell Telephone Labs wanted him to call it "'Communication Theory" as that is a far more accurate name, but for obvious publicity reasons "Information Theory" has a much greater impact—this Shannon chose and so it is known to this day. The title suggests the theory deals with information—and therefore it must be important since we are entering more and more deeply into the information age. Hence I shall go through a few main results, not with rigorous proofs of complete generality, but rather intuitive proofs of special cases, so you will understand what information theory is and what it can and cannot do for you.

First, what is "information"? Shannon identified information with surprise. He chose the negative of the log of the probability of an event as the amount of information you get when the event of probability p happens. For example, if I tell you it is smoggy in Los Angles then p is near 1 and that is not much information, but if I tell you it is raining in Monterey in June then that is surprising and represents more information. Because log 1=0 the certain event contains no information.

In more detail, Shannon believed the measure of the amount of information should be a continuous function of the probability p of the event, and for independent events it should be additive—what you learn from each independent event when added together should be the amount you learn from the combined event. As an example, the outcome of the roll of a die and the toss of a coin are generally regarded as independent events. In mathematical symbols, if I(p) is the amount of information you have for event of probability p, then for event x of probability p1 and for the independent event y of probability p2, you will get for the event of both x and y

This is the Cauchy functional equation, true for all p1and p2.

To solve this functional equation suppose

then this gives

If p1=p2 and p2=p, then

etc. Extending this process you can show, via the standard method used for exponents, for all rational numbers m/n,

From the assumed continuity of the information measure it follows the log is the only continuous solution to the Cauchy functional equation.

In information theory it is customary to take the base of the log system as 2, so a binary choice is exactly 1 bit of information. Hence information is measured by the formula

Let us pause and examine what has happened so far. First, we have not defined "information", we merely gave a formula for measuring the amount. Second, the measure depends on surprise, and while it does match, to a reasonable degree, the situation with machines, say the telephone system, radio, television, computers, and such, it simply does not represent the normal human attitude towards information. Third, it is a relative measure, it depends on the state of your knowledge. If you are looking at a stream of "random numbers" from a random source then you think each number comes as a surprise, but if you know the formula for computing the "random numbers" then the next number contains no surprise at all, hence contains no information! Thus, while the definition Shannon made for information is appropriate in many respects for machines, it does not seem to fit the human use of the word. This is the reason it should have been called "Communication Theory", and not "Information Theory". It is too late to undo the definition (which produced so much of its initial popularity, and still makes people think it handles "information") so we have to live with it, but you should clearly realize how much it distorts the common view of information and deals with something else, which Shannon took to be surprise.

This is a point which needs to be examined whenever any definition is offered. How far does the proposed definition, for example Shannon's definition of information, agree with the original concepts you had, and how far does it differ? Almost no definition is exactly congruent with your earlier intuitive concept, but in the long run it is the definition which determines the meaning of the concept—hence the formalization of something via sharp definitions always produces some distortion.

Given an alphabet of q symbols with probabilities pi then the average amount of information (the expected value), in the system is

This is called the entropy of the system with the probability distribution pi. The name "entropy" is used because the same mathematical form arises in thermodynamics and in statistical mechanics, and hence the word "entropy" gives an aura of importance which is not justified in the long run. The same mathematical form does not imply the same interpretation of the symbols!

The entropy of a probability distribution plays a central role in coding theory. One of the important results is Gibbs' inequality for two different probability distributions, pi and qi.We have to prove

The proof rests on the obvious picture, Figure 13.I, that

and equality occurs only at x=1. Apply the inequality to each term in the sum on the left hand side

If there are q symbols in the signaling system then picking the qi=1/q we get from Gibbs' inequality, by transposing the q terms,

This says in a probability distribution if all the q symbols are of equal probability, 1/q, then the maximum entropy is exactly In q, otherwise the inequality holds.

Figure 13.I

Given a uniquely decodable code, we have the Kraft inequality

Now if we now define the pseudoprobabilities

where of course E [Qi]=1, it follows from the Gibbs' inequality,

after some algebra (remember that K1 so we can drop the log term and perhaps strengthen the inequality further),

Thus the entropy is a lower bound for any encoding, symbol to symbol, for the average code length L. This is the noiseless coding theorem of Shannon.

We now turn to the main theorem on the bounds on signaling systems which use encoding of a bit stream of independent bits and go symbol to symbol in the presence of noise, meaning there is a probability a bit of information is correct, P>1/2, and the corresponding probability Q=1–P it is altered when it is transmitted. For convenience assume the errors are independent and are the same for each bit sent, which is called "white noise".

We will encode a long stream of n bits into one encoded message, the n-th extension of a one bit code, where the n is to be determined as the theory progresses. We regard the message of n bits as a point in an n-dimensional space. Since we have an n-th extension, for simplicity we will assume each message has the same probability of occurring, and we will assume there are M messages (M also to be determined later), hence the probability of each initial message is

We next examine the idea of the channel capacity. Without going into details the channel capacity is defined as the maximum amount of information which can be sent through the channel reliably, maximized over all possible encodings, hence there is no argument that more information can be sent reliably than the channel capacity permits. It can be proved for the binary symmetric channel (which we are using) the capacity C, per bit sent, is given by

where, as before, P is the probability of no error in any bit sent. For the n independent bits sent we will have the channel capacity

If we are to be near channel capacity then we must send almost that amount of information for each of the symbols ai, i=1,…, M, and all of probability 1/M, and we must have

when we send any one of the M equally likely messages ai. We have, therefore

With n bits we expect to have nQ errors. In practice we will have, for a given message of n bits sent, approximately nQ errors in the received message. For large n the relative spread (spread=width, of the distribution of the number of errors will be increasingly narrow as n increases.

From the sender's point of view I take the message ai to be sent and draw a sphere about it of radius

which is slightly larger by e2 than the expected number of errors, Q,Figure 13.II. If n is large enough then there is an arbitrarily small probability of there occurring a received message point bj which falls outside this sphere. Sketching the situation as seen by me, the

Figure 13.II

sender, we have along any radii from the chosen signal, ai, to the received message, bj, with the probability of an error is (almost) a normal distribution, peaking up at nQ, and with any given e2 there is an n so large the probability of the received point, bj, falling outside my sphere is as small as you please.

Now looking at it from your end, Figure 13.III, as the receiver, there is a sphere S(r) of the same radius r about the received point, bi, in the space, such that if the received message, bi, is inside my sphere then the original message ai sent by me is inside your sphere.

How can an error arise? An error can occur according to the following table:

Here we see that if there is at least one other original message point in the sphere about your received point then it is an error since you cannot decide which one it is. The sent message is correct only if the sent point is in the sphere and there is no other code point in it.

We have, therefore, the mathematical equation for a probability PE of an error, if the message sent is ai,

Figure 13.III

We can drop the first factor in the second term by setting it equal to 1, thus making an inequality

But using the obvious fact

hence

applied repeatedly to the last term on the right

By making n large enough the first term can be made as small as we please, say less than some number d. We have, therefore,

We now examine how we can make the code book for the encoding of the M messages, each of n bits. Not knowing how to encode, error correcting codes not having been invented as yet, Shannon chose a random encoding. Toss a penny for each bit of the n bits of a message in the code book, and repeat for all M messages. There are nM tosses hence

possible code books, all books being of the same probability 1/2nM. Of course the random process of making the code book means there is a chance there will be duplicates, and there may be code points which are close to each other and hence will be a source of probable errors. What we have to prove is this does not occur with a probability above any positive small level of error you care to pick—provided n is made large enough.

The decisive step is that Shannon averaged over all possible code books to find the average error! We will use the symbol Av[.] to mean average over the set of all possible random code books. Averaging over the constant d of course gives the constant, and we have, since for the average each term is the same as any other term in the sum,

which can be increased (M–1 goes to M),

For any particular message, when we average over all code books, the encoding runs through all possible values, hence the average probability that a point is in the sphere is the ratio of the volume of the sphere to the total volume of the space. The volume of the sphere is

where s=Q+e2<1/2, and ns is supposed to be an integer.

The largest term in this sum is the last (on the right). We first estimate the size of it, via Stirling's formula for the factorials. We then look at the rate of fall off to the next term before it, note this rate increases as we go to the left, and hence we can: (1) dominate the sum by a geometric progression with this initial rate, then (2) extend the geometric progression from ns terms to an infinite number, (3) sum the infinite geometric progression (all standard algebra of no great importance) and we finally get (4) the bound (for n large enough)

Note how the entropy H(s) has appeared in a binomial identity.

We have now to assemble the parts, note the Taylor series expansion of H(s)=H(Q+e2) gives a bound when you take only the first derivative term and neglect all others, to get the final expression

where

All we have to do now is pick an e2 so e3&lte1 and the last term will get as small as you please with sufficiently large n. Hence the average error of PE can be made as small as you please while still being as close to channel capacity C as you please.

If the average over all codes has a suitably small error, then at least one code must be suitable—hence there exists at least one suitable encoding system. This is Shannon's important result, the "noisy coding theorem", though let it be noted he proved it in much greater generality than the simple binary symmetric channel I used. The Mathematics is more difficult in the general case, but the ideas are not so much different, hence the very particular case used suffices to show you the true nature of the theorem.

Let us critique the result. Again and again we said, "For sufficiently large n". How large is this n? Very, very large indeed if you want to be both close to channel capacity and reasonably sure you are right! So large, in fact, you would probably have to wait a very long time to accumulate a message of that many bits before encoding it, let alone the size of the random code books (which being random cannot be represented in a significantly shorter form than the complete listing of all Mn bits, both n and M being very large).

Error correcting codes escape this waiting for a very long message and then encoding it via a very large encoding book, along with the corresponding large decoding book, because they avoid code books and adopt regular (computable) methods. In the simple theory they tend to lose the ability to come very near to the channel capacity and still keep an arbitrarily low error rate but when a large number of errors are corrected by the code they can do well. Put into other words, if you provide a capacity for some level of error correction then for efficiency you must use this ability most of the time or else you are wasting capacity, and this implies a high number of errors corrected in each message sent.

But the theorem is not useless! It does show, in so far as it is relevant, efficient encoding schemes must have very elaborate encodings of very long strings of bits of information. We see this accomplished in the satellites which passed the outer planets; they corrected more and more errors per block as they got farther and farther from both the Earth and the Sun (which for some satellites supplied the solar power of about 5 watts at most, others used atomic power sources of about the same power). They had to use high error correcting codes to be effective, given the low power of the source, their small dish size, the limited size of the receiving dishes on Earth as seen from their position in space, and the enormous distances the signal had to travel.

We return to the n-dimensional space which we used in the proof. In the discussion of n-dimensional space we showed almost all the volume of a sphere lay near the outer surface—thus for the very slightly (relatively) enlarged sphere about the received signal it is almost certain the original sent signal lies in it. Thus the error correction of an arbitrarily large number of errors, nQ, with arbitrarily close to no errors after decoding is not surprising. What is more surprising is the M spheres can be packed with almost no overlap—again an overlap as small as you please. Insight as to why this is possible comes from a closer examination of the channel capacity than we have gone into, but you saw for the Hamming error correcting codes the spheres had no overlap. The many almost orthogonal directions in n-dimensional space indicates why we can pack the M sphere into the space with little overlap. By allowing a slight, arbitrarily small amount, of overlap which can lead to only a very few errors in your decoding you can get this dense packing. Hamming guaranteed a certain level; Shannon only a probably small error but as close to the channel capacity as you wish, which Hamming codes do not do.

Information theory does not tell you much about how to design, but it does point the way towards efficient designs. It is a valuable tool for engineering communication system between machine-like things, but as noted before it is not really relevant to human communication of information. The extent to which biological inheritance, for example, is machine-like, and hence you can apply information theory to the genes, and to what extent it is not and hence the application is irrelevant, is simply not known at present. So we have to try, and the success will show the machine-like character, while the failure will point towards other aspects of information which are important.

We now abstract what we have learned. We have seen all initial definitions, to a larger or smaller extent, should get the essence of our prior beliefs, but they always have some degree of distortion and hence non-applicability to things as we thought they were. It is traditional to accept, in the long run, the definition we use actually defines the thing defined; but of course it only tells us how to handle things, and in no way actually tells us any meaning. The postulational approach, so strongly favored in mathematical circles, leaves much to be desired in practice.

We will now take up an example where a definition still bothers us, namely IQ. It is as circular as you could wish. A test is made up which is supposed to measure "intelligence", it is revised to make it as consistent internally as we can, and then it is declared, when calibrated by a simple method, to measure "intelligence" which is now normally distributed (via the calibration curve). All definitions should be inspected, not only when first proposed, but much later when you see how they are going to enter into the conclusions drawn. To what extent were the definitions framed as they were to get the desired result? How often were the definitions framed under one condition and are now being applied under quite different conditions? All too often these are true! And it will probably be more and more true as we go farther and farther into the softer sciences, which is inevitable during your life time.

Thus one purpose of this presentation of information theory, besides its usefulness, is to sensitize you to this danger, or if you prefer, how to use it to get what you want! It has long been recognized the initial definitions determine what you find, much more than most people care to believe. The initial definitions need your careful attention in any new situation, and they are worth reviewing in fields in which you have long worked so you can understand the extent the results are a tautology and not real results at all.

There is the famous story by Eddington about some people who went fishing in the sea with a net. Upon examining the size of the fish they had caught they decided there was a minimum size to the fish in the sea! Their conclusion arose from the tool used and not from reality.