Indico con s.d. i risultati enunciati senza dimostrazione.

1. 21.09.15 (ore 2).
   Introduzione al corso: informazioni pratiche; programma; motivazioni. Esempi: Sistema crittografico a chiave pubblica RSA-- prima descrizione introduttiva; Introduzione alla teoria dei codici autocorrettivi--distanza di Hamming e ridondanza.

   Per approfondimenti: algoritmo RSA e anche elliptic curve cryptography; elementary theory and practice of elliptic curves cryptography, the new generation of public key systems.
   Vedere anche la sezione 4.1 qui At risk - Public key encryption.
   

2. 22.09.15 (ore 3).
   Definizione di gruppo, anello, campo. Esempi. Teorema della divisione.
   Definizione della relazione di congruenza e relative proprietà: ogni intero è congruo al suo resto modulo n; due interi sono congrui modulo n se e solo se hanno lo stesso resto quando divisi per n. Somma e prodotto conservano la congruenza.L'importante identita' [xy]_d=[[x]_d[y]_d]_d con x,y numeri interi. Algoritmo dei quadrati ripetuti.
   Definizione dell'anello, Z/nZ, delle classi di resto modulo n. Esempi. Z/nZ non è un campo se n non è primo.
   Sia div(n) l'insieme dei divisori di un intero n. Nota: div(0)={0,1,2,3,...}=N. Lemma di Euclide (Euclide (300 a.C.): Siano m,n in Z. Allora esiste unico d in N tale che div(m) intersecato div(n) e' uguale a div(d). Massimo comun divisore tra due numeri interi: definizione e prime proprieta';
3. 28 Settembre 2015 (ore 2)
   Algoritmo di Euclide per il calcolo del massimo comun divisore.
   Proposizione: il massimo comun divisore di due interi a e b si puo' scrivere come combinazione lineare intera di a e b: algoritmo Euclideo esteso per la dimostrazione e il calcolo dei coefficienti della combinazione lineare.
   Proposizione: Due interi a e b sono co-primi se e solo esistono x e y interi tali che xa+yb=1.
   Proposizione: l'anello delle classi di resto Z/nZ e' un campo se e solo se n e' un numero primo.
   Proposizione: Se a divide bc e a e b sono primi tra loro, allora a divide c.
   Proposizioni: Se gcd(a,b)=1, a divide c e b divide c, allora ab divide c; Se gcd(a,b)=1 e gcd(a,c)=1 allora gcd(a,bc)=1.
   Introduzione al teorema cinese del resto.
4. 29 Settembre 2015 (ore 3)
   L'applicazione resto r da Z/nZ a Z/n₁Z x ... Z/n_rZ, con n=n₁...n_r e gcd(n_i,n_j)=1 è un isomorfismo di anelli, in particolare è biunivoca. Si osserva che questo e' equivalente all'esistenza e unicita della soluzione (modulo n) di un sistema di congruenze. Enunciato "classico" del Teorema cinese del resto (Sun-Tsu 280-473, Chin Chiu Shao 1247) . La dimostrazione dell'esistenza e' costruttiva, l'esistenza di una soluzione e' provata mediante una procedura, che determina una soluzione esplicita, basata sull'algoritmo euclideo esteso.
   Esempio di applicazione del teorema cinese del resto: caso molto semplice del "secret sharing scheme" dovuto ad A. Shamir.
   Definizione di (Z/nZ)^* come sottoinsieme di Z/nZ delle classi prime con n. (Z/nZ)^* e' un gruppo, il gruppo degli invertibili dell'anello Z/nZ. In particolare, come gia' dimostrato, Z/nZ e' un campo se e solo se n e' primo.
   Definizione della funzione φ di Eulero (1707-1783).
   Proposizione: Se n e m sono primi tra loro, allora φ(mn)=φ(m)φ(n).
   Teorema di Eulero: siano a,n interi, primi tra loro, n naturale. Allora a^φ(n)≡ 1(mod n).
   Prima parte della dimostrazione.

   Per approfondimenti: Secret sharing.
   

