Information Transmission and Encoding

You are here

Credits
6
Types
Specialization complementary (Information Technologies)
Requirements
  • Prerequisite: FM
  • Prerequisite: M1
  • Prerequisite: M2
Department
MAT
An introduction to the concepts and algortihms of error correcting codes.

Teachers

Person in charge

  • Rafel Farré Cirera ( )

Weekly hours

Theory
3
Problems
0
Laboratory
1
Guided learning
0
Autonomous learning
6

Competences

Technical Competences of each Specialization

Information technology specialization

  • CTI1 - To define, plan and manage the installation of the ICT infrastructure of the organization.
    • CTI1.4 - To select, design, deploy, integrate, evaluate, build, manage, exploit and maintain the hardware, software and network technologies, according to the adequate cost and quality parameters.
  • CTI3 - To design solutions which integrate hardware, software and communication technologies (and capacity to develop specific solutions of systems software) for distributed systems and ubiquitous computation devices.
    • CTI3.3 - To design, establish and configure networks and services.

Transversal Competences

Information literacy

  • G6 [Avaluable] - To manage the acquisition, structuring, analysis and visualization of data and information of the field of the informatics engineering, and value in a critical way the results of this management.
    • G6.3 - To plan and use the necessary information for an academic essay (for example, the final project of the grade) using critical reflection about the used information resources. To manage information in a competent, independent and autonomous way. To evaluate the found information and identify its deficiencies.

Objectives

  1. To learn the concepts of information of an event and the entropy of a probability distribution. To learn the concepts of information source and communication channel. To learn the concepts of source coding (data compression) and channel coding (error-detection and error-correction) and Shannon's theorems.
    Related competences: G6.3,
  2. To learn the basic concepts of block codes: their parameters and their relationship to the error-detecting and error-correcting abilities. To learn the main applications of modular arithmetic to the construction of block codes. To learn the protocols of error-detection and error-correction used in communication networks.
    Related competences: G6.3, CTI1.4, CTI3.3,
  3. To learn the basic structure of finite fields, mainly those of characteristic 2. To learn the finite dimensional vector spaces over a finite field. To learn the ways of defining a linear code, determining its parameters and decoding using the algorithm based on syndromes. To learn the particularities of some specific linear codes (specially the perfect codes) and their corresponding error-correction algorithms.
    Related competences: G6.3,
  4. To learn the general structure of cyclic codes and Meggit"s algorithm. To learn CRC technique: cyclic codes used for detection purposes in communication networks. To learn the binary BCH codes and their error-correction algorithms. To learn Reed-Solomon codes and their application to compact disks.
    Related competences: CTI3.3, G6.3, CTI1.4,

Contents

  1. Information and entropy.
    Mathematical definition of the amount of information. Entropy of a probability distribution and mutual information of two random variables.
  2. Source coding and channel coding
    Variable-length codes. Kraft's inequality. Huffman's codes. Extensions of a source. First Shannon's theorem. Channel capacity . Decision schemes. Second Shannon's theorem: channel coding with noise. The binary symmetric channel. Decoding by maximum likelihood.
  3. Error-detection and error-correction with block codes.
    Hamming distance. Tangency radius and covering radius. Error-detecting and error-correcting. Error-detecting protocols. The fundamental problem of coding theory.
  4. Finite fields
    Construction of finite fields, specially those of characteristic 2. Elementary properties and efective computations in finite fields.
  5. Linear codes
    Vector spaces over finite fields. Linear codes. Generating and parity-check matrices. Standard array and syndrome correction. Operations with linear codes. Perfect codes. Hamming codes, binary Golay codes and ternary Golay codes.
  6. Cyclic codes and CRC
    Polynomials over finite fields. Polynimals codes. Generating and parity-check polynomials. Systematic encoding. Meggitt's correction algorithm. Cyclic codes used for detection purposes: CRC. Ethernet CRC.
  7. Binary BCH codes
    Roots of a cyclic code: description of a cyclic code by its roots. BCH codes over a finite field. Binary primitive and stric BCH codes. The key equation. Euclid's algorithm for decoding. Berlekamp-Massey decoding.
  8. Reed-Solomon codes
    Reed-solomon codes as cyclic codes. The finite Fourier transform. Algorithm for error-correction. Application: coding of the audio compact disc.

