Introduzione alla decodifica algebrica dei codici ciclici

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

odi i i li i

L. Giuzzi

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

1 Burst di errore 1

1.1 Premessa . . . 1

1.2 Des rizione dei burst di errore . . . 2

1.3 Limitazioni . . . 3

1.4 Campi di ordine non primo . . . 4

1.5 Codi i prodotto . . . 6

1.6 Interleaving . . . 8

2 Codi i i li i 11 2.1 Sottospazi i li i . . . 12

2.2 Rappresentazione degli spazi i li i . . . 13

2.3 Matri e generatri e di un odi e i li o. . . 14

2.4 Polinomiodi ontrollo di parità . . . 16

2.5 Codi a dei odi i i li i . . . 17

2.6 De odi a dei odi i i li i . . . 19

2.7 Codi i i li iper burst di errore. . . 20

3 Codi i di ReedSolomon 23 3.1 Costruzione di ReedSolomon . . . 23

3.2 Codi a dei odi i di ReedSolomon . . . 24

3.3 De odi a e DFT . . . 25

3.4 Il problema dalla orrezione . . . 26

3.5 Algoritmo di Wel hBerlekamp . . . 28

3.6 Appli azioni dei odi i di ReedSolomon. . . 31

4 Erasures 35 4.1 Generalità . . . 35

4.2 Il anale

q

ario on erasure . . . 36 iii

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

4.3 De odi a di erasures . . . 37

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Burst di errore

1.1 Premessa

I

n al uni sistemi di omuni azione, ome ad esempio il anale binario sim-metri o, laprobabilitàdierroreèlamedesimaperogni bitdiinformazione. In parti olare, la presenza di un errore in una posizione

i

di un vettore ri evutor noninuenzaminimamentelaprobabilità hesi veri hi (omeno)un errorenella posizione

i + 1

