Polinomio generale locatore d'errore per codici ciclici binari

≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Polinomio generale locatore d’errore per codici

ciclici binari con lunghezza n 63 e capacità

< ≤

di correzione d’errore t 2

Elisa Signori

11 maggio 2009 ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Sommario

Parte prima

1 Conoscenze preliminari

Alcuni risultati di rilievo

Teoremi sulla struttura di alcuni codici

Parte seconda

2 ≤

Codici con t 1 e n 63

< {1, ⊂ ≥

Caso generale per t 2: 2i 1} S , dove i 1

= + C

{1, −

Caso t 2 e S n 1, l}

= =

Una nuova famiglia di codici

Conclusione

Parte terza

3 La classificazione è completa!

Qualche teorema utile

Casi 2 e 5 in dettaglio ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Daremo, in questa sezione, alcuni importanti concetti e

definizioni basilari che ci serviranno a capire meglio il senso e

lo scopo di questo seminario.

Definizione (codice lineare a blocchi) ∈

Sia il campo finito con q elementi e siano k n tali che

,

F N

q n

≤

k n. Sia C un sottospazio vettoriale di di dimensione k .

(F )

q

Allora C è un codice lineare a blocchi su di dimensione k e

F q

lunghezza n. ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Daremo, in questa sezione, alcuni importanti concetti e

definizioni basilari che ci serviranno a capire meglio il senso e

lo scopo di questo seminario.

Definizione (codice lineare a blocchi) ∈

Sia il campo finito con q elementi e siano k n tali che

,

F N

q n

≤

k n. Sia C un sottospazio vettoriale di di dimensione k .

(F )

q

Allora C è un codice lineare a blocchi su di dimensione k e

F q

lunghezza n. ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (distanza di un codice lineare)

Sia C un codice lineare. Definiamo la distanza d di C come la

minima distanza (qui intendiamo distanza di Hamming, ma

potremmo darne delle altre) tra due diverse parole in C, cioè:

0

d min d(c, c

= ).

0 0

∈C,c6

c,c c

=

Equivalentemente, d è il peso minimo tra i pesi delle parole

codice diverse da 0. ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (distanza di un codice lineare)

Sia C un codice lineare. Definiamo la distanza d di C come la

minima distanza (qui intendiamo distanza di Hamming, ma

potremmo darne delle altre) tra due diverse parole in C, cioè:

0

d min d(c, c

= ).

0 0

∈C,c6

c,c c

=

Equivalentemente, d è il peso minimo tra i pesi delle parole

codice diverse da 0. ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (distanza di un codice lineare)

Sia C un codice lineare. Definiamo la distanza d di C come la

minima distanza (qui intendiamo distanza di Hamming, ma

potremmo darne delle altre) tra due diverse parole in C, cioè:

0

d min d(c, c

= ).

0 0

∈C,c6

c,c c

=

Equivalentemente, d è il peso minimo tra i pesi delle parole

codice diverse da 0. ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (capacità di correzione d’errore)

Chiamiamo t la capacità di correzione d’errore di un codice

lineare C, cioè il numero di errori che tale codice può

correggere.

Teorema (stima della capacità di correzione d’errore)

Un codice C di parametri k d] sul campo ha capacità di

[n, , F q

−

rilevazione d’errore z d 1 e capacità di correzione d’errore

=

d−1

t .

= 2 ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (capacità di correzione d’errore)

Chiamiamo t la capacità di correzione d’errore di un codice

lineare C, cioè il numero di errori che tale codice può

correggere.

Teorema (stima della capacità di correzione d’errore)

Un codice C di parametri k d] sul campo ha capacità di

