Campi di Galois

F2: elementi {0, 1}, somma modulo 2

Campo di Galois Vm(F2) = F2m

Elementi: vettori binari di lunghezza m,

– p. 1/39

Campi di Galois

F2: elementi {0, 1}, somma modulo 2

Campo di Galois Vm(F2) = F2m

Elementi: vettori binari di lunghezza m,

Addizione: vettoriale su F2

– p. 1/39

Campi di Galois

F2: elementi {0, 1}, somma modulo 2

Campo di Galois Vm(F2) = F2m

Elementi: vettori binari di lunghezza m,

Addizione: vettoriale su F2

Moltiplicazione:Vediamo vettori come polinomi binari di grado ≤ m acoefficienti su F2

(am−1, . . . , a0) ≡ a(x) = am−1xm−1 + . . . + a1x + a0

Dati a,b ∈ Vm(F2)

a · b = c sse c(x) = a(x)b(x) mod p(x)

dove p(x) = pmxm + . . . + p0 = polinomio primitivo– p. 1/39

Polinomi primitivi

Polinomio irriducibile ≡ non divisibile per altro polinomioa coefficienti in F2

– p. 2/39

Polinomi primitivi

Polinomio irriducibile ≡ non divisibile per altro polinomioa coefficienti in F2

Polinomio irriducibile divide x2m−1 + 1

– p. 2/39

Polinomi primitivi

Polinomio irriducibile ≡ non divisibile per altro polinomioa coefficienti in F2

Polinomio irriducibile divide x2m−1 + 1

Polinomio primitivo= polinomio irriducibile che dividex2m−1 + 1, non xn + 1 per n < 2m − 1

– p. 2/39

Polinomi primitivi

Polinomio irriducibile ≡ non divisibile per altro polinomioa coefficienti in F2

Polinomio irriducibile divide x2m−1 + 1

Polinomio primitivo= polinomio irriducibile che dividex2m−1 + 1, non xn + 1 per n < 2m − 1

Polinomi primitivi esistono e sono noti per ogni m

m = 3 x3 + x + 1m = 4 x4 + x + 1m = 5 x5 + x2 + 1

– p. 2/39

Radice primitiva

p(x) = pmxm + . . . + p1x + p0 = polinomio primitivo

– p. 3/39

Radice primitiva

p(x) = pmxm + . . . + p1x + p0 = polinomio primitivo

α= radice di p(x)

x2m−1+1 = q(x)p(x) ⇒ α2m−1+1 = q(α)p(α) = 0 ⇒ α2m−1 = 1

– p. 3/39

Radice primitiva

p(x) = pmxm + . . . + p1x + p0 = polinomio primitivo

α= radice di p(x)

x2m−1+1 = q(x)p(x) ⇒ α2m−1+1 = q(α)p(α) = 0 ⇒ α2m−1 = 1

Possibile provare che α0, . . . , α2m−2 sono tutti elementidi Vm(F2) tranne 0

– p. 3/39

Esempio

m = 3, polinomio primitivo=x3 + x + 1

α= radice primitiva, α3 + α + 1 = 0 ≡ α3 = α + 1

αi polinomio (grado ≤ 2) vettore (a2, a1, a0)

α0 = 1 α0 001α1 α 010α2 α2 100α3 α + 1 011α4 α(α + 1) = α2 + α 110α5 α(α2 + α) = α2 + α + 1 111α6 α(α2 + α + 1) = α2 + 1 101α7 α(α2 + 1) = 1

– p. 4/39

Esempio

m = 3, polinomio primitivo=x3 + x + 1

α= radice primitiva, α3 + α + 1 = 0 ≡ α3 = α + 1

αi polinomio (grado ≤ 2) vettore (a2, a1, a0)

α0 = 1 α0 001α1 α 010α2 α2 100α3 α + 1 011α4 α(α + 1) = α2 + α 110α5 α(α2 + α) = α2 + α + 1 111α6 α(α2 + α + 1) = α2 + 1 101α7 α(α2 + 1) = 1

