La Trasformata di Winograd nella Teoria dei Codici Correttori

Università degli Studi di Torino

Facoltà di Scienze Matematiche Fisiche Naturali

Corso di Laurea in Matematica

Tesi di Laurea Magistrale

La Trasformata di Winograd

nella

Teoria dei Codici Correttori

Relatore

Prof. Umberto Cerruti Laureando

Università di Torino Sebastiano Ferraris

Controrelatrice

Prof.ssa Lea Terracini

Università di Torino Sessione di Luglio 2013

Anno Accademico 2012-2013

Introduzione

“Calcolo esatto per cominciare a conoscere tutte le cose esistenti e tutti i segreti oscuri e misteriosi.”

- Ahmes, 1600 a.C.

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 [8] che ho utilizzato per approfondire diversi argomenti inerenti la teoria dei codici correttori che hanno suscitato il mio interesse e la mia curiosità.

I principali che propongo in questa tesi sono:

.

F[x]

R

capitolo 1 Scomposizione dell’algebra = in un prodotto di cam-

r

r,F −

(x 1)

r −

pi: attraverso lo studio della fattorizzazione di x 1 tramite un gruppo

isomorfo al gruppo di Galois Gal(F(ξ), che agisce sul gruppo generato

F))

R

da x in arriviamo a costruire una nuova algebra sui fattori irriducibili

r,F r (v)

−

del polinomio x 1. Ricordando che per M (x) fattore irriducibile di

r −

x 1, ogni quoziente .

F[x] (v)

M (x)

è un campo, costruiamo la nuova algebra come il prodotto di tali campi.

R

Questa è ancora isomorfa a e l’isomorfismo così creato viene definito

r,F

trasformata di Winograd.

Sempre nel capitolo 1 dimostriamo una formula basata sul teorema di Burnside per determinare la cardinalità dell’insieme dei fattori irriducibili

(v)

M (x). R

capitolo 2 Studio degli ideali e degli idempotenti di : a partire da questo punto

r,q

proseguiamo considerando solo i campi finiti per orientare la direzione sulle applicazioni alla teoria dei codici correttori. Dopo la definizione di alcuni

R

operatori su presentiamo uno studio sugli ideali e sugli idempotenti

r,q

che giocano un ruolo fondamentale nella teoria dei codici correttori. Data

la semplicità degli ideali e degli idempotenti di un campo, questo studio

R

non avviene direttamente su ma sulla scomposizione in campi ricavata

r,q

nel capitolo precedente. R

capitolo 3 Trasformata di Winograd come trasformazione lineare fra ed il prodotto di campi in cui si scompone: approfondiamo la definizione di trasformata di Winograd ricavando la matrice associata alla trasformazione

r,q

e la matrice inversa e presentiamo alcune delle sue proprietà più rilevanti

I

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.

R

capitolo 6 Applicazioni dello studio di e della trasformata di Winograd alla

r,q

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

Originariamente la trasformata di Winograd è stata scoperta come strumento

per diminuire la complessità computazionale del prodotto di convoluzione e come

alternativa alla trasformata di Fourier discreta.

È stata presentata per la prima volta nell’articolo On Computing the Discrete

Fourier Transform [31] 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 Efficient Program for decoding the (255, 223) Reed-Solomon

8

Code over GF (2 ) [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 già 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 [2].

Ringraziamenti

Sono stati innumerevoli gli aiuti ed i contributi, diretti o indiretti, grazie ai quali ho potuto procedere con la tesi. I più diretti alla risoluzione di alcuni problemi sono stati sicuramente quelli di Stefano Barbero che ringrazio per la sua perenne disponibilità a risolvere i dubbi degli studenti di Matematica. Di palazzo Campana vorrei anche ringraziare Paolo Martini, Andrea Montabone, Nadir Murru, Simone Garruto, Riccardo Jadanza, Andrea Ricolfi e Michele Voto per l’amicizia e per avere condiviso con me le loro idee.

Ringrazio Giuliano De Rossi ex-collega della tc-web, per i suggerimenti sui diagrammi commutativi e i colleghi della sim-tec che sono stati loro malgrado assillati dalle mie deformazioni matematiche. Ringrazio anche Filippo Ferraris per i suggerimenti sulla stesura (che non ho avuto modo di seguire) e per l’interesse che ha sempre dimostrato nei miei studi. Ringrazio infine, per il sostegno morale Francesco Giovo e Barbara Bosia, per quello immorale Andrea Baglione e per quello immortale Federica Narciso. Sebastiano Ferraris, Villar Dora 2013.

Indice

0 Quattro algebre isomorfe 1

0.1 Strutture algebriche . . . . . . . . . . . . . . . . . . . . . . . . . 1

0.2 Isomorfismi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

r −

1 Fattorizzazione di x 1 9

1.1 Classi ciclotomiche . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.1.1 Il gruppo Gal(Q(ξ), . . . . . . . . . . . . . . . . . . . 14

Q))

