Information, broadcasting and protection of error codes
Basic contents of algebra, geometry and mathematical analysis.
The exam consists of a written test that is structured as follows:
- 3 or 4 exercises on theory in probability theory
- 2 or 3 questions of theory, including 1 or 2 on theory of probability (certainly a theorem with proof) and one on information theory.
The written test is passed obtaining a score greater than or equal to 18 out of 30 and it is followed by an optional oral test.
1) Knowledge and understanding skills
The course allows students to gain a solid grounding in aspects of probability theory and discrete probabilistic models, as well as the principles of the Shannon’s Information Theory (information, entropy, information compression, transmission without loss of information), and its connections with the theory of error-protection codes. At the end of the course the students will be able to expose, link and compare the main concepts and results presented in the course, to demonstrate the fundamental theorems of the examination program. Moreover, the students will have to know how to solve problems by combining theoretical knowledge with the recognition, selection or construction of models, following the example provided by the exercises.
2) Knowledge and understanding skills applied
The exercises of this course aim to acquire the ability to formulate simple models and to tackle problems of medium difficulty in conditions of uncertainty. The students will be able to apply the basics of Shannon's abstract information theory in various concrete situations.
3) Autonomy of judgment
An important part of the course aims to favor the development of logical skills. Many stochastic problems admit differentiated solutions, then many proposed exercises aim to recognize the correct proofs and to distinguish the wrong or incomplete reasoning. Topics like independence and conditional independence are particularly suitable for this purpose. The theory of probability is widely used for the development of mathematical models. Moreover, many proposed exercises require the development of modeling skills.
4) Communication skills
In order to acquire the new concepts of this course, the students must correctly explain, formalize the intuitions and be able to express them in oral and written form.
5) Learning skills
The course introduces some basic elements that will be useful to continue their studies in Computer Science. The acquisition of the basic language of Theory of Probability will also make possible further investigations, self-organized by the student, to address work-related needs.
Introduction to the theory of probability and combinatorial calculation (26 ore): Sample spaces, events, probability functions, conditional probabilities, independence between events. Examples. Discrete random variables, discrete density functions. Bernoulli’s variables. Binomial variables. Geometric variables. Hypergeometric variables. Multi-dimensional variables, multinomial law. Expected value and variance of a random variable. Chebychev inequality. Joint, conditional, marginal distributions. Expected values and variances of functions of random variables. Law of large numbers (weak).
Introduction to information theory and code theory (8 ore):
Uncertainty and information associated with events, additivity. Discrete memoryless source, entropy and properties. Source coding: uniquely decodable and non-instantaneous codes. Inequalities of Kraft and McMillan. Entropy and average length of a code, noiseless coding, compact coding (Huffman). Optimal codes and Absolutely optimal codes. Shannon's first theorem. Decoding and probability of error. Minimum Hamming distance. Error protection codes: coding and decoding. Block codes. Repetition codes. Parity check codes. Hamming codes.
Exercises on the topics of probability theory (18 ore)
Textbooks:
• Paolo Baldi, Calcolo delle probabilità, Mc Graw-Hill (capp. 1 e 2);
• Norman Abramson, Information theory and coding, Mc Graw-Hill (capp.1-6);
• E. Angeleri, Informazione: Significato e universalità, Utet 2000 (Sez. 6.3).
Lecture notes are provided on the e-learning website.
Lectures and exercises that consist in performing exercises that apply the developed theoretical contents.