. In altri asi,gli erroritendono adessereraggruppati in blo hi. Un esempio è quello dei gra su di un dis o digitale (CD e DVD, si vedano [25, 27, 26℄): la presenza di un grao è asuale, ma i bit he esso rende illeggibili risultano adia enti fra loro. Un altro esempio è quello di un telefono ellulare he sitrova adus ire di operturaperun breve lassodi tempo (ad esempio poi hé la persona he stava parlando si trova a passare innanzi un edi io heblo apartedelsegnale): inquesto asoèestremamenteimprobabile he solo un singolo bit sia an ellato ma ( hiaramente) i dati danneggiati sono adia enti fra loro.

Lo studio di te ni he per arontare la orrezione di burst di errore rive-ste pertanto una profonda valenza prati a. Ci sono due possibili appro i al problema:

a. l'utilizzodi odi i i li iopportuni;

b. la ostruzione di odi i intre iati. 1

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

1.2 Des rizione dei burst di errore

La nozione burst di errore è strettamente legata a quella di atena i li a. Pre-mettiamodue denizioniformali.

Denizione 1.1. Siav

= (v

0

v

1

· · · v

n−1

)

un vettore;due omponenti

v

i

, v

j

di v sono dette i li amente onse utive se

j = i + 1

oppure

i = n − 1

e

j = 0

. Una su essione di

k

≤ n

omponenti

v

i

0

, v

i

1

, . . . v

i

k

i li amente onse utive di un vettore v è detta atena i li a di lunghezza

k

.

Denizione 1.2. Un errore di tipo burst (detto an he burst di errore) di lun-ghezza

b

è un vettore l le ui omponenti non nulle sono ontenute in una atena i li a di lunghezza

b

. Una tale atena inizia e nis e sempre on una omponente non nulla.

Due osservazioni sono opportune:

a. Una atena i li apuò andareoltre lanedella sequenza in ui ompare,per ontinuaredall'inizio. Se iònona ade,diremounsiattoburstnon i li o. b. La prima e l'ultimaposizione del vettore l sono si uramenteerrate.

I burst di errore possono sempre essere des ritti in forma  ompressa ome segue. Supponiamo he esiaun vettoredierrore he ontieneun burstdierrore. Denizione 1.3. Ilformatodel burst ine è ilsottovettorep die formatodalle omponentinonnulledie. Lalunghezzadipsaràdenotata on

|

p

|

. Laposizione

l

del burst è l'indi e della prima omponente non nulla di e. Indi heremo un erroredi formatope posizione

i

ol simbolo

(

p

, i)

. Tale oppiaordinata èdetta des rizione di errore

Notiamo hedalla onos enzadiped

i

èsemprepossibileri ostruireilvettore e.

Esempio 1.1. Osserviamo he, in generale, un vettore di errore può essere de-s ritto in modi diversi. Sia ad esempio e

= (01000 00110)

. Sono possibili per e le tre des rizioni in Tabella 1.1. È immediatoveri are he ogni vettore e di peso

w

ammetteesattamente

w

des rizionidierenti.

Il Teorema 1.1 onsente di ovviare all'in onveniente della man anza di uni- ità della s rittura he si è visto nell'Esempio 1.1. Prima di pro edere alla dimostrazioneè bene premettere una denizionee un lemma.

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Formato Posizione Lunghezza

100 00011

1

8

11001

6

5

10010 00001

7

10

Tabella1.1: Des rizioni possibiliper un burst di errore di peso

3

Denizione 1.4. Sia e un errore e sia

(

p

, i)

una des rizione di errore. Le om-ponenti di e non in p formanouna atena i li a di

0

, he inizia ( i li amente) nella posizione

i + |

p

|

+ 1

e nis e nella posizione

i − 1

. L'insieme degli indi i orrispondenti atale atena èdetto atena zero di

(

p

, i)

.

Lades rizione deglierrorièessenzialmenteuni a, omeenun iatonel seguen-te teorema.

Teorema 1.1. Sia e un vettore di errore di lunghezza

n

on due des rizioni di errore del tipo

(

p

1

, i

1

)

e

(

p 2

, i

2

)

. Allora, se

|

p 1

|

+ |

p 2

|

≤ n + 1

abbiamo

(

p 1

, i

1

) = (

p 2

, i

2

)

.

Conseguenzaimmediatadel Teorema1.1 è il seguente orollario.

Corollario 1.2. Ogni vettore di errore e ammette al più una des rizione ome burst di errore di lunghezza minore o uguale a

(n + 1)/2

.

Siosservi heè omunquepossibileavereburst dierrore he nonammettono tale des rizione dierrore. Questo èil aso, adesempio, di tutti queglierrori he hanno peso strettamente maggiore di

(n + 1)/2

.

1.3 Limitazioni

In generale, la apa ità orrettiva di un odi e lineare è legata al numero di sindrome diverse disponibili. In parti olare, un

[n, k, d]

 odi e su

F

q

può, a priori, orreggere al più

q

n−k

diverse tipologie di errore.

Rammentiamo he, posto

t =

⌊(d − 1)/2⌋

si può dire he ogni odi e di distanza minima

d

è si uramente in grado di orreggere

t

errori asuali. In questo paragrafo forniremodelle limitazionisul numero

b

di burst di errore he un tale odi e è in gradodi orreggere.

Un burst di errore di

b

bit è des ritto mediante un formato di errore he è una atena i li a di lunghezza

b

. Al ne di determinare quanto lungo un

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

burst orreggibile possa essere è dunque ne essario al olare il numero di tutte le atene i li he di lunghezza

n

. Per sempli ità i limitiamoal asobinario. Teorema 1.3. Fissato

n

, sia

b

un intero tale he

1

≤ b ≤ (n + 1)/2

. Allora, esistono esattamente

n2

b−1

_{+ 1}

vettori di lunghezza

n

su

F

2

he ontengono atene i li he di lunghezza al più

b

.

Il seguente teorema è una riformulazione della limitazione di Hamming per odi i binari he orreggano burst di errore alla lu e del risultato pre edente. Osserviamo he fra le ipotesi non si ri hiede he il odi e sia lineare.

Teorema 1.4 (Limitazione di Hamming per burst di errore). Sia

1

≤ b ≤

(n + 1)/2

. Un odi e binario

C

di lunghezza

n

he orregge tutti gli burst di errore di lunghezza al massimo

b

ontiene al più

2

n

_/(n2

b−1

_{+ 1)}

parole. Dimostrazione. Peril Teorema 1.3vi sono esattamente

n2

b−1

_{+ 1}

possibili vet-tori di errore burst di peso non superiore a

b

. Siano

M

il numero delle parole di odi e di

C

. Il numero di parole he dieris ono da un elemento di

C

in un vettore i li o di peso al più

b

è dunque

M(n2

b−1

_{+ 1)}

. Poi hé tutti tali vettori si trovano in

V

n

_(F

2

)

, ne segue he

M(n2

b−1

_{+ 1)}

_{≤ 2}

n

.

L'analogo della limitazione di Singleton per odi i

b

 orrettori è ontenuta nel seguente teorema.

Teorema 1.5 (Limitazione di Reiger). Sia

0

≤ b ≤ n/2

. Un

[n, k]

 odi e binario

C

in grado di orreggere burst di errore di lunghezza al più

b

deve soddisfare

r

≥ 2b,

ove

r = n − k

è la ridondanza di

C

.

1.4 Campi di ordine non primo

I ampi niti più fa ili da implementare sono quelli

F

p

≃ Z

p

, ontenenti un numero primodi elementi. Infatti, ogni elemento di tali ampi è rappresentato da esattamente un intero

z

on

0

≤ z ≤ p − 1

e le operazioni di somma e prodotto fradue elementi

a, b

∈ F

p

possonoessere implementatesempli emente moltipli ando (o sommando) fra loro gli interi he rappresentano gli elementi

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

L'implementazionedi

F

q

, ove

q = p

h

è una potenza non banale di un primo

p

presenta maggioridi oltà, sia da un punto di vista teori o (è ne essario de-terminare unopportunopolinomioirridu ibiledi grado

h

su

F

p

) heprati o. In parti olare,di ilmenteunmi ropro essorenon dedi atopossiede unaversione ottimizzata delle operazionidi prodotto he servono.

I odi i orrettori su ampi di ordine non primo, d'altro anto, godono di al une importantiproprietà ne he giusti ano lostudio. In eetti,moltidei o-di i implementati on retamenteinappli azioniditipo ommer iale(CD,DVD, TelevisioneDigitale,et .) sono denitisu ampidiquestotipo. Questoèil aso, ad esempio,dei odi i di ReedSolomon, he saranno studiati nel Capitolo 3.

Inquestoparagrafomostreremounodeivantaggipiùimportanti hesihanno lavorando on un odi e

C

denito su di un ampo di ordine omposto: il fatto he

C

risultain modo naturalein grado di orreggere un numero di errori i li i moltopiùelevatorispettoquanto isipotrebbeattendereapartiredalladistanza minima.

Sianodunque

q

una potenza di primoe

m

≥ 1

un intero.

Teorema 1.6. Dato un

[n, k]

 odi e

C

su

F

q

m

in grado di orreggere errori burst di lunghezza al più

b

, esiste sempre un

[mn, mk]

odi e

C

′

su

F

q

in grado di orreggere almeno

(m − 1)b + 1

burst di errore.

Dimostrazione. Fissiamounabase

B

di

F

q

m

,visto omespaziovettorialesu

F

q

di dimensione

m

.

Consideriamoil

[mn, mk]

 odi e

C

′

su

F

q

ottenutoapartireda

C

sostituendo adognielementodel odi eoriginarioilvettoresu

F

q

helorappresentarispetto

B

, e sia

π :

C 7→ C

′

l'appli azione he realizza questa trasformazione. Ilteorema ora segue osservando he un vettore r

′

∈ C

′

, ontenente un burst di errore on lunghezza al più

(m − 1)b + 1

, viene trasformato da

π

−1

in un vettore r

∈ C

, ontenente un burst di errore di lunghezza al più

b

. La situazione è illustrata nella Figura 1.1. Ne segue he il vettore r può essere orretto in un vettore e he

′

= π(c)

è la parola orrettain

C

′

.

È importante osservare he l'ipotesi he gli errori siano burst è essenziale per la dimostrazione del Teorema 1.6. Infatti, la distanza minima di

C

e quella di

C

′

oin idono, per ui il numero

t

di errori generi i he entrambi i odi i possono orreggere è il medesimo. Come suggeris e la Figura 1.1, quando

m

è abbastanza grande non è ne essario he il odi e di partenza su

F

q

m

possegga proprietà parti olari per poter orreggere numerosiburst di errore.

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

F

q

F

q

m

e

′

≤ (m − 1)b + 1

e

≤ b

Figura1.1: Codi i

q

m

ari e odi i

q

ari

Per on ludere, osserviamo he, in generale, un odi e

t

 orrettore lineare può essere utilizzato per orreggere

t

errori oppure per identi arne

d − 1 = 2t

, ove

d

è la distanza minima. Le due modalità non possono solitamente essere impiegate ontemporaneamente, in quanto in presenza di un numero

h > t

di erroril'algoritmodi de odi a he er alaparola di odi e piùvi inaal vettore ri evuto fornirebbe un risultato errato. Per gli errori i li i è talvolta possibile faredi meglio,utlizzandodei odi i i li iopportuni, omesi vedrànelseguente apitolo.

1.5 Codi i prodotto

Una generalizzazionedella nozione di odi e in serie èquella di odi e prodotto. Talenozioneri hiededi appli arepiùoperazionidi odi ainserie suopportuni insiemi di parole. È importante osservare he in tale ostruzione entrambi i odi i

C

1

e

C

2

ostituenti possono avere parametri arbitrari.

Siano dunque

[n

1

, k

1

]

,

[n

2

, k

2

]

rispettivamente i parametri di

C

1

e

C

2

Le ostruzione prodotto orrisponde a odi are

k

2

parole di

C

1

in parallelo e poi ad appli are a tali parole

n

1

odi he in parallelo mediante

C

2

, ome illustrato in Figura 1.2. La struttura delle parole del odi e osì ottenuto è mostrata in Figura1.3.

Denizione 1.5. Siano

A, B

due matri irispettivamente

m

1

× n

1

e

m

2

× n

2

. Il prodotto se ondo Krone ker o prodotto diretto

A

⊗ B

di

A

on

B

èla matri e

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Esempio 1.2. Siano

A =

h

1 2

i

e

B =

"

1 0

1 2

#

. Allora,

A

⊗ B =

"

1 0 2 0

1 2 2 4

#

.

Ri ordiamo he il prodotto tensoriale di due spazivettoriali

V, W

èlo spazio vettoriale

V

⊗ W

generato da tutti gli elementi della forma

v

⊗ w

on

v

∈ V

1

,

w

∈ V

2

he soddisfano le regole

(v

1

+ v

2

)

⊗ w = v

1

⊗ w + v

2

⊗ w,

v

⊗ (w

1

+ w

2

) = v

⊗ w

1

+ v

⊗ w

2

,

α(v

⊗ w) = (αv) ⊗ w = v ⊗ (αw).

Da questetre aermazionisegue

v

⊗ w = 0

se, e soltanto se,

v = 0

oppure

w = 0.

Osserviamoin parti olare hese

C

1

è un odi e onmatri e generatri e

G

1

e

C

2

è un odi e on matri e generatri e

G

2

, allora lo spazio vettoriale

C

1

⊗ C

2

ha matri e generatri e esattamente

G

1

⊗ G

2

.

Forniamoora una denizioneformale di odi e prodotto.

Denizione1.6. Siano

C

1

,

C

2

due odi i onmatri igeneratri irispettivamente

G

1

,

G

2

. Il odi e prodotto

1

C

1

⊗C

2

èil odi ela uimatri egeneratri eè

G

1

⊗G

2

.

Teorema1.7. Siano

C

1

e

C

2

rispettivamenteun

[n

1

, k

1

, d

1

]

eun

[n

2

, k

2

, d

2

]

o-di e lineare. Allora il odi e prodotto

C

1

⊗ C

2

ha parametri

[n

1

n

2

, k

1

k

2

, d

1

d

2

]

. Dimostrazione. È immediato vedere he la lunghezza di

C = C

1

⊗ C

2

è

n

1

n

2

. Inoltre ogni parola di

C

1

⊗ C

2

è della forma

v

1

⊗ v

2

on

v

1

∈ C

1

e

v

2

∈ C

2

. In parti olareunaparolahapesominimoin

v

1

⊗ v

2

∈ C

1

⊗ C

2

hapesominimose,e soltantose,

v

1

hapesominimoin

C

1

e

v

2

hapesominimoin

C

2

. A questopunto è immediatovedere he

w(v

1

⊗ v

2

) = w(v

1

)w(v

2

) = d

1

d

2

,

per ui la distanza minima di

C

1

⊗ C

2

è

d

1

d

2

. Inne, ome sopra osservato, tutte le righe della matri e

G

1

⊗ G

2

sono linearmente indipendenti, per ui la dimensione del odi e prodotto èesattamente

k

1

k

2

.

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

u

Divisore Codi atore

C

1

1

Codi atore

C

1

2

. . . Codi atore

C

1

k

2

Co di atore

C

2

1

Co di atore

C

2

2

. . .

Co di atore

C

2

n

1

Assemblatore

v

u

1

u

2

u

k

2

v

1

v

2

v

n

1

Figura1.2: Codi atoreprodotto

Teorema 1.8. Siano

C

1

, C

2

ome sopra e siponga

t

i

=

⌊(d

i

− 1)/2⌋

. Il odi e prodotto

C = C

1

⊗ C

2

è ingrado di orreggere tutte le sequenze dierroriburst di lunghezza al più

b =

max

{n

1

t

2

, n

2

t

1

}.

Dimostrazione. Osserviamo he, per ogni

0

≤ j ≤ n

2

− 1

, al variare di

k

le omponenti

(j + kn

1

)

esime di una paroladi odi e di

C

sono esattamente

n

2

e formanounaparoladi odi eper

C

2

. Il odi e

C

2

puòessereusatoper orreggere

t

2

errori in ognunadi queste

n

1

parole. Ne segue he, qualoragli errori siano di tipoburst, è possibile orreggerne

t

2

n

1

. Un ragionamento analogomostra ome usando

C

2

sia possibile orreggere

t

1

n

2

burst di errore, da ui si determina il valore di

b

.

Esempio 1.3. Siano

C

1

e

C

2

due opie del odi e di Hamming di parametri

[7, 4, 3]

. Allora

C

1

⊗ C

2

è un

[49, 16, 9]

 odi e lineare apa e di orreggere

4

errori in qualsivogliaposizione e al più

7

burst di errore.

1.6 Interleaving

Un aso parti olare della ostruzione prodotto vista nel Paragrafo 1.5 è quello dell'interleaving di odi i.

Il odi e banale di lunghezza

n

su

F

q

è l'uni o odi e di parametri

[n, n, 1]

. Denoteremotale odi e ol simbolo

I

(n)

.

1

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

0

1

k

2

− 1

n

2

− 1

0

1

k

1

− 1

n

1

− 1

Ridondanza orizzontale Ridondanza verti ale

Figura1.3: Struttura di una parolanel odi e prodotto

Denizione 1.7. Si di e blo k interleaved ode di profondità o grado

n

otte-nuto apartire da

C

il odi e

C

(n)

dato da

C

(n)

= C

⊗ I

(n)

.

Osserviamo he nel aso di un odi e

n

2

interleaved ottenuto a partire da un odi e

C

di parametri

[n

1

, k

1

]

, le parole vengono ad essere disposte in una matri e

n

2

× n

1

, ome illustratoin Figura 1.4, ove

v

i

= (v

i,1

, v

i,2

, . . . , v

i,n

1

)

è una parola di

C

per

1

≤ i ≤ n

2

L'importanza dei odi i on interleaving risiede nel fatto he è possibile utilizzare per

C

(n

2

)

il medesimo algoritmo di de odi a he per

C

. In parti olare, sempre fa endo riferimento alla Figura 1.4

le omponentidi

C

(n

2

)

vengono trasmesse per olonna, ioè nell'ordine v

= (v

1,1

, v

2,1

,

· · · , v

n

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

v

1,1

v

1,2

· · ·

v

1,n

1

v

2,1

v

2,2

· · ·

v

2,n

1

. . . . . .

v

n

2

,0

v

n

2

,1

· · · v

n

2

,n

1

Figura1.4: Struttura di un odi e on interleaving

In fase di de odi a si deve dunque innanzi tutto ri ostruire la tabella olonna per olonna e, su essivamente, pro edere a de odi are e orreggere riga per riga.

n

2

n

1

b

Figura 1.5: Burst di errore e odi i on interleaving Un odi e oninterleaving

C

(n)

possiede esattamentela stessa distanza mini-madel odi e dipartenza

C

,per ui essoè ingradodi orreggereesattamentelo stessonumerodierrorigeneri i. D'altro antotali odi i risultanoestremamente prati i per orreggere burst di errore. Supponiamo in parti olare he si veri- hino

b

errori in sequenza in un messaggio ri evuto r. La situazione è quella des ritta in Figura 1.5 per un odi e

C

(n

2

)

, ove

C

ha lunghezza

n

1

e raggio di impa hettamento

e

. Osserviamo he in ogni riga solamente

b/n

2

omponenti risultano alterate. Ne risulta he se

b < en

2

, allora ogni riga, he è un vettore di lunghezza

n

1

su ui appli hiamo il odi e

C

, ontiene un numero di errori inferioread

e

e dunque, mediante

C

è possibile ri ostruirnei valori originari.

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Codi i i li i

U

n odi e

C

èunivo amenteidenti atodall'elen odelleparole heesso ontiene;d'altro anto questonon èdi per sè su iente per implemen-tare prati amentelo stesso.

Infatti,l'implementazione on retadiun odi e orrettore onsisteinalmeno tre distinti algoritmi:

1. Un algoritmodi odi a;

2. Un algoritmoper individuaree eventualmente orreggere gli errori; 3. Un algoritmodi de odi a.

Osserviamo he, a priori, non è ne essario essere in grado s rivere la lista di tutte le parole in

C

, an he se questo può aiutare molto nel determinarne le proprietà.

Un generi o odi e a blo hi, privo di ulteriore struttura può essere fornito solamenteelen andotuttiisuoielementi. Per aratterizzaretutteleparolediun

[n, k]

 odi e lineare

C

, al ontrario, basta fornire

k

vettori distinti he formino una base dello stesso.

In questo apitolo onsidereremo una lasse parti olare di odi i lineari: i odi i i li i. Questa famigliadi

[n, k]

 odi i lineari gode di notevoli proprietà, fra ui:

a. Sono ostruitia partire daun singolovettore; b. Ammettonodegli algoritmidi de odi a e ienti;

. Risultanoparti olarmente omodi per orreggere al une tipologie di errore; 11

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

d. Possono essere des ritti ed enumerati in modo esaustivo mediante la loro relazione on struttrure algebri he.

2.1 Sottospazi i li i

Iniziamoquestoparagrafo onsiderando un tipoparti olare di sottospazi di uno spazio vettoriale

V

.

Denizione 2.1. Un sottospazio

S

di

V

n

(F)

è detto sottospazio i li o se omunque dato

(a

0

a

1

. . . a

n−2

a

n−1

)

∈ S

si ha sempre

(a

n−1

a

0

a

1

. . . a

n−2

)

∈ S

Osserviamo he tutto lo spazio

V

n

(F)

, osì ome il sottospazio

{

0

}

formato dal solo vettore nullo sono sottospazi i li i. Tali sottospazi i li i sono detti banali.

Sia v

= (v

0

v

1

. . . v

n−1

)

∈ V

un vettore e sia

σ = (1 2 . . . n − 1)

. Un vettore w

∈ V

è una permutazione i li a di v se esiste un intero

i

∈ {0, 1, . . . n − 1}

tale he

w

= (v

σ

i

(0)

v

σ

i

(1)

. . . v

σ

i

(n−1)

) = σ

i

₍

v

).

In parti olare, in questo aso il vettore w può s riversi ome

w

= (v

i

v

i+1

. . . v

i+n−1

),

ove gli indi i sono daintendersi ridottimodulo

n

.

Teorema 2.1. Sia

S

un sottospazio i li o di uno spazio vettoriale

V

. Al-lora,

S

ontiene tutte le possibili permutazioni i li he di un suo qualsiasi elemento.

Dimostrazione. Sia s

= (s

0

s

1

. . . s

n−1

)

∈ S

e ssiamo

i

∈ {0, 1, . . . n − 1}

. Chia-ramente

σ

0

₍

s

) =