1.1.2 Il gruppo Gal(F (ξ), ) . . . . . . . . . . . . . . . . . . . 16

F

q q

r −

1.1.3 La fattorizzazione di x 1 . . . . . . . . . . . . . . . . . 19

1.2 Cardinalità dell’insieme di orbite . . . . . . . . . . . . . . . . . . 21

R

1.3 Fattorizzazione di come prodotto di campi . . . . . . . . . . . 24

2 Operatori, ideali e idempotenti minimali 29

R

2.1 Operatori su . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

R

2.2 Ideali di e sottospazi . . . . . . . . . . . . . . . . . . . . . . . 34

2.2.1 Ideali massimali e minimali . . . . . . . . . . . . . . . . . 38

2.2.2 Ideali ortogonali . . . . . . . . . . . . . . . . . . . . . . . . 40

2.3 Elementi idempotenti . . . . . . . . . . . . . . . . . . . . . . . . 43

3 Trasformata di Winograd 47

3.1 Algebra dei vettori circolanti concatenati . . . . . . . . . . . . . 48

3.2 Scomposizione di γ e di η . . . . . . . . . . . . . . . . . . . . . . 53

3.3 Proprietà strutturali di Γ . . . . . . . . . . . . . . . . . . . . . . 57

3.4 Matrice inversa ∆ . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4 Codici lineari 63

4.1 Codici rivelatori e codici correttori . . . . . . . . . . . . . . . . . 63

4.1.1 Codici correttori perfetti e limitazione di Hamming . . . . 66

4.1.2 (r,k)-codici e limitazione di Singleton . . . . . . . . . . . . 68

4.2 Matrice generatrice e matrice di controllo . . . . . . . . . . . . . 68

4.2.1 Codici lineari equivalenti . . . . . . . . . . . . . . . . . . 72

4.3 Codifica e decodifica nei codici lineari . . . . . . . . . . . . . . 72

4.3.1 Codifica tramite matrice generatrice . . . . . . . . . . . . . 73

4.3.2 Decodifica con la sindrome . . . . . . . . . . . . . . . . . 73

4.4 Limitazione di Gilbert-Varshamov per i codici lineari binari . . . 75

V Indice

5 Codici ciclici 77

5.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

5.2 Polinomi generatori . . . . . . . . . . . . . . . . . . . . . . . . . . 78

5.3 Matrice generatrice di un codice ciclico . . . . . . . . . . . . . . . 80

5.4 Polinomi e matrici di controllo . . . . . . . . . . . . . . . . . . . 81

5.5 Codifica e decodifica dei codici ciclici . . . . . . . . . . . . . . . . 82

5.6 Codici BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

5.6.1 Definizione dei codici BCH ed esempi . . . . . . . . . . . . 86

5.6.2 Decodifica Peterson-Gorenstein-Zierler . . . . . . . . . . . 88

6 La trasformata di Winograd nella teoria dei codici correttori 93

6.1 Matrice Γ come generatrice dei codici ciclici . . . . . . . . . . . . 93

(v)

6.1.1 Matrice Γ come matrice di controllo . . . . . . . . . . . . . 93

(v)

6.1.2 Γ come matrice di generatrice . . . . . . . . . . . . . . . . 94

(v)

6.1.3 Composizioni dei blocchi Γ . . . . . . . . . . . . . . . . . 95

6.2 Matrice ∆ nella decodifica . . . . . . . . . . . . . . . . . . . . . . 97

6.2.1 Sottovettori privi di informazione . . . . . . . . . . . . . . 97

6.2.2 Codifica con ∆, decodifica con Γ . . . . . . . . . . . . . . . 98

7 Appendice 101

7.1 Ricerca dei polinomi minimi sui campi finiti . . . . . . . . . . . . 101

7.2 Ricorrenze lineari . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

Capitolo 0

Quattro algebre isomorfe

Il tema principale della prima parte della tesi riguarda lo studio di alcune strutture algebriche e delle trasformazioni che si possono definire fra loro. In questo

r −

capitolo vediamo la struttura algebrica dei polinomi modulo x 1, delle matrici circolanti, dei vettori circolanti e delle combinazioni lineari di elementi nel gruppo ciclico C definite sul campo

F.

Lo scopo di questo capitolo è dimostrare che le algebre sopra elencate sono fra di loro isomorfe.

ψ

. 4

F[x] .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. FC

.

r .

− r

(x 1) .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

ψ ψ

. .

. .

. .

2 3

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

. .

.

. . . .

. . . .

.

. .

.

. .

.

. .

. ψ 1

c c

V M

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

r,F r,F .

F[x]

Nel prossimo capitolo amplieremo il diagramma rappresentando r −

(x 1)

r −

come prodotto di campi tramite la fattorizzazione di x 1.

0.1 Strutture algebriche

Algebra delle matrici circolanti

