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

1. 26.09.16 (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. 29.09.16 (ore 3).
   Definizione di gruppo, anello, campo. Esempi. Teorema della divisione. Definizione della relazione di congruenza e relative proprieta', ogni intero e' congruo al suo resto modulo d; due interi sono congrui modulo d se e solo se hanno lo stesso resto quando divisi per d. 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.
3. 03.10.16 (ore 2).
   Definizione dell'anello, Z/nZ, delle classi di resto modulo n. Esempi. Z/nZ non e' un campo se n non e' 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). Definizione di massimo comun divisore tra due numeri interi.
4. 06.10.16 (ore 3).
   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.
5. 10.10.2016 (ore 2).
   Introduzione al teorema cinese del resto: Esempi di applicazione resto e sistemi di congruenze, esempi di sistemi di congruenze senza soluzioni.
   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) . Diamo una dimostrazione costruttiva dell'esistenza, descriviamo infatti una procedura, basata sull'algoritmo euclideo esteso, che determina una soluzione esplicita.
6. 13.10.2016 (ore 3).
   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 elementi 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).
   Algoritmo RSA in dettaglio.

   Per approfondimenti: Secret sharing.
   Twenty years of attacks on the RSA cryptosystem di Dan Boneh.
   

7. 17.10.2016 (ore 2).
   Introduzione ai numeri primi, numeri di Mersenne, primi gemelli. 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 p divide b. Teorema: ogni naturale non nullo si scompone univocamente (a meno dell'ordine) nel prodotto di numeri primi (s.d.); la funzione di Eulero di un naturale di cui e' nota la sua scomposizione in fattori primi.
   Introduzione alla teoria della complessita: la macchina di Turing. Per approfondimenti: 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
   . 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,
   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).
8. 20.10.2016 (ore 3).
   Cenno a due delle ipotesi principali alla base della teoria della complessita' computazionale: la Church-Turing thesis e la Cobham-Edmonds thesis.
   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.
   Per approfondimenti: 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.
9. 24.10.2016 (ore 2)
   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.

   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).
   

10. 27.10.2016 (3 ore)
    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'). L'insieme delle radici n-esime di 1 in C e' un gruppo moltiplicativo isomorfo al gruppo additivo Z/nZ.
    Definizione dei polinomi ciclotomici. Esempi.
11. 3.11.2016 (ore 3)
    Proprieta' dei polinomi ciclotomici.
    Parentesi su alcune nozioni fondamentali: Sia G un gruppo. Definizione di sottogruppo H di G. Lavoriamo con gruppi commutativi. Definzione di classe laterale e di insieme G/H delle classi laterali. 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.
    Consideriamo G commutativo come sara' sempre nel nostro contesto. Se H un sottogruppo di G, allora G/H e' 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.
    
12. 7.11.2016 (ore 3)
    CARATTERISTICA DI UN CAMPO: Dato un campo K esiste un'unico omomorfismo di anelli, k, 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 k(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 e dimostrazione del criterio per stabilire se un elemento di K e' radice n-esima primitiva in K. 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 >.
    
13. 10.11.2016 (ore 3)
    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.
    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. Esempio di campo con 8 elementi. Teorema di esistenza e unicita': dati un primo p e un intero n positivo esiste un campo F con pⁿ elementi. 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 tecnico di cui omettiamo la 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. Dimostrazione del lemma*. Dimostrazione dell'unicita'. Utilizziamo la definizione di ideale massimale in un anello e il seguente Lemma che dimostreremo nella prossima lezione: un quoziente A/I e' un campo se e solo se I e' massimale in A.
14. 14.11.2016 (ore 2)
    Dimostrazione della proposizione enunciata nella 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. Esempio di applicazione. Dimostrazione per assurdo. Un sottoprodotto della dimostrazione, come gia' mostrato con l'esempio svolto, 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. Questa seconda parte della dimostrazione e' stata solo delineata brevemente e non svolta.
15. 17.11.2016 (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 definizione 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.
16. 18.11.2016 (ore 2)
    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
    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).

    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).

17. 21.11.2016 (ore
    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. 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.
    
18. 24.11.2016 (ore 3)
    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. 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 esiste una permutazione generalizzata di F_qⁿ che ristretta a C concide con f, in particolare C e C' sono equivalenti. 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. 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.
19. 28.11.2016 (ore 2)
    Codici di Hamming: definizione del codice di Hamming Ham(r,q) (e' in realta' una classe di codici equivalenti). I parametri dei codici di Hamming. In particolare i codici di Hamming hanno distanza 3 e sono codici perfetti.
    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).