s

∈ S

; per denizione di sottospazio i li o si ha he an he

σ

1

₍

s

)

∈ S

. D'altro anto se

σ

i

₍

s

)

∈ S

, allora

σ

i+1

₍

s

) = σ(σ

i

₍

s

))

∈ S

. Ne segue, per induzione, he tutte le possibili permutazioni i li he di s appartengono ad

S

.

I odi i i li isono dei asi parti olari dei odi i lineari.

Denizione 2.2. Un odi e i li o sopra

F

è un odi e lineare su

F

he è al ontempo un sottospazio i li o di

V

n

(F)

.

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

2.2 Rappresentazione degli spazi i li i

Ilmetodopiù onvenienteper rappresentare un sottospazio i li o

C

è quellodi onsiderarlo ome un opportuno insiemedi polinomi.

In parti olare,per ogni vettore

= (c

0

c

1

· · · c

n−1

)

∈ C,

è sempre possibiles rivere un polinomio

c(x) = c

0

+ c

1

x +

· · · + c

n−1

x

n−1

he lo rappresenta. Lo spazio vettoriale

V

n

(F

q

)

, di dimensione

n

è dunque rappresentato dall'insieme di tutti i polinomi in

x

su

F

q

aventi grado al più

n − 1

.

Èpossibileintrodurrein

