Information Transmission and Encoding

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

Teachers

Person in charge

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
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    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
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    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
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    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
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final exam

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

    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.