[n, , F q

−

rilevazione d’errore z d 1 e capacità di correzione d’errore

=

d−1

t .

= 2 ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (equivalenza tra codici)

∈

Per ogni permutazione S , denotiamo con la sua azione,

ρ ρ̃

n n

associata al cambio di coordinate in :

(F )

q

n n

→ . Sia una permutazione in ottenuta come:

ρ̃ : (F ) (F ) π F

q q

q

moltiplicazione per un elemento di diverso da 0;

F

q

automorfismo del campo;

combinazione dei due casi precedenti.

Siano ora C e C due codici con la stessa lunghezza n.

1 2

Diciamo che C e C sono equivalenti se esiste una

1 2 n

permutazione di del tipo:

σ (F )

q

· · · · · ·

→

v v tale che

π (v ) π (v )

σ : ρ̃

n n n

1 1 1

∈ S , come sopra e C .

ρ (π ) σ(C ) =

n i i=1...n 1 2 ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (equivalenza tra codici)

∈

Per ogni permutazione S , denotiamo con la sua azione,

ρ ρ̃

n n

associata al cambio di coordinate in :

(F )

q

n n

→ . Sia una permutazione in ottenuta come:

ρ̃ : (F ) (F ) π F

q q

q

moltiplicazione per un elemento di diverso da 0;

F

q

automorfismo del campo;

combinazione dei due casi precedenti.

Siano ora C e C due codici con la stessa lunghezza n.

1 2

Diciamo che C e C sono equivalenti se esiste una

1 2 n

permutazione di del tipo:

σ (F )

q

· · · · · ·

→

v v tale che

π (v ) π (v )

σ : ρ̃

n n n

1 1 1

∈ S , come sopra e C .

ρ (π ) σ(C ) =

n i i=1...n 1 2 ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (equivalenza tra codici)

∈

Per ogni permutazione S , denotiamo con la sua azione,

ρ ρ̃

n n

associata al cambio di coordinate in :

(F )

q

n n

→ . Sia una permutazione in ottenuta come:

ρ̃ : (F ) (F ) π F

q q

q

moltiplicazione per un elemento di diverso da 0;

F

q

automorfismo del campo;

combinazione dei due casi precedenti.

Siano ora C e C due codici con la stessa lunghezza n.

1 2

Diciamo che C e C sono equivalenti se esiste una

1 2 n

permutazione di del tipo:

σ (F )

q

· · · · · ·

→

v v tale che

π (v ) π (v )

σ : ρ̃

n n n

1 1 1

∈ S , come sopra e C .

ρ (π ) σ(C ) =

n i i=1...n 1 2 ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (equivalenza tra codici)

∈

Per ogni permutazione S , denotiamo con la sua azione,

ρ ρ̃

n n

associata al cambio di coordinate in :

(F )

q

n n

→ . Sia una permutazione in ottenuta come:

ρ̃ : (F ) (F ) π F

q q

q

moltiplicazione per un elemento di diverso da 0;

F

q

automorfismo del campo;

combinazione dei due casi precedenti.

Siano ora C e C due codici con la stessa lunghezza n.

1 2

Diciamo che C e C sono equivalenti se esiste una

1 2 n

permutazione di del tipo:

σ (F )

q

· · · · · ·

→

v v tale che

π (v ) π (v )

σ : ρ̃

n n n

1 1 1

∈ S , come sopra e C .

ρ (π ) σ(C ) =

n i i=1...n 1 2 ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (equivalenza tra codici)

∈

Per ogni permutazione S , denotiamo con la sua azione,

ρ ρ̃

n n

associata al cambio di coordinate in :

(F )

q

n n

→ . Sia una permutazione in ottenuta come:

ρ̃ : (F ) (F ) π F

q q

q

moltiplicazione per un elemento di diverso da 0;

F

q

automorfismo del campo;

combinazione dei due casi precedenti.

Siano ora C e C due codici con la stessa lunghezza n.

1 2

Diciamo che C e C sono equivalenti se esiste una

1 2 n

permutazione di del tipo:

σ (F )

q

· · · · · ·

→

v v tale che

π (v ) π (v )

σ : ρ̃

n n n

1 1 1

∈ S , come sopra e C .

ρ (π ) σ(C ) =

n i i=1...n 1 2 ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (equivalenza tra codici)

∈

Per ogni permutazione S , denotiamo con la sua azione,

ρ ρ̃

n n

associata al cambio di coordinate in :

(F )

q

n n

→ . Sia una permutazione in ottenuta come:

ρ̃ : (F ) (F ) π F

q q

q

moltiplicazione per un elemento di diverso da 0;

F

q

automorfismo del campo;

combinazione dei due casi precedenti.

Siano ora C e C due codici con la stessa lunghezza n.

1 2

Diciamo che C e C sono equivalenti se esiste una

1 2 n

permutazione di del tipo:

σ (F )

q

· · · · · ·

→

v v tale che

π (v ) π (v )

σ : ρ̃

n n n

1 1 1

∈ S , come sopra e C .

ρ (π ) σ(C ) =

n i i=1...n 1 2 ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Un’importante insieme di codici è quello dei codici ciclici, di cui

tratteremo diffusamente in questo seminario.

Definizione (codice ciclico)

· · ·

c c

Dato un n-vettore c possiamo considerare

= 0 n−1

il suo shift:

· · ·

c c c che è ancora un n-vettore con

sh(c) = n−1 0 n−2

lo stesso campo di coefficienti.

Sia C un codice di parametri k d] sul campo

