Information Theory

Credits
6
Types
Compulsory
Requirements
This subject has not requirements, but it has got previous capacities
Department
MAT;TSC;FIS
In 1948 engineer and mathematician Claude E. Shannon published “A mathematical theory of communication” in Bell Systems Technical Journal. In this foundational paper he gave birth to Information Theory, an entirely new field, by introducing the concepts of information entropy and redundancy, and the theorems of source and channel coding. Information Theory provides a theoretical model for signal processing and communication and has been at the heart of the digital revolution experimented in the last decades, because it provides tools for achieving efficiency (data compression), reliability (error detection and correction codes) and security (cryptography) particularly suited for processing, storage and transmission of digital data.
The course has two main objectives: (1) give the students a rigorous introduction to the main points of Information Theory, including proofs of the two fundamental theorems of noiseless-source coding and noisy-channel coding; (2) present several applications, including data compression and error correction codes, but also some others as inference or cryptography.

Teachers

Person in charge

  • Josep Vidal Manzano ( )

Others

  • Adrián Francisco Tauste Campo ( )

Weekly hours

Theory
2
Problems
2
Laboratory
0
Guided learning
0
Autonomous learning
6

Competences

Technical Competences

Technical competencies

  • CE1 - Skillfully use mathematical concepts and methods that underlie the problems of science and data engineering.
  • CE3 - Analyze complex phenomena through probability and statistics, and propose models of these types in specific situations. Formulate and solve mathematical optimization problems.
  • CE7 - Demonstrate knowledge and ability to apply the necessary tools for the storage, processing and access to data.
  • CE8 - Ability to choose and employ techniques of statistical modeling and data analysis, evaluating the quality of the models, validating and interpreting them.

Transversal Competences

Transversals

  • CT5 [Avaluable] - Solvent use of information resources. Manage the acquisition, structuring, analysis and visualization of data and information in the field of specialty and critically evaluate the results of such management.
  • CT6 - Autonomous Learning. Detect deficiencies in one's own knowledge and overcome them through critical reflection and the choice of the best action to extend this knowledge.
  • CT7 - Third language. Know a third language, preferably English, with an adequate oral and written level and in line with the needs of graduates.

Basic

  • CB1 - That students have demonstrated to possess and understand knowledge in an area of ??study that starts from the base of general secondary education, and is usually found at a level that, although supported by advanced textbooks, also includes some aspects that imply Knowledge from the vanguard of their field of study.
  • CB2 - That the students know how to apply their knowledge to their work or vocation in a professional way and possess the skills that are usually demonstrated through the elaboration and defense of arguments and problem solving within their area of ??study.
  • CB4 - That the students can transmit information, ideas, problems and solutions to a specialized and non-specialized public.
  • CB5 - That the students have developed those learning skills necessary to undertake later studies with a high degree of autonomy

Generic Technical Competences

Generic

  • CG5 - To be able to draw on fundamental knowledge and sound work methodologies acquired during the studies to adapt to the new technological scenarios of the future.

Objectives

  1. To acquire the knowledge necessary to understand the basic principles of treatment, compression, cryptography and analysis of data based on Shannon's theory.
    Related competences: CB1, CB2, CB4, CB5, CT5, CT6, CT7, CE1, CE3, CE7, CE8, CG5,

Contents

  1. Discrete random variables and processes
    Probability, ensembles of random variables, stochastic processes, Márkov processes
  2. Measures of information
    Information theory, entropy, joint entropy and mutual information, data processing inequality, Fano's inequality, applications
  3. Information of data sources
    Codes, asymptotic equipartition property, data compression, the high probability set, non-independent sources
  4. Source coding
    Properties of codes, unique decodability, mínimum average length, Huffman codes, dictionary codes
  5. Capacity of discrete channels
    Joint typical sequences, channel capacity theorem, separability of source and channel coding.
  6. Channel codes
    Introduction to error correction codes, block codes
  7. Cryptography
    Shannon theory of secrecy systems; main theorem; one-time pad; symmetric cryptography in practice

Activities

Activity Evaluation act


Development of lecture "Discrete random variables and processes"


Objectives: 1
Contents:
Theory
2h
Problems
2h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Development of lecture "Measures of information"


Objectives: 1
Contents:
Theory
5h
Problems
5h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Development of lecture "Information of data sources"


Objectives: 1
Contents:
Theory
5h
Problems
5h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Development of lecture "Source coding"


Objectives: 1
Contents:
Theory
6h
Problems
6h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h

Development of lecture "Capacity of discrete channels"


Objectives: 1
Contents:
Theory
3h
Problems
4h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Development of lecture "Channel codes"


Objectives: 1
Contents:
Theory
6h
Problems
9h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Development of lecture "Cryptography"


Objectives: 1
Contents:
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Teaching methodology

50% of lectures in which the participation of students is stimulated, followed by 50% of practical classes based on exercises and programming of algorithms with the aim of bringing information theory to practical applications related to data science engineering.

Evaluation methodology

There will be a mid-term test of two hours duration at the 8th week and a final exam. The grade is calculated as the maximum of (final exam grade, 0.6 * final exam grade + 0.4 * mid-term exam grade).
The re-evaluation exam, for fails who have attended lectures and final exam, will consist of one exam to be held in July and that will be considered at 100% for the final grading.

Bibliography

Basic:

Previous capacities

Fundamentals of probability, statistics and stochastic processes