Information Coding and Compression

Ingegneria Informatica Information Coding and Compression

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



YEAR OF COURSE 1
YEAR OF DIDACTIC SYSTEM 2017
SECONDO SEMESTRE
CFUHOURSACTIVITY
540LESSONS
432EXERCISES
Objectives
THIS COURSE PRESENTS THE BASIC CONCEPT OF INFORMATION, AND THE RELATED ULTIMATE LIMITS OF DIGITAL COMMUNICATION SYSTEMS. THE PRACTICAL ASPECTS OF CODING (SOURCE AND CHANNEL) ARE ALSO ADDRESSED.

KNOWLEDGE AND UNDERSTANDING:
MATHEMATICAL AND STATISTICAL MODELING OF INFORMATION.

APPLIED KNOWLEDGE AND UNDERSTANDING:
MODELING AND ANALYSIS OF INFORMATION SOURCES AND COMMUNICATION CHANNELS. ANALYSIS OF THE MAIN CLASSES OF SOURCE AND CHANNEL CODES.
Prerequisites
MATHEMATICS AND PROBABILITY THEORY. BASIC KNOWLEDGE OF PROGRAMMING AND ALGORITHM THEORY.
Contents
ELEMENTS OF INFORMATION THEORY.
HISTORICAL SKETCH. ENTROPY AND ITS AXIOMATIC DEFINITION. ENTROPY AND DATA COMPRESSION. THE BINARY ENTROPY FUNCTION. JOINT AND CONDITIONAL ENTROPY MUTUAL INFORMATION AND DIVERGENCE. LOG-SUM INEQUALITY AND ITS CONSEQUENCES. CHEBISHEV INEQUALITY AND THE WEAK LAW OF LARGE NUMBERS. AEP AND TYPICAL SEQUENCES. SOURCE CODING BY AEP. THEOREMS OF SOURCE CODING. PREFIX-FREE CODES. MARKOV CHAINS. DATA PROCESSING INEQUALITY. DIFFERENTIAL ENTROPY. CONSTRAINED OPTIMIZATION AND LAGRANGE METHOD. MAXIMUM ENTROPY DISTRIBUTIONS. CHANNEL CAPACITY FOR DMC. CAPACITY OF BSC. FANO INEQUALITY. FUNDAMENTALS OF SHANNON'S II THEOREM. REPETITION CHANNEL CODES OVER THE BSC. HAMMING(7,4) CODE. LIMITS OF COMMUNICATION RATE IN THE PRESENCE OF ERRORS. CAPACITY OF THE GAUSSIAN CHANNEL WITH POWER CONTRAINT. SPHERE PACKING.

PRACTICAL ASPECTS OF SOURCE AND CHANNEL CODING:
HUFFMAN CODES. LEMPEL-ZIV CODES.
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 EXAMINED QUANTIZERS.
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 BLOCK CODES. CONVOLUTIONAL CODES. TURBO CODES. LDPC
Teaching Methods
INFORMATION THEORY WILL BE PRESENTED BY THEORETICAL LESSONS. IN THE APPLICATION PART OF THE COURSE CONCERNING SOURCE AND CHANNEL CODING, THE FOCUS IS ON THE ALGORITHMS AND COMPUTER PROGRAMS.

IN ORDER TO PARTICIPATE TO THE FINAL ASSESSMENT AND TO GAIN THE CREDITS CORRESPONDING TO THE COURSE, THE STUDENT MUST ATTEND AT LEAST 70% OF THE HOURS OF ASSISTED TEACHING ACTIVITIES.
Verification of learning
THE STUDENT WILL PRESENT AND DISCUSS A COMPUTER PROJECT DEVELOPED DURING THE COURSE FOR THE PART CONCERNING THE SOURCE AND CHANNEL CODES, AND AN ORAL EXPOSITION FOR THE PART CONCERNING THE THEORETICAL ASPECTS OF THE COURSE.

THE EVALUATION WILL BE BASED ON CORRECTNESS, EFFICACY, AND CLARITY OF THE PROJECT, AND ON THE DEGREE OF UNDERSTANDING, DEVELOPED SKILLS AND CRITICAL ANALYSIS FOR WHAT CONCERNS THE THEORETICAL ASPECTS.

Texts
T. M. COVER, J. A. THOMAS, ELEMENTS OF INFORMATION THEORY, JOHN WILEY & SONS, 1991.


A. GERSHO, R. M. GRAY, VECTOR QUANTIZATION AND SIGNAL COMPRESSION, SPRINGER, 1992
More Information
THE COURSE LANGUAGE IS: ITALIAN.
  BETA VERSION Data source ESSE3 [Ultima Sincronizzazione: 2019-10-21]