5. 5 Ottobre 2015 (2 ore)
   Seconda parte della dimostrazione. Introduzione ai numeri primi, numeri di Mersenne, primi genemelli, cenno ad alcuni problemi aperti.
   Definizione di numero primo; Lemma: ogni naturale non nullo e' prodotto di primi; Teorema (Euclide): ci sono infiniti numeri primi; Lemma: se un primo p divide il prodotto di due interi ab, allora o p divide a oppure o divide b. Teorema: ogni naturale non nullo si scompone univocamente (a meno dell'ordine) nel prodotto di numeri primi (s.d.); il calcolo della funzione di Eulero nota la scomposizione in fattori primi di un naturale.
   Algoritmo RSA in dettaglio.

   Per approfondimenti: Twenty years of attacks on the RSA cryptosystem di Dan Boneh.
   The largest known primes- a summary,
   Great internet Mersenne prime search,
   Risultato del 2013 sul primes gap, articolo divulgativo,
   Risultato del 2013 sul primes gap, articolo originale.

6. 6 Ottobre 2015 (3 ore)
   QUOZIENTI. Sia G un gruppo. Definizione di sottogruppo H di G, di classe laterale sinistra e di insieme G/H delle classi laterali sinistre. Indico con |G| il numero degli elementi di un gruppo finito.
   Proposizione: sia G un gruppo finito, allora |H| divide |G|.
   Sia g un elemento di un gruppo G. Definizione di ordine di g, ord(g). Proposizione: Sia G un gruppo finito, allora ord(g) divide |G|, g^|G|=e, se g^r=e, allora ord(g) divide r.
   Sia H un sottogruppo di G, se H soddisfa una particolare condizione (e' normale) allora G/H e' un gruppo. Se G e' commutativo ogni sottogruppo H e' normale e dunque il quoziente G/H e' sempre un gruppo con l'operazione naturale di composizione tra le classi indotta dalla composizione in G.
   Siano G e K due gruppi. Un'applicazione f da G a K e' un omomorfismo di gruppi se per ogni g,g' in G si ha f(gg')=f(g)f(g'). Il nucleo di un omomorfismo f e l'insieme degli elementi g in G tali che f(g)=e. Il nucleo di un omomorfismo e' un sottogruppo di G. L'omomorfismo f e' iniettivo se e solo se ker(f)={e}.
   Teorema: Siano G e K due gruppi e sia f un omomorfismo da G a K. Allora f induce una applicazione ben definita e iniettiva da G/Ker(f) in K che, composta con la proiezione naturale da G su G/Ker(f), da' f.
   Definizione di un ideale I di un anello A. Il quoziente A/I e' un anello. Sia f da A a B un omomorfismi di anelli. Allora Ker(f) e' un ideale di A. Traduciamo al caso degli anelli il teorema visto per i gruppi, ossia, sia f da A in B un omomorfismo di anelli, allora f induce un'applicazione ben definita e iniettiva da A/I in B che, composta con la proiezione naturale da A su A/I, da' f.
   Il protocollo per lo scambio di chiavi di Diffie-Hellmann. L'unico modo noto per risolvere il problema di Diffie-Hellman (DHP) e' attraverso il logaritmo discreto. Cenno alla definzione e al problema del logaritmo discreto (DLP). La sicurezza del protocollo Diffie-Hellman si basa sulla difficolta' computazionale del DPL, cosi' come la sicurezza dell'RSA si basa sulla difficolta' computazionale della fattorizzazione in primi. Cosa significa esattamente "difficolta' computazionale"? Cosa dignifica che due problemi sono equivalenti? Il primo mattone per la teoria della complessita': la macchina di Turing deterministica.

   Per approfondimenti: Gruppi ciclici finiti e il protocollo di scambio delle chiavi di Diffie e Hellman.
   Il sistema crittografico di El Gamal.
   A walk through combinatorics, Miklos Bona, sia la seconda che la terza edizione contengono i capitoli sulla teoria della complessita' e una descrizione chiara della macchina di Turing.
   Notes on Turing machine.
   

7. 12 Ottobre 2015 (ore 2)
   Introduzione alla teoria della complessita' computazionale. Descrizione dei problemi elencati dopo la definizione di linguaggio. Definizione: Un linguaggio L e' l'insieme di tutti gli oggetti per cui la risposta a un dato problema decisionale e' si'.
   Esempi: L_Pr=insieme dei numeri primi
   L_EC=insieme dei grafi connessi che ammettono un circuito Euleriano
   L_HC=insieme dei grafi connessi che ammettono un circuito Hamiltoniano
   L_TSP=insieme di coppie (G,B) con G grafo connesso pesato e B numero positivo tali che G ammette un circuito Hamiltoniano con costo inferiore a B
   L_SAT=insieme delle formule Booleane AND of OR's soddisfacibili
   Definizione delle seguenti nozioni: una macchina di Turing T accetta un linguaggio L; un linguaggio L appartiene alla classe di complessita' computazionale P; un linguaggio L appartiene alla classe di complessita' computazionale NP, comprendente la nozione di testimone o certificato. Brevemente P e' la classe dei linguaggi per cui, per ogni input, l'appartenenza o meno al linguaggio puo' essere decisa in tempo polinomiale nella taglia dell'input. NP e' la classe dei linguaggi per cui, per ogni input nel linguaggio, la prova di appartenenza puo' essere verificata in tempo polinomiale nella taglia dell'input.
   Cenno a due delle ipotesi principali alla base della teoria della complessita' computazionale: la Church-Turing thesis e la Cobham-Edmonds thesis.
   Per approfondimenti: L'articolo originale in cui Turing introdusse la macchina di Turing On computable numbers, with an application to the Entscheidungsproblem A. Turing, Proceedings of the London Mathematical Society, (Ser. 2, Vol. 42, 1937), e, ancora, Turing and the development of computational complexity di S. Homer e A. Selman (2011), dove vengono illustrate anche le ipotesi di cui sopra.
   Definizione di formula Booleana AND of OR's.
   Il materiale utilizzato per l'introduzione alla teoria della complessita' comprende anche la: Conferenza di Vijaya Ramachandran: P vs NP problem, tenuta al Clay Mathematics Institute, molto chiara, e i capitoli 17 e 18 del libro A walk through combinatorics, Miklos Bona citato anche nella scorsa lezione.
   Per la teoria dei grafi vedere, ad esempio: Corso di teoria dei grafi, Carlo Casolo e il libro di Bona succitato.
8. 13 Ottobre (3 ore)
   Dati due linguaggi L ed L' definiamo quando L e' riconducibile ad L', L≤_pL'. Definizione di NP completezza.
   Teorema (Cook, 1961): L_SAT e' NP completo. Proposizione: Se L e' NP completo e L≤_pL', allora L' e' NP completo. Ad ora si conoscono migliaia di linguaggi NP completi.
   Altri esempi di linguaggi NP completi: L_HC e L_TSP.
   P=NP se e solo se un linguaggio NP completo e' in P (segue dalla definizione di NP completezza). Definizione di linguaggio NP-hard.
   Esempi di estensione di campi: costruzione del campo dei numeri complessi C come campo quoziente dell'anello dei polinomi a coefficienti in R, modulo l'ideale generato dal polinomio irriducibile x²+1. Costruzione di un campo con 4 elementi come campo quoziente dell'anello dei polinomi a coefficienti in F₂[x], modulo l'ideale generato dal polinomio irriducibile x²+x+1: elementi e tabelle additive e moltiplicative.
   POLINOMI: L'anello dei polinomi, A[x], nell'indeterminata x a coefficienti in un anello A. Grado di un polinomio. Siano f,g sono in K[x], allora deg(fg)=def(f)+deg(g). Gli elementi invertibili di K[x] sono tutti e soli i polinomi costanti non nulli.
   Teorema della divisione:Sia d un polinomio a coefficienti in un anello A, diverso da 0 e tale che il coefficiente del monomio di grado massimo e' invertibile. Allora, dato f in A[x], esistono unici q e r in A[x] tali che f=qd+r, con deg(r)< deg(d) o r=0.
   Definizione di radice di un polinomio. Denotiamo con V(p) l'insieme delle radici del polinomio p. Un elemento a in K e' una radice del polinomio p se e solo se (x-a) divide p. Definizione di molteplicita', ν_a(p) di una radice a del polinomio p. Si ha V(fg)=V(f)UV(g). Teorema: Sia F in K[x]. Se V(f)={a₁,...,a_r} allora f=q(x-a₁)^ν_a1(p)...(x-a_r)^ν_ar(p), con q in K[x] e V(q) vuoto. Inoltre ν_a1+...+ν_ar≤deg(f).
   Derivata di un polinomio e sue proprietà .
   Lemma: Siano f,g due polinomi in K[x]. Se f² divide g, allora f divide Dg; l'elemento a in K e' una radice del polinomio f con molteplicità maggiore di 1 se e solo se e' una radice di f e di Df.
   Radici n-esime di 1 nel campo dei complessi C: definizione, radici n-esime primitive di 1 in C (caratterizzazione e proprieta').

   Per approfondimenti: M. Agrawal, N. Kayal, N. Saxena, Primes is in P, Annals of Mathematics, 160 (2004) 781-793: We present an unconditional deterministic polynomial-time algorithm that determines whether an input number is prime or composite. Un articolo molto bello sul risultato precedente, di A. Graville, sul Bull. of AMS. Per la teoria della complessita' vedere anche ad esempio: il libro Computational Complexity: A Modern Approach Sanjeev Arora and Boaz Barak, Cambridge University Press. E, in relazione con l'RSA, l'articolo Complexity theory and the RSA cryptosystem J. Garlapati. Il certificato di Pratt. Gli articoli originali di Cook e Levine (indipendenti) sulla NP-completezza di SAT: S. Cook, The complexity of theorem proving procedures, Proceedings of the Third Annual ACM Symposium on Theory of Computing, (1971) pp. 151-158. L. Levin, Universal search problems (in russo), Problems of Information Transmission, 9 (3): (1973) 115-116, translated into English by Trakhtenbrot, B. A. A survey of Russian approaches to perebor (brute-force searches) algorithms, Annals of the History of Computing 6 (4) (1984).
   

9. 19 Ottobre 2015 (ore 2)
   L'insieme delle radici n-esime di 1 in C e' un gruppo moltiplicativo isomorfo al gruppo additivo Z/nZ.
   Definizione e proprieta' dei polinomi ciclotomici. Esempi. CARATTERISTICA DI UN CAMPO:
   Dato un campo K esiste un'unico omomorfismo di anelli, f, dall'anello degli interi Z a K. Quindi ha senso vedere gli interi come elementi di un campo qualunque K. Sia n in Z, quando scriviamo n in K intendiamo l'elemento f(n) in K. L'ordine di 1 in (K,+) e' un'invariante fondamentale del campo K, detto caratteristica. Se 1 ha ordine infinito diciamo che char(K)=0. Se ord(1)=n finito allora char(K)=n. Quando la caratteristica e' finita possiamo pensarla come il piu' piccolo intero positivo tale che 1+1+...+1(n volte)=0. Esempi: Char(Q)=0, Char(R)=0, Char(C)=0, Char(F_p)=p, Char(F₂/2+x+1>)=2. Proposizione: Sia K un campo tale che Char(K)=n. Allora c'e' un omorfismo iniettivo di Z/nZ in K. In particolare n e' primo. Quindi riepilogando la caratteristica di un campo e' zero oppure un numero primo. Se e' zero l'omomorfismo f e' iniettivo epossiamo pensare a Z come a un sottoanello del campo K, se e' p allora Ker(f)=pZ e possiamo pensare a F_p come a un sottocampo di K.
   Osserviamo che i polinomi ciclotomici, essendo a coefficienti interi, possono essere considerati in K[x] per ogni campo K. Esempio: phi₃=x²+x+1 in C ha per radici le due radici terze primitive di 1, in R e' irriducibile, in F₂ e' irriducibile, in F₃ ha una sola radice doppia x²+x+1=x²-2x+1=(x-1)², in F₄ ha due radici, entrambe radici terze (primitive) di 1. Definizione di radice n-esima primitiva in un campo K. Proprieta'. Enunciato del criterio per stabilire se un elemento di K e' radice n-esima primitiva in K.
10. 20 Ottobre 2015 (ore 3)
    Dimostrazione del criterio enunciato nella lezione precedente.
    Definizione di gruppo ciclico.
    Teorema di Gauss: un sottogruppo G finito del gruppo moltiplicativo di un campo K e' ciclico. Dimostrazione: si utilizza il criterio appena dimostrato.
    Definizione di polinomio irriducibile.
    Proposizione: Se f in K[x] ha grado 1 allora e' irriducibile.
    se f e' irriducibile in K[x] e grado di f >1 allora f non ha radici
    se f ha grado 2 o 3 e non ha radici in K allora e' irriducibile in K[x]
    Definizione degli anelli quozienti F_p[x]/< f >.
    F_p[x]/< f > e' un campo se e solo se f e' irriducibile in F_p[x].
    F_p e' un sottocampo di L:=F_p[x]/< f >
    Il polinomio f e' in F_p[x] e quindi in L[x]. L'elemento [x] in L e' una radice di f. Quindi abbiamo costruito una estensione di F_p a un campo L che contiene una radice del polinomio f, irriducibile in F_p[x].
    Il campo L= F_p[x]/< f > ha pⁿ elementi.
    Proposizione: Dato un campo K, l'anello K[x] e' un anello a ideali princincipali.
    Applicazione: il massimo comun divisore tra due polinomi g e h in K[x] e' il generatore monico dell'ideale I={ag+bh | a,b in K[x]}.
    Esempio di costruzione di un campo con 9 elementi e di operazioni tra elementi del campo.
    Proposizione: Sia F un campo finito. Allora esistono un numero primo p e un polinomio irriducibile in F_p[x] tali che F e' isomorfo a F_p[x]/< f >. Corollario: Un campo finito F ha cardinalita' uguale alla potenza di un primo. Questo primo e' la caratteristica del campo.
    
11. 26 ottobre 2015 (ore 2)
    Riepilogo della lezione precedente. Esempio di campo con cardinalita' 8. Teorema di esistenza e unicita': dati un primo p e un intero n positivo esiste un campo F di cardinalita' pⁿ. Il campo F e' unico a meno di isomorfismi. Se q=pⁿ denotiamo con F_q tale campo. Dimostriamo prima l'esistenza. Lemma: sia f un fattore irriducibile in F_p[x] del polinomio ciclotomico phi_pⁿ-1, allora il grado di f e' uguale a n. Questo Lemma implica la parte di esistenza del teorema. Dimostriamo il Lemma, occorre un Lemma ulteriore di semplice dimostrazione: siano r,s,t naturali con r>1, allora r^s-1 divide r^t-1 se e solo se s divide t.
12. 27 ottobre 2015 (ore 3)
    Definizione di ideale massimale in un anello. Lemma: un quoziente A/I e' un campo se e solo se I e' massimale in A. Si dimostra solo A/I campo inmplica I massimale. Dimostrazione della parte di unicita' del teorema. Osservazione: dalla dimostrazione e' facile dedurre che ogni polinomio di grado n irriducibile in F_p ha n radici in F_pⁿ. Esempi. Teorema: il polinomio X^pn-X in F_p e' il prodotto DEI polinomi irriducibili in F_p di grado d che divide n. Esempi. Contare i polinomi irriducibili in F_p di grado assegnato. Dimostrazione del teorema. Esercizio di introduzione all'algoritmo di Berlekamp per la fattorizzazione di polinomi.
13. 2 novembre 2015 (ore 2)
    Seconda parte dell'esercizio iniziato la lezione precedente. Dimostrazione del seguente teorema: sia f un polinomio in F_p[x], sia R l'anello F_p[x]/< f > e sia F : R ---> R la mappa di Frobenius, cosi' definita f(v)=v^p. Si consideri R come spazio vettoriale su F_p. Allora
    1) F e' lineare 2) f e' irriducibile in F_p[x] se e solo se Ker(F)={0} e Ker(F-I)=F_p.
    Dimostrazione: parte I: se f e' irriducibile allora Ker(F)={0} e Ker(F-I)=F_p. Si dimostra per assurdo e un sottoprodotto della dimostrazione e' proprio l'algoritmo di Berlekamp per la fattorizzazione di polinomi in F_p[x].
    Parte II: se Ker(F)={0} e Ker(F-I)=F_p allora f e' irriducibile in F_p[x]. Sappiamo che f irriducibile in F_p se e solo se R e' un campo, quindi dimostriamo, essenzialmente con strumenti di algebra lineare che R e' un campo.
14. 3 novembre 2015 (ore 3)
    Teoria dei codici: definizioni preliminari: alfabeto di taglia/cardinalita' q, parola q-aria, codice q-ario di lunghezza n, taglia o cardinalita' M di un codice, codici di tipo (n,M)_q, information rate di un codice. Canale di comunicazione: e' dato da un alfabeto (diamo la definzione con lo stesso alfabeto in entrata e in uscita) e da una matrice di probabilita' di trasmissione in avanti. Canale senza memoria. Canale simmetrico. Canale fortemente simmetrico. BSC=binary simmetric channel.
    Distanza di Hamming, definizione e proprieta'. Criterio di decodifica a minima distanza (DMD). Proposizione: Per un canale senza memoria e fortemente simmetrico le decodifiche a massima probabilita' e minima distanza coincidono. Distanza di Hamming di un codice. Distanza d(x,C) di una parola w in Aⁿ da un codice C. Definizione di sfera aperta e chiusa di centro x e raggio s, denotate (in questo registro) rispettivamente con B_s(x) e B_s(x).
    Un codice C segnala al piu' s errori in DMD se per ogni x in C B_s(x)∩C={x}.
    Teorema: un codice C segnala al piu' s errori se e solo se d(C)≥s+1

    Per approfondimenti: "probably no single work in this century has more profoundly altered man's understanding of communication than Shannon's 1948 paper A mathemathical theory of communication" (David Slepian (editor) in Key papers in the Development of Information Theory, IEEE Press, NY, 1974).

15. 9 Novembre 2015 (ore 2)
    Un codice corregge al piu' s errori se per ogni parola w in Aⁿ tale che d(w,C) minore o uguale a s si ha che esiste un'unica parola c in C tale che w appartiene a B_s(c). Spieghiamo perche' questa definizione e' corretta. Teorema: un codice C corregge al piu' s errori se e solo se d(C)≥2s+1. Lemma: sia C un codice. Allora d(C)≥2s+1 se e solo se per ogni c e c' in C, con c diversa da c', si ha B_s(c)∩B_s(c')=vuoto. Indichiamo con (n,M,d)_q un codice q-ario di lunghezza n, taglia M e distanza d. Il codice C segnala al piu' d-1 errori e corregge al piu' e=[d-1/2] errori ([]=parte intera inferiore). Fissato q, i parametri n,M,d sono parametri essenziali per il codice. Problema di ottimizzazione: fissati n e d qual e' la taglia massima Max tale che se M'> Max non esiste un codice (n,M',d)?
    Teorema di Hamming: limitazione superiore per la taglia M di un codice in funzione di n,d,q. Lemma: numero di parole in una palla chiusa di raggio r.
16. 10 novembre 2015 (ore 3)
    Dimostrazione del teorema di Hamming. Definizione di codice perfetto.
    Codici lineari. Definizione: un codice lineare e' un sottospazio vettoriale di F_qⁿ (q=p^r con p primo). Esempi. Prodotto scalare in F_qⁿ. Definizione di ortogonale di C. Proprieta'. Definizione di matrice generatrice G e matrice di controllo di parita' H di un codice lineare: sia dim(C)=k, allora G e' una matrice le cui righe costituiscono una base di C (dunque rango(G)=k), mentre H e' una matrice le cui righe costituiscono una base dell'ortogonale di C (dunque rango(H)=n-k).
    Proposizione: x in F_qⁿ appartiene a C se e solo se Hx^t=0; x in F_qⁿ appartiene all'ortogonale di C se e solo se Gx^t=0; una matrice H' M_(n-k),n(F_q) di rango n-k e' una matrice di controllo di parita' di C se e solo se G(H')^t=0; una matrice G' M_k,n(F_q) di rango k e' una matrice generatrice di C se e solo se H(G')^t=0.
    Peso di Hamming di una parola x in F_qⁿ, denotato con wt(x). Peso di Hamming, wt(C), di un codice C. Proposizione: per un codice lineare C si ha d(C)=wt(C).
    Calcolo della distanza mediante la matrice di controllo di parita' H. Proposizione: sia C un codice lineare e sia H una sua matrice di controllo di parita'. Allora si ha:
    1) d(C) maggiore o uguale a l se e solo se ogni (l-1) colonne di H sono linearmente indipendenti.
    2) d(C) minore o uguale a l se e solo se esistono l colonne di H linearmente dipendenti
    3) d(C)=l se e solo se ogni (l-1) colonne di H sono linearmente indipendenti ed esistono l colonne di H linearmente dipendenti.
    Esempio.
    Codici equivalenti. Definizione di GP(n,F_q): gruppo delle permutazioni generalizzate. Proposizione: il gruppo delle permutazioni generalizzate coincide con il sottogruppo degli isomorfismi di F_qⁿ che conservano il peso.
