Chapter 7
Information Theory

7.1  Redundancy

Information for this chapter was taken from Steven Roman's book Coding and information theory, Springer, 1992, pp.1-4.

A common model for a communications channel is the binary symmetric channel. This is defined as follows: the input data running through the binary symmetric channel is a string of bits (zeros and ones), and the channel is `noisy', that is, there is a non-zero constant probability p < 1/2 that a zero is changed to a one, or vice versa. We say that a channel error or bit error occurs with probability p, no matter what the input bit is.

If the receiver simply decides to accept a received bit as correct, then the probability of making a decision error on each bit of the input data is p.

We want a scheme to enable us to detect and possibly correct such errors. This is achieved by introducing redundancy into the input data. One way is to use a repetition code:

Suppose that for each 0 in the original input string we transmit 000, and for each 1 in the input string we transmit 111. If, say, a triple 010 is received, the decoder must make a decision on whether 000 or 111 has been sent. Suppose the decoder uses the `majority decision rule', that is, the decoder decides that the original bit was a 0 because there are more zeros than ones in the received triple 010.

This decision will be correct if the original triple was 000 and the second bit was changed, from 0 to 1, but will be incorrect if the original triple was 111 and the first and third bits were changed from 1 to 0.

Thus the `majority decision rule' (and indeed any decision rule) involves a decision error.

If we assume that errors occur independently (which is a convenient assumption, but not always reasonable) then the probability p_error of making a decision error with the procedure described above is the probability that 2 or 3 bits in a triple have changed, and this equals

perror = æ è 3 2 ö ø p2(1-p) + æ è 3 3 ö ø p3 = 3p2 -2p3.

Note that p_error is always less than p because p < 1/2.

Conclusion 1. Encoding the original source data by introducing redundancy may reduce the probability of decision error.

A general repetition code involves transmitting a string 00... 0 of length 2n+1 for each input bit 0, and transmitting a string 11... 1 of length 2n+1 for each input bit 1. We use an odd number 2n+1 to enable us to use the `majority decoding rule': if a received string of odd length 2n+1 contains more zeros than ones then we decode it as 0, and vice versa.

Thus the probability p_error of making a decision error is the probability that there are at least n+1 bit errors in the received string. The number of bit errors is a binomial random variable with parameters (2n+1, p) and the theory of binomial random variables tells us

(i) that the expected number of errors is (2n+1)p, which is less than n+1/2 since p < 1/2, and
(ii) that p_error ® 0 as n®¥.

However, using 2n+1 units of channel time to send one source bit is very expensive. One measure of this transmission cost is

rate of transmision =  length of source message length of encoded message

For the general repetition code, the rate of source transmission is 1/(2n+1).

Conclusion 2. The probability of decision error can be made arbitrarily small at the expense of lowering the rate of transmission.

However the rate of transmission might become unacceptably small.

Basic Idea. We usually group the source data, one or several bits at a time, and encode each group of bits into a codeword by an encoding scheme (such as a repetition code) which assigns a codeword to each group from the source message. This encoding adds redundancy to enable detection of errors, and possibly also correction of errors.

Source     ®₁₀₁₁    encoder    ®_1011010     channel (may introduce errors)  ®_1010010    decoder (corrects errors)    ®₁₀₁₁ receiver.

There is a remarkable result due to Shannon (1948), and father of Information Theory. Claude Shannon was the mathematician who laid the foundations of Information Theory while working at Bell Labs in the US. He died this year (2001) at the age of 84. You can find an obituary for him at the

Bell Labs web site.

Shannon's Noisy Channel Theorem For every channel there is a number C called the capacity of the channel such that, if it is acceptable to have a rate of transmission less than C, then there exists an encoding scheme that will reduce the probability of decision error to any desired (low) level.

It turns out that, for the binary symmetric channel,

C=1+plog2p+(1-p)log2(1-p)

