Module COMP4231: Data Compression and Coding Theory

Department: Computer Science

COMP4231: Data Compression and Coding Theory

Pre-requisites

Corequisites

Excluded Combinations

Aims

• To understand:
• the main techniques for error correction
• the key results of information theory and their relevance to cryptography and data compression
• the main techniques for lossless and lossy date compression
• the efficiency criteria for data compression.

Content

• Linear error correcting codes, including Hamming codes
• Bounds on codes
• Cyclic codes, including Reed-Solomon codes and their decoding
• Code-based cryptography
• Channel capacity and rate-distortion theory
• Information-theoretic security
• Huffman coding
• Arithmetic coding
• Lempel-Ziv and application to ZIP or PNG
• Context-based compression o Transform domain compression with application to JPEG
• Wavelet-based compression with application to JPEG2000
• Video and Audio compression

Learning Outcomes

• On completion of the module, students will be able to demonstrate:
• an understanding of the key features of error-correcting codes
• an understanding of public-key cryptosystems based on error-correcting codes
• an understanding of the how information theory describes the limits of data compression and cryptography
• an understanding of the key features of popular lossy and lossless compression techniques
• an understanding of the performance criteria for lossless and lossy compression

• On completion of the module, students will be able to demonstrate:
• an ability to assess the performance of error-correcting codes an ability to assess the effectiveness and security of code-based cryptosystems
• an ability to use information-theoretic tools to bound the performance of digital communication systems
• an ability to assess and design compression techniques for diverse kinds of data
• an ability to implement the key tools used in data compression.

• On completion of the module, students will be able to demonstrate:
• an ability to use algebraic techniques to solve communication problems
• an ability to apply information theory to related domains
• an ability to identify and assess the quality of heuristics for different algorithms

Modes of Teaching, Learning and Assessment and how these contribute to the learning outcomes of the module

• Lectures enable the students to learn new material.
• The examination assesses the knowledge and understanding of the material covered in the lectures.
• The report element of the coursework consists of a written assignment supported by code.

Teaching Methods and Learning Hours

Summative Assessment

Formative Assessment

Example formative exercises are given during the course.