17. 16 novembre 2015 (2 ore)
    Definizione: due codici lineari C e C' in F_qⁿ si dicono equivalenti se esiste f: F_qⁿ ---> F_qⁿ in GP(n,F_q) tale che f(C)=C'.
    Teorema (Florence MacWlliams) Siano C e C' due codici linearin in F_qⁿ, se C e C' sono isometrici, ossia, se esiste f:C--->C' isomorfismo che conserva la distanza, allora C e C' sono equivalenti, ossia f estende a un'isometria di F_qⁿ. S.D. Per una dimostrazione vedi qui, il pdf e' disponibile.
    Proposizione: due codici equivalenti hanno lo stesso peso e la stessa distanza.
    Osservazione: sia G la matrice generatrice di un codice C, le seguenti operazioni sulle righe di G producono una nuova matrice generatrice di C: scambiare due righe tra loro, moltiplicare una riga per uno scalare diverso da zero, sostituire una riga con la riga stessa sommata a una combinazione lineare delle altre. Invece permutare le colonne o moltiplicare una colonna per uno scalare produce una matrice G' che definisce, come matrice generatrice, un codice C' equivalente a C.
    Codici di Hamming: definizione del codice di Hamming Ham(r,q) (e' in realta' un'insieme di codici equivalenti). I parametri dei codici di Hamming. in particolare i codici di Hamming hanno distanza 3 e sono codici perfetti.
    
18. 17 Novembre 2015 (ore 3)
    La matrice generatrice G di un codice si dice in forma standard se G=(I_k|X)
    Teorema: ogni codice lineare C e' equivalente a un codice C' che ha una matrice generatrice in forma standard. Dim: applicare la riduzione di Gauss ("per ogni riga all'avanti e all'indietro") e poi eventualmente operare sulle colonne come descritto sopra.
    Proposizione: Sia G=(I_k|X) matrice generatrice di un codice C in forma standard, allora la matrice H=(-X^t|I_n-k) e' una matrice di controllo di parita' per C.
    Processo di codifica per un codice lineare. Message digits, check digits. Processo di decodifica a minima distanza (DMD) per un codice lineare. Sia C un codice lineare in F_qⁿ di dimensione k. Si considera lo spazio vettoriale quoziente F_qⁿ/C. Tale spazio ha dimensione n-k e ha dunque q^n-k elementi, ognuno di questi e', come sappiamo, una classe laterale (coset).
    Sia w la parola ricevuta. Nella decodifica a minima distanza cerco c in C che minimizza d(w,c). Poiche' d(w,c)=wt(w-c), cerco la parola w-c, con c in C, di peso minimo. Osservazione importante: w-c appartiene alla stessa classe di w. Dunque cerco la parola nella classe di w, ossia in w+C, di peso minimo.
    Siamo quindi interessati a individuare, in ogni classe, le parole di peso minimo. In ogni classe prendiamo LA (o una, se ce n'e' piu' d'una) parola di peso minimo, questa e' per definizione il capoclasse (coset leader) della classe. La tabella standard (standard array) e' costituita in questo modo: la prima colonna, a_i1, di q^n-k elementi, da' la lista dei capoclasse, con a₁₁=0. Per ogni coset leader la riga corrispondente da' la lista degli elementi della classe, ossia fissato i, per ogni j, a_ij=a_1j+a_i1. Si segnalano con un asterisco le classi che hanno piu' di un elemento minimo. Il procedimento di decodifica a minima distanza e' il seguente: ricevo w. Controllo la tabella e individuo il capoclasse err(w) corrispondente a w. Decodifico con c=w-err(w), che e' la prima parola della colonna di w. Se w appartiene a una riga asteriscata o richiedo la trasmissione (decodifica incompleta) e procedo come sopra (decodifica completa).
    Decodifica a sindrome. Sia C un codice lineare [n,k,d]_q, con matrice generatrice G e matrice di controllo di parita' H. Definiamo l'applicazione lineare S_H:F_qⁿ--->F_q^n-k come S_H(w)=(Hw^t)^t. La parola S_H(w) si dice sindrome di w. L'applicazione lineare S_H e' suriettiva, il suo nucleo e' C. Proposizione: L'applicazione S_H induce un'isomorfismo da F_qⁿ/C in F_q^n-k. Dim: immediata utilizzando quanto fatto in precedenza. Costruiamo una tabella detta tabella delle sindromi (syndrome look-up table) nel modo seguente: la prima colonna coincide con la prima colonna della tabella standard, da' quindi una lista di capoclasse, con primo elemento 0. La seconda colonna associa ad ogni capoclasse u la sua sindrome S_H(u). Anche qui indichiamo con asterisco le righe (classi) in cui non c'e' un'unica parola di peso minimo.
19. 23 Novembre 2015 (ore 2)
    Composizione della tabella delle sindromi elencando per prime, nella colonna dei capoclasse, le parole di B_e(0). Infatti la sindrome S_H e' biunivoca sulla palla B_e(0) e dunque le parole nella palla sono capoclasse delle rispettive classi. Esempio. Esempio di decodifica a sindrome per i codici di Hamming, in particolare per Ham(2,3).
    Bounds: definizione di A(n,d)_q e di B(n,d)_q. Enunciato del bound di Singleton e bound di Singleton per codici lineari [n,k,d]_q: k minore o uguale a n-d+1.
20. 24 Novembre 2015 (ore 3)
    Dimostrazione del bound di Singleton (upper bound). Sphere covering bound (lower bound). La dimostrazione e' dello stesso tipo di quella del bound di Hamming (upper bound): per quello di Hamming si ha che l'unione (disgiunta) di palle chiuse di raggio e centrate nelle parole del codice e' contenuta dello spazio totale, per lo sphere covering bound lo spazio totale e' contentuto (ricoperto) dall'unione delle palle chiuse di raggio d-1 centrate nelle parole del codice.
    Teorema costruttivo preliminare al bound di Gilbert-Varshamov: se i parametri k,n,d soddisfano una opportuna condizione, allora esiste un codice lineare [n,k,d'] con d' maggiore o uguale a d.
21. 29 Novembre 2015 (ore 2)
    Bounds: Riepilogo della lezione precedente (Hamming bound (upper bound) e sphere packing bound (lower bound)). Riepilogo della dimostrazione del Teorema spiegata alla lezione precedente.
    Lemma sul logaritmo.
    Corollario [Gilbert-Varshamov lower bound]: Fissato q, per d,n tali che 2 ≤ d ≤ n si ha;
    B_q(n,d)≥ q^{n-⌈ log_q( Vn-1_q(d-2)+1)⌉} ≥ q^n-1/ V^n-1_q(d-2).
    Introduzione ai bounds asintotici.
    Versione asintotica del bound di Gilbert-Varshamov, cenno ai risultati di Goppa e Tfsasman-Vladut-Zink.
    Codici ciclici: definizione ed enunciato del teorema di classificazione.

    Approfondimenti: l'introduzione del seguente articolo di M. Cheraghchi, A. Shokrollahi, A. Wigderson presenta in modo preciso ed estremamente chiaro i bounds e cosa significa costruire codici con parametri estremali, anche per bounds asintotici: Computational Hardness and Explicit Constructions of Error Correcting Codes .
    Nelle seguenti note di Y. Lindell si trova il passaggio dal bound di Gilbert-Varshamov alla sua versione asintotica, con notazioni compatibili con quelle del libro di testo.
    In questa pagina si trova l'aggioramento continuo dei bounds sui parametri di vari tipi di codici, la pagina e' esaustiva.
    Note sintetiche su quanto trattato in questa lezione e nella precedente.
    

22. 1 dicembre (ore 3)
    Dimostrazione del teorema di classificazione dei codici ciclici: i codici ciclici in F_qⁿ sono in corrispondenza biunivoca con i divisori monici di xⁿ-1 in F_q[x].
    Dal polinomio generatore g, divisore monico di xⁿ-1 di grado n-k, alla matrice generatrice G del codice ciclico corrispondente, di dimensione k.
    Esempi. Codici corrispondenti a polinomi distinti possono essere equivalenti. Dal polinomio generatore g alla matrice di controllo di parita' H del tipo (I_n-k|A).
    Esempi.
23. 14 Dicembre 2015 (2 ore)
    Riepilogo sui codici ciclici. Decodifica di codici ciclici:con la matrice di controllo di parita' H del tipo (I_n-k|A), la sindrome di una parola w coincide con il resto della divisione del corrispondente polinomio w(x) per g(x). Calcolo della sindrome di shifts successivi di w. Algoritmo di decodifica error trapping corregge errori con sequenze cicliche di zeri sufficientemente lunghe e peso inferiore alla capacita' correttiva del codice. Dimostrazione dell'algoritmo di decodifica error trapping ed esempio.
    Cenno all'algoritmo di decodifica per la correzione di errori di tipo burst, perfettamente analogo al precedente.
    Codici di Reed-Solomon: definizione come codici ciclici, calcolo della distanza. Esercizi sui codici ciclici e sull'error trapping decoding.