where p is the probability of bit error. (Here log₂ p, the `log to base 2 of p', is the real number a such that p=2^a.)

For example, if p=0.01 then C ~ 0.919.

Problems 1. Shannon's Noisy Channel Theorem does not give a construction for these good encoding schemes. The proof only shows that they exist. No one has yet discovered how to construct them.

2. There are other desirable qualities for encoding schemes that compete with the quality of having a very small probability of decision error. For example, we would like to have easy encoding and decoding procedures. Also we want the codewords to have moderate length (and as we saw with repetition codes, sometimes a small decision error probability requires very long codewords).

7.2  Information and uncertainty

Shannon(1948) introduced a function to measure the uncertainty involved in making random selections or sampling from a finite set, and he wanted also to measure the information one could gain from such sampling.

Suppose we will make a random selection from a finite set S={x₁,...,x_n} according to a probability distribution P ={p₁,...,p_n}, that is the probability of selecting x_i on a single random selection is p(x_i)=p_i for each i (so 0 £ p_i £ 1 and å_ip_i=1).

Before making the random selection there is possibly some uncertainty about the outcome. After making the selection there is possibly some gain in information. Shannon wanted to formalise these intuitive notions.

One extreme case: p₁=1, and all other p_i=0. Here there is no uncertainty and no gain in information from the outcome.

Another almost extreme case: `Most' p<sub>i</sub>=0. Here we have a `little' uncertainty and we gain a `little' information from the outcome.

We have maximum uncertainty if p₁=... = p_n=1/n, and we gain maximum information from the outcome.

Shannon wanted an `uncertainty function' H(P)=H(p₁,...,p_n) that would give some measure of the uncertainty associated with random selection. It should depend only on the probability distribution P, and it should have the following properties.

Property 1. H is continuous.

Reason: Small changes in P should only change the value of H slightly.

Property 2. H([ 1/n],...,[ 1/n]) < H([ 1/(n+1)],...,[ 1/(n+1)]).

Reason: When all the p_i are equal then increasing the number of outcomes increases the uncertainty.

Property 3. Whenever n=b₁+...+b_k with each b_i a positive integer,

H(  1 n ,...,  1 n ) = H(  b1 n ,...,  bk n )+ k å i=1   bi n H(  1 bi ,...,  1 bi )

.

Reason: Making a random selection by the following two step process should not change the uncertainty. Partition the set S={x₁,...,x_n} of size n into k blocks S={B₁|B₂|...|B_k} with |B_i|=b_i. First choose one of the k blocks in such a way that the probability of choosing B_i is b_i/n (i.e. proportional to |B_i|) - the first summand on the right hand side gives the uncertainty for this choice. Next choose an element from the selected B_i such that each of the b_i elements of B_i has probability 1/b_i of being chosen. The uncertainty of this second choice is H([ 1/(b_i)],...,[ 1/(b_i)]) and the second term on the right hand side is the average uncertainty of this second step over all the possible outcomes of the first step, i.e. å_i=1^kP(B_i)×(Uncertainty inchoosing from B_i).

Shannon's Uncertainty Theorem. A function H satisfies properties 1, 2 and 3 if and only if H=H_b for some b > 1, where

Hb(p1,...,pn)=- n å i=1  pilogb pi= n å i=1  pilogb  1 pi

and we set plog_bp=0 for p=0.

The Proof of this theorem is not required for this unit. For anyone interested a proof can be found, for example, in Steven Roman's book Coding and information theory, Springer, 1992, pp.13-15.

Entropy The quantity H_b(p₁,...,p_n) is called the base b entropy of the distribution P ={p₁,...,p_n}. When b=2 we often say that H₂(p₁,...,p_n) is the binary entropy of P.

Note the entropy measures both the amount of uncertainty before sampling, and the amount of information obtained by sampling.

Recall how logs work: for a positive real number b and a non-zero real number x, log_b x is defined as the real number a such that x=b^a. This is related to the natural log of x, that is log to base e, as follows: x=b^a  Þ log_ex=log_e(b^a)=alog_eb = log_b x·log_e b  Þ 

logb x = logex/loge b.

Don't forget that -log_b x = log_b(1/x) for all b and x.

Units of Entropy: If S={0,1,...,k-1}, then sampling from S with equal probabilities p₁=p₂=... = p_k=[ 1/k] gives an amount of information that we will take to be `one k-ary unit of information'. Since

Hk(  1 k ,...,  1 k )=- k å i=1   1 k logk  1 k =1

the base k entropy function H_k measures the number of k-ary units of information. In particular the binary entropy function H₂ measures information in binary units or bits. If we sampled from S={0,1} with equal probability then one random selection would give one bit of information.

Note. In many books the term `binary units' is abbreviated to `binits' or `bits'. However this use of the word `bit' is different from our common use of `bit' for a zero or 1 in a binary string.

Example 1 Sampling from the set S={x₁,x₂,x₃} with probabilities p₁=p₂=p₃ = [ 1/3] gives

H2(  1 3 ,  1 3 ,  1 3 )=  1 3 log23+  1 3 log23+  1 3 log23=log23 » 1.585 bits

while sampling from S={x₁,x₂,x₃} with probabilities p₁=p₂=[ 1/4] and p₃=[ 1/2] gives

H2(  1 4 ,  1 4 ,  1 2 )=  1 4 log24+  1 4 log24+  1 2 log22 = 1.5 bits.

With the second sampling we are more certain about the outcome (why?) and so it makes sense that the information obtained is less.

Example 2 In Table 2.6 we gave theprobabilities of occurrence of each of the letters A to Z in English text. If we take these probabilities p_A,...,p_Z as the probability distribution P for random sampling from a piece of English text, and compute H₂(p_A,...,p_Z) then the result is roughly 4. Thus on the average we get 4 bits of information by sampling a single letter from English text.

7.3  Entropy

`The' entropy function. The important entropy function

H2(p,1-p) = -plog2p -(1-p)log2(1-p) = plog2  1 p +(1-p)log2  1 1-p

is called the entropy function and is often written as H(p). It turns out that this is the entropy function associated with a binary symmetric communication channel.

Uncertainty in transmitting one bit. For each bit transmitted by a binary symmetric channel there is a bit error probability p that an error will occur, that is, if 0 is transmitted then with probability p a 1 is received, and vice versa. We can think of each received bit being a random sample from the set S={ error, no error }, where the probabilty of error is p. The probability distribution corresponding to this is P ={p,1-p}, and its entropy is H₂(P)=H(p).

Example If p=0.01 then H(0.01)=-0.01log₂0.01 -0.99log₂0.99 ~ 0.081. In fact for every value of p such that 0 < p < 1/2 we get a value H(p) strictly between 0 and 1 (see Exercise Set 7.4, question 6).

Information carried by one bit. Suppose a computer is waiting to receive a bit sent along a binary symmetric channel with bit error probability p. Before the bit is received the computer is ready to receive either a 0 or a 1, with equal probability. So the uncertainty before the bit is received is

Hbefore = H(  1 2 ) = H2(  1 2 ,  1 2 )=-  1 2 log2  1 2 - (1-  1 2 )log2(1-  1 2 ) = -log2  1 2 = 1.

The uncertainty associated with receiving the bit is H_after=H(p). The reason we may still have some uncertainty is that the received bit may not be equal to the bit that was sent. This uncertainty H(p) measures the amount of `noise' in the channel.

We call the difference H_before-H_after=1-H(p) the information obtained from receiving the bit. If there was no noise, that is, if p=0, then H(p)=0 and the information obtained is precisely 1-0=1 binary unit of information. On the other hand if, say, p=0.01 then we obtain 1-H(0.01)=1-0.081=0.919 binary units of information for each bit transmitted.

Channel Capacity. We say that a binary symmetric channel with bit error probability p has channel capacity C=1-H(p) binary units per bit. This measures the information obtained by receipt of one bit over the channel. [The definition of capacity for other channels is more complicated than this.] The channel capacity is the constant occurring in Shannon's Noisy Channel Theorem.

7.4  Exercise Set: Information Theory

1. What are the codewords in a repetition code where each input bit is encoded as a string of length 5? Compute the probability p_error of making a decision error where the bit error is p=1/4.

2. Compute (a) H₂(1/8,1/8,3/4), (b) H₂(1/3,2/3), (c) H₂(1,0,0). (Recall the convention that plog_bp=0 for p=0.)

3. Suppose we toss a fair coin, and if the outcome is `heads' then we toss it again. How much uncertainty is there in the outcome? (Use the binary entropy function.)

4. Find a relationship between H_b(P) and H_c(P).

5. Prove that `the entropy function' H(x) = -xlog₂x-(1-x)log₂(1-x) (0 < x < 1) is symmetric about x=1/2, that is, H(1/2-x)=H(1/2+x) for 0 < x < 1/2.

6. (a) Compute the derivative of `the entropy function' H(x)=-xlog₂x-(1-x)log₂(1-x), for 0 < x < 1. (b) Prove that the maximum value for H(x) on the closed interval [0,1] occurs at x=1/2. Sketch a graph of H(x) on this interval. (c) Prove that, for each p such that 0 < p < 1/2, we have 0 < H(p) < 1. [Recall that log₂x=log_ex/log_e2; also recall the convention that plog₂p=0 when p=0.]

7. [From Roman, p20] The accuracy of a certain radio station's weather man at predicting rain is given by the following chart.

	Actual rain	Actual no rain
Predicts rain	1/12	1/6
Predicts no rain	1/12	2/3

For example, 1/12 of the time the weatherman predicts rain when in fact it does rain. Notice that the weatherman is correct 3/4 of the time. An uninformed listener observes that he could be correct 5/6 of the time by simply always predicting no rain. He applies for the weatherman's job. However the station manager declines to hire the listener. Why?

7.5  Exercise Solutions: Information Theory

1. The codewords are 00000 and 11111; p_error is the probability of making at least three bit errors. So

perror = æ è 5 3 ö ø æ è  1 4 ö ø 3   æ è  3 4 ö ø 2   + æ è 5 4 ö ø æ è  1 4 ö ø 4   æ è  3 4 ö ø + æ è 5 5 ö ø æ è  1 4 ö ø 5   =  1 45 æ è 10·32+5·3+1 ö ø +  106 45 =  53 128 =0.414

2. (a)

H2(  1 8 ,  1 8 ,  3 4 ) = -  1 8 log2  1 8 -  1 8 log2  1 8 -  3 4 log2  3 4 » 1.06

bits. Note -log₂[ 1/8]=log₂8=log₂ 2³=3, etc.

(b)

H2(  1 3 ,  2 3 )=-  1 3 log2  1 3 -  2 3 log2  2 3 » 0.918 bits.

(c) H₂(1,0,0)=-1·log₂1-0-0=0.

3. The possible outcomes are (i) tails on the first toss with probability p₁=1/2, (ii) heads on the first toss followed by tails when we toss again, with probability p₂=(1/2)×(1/2)=1/4, and (iii) heads on the first toss followed by heads when we toss again, with probability p₃=(1/2)×(1/2)=1/4. The uncertainty is H₂(1/2,1/4,1/4) which we computed as 1.5 bits in Example 7.2.1.

4. Now H_b(P)=-å_i p_ilog_b p_i and H_c(P)=-å_i p_ilog_c p_i. Since log_b p_i=log_e p_i/log_e b = (log_e p_i/log_e c)·(log_e c/log_eb)=log_c p_i·(log_ec/log_eb), for each i, we get H_b(P)=H_c(P)·(log_e c/log_eb).

5. H(1/2+x)=-(1/2+x)log₂(1/2+x)-(1-(1/2+x))log₂(1-(1/2+x)) = -(1-(1/2-x))log₂(1-(1/2-x)) -(1/2-x)log₁(1/2-x)=H(1/2-x).

6. Since log₂x=clogx where c=1/log2 and we write logx=log_ex, we have H(x)=-cxlogx -c(1-x)logx. For 0 < x < 1, using the product rule for differentiation,

H¢(x) = -clogx -cx·  1 x +clog(1-x) -c(1-x)·  1 1-x ·(-1) = clog(  1-x x ).

Now H(x) is differentiable on (0,1), and H¢(x)=0  Û log([(1-x)/x]) = 0  Û [(1-x)/x]=1  Û x=1/2. Thus there is a local extremum at x=1/2. Note that 0 < x < 1/2  Þ [(1-x)/x] = [ 1/x]-1 > 2-1=1  Þ log([(1-x)/x]) > log1=0  Þ H¢(x) > 0  Þ H(x) is increasing. By question 5, H(x) is symmetric about x=1/2 so H(x) is decreasing for 1/2 < x < 1. Hence H(x) has a local maximum at x=1/2. The values at the endpoints are H(0)=H(1)=0 so H(x) has a global maximum at x=1/2 and H(1/2) = -[ 1/2]log₂[ 1/2]-[ 1/2]log₂[ 1/2] = -log₂[ 1/2] = 1. Thus for 0 < p < 1/2, we have 0 < H(p) < 1.

7. The station manager made his decision based on the relative amounts of information that the weatherman and the listener could provide. Let's model this by assuming that there are four possible events: RR=`actual rain and rain predicted'; RN=`actual rain and no rain predicted'; NR=`actual no rain and rain predicted'; NN=`actual no rain and no rain predicted'. From the data given the probability of rain is 1/6, and of no rain is 5/6.

For the weatherman the probability distribution P_W to be used is p_RR=1/12, p_RN=1/12, p_NR=1/6, p_NN=2/3 (from the table given). The information in binary units conveyed by a single announcement is therefore

H2(PW) = -  1 12 log2(  1 12 )-  1 12 log2(  1 12 )-  1 6 log2(  1 6 )-  2 3 log2(  2 3 ) » 1.4183.

For the uninformed listener the probability distribution P_L to be used is p_RR=0, p_RN=1/6, p_NR=0, p_NN=5/6. The information in binary units conveyed by a single announcement is therefore

H2(PL) = -  1 6 log2(  1 6 )-  5 6 log2(  5 6 ) » 0.6500.

Since the weatherman was able to give greater information from his forecasts, the station manager chose to retain him in the job.