Data Compression 2006 Fall

Lecturers:

András Antos

Classes per week:

Credits:

Exam:

written
December 13, 2006, 10:15 a.m. T.64 and
January 11, 2007, 3 p.m. SZTAKI L410

Schedule, place:

Tuesday 8:30-10:00, T.63
Wednesday 10:15-11:45, T.64

Remarks:

T.M. Cover and J.A. Thomas, ``Elements of Information Theory'', John Wiley & Sons, Inc., New York, 1991.
L. Györfi, S. Gyõri, and I. Vajda, ``Információ- és kódelmélet'' (Information and Code Theory), 2^nd ed., TypoTEX Kiadó, 2002 (textbook in Hungarian).
T. Linder and G. Lugosi, ``Bevezetés az informacióelméletbe'' (Introduction to Information Theory), Technical University of Budapest, 1990 (course notes in Hungarian).

Here is a brief summary of probabilty theory based on the Appendix of the textbook

L. Devroye, L. Györfi, and G. Lugosi, ``A Probabilistic Theory of Pattern Recognition'', Springer-Verlag, New York, 1996. It is edited by me to handle only discrete random variables and joint distributions of finitely many of them.

Entropy:: entropy, joint entropy, conditional entropy, mutual information, conditional mutual information, relative entropy, conditional relative entropy, chain rules, Jensen inequality, logsum inequality, data processing inequality, Fano's inequality.
Data Compression:: source codes, Kraft inequality, McMillan, connection with entropy - lower bound for L, Shannon codes - upper bound for L, Huffman codes, optimality, competitive optimality of Shannon code.
Entropy Rates of a Stochastic Process:: Markov chains, entropy rate.
Channel Capacity:: noiseless binary channel, noisy channel with no overlap, noisy typewriter, binary symmetric channel, binary erasure channel, the channel coding model, channel coding theorem, .