Educational offer - University of Padova

Syllabus

Prerequisites:	Previous knowledge of the following topics is expected: Calculus, Linear Algebra, Probability, Random Variables and Stochastic Processes, Signals and Systems, Digital signal processing, basic elements of the Matlab programming language.
Target skills and knowledge:	The educational goal of the course is to provide the fundamentals and tools to analyze and develop both lossless and lossy data compression techniques. In particular the course is expected to provide the following knowledge and skills: 1. To learn a solid knowledge of Information Theory. 2. To know the main lossless coding techniques. 3. To be able to apply the lossless coding techniques to the reversible compression of data and multimedia contents. 4. To know the fundamentals used to develop lossy coding techniques. 5. To be able to use the appropriate lossy techniques to the compression of audio, images and video signals. 6. To be able to evaluate the bounds on the performances of both lossless and lossy compression methods. 7. To know the main coding standards presently used for the compression of multimedia contents (audio, images, video).
Examination methods:	The grading of the expected knowledge and skills is based on two contributions: 1. A closed book written exam, where the student must solve 3 problems, needed to verify that a good knowledge of the theoretical aspects of Information Theory and of the fundamental characteristics of the various lossless and lossy coding systems analyzed during the course has been acquired. 2. The development of a home assignment consisting in a computer simulation project using Matlab. The project simulates a coding/decoding system for data and/or multimedia signals. Each student must write a report describing the methodologies used to solve the assigned project with the obtained results and show them by means of a short presentation (using slides). The written exam contributes 50% to the final score, and the project contributes the remaining 50% to the final score.
Assessment criteria:	The evaluation criteria with which the verification of the knowledge and expected skills is carried out considers the following aspects: 1. The completeness and the degree of detail of the acquired knowledge of Information Theory and of the different lossless and lossy coding techniques. 2. The knowledge of the applications of the lossless and lossy coding techniques to the compression of the various kind of multimedia signals. 3. The ability to evaluate the performance bounds achievable with both lossless and lossy compression systems. 4. The skill to apply the acquired theory to identify the appropriate tools for the design and realization of coding/decoding systems for the compression of data and/or multimedia signals, whit particular attention to practical implementation aspects.
Course unit contents:	Lossless coding: Fundamentals of Information Theory. Entropy and its properties. Single symbol coding. Uniquely decodable codes and prefix codes. Huffman coding. Coding blocks of symbols. First Shannon theorem. Typical set. Asymptotic equipartition property. Arithmetic coding and dictionary-based coding (Ziv-Lempel). Context based adaptive coding. Lossy coding: Scalar quantization. Uniform and nonuniform quantization. Optimal Lloyd-Max quantizer. Nonuniform companded quantization. Vector quantization. The LBG algorithm. Rate-distortion function R(D) and distortion-rate function D(R). Gaussian case. Shannon lower bound. Predictive coding. DPCM and optimal linear predictor. Transform coding. Karhunen-Loève transform and DCT. Subband coding. Optimal bit allocation. Coding gains and asymptotic values. Applications to multimedia signal compression (audio, images, video): Multimedia signals redundancy. Objective redundancy and perceptual redundancy. Image coding. Coding of general audio signals and of speech. Video coding. Essentials of MPEG Audio (MP3), JPEG, JPEG2000, MPEG2 and H.264/AVC standards.
Planned learning activities and teaching methods:	Teaching is provided by means of lectures at the chalkboard, since we believe that this way of teaching allows to keep the right rate (speed) in the presentation of the different topics and to maintain the student attention high, with the possibility of interaction and participation. The lectures at the chalkboard are complemented by the presentation of several design and/or simulation results shown using a computer and visualized on large screen.
Additional notes about suggested reading:	All the topics of the course will be taught in classroom. Class notes can be integrated with the reference textbook and with additional material made available on the moodle platform.
Textbooks (and optional supplementary readings)	K. Sayood, Introduction to data compression. Walham: Morgan Kaufmann, 2012.