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
CFUHOURSACTIVITY
540LESSONS
432EXERCISES
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
More Information
The course language is Italian.
  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2019-05-14]