V

n

(F

q

)

unaoperazionedi moltipli azione: il prodot-to didue vettoriè determinato al olandoil prodottousuale frai polinomi asso- iatie, su essivamente al olandoneil restoquandolisi divideper

(x

n

_{− 1)}

. La struttura algebri a

C

osì ostruita è l'anello quoziente di

F[x]

rispetto l'ideale generato dal polinomio

(x

n

_{− 1)}

.

Per unfondamentaleteorema dinatura algebri aquestoanello è

1

generato; in altre parole esiste un elemento

g(x)

∈ C

tale he le permutazioni i li he di

g(x)

ostituis onoun insiemedi generatori per

C

.

In terminipiù formali, sia

C

un odi e i li o diverso da

{

0

}

. Allora

1. esiste un uni o polinomiomoni o

g(x)

avente grado minimo

r

in

C

, dim

C =

n − r

e inoltre

C = {g(x)q(x) : q(x) ∈ F[x];

deg

q(x) < n − r}.

2. Ilpolinomio

g(x)

divide

x

n

_{− 1}

in

F[x]

.

Ilseguente teorema aratterizza tutti i odi i i li idi lunghezza

n

.

Teorema 2.2. Vi è una orrispondenza biunivo a fra i sottospazi i li i di

V

n

(F)

e i polinomi moni i

g(x)

∈ F[x]

he sono divisori di

f(x) = x

n

_{− 1}

. Esempio 2.1. Consideriamotutti i possibili odi i i li ibinari di lunghezza

7

. Tali odi i sono dunque sottospazidi

V

7

(Z

2

)

. Poniamo

f(x) = x

7

_{− 1}

. In

Z

2

tale polinomio

f(x)

si fattorizza in irridu ibili ome

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

pertantoi divisori moni idi

f(x)

sono tutti e soli i seguenti

g

1

(x) = 1

g

2

(x) = x + 1

g

3

(x) = x

3

+ x

2

+ 1

g

4

(x) = x

3

+ x + 1

g

5

(x) = (x + 1)(x

3

+ x

2

+ 1)

g

6

(x) = (x + 1)(x

3

+ x + 1)

g

7

(x) = (x

3

+ x

2

+ 1)(x

3

+ x + 1)

g

8

(x) = f(x).

Ne segue he

V

7

(Z

2

)

ontiene esattamente

8

sottospazi i li i.

A titolo di esempio, osserviamo he il polinomio

g

6

(x)

genera il sottospazio i li o

S = {(0000000), (1011100), (0101110), (0010111)

(1001011), (1100101), (1110010), (0111001)}.

Similmente,il polinomio

g

7

(x)

genera il sottospazio i li o

S = {(0000000), (1111111)}.

2.3 Matri e generatri e di un odi e i li o

Osserviamo he la forma più naturale per la matri e generatri e di un odi e i li o è quella a s ala

1

. In parti olare, la matri e quadrata ottenuta onside-randole prime

k = n − r

olonne è triangolaresuperiore e hadeterminante non nullo. Pertanto,leprime

k

posizionibastanoari ostruire,inassenzadierrori,la parola originariamentetrasmessa e sono dunque di informazione. D'altro anto questa forma i li a non è quasi mai standard, per ui la odi a non risulta sistemati a.

Un'altraformainteressante, heèsemprepossibiledareallamatri e genera-tri e, è quellaantisistemati a, ottenuta mediante la ostruzione des ritta qui diseguito. Taleformasirivelaparti olarmente omodainfasedi implementazio-nedialgoritmidide odi a,inquantouna opiadellaparolaoriginalesiritrova, in questo aso, nelle ultime

k

posizioni trasmesse. Sia

C

un

[n, k]

 odi e i li o

1

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

sopra

F

on polinomio generatore

g(x)

. Il nostro obiettivo è dunque quello di determinare per

C

una matri e generatri e dellaforma

G = (R I

k

)

.

Pro ediamo ora alla ostruzione della matri e

G

. 1. Per ogni

i = 0, 1, . . . , k − 1

, si divida

x

n−k+i

per

g(x)

, osi hé

x

n−k+i

= q

i

(x)g(x) + r

i

(x),

ove deg

r

i

(x) <

deg

g(x) = n − k

oppure

r

i

(x) = 0

; 2. Si ponga

p

i

(x) = x

n−k+i

− r

i

(x) = q

i

(x)g(x)

∈ C;

3. Osserviamo he deg

p

i

(x) −

deg

0

_p

i

(x)

≥ i;

4. Ne segue he onsiderando i oe ienti di

p(x) = x

n−k+i

_{− r}

i

(x)

ome righe di una matri e, otteniamouna struttura del tipo

0

r − 1

r

n − 1















−r

0

(x)

1

0

. . .

0















−r

1

(x)

0

1

. . . . . . . . . . . . . . . . . .

0

−r

k−1

(x)

0 . . .

0

1

ovverouna matri e

G = (R I

k

)

in uile righedi

R

orrispondono a

−r

i

(x)

on

0

≤ i ≤ k − 1

;

5. Ognirigadi

G

èunaparoladi

C

;inoltrelerighesonotuttefralorolinearmente indipendenti, per ui

G

è una matri e generatri e per il odi e

C

avente la formadesiderata.

Esempio 2.2. Si onsideri nuovamente il

[7, 4]

 odi e i li o generato dal poli-nomio

1 + x + x

3

. Per mezzo dell'algoritmoeu lideo, determiniamo

x

3

_{= (1)(x}

3

_{+ x + 1) + (1 + x)}

x

4

= (x)(x

3

+ x + 1) + (x + x

2

)

x

5

= (x

2

+ 1)(x

3

+ x + 1) + (1 + x + x

2

)

x

6

= (x

3

_{+ x + 1)(x}

3

_{+ x + 1) + (1 + x}

2

_),

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

In tal modoresta denita la seguente matri e generatri e:

G =











1 1 0 1 0 0 0

0 1 1 0 1 0 0

1 1 1 0 0 1 0

1 0 1 0 0 0 1











= (R I

4

),

on

R =











1 1 0

0 1 1

1 1 1

1 0 1











.

Come già osservato, le righe di

R

orrispondono ai vettori dei oe ienti dei polinomi

