BSc:InformationTheory

From IU
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Information Theory

  • Course name: Information Theory
  • Course number: N/A

Course Characteristics

Key concepts of the class

  • Information coding
  • Information transmission

What is the purpose of this course?

This course provides a basic introduction to the Information Theory and its applications to digital systems. In particular, it focuses on the theoretical and practical aspects that are connected to the data compression and transmission highlighting the different problems and approaches to overcome the limitations. Moreover, a short introduction about the mathematical requirements will focuses on the probability and basic statistical concepts that will be used throughout the course.

Course objectives based on Bloom’s taxonomy

- What should a student remember at the end of the course?

  • Information definitions.
  • Entropy definitions.
  • Encoding techniques.
  • Transmission techniques.
  • Compression techniques.

- What should a student be able to understand at the end of the course?

  • How random variables and signals are connected.
  • The concept of information and how it is connected to entropy.
  • The different types of transmission channels.
  • How encoding works.
  • How compression works.

- What should a student be able to apply at the end of the course?

  • Implement a compression algorithm.
  • Select the most suitable channel for transmission.
  • Identify and correct errors in data exchanges.

Course evaluation

Course grade breakdown
Proposed points
Labs/seminar classes 20
Interim performance assessment 30
Exams 50

If necessary, please indicate freely your course’s features in terms of students’ performance assessment.

Grades range

Course grading range
Proposed range
A. Excellent 90-100
B. Good 75-89
C. Satisfactory 60-74
D. Poor 0-59

If necessary, please indicate freely your course’s grading features.

Resources and reference material

Course Sections

The main sections of the course and approximate hour distribution between them is as follows:

Course Sections
Section Section Title Teaching Hours
1 Introduction 2
2 Probability and Information 4
3 Information and Entropy 4
4 Encoding 6
5 Channels 6
6 Compression 6
7 Errors 2

Section 1

Section title:

Introduction

Topics covered in this section:

  • Definition of information
  • Communication systems
  • Uncertainty
  • Shannon paper

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 0
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 0


Typical questions for ongoing performance evaluation within this section

  1. Describe the components of a communication system
  2. How is it possible to measure information?
  3. Definition of uncertainty
  4. What is information?

Typical questions for seminar classes (labs) within this section

  1. Design the structure of a communication system
  2. Possible ways to measure the information of a message
  3. Make an example on how information and uncertainty is related
  4. Analyze the Shannon’s paper

Test questions for final assessment in this section

  1. Shennon’s definition of information
  2. Definition of uncertainty and its relation with information.
  3. Describe the different ways of measuring information

Section 2

Section title:

Probability and Information

Topics covered in this section:

  • Discrete probability
  • Random variables
  • Bayes’ theorem
  • Naive Bayesian Classifier

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 0
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 0


Typical questions for ongoing performance evaluation within this section

  1. Define simple, joint, marginal, and conditional probability
  2. Define an ergodic process
  3. Describe the implications of the Bayes’ theorem
  4. What is a classifier?

Typical questions for seminar classes (labs) within this section

  1. Draw the possibility tree for a certain set of events
  2. Given a process, check if it is ergodic
  3. Write the code for the implementation of a Naive Bayesian Classifier
  4. Write the code to test the ergodicity of a process

Test questions for final assessment in this section

  1. Describe the relationships among the different kinds of probabilities.
  2. Compare the characteristics of different distributions and how they relate to real problems.
  3. Make examples of the application of the Bayes’ theorem in real-life problems.

Section 3

Section title:

Information and Entropy

Topics covered in this section:

  • Entropy
  • Relative entropy
  • Mutual information
  • Jensen’s inequality
  • Gibbs’ inequality

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 0
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 0


Typical questions for ongoing performance evaluation within this section

  1. Describe the entropy properties
  2. Define joint and conditional entropy
  3. Describe the Jensen’s inequality
  4. Describe the Gibbs’ inequality

