| Digital Codes | Code: M0.528 : 6 |
Error control codes are used to detect and correct errors that may occur in data transmission or storage through eventually defective channels or storage devices that can distort the sent or stored information. For example, the atmosphere introduces errors in the transmission of images from the Meteosat satellite to Earth, different interferences in a communication by mobile phone may cause transmission errors, or reading devices need correcting algorithms for handling CDs, DVDs or USB memories. Error control codes are also used in distributed data storage in the clouds to recover lost or damaged chunks of information.
The modus operandi of those codes is sending along with the original information a small amount of redundancy, so that from all the received information, one can deduce what is actually transmitted. The simplest example is adding for every transmitted bit (a 0 or a 1), two identical copies. So if the original bit or one of its copies is wrongly received, we can still correct it from the other two, which we expect to coincide. Note that by adding redundancy, on one side we improve the quality of the received information. But, on the other side, we augment the transmission cost. In the example of repeating bits, the transmission cost is multiplied by three.
Coding Theory aims at designing and implementing codes with good correcting capacity, while maintaining a low transmission cost, as well as designing detection and correction algorithms that allow the receiver to recover the original information.
In this course we will introduce Reed-Solomon codes, nowadays the most used codes, the CRC codes used in mobile cell phone networks, cordless phones, USB memories, Gzip, Bzip2 and other software systems, as well as the LRC codes used by the Microsoft team in their Windows Azure.
This subject is an optative subject of the first semester. It has continuity with the subject of Cryptography of the second semester.
Software engineering, electronic devices and cloud storage systems.
Basic mathematics knowledge (Mathematics or Engineering Bachelor's degree)
- Knowing the notions of divisibility, prime numbers and greatest common divisor. Knowing how to factor an integer and to determine its primality and knowinh how to calculate the greatest common divisor of two integers.
- Knowing how to manipulate integer congruences and the rings Zm. Knowing how to operate with polynomials.
- Knowing how to manipulate finite fields.
- Knowing the basic notions of information theory and the meaning of the discipline.
- Having an idea of the notion of noisy channel, as well as of the problem of error detection and correction.
- Knowing the notions of block code, Hamming distance, code length and error correcting capacity.
- Knowing the notion of linear code and knowing how to manipulate the generator and parity check matrices of a linear code.
- Knowing how to apply error correction by syndromes.
- Knowing cyclic codes and understanding the notion of generator polynomial. Knowing how to do the basic operations of a cyclic code using the generator polynomial.
- Knowing how to build and how to operate with algebraic, Reed Solomon and BCH codes.
- Knowing the CRC and LRC codes.
- Having an idea of other applications.
1. Arithmetic and Finite Fields:
a) Divisibility, prime numbers, greatest common divisor and Euclid's algorithm.
b) Congruences. Rings Zm. Polynomials, divisibility of polynomials, primitive elements.
c) Finite fields.
2. Information coding (classical):
a) Information theory. Noisy channels.
b) Block codes. Length and correction capacity.
c) Linear codes. Generator matrix and parith check matrix. Correction of errors by syndrome.
d) Cyclic codes. Generator polynomial.
e) Algebraic codes. Reed-Solomon and BCH codes.
3. Information coding (advanced)
Diverse applications of the Reed-Solomon codes CRC and LRC codes
| Finite arithmetic and error correcting codes |
Assessment at the UOC is, in general, online, structured around the continuous assessment activities, the final assessment tests and exams, and the programme's final project.
Assessment activities and tests can be written texts and/or video recordings, use random questions, and synchronous or asynchronous oral tests, etc., as decided by each teaching team. The final project marks the end of the learning process and consists of an original and tutored piece of work to demonstrate that students have acquired the competencies worked on during the programme.
To verify students' identity and authorship in the assessment tests, the UOC reserves the right to use identity recognition and plagiarism detection systems. For these purposes, the UOC may make video recordings or use supervision methods or techniques while students carry out any of their academic activities.
The UOC may also require students to use electronic devices (microphones, webcams or other tools) or specific software during assessments. It is the student's responsibility to ensure that these devices work properly.
The assessment process is based on students' individual efforts, and the assumption that the student is the author of the work submitted for academic activities and that this work is original. The UOC's website on academic integrity and plagiarism has more information on this.
Submitting work that is not one's own or not original for assessment tests; copying or plagiarism; impersonation; accepting or obtaining any assignments, whether for compensation or otherwise; collaboration, cover-up or encouragement to copy; and using materials, software or devices not authorized in the course plan or instructions for the activity, including artificial intelligence and machine translation, among others, are examples of misconduct in assessments that may have serious academic and disciplinary consequences.
If students are found to be engaging in any such misconduct, they may receive a Fail (D/0) for the graded activities in the course plan (including final tests) or for the final grade for the course. This could be because they have used unauthorized materials, software or devices (such as artificial intelligence when it is not permitted, social media or internet search engines) during the tests; copied fragments of text from an external source (the internet, notes, books, articles, other students' work or tests, etc.) without the corresponding citation; purchased or sold assignments, or undertaken any other form of misconduct.
Likewise and in accordance with the UOC's academic regulations, misconduct during assessment may also be grounds for disciplinary proceedings and, where appropriate, the corresponding disciplinary measures, as established in the regulations governing the UOC community (Normativa de convivència).
In its assessment process, the UOC reserves the right to:
- Ask students to provide proof of their identity as established in the UOC's academic regulations.
- Ask students to prove the authorship of their work throughout the assessment process, in both continuous and final assessments, through a synchronous oral interview, of which a video recording or any other type of recording established by the UOC may be made. These methods seek to ensure verification of the student's identity, and their knowledge and competencies. If it is not possible to ensure the student's authorship, they may receive a D grade in the case of continuous assessment or a Fail grade in the case of the final assessment.
Artificial intelligence in assessments
The UOC understands the value and potential of artificial intelligence (AI) in education, but it also understands the risks involved if it is not used ethically, critically and responsibly. So, in each assessment activity, students will be told which AI tools and resources can be used and under what conditions. In turn, students must agree to follow the guidelines set by the UOC when it comes to completing the assessment activities and citing the tools used. Specifically, they must identify any texts or images generated by AI systems and they must not present them as their own work.
In terms of using AI, or not, to complete an activity, the instructions for assessment activities indicate the restrictions on the use of these tools. Bear in mind that using them inappropriately, such as using them in activities where they are not allowed or not citing them in activities where they are, may be considered misconduct. If in doubt, we recommend getting in touch with the course instructor and asking them before you submit your work.
|
You can only pass the course if you participate in and pass the continuous assessment. Your final mark for the course will be the mark you received in the continuous assessment. |