Logo UAB
2021/2022

Information Theory

Code: 104405 ECTS Credits: 3
Degree Type Year Semester
2503740 Computational Mathematics and Data Analytics OB 3 1
The proposed teaching and assessment methodology that appear in the guide may be subject to changes as a result of the restrictions to face-to-face class attendance imposed by the health authorities.

Contact

Name:
Cristina Fernández Córdoba
Email:
Cristina.Fernandez@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à
Joan Bartrina Rapesta

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 (4 hours)

    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 hour)

    1. Important models of memoryless discrete channels.

    2. Decoding rules.

  3. Source coding (3 hours)

    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 (4 hours)

    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.

During laboratory sessions, topics related to the lectures will be studied in depth. These include the presentation of real cases, or the extension of certain subjects with techniques and algoriths alternative to those already seen. 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      
Assessment exams and activities 12 0.48 4, 2, 7, 6, 3, 1, 5
Lab Classes 6 0.24 4, 2, 7, 6, 3
Seminars 7 0.28 4, 2, 7, 6, 3, 1, 5
Theorical classes / lectures 12 0.48 4, 2, 7, 6, 5
Type: Supervised      
Tutoring and consultations 6 0.24 4, 2, 7, 6, 5
Type: Autonomous      
Preparing exercises and practical assigments 10 0.4 3, 5
Preparing tests and independent study 10 0.4 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.

Subject assessment (out of 10 points) will be carried out as follows:

  • Individual tests, 4 points. The individual test will take place on the date specified by coordination, and will be given on finishing all the chapters of the course. At least 1.6 out of 4 points must be obtained in order to pass the subject.
  • Activity presentations, 1 point. Some activity related to some topic given in the course should be presented.
  • Exercises resolution, 1.5 points. Activities must be carried out or exercises must be solved via online quizzes. In some cases, another assessment activity could be programmed and will be informed to the students through the Campus Virtual.
  • Mandatory laboratory practices, 2.5 points. As part of continuous assessment, certain laboratory assignments must be fulfilled. At least 1 point (out of 2.5 points) must be obtained to pass the subject.
  • Final exam, 4 points. Those who have not passed the subject through the individual test will have the option to take final exam as a re-assessment grade to compensate it.This exam covers material from the entire course. At least 1.6 (out of 4) points must be obtained in order to pass the subject.
  • Practice recovery, 2.5 points: Those who have not passed the mandatory laboratory practice evaluation will have the option to deliver a new version and must obtain at least 1 (out of 2.5) to pass the subject. Moreover, there will be an oral exam concerning this part of the subject.

Notwithstanding otherdisciplinary measures deemed appropriate, and in accordance with the academic regulations in force, assessment activities (laboratory practices, exercises ressolutions or exams) will receive a zero score whenever a student commits academic irregularities that may alter such assessment. Assessment activitiesgraded in this way and by this procedure will not be re-assessable. If passing the assessment activity or activities in question is required to pass the subject, the awarding of a zero for disciplinary measures will also entail a direct fail for the subject, with no opportunity to re-assess this in the same academic year. Irregularities contemplated in this procedure include, among others:

  • the total or partial copying of a practical exercise, report, or any other evaluation activity;
  • allowing others to copy;
  • presenting group work that has not been done entirely by the members of the group;
  • presenting any materials prepared by a third party as one’s own work, even if these materials are translations or adaptations, including work that is not original or exclusively that of the student;

To pass the course it is necessary that the markof each one of the parts exceeds the minimum required and that the overall grade is 5.0 or higher. If you do not pass the subject because some of the assessment activities do not reach the minimum mark required, the mark in the Transcript of Records (ToR) will be the lowest value between 4.5 and the average weighted notes. With the exceptions that the "non-assessable" grade will be assigned to those students who do not participate in any of the assessment activities, and that the mark in the ToR will be the lowest value between 3.0 and the weighted average of the marks, in the event of irregularities have been committed for any assessmentactivity(andtherefore re-assessmentwill not be possible). In order to pass the course with honors, the final grade must be a9.0 o higher. Because the number of students with thisdistinction cannot exceed 5% of the numberof students enrolled in the course, this distinction will be awardedtowhoever has the highest final grade. In case of a tie, partial-test results will be taken into consideration.

It is important to bear in mind that no assessment activities will be permited forany student at a different date or time to that established, unless for justified causes duly advised before the activity and with the lecturer's previous consent. In all other cases, if an activity has not been carried out, this cannot be re-assessed.

In the case of on-line quizzes, a review may be requested after the date of closure of the quiz. For all other assessment activities, a place, date and time of review will be indicated allowing students to review the activity with the lecturer. In this context, students may discuss the activity grade awarded by the lecturers responsible for the subject. If students do not take part in thisreview, no further opportunity will be made available.

To consult the academic regulations approved by the Governing Council of the UAB, please follow this link: http://webs2002.uab.es/afers_academics/info_ac/0041.htm

Assessment Activities

Title Weighting Hours ECTS Learning Outcomes
Activity presentation 1 1.5 0.06 4, 2, 3, 1, 5
Exercises resolution 2.5 1.5 0.06 2, 7, 6, 3, 5
Final test 4 3 0.12 4, 2, 7, 6, 3, 1, 5
Individual test 4 3 0.12 4, 2, 7, 6, 3, 1, 5
Mandatory laboratory practices 2.5 1.5 0.06 4, 2, 7, 6
Practice recovery 2.5 1.5 0.06 4, 2, 7, 6

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

The software used for the development of the practice will be the Oracle Java SDK, Eclipse, Apache Ant, FIYI, and the software developed by the teaching staff of the subject. All software will be distributed free, allowing the student to work from home.