| PAGINA INIZIALE | INFORMAZIONI STUDENTI |
|
Dipartimento di Matematica e
Fisica |
Codici
Lineari (8 crediti) prof. Francesco Mazzocca |
|
Introduzione alla costruzione e all'uso (codifica e decodifica) di codici rivelatori e correttori di errori, mediante metodi geometrici e algebrici. a.a.2016/17 dal -- al -- giugno 2017 L'esame consta di una prova orale. mercoledì
dalle 09.00 alle 11.00 |
Anno Accademico 2016-17 Appunti (lucidi) del corso (a-a- 2015/16) Programma di massima Introduzione
al corso: il problema della trasmissione dell'informazione, i
contributi di C.E.Shannon e R.W.Hamming e i primi codici autocorrettori. (n,M)-Codici q-ari. Distanza di Hamming. Distanza minima. Sfere di Hamming. Disuguaglianza di Singleton. Codici sistematici. Codici MDS. Decodifica di minima distanza: rilevazione e correzione di errori. Raggi di impacchettamento e di copertura di un codice. Codici e-correttori. Disuguaglianza di Hamming e codici perfetti. I codici perfetti banali e il codice di Hamming Ham(3,2). Algoritmi di decodifica di minima distanza. Decodifica con tabelle standard. Equivalenza di codici. Il problema fondamentale della teoria dei codici e la funzione Aq(n,d). Codici di ripetizione. Disuguaglianza di Gilbert-Varshamov. Il problema di Eulero dei 36 ufficiali e quadrati latini. Quadrati latini ortogonali e enunciato del teorema di R.C.Bose - E.T.Parker – S.S.Shrikhande. Massimo numero di quadrati latini mutuamente ortogonali. Relazione tra (4,M,3)-codici e Aq(4,3). Richiami sui campi di Galois. Codici lineari: prime definizioni, proprietà ed esempi. Peso minimo. Matrici generatrici. Il codice binario di Golay. Equivalenza di codici lineari. Prodotto scalare standard e ortogonalità in V(n,q). Codice ortogonale. Matrici di controllo. Codici autoortogonali e autoduali. Codice esteso. Il codice binario di Golay esteso. Codifica di canale. Laterali di un codice lineare e tabelle standard. Decodifica con tabelle standard. Sindromi e decodifica a sindromi. Codici binari autoduali, codici binari pari e doppiamente pari. Proprietà dei codici binari di Golay. Teoremi relativi allla relazione fondamentale tra la distanza minima e le matrici di controllo di un codice lineare. Il codice ternario di Golay. (n,d-1)-insiemi e (n,d-1)-insiemi ottimi negli spazi vettoriali su campi di Galois. Packing problem negli spazi vettoriali su campi di Galois, problema fondamentale della teoria dei codici lineari e equivalenza dei due problemi. La funzione maxd-1(m,q). Codici lineari MDS. Determinanti di Vandermonde. Curve razionali normali in V(m,q), iperovali regolari in V(3,q) e codici MDS associati. La funzione max2(m,q). Costruzione e proprietà dei codici di Hamming. Codici di Hamming binari e loro decodifica veloce. Codici binari di Hamming e gioco dei cappelli. Le funzioni max3(m,2) e max3(m,q). Introduzione alla crittografia asimmetrica e algoritmo RSA. Il criptosistema di McEliece. Richiami su: l'anello F[x] dei polinomi su un campo, ideali di F[x], quozienti di F[x], l'anello quoziente Fq[x]/(xn-1). Codici ciclici: definizione, esempi, caratterizzazione, polinomio generatore, polinomio di controllo. Ciclicità dei codici binari di Hamming. Codici BCH binari 2-correttori. Piani proiettivi: definizione e prime proprietà. Piani proiettivi su campi. Piani proiettivi finiti. Matrice d'incidenza di un piano proiettivo finito e sue proprietà. Codice lineare (binario) associato ad un piano proiettivo finito d'ordine n e sue prime proprietà. Proprietà del codice lineare associato ad un piano proiettivo finito d'ordine n=2(mod 4). Polinomio enumeratore dei pesi di un codice lineare e relazione di MacWilliams. Non esistenza del piano proiettivo d'ordine 10.
|
| |