INVERSO: α−i = αn−i, n = 2m − 1

– p. 4/39

Esempio

m = 3, polinomio primitivo=x3 + x + 1

α= radice primitiva, α3 + α + 1 = 0 ≡ α3 = α + 1

αi polinomio (grado ≤ 2) vettore (a2, a1, a0)

α0 = 1 α0 001α1 α 010α2 α2 100α3 α + 1 011α4 α(α + 1) = α2 + α 110α5 α(α2 + α) = α2 + α + 1 111α6 α(α2 + α + 1) = α2 + 1 101α7 α(α2 + 1) = 1

INVERSO: α−i = αn−i, n = 2m − 1

– p. 4/39

Codici Reed-Solomon

Codici di Hamming: H = [α0, . . . , αn−1]

– p. 5/39

Codici Reed-Solomon

Codici di Hamming: H = [α0, . . . , αn−1]

Codice Reed–Solomon(n,t), n = 2m − 1

H =

α0 . . . αn−1

α20 . . . α2

n−1...

......

α2t0 . . . α2t

n−1

con αi = αi, α = radice primitiva di Vm(F2)

– p. 5/39

Codici Reed-Solomon

Codici di Hamming: H = [α0, . . . , αn−1]

Codice Reed–Solomon(n,t), n = 2m − 1

H =

α0 . . . αn−1

α20 . . . α2

n−1...

......

α2t0 . . . α2t

n−1

con αi = αi, α = radice primitiva di Vm(F2)

Parole codice: C = (c0, . . . , cn−1), ci ∈ Vm(F2) t.c.

HCT = 0 ≡n−1∑

i=0

αijci = 0, j = 1, . . . , 2t

– p. 5/39

CodificaC = (c0, . . . , cn−1) ≡ C(x) = cn−1x

n−1 + . . . + c1x + c0

– p. 6/39

CodificaC = (c0, . . . , cn−1) ≡ C(x) = cn−1x

n−1 + . . . + c1x + c0

Parole codice hanno radici α, . . . , α2t

C ∈ RS(n, t) ≡ HCT = 0

≡∑n−1

i=0 αijci = 0, j = 1, . . . , 2t

≡ C(αj) = 0 j = 1, . . . , 2t

– p. 6/39

CodificaC = (c0, . . . , cn−1) ≡ C(x) = cn−1x

n−1 + . . . + c1x + c0

Parole codice hanno radici α, . . . , α2t

C ∈ RS(n, t) ≡ HCT = 0

≡∑n−1

i=0 αijci = 0, j = 1, . . . , 2t

≡ C(αj) = 0 j = 1, . . . , 2t

Parola codice sono i multipli di (x − α) . . . (x − α2t)C(x) = q(x)g(x)

g(x) = (x − α) . . . (x − α2t) =polinomio generatore delcodice

– p. 6/39

CodificaC = (c0, . . . , cn−1) ≡ C(x) = cn−1x

n−1 + . . . + c1x + c0

Parole codice hanno radici α, . . . , α2t

C ∈ RS(n, t) ≡ HCT = 0

≡∑n−1

i=0 αijci = 0, j = 1, . . . , 2t

≡ C(αj) = 0 j = 1, . . . , 2t

Parola codice sono i multipli di (x − α) . . . (x − α2t)C(x) = q(x)g(x)

g(x) = (x − α) . . . (x − α2t) =polinomio generatore delcodice

RS(n,t): tutti polinomi su Vm(F2) multipli di g(x)

– p. 6/39

Distanza Minima RS(n,t): 2t + 1

d ≤ 2t + 1g(x) ≡ parola codice grado 2t, g = (g0, . . . , g2t, 0, . . . , 0)⇒ wmin ≤ w(g) ≤ 2t + 1Quindi d = wmin ≤ 2t + 1

– p. 7/39

