ITALIANO

Introduzione ai campi di Galois e agli spazi vettoriali su tali campi. Introduzione ai sistemi di comunicazione e alla teoria dei codici. Codici lineari. Codici lineari associati a piani finiti.

MATERIALE DIDATTICO
- F.Mazzocca, LUCIDI DEL CORSO, Dipartimento di Matematica e Fisica, Università della Campania “L.Vanvitelli”.
( http://www.francesco.mazzocca.name/CodiciLineari.pdf )
- F.Mazzocca, LUCIDI DEL SEMINARIO “INTRODUZIONE ALLA CRITTOGRAFIA”, Dipartimento di Matematica e Fisica, Università della Campania “L.Vanvitelli”.
( http://www.francesco.mazzocca.name/Crittografia.pptx )


LETTURE CONSIGLIATE
- W.M. Baldoni, Ciro Ciliberto, Giulia Maria Piacentini Cattaneo, ARITMETICA, CRITTOGRAFIA E CODICI, Springer, 2009.
- Luigia Berardi, ALGEBRA E TEORIA DEI CODICI CORRETTORI, Collana di matematica e statistica, Franco Angeli Editore, 1994.
- Luca Giuzzi, CODICI CORRETTORI, Collana UNITEXT, Springer, 2006.
- Raimond Hill, A FIRST COURSE IN CODING THEORY, Oxford Applied Mathematics and Computing Science Series, Clarendon Press - Oxford, 1990.

Conoscenza e capacità di comprensione:
Scopo del corso è quello di presentare alcune tecniche di base, a carattere algebrico-geometrico, fondamentali per la teoria dei codici (e la crittografia), nonché esempi concreti del loro effettivo utilizzo. Tra l’altro, si descriveranno in dettaglio alcuni tra i più noti e utilizzati tipi di codici (ASCII, ISBN, EAN, di Hamming, di Golay, MDS, ciclici, BCH,...), importanti sia dal punto di vista teorico che delle applicazioni, enucleandone pregi e limitazioni. Nella pratica le tecniche che si descriveranno sono utilizzate per l’implementazione di alcune tipologie di codifica di sorgente (codici correttori a blocchi). Il loro studio, tradizionalmente legato alla trasmissione numerica dell’informazione, riveste un crescente interesse anche nell’ambito dei sistemi software per l’immagazzinamento di dati in memorie intrinsecamente inaffidabili (ad esempio, quelle a stato solido). Si illustreranno anche applicazioni della teoria dei codici lineari alla crittografia. Uno dei punti centrali del corso sarà lo studio delle principali interconnessioni tra la teoria dei codici lineari e quella delle geometrie su campi di Galois.
Capacità di applicare conoscenza e comprensione:
Il corso si propone di rendere lo studente capace di assimilare le conoscenze acquisite e di saperle utilizzare per studiare e risolvere problemi teorici e concreti nell’ambito della codifica e decodifica dell’informazione e della crittografia e nell’ambito di altri settori della matematica combinatoria (in particolare, geometrie su campi di Galois).

Superamento degli esami dei seguenti corsi: Geometria 1, Algebra 1.

64 ore di lezioni frontali in aula.

La verifica e la valutazione del livello di conoscenza da parte dello studente avviene attraverso un esame finale orale sugli argomenti riportati nel programma del corso.

Abilità comunicative:
Il corso intende favorire le capacità dello studente ad esporre in modo chiaro e rigoroso le conoscenze acquisite e a saper comporre relazioni scritte in modo corretto, chiaro e, se necessario, conciso.
Autonomia di giudizio:
Gli studenti sono guidati ad apprendere in maniera critica e responsabile e ad arricchire le proprie capacità di giudizio attraverso opportuni riferimenti bibliografici, programmi di computer algebra e siti web suggeriti dal docente.

Capacità di apprendere: L’impostazione del corso intende fornire agli studenti gli strumenti metodologici e le capacità di apprendimento per poter proseguire con successo gli studi nell’ambito della teoria dei codici e, più in generale, delle teorie (matematiche e non) ad essa collegate.

SISTEMI DI COMUNICAZIONE. 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. Alcuni codici di Hamming.
Schema di Shannon di un sistema di comunicazione. Sorgenti di informazione senza memoria: definizione, distribuzione di probabilità , entropia, esempi. Compressione di dati: algoritmo di Huffman e algoritmo di Shannon-Fano. Codici istantanei e disuguaglianza di Kraft. Codifica di sorgente e relativo teorema di Shannon.
Canali di trasmissione senza memoria: definizione, matrice di transizione, rumore, 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.
GENERALITA’ SUI CODICI. (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. 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. 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. Calcolo di Aq(4,3).
CODICI LINEARI. Richiami sui campi finiti. Prime definizioni, proprietà ed esempi relativi ai codici lineari.. 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 alla 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 (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 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. Numero dei codici ciclici. Ciclicità dei codici binari di Hamming.
Codici BCH binari 2-correttori. Introduzione alla crittografia. Crittografia asimmetrica e algoritmo RSA. Il crittosistema di McEliece.
CODICI LINEARI E PIANI FINITI. 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.

Italian

Introduction to Galois fields and vector spaces over these fields. Introduction to communication systems and coding theory. Linear codes. Linear codes associated with finite planes.

TEACHING MATERIALS
- F.Mazzocca, SLIDES OF THE COURSE, Dipartimento di Matematica e Fisica, Università della Campania “L.Vanvitelli”.
(http://www.francesco.mazzocca.name/CodiciLineari.pdf )
- F.Mazzocca, SLIDES OF THE SEMINAR “INTRODUZIONE ALLA CRITTOGRAFIA”, Dipartimento di Matematica e Fisica, Università della Campania “L.Vanvitelli”.
( http://www.francesco.mazzocca.name/Crittografia.pptx )


MORE READINGS
- W.M. Baldoni, Ciro Ciliberto, Giulia Maria Piacentini Cattaneo, ARITMETICA, CRITTOGRAFIA E CODICI, Springer, 2009.
- Luigia Berardi, ALGEBRA E TEORIA DEI CODICI CORRETTORI, Collana di matematica e statistica, Franco Angeli Editore, 1994.
- Luca Giuzzi, CODICI CORRETTORI, Collana UNITEXT, Springer, 2006.
- Raimond Hill, A FIRST COURSE IN CODING THEORY, Oxford Applied Mathematics and Computing Science Series, Clarendon Press - Oxford, 1990.

Pass the exams of the following courses: Geometry 1, Algebra 1.

64 hours of classroom lectures.

An oral final exam on the topics in the course program.

COMMUNICATION SYSTEMS. Introduction to transmission of information. Codes and first examples. Shannon scheme of a communication system. Memoryless information sources. Data compression. Source coding and related Shannon theorem. Memoryless transmission channels. Symmetric channels. Channel coding and related Shannon theorem.
CODES. q-Ary (n,m)-codes. Hamming distance. Singleton inequality and MDS codes. e- Correcting codes. Hamming inequality and perfect codes. The fundamental problem of the coding theory and the function Aq(n,d). Minimum distance decoding algorithms. Equivalence of codes. Latin squares and the function Aq(4,3).
LINEAR CODES. Basic definitions, properties and examples. The binary Golay code. Equivalence of linear codes. Dual codes.. Extended codes. Encoding and decoding with a standard tableau. Syndromes and syndrome decoding. The fundamental relationship between minimum distance and check matrices of a linear code. Packing problem in finite vector spaces, fundamental problem of the theory of linear codes and equivalence of the two problems. The function maxd-1(m, q). Construction and properties of Hamming codes. Fast decoding of Hamming binary codes. The functions max3(m,2) and max3(3, q). Basics of finite fields. Cyclic codes: definition, examples, characterization, generator and check polynomials. 2-corrector BCH binary codes and their decoding. Introduction to asymmetric cryptography. The cryptosistem of McEliece.
LINEAR CODES AND FINITE PLANES. Finite projective planes. Linear binary code associated with a finite projective plane and its first properties. Properties of the binary code associated with a finite projective plane of order n=2(mod 4). The non-existence of the projective plane of order 10.