Typical questions for seminar classes (labs) within this section

  1. Calculate the entropy in different conditions
  2. Calculate relative entropy in different conditions
  3. Calculate mutual information in different conditions
  4. Applications of convex functions

Test questions for final assessment in this section

  1. Calculate the entropy of a message.
  2. Describe the relationship between relative entropy and mutual information.
  3. Compare the entropy of the same message sent using different encodings.

Section 4

Section title:

Encoding

Topics covered in this section:

  • Source coding theorem
  • Huffman coding
  • Arithmetic coding

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 0


Typical questions for ongoing performance evaluation within this section

  1. Describe the source coding theorem
  2. Describe Huffman coding
  3. Describe arithmetic coding
  4. Compare different coding techniques

Typical questions for seminar classes (labs) within this section

  1. Write a piece of code that implement the Huffman encoding
  2. Write a piece of code that implement the arithmetic encoding
  3. Write a piece of code that implement the Huffman decoding
  4. Write a piece of code that implement the arithmetic decoding

Test questions for final assessment in this section

  1. How the performances of the Huffman coding change based on the changes of the size of the dictionary.
  2. Describe advantages and disadvantages of coding techniques based on dictionaries.
  3. Describe advantages and disadvantages of coding techniques not based on dictionaries

Section 5

Section title:

Channels

Topics covered in this section:

  • Types and characteristics of channels
  • Noise
  • Capacity
  • Schedules

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 0
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 0


Typical questions for ongoing performance evaluation within this section

  1. Compare different channel types.
  2. How is it possible to communicate over a noisy channel?
  3. Make examples of different channel types.
  4. What is the capacity of a channel?

Typical questions for seminar classes (labs) within this section

  1. Calculate the capacity of a channel.
  2. How the capacity changes based on the type of channel?
  3. Send the same message through different channel types with no noise. Which are the differences?
  4. Send the same message through different channel types with noise. Which are the differences?

Test questions for final assessment in this section

  1. What is the effect of the noise in the different channel types?
  2. What is the relation between codes and channels?
  3. Calculate the entropy of a message before and after a channel.

Section 6

Section title:

Compression

Topics covered in this section:

  • Lempel-Ziv coding
  • Block codes
  • Lossy compression

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 0


Typical questions for ongoing performance evaluation within this section

  1. Differences between stream and block coding algorithms
  2. Principles of lossy compression
  3. Describe Lempel-Ziv coding
  4. Examples of block codes

Typical questions for seminar classes (labs) within this section

  1. Write a piece of code that implement the Lempel-Ziv coding
  2. Write a piece of code that implement a lossy compression algorithm
  3. Write a piece of code for a block code
  4. Write a piece of code for a stream code

Test questions for final assessment in this section

  1. Compare Huffman coding and Lempel-Ziv coding
  2. Analyse the different versions of the Lempel-Ziv coding
  3. Given a message, calculate the Huffman code.

Section 7

Section title:

Errors

Topics covered in this section:

  • Error detection techniques
  • Error correction techniques
  • Hamming code

What forms of evaluation were used to test students’ performance in this section?

|a|c| & Yes/No
Development of individual parts of software product code & 1
Homework and group projects & 0
Midterm evaluation & 1
Testing (written or computer based) & 0
Reports & 0
Essays & 0
Oral polls & 0
Discussions & 0


Typical questions for ongoing performance evaluation within this section

  1. Describe the error detection techniques
  2. Describe the error correction techniques
  3. Describe the Hamming code
  4. Describe the parity detection techniques

Typical questions for seminar classes (labs) within this section

  1. Write a piece of code that implements the Hamming code
  2. Calculate the Hamming code of a data sequence
  3. Given a message extract the Hamming code
  4. Given a message check its correctness using the Hamming code

Test questions for final assessment in this section

  1. Compare the requirements for the detection and correction of errors using the Hamming code
  2. Compare the requirements for detecting and correcting errors
  3. Given a message with an error and using the Hamming code, calculate the correct message