d ≥ 2t + 1Ogni r ≤ 2t colonne di H sono linearmente indipendenti:

Consideriamo αi1 = γ1, . . . , αir = γr e sottomatrice di H

H ′ =

γ1 . . . γr

γ21 . . . γ2

r...

γr1 . . . γr

r

– p. 8/39

Risulta

Det(H ′) = (γ1 · · · γr)Det

1 . . . 1

γ1 . . . γr

......

...γr−11 . . . γr−1

r

= γ1 · · · γr

∏

i<j

(γj − γi) 6= 0

Quindir ≤ 2t colonne di H sono linearmente indipendenti⇒ ogni parola ha peso ≥ 2t + 1 ⇒ d = wmin ≥ 2t + 1

– p. 9/39

Codifica Sistematica RS(n,t)

Simboli di informazione (a0, . . . , ak−1), ai ∈ F2m, k = n − 2t

CODIFICA

C(x) = x2ta(x) + b(x)

b(x) = resto⌊

x2ta(x)g(x)

⌋

, deg(b(x)) ≤ 2t − 1

C = (c0, . . . , cn−1) = (b0, . . . , b2t−1, a0, . . . , ak−1)

Nota Divisione polinomi VELOCE mediante circuiti

– p. 10/39

Proprietá C(x) multiplo di g(x)

DIM. C(x) = x2ta(x) + b(x), con b(x) = resto⌊

x2ta(x)g(x)

⌋

Divisione x2ta(x) per g(x): quoziente q(x), resto b(x)

C(x) = x2ta(x) + b(x)

= (q(x)g(x) + b(x)) + b(x)

= q(x)g(x)

– p. 11/39

Decodifica RS(n,t)

Parola trasmessa C ≡ C(x) = c0 + . . . + cn−1xn−1

Sequenza ricevuta R ≡ R(x) = r0 + . . . + rn−1xn−1

– p. 12/39

Decodifica RS(n,t)

Parola trasmessa C ≡ C(x) = c0 + . . . + cn−1xn−1

Sequenza ricevuta R ≡ R(x) = r0 + . . . + rn−1xn−1

Errore in posizione i sse ri 6= ci

Sia ei = ri − ci

QuindiR = C + E

Vettore errore E ≡ E(x) = e0 + . . . + en−1xn−1

– p. 12/39

Decodifica RS(n,t)

Parola trasmessa C ≡ C(x) = c0 + . . . + cn−1xn−1

Sequenza ricevuta R ≡ R(x) = r0 + . . . + rn−1xn−1

Errore in posizione i sse ri 6= ci

Sia ei = ri − ci

QuindiR = C + E

Vettore errore E ≡ E(x) = e0 + . . . + en−1xn−1

VOGLIAMO DETERMINARE E(x)

– p. 12/39

Assumiamo

γ errori in posizioni j1, . . . , jγ

⇒ ej1 , . . . , ejγ6= 0, altri ei = 0

⇒ E(x) = ej1xj1 + . . . + ejγ

xjγ

Definiamoβ1 = αj1 , . . . , βγ = αjγ e E1 = ej1 , . . . , Eγ = ejγ

⇒ E(x) = E1xj1 + . . . + Eγxjγ

– p. 13/39

Calcoliamo la sindrome S = (s1, . . . , s2t) = HRT

Risulta

si = (riga ima di H)R = (αi, . . . , αij , . . . , αi(n−1))(r0, . . . , rn−1)

= r0 + r1αi + . . . + rjα

ij + . . . + rn−1αi(n−1)

= R(αi)

– p. 14/39

Sindrome S = (s1, . . . , s2t) = HRT , si = R(αi), i = 1, . . . 2t

Essendo S = HRT = H(C + E)T = HCT + HET = HET

⇒

si = E(αi) = e0 + e1αi + . . . + en−1α

i(n−1)

= E1αij1 + . . . + Eγαijγ

= E1βi1 + . . . + Eγβi =

γ∑

