The Exam
The final exam covers chapters 1 - 5 of the text, "Information and
Coding Theory," by Jones and Jones and chapter 3 of the supplemental
text, "Elements of Information Theory," by Cover and Thomas, which is
on reserve at the library. There will be an emphasis on the
material covered since the second midterm, i.e, sections 5.3-5.6 in Jones
and Jones and chapter 3 in Cover and Thomas. The new material will
be worth approximately 40-50% of the points available. The final will be
approximately twice as long a midterm, will
be out of 140 points and will comprise 35% of the course grade.
General Advice
Studying the homework problems and the midterm exams is certainly a good idea.
There could well be questions on the final similar to or even identical to
homework or midterm problems. While the computations in this class are
not usually difficult, they can be time consuming. Make sure to practice them
and determine the most efficient way to do each kind of computation. I will
put in a few unfamiliar problems, i.e., not like the ones in the homework or
on the midterms. If you do not understand what a question means, please ask
me.
Definitions and Theorems
I may ask you to state one or more definitions or theorems. When you state
a theorem, you should identify all the symbols you use by name.
The following is a list of definitions and theorems that you should be
prepared to state.
Chapter 1
This chapter introduces the basic definitions and notation, including
the definitions of source, code etc. I hope that it goes without saying
that you will need to be comfortable with these basics. Be aware that the
term "code" is
sometimes used in its strict sense as a function from the source alphabet to
the set of non-empty words in the code alphabet, and it sometimes refers just
to the image of this function, i.e., the set of code-words. If you are
unsure what is wanted by a specific test question, please ask.
Also important are uniquely-decodable codes and instantaneous codes. You should be able to identify give codes as uniquely-decodable, instantaneous, neither or both, and to provide examples of such codes, if examples exist. (All instantaneous codes are uniquely decodable.)
The main theorems in this chapter are the Sardinas-Patterson Theorem, Kraft's Inequality and McMillan's Inequality. You should be able to state and apply these results to specific cases. Note that for the Sardinas-Patterson Theorem you should not just provide Theorem 1.10, but also define C_infinity.
Chapter 2
This chapter is about optimal codes, as its title suggests. You need to be
able to state the definition of an optimal code and be able to find an
optimal code and/or the average word-length of an optimal r-ary code
for a given source. To do this, one constructs an r-ary Huffman code, as
Huffman codes are optimal. Note that the result of section 2.3 allows one to
compute the average word-length of a Huffman code without actually constructing
the code. Using this can save time on the test.
Chapter 2 also introduces the n-th extension of a source. Note that a code for the n-th extension of a source S is called an encoding of S.
Chapter 3
You will definitely need to know the definition of entropy and be able to
compute the entropy of a given source. It is also important to have an
intuitive understanding of entropy as uncertainty or information, and to know
its basic mathematical properties, i.e., theorems 3.7, 3.10, and 3.20, and its
relationship to average word-length.
The most important result in this chapter is Shannon's First Theorem, theorem 3.23. You should be able to state the theorem and understand its proof, including the roll of Shannon-Fano codes, inequality 3.8 and the nth extensions of the source.
Chapter 4
Chapter 4 introduces information channels, you need to be familiar with
them and their accompanying notation, e.g., the various probabilities, p_i's,
q_j's, P_ij's, Q_ij's and R_ij's. You will also need to be able to compute
those probabilities. The binary symmetric channel is an important example, so
you should certainly know its definition, and it would not hurt to know
its properties, see sections 4.2 and 4.4.
The system entropies are also defined in chapter 4. You should know their definitions and be able to compute them, and you should have an intuitive understanding of their meaning in terms of the uncertainty or information from the perspective of a sender, receiver or ideal observer.
Mutual information is also defined in chapter 4. Again know the definition of mutual information, be able to compute it and have an intuitive understanding of its meaning. You should also know its mathematical properties, i.e., equations 4.15 and 4.16 theorem 4.11 and its corollary 4.12.
Channel capacity is also defined in chapter 4. You should know and be able to use the definition in some simple cases or in a proof.
Chapter 5
Chapter 5 concerns decision rules and the probability of decoding errors for
those rules. You should know what is meant by an ideal-observer rule, maximum
likelihood rule and nearest-neighbor decoding, and be able to compute their
error probabilities. You should also be able to compute the error
probabilities for a new rules defined in a test question.
The most important result in this section is Shannon's Theorem, which you should be able to state and illustrate. To understand the statement of the theorem you need to know about Hamming distance and the rate of a code.
Be able to use and state the Fano Bound and state and illustrate the converse to Shannon's Theorem. The textbook's statement of the converse of Shannon's Theorem is somewhat vague, follow this link to a clearer statement.
Chapter 3 in Elements of Information Theory
You should be able to state the asymptotic equipartition property, including
an explicit description of convergence in probability, see equation 3.7.
You should know the definition of the typical sets and their properties, see
theorem 3.1.2.
You should be able to outline the encoding scheme described in section 3.2 and know its consequence, Theorem 3.2.1, compare to Shannon's First Theorem.