This test consists of 20 questions. The number (1 to 4) of stars (*) associated with each question is proportional to the level of difficulty. For a correct (respectively false) answer, your score increases (respectively decreases) by one. If you do not provide any answer to a question, your score will be unchanged. The best mark is 20 and the worse is 0. A negative total score is modified to the final mark "0". If the fractional value of the total score x is more than and excluding 0 and less than and including 0.5, then the final mark is the sum of the integer part of x and 0.5. Otherwise, the final mark is the smallest integer greater than or equal to x.



UNCERTAINTY AND INFORMATION RELATED TO EVENTS

Two cards are simultaneously drawn at random from a pack of 52 playing cards.

Let S be a memoryless quaternary source the entropy per symbol of which is 1.5 bit and the symbol rate 1,000 symbols per second.

The minimum binary rate resulting from the encoding of S with a fixed length binary code is, in bits per second :

(question 11 *)

500

1000

2000

4000

Can S be encoded by a uniquely decipherable binary code so that the average bit rate is less than 1,400 bits/sec?

(question 12 **)

yes

no

We intend to construct a Huffman code for the n^th extension of S in such a way that the average bit rate is less than 1,600 bits/sec. What is the minimum extension n of S to be encoded to meet such a condition?

(question 13 **)

4

6

8

10

12

14

Source coding aims to :

(question 14 *)

reduce the symbol rate

increase the symbol rate

The entropy rate of the source which results from a source coding of a source S is :

(question 15 *)

greater than the entropy rate of S

equal to the entropy rate of S

smaller than the entropy rate of S

CHANNEL CAPACITY

The capacity, in bits, of the channel sketched below

is :
(question 16 *)

1	1.5	1.585	2

The capacity, in bits, of the channel sketched below

is :
(question 17 ***)

1	1.5	1.585	2

The capacity, in bits, of the channel sketched below

is :
(question 18 ***)

1.12	1.23	1.31	1.52

The input to a channel is a word of 8 bits. The output is also a word of 8 bits. Each time it is used, the channel flips exactly one of the transmitted bits, but the receiver does not know which one. The other seven bits are received without error. All 8 bits are equally likely to be the one that is flipped. The capacity of this channel is, in bits : (after David MacKay)

(question 19 ****)

3	4	5	6	7

The entropy of a source S is 2.7 bits and its symbol rate 1,000 8-ary symbols per second. One is given a Binary Symmetric Channel of probability of error p = 0.001 and the maximum symbol rate of which is 3,000 bits/sec. Assuming appropriate means are used, is it possible to transmit the outcomes of S through the channel C with an arbitrarily low probability of error?

(question 20 **)

yes

no

Last updated on 5 March 2004.