La trasformata di Winograd nella teoria dei codici correttori

Be F field of prime characteristic p. The polyonmial factorization of x^r - 1 on F with r and p coprime, made through the study of the action of Galoise Group Gal(F(ξ), F)) on the cyclic group generated by x, leads to a quotient's decomposition F[x] on x^r - 1 in a field's produc. That product is still isomorphic to the quotient and the isomorphism itself is called Winograd Transform. We examinate orbits which determines the factorization showing some examples and a simple formula to compute the number of irreducible factors based on Burnside's Lemma. After a research in Winograd transform as linear transform between vector spaces and his role played in the identification of idempotents and ideals, we introduce the Error Correcting Codes, emphasize Cyclic Codes and BCH Codes. Here previous results takes place in the range of applications. In the last chapter Winograd transform and Error Correcting Codes find a commonplace in two applications: as first we see that union of a collection ok blocks of the Winograd transform defines a parity check matrix as well as a generating matrix for some cyclic codes. The second application consists in a way to codify a message which leads to reduce the number of information, identifing some 0-informations subvectors. Main references are a pre-print written by the supervisor and the volumes "Theory and Practice of Error Control Codes", by Richard E. Blahut and "Algebra e teoria dei codici correttori" by Luigia Berardi.

La fattorizzazione del polinomio x^r - 1, per r coprimo con p caratteristica del campo F su cui è definito, effettuata mediante l studio dell'azione del gruppo di Galois Gal(F(ξ), F)) sul gruppo ciclico generato da x porta ad una scomposizione del quoziente F[x] su x^r - 1 in un prodotto di campi. Tale prodotto è ancora isomorfo come algebra al quoziente, e l'isomorfismo che si viene a creare è noto come trasformata di Winograd. Si esaminano approfonditamente le orbite che determinano la fattorizzazione proponendo alcuni esempi ed una formula per calcolarne la cardinalità basata sul lemma di Burnside. Una volta studiate le proprietà principiali della trasformata di Winograd come trasformazione lineare fra spazi vettoriali ed il ruolo che gioca nel determinare ideali ed idempotenti si presenta la teoria dei codici correttori, con enfasi particolare ai codici ciclici e ai codici BCH. In questa parte i risultati dei capitoli precedenti prendono posto in modo naturale in un ambito applicativo. Nell'ultimo capitolo trasformata di Winograd e teoria dei codi correttori trovano un punto in comune in due applicazioni: come prima applicazione vediamo che una scelta di blocchi della trasformata di Winogad definisce una matrice che può essere usata come matrice di controllo o come matrice generatrice di determinati codici correttori. La seconda applicazione consiste in un sistema per codificare 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. Le fonti principali sono un pre-print del relatore di questa tesi ed i volumi "Theory and Practice of Error Control Codes", di Richard E. Blahut ed "Algebra e teoria dei codici correttori" di Luigia Berardi.