1
Theory of Information: Problems 1 to 15

1.1. Problem 1 - Entropy

We consider the information transmission channel of memoryless binary symmetrical type of Figure 1.1.

Figure 1.1. Basic diagram of a digital communication

It is assumed that the signal-to-noise ratio leads to the following values of conditional probabilities of errors:

The source of binary information is considered to emit independent information with the following probabilities:

1. 1) Calculate the source entropy H(X).
2. 2) Calculate the entropy H(Y) at the receiver end.
3. 3) Calculate the conditional entropy H(Y/X) (entropy of transmission error).
4. 4) Calculate the loss of information in the transmission channel H(X/Y).
5. 5) Deduce the average amount of information received by the recipient for each binary symbol sent I(X, Y) (mutual information).
6. 6) Determine the channel capacity C and show that it is obtained when p1 = 0.5.

Solution of problem 1

1. 1) By definition, we have:

   then:

2. 2) By definition, we have:

   and:

   hence:

3. 3) In the same way, we have:

   and:

   Since we are dealing with a binary symmetric communication channel, it turns out that:

4. 4) We have:

   That is:

5. 5) By definition, we have:
6. 6) By definition, we have:

You need to have the numerator of the log function equal to the denominator, hence:

Thus, the maximum defines the capacity C of the communication channel and is obtained for:

1.2. Problem 2 - K-order extension of a transmission channel

A memoryless binary symmetric transmission channel is considered: whatever the binary information to be transmitted, the probability of the transmission error is constant, equal to p.

Figure 1.2. Basic block diagram of a digital communication of a memoryless information source

A. K-order extension of a memoryless binary symmetric channel of error probability p

The k-order extension channel has an input alphabet of 2k binary words of length k and an output alphabet identical to that of the input alphabet. This channel is thus represented by a square matrix Pk of dimension [2k, 2k] whose element pij corresponds to the probability of receiving yj conditionally to have xi transmitted p(yj/xi).

1. 1) If d is the Hamming distance between the two binary words of length k corresponding for one to the symbol xi, and for the other to the symbol yj, express the probability pij according to the three parameters: p, k, d.

B. Second-order extension of a memoryless binary symmetric channel

1. 2) Write completely in literal form as a function of p the matrix P2 representative of the second order extension of the binary symmetric channel.
2. 3) The information source is considered to be transmitting equiprobable quaternary symbols xi in the channel. Calculate the probability p(yj) to receive a symbol yj.
3. 4) Deduce the relationship which exists between the elements pij of the matrix P2 representative of the second order extension of the binary symmetric channel and the probability p(xi/yj) that the symbol xi was emitted conditionally having received yj.
4. 5) Calculate the average amount of information H(X/Y) lost in the channel due to transmission errors. You will express H(X/Y) as a function of:

C. Fourth-order extension of a memoryless binary symmetric channel

The size of the input alphabet of the source is then 16 . The output alphabet is the same as that of the input alphabet.

The source is considered to emit equiprobable symbols xi.

1. 6) We extrapolate the result obtained in B-5 by considering that we have:

In the case p = 0.03, calculate the statistical mean of the information amount H(X/Y) lost per symbol sent.

1. 7) What is the entropy H(X) of the source?
2. 8) What is the maximum number of possible errors on a symbol received?

Solution of problem 2

A. K-order extension

1. 1) The symbol xi is made up of k bits. It is the same for the symbol yj, so:

The communication channel is memoryless, so the probability of obtaining a given bit at the output depends only on the bit transmitted at the input (in addition to the intrinsic properties of the transmission channel itself), hence:

because of the independence between the source of information and the communication channel.

The Hamming distance d = dH(yj, xi) is the number of bits of the same rank that are different between the symbol yj and symbol xi.

Then:

This law is close to the Binomial law because if p is the probability of a wrong decision on bit b, then (1 - p) is the probability of a right decision on bit b.

B. Second-order extension of the channel

1. 2) We have:

because of the symmetry.

Table 1.1. Matrix P2 representative of second-order extension of a binary symmetric channel

1. 3) We have:

   Yet, the symbols are equiprobable:

   Then, the symbols yj are also equiprobable:

2. 4) We have:

because:

1. 5) Average amount of bit of information H(X/Y) lost in the transmission channel.

   We have:

because here we have:

C. Fourth-order extension of the transmission channel

1. 6) p = 0.03 and H(X/Y) = 4H(p).

Average amount of information (in bit of information) lost per binary symbol sent?

We have:

1. 7) Entropy of the source?

and:

hence:

1. 8) Maximum number of possible errors?

1.3. Problem 3 - Compressed speech digital transmission and Huffman coding

In the context of the transmission of the highly compressed speech signal over the telephone channel entirely in digital form, let us look at the problem of statistical source coding.

An information source S delivering elementary symbols s belonging to a symbol dictionary of size 6 is considered. The probabilities of transmission of this simple source of information are given in Table 1.2.

Table 1.2. Probabilities of emitting symbols s by the information source

The symbols are delivered by the source S every T = 10-3 s.

1. 1) Determine the entropy H(S) of the source. Deduce the entropy bitrate Ds.
2. 2) Construct the statistical Huffman coding, called code C1, which generates a binary code associated with each symbol si.
3. 3) Deduce the average length of code C1 and the bitrate D1 per second.
4. 4) What are the efficiency ?1 and redundancy ?1 of code C1 ?
5. 5) If we chose a fixed-length code (code C2), what would be its efficiency ?2? What do you conclude?
6. 6) Would it be possible to transmit this source of information over a transmission channel having a bitrate capacity of 2,400 bit/second?

Solution of problem 3

1. 1) The entropy of the source is:

   Recall:

   The entropy bitrate of the source is:

2. 2) Construction of the Huffman code.

   Table 1.3. Construction of the Huffman code C1

3. 3) Average length of codewords:

   Bitrate per second:

4. 4) Efficiency and redundancy of the Huffman code:
5. 5) Fixed-length code C2.

   Since we have 6 messages, we need 3 bits as: 22 < 6 < 23, then:

   The fixed-length code C2 is less efficient than the Huffman code C1.

   The bitrate per second with code C2 is: 3 × 1,000 = 3 Kbit/s.

6. 6) The capacity of the channel is 2.4 Kbit/s, so we can transmit the code C1 but not the code C2 because the bitrate of C2 is more important than the capacity of the channel.

1.4. Problem 4 - Coding without...