La Trasformata di Winograd nella Teoria dei Codici Correttori

|C|

ghezza k definita per gli (r, k)-codici segue che = q , mentre dal teorema

r−d+1

|C|

segue che = q .

Definizione 4.1.13. Un (r, k)-codice C è detto a massima distanza sepa-

rabile (o MDS) se comunque scelti k posti di un qualsiasi vettore del codice,

questi sono di informazione.

4.2 Matrice generatrice e matrice di controllo

Utilizzando il fatto che i codici lineari sono in particolare dei sottospazi vetto-

riali, possiamo scrivere gli elementi di un codice dalla matrice di passaggio dallo

r

spazio al sottospazio C.

F 68

4.Codici lineari

ri=1 r ki=1

{b } {e }

Sia base di e sia base di C, allora è noto che ogni vettore b

F

i i i

può essere scritto come combinazione lineare dei e :

i

r

X

b = a e

i ij j

j=1

A tale sistema corrisponde la matrice di caratteristica k, indicata con G e detta

matrice generatrice del codice C

 

· · · · · ·

a a a

11 1k 1r

· · · · · ·

a a a

21 2k 2r

 

G =  

. .. ..

..

 

. .

 

··· ···

a a a

k1 kk kr

In questo caso il codice C è detto generato da G. Utilizzando i risultati del-

2

l’algebra lineare è possibile scrivere la matrice G in modo tale che le prime k

×

colonne coincidano con le prime k colonne della matrice identità k k:

|

G = (I E)

k

In questa forma G è detta in forma standard. Risulta immediato il rapporto

fra gli (r, k)-codici sopra definiti ed i codici lineari:

Teorema 4.2.1. Ogni matrice k×r di caratteristica k definisce un (r, k)-codice.

Dimostrazione. Ad ogni matrice corrisponde infatti un sottospazio di dimensio-

ne k dello spazio delle parole rispetto a delle basi fissate. Tutte le combinazioni

lineari degli elementi della base del sottospazio sono vettori di un sottospazio

k-dimensionale che è quindi un (r, k)-codice.

Dato che esistono matrici generatrici diverse che definiscono lo stesso sottospazio

×

vettoriale, non c’è una corrispondenza biunivoca fra le matrici k r di caratte-

ristica k ed i codici lineari. I codici lineari equivalenti saranno approfonditi nei

prossimi paragrafi.

Fra i vantaggi della rappresentazione matriciale si annovera un modo rapido per

capire (e per costruire) codici a massima distanza separabile.

3

Teorema 4.2.2. Un codice lineare C k-dimensionale è un MDS se e solo se

ogni minore di ordine k di una matrice generatrice del codice è non nullo.

Dimostrazione. Dimostriamo il risultato per doppia inclusione:

⇒) C è MDS se k posti qualsiasi sono di informazione. Se per assurdo la

matrice generatrice di C avesse un minore di ordine k nullo, i vettori di

tale matrice non sarebbero linearmente indipendenti e due parole diverse

di lunghezza k private dei simboli di ridondanza coinciderebbero.

⇐) Per contrapposizione: sia C codice avente G matrice generatrice che pos-

siede un minore nullo di ordine k. Allora esistono almeno due parole di-

verse che private dei simboli di ridondanza risultano essere uguali. Quindi

C non è un codice MDS.

2 Ad esempio con una generalizzazione di pag. 99 [28].

3 [2] pag. 131, teorema 6.9. 69 4.Codici lineari

Si pone ora il problema di cercare un modo computazionalmente efficiente

r

per determinare se una parola dello spazio appartiene ad un dato codice

F

lineare C. Per tale scopo è necessario introdurre i codici duali definiti sull’usuale

prodotto scalare fra vettori: r

Definizione 4.2.1. Sia un codice lineare C di si definisce spazio ortogo-

F

nale l’insieme ⊥ {x | · ∀c ∈

C := x c = 0 C}

r

che è a sua volta un sottospazio vettoriale di detto codice ortogonale (o

F

codice duale). ⊥

Dato che sui campi finiti possono esserci vettori isotropi, C e C possono avere

⊥

in comune vettori diversi dal vettore nullo. Nel caso in cui C = C allora C

è detto codice autoduale; gli unici codici autoduali possibili sono quelli in cui

r

k = n/2. Il fatto che il codice ortogonale sia un sottospazio vettoriale di ,

F

porta alla seguente

Definizione 4.2.2. Sia C (n, k)-codice lineare, allora la matrice generatrice del

codice ortogonale è detta matrice di controllo ed è indicata con H.

I prossimi teoremi stabiliscono un modo per determinare l’appartenenza di una

parola ad un codice tramite la matrice di controllo.

Teorema 4.2.3. Sia C (n, k)-codice lineare generato dalla matrice G.

Allora ⊥ t t

∈ ⇐⇒

x C Gx = 0

Dimostrazione. Dimosrtiamo per doppia inclusione:

⊥

⇒) ∈

Sia x C allora x è ortogonale ad ogni parola di C, quinde a maggior

ragione è ortogonale alle parole di ogni base di C, anche della base i cui

t t

vettori costituiscono la matrice G: Gx = 0 .

t t

⇐) Viceversa se Gx = 0 , allora x è ortogonale a una scelta di vettori

{e }

, . . . , e base di C. Dato che ogni parola del codice è definita come

0 r−1 · · ·

combinazione lineare c = λ e + + λ e allora

0 0 r−1 r−1

· · · · ·

x c = x (λ e + + λ e )