j=1

Ejβij

– p. 15/39

Calcolo della sindrome

si = resto⌊

R(x)x+αi

⌋

, i = 1, . . . 2t

DIM. Dividendo R(x) per x + αi: quoziente qi(x) e resto bi

R(x) = qi(x)(x + αi) + bi

⇒ R(αi) = bi

⇒ si = bi

– p. 16/39

Decodificare ≡

Trova posizioni degli errori (j1, . . . , jγ)

Trova valore degli errori (E1, . . . , Eγ)

– p. 17/39

Polinomio locatore degli errori

Polinomio locatore degli errori:σ(x) con radici β−1

1 , . . . , β−1γ

σ(x) = (1 + β1x) . . . (1 + βγx) = 1 + σ1x + . . . + σγx

– p. 18/39

Polinomio locatore degli errori

Polinomio locatore degli errori:σ(x) con radici β−1

1 , . . . , β−1γ

σ(x) = (1 + β1x) . . . (1 + βγx) = 1 + σ1x + . . . + σγx

Vogliamo determinare σ1, . . . , σγ

– p. 18/39

Polinomio locatore degli errori

Polinomio locatore degli errori:σ(x) con radici β−1

1 , . . . , β−1γ

σ(x) = (1 + β1x) . . . (1 + βγx) = 1 + σ1x + . . . + σγx

Vogliamo determinare σ1, . . . , σγ

Possiamo farlo a partire da s1, . . . , s2t

– p. 18/39

Poiché σ(β−1ℓ ) = 0, ∀ℓ = 1, . . . , γ

– p. 19/39

Poiché σ(β−1ℓ ) = 0, ∀ℓ = 1, . . . , γ

per ogni j ≤ 2t abbiamo

0 =

γ∑

ℓ=1

Eℓβj+γℓ σ(β−1

ℓ )

=

γ∑

ℓ=1

Eℓβj+γℓ (1 + σ1β

−1ℓ + . . . + σγβ

−γℓ )

=

γ∑

ℓ=1

Eℓβj+γℓ + σ1

γ∑

ℓ=1

Eℓβj+γ−1ℓ + . . . + σγ

γ∑

ℓ=1

Eℓβjℓ

= sj+γ + σ1sj+γ−1 + . . . + σγsj

– p. 19/39

Cioé sγ+j = σ1sj+γ−1 + . . . + σγsj, per ogni j

– p. 20/39

Cioé sγ+j = σ1sj+γ−1 + . . . + σγsj, per ogni j

sγ+1 = σ1sγ + . . . + σγs1

sγ+2 = σ1sγ+1 + . . . + σγs2

. . . . . .

s2γ = σ1s2γ−1 + . . . + σγsγ

– p. 20/39

Cioé sγ+j = σ1sj+γ−1 + . . . + σγsj, per ogni j

sγ+1 = σ1sγ + . . . + σγs1

sγ+2 = σ1sγ+1 + . . . + σγs2

. . . . . .

s2γ = σ1s2γ−1 + . . . + σγsγ

Vogliamo determinare σ1, . . . , σγ

– p. 20/39

In forma matriciale

s1 . . . sγ

s2 . . . sγ+1

. . . . . . . . .

sγ . . . s2γ−1

σγ

σγ−1

. . .

σ1

=

sγ+1

sγ+2

. . .

s2γ

– p. 21/39

In forma matriciale

s1 . . . sγ

s2 . . . sγ+1

. . . . . . . . .

sγ . . . s2γ−1

σγ

σγ−1

. . .

σ1

=

sγ+1

sγ+2

. . .

s2γ

TeoremaSe vi sono γ errori la matrice é invertibile;se vi sono < γ errori la matrice ha determinante nullo.

– p. 21/39

Metodo (Peterson-Gorenstein–Ziegler)(1) Input: R(x)(2) Calcola s1, . . . , s2t

(3) Poni γ = t

(4) WHILE Det

