Facoltà di Scienze Matematiche, Fisiche e Naturali
Corso di Laurea in Matematica

Anni Accademici
2009/2010 - 2010/2011 - 2011/2012

Introduzione alla costruzione e all'uso (codifica e decodifica) di codici rivelatori e correttori di errori, mediante metodi geometrici e algebrici.

Lucidi delle lezioni  e   Indice
Introduzione alla Crittografia   -   Crittosistema di McEliece

Introduzione al corso: il problema della trasmissione dell'informazione; I contributi di C.E.Shannon e R.W.Hamming.

Alfabeti, parole su un alfabeto, codici su un alfabeto: prime definizioni ed esempi. Il codice fiscale italiano. Il codice ISBN. Il codice MORSE. Il codice ASCII. Il codice a barre EAN.

Schema di Shannon di un sistema di comunicazione. Sorgenti di informazione senza memoria: definizione, distribuzione di probabilità, entropia, esempi. Compressione di dati e algoritmo di D.A.Huffman. Codici istantanei e disuguaglianza di Kraft. Codifica di sorgente e relativo teorema di Shannon. Canali di trasmissione senza memoria: definizione, matrice di transizione, rumore, n-esima matrice, entropia, flusso medio di informazione e capacità. Canali simmetrici. Sistemi di comunicazione discreti. Codifica di canale e relativo teorema di Shannon. Schemi di decodifica. Affidabilità di un sistema di comunicazione.

(n,M)-Codici q-ari. Distanza di Hamming. Distanza minima. Sfere di Hamming. Codici sistematici. Disuguaglianza di Singleton e 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). Il problema fondamentale della teoria dei codici e la funzione Aq(n,d). Codici di ripetizione. Disuguaglianza di Gilbert-Varshamov. Algoritmi di decodifica di minima distanza. Decodifica con tabelle standard. Equivalenza di codici.

Codici perfetti e teoria dei giochi: il problema dei cappelli. 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.Shikhande. Massimo numero di quadrati latini mutuamente ortogonali. Relazione tra (4,M,3)-codici e Aq(4,3).

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 duale. Matrici di controllo. Codice esteso. Il codice binario di Golay esteso. Codifica e decodifica con tabelle standard. Sindromi e decodifica a sindromi. Codici binari autoduali e studio 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. Costruzione e proprietà dei codici di Hamming. Decodifica veloce dei codici di Hamming binari. Le funzioni max3(m,2) e max3(3,q).

Richiami sui campi finiti. Richiami su: l'anello F[x] dei polinomi su un campo, ideali di F[x], quozienti di F[x], l'anello quoziente Fq[x]/(xⁿ-1). Codici ciclici: definizione, esempi, caratterizzazione, polinomio generatore, polinomio di controllo. Ciclicità dei codici binari di Hamming. Codici BCH binari 2-correttori.

Introduzione alla crittografia asimmetrica e algoritmo RSA. Il criptosistema di McEliece.

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.

1. F.Mazzocca, Appunti del corso.
2. Berardi L., Algebra e teoria dei codici correttori, Collana di matematica e statistica, Franco Angeli Editore, 1994.
3. L.Giuzzi, Codici correttori, Collana UNITEXT, Springer, 2006.
4. Hill R., A First Course in Coding Theory, Oxford Applied Mathematics and Computing Science Series, Clarendon Press - Oxford, 1990.
5. C.E.Shannon, A Mathematical Theory of Communication, The Bell System Technical Journal, Vol.27, pp.379-423  623-646 July, October, 1948.
6. F.Mazzocca, Appunti del corso di Geometria Combinatoria.

• Eric Weisstein's World of Mathematics (coding theory - combinatorics - graph theory - finite groups).
• Coding theory: the first 50 years
• Saleem Bhatti, Information and Coding Theory
• Peter J. Cameron, Finite geometry and coding theory
• Bill Cherowitzo, Coding Theory, Combinatorial structures
• J.I. Hall, Notes on Coding Theory
• Ling San, Coding Theory
• Madhu Sudan, A Crash Course on Coding Theory
  
   
• Interactive Mathematics Miscellany and Puzzles .
• The MacTutor History of Mathematics archive
• "Progetto Matematic@"  dell'Università di Bologna   (piani affini).
  
   
• Unione Matematica Italiana     European Mathematical Society    International Mathematical Union
• Progetto Lauree Scientifiche

Indice  pdf  ps

PARTE PRIMA : Richiami e argomenti preliminari
1. Il gruppo simmetrico  pdf  ps
2. Rappresentazioni di permutazione di un gruppo   pdf  ps
3. Richiami sui campi  pdf  ps
4. Campi di Galois  pdf  ps
5. Polinomi su campi di Galois  pdf  ps
6. Richiami di geometria proiettiva e affine su un campo  pdf  ps
7. Piani proiettivi e affini  pdf  ps

PARTE SECONDA : Elementi di geometria su campi di Galois
8. Archi e calotte di ordine massimo  pdf  ps
9. Blocking set  pdf  ps

PARTE TERZA : Elementi di teoria dei disegni
10. Generalità sui disegni  pdf  ps
11. Disegni simmetrici  pdf  ps
12. Estensioni di disegni  pdf  ps

PARTE QUARTA : Elementi di teoria dei codici lineari
13. Generalità sui codici   pdf  ps
14. Codici lineari  pdf  ps
15. Codici lineari e disegni  pdf  ps

Bibliografia  pdf  ps