2. TEORIA DEI CODICI

2.1. TOPOLOGIA DI RETI DI COMUNICAZIONE

In [21] si è affrontato un problema di topologia di reti di comunicazione (packet switched networks) che è stato tradotto in un problema di teoria di disegni, la cui soluzione coinvolge (k,n)-archi pesati in piani proiettivi e codici lineari 3-dimensionali. In particolare il problema principale era massimizzare “coverings”: nel lavoro si è fornito un procedimento costruttivo, che risulta unico, per la generazione di coverings di ordine massimo. Ciò risolve un problema che secondo quanto affermato nel 1999 (Lecture Notes 267, Cambridge Univ. Press) da uno dei massimi esperti di teoria dei disegni, C.J. Colbourn, sembrava inaccessibile in quanto prevedeva necessaria la risoluzione del packing problem degli archi piani di ogni specie. La soluzione del problema era ritenuta particolarmente rilevante, tanto che esso fu oggetto di studi internazionali durante almeno due decenni. Nei vari tentativi, furono adoperati vari metodi, cercando di tradurre il problema in vari contesti: dalla teoria dei grafi (J.C. Bermond et al. 1983), all’analisi numerica basata sui computer e alla teoria dei disegni (B. Yener et al., 1997), alla teoria dei piani proiettivi (C.J. Colbourn, 2002). Questi meccanismi di traduzione solo in [21] raggiungono il livello di generalità che permette una soluzione completa in un caso generico e conduce a legami con la teoria dei codici, precedentemente non noti, e ad un nuovo tipo di problemi nella teoria dei disegni. In [21] è anche nuova l’applicazione di una tecnica dalla teoria dei grafi (la fractional matching number, teoria che usa la programmazione lineare, Furedi, 1981, 1989), la quale permette la dimostrazione dell’ottimalità della nostra costruzione nel caso generico in questione. Sempre in [21] la formulazione in termini di disegni ci conduce allo studio di un nuovo tipo di strutture estremali generalizzando la nozione di almost projective planes (nel senso più ristretto studiati da A.A.Blokhuis et al., 2001): esempi significativi si trovano nel lavoro.

2.2. CODICI NMDS, CODICI ALTAMENTE SIMMETRICI

I codici NMDS (codici con difetto di Singleton uguale a 1, il cui duale gode della stessa proprietà) sono i piu ambiti dopo gli MDS. Infatti trovare buoni codici lineari consiste, essenzialmente, per una data lunghezza ed una fissata dimensione massimizzare la distanza minima, in modo da potenziare la loro capacità di correzione di errori. Come è noto questa distanza minima non può superare il limite di Singleton e quando esso è raggiunto si hanno codici MDS, che, salvo casi banali, non possono esistere per lunghezze superiori a q+1. Pertanto il problema successivo che si pone in termini di determinazione di codici buoni è cercare quelli con difetto di Singleton uguale ad 1.

In [AC5] e [28] si determina una famiglia di codici lineari NMDS altamente simmetrici, aventi come gruppo di automorfismi il prodotto diretto del gruppo di Galois di una certa estensione di campi e di un gruppo regolare di permutazioni.

