Information Theory

Recommended Prerequisites

Mathematical Analysis I, Statistics, Introduction to Programming and Problem Solving, Principles of Procedural Programming.

Teaching Methods

Theoretical classes with detailed presentation, using audiovisual means, of the concepts, principles and fundamental theories and solving of basic practical exercises to illustrate the practical interest of the subject and exemplify its application to real cases.

Theoretical-practical classes where the students, supervised by the staff member, solve practical exercises, which require the combination of different theoretical concepts and promote critical reasoning in the presence of more complex problems.

Practical classes are devoted to programming exercises involving the main concepts tough throughout the course. Namely, three practical programming assignments are given to be solved throughout the lecture period of the course. During the theoretical classes, students are requested to solve mini-tests and receive homework assignments to be evaluated. Evaluation includes also a final exam.

Learning Outcomes

To provide the students with the main concepts and foundations of information theory and its applications in computational learning, source and channel coding and cryptography. The goal is to expose the algebraic foundations in order to enable the student to learn the abstract concepts of information theory and the sophisticated mathematics of coding.

The course will contribute to the acquisition of the following competences:

Instrumental:

• Analysis and synthesis of complex problems;
• Mathematical Reasoning;
• Abstraction and generalization;
• Problem solving, namely in the area of computational learning, data compression channel coding and cryptography.

Personal:

• Team work;
• Critical reasoning.

Systematic:

• Self-learning

• Research.

Work Placement(s)

No

Syllabus

1.Foundations:
 Applications; Information: intuition, concept and properties; Entropy, uncertainty and dispersion; Joint and conditional Entropy; Kullback-Leibler divergence; Mutual Information; Chain rules; maximal entropy principle.
2.Entropy and Compression:
Source coding theo.; Codes and properties; Kraft and McMillan theor.; Optimal codes; Shannon-Fano-Elias codes; Huffman codes; Arithmetic codes; Dictionary codes.
3.Cryptography
Domains and type of alg.; Classical algo.s; random sequences; Perfect and Imperfect encryption; Distribution of keys; Symmetrical key alg.- RSA, Euler theo., security limits, Euclid’s Algo.s, Fermat’s theorem, Chinese remainder theo.); Symmetrical key algo.s.; Hashing functions.
4. Error Control Coding
Channel coding theo.; Type of channels and codes; Linear codes, Hamming codes; cyclic codes.

Head Lecturer(s)

Rui Pedro Pinto de Carvalho e Paiva

Assessment Methods

Continuous evaluation
During the theoretical classes, students are requested to solve mini-tests and receive homework assignments to be evaluated: 100.0%

Final evaluation
Exam: 100.0%

Bibliography

K. Sayood, Introduction to data compression: second edition, Morgan Kaufman, 2000. (selected chapters)
J. C. MacKay (2003) Information Theory, Inference and Learning Algorithms, University of Cambridge, (http://www.inference.phy.cam.ac.uk/mackay/itila/book.html)(selected chapters)
W. Trappe, L. Washington, Introduction to Cryptography with Coding Theory, Prentice Hall, 2nd Edition (selected chapters)
Shu Lin, Daniel J. Costello (2004) Error Control Coding, Second Edition, Prentice Hall; 2nd Edition (selected chapters)
Carvalho, P. (2011) – Slides de Teoria de Informação, DEI-FCTUC.

Complementar/Complementary:
T. Cover, J. Thomas (1991) Elements of Information Theory, John Wiley&Sons