Una matrice quadrata è detta circolante se, fissata la prima riga, ogni riga successiva è il risultato di una permutazione ciclica di un posto verso destra della riga precedente.  

a a ... a

0 1 r−1

a a ... a

r−1 0 r−2

 

C =  

.. .. ..

 

. . .

 

a a ... a

1 2 0

×

L’insieme delle matrici circolanti r r a coefficienti nel campo è indicato con

F

cr,F

M e la permutazione ciclica è chiamata shift.

1

0. Quattro algebre isomorfe

×

Definizione 0.1.1. Sia A matrice r r i cui elementi in sono indicati con

F

(A) = a . A è detta matrice circolante se a = a quando

i,j i,j i,j k,l

− ≡ −

j i l k mod r

r

∈

Sia a vettore corrispondente alla prima riga di una matrice circolante, allora a prende il nome di vettore circolante e la matrice circolante completamente determinata da tale vettore viene indicata con circ(a).

Possiamo considerare le matrici circolanti con la struttura algebrica ereditata

cr,F

M

dalle matrici quadrate a coefficienti in quindi ha struttura di spazio

F,

vettoriale di dimensione r su essendo chiusa per la somma ed il prodotto

F

scalare.

Ciascuna delle strutture algebriche presentate in questo capitolo possiede un elemento particolare detto shifter. Lo shifter delle matrici circolanti è definito da s come:

r  

0 1 0 ... 0

0 0 1 ... 0

  ≡

1 i j + 1 mod r

 

.. .. .

.. (s ) =

s =  

. . r i,j

r 0 altrimenti

 

 

0 0 0 ... 1

 

1 0 0 ... 0

Osserviamo che s = circ((0, 1, 0, . . . , 0)) e che l’insieme delle potenze di s

r r

forma un gruppo ciclico di ordine r.

Ad esempio per r = 3 si ha 

 

 

 1 0 0

0 0 1

0 1 0 3

2 0 1 0

1 0 0

0 0 1 s =

s =

s =

3 

 

 

 3

3 0 0 1

0 1 0

1 0 0

Quindi ogni matrice circolante è esprimibile come combinazione lineare degli elementi del gruppo delle potenze di s : indicata con M la generica matrice

r

circolante, M = circ(a), dove a = (a , a , . . . , a ), allora

0 1 r−1

rr 1 r−1

· · ·

M = a s + a s + + a s

0 1 r−1

r r

1 r−1

· · ·

= a I + a s + + a s

0 r 1 r−1

r r

Possiamo vedere ogni matrice circolante come un polinomio a coefficienti in F

la cui indeterminata è s

r r−1

X

cr,F jr

M { | ∈

= a s a F}

j j

j=0

Alla somma ed al prodotto scalare ereditati dalla struttura matriciale, aggiungiamo il prodotto fra matrici circolanti, che risulta ben definito e compatibile con il prodotto scalare dalla possibilità di esprimere ogni matrice circolante come un polinomio ad indeterminate appartenenti ad un gruppo ciclico. Quindi

cr,F

M ha la struttura di algebra. 2

0. Quattro algebre isomorfe

Algebra dei vettori circolanti

Dato lo spazio vettoriale r-dimensionale sul campo i cui elementi vettoriali

F,

−

hanno convenzionalmente i pedici numerati da 0 ad r 1, vogliamo definire un

prodotto che ne determini la struttura di algebra. Indichiamo con (a) = a

i i

l’elemento dell’i-esimo posto nel vettore, allora per a, b vettori, definiamo il

vettore a ? b, i cui elementi sono determinati dalla sommatoria

X ∀i ∈

a b

(a ? b) = Z

j i−j r

i j∈Z r

che chiameremo prodotto di convoluzione di a per b. Possiamo anche definirlo come il prodotto del vettore a per la matrice circolante definita da b. Ad esempio per r = 3  

b b b

0 1 2

a a a b b b

a ? b = 0 1 2 2 0 1

 

b b b

1 2 0

In questa struttura lo shifter è dato dal vettore (0, 1, 0, . . . , 0), infatti si verifica immediatamente che

a ? (0, 1, 0, . . . , 0) = (0, 1, 0, . . . , 0) ? a = (a , a , . . . , a )

r−1 0 r−2

Possiamo verificare che con il prodotto di convoluzione l’insieme dei vettori non

c

V

nulli formano un semigruppo, quindi l’insieme è un’algebra detta algebra

r,F

dei vettori circolanti.

Algebra FC r

Consideriamo la struttura definita sul gruppo ciclico di ordine r generato da g, indicato con C =< g >, su quale agisce il campo Si tratta dell’algebra i

F.

r

cui elementi sono i polinomi di grado inferiore ad r e la cui indeterminata è il generatore del gruppo ciclico. 2 r−1

{a · · · | ∈

= + a g + a g + + a g a

FC F}

r 0 1 2 r−1 i