Università Roma Tre

1) Introduzione alla teoria dell'informazione

- Codici a correzione d'errore. Canale binario simmetrico.
Codici a blocco. Codici di Hamming. $(7,4)$-Hamming.
Matrice di generazione del codice nel caso lineare.
Decodifica nel caso del codice $(7,4)$-Hamming. Sindromi.
Decodifica mediante sindromi. Efficenza dei codici.
Capacità di un canale. Codici simmetrici. Rappresentazione grafica
associata ad un codice.

- Probabilità. Spazi di probabilità. Probabilità discreta.
Probabilità a posteriori. Principio di massima
verosimiglianza. Definizione di entropia. Contenuto informativo
secondo Shannon. Ridondanza. Entropia congiunta. Regola di
decomposizione per il calcolo dell'entropia. Disugualgianza di Gibbs.
Disuguaglianza di Jensen.
- Inferenza.

([1] capp. 1, 2, 3)

2) Compressione Dati

- Teorema di codifica della sorgente. Misura del contenuto d'informazione
di una variabile aleatoria. Contenuto informativo grezzo. Contenuto informativo
e compressione con perdita. Contenuto informativo essenziale. Teorema di Shannon.
Insiemi di tipicità. Principio di equipartizione asintotica.

- Codici Simbolici. Codifica senza perdita di informazione.
Codici prefissi. Decodifica univoca. Disuguaglianza di Kraft.
Codici ottimali. Codifica di Huffman.

- Codici Flusso. Codici aritmetici. Modello Bayesiano.
Codici Huffman con intestazione. Codici aritmetici con modello
predittivo di Laplace. Codici aritmetici con modello predittivo
di Dirichlet. Codifica Lempel-Ziv.

([1] capp. 4,5,6)

3) Codifica di canale in presenza di rumore

- Variabili aleatorie dipendenti. Entropia congiunta.
Entropia Condizionata. Mutua informazione. Mutua informazione
condizionata.

- Comunicazione su canali in presenza di rumore. Canale discreto
senza memoria (DMC). Esempi: canale binario simmetrico (BSC), canale
binario con cancellazione (BEC), la telescrivente con rumore (NT),
lo zeta-channel (Z). Informazione trasportata da un canale.

- Il teorema di codifica della sorgente nel caso con rumore.
Decodifica ottimale. Probabilità di errore sul blocco e in media sul
singolo bit. Sequenze tipiche e insiemi di tipicità
congiunta. Decodifica mediante insiemi di tipicità. Valutazione
dell'informazione nel caso di utilizzo di un canale oltre la
capacità.

- Codici a correzione d'errore e applicazioni.

([1] capp. 8,9,10,11)

4) Ulteriori codici

- Codici Hash.
- Codici Lineari.

([1] capp. 12,14)

[1] David J. C. MacKay, Information Theory, Inference and Learning Algorithms. (2004) Cambridge University Press;
[2] R. Blahut, Principles and Practice of Information Theory, (1987) Addison Wesley.
[3] Thomas and Cover, Elements of Information Theory, (1991) Wiley;