Information theory - 3AMMA331

Goal(s)

At the end of the course, the student should be knowledgeable in the fundamentals of information theory, source coding (data compression) and channel coding (error detection and correction), in order to be able later to grasp the more recent techniques in the field.

Content(s)

• Information theory
  • Information measure
  • Sources, stateful and stateless sources, Markov sources, source extention, source rate
  • Entropy, mutual entropy, conditional entropy
  • Communication canals, transition matrices
  • Lossless canals, deterministic, noiseless, binary, symetric
  • Mutual information, canal capacity
  • White noise additive canals, capacity
  • Second Shannon theorem - canal coding

• Introduction to source coding
  • Kraft inequality, Mac-Millan theorem
  • Mean length, efficiency and redundancy of a source code
  • First Shannon theorem
  • Shannon-Fano and Huffman codes
  • Lempel-Ziv codes
• Linear block codes
  • Generation matrix, control matrix
  • Hamming distance and weight
  • Repetition code, parity code, Hamming code, extended Hamming code
  • Syndrom, decoding
• Cyclical codes
  • Polynomial representation
  • Generating polynomial, control polynomial, generating matrix
  • Coder and decoder principlse, Meggit decoder
  • Code examples: BCH code, Golay code, Reed-Salomon code

Basic mathematics. Combinatorics. Probability theory. Signal processing.