Activities

Activity Evaluation act


Information and entropy

Developing the subject "Information and entropy"
Objectives: 1
Contents:
Theory
3h
Problems
0h
Laboratory
1h
Guided learning
0h
Autonomous learning
5.5h

Developing the subject "Source coding and channel coding"

Developing the subject "Source coding and channel coding"
Objectives: 1
Contents:
Theory
3h
Problems
0h
Laboratory
1h
Guided learning
0h
Autonomous learning
14h

Partial exam

Partial exam on subjects 1, 2 and 3
Objectives: 1 2
Week: 6
Type: theory exam
Theory
2h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
7h

Developing the subject "Error-detection and error-correction with block codes".

Developing the subject "Error-detection and error-correction with block codes".
Objectives: 2
Contents:
Theory
4h
Problems
0h
Laboratory
1h
Guided learning
0h
Autonomous learning
4h

Solving problems 1

Troughout the course the student has to work on at least two problems.
Objectives: 1 2
Week: 8
Type: lab exam
Theory
0h
Problems
0h
Laboratory
0.5h
Guided learning
0h
Autonomous learning
2.2h

Developing the subject "Finite fields"

Developing the subject "Finite fields"
Objectives: 3
Contents:
Theory
6h
Problems
0h
Laboratory
2h
Guided learning
0h
Autonomous learning
5h

Developing the subject "Linear codes"

Developing the subject "Linear codes"
Objectives: 3
Contents:
Theory
5h
Problems
0h
Laboratory
2h
Guided learning
0h
Autonomous learning
6h

Developing the subject "Cyclic codes and CRC"

Developing the subject "Cyclic codes and CRC"
Objectives: 4
Contents:
Theory
6h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
6h

Developing the subject "Binary BCH codes"

Developing the subject "Binary BCH codes"
Objectives: 4
Contents:
Theory
6h
Problems
0h
Laboratory
3h
Guided learning
0h
Autonomous learning
7h

Developing the subject "Reed-Solomon codes"

Developing the subject "Reed-Solomon codes"
Objectives: 4
Contents:
Theory
6h
Problems
0h
Laboratory
1h
Guided learning
0h
Autonomous learning
4h

Solving problems 2

Troughout the course the student has to work on at least two problems.
Objectives: 3 4
Week: 13
Type: lab exam
Theory
0h
Problems
0h
Laboratory
0.5h
Guided learning
0h
Autonomous learning
2.3h

Report on a subject related to the course

Report on a subject related to the course where both the contents and the use of reliable information resources will be assessed.
Objectives: 1 2 3 4
Week: 14
Type: theory exam
Theory
1h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Final exam

Final exam on subjects from 4 to 8
Objectives: 3 4
Week: 15 (Outside class hours)
Type: theory exam
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
17h

Teaching methodology

In theoretical sessions the professor explains the theoretical issues giving examples and solving problems. It combines both the master methodology, in which the professor presents, explains and illustrates the concepts of the subject, and the interaction with students.

In the lab sessions, and during the hours of personal study, students should try to solve problems from a collection. The teacher supports the student with the difficulties that may raise. It is intended that students take the initiative in solving problems, evaluating solutions and learn from their mistakes.

Evaluation methodology

There will be two partial exams.

The final mark is obtaining averaging the gradings of the partial exams.

Bibliography

Basic:

Complementary:

Web links

Previous capacities

The student should:

(a) know the logarithm function and its properties,
(b) basic properties of finite probability distributions and random variables,
(c) know the ring of modular integers and perform calculations;
(d) know the basics of vector spaces: systems of linear equation, linear dependence and independence, basis and dimension, matrix operations (sums, products) and compute inverse;
(d) know the basic properties of polynomials and know how to operate with them.