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

1. 22.09.14 (ore 2).
   Introduzione al corso: informazioni pratiche, modalita' d'esame, programma, motivazioni, testi di riferimento.
   Introduzione al sistema crittografico RSA-- sistema di crittografia a chiave pubblica--per la trasmissione di dati. Essenzialmente le chiavi pubbliche sono un numero naturale N (prodotto di due numeri primi molto grandi) e un numero naturale e scelto opportunamente; la chiave privata e' un altro numero d, segreto, che si utilizza per la decrittazione.
   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.
   Numeri naturali, numeri interi, definizione di gruppo, gruppo commutativo, anello.

2. 25.09.14 (ore 3).
   Anello commutativo, campo. Esempi, tra cui F₂. Divisione con resto (teorema s.d.). Definizione di divisore. Congruenze: definizione di congruenza modulo un intero positivo d. La congruenza e' una relazione di equivalenza. Ogni numero e' congruo, modulo d, al suo resto quando viene diviso per d. Due numeri sono congrui tra loro modulo d se e solo se hanno lo stesso resto quando vengono divisi per d. La congruenza conserva somma e prodotto. L'insieme delle classi di resto modulo d e' un anello commutativo con d elementi. Esempi e relative tabelle additive e moltiplicative.
3. 29.09.14 (ore 2)
   L'importante identita' [xy]_d=[[x]_d[y]_d]_d con x,y numeri interi. Su questa si basa l'algoritmo dei quadrati ripetuti per calcolare il resto con dividendi molto grandi. Esempio svolto: calcolo del resto della divisione di 1211 per 21. Sia div(n) l'insieme dei divisori di un intero n. Nota che div(0)={0,1,2,3,...}=N Lemma (Euclide): Siano m,n in Z. Allora esiste unico d in N tale che div(m) intersecato div(n) e' uguale a div(d). Dimostrazione unicita'. Massimo comun divisore: esistenza e unicita' (Lemma di Euclide (Euclide (300 a.C.))). Algoritmo Euclideo (Euclide (300 a.C.)) per determinare il massimo comun divisore, gcd(m,n), tra due interi m e n.
4. 2.10.14 (ore 3)
   Algoritmo Euclideo esteso per determinare interi x e y tali che xm+yn=gcd(m,n). Definizione: m e n sono primi tra loro se gcd(m,n)=1.
   Proposizione: m e n sono primi tra loro se e solo se esistono x e y tali che xm+yn=1.
   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.
   Teorema cinese del resto (Sun-Tsu 280-473, Chin Chiu Shao 1247) Dimostrazione. In particolare l'esistenza di una soluzione 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.
   Per approfondimenti: Secret sharing.
   