s1 . . . sγ

. . . . . . . . .

sγ . . . s2γ−1

= 0 poni γ = γ − 1

(5)

σγ

σγ−1

. . .

σ1

=

s1 . . . sγ

. . . . . . . . .

sγ . . . s2γ−1

−1

sγ+1

sγ+2

. . .

s2γ

– p. 22/39

Metodo (Peterson-Gorenstein–Ziegler)(1) Input: R(x)(2) Calcola s1, . . . , s2t

(3) Poni γ = t

(4) WHILE Det

s1 . . . sγ

. . . . . . . . .

sγ . . . s2γ−1

= 0 poni γ = γ − 1

(5)

σγ

σγ−1

. . .

σ1

=

s1 . . . sγ

. . . . . . . . .

sγ . . . s2γ−1

−1

sγ+1

sγ+2

. . .

s2γ

NOTA: Esistono metodi successivi piú efficienti

– p. 22/39

Calcola Sindrome relativa a R(x)

– p. 23/39

Calcola Sindrome relativa a R(x)

Calcola polinomio locatore errori σ(x)Esistono algoritmi efficienti per trovare polinomio(di grado minimo ⇒ parola codice piú vicina ad R(x))σ(x) = (1 + β1x) . . . (1 + βγx) = 1 + σ1x + . . . + σγxγ

– p. 23/39

Calcola Sindrome relativa a R(x)

Calcola polinomio locatore errori σ(x)Esistono algoritmi efficienti per trovare polinomio(di grado minimo ⇒ parola codice piú vicina ad R(x))σ(x) = (1 + β1x) . . . (1 + βγx) = 1 + σ1x + . . . + σγxγ

Determina le posizioni degli erroriValuta σ(x) in 1, α, α2, . . . per trovare radici β−1

i

β−1i = αji ⇒ errore in posizione βi = αn−ji

– p. 23/39

Calcola Sindrome relativa a R(x)

Calcola polinomio locatore errori σ(x)Esistono algoritmi efficienti per trovare polinomio(di grado minimo ⇒ parola codice piú vicina ad R(x))σ(x) = (1 + β1x) . . . (1 + βγx) = 1 + σ1x + . . . + σγxγ

Determina le posizioni degli erroriValuta σ(x) in 1, α, α2, . . . per trovare radici β−1

i

β−1i = αji ⇒ errore in posizione βi = αn−ji

Determina il valore degli errori

– p. 23/39

Polinomio valutatore degli errori

Polinomio valutatore degli errori

ω(x) = S(x)σ(x) mod x2t

– p. 24/39

Polinomio valutatore degli errori

Polinomio valutatore degli errori

ω(x) = S(x)σ(x) mod x2t

Lemma Per ogni ℓ = 1, . . . , γ

Eℓ =ω(β−1

ℓ )

βℓ

∏

i6=ℓ(1 + βiβ−1ℓ )

– p. 24/39

DIM.

S(x) =2t

∑

i=1

sixi−1 =

2t∑

i=1

xi−1n−1∑

j=0

ejαij

=n−1∑

j=0

ejαj

2t∑

i=1

α(i−1)jxi−1

=n−1∑

j=0

ejαj 1 − (αjx)2t

1 − αjx

– p. 25/39

DIM.

S(x) =2t

∑

i=1

sixi−1 =

2t∑

i=1

xi−1n−1∑

j=0

ejαij

=n−1∑

j=0

ejαj

2t∑

i=1

α(i−1)jxi−1

=n−1∑

j=0

ejαj 1 − (αjx)2t

1 − αjx

S(x) mod x2t =∑n−1

j=0ejα

j

1−αjx=

∑γj=1

Ejβj

1−βjx

– p. 25/39

ω(x) = S(x)σ(x) mod x2t =

γ∑

j=1

Ejβj

1 − βjx

∏

i

(1 + βix)

=

γ∑

j=1

Ejβj

∏

i6=j

(1 + βix)

