Teoria dell'Informazione, A.A. 2003/2004

Orari del corso:

Argomenti trattati a lezione

  1. 29 Settembre 2003. Presentazione del corso. Codici di sorgente: panoramica. Codici B-LV. Alberi di codice e univoca decodificabilità.
  2. 30 Settembre 2003. Decodificabilità istantanea e non. Disuguaglianza di Kraft-McMillan. Sufficienza dei codici a prefisso. Probabilità di emissione; lunghezza media di un codice. Entropia.
  3. 6 Ottobre 2003. Divergenza. Teorema di Shannon. Codici di Shannon Fano, limitazione superiore di EL per i codici ottimi.
  4. 8 Ottobre 2003. Descrizione con variabili aleatorie di una sorgente di Informazione. Tasso del codice. Sorgenti stazionarie e senza memoria. Ottimalità asintotica dei codici di Shannon-Fano. Il codice di Fano.
  5. 10 Ottobre 2003. Il codice di Fano. Geminazione, Taglio e codice di Huffman. Entropia condizionata, mutua informazione.
  6. 13 Ottobre. Autoinformazione. Tipi e loro dimensioni. Codice multinomiale. e sua asintotica ottimalità.
  7. 16 Ottobre 2003. Codici LV-B. Famiglie esaurienti, a prefisso e complete. Generazione di famiglie complete. Relazioni tra tasso ed entropia.
  8. 20 Ottobre 2003. Alberi e Codici di Tunstall. Ottimalità degli stessi e rapporti asintotici con l'entropia della sorgente. Non ottimalità dei codici di Tunstall al di fuori delle famiglie complete.
  9. 21 Ottobre 2003. Codice universale di Ziv Lempel. Codice universale di Burrows-Wheeler.
  10. 23 Ottobre 2003. Codici B-B. Valutazione del tasso in codifica priva di errore. Modelli con errore: ricerca di una famiglia ottima. Determinazione delle dimensioni di un tipo T con il metodo probabilistico.
  11. 27 Ottobre 2003. Codici δ-tipici e Secondo Teorema di Shannon. Codici LV-LV. Limiti e codici asintoticamente ottimi.
  12. 28 Ottobre 2003: Codifica di canale: generalità. Esempi: controllo parità, codice a ripetizione e codice di Hadamard. Il modello del canale: matrice di canale, funzioni di codifica e decodifica, tasso e probabilità di errore.
  13. 30 Ottobre 2003: Esempi. Capacità di un canale e Teorema di Shannon di canale (no dim). Calcolo e significato della capacità su alcune tipologie di canale (inutile, senza errori, deterministico, CSB, CSQ). Confronti.
  14. 3 Novembre 2003: Discriminazione di Ipotesi Statistiche: a massima verosimiglianza e a massima probabilità a posteriori. Decodifica di canale a massima verosimiglianza su CSB, CSQ: decodifica a minima distanza di Hamming. Distanza minima di un codice.
  15. 4 Novembre 2003: tasso di correzione e relazioni con la Probabilità di errore. Limitazioni di Singleton e Plotkin.
  16. 10 Novembre 2003: Limitazioni di Hamming e Gilbert e considerazioni generali. Codici Correttori di Errore: introduzione ai codici algebrici.
  17. 11 Novembre 2003: Campi finiti: con p elementi e con p^r elementi. Matrice generatrice G (matrici equivalenti e in forma canonica) e Matrice di Controllo H dei codici algebrici. Peso minimo di un codice. Sindrome. Decodifica usando la Tabella di Slepian.
  18. 13 Novembre 2003: Codici di Hamming: binario, q-ario ed esteso. Perfezione del codice di Hamming.
  19. 17 Novembre 2003: Codici BCH. Introduzione, principi generali ed esempio dettagliato di codice BCH binario 2-correttore.
  20. 18 Novembre 2003: Codici di Reed-Müller: Rappresentazione algebrica di funzioni booleane, codifica e decodifica con correzione di errori.
  21. 20 Novembre 2003: Codici ciclici. Definizioni principali, polinomio generatore, teorema principale (no dim). Matrice generatrice ed esempio. Valutazione del corso.
  22. 24 Novembre 2003: Polinomio di controllo h e matrice H corrispondente. Esempio: codici di Hamming. Scelta di g e h usando le radici primitive dell'unità e i relativi polinomi minimi.
  23. 25 Novembre 2003. Progetto dei codici ciclici a partire dalle radici primitive dell'unità e relazioni con la distanza minima. Cenni ai codici di Reed e Solomon. Codici convolutivi e l'algoritmo di Viterbi.
  24. 27 Novembre 2003: Codici segreti. Breve storia della crittografia e principali risultati della crittografia a chiave pubblica.
Testo principale: Francesco Fabris. Teoria dell'Informazione, codici, cifrari. Bollati Boringhieri, 2001.

Qualche link interessante:

Home page