Teoria dell'informazione e della trasmissione
A.A. 2018/2019
Obiettivi formativi
Il corso si prefigge di fornire agli studenti un'approfondita conoscenza della teoria dell'informazione secondo Claude Shannon, insieme alle necessarie nozioni di teoria dei codici
Risultati apprendimento attesi
Non definiti
Periodo: Secondo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Linea Milano
Responsabile
Periodo
Secondo semestre
Programma
Introduzione al corso e nozioni matematiche basilari. Modello di canale con rumore.
Codifica sorgente: definizioni. Modello di sorgente. Codice non singolare. Estensione di un codice. Codice univocamente decodificabile.
Codice istantaneo e disuguaglianza di Kraft. Codice di Shannon/Fano.
Entropia di una sorgente discreta e sue proprietà. Entropia binaria. Entropia relativa. Information inequality. Entropia come limite inferiore della lunghezza media di un codice istantaneo.
Estensione n-esima di una sorgente e sua entropia. Codifica a blocchi. Primo teorema di Shannon.
Codice istantaneo ottimo, Codici di Huffman binari e di radice r.
Disuguglianza di di McMillan.
Derivati dell'entropia (entropia, entropia congiunta, entropia condizionata). Spazi condizionati. Chain rule per entropia. Informazione mutua. Relazioni fra entropie e informazione mutua. Data Processing Inequality. Disuguaglianza di Fano.
Codifica di canale. Il modello di canale di Shannon. Equazioni di canale. Capacità di canale. Canale discreto senza memoria. Canale con rumore e uscite disgiunte. Il canale binario simmetrico, canali uniformi in ingresso e/o in uscita. Canale binario a cancellazione.
Proprietà di Equipartizione Asintotica (SENZA DIMOSTRAZIONI). Tasso di trasmissione. Insieme tipico e congiuntamente tipico (SENZA DIMOSTRAZIONI).
Il secondo teorema di Shannon e le sue implicazioni.
Rumore bianco, Bit parità, Burst error-detecting code, Weighted codes, codice a ripetizione, ISBN. Codice a blocco, codice che rileva z-errori, codice che corregge t-errori, codice che rileva z- e simultaneamente corregge t-errori, distanza di Hamming, peso di Hamming.
Esempi di codici correttori: codice rettangolare, codici di Hamming.
Codici lineari binari e non. Definizione e proprietà, peso minimo di un codice lineare, matrice generatrice, matrice di parità, sistema di equazioni di decodifica/codifica, sindrome.
Codici ciclici. Definizione e proprietà, polinomio generatore; matrice generatrice; polinomio di parità, matrice di parità.
Codici Reed-Solomon, BCH.
Accenni a codici più evoluti (convoluzionali, turbo, LDPC, MDPC).
Codifica sorgente: definizioni. Modello di sorgente. Codice non singolare. Estensione di un codice. Codice univocamente decodificabile.
Codice istantaneo e disuguaglianza di Kraft. Codice di Shannon/Fano.
Entropia di una sorgente discreta e sue proprietà. Entropia binaria. Entropia relativa. Information inequality. Entropia come limite inferiore della lunghezza media di un codice istantaneo.
Estensione n-esima di una sorgente e sua entropia. Codifica a blocchi. Primo teorema di Shannon.
Codice istantaneo ottimo, Codici di Huffman binari e di radice r.
Disuguglianza di di McMillan.
Derivati dell'entropia (entropia, entropia congiunta, entropia condizionata). Spazi condizionati. Chain rule per entropia. Informazione mutua. Relazioni fra entropie e informazione mutua. Data Processing Inequality. Disuguaglianza di Fano.
Codifica di canale. Il modello di canale di Shannon. Equazioni di canale. Capacità di canale. Canale discreto senza memoria. Canale con rumore e uscite disgiunte. Il canale binario simmetrico, canali uniformi in ingresso e/o in uscita. Canale binario a cancellazione.
Proprietà di Equipartizione Asintotica (SENZA DIMOSTRAZIONI). Tasso di trasmissione. Insieme tipico e congiuntamente tipico (SENZA DIMOSTRAZIONI).
Il secondo teorema di Shannon e le sue implicazioni.
Rumore bianco, Bit parità, Burst error-detecting code, Weighted codes, codice a ripetizione, ISBN. Codice a blocco, codice che rileva z-errori, codice che corregge t-errori, codice che rileva z- e simultaneamente corregge t-errori, distanza di Hamming, peso di Hamming.
Esempi di codici correttori: codice rettangolare, codici di Hamming.
Codici lineari binari e non. Definizione e proprietà, peso minimo di un codice lineare, matrice generatrice, matrice di parità, sistema di equazioni di decodifica/codifica, sindrome.
Codici ciclici. Definizione e proprietà, polinomio generatore; matrice generatrice; polinomio di parità, matrice di parità.
Codici Reed-Solomon, BCH.
Accenni a codici più evoluti (convoluzionali, turbo, LDPC, MDPC).
Prerequisiti
Per la comprensione degli argomenti trattati nel corso è gradita una buona conoscenza di: gruppi finiti, campi finiti, spazi lineari, prodotto matriciale e vettoriale, algebra modulare, algebra polinomiale, logaritmi. Inoltre sono assai graditi elementi di calcolo delle probabilità, variabili casuali discrete, probabilità congiunte, marginali, condizionate, Teo di Bayes.
Materiale di riferimento
Materiale di riferimento:
Thomas Cover, Joy Thomas, Elements of Information Theory (2nd edition), Wiley, 2006.
Jiri Adamek, Foundations of Coding, Wiley, 1991.
S.Monser, P.Chen, A Student's Guide to Coding and Information Theory, Cambridge University press, 2012.
Altro materiale suggerito (per approfondimenti su specifici argomenti del corso):
Richard Hamming, Coding and Information Theory, Prentice-Hall, 1986 o 1980.
Robert H. Morelos-Zaragoza, The Art of Error-Correcting Coding, Wiley, 2006.
M.Baldi, QC-LDPC Code-Based Cryptography, Springer, 2014.
Thomas Cover, Joy Thomas, Elements of Information Theory (2nd edition), Wiley, 2006.
Jiri Adamek, Foundations of Coding, Wiley, 1991.
S.Monser, P.Chen, A Student's Guide to Coding and Information Theory, Cambridge University press, 2012.
Altro materiale suggerito (per approfondimenti su specifici argomenti del corso):
Richard Hamming, Coding and Information Theory, Prentice-Hall, 1986 o 1980.
Robert H. Morelos-Zaragoza, The Art of Error-Correcting Coding, Wiley, 2006.
M.Baldi, QC-LDPC Code-Based Cryptography, Springer, 2014.
Docente/i
Ricevimento:
Controllare le informazini presenti sulla pagina personale del docente.
Stanza 5008 -- Quinto Piano, Dipartimento di Informatica, via Celoria 18, Milano.