An introduction to the concepts and algortihms of error correcting codes.
Person in charge
Jose Luis Ruiz Muñoz (
Technical Competences of each Specialization
Information technology specialization
CTI1 - To define, plan and manage the installation of the ICT infrastructure of the organization.
- 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.
- To design, establish and configure networks and services.
G6 - 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.
- 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.
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.
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.
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.
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.
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.
Construction of finite fields, specially those of characteristic 2. Elementary properties and efective computations in finite fields.
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 as cyclic codes. The finite Fourier transform. Algorithm for error-correction. Application: coding of the audio compact disc.
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:
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:
Final exam on subjects from 4 to 8 Objectives:34 Week:
15 (Outside class hours) Type:
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.
(1) Students have to write a report on a topic related to course. The report's content and the use of reliable information resources will be assessed separately.
The grade for the cross-competition "Using reliable information resources" is gotten directly from the report and the bibliography research therein.
(2) Students are supposed to hand in three problems each counting 10% of the final mark.
Rating: P1, P2, P3
(3) There is a mid-term exam in class time (20%), about the sixth week of the course on the contents 1, 2 and 3. These subjects will not be further requested.
(4) There is a final exam not in class-time (50%) on the contents 4, 5, 6, 7 and 8.
(5) The final mark of the course is computed as:
0.10 * P1 + 0.10*P2 + 0.10*P3 + 0.20 Pa + 0.50 * F
(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.
Where we are
B6 Building Campus Nord
C/Jordi Girona Salgado,1-3
08034 BARCELONA Spain
Tel: (+34) 93 401 70 00