This version of the course guide is provisional until the period for editing the new course guides ends.

Logo UAB

Information Theory

Code: 104405 ECTS Credits: 3
2024/2025
Degree Type Year
2503740 Computational Mathematics and Data Analytics OB 3

Contact

Name:
Adrià Figuerola Torrell
Email:
adria.figuerola@uab.cat

Teachers

Joan Serra Sagrista

Teaching groups languages

You can view this information at the end of this document.


Prerequisites

There are no prerequisites. However, it is recommended for students to have notions of linear algebra and probabilities.


Objectives and Contextualisation

To study the mathematica theory of information, in the discrete case, based on the publications by C.E. Shannon on 1948. To study different data source, the source codification, the data compression and the codificationsof the channel, with the aim of obtaining an efficient data transmission an storage.


Learning Outcomes

  1. CM21 (Competence) Select the suitable data compression in each case to preserve the desired properties.
  2. KM19 (Knowledge) Identify the concepts of entropy and data compression, mutual information and capacity and their application to data transmission.
  3. KM19 (Knowledge) Identify the concepts of entropy and data compression, mutual information and capacity and their application to data transmission.
  4. KM19 (Knowledge) Identify the concepts of entropy and data compression, mutual information and capacity and their application to data transmission.

Content

  1. Basic concepts of information theory

    1. Information measurement.

    2. Shannon’s memoryless discrete source.

    3. Entropy of a discrete random variable.

    4. Mutual information between two discrete random variables. Channel capacity.

  2. Channel coding

    1. Important models of memoryless discrete channels.

    2. Decoding rules.

  3. Source coding

    1. Fixed and variable length codes, uniquely decodable codes, and instant codes.

    2. Shannon's first theorem. Existence of optimal codes.

    3. Construction of optimal codes: Huffman method.

  4. Data compression

    1. Types of compression.

    2. Statistical methods and dictionary techniques.

 


Activities and Methodology

Title Hours ECTS Learning Outcomes
Type: Directed      
Seminars 12 0.48
Theorical classes / lectures 13 0.52
Type: Supervised      
Tutoring and consultations 6 0.24
Type: Autonomous      
Preparing exercises 16 0.64
Preparing tests and independent study 16 0.64

Theoretical content will be taught through lectures, although students will be encouraged to actively participate in the resolution of examples, etc. These classes will be in face-to-face format, although it is also possible to provide videos posted on the CV. During problem sessions, a list of exercises will be resolved. Students are encouraged to solve the problems on their own in advance. Students will also be encouraged to present their own solutions in class.Campus Virtual will be used for communication between lecturers and students (material, updates, announcements, etc.).

 

 

Annotation: Within the schedule set by the centre or degree programme, 15 minutes of one class will be reserved for students to evaluate their lecturers and their courses or modules through questionnaires.


Assessment

Continous Assessment Activities

Title Weighting Hours ECTS Learning Outcomes
Deliverable of activities 1.5 1.5 0.06 CM21, KM19
Exercises resolution 2.5 1.5 0.06 CM21, KM19
Final test 6 3 0.12 CM21, KM19
Individual tests 6 6 0.24 CM21, KM19

Continuous-assessment dates will be published on Campus Virtual and on the presentation slides, specific programming may change when necessary. Any such modification will always be communicated to students through Campus Virtual, which is the usual communication platform between lecturers and students.

The evaluation of the course, out of 10 points, will be made as follows:

  • Two individual partial tests, 3 points each. As part of the continuous evaluation, the first test will be given during the week of intersemesteral exams agreed by the coordination. The second partial test will be taken on the last day of the course. It is necessary to obtain at least 1.2 out of 3 points in each of the individual tests in order to pass the course.
  • Deliverable of activities, 1.5 point. An activity related to some topics of the course must be submitted.
  • Exercise resolution, 2.5 points. As part of the continuous evaluation, activities will have to be done or exercises will have to be solved via online questionnaires. In some cases, some other evaluation activity could be programmed and will be made known to the students through the Virtual Campus.
  • Final exam, 6 points. Those who have not passed any of the individual tests will have the option to take the final exam to make up for the partial exams of the course they did not pass. It is necessary to obtain at least 2.4 out of 6 points in each partial exam in order to pass the course.