20. 01.12.2016 (3 ore)
    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. Su questa proposizione si basa la tabella delle sindromi (syndrome look-up table), costituita da due colonne e da q^n-k righe. La prima colonna coincide con la prima colonna della tabella standard, da' quindi una lista di capoclasse, con primo elemento 0. Ogni classe e' etichettata da una parola di F_q^n-k, precisamente, sfruttando la proposizione, a ogni capoclasse corrisponde, sulla colonna di destra, la sua sindrome. Anche qui indichiamo con asterisco le righe (classi) in cui non c'e' un'unica parola di peso minimo. Decodifica utilizzando la tabella delle sindromi.
    Proposizione: la sindrome e' iniettiva sulla palla chiusa di centro 0 e raggio e in F_qⁿ. Questo ci permette di comporre la tabella delle sindromi elencando per prime, nella colonna dei capoclasse, le parole di B_e(0). Per queste classi la decodifica non e' mai ambigua, non sono mai asteriscate.
    Introduzione ai problemi di ottimizzazione: bounds e bounds asintotici. Fissato $q$ e due dei tre parametri fondamentali si pone il problema di costruire un codice con i parametri fissati e tali che il terzo parametro sia estremale. Definiamo A_q(n,d) la taglia massima raggiungibile da un codice di lunghezza n e distanza d; Definiamo B_q(n,d) la taglia massima raggiungibile da un codice lineare di lunghezza n e distanza d.
    Si ha: B_q(n,d)≤ A_q(n,d)≤ qⁿ;
    B_q(n,1)≤ A_q(n,1)=qⁿ;
    B_q(n,n)≤ A_q(n,n)=q.
    Costruzione di codici a partire da codici assegnati, che parametri possiamo variare e come. Osservazione: con questi metodi non si migliorano i parametri dei codici. Proposizione: Sia C un codice lineare [n,k,d]_q (ricordiamo che k≤ n e d≤ n-k+1). Allora:
    (i) [costruzione per allungamento] per ogni r≥ 1 esiste un codice lineare [n+r,k,d]_q;
    (ii)[estrazione di un sottocodice]per ogni 1 ≤ r≤ k-1 esiste un sotto-codice lineare [n,k-r,d]_q di C;
    (iii)[puncturing] per ogni 1 ≤ r≤ d-1 esiste un sotto-codice lineare [n-r,k,d-r]_q di C;
    (iv) per ogni 1 ≤ r≤ d-1 esiste un codice lineare [n,k,d-r]_q di C;
    (v) per ogni 1 ≤ r≤ k-1 esiste un codice lineare [n-r,k-r,d]_q di C;
    (vi) siano C₁ e C₂ codici lineari con parametri rispettivamente [n₁,k₁,d₁]_q e [n₂,k₂,d₂]_q. Si definisce il codice C₁⊕C₂ con parametri [n₁+n₁,k₁+k₂,min{d₁,d₂}]_q.
    
21. 05.12.2016 (2 ore)
    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' contenuto (ricoperto) dall'unione delle palle chiuse di raggio d-1 centrate nelle parole del codice.
    Teorema costruttivo preliminare al bound di Gilbert-Varshamov (senza dim): 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.
    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.

    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. 12.12.2016 (ore 2)
    Codici ciclici: definizione e teorema di classificazione: i codici lineari ciclici in F_qⁿ sono in corrispondenza biunivoca con i divisori monici del polinomio xⁿ-1 in F_q[x]. Questo deriva dal fatto che i codici ciclici in F_qⁿ sono in corrispondenza biunivoca con gli ideali dell'anello F_qⁿ[x]/(xⁿ-1) e quindi con gli ideali di F_qⁿ[x] che contengono il polinomio xⁿ-1.
    Sia g di grado n-k in F_q[x] il polinomio generatore del codice ciclico C in F_qⁿ, allora la dimensione di C e' k. Matrice generatrice di un codice ciclico a partire dal polinomio generatore.
23. 15.12.2016 (ore 3)
    Esempi di codici ciclici. Esempio di codici ciclici in F_qⁿ equivalenti e generati da polinomi diversi.
    L'ortogonale di un codice ciclico e' ciclico. Sia C un codice ciclico in F_qⁿ con polinomio generatore g di grado (n-k). Si definisce il polinomio di controllo di parita' di C. Matrice di controllo di parita' di un codice ciclico. Per un codice ciclico e' sempre possibile determinare una matrice H di controllo di parita' della forma (I_n-k|A). Sia w in F_qⁿ, allora la sindrome S_H di w corrisponde al resto della divisione di w(x) per g(x). Si ha quindi che s e w, come elementi di F_qⁿ, appartengono alla stessa classe laterale in F_qⁿ/C e quindi, se wt(s) non supera la capacita' correttiva del codice, la decodifica di w a minima distanza e' w-s. Esempio.
    Questa osservazione porta a definire un algoritmo di decodifica per errori localizzati particolarmente efficiente, detto error trapping , che non abbiamo descritto a lezione.

    Approfondimenti: Un articolo utile sui codici ciclici: An introduction to linear and cyclic codes di D. Augot, E. Betti e E. Orsini.