Logo UAB
2022/2023

Information Theory

Code: 104405 ECTS Credits: 3
Degree Type Year Semester
2503740 Computational Mathematics and Data Analytics OB 3 1

Contact

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

Use of Languages

Principal working language:
catalan (cat)
Some groups entirely in English:
No
Some groups entirely in Catalan:
Yes
Some groups entirely in Spanish:
No

Teachers

Joan Serra Sagristà

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.

Competences

  • Demonstrate a high capacity for abstraction and translation of phenomena and behaviors to mathematical formulations.
  • Formulate hypotheses and think up strategies to confirm or refute them.
  • Relate new mathematical objects with other known objects and deduce their properties.

Learning Outcomes

  1. "Explain ideas and mathematical concepts pertinent to the course; additionally, communicate personal reasonings to third parties."
  2. Contrast, if possible, the use of calculation with the use of abstraction in solving a problem.
  3. Develop autonomous strategies for solving problems such as identifying the ambit of problems within the course, discriminate routine from non-routine problems, design an a priori strategy to solve a problem, evaluate this strategy.
  4. Evaluate the advantages and disadvantages of using calculation and abstraction.
  5. Read and understand a mathematical text at the current level of the course.
  6. Understand the basic results and the fundamental properties of entropy and mutual information.
  7. Understand the concepts of entropy and data compression, mutual information and capacity and their application to the transmission of data.

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.

 

Methodology

Theoretical content will be taught through lectures, although students will be encouraged to actively participate in the resolution of examples, etc. Some of the theoretical classes may be given through videos given in 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.

Activities

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

Assessment

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 the course as a result of the individual tests will have the option of taking the final exam to recover all the subject of the course. It is necessary to obtain at least 2.4 out of 6 points to pass the course.

The following activities cannot be recovered:

  • Exercise resolution.
  • Presentation of activity.

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 procedure will 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 grade of "not evaluable" will be given to those who do not participate in any of the evaluation activities, and the numerical grade of the transcript will be the lower value between 3.0 and the weighted average of the grades in case of irregularities in an evaluation activity (and, therefore, it will not be possible to pass by compensation). 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 student in a different schedule than the one established 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

Assessment Activities

Title Weighting Hours ECTS Learning Outcomes
Deliverable of activities 1.5 1.5 0.06 4, 2, 3, 1, 5
Exercises resolution 2.5 1.5 0.06 2, 7, 6, 3, 5
Final test 6 3 0.12 4, 2, 7, 6, 3, 1, 5
Individual tests 6 6 0.24 4, 2, 7, 6, 3, 1, 5

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, Excel, Python and other software are suitable for carrying out the activities.