– p. 26/39

ω(x) = S(x)σ(x) mod x2t =

γ∑

j=1

Ejβj

1 − βjx

∏

i

(1 + βix)

=

γ∑

j=1

Ejβj

∏

i6=j

(1 + βix)

ω(β−1l ) = Eℓβℓ

∏

i6=ℓ(1 + βiβ−1ℓ )

– p. 26/39

ω(x) = S(x)σ(x) mod x2t =

γ∑

j=1

Ejβj

1 − βjx

∏

i

(1 + βix)

=

γ∑

j=1

Ejβj

∏

i6=j

(1 + βix)

ω(β−1l ) = Eℓβℓ

∏

i6=ℓ(1 + βiβ−1ℓ )

Eℓ =ω(β−1

ℓ )

βℓ

Q

i6=ℓ(1+βiβ−1

ℓ )

– p. 26/39

Algoritmo di Euclide

Servirá per calcolare i polinomi σ(x) ed ω(x)

Siano a(x) e b(x) polinomi su campo F , con deg(a) ≥ deg(b)Algoritmo di Euclide trove massimo comun divisore (mcd)d(x) di a(x) e b(x) e produce equazione

s(x)a(x) + t(x)b(x) = d(x)

– p. 27/39

Algoritmo iterativo che produce sequenza polinomi:si, ti, ri, qi con

s−1(x) = 1 t−1(x) = 0 r−1(x) = a(x)

s0(x) = 0 t0(x) = 1 r0(x) = b(x)

– p. 28/39

Algoritmo iterativo che produce sequenza polinomi:si, ti, ri, qi con

s−1(x) = 1 t−1(x) = 0 r−1(x) = a(x)

s0(x) = 0 t0(x) = 1 r0(x) = b(x)

Per i ≥ 1, qi(x) e ri(x) rappresentano quoziente e restodella divisione di ri−2(x) per ri−1(x):ri−2(x) = qi(x)ri−1(x) + ri(x) deg(ri) < deg(ri−1)Inoltresi(x) = si−2(x) − qi(x)si−1(x)ti(x) = ti−2(x) − qi(x)ti−1(x)

– p. 28/39

Resti grado decrescente ⇒ esiste ultimo resto di grado > 0,sia rn(x).Si dimostra chern(x) = d(x) = mcd(a, b)sn(x)a(x) + tn(x)b(x) = rn(x)

– p. 29/39

A. tiri−1 − ti−1ri = (−1)ia i = 0, . . . , n + 1

B. siri−1 − si−1ri = (−1)ib i = 0, . . . , n + 1

C. siti−1 − si−1ti = (−1)i+1 i = 0, . . . , n + 1

D. sia − tib = ri i = −1, . . . , n + 1

E. deg(si) + deg(ri−1) = deg(b) i = 1, . . . , n + 1

F. deg(ti) + deg(ri−1) = deg(a) i = 0, . . . , n + 1

– p. 30/39

Lemma Dati interi non negativi µ e ν con ν > deg(mcd(a, b))e µ + ν = deg(a) − 1, esiste unico j t.c.

deg(tj) ≤ µ deg(rj) ≤ ν

DIM. Sia j t.c.

deg(rj−1) ≥ ν + 1, deg(rj) ≤ ν

Dalla proprietá F (deg(ti) + deg(ri−1) = deg(a)) si ha

deg(tj) ≤ µ deg(tj+1) ≥ µ + 1

Quindi l’indice j esiste ed é unico.

– p. 31/39

Teorema. Siano t(x) e r(x) due polinomi t.c.

t(x)b(x) ≡ r(x) mod a(x) (1)

deg(t) + deg(r) < deg(a) (2)

Esistono unico indice j, 0 ≤ j ≤ n, e polinomio λ(x) t.c.

t(x) = λ(x)tj(x), r(x) = λ(x)rj(x) (3)

– p. 32/39

Computo di σ(x) e ω(x)