La famiglia contiene molti codici classici (il codice esteso di Hamming, l'hexacode, i codicidi Golay, i codici di Pless) ed anche alcuni codici nuovi sopra F_4 e F_8 con parametri estremamente buoni. Questa famiglia può essere estesa in maniera naturale a codici il cui alfabeto forma un anello. Lo Z_4 octacode lineare appartiene alla famiglia: esso fornisce una costruzione del famoso Nordstrom-Robinson code. Viene inoltre fornita una descrizione algebrico-geometrica di uno dei due codici massimali NMDS su GF(8) (classificati in [15]), quello che possiede un “inusuale grande” gruppo di simmetrie (prodotto diretto di A_₄ con un gruppo elementare abeliano di ordine 16); tale descrizione si appoggia alla nozione combinatoria di order design.

Il codice ternario [66, 10, 36]_3, recentemente determinato da N. Pace e' altamente simmetrico, avendo come gruppo di automorfismi il gruppo di Mathieu M_12 (ordine 95040): in [81] si fornisce una costruzione teorico-gruppale di tale codice in termini di M_12 e una descrizione combinatoria in termini dello small Witt design, il sistema di Steiner S(5,6,12).

I risultati strettamente collegati con gli (n,k) archi sono stati illustrati nella precedente sezione.

2.3. CODICI LDPC

I codici LDPC (Low-Density Parity-Check) sono una classe di codici estremamente performanti, essendo la loro capacità di correzione di errori vicina al limite di capacità di Shannon.

In [54] sono state costruite nuove classi di codici LDPC, in alcuni casi dai parametri migliori rispetto a quelle finora conosciute. Ciò è stato ottenuto sviluppando un approccio geometrico, basato sul concetto di configurazione. Per l'efficienza degli algoritmi di decodifica di codici LDPC è necessario che il grafo di Tanner associato al codice non contenga cicli di bassa lunghezza. Il problema matematico che ne deriva è quello della costruzione di grafi bipartiti con alta girth, o, in termini combinatorici, di configurazioni simmetriche.

Per la determinazione di nuove classi di tali configurazioni in [AC10] e [AC15] e [74] sono stati utilizzati metodi gruppali e combinatorici. In particolare in [AC15] e [74] sono stati usati come strumento chiave i Golomb rulers e i Golomb rulers modulari. Ciò ha consentito di ottenere molti nuovi parametri, con particolare riferimento al caso ciclico; si sono stabilite inoltre nuove limitazioni superiori sul minimo intero E(k) (Ec(k)) tale che per ogni v > E(k) (Ec(k)) esiste una v_k-configurazione simmetrica (simmetrica ciclica).

Nel contesto di grafi simmetrici in [57] sono stati studiati i grafi unitari, e la loro classificazione costituisce il risultato principale del lavoro. Essi sono una famiglia di grafi simmetrici aventi come vertici le bandiere dell'unital hermitiano e relazioni di adiacenza determinate dallla struttura del campo finito sottostante; ammettono il gruppo unitario come gruppo di automorfismi. Tali grafi hanno un ruolo significativo nella classificazione dei grafi simmetrici con quozienti completi tali che la struttura di incidenza associata è doppiamente transitiva sui punti.

2.4. CODICI ADDITIVI

I codici additivi formano una generalizzazione di grande portata del concetto classico di un codice lineare. Nel senso piu vasto codici additivi sono codici sopra un alfabeto che forma un gruppo abeliano (scritto in maniera additiva). Nella mia ricerca si è considerato un concetto leggermente piu ristretto dove l'alfabeto forma uno spazio vettoriale sopra un corpo e la linearità è valida sopra quel corpo. Nell'interpretazione geometrica la teoria dei codici lineari è equivalente alla teoria degli insiemi di punti in spazi di Galois e la distribuzione di questi punti su iperpiani. L'espressione geometrica della teoria dei codici additivi q²-ari q-lineari (e cioè di una sottofamiglia parametrica) è la teoria delle rette in spazi di Galois e loro distribuzione su iperpiani. Anche questo concetto ristretto è una generalizzazione di vasta portata del concetto di un codice lineare. Infatti contiene come caso speciale la teoria dei codici quantici (quantum stabilizer codes). In [AC9] usando una descrizione geometrica si prova la non esistenza di un codice additivo [12,7,5]_₄. In [45], usando argomentazioni geometriche si fornisce la classificazione completa dei parametri di codici quaternari additivi ottimali di lunghezza <=12. Il lavoro contiene inoltre la costruzione di un nuovo codice ottimale di lunghezza 13. In [48] è presente la prova geometrica dettagliata della non esistenza di un codice quaternario additivo di lunghezza 12 dimensione binaria 9 e distanza minima 7. In [70] si e' provata la non esistenza di un codice quaternario additivo di lunghezza 15 dimensione binaria 5 e distanza minima 9 da cui consegue che la massima dimensione per un codice additivo quaternario di lunghezza 15 e' 4.5.

2.5. CODICI QUANTICI

Negli ultimi anni una tematica della mia ricerca è stata quella dei codici quantici.

Pur essendo ancora in uno stato embrionale, la ricerca sul calcolo quantico, sia teorica che pratica, è molto attiva, essendo anche stimolata e sostenuta sia da governi nazionali che da agenzie militari. I codici quantici correttori di errori rivestono grande importanza nella protezione dell'informazione da errori in un futuro computer quantico, per la cui realizzazione diversi gruppi di ricerca stanno lavorando. I calcolatori quantici su larga scala sono potenzialmente in grado di risolvere problemi molto più velocemente di un qualsiasi calcolatore classico, che usi i migliori algoritmi noti; un esempio è la scomposizione in fattori di un numero intero, problema legato ai più comuni algoritmi crittografici. Il lavoro fondamentale di Calderbank-Rains-Shor-Sloane (1998) traduce la correzione di errori in computazioni quantiche nel linguaggio dei teoria dei codici sopra campi finiti (quantum stabilizer codes, caso speciale di codici additivi quaternari). In [43], si fa un passo avanti traducendo in linguaggio geometrico il problema della correzione di errori in ambito quantico: codici binari quantici e più in generale codici quaternari additivi sono descritti da sistemi di punti e rette nei spazi binari di Galois. Tale approccio ha chiarito la struttura di alcune famiglie di quantum codes classici, ha condotto a nuove costruzioni, ha permesso di stabilire relazioni con oggetti come quadriche e funzioni APN (concetto principale nella teoria dei crittografici S-boxes). Questo punto di vista geometrico sempre in [43] ha consentito la risoluzione di problemi aperti sull’esistenza di codici quantici ottimali, in particolare la costruzione di codici quantici con nuovi parametri. Con analogo approccio geometrico in [51] si dimostra la non esistenza di un [[13,5,4]] quantum stabilizer code, un problema irrisolto da diversi anni. Nella prova oltre che il considerare sistemi e rette nello spazio ambiente PG(7,2) ed in vari sottospazi, si utilizzano spazi fattoriali. Come conseguenza diversi problemi aperti sono rimossi dal database di Grassl (M. Grassl, http://www.codetables.de). In [AC18], [L2], [53] sono stati studiati codici quantici lineari di parametri [[n,n-10,4]] attraverso la loro controparte geometrica, ovvero calotte in PG(4,4) di cardinalità n, tali che la cardinalità della loro intersezione con un qualsiasi iperpiano ha la stessa parità di n. In particolare è stato determinato lo spettro delle cardinalità di tali calotte, classificando inoltre gli esempi estremali. Questi esempi sono stati ultilizzati per la definizione induttiva di famiglie infinite di calotte quantiche in dimensione superiore.

In [63] si determinano costruzioni generali per codici quantici sopra campi finiti qualsiasi ed una di esse generalizza un teorema presente nel lavoro fondamentale di Calderbank-Rains-Shor-Sloane. La parte centrale del lavoro consiste dello studio di calotte quantiche negli spazi proiettivi quaternari. In particolare sono determinate varie costruzioni recursive.