0 0 r−1 r−1

· · · · ·

= λ (x e ) + + λ (x e )

0 0 r−1 r−1

=0

Da cui segue che x è ortogonale ad ogni parola di C ed appartiene quindi

al codice duale. ⊥ −

Corollario 4.2.1. Se C (n, k)-codice lineare allora C è un (r, r k)-codice

− ×

lineare e la sua matrice generatrice è di dimensione (r k) r.

70

4.Codici lineari ⊥

Dimostrazione. Dal teorema precedente i vettori x = (x , . . . , x ) di C sono

1 r

rq {e }

vettori di ortogonali ai vettori di una base di C. Sia . . . e tale base,

F 0 k

⊥

allora x appartiene a C se le sue componenti soddisfano il sistema

∀i ∀j

(e ) x = 0 = 1, . . . , k = 1, . . . , r

i j j −

Tale sistema possiede esattamente n k soluzioni linearmente indipendenti, che

⊥

costituiscono una base per C .

Teorema 4.2.4. Sia C (n, k)-codice lineare generato dalla matrice G ed avente

H come matrice di controllo.

Allora t t

∈ ⇐⇒

x C Hx = 0

⊥ ⊥ ⊥

∈ · ∀c ∈

Dimostrazione. x C se e solo se x c = 0 C . Ma questo accade

in particolare per tutti i vettori della base che costituiscono le righe di H, e

viceversa se accade per tutti i vettori della base accade per ogni altro vettore.

t

Risulta quindi essere di importanza cruciale il valore di Hx che prende il nome

r

∈

di sindrome del vettore x . È possibile ricavare la matrice di controllo H

F

costruendola a partire dalla matrice generatrice G, utilizzando il seguente

Teorema 4.2.5 (di correlazione fra G ed H). Sia C (r, k)-codice lineare di

|

matrice generatrice G scritta in forma standard come G = (I E), allora la

k

t |

matrice di controllo risulta essere H = (−E I ).

n−k rq {e

e alla base . . . e di

Dimostrazione. Se G, rispetto alla base standard di F 0 k

C, è data da  

· · · · · ·

1 0 0 e e

1,k+1 1,k+1

· · ·

· · · e e

0 1 0 1,k+1 1,k+1

 

G =  

. .. .. ..

..

 

. . .

 

· · ·

· · · e e

0 0 1 1,k+1 1,k+1

allora un vettore x è una parola del codice C se e solo se

   

x 0

1

. ..

  ..

· · · · · ·

1 0 0 e e    

.

1,k+1 1,k+1    

· · · · · ·

0 1 0 e e    

x 0

1,k+1 1,k+1

  k

   

=

 

.. .. .. ..    

x 0

 

. . . . k+1

   

     

. .

· · · · · · .. ..

0 0 1 e e    

1,k+1 1,k+1    

x 0

r

−

che ha esattamente n k soluzioni linearmente indipendenti. Queste possono

essere costuite assegnando ai vetttori (r−k)-dimensionali delle incognite i vettori

r−k

della base standard di per ottenere una matrice generatrice dello spazio

F q |

duale della forma H = (? I ).

n−k

Tali soluzioni sono date da −e −e

(−e , , . . . , , 1, 0, . . . , 0)

1,k+1 2,k+1 k,k+1

−e −e

(−e , , . . . , , 0, 1, . . . , 0)

1,k+2 2,k+2 k,k+2

.. ..

. .

−e −e

(−e , , . . . , , 0, 0, . . . , 1)

1,r 2,r k,r

71 4.Codici lineari

e consentono di ricavare i vettori che occupano lo spazio che avevamo indicato

con ?:  

−e −e −e

. . . 1 0 . . . 0

1,k+1 2,k+1 k,k+1

−e −e −e 0 1 . . . 0

. . .

1,k+2 2,k+2 k,k+2

 

H =  

.. .. .. ..

 

. . . .

 

−e −e −e

... 0 0 ... 1

1,k+r 2,k+r k,k+r

da cui risulta la tesi.

4.2.1 Codici lineari equivalenti

Come già accennato due sottospazi vettoriali isomorfi possono essere generati da

basi diverse, quindi serve un criterio per distinguere i codici isomorfi da quelli

non isomorfi.

Definizione 4.2.3. Due codici lineari si dicono equivalenti se è possibile otte-

nere tutte le parole di uno a partire dall’altro, applicando una successione delle

seguenti operazioni

1. Permutare la posizione di due elementi delle parole.

2. Moltiplicare le lettere di una posizione all’interno di ogni parola per una

lettera non nulla.

Essendo possibile applicare alla matrice G delle trasformazioni elementari che

modificano gli elementi delle righe e delle colonne della matrice senza cambiare

il sottospazio da essa generato, a meno di permutazioni sugli elementi di ogni

vettore che vi appartiene, segue la dimostrazione della

0

Proprietà 4.2.1. Due codici lineari C e C sono detti equivalenti, se è possibile

0

ottenere la matrice generatrice G di C dalla matrice generatrice G di C tramite

una sequenza di trasformazioni elementari dei seguenti tipi:

1. Scambiare due righe.

2. Moltiplicare gli elementi di una riga per un elemento non nullo in F.

3. Scambiare due colonne.

4. Moltiplicare gli elementi di una colonna per un elemento non nullo in F.

4.3 Codifica e decodifica nei codici lineari

Esistono dei procedimenti standard per la codifica e la decodifica dei codici

lineari che possono essere “raffinati”per codici particolari. In questa se