1 + x

,

x + x

2

,

1 + x + x

2

ed

1 + x

2

. Una sequenza di informazione m

= (1011)

viene odi atamediante

G

ome

=

m

G = (100 1011)

.

2.4 Polinomio di ontrollo di parità

La matri e generatri e di un odi e i li o può essere ostruita a partire da un singolo polinomio

g(x)

. Similmente è possibile determinare una matri e di ontrollo di parità, utilizzandoun altro polinomio.

Denizione 2.3. Sia

h(x) =

P

k

i=0

a

i

x

i

, on deg

h(x) = k

. Si di e polinomio re ipro o

h

R

(x)

di

h(x)

il polinomiodatoda

h

R

(x) =

k

X

i=0

a

k−i

x

i

.

È immediatovedere he,poi hédeg

h(x) = k

, ilpolinomio

h

R

(x)

può sempre s riversi formalmente ome

x

k

_h(1/x)

.

Denizione2.4. Datoun odi e i li o

C

,il odi e invertito

C

R

di

C

è il odi e ottenuto da

C

invertendo ogni parola di odi e.

In parti olare,

(c

0

c

1

. . . c

n−1

)

∈ C

se, e soltanto se,

(c

n−1

c

n−2

. . . c

1

c

0

)

∈ C

R

. Notiamo he se

g(x)

è un generatore per

C

, allora

g

−1

0

g

R

(x)

è un generatore moni oper

C

R

.

Denizione 2.5. Sia

C

un odi e i li o on polinomio generatore

g(x)

. Il polinomio di ontrollo di parità di

C

è il polinomio

h(x)

tale he

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Osserviamo he in

F[x]

n

si ha

(g(x) + (x

n

_{− 1)) (h(x) + (x}

n

_{− 1)) = 0 + (x}

n

_{− 1).}

Il seguente teorema fornis e la motivazione per il nome dato al polinomio

h(x)

nella Denizione2.5.

Teorema 2.3. Sia

g(x)

∈ F[x]

un divisore moni o di grado

n − k

di

f(x) =

x

n

_{− 1}

e sia

C

il

[n, k]

 odi e i li o he esso genera. Denotiamo on

h(x) =

(x

n

_{− 1)/g(x)}

il polinomio di ontrollo di parità di

C

. Allora,

C = {c(x) ∈ F[x] :

deg

c(x)

≤ n, c(x)h(x) = 0

(

mod

x

n

_{− 1)}.}

In altre parole, le parole

c(x)

del odi e

C

sono univo amente determinate dal fatto he il prodotto

c(x)h(x)

è divisibileper

x

n

_{− 1}

.

È ora possibile mostrare ome i on etti di polinomiogeneratore, polinomio re ipro o e polinomio di ontrollo di parità sono strettamente asso iati a quel-lo di odi e ortogonale. In tale modo si potrà fornire un metodo diretto per determinare

h(x)

.

Teorema 2.4. Sia

g(x)

il polinomio generatore di un

[n, n − r]

 odi e i li o

C

sopra

F

. Il odi e ortogonale

C

⊥

è il odi e i li o generato da

h

R

(x)

ove

h(x)

è il polinomio di ontrollo di parità di

C

.

Osserviamo he, in generale,

h

R

(x)

non èun polinomiomoni o.

2.5 Codi a dei odi i i li i

Nei paragrapre edenti siè visto ome sia possibile ostruirela matri e genera-tri e

G

di un

[n, k]

 odi e i li o

C

apartire dal suo polinomiogeneratore

g(x)

. In parti olare, si può assumere he talematri e abbia la forma

G = (R I

k

)

ome fatto nella ostruzione di Pagina 14. In eetti, vedremo ora ome sia possibile odi are unasequenza di informazioneasenza dover ne essariamente s rivere espi itamente tuttala matri e.

Per ogni

i = 0, 1, . . . , k − 1

hiamiamo

r

i

(x)

il polinomioin

x

tale he

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Rammentiamo he data una sequenza di informazione a

= (a

0

, a

1

, . . . , a

k

)

, possiamo sempre ostruire un polinomio

a(x) =

k−1

X

i=0

a

i

x

i

.

Poi héla formadella matri e

G

è antisistemati a,ogni paroladi odi e onterrà i

k

simbolirappresentanti l'informazione nelleultime omponenti,mentre i sim-boli di ontrollo di parità saranno i primi

n − k

. Pertanto, per determinare la rappresentazione di

a(x)

basta trovare l'uni ovettore di

C

ontenentei termini

a

0

x

n−k

a

1

x

n−k+1

. . .

a

k

x

n

.

In altre parole, si deve s rivere un polinomio

q(x)

tale he

x

n−k

a(x) = q(x)g(x) + t(x),

(2.1)

ossia

q(x)g(x) = −t(x) + x

n−k

a(x),

on

t(x) = 0

oppure deg

t(x) <

deg

g(x) = n − k

.

Osserviamo he la formadi una parola di odi e risulta

[

−a

0

r

0

(x)

a

0

0

. . . 0

]+

[

−a

1

r

1

(x)

0

a

1

. . .

0

]+

[

. . . . . . . . . . . . . . .

]+

[

−a

k−1

r

k−1

(x)

0

. . . 0

a

k−1

]=

[

−t(x)

a

0

a

1

. . . a

k−1

]

;

In parti olare, i simboli di ontrollo di parità,asso iati all'informazione rappre-sentata da

a(x)

, sono proprio i oe ienti di un polinomio

−t(x)

dove

t(x) =

P

k−1

i=0

a

i

r

i

(x)

. Da questo fatto, per la relazione (2.1), dis ende he il polinomio

t(x)

èesattamenteilrestodelladivisionedi

x

n−k

_a(x)

perilpolinomiogeneratore del odi e

g(x)

.

Des riviamooraformalmenteun primo on iso algoritmodi odi a,per un

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Algoritmo 2.1 (Codi a odi i i li i). Dati:

D1 un

[n, k]

 odi e i li o

C

on polinomiogeneratore

g(x)

; D2 un vettore di informazione a

= (a

0

, a

1

, . . . , a

k−1

)

.

Determinare:

G1 un vettore s

= (s

0

, s

1

, . . . , s

n−k−1

)

di simboli di ontrollo parità tale he

(

a

,

s

)

∈ C

Si pro eda ome segue: Si pongag

= (g

0

g

1

. . . g

n−k−1

)

.

S1 Porre

s

j

= 0

per

0

≤ j ≤ n − k − 1

. S2 Porre

i = 1

.

S3 Distinguiamodue asi:

(a) Se

a

k−i

= s

n−k−1

, porre

s

j

= s

j−1

per

j

he va da

n − k − 1

ad

1

ed

s

0

= 0

.

(b) Se

a

k−i

6= s

n−k−1

,porre

s

j

= s

j−1

+ g

j

per

j

he va da

n − k − 1

ad

1

ed

s

0

= g

0

.

S4 Se

i > k

fermarsi,altrimenti tornare al passo3.

Ilgrandevantaggio di questoalgoritmoè he non si ri hiede di memorizzare tuttalamatri egeneratri e

G = (R I

k

)

enemmenodi al olareaprioriipolinomi

r

i

(x)

.

2.6 De odi a dei odi i i li i

An he la de odi a di un odi e i li o può essere implementatain modo parti- olarmente on isoin terminidi operazioni fra polinomi.

Alsolito,ssiamoun

[n, k]

 odi e i li o

C

sopra

F

, onpolinomiogeneratore

g(x)

. Da quanto visto nel pre edente Paragrafo 2.5, è sempre possibile rappre-sentarelaoperazionedi odi amedianteunamatri egeneratri e

G

dellaforma

G = (R|I

k

)

. Conseguentemente, lamatri e di ontrollo di parità di

C

deve avere la forma

H =



I

n−k

|

− R

T



Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

In terminidei polinomi

r

i

(x)

si vede immediatamente he

H =













1

0

. . . 0

r

0

(x)

r

1

(x)

. . .

r

k−1

(x)

0

1

. . . . . . . . . . . . . . .

0

0 . . .

