Tesi di laurea di Sebastiano Ferraris presso la Facoltà di Scienze Matematiche Fisiche Naturali Corso di Laurea in Matematica Università di Torino. Il punto di partenza di questa tesi sono alcune lezioni di Laboratorio di Applicazioni dell'Algebra utilizzate per approfondire diversi argomenti inerenti la teoria dei codici correttori. 
La teoria dei codici correttori si basa sulla necessità di trasmettere informazione attraverso un canale che per motivi tecnici può alterare parte del messaggio. In ogni sistema di comunicazione infatti la ricezione può essere disturbata da segnali di interferenza chiamati genericamente "rumore" che si sommano all'informazione originariamente trasmessa.
Il punto di partenza di questa tesi sono alcune lezioni di Laboratorio di Applicazioni dell'Algebra tenuto nel 2011 ed un pre-print del prof. Umberto Cerruti che ho di utilizzato per approfondire diversi argomenti inerenti la teoria dei codici correttori che hanno suscitato il mio interesse e la mia curiosita. I principali che propongo in questa tesi sono:
capitolo 1 Scomposizione dell'algebra Rr;F = F[x] / (xr - 1) in un prodotto di campi: attraverso lo studio della fattorizzazione di xr - 1 tramite un gruppo isomorfo al gruppo di Galois Gal(F(); F)) che agisce sul gruppo generato da x in Rr;F arriviamo a costruire una nuova algebra sui fattori irriducibili del polinomio xr - 1. Ricordando che per M(v)(x) fattore irriducibile di xr - 1, ogni quoziente F[x] / M(v)(x) è un campo, costruiamo la nuova algebra come il prodotto di tali campi. Questa e ancora isomorfa a Rr;F e l'isomorfismo così creato viene definito trasformata di Winograd. Sempre nel capitolo 1 dimostriamo una formula basata sul teorema di Burnside per determinare la cardinalità dell'insieme dei fattori irriducibili M(v)(x).
capitolo 2 Studio degli ideali e degli idempotenti di Rr;q: a partire da questo punto proseguiamo considerando solo i campi finiti per orientare la direzione sulle applicazioni alla teoria dei codici correttori. Dopo la definizione di alcuni operatori su Rr;q presentiamo uno studio sugli ideali e sugli idempotenti che giocano un ruolo fondamentale nella teoria dei codici correttori. Data la semplicità degli ideali e degli idempotenti di un campo, questo studio non avviene direttamente su Rr;q ma sulla scomposizione in campi ricavata nel capitolo precedente.
capitolo 3 Trasformata di Winograd come trasformazione lineare fra Rr;q ed il prodotto di campi in cui si scompone: approfondiamo la definizione di trasformata di Winograd ricavando la matrice associata alla trasformazione e la matrice inversa e presentiamo alcune delle sue proprietà più rilevanti per gli scopi della tesi. Per poter definire la matrice di trasformazione in modo più semplice partiamo dalla definizione di una ulteriore algebra, che chiamiamo algebra dei vettori circolanti concatenati. Questa continua ad essere un'algebra isomorfa a quelle già proposte e mantiene la struttura di prodotto di campi, ma con una forma più efficace per parlare di matrici di trasformazioni. Anche in questo capitolo i vari sviluppi della teoria sono accompagnati da esempi numerici.
capitoli 4 e 5 Introduzione alla teoria dei codici correttori: in questo interludio presentiamo la teoria dei codici correttori dalle basi, per arrivare a definire i codici lineari, i codici ciclici ed i codici BCH. Nel corso del capitolo utilizziamo la maggior parte dei risultati ottenuti nei capitoli 1 e 2 e prepariamo il terreno per poter presentare le applicazioni della trasformata di Winograd ai codici correttori, scopo della tesi.
capitolo 6 Applicazioni dello studio di Rr;q e della trasformata di Winograd alla teoria dei codici correttori: come prima applicazione vediamo che una scelta di blocchi della trasformata di Winograd definisce una matrice che può essere usata come matrice di controllo o come matrice generatrice di determinati codici correttori. La seconda applicazione e un sistema per codicare e decodificare un messaggio che permette di diminuire la quantità di informazione per inviare un messaggio codificato, individuando in ogni parola alcuni sottovettori che non contengono informazioni rilevanti.
Originariamente la trasformata di Winograd e stata scoperta come strumento per diminuire la complessità computazionale del prodotto di convoluzione e come alternativa alla trasformata di Fourier discreta. E stata presentata per la prima volta nell'articolo On Computing the Discrete Fourier Transform di Shmuel Winograd. In questa ricerca ho omesso i collegamenti fra la trasformata di Winograd e la Trasformata di Fourier, ho omesso le implicazioni con la teoria dei codici spettrale e non ho parlato di una applicazione della trasformata di Winograd alla teoria dei codici correttori scoperta da Miller, Truong e Reed presentata nel 1980 con l'articolo Ecient Program for decoding the (255; 223) Reed-Solomon Code over GF(28) [22]. Ho invece considerato la trasformata di Winograd come una trasformazione lineare fra due spazi vettoriali, esaminando due applicazioni ai codici ciclici. Le fonti principali, oltre al gia citato articolo del relatore della tesi, sono Theory and Practice of Error Control Codes, di Richard E. Blahut [4] ed Algebra e teoria dei codici correttori di Luigia Berardi.
Scarica la tesi in formato pdf
Sebastiano Ferraris, La Trasformata di Winograd nella Teoria dei Codici Correttori
,
