ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| TEORIA DELL'INFORMAZIONE | INF/01 | LEZIONI | 48 |
|
Acquisizione dei fondamenti teorici della teoria dell'informazione, delle metodologie e delle tecnologie per la codifica di sorgente di segnali, delle tecnologie per la protezione dell'informazione nei confronti di errori, principali metodologie di compressione dati, con particolare riferimento alla teoria matematica della comunicazione di C. Shannon, con particolare attenzione alle nozioni di informazione e di codice.
Theoretical foundations of information theory and of methods and tecniques for coding of data sources.
Esame orale
oral exam
Prova orale preceduta da uno scritto/progetto da svolgersi in aula o a casa.
Oral exam preceded by a written / project to be carried out in the classroom or at home.
Conoscenze di base di usare un linguaggio di programmazione, nozioni di base della teoria degli algoritmi e delle strutture dati, calcolo delle probabilità e algebra.
Le conoscenze necessarie saranno comunque ripetute durante il corso.
Basic knowledge of the use of a programming language, basic notions of algorithm theory and data structures, probability and algebra. The needed knowledge will be given again during the course
Lezioni frontali
Attività di apprendimento:
Frequenza: fortemente consigliata
Metodo di insegnamento:
Frontal lessons
Learning activities:
attendance of lessons
participation in classroom discussions
individual and group study
Frequency: strongly recommended
Teaching method:
Frontal lessons with slides
Elementi di teoria dell’informazione: entropia di una sorgente, entropia relativa. Entropia congiunta e entropia condizionata.
Sorgenti con e senza memoria.
Codifica di sorgente senza perdita di informazione: Codici ottimi. Limiti sulla lunghezza delle parole di codice per i codici ottimi. Codici univocamente decifrabili. Codici univocamente decifrabili e con ritardo di decifrazione. Codici prefissi.
Diseguaglianza di Kraft-McMillan. Algoritmo di Sardinas-Patterson. Codificatori di Huffman e di Shannon-Fano-Elias. Codifica di sorgente Universale. Codificatori aritmetici. Codifica Move-To-Front.
Teoremi di Shannon. Complessità di Kolmogorov.
Codificatore di Lempel-Ziv: LZ77, LZ87, LZW.
Metodi di compressione basati su contesto. La trasformata di Burrows e Wheeler (BWT). Invertibilita' della BWT. Proprietà matematiche della BWT. Metodi di compressione e indicizzazione basati su BWT.
Codice a rivelazione o correzione di errori. Classificazione dei codici: codici a ripetizione, a blocchi, lineari, ciclici. Codici a controllo parità. Codici di Hamming. Codici convoluzionali. Algoritmo di Viterbi.
Elements of information theory: entropy of a source, relative entropy. Joint entropy and conditional entropy.
Lossless source coding: Optimal codes. Limits on codeword length for optimal codes. Uniquely decipherable codes with and without delay. Prefix codes.
Source with and without memory.
Kraft-McMillan inequality. Sardinas-Patterson algorithm. Huffman and Shannon-Fano-Elias encoders. Universal source coding. Arithmetic encoders. Move-To-Front encoder.
Shannon theorems. Kolmogorov complexity.
Lempel-Ziv encoder:: LZ77, LZ87, LZW.
Context-based compression methods. The Burrows and Wheeler transform (BWT). Invertibility of the BWT. Mathematical properties of the BWT. BWT-based compression and indexing methods.
Error Detection and correction codes. Code classification: repeating, block, linear, cyclic codes. Parity checking codes. Hamming codes. Convolutional codes. Viterbi algorithm.
Testi di riferimento
Cover T.M. and Thomas J.A., Elements of Information Theory, Wiley-Interscience, 2006 (per gli argomenti di teoria dell'Informazione/for topics on Information Theory) ISBN 978-0471241959
Robert Ash. Information Theory.
Sayood K., Introduction to Data Compression, Morgan Kauffman, 2017 ISBN 978-0124157965
Salomon D., Motta G. Handbook of Data Compression, Fifth Edition, Springer 2010 ISBN 978-1-84882-902-2
- Appunti di teoria dell'informazione, by P. Piram and F. Romani
- Copy of slides
All the material is in italian language.
Reference textbooks:
Cover T.M. and Thomas J.A., Elements of Information Theory, Wiley-Interscience, 2006 (per gli argomenti di teoria dell'Informazione/for topics on Information Theory) ISBN 978-0471241959
Robert Ash. Information Theory.
Sayood K., Introduction to Data Compression, Morgan Kauffman, 2017 ISBN 978-0124157965
Salomon D., Motta G. Handbook of Data Compression, Fifth Edition, Springer 2010 ISBN 978-1-84882-902-2
Nessuna regola particolare
No special rules
Esame orale con un'eventuale pre-test da svolgersi in aula o a casa
Oral exam with a possible pre-test to be held in the classroom or at home