5. 6.10.14 (ore 2)
   Esercizio sui reticoli in R; completamento della presentazione dello secret sharing scheme di Shamir. 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 è biunivoca (è infatti un isomorfismo di anelli (dimostrata solo la biunivocita'). Si osserva che questo e' equivalente al teorema cinese del resto come enunciato nella precedente lezione (risolubilita' di un sistema di congruenze).
   (Z/nZ)^* e' un gruppo, il gruppo degli invertibili dell'anello Z/nZ. Z/nZ e' un campo se e solo se n e' primo.
   Definizione della funzione φ di Eulero (1707-1783).
6. 9.10.2014 (ore 3)
   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.
   Numeri primi: definizione; crivello di Eratostene; 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.
   Per approfondimenti: Twenty years of attacks on the RSA cryptosystem di Dan Boneh. The largest known primes- a summary.
7. 13.10.2014 non c'e' stata lezione.
8. 16.10.2014 (3 ore)
   Distribuzione primo foglio di esercizi. Introduzione alla teoria della complessita' computazionale. Un esempio di algoritmo per scomporre un intero nel prodotto di due fattori che esegue in un tempo che dipende esponenzialmente dalla taglia dell'input. Definizione (operativa) di algoritmo. Misura dell'efficienza di un algoritmo: la macchina di Turing deterministica. Definizione formale ed esempio. Un algoritmo polinomiale per un dato problema e' un algoritmo che risolve il problema correttamente per ogni input e impiega non piu' di cn^k passi per un input di taglia n. Dove c e k sono costanti. Diremo anche, in altri termini, che il tempo di esecuzione e' un O(n^k). Esempi di algoritmi polinomiali (somma e prodotto di numeri interi).
   Tesi di Cobham e Edmond (1965): un problema e' computazionalmente facile solo se ammette un algoritmo polinomiale.
   Un problema che non ammette un algoritmo polinomiale si dice non trattabile. Tabella per mostrare la differenza qualitativa tra algoritmi polinomiali e algoritmi esponenziali (la definizione di algoritmo esponenziale puo' essere scritta sulla falsa riga di quella di algoritmo polinomiale). Problemi decisionali. Definizione. Esempi: Decidere se un numero e' primo (primalita'); decidere se un grafo G connesso ammette un circuito Euleriano; decidere se un grafo G connesso ammette un circuito Hamiltoniano; decidere se un grafo connesso pesato G' con il dato di un numero positivo B (budget), ammette un circuito Hamiltoniano di costo inferiore a B (problema TSP=travel salesman problem); decidere se una formula Booleana AND of ORs e' soddisfacibile. Esempi ed esistenza nota o meno di algoritmi polinomiali per i problemi sopra descritti.
   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
   Nota la definizione di formula Booleana AND of ORs. Tra il materiale utilizzato per l'introduzione alla teoria della complessita' : Conferenza di Vijaya Ramachandran: P vs NP problem, tenuta al Clay Mathematics Institute e i capitoli 17 e 18 del libro A walk through combinatorics, Miklos Bona, sia la seconda che la terza edizione contengono i capitoli sulla teoria della complessita'. Notes on Turing machine.
   Per la teoria dei grafi vedere, ad esempio: Corso di teoria dei grafi, Carlo Casolo e il libro di Bona succitato.

   Per approfondimenti: per altri algoritmi di fattorizzazione dei numeri naturali vedere ad esempio il libro di testo a pagina 30. Sempre sulla fattorizzazione in primi vedere anche Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer di PW Shor SIAM J. Comput., (26)5, 1484-509 (997). 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 sull'argomento Turing and the development of computational complexity di S. Homer e A. Selman (2011).

9. 20.10.2014 (2 ore)
   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.
   Esempi: tutti i linguaggi citati nella lezione precedente sono in NP. Per ognuno forniamo il certificato, in particolare per L_Pr, per cui la dimostrazione dell'appartenenza a NP risale al '75 (certificato di Pratt). I linguaggi L_EC e L_Pr sono anche in P (per L_Pr in P vedi articolo del 2004, citato qui sotto)
   Significato degli acronimi P e NP.Il problema P vs NP.Definizione di riducibilita' di un linguaggio L' a un linguaggio L,scriviamo L'≤_pL. Esempio: L_HC≤_pL_TSP.
   Definizione di linguaggio NP completo. Teorema (Cook, 1961): 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. Fatto: P=NP se e solo se un linguaggio completo e' in P (segue dalla definizione di NP completezza). Definizione di linguaggio NP-hard.

   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).
   Il problema P vs NP e il millenium prize.

10. 23.10.2014 (3 ore)
    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. Tale esempio fornisce una motivazione per lo studio dei polinomi e dei quozienti. POLINOMI: L'anello dei polinomi, A[x], nell'indeterminata x a coefficienti in un anello A. Grado di un polinomio. 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. Esempi di algoritmo della divisione con polinomi a coefficienti in F_{p, con p primo.
    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.
    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)={a1,...,ar} allora f=q(x-a1)^νa1(p)...(x-ar)^ν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.}
11. 27.10.2014
    Didattica sospesa per iniziativa di orientamento.
12. 30.10.2014
    QUOZIENTI. Sia G un gruppo. Definizione di sottogruppo H di G, di classe laterale sinistra e di insieme G/H delle classi laterali sinistre. Sia G un gruppo finito, allora |H| divide |G|. Sia g in un gruppo G un elemento. Definizione di potenza intera di un elemento g in un gruppo G. Definizione di ordine di g, ord(g). Sia G un gruppo finito, allora ord(g) divide |G|, g^|G|=e, se g^r=e, allora ord(g) divide r. 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}. L'operazione di composizione di G induce una struttura di gruppo sul quoziente quando il sottogruppo e' normale. Questo e' sempre vero nel caso del nucleo. Ker(f), di un omomorfismo f. Per semplicita' comunque ci limiteremo a considerare gruppi abeliani, che sono quelli che ci interessano per il corso. I sottogruppi di gruppi abeliani sono sempre normali e il quoziente esedita sempre da G una struttura di gruppo.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/H in K che, composta con la proiezione naturale da G su G/H, da' f. Definizione di un ideale I di un anello A. Il quoziente A/I e' un anello. Definizione di omomorfismo di anelli. 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 neturale da A su A/I, da' f.
13. 3.11.2014 (2 ore)
    Radici di 1 in C: definizione, radici n-esime primitive di 1 in C (caratterizzazione e proprieta'). Polinomi ciclotomici: definizione, esempi e proprieta'.
14. 6.11.2014 (3 ore)
    Caratteristica di un campo. Radici n-esime primitive di 1 in un campo K. Criterio per determinare se un elemento a di K e' una radice n-esima primitiva utilizzando i polinomi ciclotomici. Definizione di gruppo ciclico. Esempi. Teorema di Gauss: sia G un sottogruppo FINITO del gruppo moltiplicativo di un campo, allora G e' ciclico. L'anello F_p[x]/(f), con f in F_p[x]. Esempi. Cardinalita' di F_p[x]/(f). Definizione di polinomio irriducibile. Osservazione: se f in F_p[x] e' irriducibile allora non ha radici, se f in F_p[x] di grado 2,3 non ha radici, allora e' irriducibile. Prop. L'anello F_p[x]/(f) e' un campo se e solo se f e' un polinomio irriducibile. Si osserva che il campo F_p[x]/(f) ha caratteristica p. Lemma: Sia F un campo finito. Allora esistono un naturale p, primo, e un polinomio irriducibile f in F_p[x], tali che F_p[x]/(f) e' isomorfo a F. Corollario: un campo finito F ha cardinalita' uguale alla potenza di un primo. Per approfondimenti: Gruppi ciclici finiti e il protocollo di scambio delle chiavi di Diffie e Hellman. Il sistema crittografico di El Gamal.
15. 10.11.2014 (2 ore)
    Teorema di esistenza e unicita': Siano p un primo e n un naturale, n>0. Allora esiste, unico, un campo di ordine pⁿ. Dimostrazione dell'esistenza. Dimostriamo il seguente risultato: siano p un primo e n un naturale, n>0. Sia f un fattore irriducibile di Phi_pⁿ-1 in F_p[x], allora f ha grado n. Questo implica che dati p un primo e n un naturale, n>0 esiste un polinomio irriducibile f in F_p[x] di grado n (si ottiene quindi il campo F_p[x]/(f) di cardinalita' pⁿ)
16. 13.11.2014 (3 ore)
    Lemma: Sia A un anello commutativo e I un ideale di A, il quoziente A/I e' un campo se e solo se I e' un ideale massimale. (dimostriamo solo l'implicazione diretta). Dimostrazione dell'unicita':Siano F e F' due campi con la stessa cardinalita' finita, allora F e F' sono isomorfi. Definizione della mappa di Frobenius (1849-1917) dall'anello F_p[x]/< f > in se. F_p[x]/< f > e' uno spazio vettoriale su F_p di dimensione uguale al grado di f. La mappa di Frobenius e' un omomorfismo di anelli e una applicazione lineare.
    Teorema: Un polinomio f e' irriducibile in F_p> se e solo se Ker(F)=0 e Ker(F-I)= F_p. Esempio di applicazione dell'algoritmo di fattorizzazione.
    Prima parte della dimostrazione: f irriducibile implica Ker(F)=0 e Ker(F-I)=F_p. La dimostrazione da' un algoritmo per la fattorizzazione di polinomi (algoritmo di Berlekamp).
17. 17.11.2014 (2 ore)
    Traccia della dimostrazione dell'implicazione inversa, ossia, se Ker(F)=0 e Ker(F-I)=F_p, allora f e' e' irriducibile in F_p>. Teorema (s.d.): Il polinomio X^pn-1-X in F_p[x] e' il prodotto di tutti e soli i polinomi monici irriducibili di F_p di grado d, con di compreso tra 0 e n e d che divide n. Inoltre ogni fattore ha molteplicita' 1.
    Corollario: Sia N_d il numero dei polinomi monici irriducibili di grado d in F_p, allora pⁿ=&sum_{d | n}d N_d.
    Da cui la formula diretta per N_n scritta utilizzando la funzione di Moebius (vedere ad esempio in questo file l'esempio numero 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: 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. 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).
18. 20.11.2014 (3 ore)
    Distanza di Hamming, definizione e proprieta'. Criterio di decodifica a minima distanza (DMD). Il procedimento di decodifica a minima distanza e' detto anche nearest neighbour decoding.
    Proposizione: Per un canale senza memoria e fortemente simmetrico le decodifiche a massima probabilita' e minima distanza coincidono. 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}. Un codice C corregge al piu' s errori in DMD se per ogni w in Aⁿ tale che d(w,C)≤s esiste un'unica parola x in C tale che w appartiene a B_s(x). Lemma: Sia C un codice in Aⁿ_q. Allora d(C)≥2s+1 se e solo se B_s(x)∩B_s(y)=∅ per ogni x e y in C, x diverso da y.
    Proposizione:(i) un codice C segnala al piu' s errori se e solo se d(C)≥s+1; (ii) un codice C corregge al piu' s errori se e solo se d(C)≥2s+1
    Un codice C si dice di tipo (n,M,d)_q se C e' contenuto in Aⁿ, la cardinalita' di A, |A|, e' q, la cardinalita' di C, |C|, e' M e d=d(C). La capacita' di rilevare/correggere errori con la decodifica a minima distanza dipende dal parametro d, precisamente:un codice (n,M,d)_q rileva al piu' d-1 errori e corregge al piu' [(d-1)/2] errori (il numero [(d-1)/2] indica la parte intera inferiore di (d-1)/2). Denotiamo con e=[(d-1)/2]. Teorema di Hamming (limitazione superiore per M in funzione di n, q ed e).
19. 24.11.2014 (2 ore)
    Lemma: formula per il numero di parole di Aⁿ contenute in una palla chiusa di raggio r. Definizione di codice perfetto. Esercizio: dimostrare che se (n,M,d)_q e' perfetto allora d e' dispari. Codici lineari: definizione. Esempi. Prodotto scalare in F_qⁿ. Ortogonale di un codice lineare. La somma delle dimensioni di C e del suo ortogonale e' n. L'ortogonale dell'ortogonale di C e' C. Definizione di matrice generatrice G e matrice di controllo di parita' H di un codice lineare. Caratterizzazione di un codice e del suo ortogonale a partire rispettivamente dalla matrice di controllo di parita' e dalla matrice generatrice.
20. 27.11.2014 (3 ore) Peso di Hamming di un elemento in F_qⁿ. Peso di Hamming di un codice lineare. Dato C codice lineare per e distanza di C sono uguali. Proposizione: sia C un codice lineare in F_qⁿ di dimensione k. Sia H una matrice di controllo di parita' di C. Allora:
    (i) d(C)≥l se e solo se non ci sono l-1 colonne di H linearmente dipendenti
    (ii) d(C)≤l se e solo se esistono l colonne di H linearmente dipendenti.
    (iii) d(C)=l se e solo se non ci sono l-1 colonne di H linearmente dipendenti ed esistono l colonne di H linearmente dipendenti.
    Costruiamo i codici di Hamming, che sono un esempio di codici linerari perfetti:
    definizione di spazio proiettivo P(F_q^r); P(F_q^r); contiene esattamente s=(q^r-1)/(q-1) punti; definizione di un codice Ham(r,q) mediante la matrice di controllo di parita'. I parametri di Ham(r,q) sono [s,s-r,3]_q e vale l'uguaglianza nell'Hamming bound.
    I codici Ham(r,q) sono tutti equivalenti come codici lineari (come esercizio successivo alla def. di equivalenza).
    Definizione: una applicazione lineare f da F_qⁿ in se' conserva la distanza di Hamming se per ogni coppia di elementi x,y in F_qⁿ si ha d(f(x),f(y))=d(x,y) (equivalentemente: se per ogni x in F_qⁿ si ha wt(f(x)=wt(x)). Osservazione: ogni applicazione lineare da F_qⁿ in se'che conserva la distanza di Hamming e' un isomorfismo. Chiamiamo un isomorfismo che conserva la distanza Hamming un'isometria.
    Definizione del gruppo delle permutazioni generalizzate, GP(n,F_q): e' il sottogruppo del gruppo degli isomorfismi, GL(n,F_q), di F_qⁿ, generato dalle permutazioni e dagli isomorfismi del tipo diag(l₁,...,l_n). Proposizione: GP(n,F_q) coincide con il sottogruppo degli isomorfismi di F_qⁿ che conservano la distanza di Hamming (isometrie).
21. 01.12.2014 (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 linear in 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. Le seguenti operazioni sulle colonne producono una matrice, che definisce, come matrice generatrice, un codice C' equivalente a C. 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 e l'osservazione precedente. 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 q^n-k elementi, ognuno di questi e', come sappiamo, una classe laterale (coset). Osservazione importante: nella decodifica a minima distanza di una parola ricevuta w con una parola x in C, la parola w-x e' una parola della classe di w. Poiche' d(w,x)=wt(w-x), la parola w-x e' una parola nella classe di w di peso minimo. Siamo quindi interessati a individuare, in ogni classe, le parole di peso minimo. In ogni classe scegliamo una parola di peso minimo, questa e' per definizione il 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 coset leader, 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.
22. 04.12.2014 (3 ore)
    Riprendiamo la tabella "standard array". Il procedimento di decododifica a minima distanza e' il seguente: ricevo w. Controllo la tabella, individuo la riga a cui appartiene w. Il capoclasse err(w) corrispondente a w e' il primo coefficiente di tale riga. Decodifico con x=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. L'elemento 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 tavola detta syndrome look-up table nel modo seguente: la prima colonna coincide con la prima colonna dello standard array, da' quindi una lista di coset leader, con primo elemento 0. La seconda colonna associa ad ogni coset leader 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. Miglioriamo questa tabella. Proposizione: l'applicazione S_H e' iniettiva su B_e(0), dove e e' come al solito la parte intera inferiore di (d-1)/2 e rappresenta la capacita' correttiva del codice.
    Corollario: ogni parola in B_e(0) e' l'unica parola di peso minimo nella propria classe.
    Costruiamo la syndrome look-up table mettendo, per prime nella prima colonna, tutte le parole in B_e(0), partendo da 0. Le righe (classi) corrispondenti NON saranno asteriscate. Completiamo con i rimanenti coset leaders.
    Procedimento di decodifica a sindrome (sempre DMD): ricevo la parola w. Passo 1: calcolo S_H(w). Passo 2: mediante la tabella syndrome look-up table individuo il coset leader corrispondente err(w). Passo 3: decodifico con x=w-err(w). Osservazione: se S_H(w) appartiene a S_H(B_e(0))--ossia se w sta sulla riga corrispondente a un coset leader in B_e(0)--la decodifica e' esatta, ossia x e' l'unica parola di C tale che d(w,x)= d(w,C). Esempi.
23. 11.12.2014 (2+3 ore)
    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.
    Abbiamo gia' visto l'Hamming bound. Singleton bound: per codici generali e per codici lineari. Teorema di unisolvenza: Siano a₁,...,a_m elementi distinti in un campo K. Sia n≤ m. Allora l'applicazione ev_a:k[x]_≤n-1---> K^m cosi' definita: ev_a(p)=(p(a₁),...,p(a_m)) e' lineare e iniettiva. Se n=m e' un isomorfismo di spazi vettoriali. Costruzione dei codici di Reed-Solomon RS(k,q); parametri [q-1,k,n-k+1]_q. I codici di Reed-Solomon verificano il bound di Singleton.
    Teorema (s.d.): fissata la potenza di un primo q, siano n,k,d interi tali che: 2 ≤ d ≤ n, 1 ≤ k ≤ n e V^n-1_q(d-2)≤ n-k. Allora esiste un codice lineare [n,k,d']_q, con d' ≥ d. Corollario [Gilbert-Varshamov lower bound](s.d.): 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 (s.d.).
    Per 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 sulla versione asintotica del bound di Gilbert-Varshamov.
    
    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. Esempi di codici ciclici. Esempio di codici ciclici in F_qⁿ equivalenti e generati da polinomi diversi.
24. 15.12.2014 (non c'e' stata lezione causa concomitante sessione di Laurea)
25. 18.12.2014 (3 ore)
    Introduzione alla decodifica dei codici ciclici e alla costruzione di una matrice di controllo di parita' a partire dal polinomio generatore g. Proposizione: 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). Utilizzando H, una parola s in F_q^n-k e' la sindrome di una parola w in F_qⁿ se e solo se per i polinomi corrispondenti si ha che s(x) e' il resto della divisione del polinomio w(x) per g. 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. Un articolo utile sui codici ciclici: An introduction to linear and cyclic codes di D. Augot, E. Betti e E. Orsini. E' possibile definire per i codici ciclici, utilizzando la loro struttura particolare, un algoritmo di decodofica detto error trapping che non abbiamo descritto a lezione.