0

1













.

Sia adesso

h(x)

il polinomiodi ontrollo di parità di

C

e onsideriamoora una sequenza ri evuta n. Poniamo s

=

n

H

T

; pertanto, il vettore s è la sindrome asso iata a n. Rammentiamo he, per ostruzione, la matri e di ontrollo di parità

H

è la matri e generatri e di un odi e i li o on polinomio generatore

h

R

(x)

. Inparti olare,sivede heil al olodellasindrome orrisponde,intermini polinomiali, ad un prodotto del polinomio

s(x)

asso iato alla sequenza ri evuta sperilpolinomio

h(x)

,il tutto al olatonell'anello

F[x]

n−k

. C'èunaparti olare onvenienza nello s egliere per

C

una matri e di ontrollo di parità

H

del tipo della (2.2), ome dimostra il seguente teorema.

Teorema 2.5. Consideriamo un

[n, k]

 odi e i li o

C

sopra

F

generato da

g(x)

. Siano v

∈ F

n

e s rispettivamente un vettore e la sua sindrome e indi hiamo on

v(x)

e

s(x)

le orrispondenti rappresentazioni polinomiali. Allora,

s(x)

è il resto della divisione di

v(x)

per

g(x)

.

In altre parole, il Teorema 2.5 mostra he la sindrome di una sequenza può esseredeterminatasempli ementeeseguendounadivisionefrapolinomimediante l'algoritmoeu lideo. Questo,ingenerale,risultamoltopiùsempli edarealizzare, he non il al olare la sindromemedianteil prodotto matri e/vettore.

2.7 Codi i i li i per burst di errore

Prima di on ludere osserviamo he esistono dei odi i i li i he sono ontem-poraneamenteingradodide odi areburst errorseerrori generi i. Questi sono i osiddetti odi i fortemente

b

burst error orre ting.

In parti olare,utilizzandodei odi i hesoddisnolaDenizione 2.6è possi-bile disegnare un de odi atore he ontemporaneamente orregga al uni errori i li ie ne identi hi altri. Questo è il ontenuto del Teorema2.6.

Denizione 2.6. Un

[n, k]

 odi e i li o onpolinomiogeneratore

g(x)

è detto un odi e fortemente

b

burst error orre ting se, dati duevettori di errore e

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

e e 2

on la medesima sindrome e des rizioni rispettivamente

(

p 1

, i

1

)

e

(

p 2

, i

2

)

on

|

p 1

|

+ |

p 2

|

≤ 2b

, si ha e 1

=

e 2 .

Teorema2.6. Sia

C

un odi efortemente

b

 orrettoredibursterror. Allora, per ogni

b

1

, b

2

tali he

b

1

≤ b

2

e

b

1

+ b

2

= 2b

, è possibile implementare un de odi atore he orregga tutti i burst di errore di lunghezza al più

b

1

e, ontemporaneamente, identi hi tutti i burst di errore di lunghezza al più

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Codi i di ReedSolomon

L