[n, ,

∀c ∈ ∈

tale che C,sh(c) C. Diciamo allora che C è ciclico.

F q ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Un’importante insieme di codici è quello dei codici ciclici, di cui

tratteremo diffusamente in questo seminario.

Definizione (codice ciclico)

· · ·

c c

Dato un n-vettore c possiamo considerare

= 0 n−1

il suo shift:

· · ·

c c c che è ancora un n-vettore con

sh(c) = n−1 0 n−2

lo stesso campo di coefficienti.

Sia C un codice di parametri k d] sul campo

[n, ,

∀c ∈ ∈

tale che C,sh(c) C. Diciamo allora che C è ciclico.

F q ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Osservazione

Le parole di C si prestano molto bene ad essere rappresentate

come polinomi e questo può portare grandi vantaggi

· · ·

c c

nell’operare con codici ciclici; infatti se c :

= 0 n−1

n−1

∗ · · · ∗ ∈

pol c c x c x

(x) = + + + [x].

F

c q

0 1 n−1 ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Osservazione ≤ − ⇒ ∈

Notiamo anche che deg(pol 1) pol .

) (n [x]/

F n

c c q −1)

(x

E’ noto che, se C è un codice di parametri k d] ciclico, allora

[n, ,

C, visto come sottoanello di , è un ideale.

[x]/

F n

q −1)

(x

Poiché è un anello a ideali principali, esiste una

[x]/

F n

q −1)

(x ∈

classe di polinomi equivalenti che genera C.

[g] [x]/

F n

q −1)

(x ∈

Tale classe ammette un unico rappresentante g di

[x]

F q

grado minimo. Tale g è detto polinomio generatore di C e

n

− −

deg(g) n k g|(x 1).

= , ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Osservazione ≤ − ⇒ ∈

Notiamo anche che deg(pol 1) pol .

) (n [x]/

F n

c c q −1)

(x

E’ noto che, se C è un codice di parametri k d] ciclico, allora

[n, ,

C, visto come sottoanello di , è un ideale.

[x]/

F n

q −1)

(x

Poiché è un anello a ideali principali, esiste una

[x]/

F n

q −1)

(x ∈

classe di polinomi equivalenti che genera C.

[g] [x]/

F n

q −1)

(x ∈

Tale classe ammette un unico rappresentante g di

[x]

F q

grado minimo. Tale g è detto polinomio generatore di C e

n

− −

deg(g) n k g|(x 1).

= , ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (complete defining set)

Sia g il generatore di un codice ciclico C di parametri k d] e

[n, ,

sia una radice n-esima primitiva dell’unità nel campo di

α n −

spezzamento di x 1.

Definiamo S l’insieme:

c i

· · · | ∀j ∈ · · · −

S i i g(α 0 1, 2, k .

= , , ) = , , (n )

j

c 1 n−k

S è detto complete defining set di C.

c ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (defining set)

0

L’insieme S è un defining set per C se

C

0 ⊂

S S ;

1 C

C 0 0 0

i i

∀f ∈ ∀i ∈ ⇒ ∀i ∈

vale: f 0 S f 0 S .

[x] (α ) = , (α ) = ,

2 F q C

C

Poiché ogni codice ciclico è completamente determinato dalle

radici del suo generatore g, una matrice di controllo di parità

H,

per C, è data dal teorema seguente. ≤

Polinomio generale locatore d’errore per codici ciclici binari con lunghezza n 63 e capacità di correzione d’errore t 2

<

Parte prima

Conoscenze preliminari

Conoscenze preliminari

Definizione (defining set)

0

L’insieme S è un defining set per C se

C

0 ⊂

S S ;

1 C

C 0 0 0

i i

∀f ∈ ∀i ∈ ⇒ ∀i ∈

vale: f 0 S f 0 S .

[x] (α ) = , (α ) = ,

2 F q C

C

Poiché ogni codice ciclico è completamente determinato dalle

radici del suo generatore g, una matrice di controllo di parità

H,

per C, è data dal teorema segue