The following activities cannot be recovered:

  • Exercise resolution.
  • Delivery activities.

Without prejudice to other disciplinary measures deemed appropriate, and in accordance with current academic regulations, the evaluation activities (practices, problems or exams) with irregularities committed by a student that may lead to a variation of the grade will be graded in full of a zero (0). The evaluation activities qualified in this way and by this procedurewill not be recoverable. If it is necessary to pass any of these evaluation activities to pass the course, it will be directly suspended, without the opportunity to recover it in the same course. These irregularities include, among others

  • total or partial copying of a practice, report, or any other evaluation activity;
  • allowing the student to copy;
  • submitting group work not done entirely by the members of the group;
  • presenting as one's own materials elaborated by a third party, even if they are translations or adaptations, and in general works with elements that are not original and exclusive to the student;
  • having communication devices (such as cell phones, *smart *watches, etc.) accessible during individual evaluation tests (exams).

To pass, it is necessary that the evaluation of each of the parts exceeds the minimum required and that the total evaluation exceeds 5 points. In case of not passing the course because any of the evaluation activities does not reach the minimum required grade, the numerical grade of the file will be the lower value between 4.5 and the weighted average of the grades. The designation 'not assessable' will be assigned to students who have not participated in any assessment activity. In the event that a student has committed an irregularity during one of the assessments, their final mark will be limited to the lowest value between 3.0 or the average calculated from their marks. This means that passing by grade compensation will not be an available option. In order to obtain a *MH the final grade must be equal to or higher than 9 points. Since the number of *MH cannot exceed 5% of the number of students enrolled, they will be awarded to whoever has the highest final grades. In case of a tie, the results of the midterm exams will be taken into account.
Partial tests will be taken into account. It is important to note that no evaluation activity will be done to any studentin a different schedule than the oneestablished if there is no justified cause,priornotice has been given in the activity and the faculty has given its consent. In any other case, if the student has not attended an activity, it cannot be made up. In the case of online evaluations of questionnaires, a review may be requested after the closing date of the questionnaire. For the rest of the evaluation activities, a place, date and time of review will be indicated in which the student can review the activity with the teacher. In this context, claims on the grade of the activity may be made, which will be evaluated by the faculty responsible for the subject. If the student does not show up for this review, the activity will not be reviewed afterwards.


You can consult the UAB academic regulations approved by the UAB Governing Council: http://webs2002.uab.es/afers_academics/info_ac/0041.htm


Bibliography

Basic bibliography

  • L. Huguet i J. Rifà. Comunicación Digital. Ed. Masson, 1991.
  • D. Salomon: Data compression - The Complete Reference, 4th Edition. Springer 2007.
  • R.B. Ash. Information Theory. John Wiley and Sons Inc, 1965.
  • G. Alvarez. Teoría matemática de la información. Ediciones ICE, 1981.
  • T.C. Bell, J.G. Cleary i I.H. Witten. Text Compression. Prentice Hall, 1990.

Complementary bibliography

  • C.E. Shannon, "A mathematical theory of communications," Bell Syst. Tech. J., 27, 379-423, 1948.
  • B. McMillan, "The basic theorems of Information Theory," Ann. Math. Stat., 24, 196-219, 1953.
  • A.I. Khinchin. Mathematical foundations of Information Theory. Dover Publications, Inc., 1957.
  • R. W. Hamming. Coding and Information Theory. Prentice Hall, Inc., 1980.
  • M. Mansuripur. Introduction to Information Theory. Prentice Hall, Inc., 1987.
  • G.J. Chaitin. Algorithmic Information Theory. Cambridge University Press., 1987.
  • V. Shoup. A computational Introduction to number theory and Algebra. http://shoup.net/ntb/

Software

MATLAB, Python and other software are suitable for carrying out the activities.


Language list

Name Group Language Semester Turn
(SEM) Seminars 1 Catalan first semester morning-mixed
(TE) Theory 1 Catalan first semester morning-mixed