An introduction to the concepts and algortihms of error correcting codes.
Teachers
Person in charge
Francesc Tiñena Salvañà (
)
Others
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
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,
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:
CTI3.3,
G6.3,
CTI1.4,
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,
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
Information and entropy.
Mathematical definition of the amount of information. Entropy of a probability distribution and mutual information of two random variables.
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.
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.
Finite fields
Construction of finite fields, specially those of characteristic 2. Elementary properties and efective computations in finite fields.
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.
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.
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.
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
ActivityEvaluation act
Information and entropy
Developing the subject "Information and entropy" Objectives:1 Contents:
Troughout the course the student has to work on at least two problems. Objectives:34 Week:
13
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:1234 Week:
14
Theory
1h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h
Final exam
Final exam on subjects from 4 to 8 Objectives:34 Week:
15 (Outside class hours)
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:
Apunts de Teoria de la Informació i Codificació -
Farré, Rafel,
2003.
(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.