TEOREMA. Sia il numero di errori ≤ t. Si applichil’algoritmo di Euclide a a(x) = x2t e b(x) = S(x) e sia j ilprimo indice t.c. deg(rj) < t, allora

σ(x) = tj(x), ω(x) = rj(x)

– p. 33/39

Computo di σ(x) e ω(x)

TEOREMA. Sia il numero di errori ≤ t. Si applichil’algoritmo di Euclide a a(x) = x2t e b(x) = S(x) e sia j ilprimo indice t.c. deg(rj) < t, allora

σ(x) = tj(x), ω(x) = rj(x)

DIM. Se numero di errori é ≤ t, allora

deg(σ) ≤ t deg(ω) < t, σ(x)S(x) ≡ ω(x) mod x2t

Teorema su A.E: Siano t(x) e r(x) due polinomi t.c.t(x)b(x) ≡ r(x) mod a(x)deg(t) + deg(r) < deg(a)Esistono unico indice j, 0 ≤ j ≤ n, e polinomio λ(x) t.c.t(x) = λ(x)tj(x), r(x) = λ(x)rj(x)

– p. 33/39

TEOREMA. Sia il numero di errori ≤ t. Si applichil’algoritmo di Euclide a a(x) = x2t e b(x) = S(x) e sia j ilprimo indice t.c. deg(rj) < t, allora

σ(x) = tj(x), ω(x) = rj(x)

Se numero di errori é ≤ t, allora

deg(σ) ≤ t deg(ω) < t, σ(x)S(x) ≡ ω(x) mod x2t

Teorema su A.E: ⇒ σ(x) = λ(x)tj(x) e ω(x) = λ(x)rj(x)

– p. 34/39

TEOREMA. Sia il numero di errori ≤ t. Si applichil’algoritmo di Euclide a a(x) = x2t e b(x) = S(x) e sia j ilprimo indice t.c. deg(rj) < t, allora

σ(x) = tj(x), ω(x) = rj(x)

Se numero di errori é ≤ t, allora

deg(σ) ≤ t deg(ω) < t, σ(x)S(x) ≡ ω(x) mod x2t

Teorema su A.E: ⇒ σ(x) = λ(x)tj(x) e ω(x) = λ(x)rj(x)

Notando che σ(x) e ω(x) non hanno fattori comuni, siottiene σ(x) = tj(x), ω(x) = rj(x)

– p. 34/39

ALGORITMO DI DECODIFICA

Input: vettore ricevuto R

1. Calcola le sindromi

2. Applica A.E. a x2t e S(x), stop quando deg(rj) < t

Poni σ(x) = tj(x) e ω(x) = rj(x) = x + 1

3. Trova le radici di σ

β−1i radice ⇒ errore in posizione βi

4. Determina il vettore errore E= (E0, . . . , En−1):

Eℓ =ω(β−1

ℓ )

βℓ

Q

i6=ℓ(1+βiβ−1

ℓ )se c’e’ errore

Eℓ = 0 altrimenti.

5. Output R+E

– p. 35/39

Esempio

Consideriamo il codice RS(7, 2) su F8.Sia il vettore ricevuto R = (α3, α, 1, α2, 0, α3, 1).Le sindromi sono S1 = α3, S2 = α4, S3 = α4, S4 = 0.Eseguiamo l’algoritmo di Euclide su x2t = x4 eS(x) = α4x2 + α4x + α3 fermandoci quando deg(rj) < t = 2.

i ti ri qi

−1 0 x4

0 1 α4x2 + α4x + α3

1 α3x2 + α3x + α5 x + 1 α3x2 + α3x + α5

Quindi σ(x) = t1(x) = α3x2 + α3x + α5 ω(x) = r1(x) = x + 1Si ricordari−2(x) = qi(x)ri−1(x) + ri(x) deg(ri) < deg(ri−1)ti(x) = ti−2(x) − qi(x)ti−1(x)

– p. 36/39