Algebra II 2006/2007

Scopo: nel corso si intendono approfondire concetti algebrici con
particolare enfasi alle moderne applicazioni dell'algebra nella
sicurezza delle trasmissioni(come pagare sul web), nella
correzione degli errori nelle comunicazioni (masterizzare un CD) e
nella compressione dei dati (inviare messaggi col cellulare)

Programma:
1) Introduzione:
    Basi della comunicazione;
    Sistemi di comunicazione in generale: messaggio, codificatore, canale, ricezione decodifica;
    Esempi di Codici: Ripetizione, a somma zero, Hamming 7,4.

2) Sphere Packings a Teorema di Shannon
    Codifica a blocchi su un canale simmetrico m-ario;
    Principio MLD (maximum likelihood decoding) e MDD (minimum distance decoding);
    Sphere Packing, distanza minima e capacita' correttiva di un codice;
    Condizione di Sphere packing, limiti superiori su dimensioni di codici con prefissata lunghezza e distanza minima;
    Limite di Gilbert-Varshamov;
    Cenni al Teorema di Shannon;
    Famiglie di Shannon;
    Problema della costruzione di codici ottimali;
    Entropia e Capacita' del canale simmetrico m-ario.

3) Codici Lineari:
    Richiami di Algebra Lineare;
    Richiami di Algebra: Campi finiti, ideali e anelli quoziente;
    Definizione di codice lineare;
    Dimensione;
    Peso di Hamming;
    Matrici Generatrici;
    Codici ortogonali: rappresentazione duale di un codice;
    Matrici di controllo;
    Limite di Singleton;
    Codici MDS (maximum distance separator);
    Codifica e informazione: matrici standard e sistematiche, forma a scala ridotta (RREF);
    Decodifica di codici lineari: coset leaders;
    Sindromi.

4) Codici di Hamming e di Reed-Muller:
    Rudimenti di Geometria Proiettiva su campi finiti;
    Definizione dei codici di Hamming Ham(q,r) di ridondanza r sul campo GF(q);
    Lunghezza, dimensione e distanza minima di Ham(q,r);
    Perfezione dei codici di Hamming: cenno ai codici di Golay;
    Somma di Plotkin di codici;
    Codici di Reed-Muller di livello 1 RM(1,m);
    Lunghezza, dimensione e distanza minima di RM(1,m).

5) Codici di Reed-Solomon generalizzati (GRS):
    Loro costruzione;
    Mappe di valutazione polinomiali;
    Lunghezza, dimensione e distanza minima;
    Polinomi di Lagrange e interpolazione;
    Chiusura della famiglia GRS rispetto all'ortogonale;
    Decodifica dei codici GRS;
    Polinomio locatore di errori e polinomio valutatore di errori;
    Algoritmo di Berlekamp-Massey.

6) Codici Ciclici:
    Azioni di permutazione su uno spazio vettoriale;
    Definizione di codice ciclico;
    Teorema di Prange: codici ciclici e ideali dell'anello F[x]/(x^n-1);
    Polinomio generatore;
    Chiusura rispetto all'ortogonale: polinomio reciproco;
    Reverse di un codice ciclico;
    Insiemi ciclotomici;
    Elementi algebrici e relativi polinomi minimi;
    Determinazione dei divisori di x^n-1 su GF(q).

7) Polinomi enumeratori e Teorema di MacWilliams:
    Polinomio enumeratore: forma non-omogenea e forma omogenea;
    Esempi;
    Trasformazioni lineari su polinomi omogenei;
    Teorema di MacWilliams;
    Caratteri di un gruppo abeliano finito;
    Leggi di ortogonalita'.

testi:

Dispense distribuite nel corso reperibili sotto http://scienze-como.uninsubria.it/Previtali/Teaching.html

L. Childs, "Algebra, un'introduzione concreta", ETS.
J.H. Hall "Notes in Coding theory", University of East Lansing.
Huffman, W. Cary; Pless, Vera Fundamentals of error-correcting codes.
Cambridge University Press, Cambridge, 2003. xviii+646 pp. ISBN: 0-521-78280-5
J. van Lint "An Introduction to coding theory", GTM Springer Verlag.