Information theory

Information

Aim and objective

Introduction to the field of information theory and its applications to the communication theory. Presentation of the basic quantities for entropy and mutual information. Presentation of the basic algorithms for source coding, channel coding and cryptography.

Outcome learning

• INSA reference data :
  • CNISF reference data :
    • T40D [2I]
  1 - Notion, 2 - Concept, 3 - Application, I - fully, P - incomplete

  Course description

  Mathematical tools :

  • Probabilities, entropy and mutual information,
  • Entropy rate of stochastic processes,
  • Rate distortion theory,
  • Markov models.

  Source coding :

  • Kraft inequality, optimal codes, bounds on the optimal codelenght,
  • Data compression without distortion : Shanon-Fano, Huffman, Run-lenght coding, Lempel- Ziv, arithmetic algorithms,
  • Data compression algorithms with distortion : scalar quantification, vectorial quantification, linear prediction,
  • Audio coding (MP3, AAC), image coding (JPEG) and video coding (MPEG).

  Chanel coding :

  • Channel capacity,
  • Error detection and/or correction algorithms,
  • Hamming codes,
  • Binary cyclic codes and BCH codes
  • Binary convolutional codes
  • Combining codes

  Cryptography

  Prerequisites

  Signal processing, Matlab/Octave programming and probabilities.

  Bibliography

  • [Th. Cover et J. Thomas, 1991] "Elements of Information Theory", Wiley Series in Telecommunications ed., 1991, 542 pages
  • [R. Morelos-Zaragoza, 2002] "The art of error correcting coding", Wiley Series, 221 pages.

  Assessment

  • Final exam (60%) : Written exam (3h)
  • Oral exam (40%) : Project presentation