To study methods for compression of symbolic data as well as audio,
image and video data. To gain an appreciation of the ubiquity and
importance of compression technologies.
Students should achieve: broad knowledge of compression techniques
as well as the mathematical foundations of data compression;
factual knowledge about existing compression standards or
commonly-used compression utilities;
understanding of the ubiquity and importance of compression technologies
in today's environment;
elementary understanding of the need for modeling data and
the underlying issues.
Class sessions together with course notes, recommended textbooks,
problem classes with worksheets and model solutions, web support.
marked courseworks, class tests, traditional written
To teach students how to compute basic statistics of data, and
how to apply nontrivial algorithms to real-world problems.
Students will be able to: understand and describe various models
of data; understand the basic data compression algorithms and show
how they work on a particular input; implement these algorithms;
compare their efficiency in terms of speed and compression ratio.
Class sessions and problem classes.
marked coursework, class tests, traditional written
Explanation of Pre-requisites
There are two main prerequisites. Firstly, students should have some
knowledge of how data of various kinds (numbers, characters, images
and sound) are represented digitally in uncompressed format. This
will be reviewed rapidly at the start of the course. Some elementary
mathematics is also required. In particular, trigonometry: basic
functions-, and measuring angles in radians;
probability: basic definitions and expected values; matrices:
transposition and multiplication and recurrence relations: basic
familiarity. Basic familiarity with the elements of computer systems
and networks is also desirable.
Data compression is about finding novel ways of representing data so
that it takes very little storage, with the proviso that it should
be possible to reconstruct the original data from the compressed
version. Compression is essential when storage space is at a premium
or when data needs to be transmitted and bandwidth is at a premium
(which is almost always). The first thing that one learns about
compression is that it is not ``one size fits all'' approach: the
essence of compression is to determine characteristics of the data
that one is trying to compress (typically one is looking for
patterns that one can exploit to get a compact representation). This
gives rise to a variety of data modeling and representation
techniques, which is at the heart of compression. The convergence of
the communications, computing and entertainment industries has made
data compression a part of everyday life (e.g. MP3, DVD and Digital
TV) and has thrown up a number of exciting new opportunities for new
applications of compression technologies.
Introduction: Raw multimedia data representation, Transmission
medium characteristics, Data compression, Adaptive and non-adaptive
methods, Lossy and lossless compression, Introduction to information
theory and Theoretical limits of compressibility. Compressing
symbolic data: Run-length coding, Entropy coders: Huffman coding,
arithmetic coding, Dictionary coders: LZ77, LZW, Other text
compression methods: Block-sorting. Standard text compression
utilities: compress, zip. Image compression: Monochrome, facsimile
and grayscale compression, GIF compression, JPEG compression, Video
compression: Frame-by-frame compression: M-JPEG. Inter-frame
compression: MPEG. Audio compression: Speech coding: ADPCM;
CD-quality audio: MPEG layer 3. Overview of compression
Course notes, web page, study guide, worksheets, handouts, lecture
rooms with a computer to CFS, data projector, two OHPs, past
courseworks and examination papers.
Course questionnaires, course review.