# Ingegneria Informatica | Information Coding and Compression

## Ingegneria Informatica Information Coding and Compression

 0622700032 DIPARTIMENTO DI INGEGNERIA DELL'INFORMAZIONE ED ELETTRICA E MATEMATICA APPLICATA EQF7 COMPUTER ENGINEERING 2017/2018

 YEAR OF COURSE 1 YEAR OF DIDACTIC SYSTEM 2017 SECONDO SEMESTRE
SSD CFU HOURS ACTIVITY TYPE OF ACTIVITY ING-INF/03 5 40 LESSONS SUPPLEMENTARY COMPULSORY SUBJECTS ING-INF/03 4 32 EXERCISES SUPPLEMENTARY COMPULSORY SUBJECTS
 VINCENZO MATTA T STEFANO MARANO
Objectives
The course is aimed to provide the methodological background for understanding channel coding and data compression.

Knowledge and understanding
Mathematical and statistical modeling of information. Principles of information theory. Redundancy and information representation. Fundamental limits of data compression and data transmission.

Applying knowledge and understanding
Modeling and analysis of source and channel coding. Design and implementation of coding and data compression algorithms.
Prerequisites
PREREQUISITES: MATHEMATICS. PROBABILITY THEORY. FUNDAMENTALS OF DIGITAL COMMUNICATIONS.
Contents
- SOURCE CODING

VARIABLE RATE CODING. FUNDAMENTAL LIMITS OF LOSSLESS CODING. HUFFMAN CODES. FIXED RATE CODING.
MULTITERMINAL SOURCE CODING: SLEPIAN-WOLF THEOREM.
SOURCE/CHANNEL SEPARATION AND UNCODED TRANSMISSIONS.

PRACTICAL IMPLEMENTATION AND SIMULATION, BY MEANS OF COMPUTER EXPERIMENTS, OF THE LOSSLESS SOURCE CODES EXAMINED DURING THE COURSE.

- QUANTIZATION

SCALAR QUANTIZATION. DISTORTION MEASURES. UNIFORM AND NON-UNIFORM QUANTIZATION. OPTIMAL DESIGN OF QUANTIZERS. NEAREST NEIGHBOR AND CENTROID CONDITIONS. LLOYD ALGORITHM. THE RATE DISTORTION FUNCTION R(D). COMPUTATION OF R(D) FOR GAUSSIAN AND BINARY RANDOM VARIABLES.

PRACTICAL IMPLEMENTATION AND SIMULATION, BY MEANS OF COMPUTER EXPERIMENTS, OF THE QUANTIZERS EXAMINED DURING THE COURSE.

- COMPRESSED SENSING

INTRODUCTION, MOTIVATION AND APPLICATIONS.
BEHIND AND BEYOND CLASSICAL SAMPLING THEORY.
SAMPLING OF SPARSE SIGNALS. SENSING MATRICES. RECONSTRUCTION WITH L0-NORM MINIMIZATION. RECONSTRUCTION WITH L1-NORM MINIMIZATION AND RELATED OPTIMIZATION ROUTINES.

- CHANNEL CODING

SECOND SHANNON'S THEOREM FOR DMCS.

LINEAR BLOCK CODING. FINITE FIELDS. GENERATOR AND PARITY CHECK MATRIX. HARD AND SOFT DECODING. SYNDROME. STANDARD ARRAY. COMPUTER EXPERIMENTS ON LINEAR BLOCK CODING.

CONVOLUTIONAL CODING AND VITERBI ALGORITHM. COMPUTER EXPERIMENTS ON CONVOLUTIONAL CODING.

TURBO CODES AND PRINCIPLES OF ITERATIVE DECODING. COMPUTER EXPERIMENTS ON TURBO CODING.

LDPC CODING AND THEIR DECODING BY BIT FLIPPING AND BY MESSAGE PASSING. COMPUTER EXPERIMENTS ON LDPC CODING.

RATELESS CODING AND LUBY ALGORITHM. COMPUTER EXPERIMENTS ON LUBY CODES.
Teaching Methods
LECTURES PROVIDING THE THEORETICAL BACKGROUND, COMPUTER-BASED DEMONSTRATIONS, CLASSROOM EXERCISES AND HOMEWORK ASSIGNMENTS.

IN ORDER TO PARTICIPATE TO THE FINAL ASSESSMENT AND TO GAIN THE CREDITS
CORRESPONDING TO THE COURSE, THE STUDENT MUST HAVE ATTENDED AT LEAST 70%
OF THE HOURS OF ASSISTED TEACHING ACTIVITIES.
Verification of learning
THE FINAL EXAM IS AIMED TO EVALUATE: KNOWLEDGE AND UNDERSTANDING SKILLS ABOUT THE TOPICS AND CONCEPTS ADDRESSED DURING THE COURSE; THE ABILITY OF SOLVING CODING AND DATA COMPRESSION PROBLEMS IN COMMUNICATION SYSTEMS; LEARNING SKILLS, SCIENTIFIC APPROACH TO COMPLEX PROBLEMS AND INCLINATION TO CRITICAL REASONING.

THE EVALUATION IS MAINLY BASED ON AN ORAL EXAMINATION, DEALING WITH ALL THE TOPICS ADDRESSED DURING THE COURSE, AND THE FINAL RATING TAKES INTO ACCOUNT, ALONG WITH THE MENTIONED CRITERIA, THE QUALITY OF THE PRESENTATION.
Texts
- T. M. COVER, J. A. THOMAS, ELEMENTS OF INFORMATION THEORY, JOHN WILEY & SONS, 1991

- A. GERSHO, R. GRAY: VECTOR QUANTIZATION AND SIGNAL COMPRESSION, KLUWER, 1991

- E. BIGLIERI, CODING FOR WIRELESS CHANNELS, SPRINGER-VERLAG, 2008

- JOHN G. PROAKIS, DIGITAL COMMUNICATIONS, MCGRAW-HILL, 2008