a famiglia di odi i piú utilizzata nelle appli azioni prati he è si ura-mentequella di ReedSolomon,[73℄.

3.1 Costruzione di ReedSolomon

I odi i di ReedSolomon sono un tipo parti olare di odi e i li o; un metodo perintrodurlièquellodiutilizzare la osiddetta ostruzione BCH(daintrodotta nel 1960 da R. C. Bosee D.RayChaudhuri e, indipendentemente, nel 1959 da A. Ho quenghem), s egliendo opportunamente i parametri. Tale ostruzione è des ritta nei due seguenti paragra.

Un metodo più diretto per ottenere tale odi i è quello presentato nella seguente denizione.

Denizione 3.1. Sia

n = p

t

_{− 1}

, ove

p

è un primoe

t

un intero maggiore di

0

. Per ogni

k

≤ n

, Si di e odi e di ReedSolomon RS

(n, k)

lo spazio vettoriale tutte le funzioni polinomiali

f : F

⋆

n+1

7→ F

n+1

aventi grado al più

k

.

In parti olare, un modo per s rivere tutte le parole del odi e di Reed SolomonRS

(n, k)

è il seguente:

C = {(c

0

, c

1

, . . . , c

n−1

) : c

i

= a(ω

i

); a(x)

∈ F

q

[x],

deg

a(x) < k},

ove

ω

è un elementoprimitivo

1

di

F

n+1

. 1

Questo signi a he perogni elemento

α

∈ F

n+1

diverso da

0

esiste un indi e

i

tale he

α = ω

i

. Elementidiquesto tipopossonosempreesseretrovati in

F

n+1

. Osserviamoinne he perognielemento

α

∈ F

n+1

diversoda

0

vale semprelarelazione

α

n

_{= 1}

. 23

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Cal oliamo ora la distanza minimadel odi e RS

(n, k)

. Rammentiamo he un odi e è detto MDS (Maximum distan e separable) se i suoi parametri soddisfano on l'uguaglianzala limitazionedi Singleton

d − 1

≤ n − k.

Teorema3.1. Ladistanzaminimadel odi eRS

(n, k)

èesattamente

n−k+1

; pertanto questo odi e è MDS.

Dimostrazione. Siano

p(x)

,

q(x)

due polinomi distinti di grado al più

k − 1

. Poniamo

r(x) = p(x) − q(x)

. Chiaramente,

p(x) = q(x) ⇔ r(x) = 0,

deg

r(x) < k

e

r(x)

non è il polinomio nullo. Sia

I

l'insiemedegli indi i tali he

p(ω

i

_{) = q(ω}

i

₎

. Per il teoremadi Runi, possiamo s rivere

r(x) =

Y

i∈I

(x − ω

i

_).

In parti olare, il grado di

r(x)

è uguale alla ardinalità di

I

. Ne segue

|I|

≤ k

e dunquela distanza di Hammingfra le parole p e q asso iate a

p(x)

e

q(x)

deve soddisfare

d(

p

,

q

)

≥ n − (k − 1) = n − k + 1.

Dq questodis ende la tesi.

3.2 Codi a dei odi i di ReedSolomon

Un metodo parti olarmente e iente per odi are una messaggio m

= (m

0

m

1

· · · m

k

)

medianteun

[n, k]

 odi edi ReedSolomon

C =

RS

d

(n)

è ilseguente. Sia

ω

un elementoprimitivo di

F

n+1

. Si può rappresentare m medianteun polinomio

m(x) =

n−d−1

X

i=0

m

i

x

i

.

A questo puntoasso iamo a

m(x)

il vettore

= (m(ω

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Per quanto visto prima,

∈ C

, per ui l'operazione des ritta

F

k

n+1

7→ F

n

n+1

è una odi a. An hé questa pro edura di odi a sia e iente è ne essario prestare parti olare attenzione all'implementazione dell'operazione di prodotto del ampo nito

F

n+1

. Osserviamo he la odi a qui presentata non è di tipo sistemati o e, in generale, i valori

m

i

non ompaiono in al una posizione.

3.3 De odi a e DFT

Innanzitutto mostriamo ome sia possibileri ostruire a partire da un vettore

= (m(ω

0

_{) m(ω}

1

₎

_{· · · m(ω}

n−1

₎₎

i oe ienti del polinomio

m(x)

.

A talne introdu iamo lanozione di trasformatadis reta di Fourier.

Denizione 3.2. Sia

ω

unelemento primitivossatodel amponito

F

n+1

; in-di hiamo on

V

lospaziovettoriale

F

n

n+1

didimensione

n

su

F

n+1

. Consideriamo un vettore generi o

f

= (f

0

f

1

· · · f

n−1

)

∈ V.

La trasformata dis reta di Fourier (DFT) di èil vettore

^

f

= (^

c

0

^

c

1

· · · ^

c

n−1

)

∈ V

la ui entrata

t

esimaè

^

f

t

=

n−1

X

i=0

c

i

ω

it

.

Osserviamo he ses riviamo

f(x) =

n−1

X

i=0

f

i

x

i

,

allora la omponente

t

esima della DFT di f èesattamente il valore

f(ω

t

₎

. Per-tanto si può dire he la operazione di odi a di un vettore mediante un odi e di ReedSolomon orrisponde al al olarne latrasformata.

Mostriamo ora he la DFT è invertibile. A tal ne è ne essario premettere un lemma.

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Lemma 3.2. Sia

α

∈ F

n+1

un elemento di un ampo nito. Allora,

n−1

X

i=0

α

i

=



n

se

α = 1

0

altrimenti

.

Dimostrazione. Consideriamol'espressione

α

n−1

X

i=0

α

i

₌

n−1

X

i=0

α

i+1

₌

n

X

i=1

α

i

_.

D'altro anto,

α

n

_{= 1 = α}

0

per ogni

α

∈ F

n+1

, per ui

(α − 1)

n−1

X

i=0

α

i

!

= 0.

Ne segue he

α = 1

oppure la sommatoriaè nulla. S riviamo la omponente

t

esima della trasformata

^

^

f

t

=

n−1

X

i=0

^

f

i

ω

it

=

n−1

X

i=0

n−1

X

j=0

f

j

ω

ij

!

ω

it

₌

n−1

X

j=0

f

j

n−1

X

i=0

ω

i(j+t)

!

.

Per il Lemma 3.2, la somma fra parentesi è nulla tranne quando

j + t = n

, nel quale aso, essa vale

n

. Pertanto,

^

^

f

t

= nf

−t

,

ove l'indi e

t

è da intendersi ridotto modulo

n

. ed è dunque sempre possibile ri avare i valori di f a partire da quelli di

f

^

. In termini di polinomi questa relazione si può s rivere ome

f

t

=

1

n

^

^

f(ω

−t

).

3.4 Il problema dalla orrezione

Ilproblema hiave per l'algoritmodi orrezione è il seguente. Problema 3.1 (Interpolazione di polinomi). Siano

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

b.

t

≤ n/2

un intero.

Poniamo

n = q − 1

e

k = n − 2t

. Dati

D1.

n

elementi distinti

x

0

, x

1

, x

2

, . . . , x

n−1

di

F

q

e

D2.

n

elementi (non ne essariamentedistinti)

y

0

, y

1

, . . . , y

n−1

∈ F

q

determinare un polinomio

P(x)

∈ F

q

[x]

on:

a. deg

P(x)

≤ k − 1

;

b.

P(x

i

)

6= y

i

per alpiù

t

valori di

i

.

Nella formulazione generale questo problema è molto di ile da arontare dal punto di vista omputazionale

2

.

Fortunatamente, la de odi a di un odi e di ReedSolomon orrisponde ad una istanza moltoparti olaredel problema sopra presentato ed è fattibilein tempopolinomiale. Ilseguentes hemamostra omesipossapro edereinquesto aso.

1. Innanzituttoveri hiamo herisolvereilProblema3.1èequivalentea de odi- areuna parola ri evuta on ReedSolomon. Sia ora

C

un il odi e RS

d

(n)

. Poniamo

x

i

= α

i

e supponiamo he sia ri evutauna parola r

= (y

0

y

1

. . . y

n−1

),

asso iata ad una parola di odi e originariamentetrasmessa P. Notiamo he Pèlavalutazionesututtiglielementinonnullidi

F

q

diunqual hepolinomio

P(x)

∈ F

q

[x]

on deg

P(x)

≤ k − 1

. La presenza di errori orreggibili, ovvero on peso non superiore a

t =

⌊(d − 1)/2⌋

, impli a he r dieris e da P in al più

t

posizioni. Le ondizioni del Problema 3.1, e, in parti olare la (b), sono dunquesoddisfattee quindi unasoluzione diquel problema onsente di determinare il polinomio

P(x)

e, onseguentemente, la parolaP.

2

Essosi uramente appartienealla lasseNP (siveda[36℄peruna trattazioneapprofondita della teoria della omplessità), in quanto è possibile veri are in tempo polinomiale se una soluzione

P(x)

è orretta,manon sono orrentementenoti algoritmiintempopolinomialeper determinaretale

P(x)

. Inoltre,nonènemmenonotosesiapossibiledimostrare heunasoluzione non possaessere al olatain tempopolinomiale(questa ultima ondizione orrisponderebbea mostrare heilProblema3.1appartienealla lasse oNP)

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

2. Proviamoora he,se esiste unasoluzione a taleproblema,allora essaè, sotto le ondizioni orrenti, uni a e oin ide esattamente on

P(x)

. La te ni a dimostrativa è ome segue. Supponiamo dunque he esistano due polinomi

Q(x)

,

R(x)

he rispondano al Problema 3.1 e soddisno le ondizioni di ui sopra. Allorail polinomio

S(x) = Q(x) − R(x)

è diversoda

0

peralpiù

2t

valoridi

x

. D'altro anto,l'ordinedel ampo

F

q

è

n + 1

,per ui

S(x)

hane essariamentealmeno

n + 1 − 2t > k

radi i. Ne segue

S(x) = 0

identi amente oppure deg

S(x) > k

, una ontraddizione, in quanto i gradi di

Q(x)

e

R(x)

sono al più

k − 1

.

3. Dalle due onsiderazioni pre edenti dis ende he, se il Problema 3.1 ammet-te soluzione, allora tale soluzione fornis e l'uni a de odi a della parola r se ondo il odi e

C

.

3.5 Algoritmo di Wel hBerlekamp

Presentiamo ora un algoritmo on reto di omplessità polinomiale

O(n

3

₎

per de odi are i odi idi ReedSolomon. Talealgoritmoè dovutoa Wel h e Berle-kamp ; essoè stato su essivamente miglioratoe attualmentesono noteversioni della pro edura di de odi a di omplessità

O(n

poly log

n)

.

Supponiamo he

p(x)

siailpolinomio orretto asso iatoadunaparola ri evu-ta y

= (y

0

y

1

· · · y

n−1

)

. Questo polinomioè quello he l'algoritmodi orrezione deve ri ostruire.

Consideriamooraunpolinomio,

E(x)

, hegodadellaproprietà he

E(ω

i

_{) = 0}

se

p(ω

i

₎

_{6= y}

i

.

In generale, gli elementi

ω

i

orrispondenti alle posizionidi errore sono tutti radi i del polinomio

E(x)

, ma ma non è detto he tutte le radi i di

E(x)

siano posizioni di errore.

Introdu iamo ora un altro polinomio,

N(x)

he dovrà rappresentare

N(x) = p(x)E(x).

In parti olare vogliamo he

N(ω

i

) = p(ω

i

_)E(ω

i

_{) = y}

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

A priori

N(x)

è di ile da determinare, osì ome

E(x)

. Il seguente algoritmo mostra hela osaèfattibile. Intalealgoritmo

t

èilnumeromassimodierrori he vogliamopoter orreggere;

p(x)

il polinomio orrispondente alla parola orretta e

ω

i

potenze distinte di un elemento primitivo.

Algoritmo 3.1 (Wel hBerlekamp). Dati: D1

n, k

interi; D2

t

≤

n−k

2

intero; D3

ω

0

_{, ω}

1

_{, . . . , ω}

n−1

_{∈ F}

n+1

elementi tutti fra loro distinti; D4

y

0

, y

1

, . . . , y

n−1

∈ F

.

Determinare:

G1 Un polinomio

p(x)

tale he a. deg

p(x) < k

;

b.

p(x

i

) = y

i

per ogni

i

ompreso fra

0

e

n − 1

tranne he in alpiù

t

asi. Si pro eda ome segue:

S1 Cer hiamo due polinomi

N(x) =

P

k+t−1

j=0

N

j

x

j

ed

E(x) =

P

t

j=0

E

j

x

j

tali he (a) deg

E(x) = t

;

(b)

E(x)

è moni o, ioè

E

t

= 1

(3.1)

( ) deg

N(x)

≤ k + t − 1

; (d) per ogni

i = 0, . . . , n − 1

,

N(ω

i

) = y

i

E(ω

i

).

(3.2)

S2 Le relazioni (3.1) e (3.2) orrispondono ad un sistema di

n + 1

equazioni nelle

k+t−1+t+1 = k+2t

≤ n

in ognite

N

0

, N

1

, . . . , N

k+t−1

,

E

0

, E

1

, . . . E

t

. Tale sistema può essere risoltoin

O(n

3

₎

on te ni he standarde fornis e i due polinomi

N(x)

e

E(x)

.

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

a. Ilfatto he ilgradodi

E(x)

sia

t

èespli itamente ri hiesto per hél'algoritmo possa funzionare.

b. In generale la oppia

(N(x), E(x))

al olata non è uni a. D'altro anto, se

(N(x), E(x))

e

(N

′

_{(x), E}

′

_(x))

sono due polinomi he soddisfano le ondizioni di ui sopra, allora

y

i

E(ω

i

) = N(ω

i

)

ed

N

′

(ω

i

_{) = y}

i

E

′

(ω

i

_),

da ui, moltipli andole relazioni fra loro,

y

i

E(ω

i

)N

′

(ω

i

_{) = y}

i

E

′

(ω

i

_)N(ω

i

_).

(3.3) Dalla relazione (3.3)segue he

E(ω

i

)N

′

(ω

i

_{) = E}

′

(ω

i

_)N(ω

i

₎

(3.4) per ogni

i

. Infatti, per

y

i

6= 0

l'aermazioneè banale, dividendo per

y

i

. Se inve e

y

i

= 0

, allora

N(ω

i

_{) = N}

′

_(ω

i

_{) = 0}

e dunqueabbiamonuovamente he la relazione (3.4) è soddisfatta. Ora,poi hé

deg

E

′

(x)N(x) =

deg

E(x)N

′

(x)

≤ k + 2t − 1 < n,

abbiamo he i due polinomi

E(x)N

′

_(x)

e

E

′

_(x)N(x)

oin idono in un numero di punti superiore al loro grado e sono dunque identi i. Ne segue he

p(x) =

N(x)/E(x)

è univo amente determinato.

. È immediatoveri are hedeg

p(x) < k

; d'altro anto,se

ω

i

nonèunaradi e di

E(x)

, allora

p(ω

i

) = N(ω

i

_)/E(ω

i

_{) = y}

i

E(ω

i

)/E(ω

i

) = y

i

,

per ui il polinomio

p(x)

soddisfa le proprietà ri hieste ed è soluzione al problema della de odi a del odi e di ReedSolomon.

Per on ludere, osserviamo he l'algoritmopresentato può essere implementato in tempo polinomiale

(O(n

3

₎₎

. Infatti, la risoluzione di un sistema lineare in

(k + 2t)

≤ n

in ognite è sempre possibilein un tempo he è

O(n

3

₎

.

I fatti essenziali he sono stati sfruttati per lade odi a dei odi i di Reed Solomonsono stati i seguenti:

a. gli indi idelle parole sono rappresentati da elementi

x

i

= α

i

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

b. le valutazioni di due polinomi he orrispondono a parole di odi e distinte non possono oin idere in moltipunti;

. il prodottodi due polinomidi gradobasso ha a sua volta gradobasso;

d. il quoziente di due polinomi risulta (in asi opportuni), a sua volta un poli-nomio.

3.6 Appli azioni dei odi i di ReedSolomon

In questoparagrafopresenteremo dueesempi diappli azionedei odi idi Reed Solomon, il primoè il sistema omuni azione delle sonde Voyager, il se ondo il formatodi ar hiviazionedei dati su di un DVD.

Esempio 3.1. Le sonde Voyager sono state lan iate nel 1977. L'obiettivo origi-nariodi fornireinformazionieimmaginiadaltarisoluzionedi Giove eSaturnoe, eventualmentedei pianetipiùesterni. Ilprogettodel sistemaprevededue anali di omuni azione, su bande di frequenza distinte, denominate on le lettere S (

2115

MHz) e X (

8415

MHz). In parti olare, il anale sulla banda X è dedi ato alla trasmissione dei dati dalla sonde verso terra, mentre il anale sulla banda S è per la trasmissione da terra verso le sonde e, eventualmente, ome anale se ondario di trasmissione dati dalla sonda. La apa ità in bit al se ondo del analeSè ompresafra

10

e

2560

,mentrepersul analeXèpossibiletrasmettere sino a

115.2

kilobits al se ondo; si veda [56℄ per i dettegli.

La distanza della sonda Voyager 2 dalla terra al momento dell'in ontro on Giove era di ir a

5.2

AU; al momento dell'in ontro on Nettuno di

30

AU, ove ununitàastronomi a(AU) orrispondea ir a

1.496×10

8

hilometri. Ènaturale prevedere he su queste distanze si possano veri are errori nella propagazione delsegnale,inparti olarequalorasivoglianotrasmetteredatiadaltavelo iàsulla banda X. Per poter orreggere questi errori, i progettisti delle missioni hanno provveduto ad implementare dei odi i orrettori di errore. Tali odi i sono ostruiti ombinandoun odi e lineare onun odi e onvoluzionale opportuno.

Il odi e lineare utilizzato per trasmettere le immagini da Giove e Saturno era il

[24, 12, 8]

 odi ebinario di Golayesteso

3

G

24

. Questo odi e è in grado di orreggerealpiù

3

errori per ogni

24

bits didatitrasmessi (esattamente

1

errore per byte), ma ha una ridondanza di

12

bits, pari al

100

% della lunghezza del messaggio originale.

3

Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 -- Bozza 3 giugno 2006 --

Pertrasmettereleinformazionidai pianetipiùesterni (UranoeNettuno) era ne essarioutilizzare una odi apiù e iente. A talne siè sostituitoil odi e

G

24

on il odi e di ReedSolomon RS

(255, 223)

di distanza minima

33

. Tale odi e:

a. ha dimensione

223

su

F

2

8

;

b. garantis edi orreggerealmeno

16

erroriper ogniblo o di

255

bits, paria

1

errore per ogni blo odi

16

bits;

. ha una ridondanza di soli

32

bits pari al

14

% della lunghezza del messaggio originario.

È hiaro heil odi edi ReedSolomon,dasolo, può orreggeremeno errori he non quellodi Golay,ma il risparmioin terminidi informazionetrasmessa rende l'operazione omunque onveniente. In realtà, la modi a dell'appare hiatura di odi anon hèl'impiegodialgoritmipiùsosti atidide odi aha onsentito di abbassarela frazione di errori non orretti da

5

× 10

−3

sino a

10

−6

.

Esempio3.2. IDVDRO(ReadOnly digital versatile disk)sonounsupporto di memorizzazionedatiad alta apa ità(possono ontenere sino a

8.5

Gigabyte di informazioni. Dal punto di vista si o si tratta di dis hi del diametro di

120

millimetri on un foro entrale di

15

millimetri. Ogni dis o è formato da due stratidisupportoin ollatifraloro. Questistratiisolanounaoduelaminesu ui i dati sono immagazzinati ome variazioni dell'indi e di dirazione delle lamine stesse.

Un supporto di memorizzazione quali i DVD può essere soggetto a danni dovuti sia all'inve hiamento del supporto he all'usura. In parti olare, vi può essere un alterazione della lamina su ui sono immagazzinatii dati a ausa di ondizioniavverse (ad esempio,esposizione al alore o alu e solareintensa) op-puregli stratidi supportopossonoessere danneggiatidagrae/o abrasioni. Al nediin rementareladuratautiledeidis hi,idatidevonoessereimmagazzinati utilizzandoun odi e a orrezionedierrore. Ilpro edimentoè omesegue. Ogni blo odi

192

× 172

bytesvienerappresentatomedianteunamatri erettangolare

B

. Dapprima si appli a ad ogni riga della matri e il odi e RS

(182, 172)

di pa-rametri

[182, 172, 11]

. In talmodosi ottieneuna nuova matri e

B

′

didimensioni

192×182

. Aquestopunto,adogni olonnadi

B

′

siappli ail odi eRS

(208, 192)

di parametri

[208, 192, 17]

,di modo da ottenere una matri e nale

B

′′

di dimen-sioni

208

× 182

. Questo è il blo o di informazione he viene on retamente s ritto su dis o.