This double module introduces the fundamentals of coding theory and data compression. 

The first part is devoted to coding theory and will mainly focus on error-correcting codes, their properties and applications. No document or computer files can be guaranteed free from error.  Error-correcting codes are used to spot mistakes and suggest the most likely correction. If the rate of errors is such that several mistakes are likely in a single ‘word’ (e.g. radio transmissions), then the codes used are more combinatoric.  If errors are so rare that having two mistakes in the same ‘word’ is very unlikely (e.g. brand new computer disc), then the codes used are more algebraic. Many error-correcting codes correspond to geometrical patterns.

The second part of the module deals with the broad field of data compression. We will first study lossless compression schemes, including the fundamental algorithms of Shannon, Huffman, Lempel-Ziv and arithmetic coding. Finally, the module will give the basic principles of lossy compression, such as quantization and transform coding. For instance, we will see the role wavelets (“the mathematical microscope”) play in data compression.

• Understand how error-correcting codes can be used to reduce the probability of a message being misread.
• Classify an error-correcting code and describe its properties.
• Describe some standard examples of error-correcting codes.
• Demonstrate an understanding of the theoretical constraints on possible error-correcting codes.
• Display competence in the fundamental ideas of the lossless data compression.
• Demonstrate understanding of the underlying mathematical theory and algorithms.
• Understand fundamental ideas of quantization and transform coding.
• Understand how lossless and lossy compression algorithms can be used for solving scientific and engineering problems.

54 - 50 minute lectures

Some handouts will be provided in hard copy or via Learning Central, but students will be expected to take notes of lectures.

Students are also expected to undertake at least 100 hours private study including preparation of solutions for given exercises

The main properties of the error-correcting codes, fundamentals of data compression algorithms, methods of quantization and lossy data compression.

Understanding how compression techniques can be used for solving scientific and engineering problems.

Formative assessment is carried out by means of regular tutorial exercises.  Feedback to students on their solutions and their progress towards learning outcomes is provided during tutorial classes.

Thesummative assessment is the written examination at the end of the module.  This gives students the opportunity to demonstrate their overall achievement of learning outcomes.  It also allows them to give evidence of the higher levels of knowledge and understanding required for above average marks.

The examination paper has a choice of three from four equally weighted questions.

• Code-words, block codes, error rate
• Equivalent codes, symmetries.
• Hamming distance, the minimum distance in a code.
• Transmission efficiency of information.  The “sphere-packing” bound for M in terms of d.
• Finite fields, Plotkin’s bounds
• Linear codes, perfect codes
• Compression Techniques
• Coding in Data Compression
• Introduction to Information Theory
• Shannon’s Fundamental Theorems
• Fundamental Compression Algorithms
• Quantization
• Transform Coding

A First Course in Coding Theory, Hill, R., Clarendon Press, 1986

Introduction to Data Compression, Sayood, K., Morgan Kaufmann, 2000

Not applicable.