PAGINA INIZIALE
pagine web di francesco mazzocca - seconda universitÓ degli studi di napoli - dipartimento di matematica e fisica - caserta
INFORMAZIONI STUDENTI

Dipartimento di Matematica e Fisica
Corso di Laurea in Matematica

Anno Accademico
2016/2017

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
secondo semestre
febbraio 2017

dal -- al --
---
---

giugno 2017

L'esame consta di una prova orale.  


calendario


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.
Alfabeti, parole e codici su un alfabeto. Prime definizioni: codici a blocchi e a lunghezza variabile, tasso di informazione. Primi esempi: il codice fiscale italiano, il codice ISBN, il codice MORSE, il codiche ASCII, il codice EAN, il (7,16)-codice binario di Hamming, il (4,9)-codice ternario di Hamming.
Composizione di parole.
Codici istantanei, disuguaglianza di Kraft, teorema e algoritmo di Kraft.
Teorema di McMillan. Codifica e decodifica. 
Schema di Shannon di un sistema di comunicazione. 
Sorgenti di informazione senza memoria: definizione, distribuzione di probabilitÓ. Codifica di una sorgente e sua  lunghezza media. Codifiche ottime. Compressione di dati e codifica binaria di Huffman. Informazione associata alle lettere e entropia di una sorgente senza memoria. Teorema di Shannon per la codifica delle sorgenti. 
Canali di trasmissione senza memoria: definizione, matrice di transizione, rumore, n-esima matrice. Canali simmetrici. Entropia, flusso medio di informazione e capacitÓ. 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. 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.ParkerS.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.

  1. F.Mazzocca, Appunti (lucidi) del corso, 2015, a disposizione degli interessati nella sezione materiale didattico di questo sito.
  2. L.Berardi, Algebra e teoria dei codici correttori, Collana di matematica e statistica, Franco Angeli Editore, 1994.
  3. L.Cauchi, V.La Terra, R.Grasso, F.Gullo, Appunti di Teoria dei Codici, FacoltÓ di Ingegneria, UniversitÓ di Catania, 2009.
  4. C.Fiori, Lezioni di Algebra e Teoria dei Codici, Dipartimento di Scienze Fisiche, Informatiche, Matematiche dell'UniversitÓ di Modena e Reggio Emilia, 2007.
  5. L.Giuzzi, Codici correttori, Collana UNITEXT, Springer, 2006.
  6. R.W.Hamming, Self-Correcting Codes, Case 20878, Memorandum 1130-RWH-MFW, Bell Telephone, 1947.
  7. R.W.Hamming, Error Detecting and Error Correcting Codes, The Bell System Technical Journal, April, 1950
  8. R.Hill., A First Course in Coding Theory, Oxford Applied Mathematics and Computing Science Series, Clarendon Press - Oxford, 1990.
  9. Y.Lindell, Introduction to Coding Theory, Lecture Notes, Department of Computer Science, Bar-Ilan University, Israel, 2010.
  10. F.Mazzocca, Codici e Geometria, Periodico di Matematiche, Vol.1 (2012), Pagg. 27-47.
  11. F.Mazzocca, Note di Geometria Combinatoria, Cromografica Roma S.r.l., Roma, per Gruppo Editoriale l'Espresso S.p.A., 2013.
  12. C.E.Shannon, A Mathematical Theory of Communication, The Bell System Technical Journal, Vol.27, pp.379-423  623-646 July, October, 1948.
  13. S.A. Vanstone, An Introduction to Error Correcting Codes with Applications, Kluwer Academic Press, 2001.