APPUNTI DI TEORIA DEI CODICI - pelleriti.altervista.orgpelleriti.altervista.org/doc/TC.pdf · di...

$: APPUNTI DI TEORIA DEI CODICI - pelleriti.altervista.orgpelleriti.altervista.org/doc/TC.pdf · di seguire presso l’Universitµa di Auburn (USA) il suo corso di \Coding Theory". Faccio$
UNIVERSITA DI CATANIA

FACOLTA DI INGEGNERIA

APPUNTI DI TEORIA DEI CODICI

Autori:

L. Cauchi

V. La Terra

R. Grasso

Coperto da diritti di c©copyright

Ho letto questi appunti scritti da Lucia Cauchi, Rosario Grasso e Valeria La Terra,

studenti che hanno seguito il mio corso di “Teoria dei Codici” negli anni accademici 2005

– 2006 e 2006 – 2007.

Ho deciso di inserirli nella mia pagina web perche rispecchiano pienamente le mie lezioni

e sono sicuro che essi riusciranno ad essere un ulteriore aiuto didattico agli studenti che

hanno seguito e seguiranno il corso di “Teoria dei Codici”.

Ringrazio Lucia Cauchi, Rosario Grasso e Valeria La Terra, per la loro disponibilita a

condividere liberamente il loro spontaneo lavoro, coperto da diritti di “copyright” legali e

informatici, con tutti i loro colleghi e con il docente.

Mi corre l’obbligo di ringraziare il Professore Dean Hoffman che mi ha permesso, nel 1997,

di seguire presso l’Universita di Auburn (USA) il suo corso di “Coding Theory”.

Faccio inoltre presente che tali appunti nella parte riguardante la Teoria dei Codici trovano

principale fonte bibliografica nel testo “Coding Theory and Cryptography” scritto da D.

Hankerson, D. Hoffman, D.Leonard, C. Lindner, C. Rodger, K. Phelps, J. Wall.

Lorenzo Milazzo

Aggiornamento del 03/12/2007.

Indice

1 Cenni di Teoria dell’Informazione 1

1.1 I primi concetti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2 Schema di codifica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

1.3 Codici univocamente decifrabile e istantanei . . . . . . . . . . . . . . 4

1.4 Codici ottimi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4.1 Algoritmo di Huffman . . . . . . . . . . . . . . . . . . . . . . 16

1.5 La funzione entropia . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.5.1 Proprieta della funzione entropia . . . . . . . . . . . . . . . . 24

2 Teoria dei Codici

I Primi concetti 27

2.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.2 Probabilita e distanza . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.3 Peso ed errore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.4 Prime tecniche di codifica . . . . . . . . . . . . . . . . . . . . . . . . 37

2.5 Individuazione di errore . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.6 Correzione di errore . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3 Codici lineari 47

3.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

i

INDICE

3.2 Prodotto scalare in Kn . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3.3 Matrice generatrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

3.4 Matrice di parita . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.4.1 Algoritmo di generazione di H . . . . . . . . . . . . . . . . . . 55

3.5 Coset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.6 Sindrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

4 Codici perfetti 76

4.1 Cardinalita di un codice C . . . . . . . . . . . . . . . . . . . . . . . . 76

4.2 Codici MDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.3 Codici estesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

4.4 Codici perfetti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

4.4.1 Codice di Hamming . . . . . . . . . . . . . . . . . . . . . . . . 93

4.4.2 Codice di Golay esteso . . . . . . . . . . . . . . . . . . . . . . 96

5 Codici ciclici 107

5.1 Polinomi su K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

5.2 Parole di C e polinomi . . . . . . . . . . . . . . . . . . . . . . . . . . 110

5.3 Codici ciclici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

5.4 Codice ciclico e polinomi di Kn−1 . . . . . . . . . . . . . . . . . . . . 115

5.5 Matrice generatrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

5.6 Sindrome e matrice di parita . . . . . . . . . . . . . . . . . . . . . . . 122

6 Campi finiti e codici 2 - BCH 125

6.1 Polinomio primitivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

6.2 Campi finiti di Galois . . . . . . . . . . . . . . . . . . . . . . . . . . . 129

6.3 Polinomio minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

6.4 Codici di Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

ii

INDICE

6.5 Codici 2-BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

6.6 Schema di codifica per codici 2-BCH . . . . . . . . . . . . . . . . . . 143

iii

Capitolo 1

Cenni di Teoria dell’Informazione

1.1 I primi concetti

Si definisce S0 sorgente di un codice una coppia S0 = (S, P ) dove S = {s1, s2, · · · ,

sn} e un insieme finito di eventi che, come vedremo in seguito, si associano alle parole

di un codice, e P = {p(s1), p(s2), ...., p(sn)} e una distribuzione di probabilita sugli

eventi di S, dove p(si) = pi, con 0 ≤ pi ≤ 1 e∑

i pi = 1.

Si definisce alfabeto di un codice l’insieme finito di caratteri A = {a1, a2, · · · , ar},nel caso in cui il numero di simboli in A e r (cioe |A| = r) si dice che l’alfabeto

genera un codice r-ario, in questi appunti (soprattutto dal capitolo 2) saranno per

lo piu trattati casi in cui alfabeto e costituito da solo due caratteri e in particolare

l’alfabeto A = {0, 1}, tali codici sono detti binari.

Una sequenza di caratteri u = ai1 , ai2 , ...., ain e detta stringa e in essa possono

esistere caratteri ripetuti. Il numero di caratteri presenti in una stringa u e detto

lunghezza della stringa ed essa e rappresentata dalla simbologia l(u).

Indichiamo con A∗ l’insieme di tutte le possibili stringhe che si possono formare con

i caratteri dell’alfabeto (indipendentemente dalla lunghezza). Se una stringa non ha

caratteri si dice che essa e la stringa nulla.

1

1.2 Schema di codifica

Si definisce codice C = {c1, c2, · · · , cn} un particolare sottoinsieme finito di A∗, cioe

C ⊂ A∗, gli elementi ci di C sono detti parole del codice. E possibile avere codici

con parole che hanno lunghezza differente oppure codici le cui parole hanno tutte la

stessa lunghezza, in tal caso il codice e detto a blocchi.


Se S0 = (S, P ) e una sorgente di un codice, si definisce schema di codifica per S0 la

coppia ordinata (C, f), dove f : S → C e un’applicazione iniettiva detta funzione

di assegnazione. Tale funzione definisce una corrispondenza uno a uno tra gli

elementi di S con le parole del codice C.

Si definisce lunghezza media lc di un codice C la quantita:

lc =n∑

i=1

pil(f(si)), (1.1)

dove l(f(si)) e la lunghezza della parola del codice f(si) che corrisponde all’evento

si di probabilita pi, tale probabilita assume il valore della probabilita legata alla

parola f(si). Un codice C1 si dice piu efficiente del codice C2 se lC1 < lC2 .

Vediamo adesso di capire quando si usano codici a blocchi o codici a lunghezza

variabile e in tal caso cerchiamo di stabilire un criterio di assegnazione che permetta

di definire una funzione di assegnazione “piu conveniente”.

Esempio 1

Dato l’insieme S = {a, b, c, d} con P definita nel seguente modo: p(a) =217

, p(b) =217

, p(c) =917

e p(d) =417

. Sia C1 = {0, 11, 10, 100} il codice a lunghezza variabile e

l’applicazione f1 : S → C1 cosı definita: f1(a) = 11, f1(b) = 0, f1(c) = 100 e f1(d) = 10.

La lunghezza media di tale codice e:

2


l1 =n∑

i=1

pil(f(si)) = 2 · 217

+ 1 · 217

+ 3 · 917

+ 2 · 417

=4117

. (1.2)

Si consideri adesso un secondo codice C2 = {00, 10, 11, 01010} e l’applicazione f2 : S → C2

cosı definita: f2(a) = 01010, f2(b) = 00, f2(c) = 10 e f2(d) = 11. Analogamente a quanto

fatto per C1 calcoliamo la sua lunghezza media:

l2 =n∑

i=1

pil(f(si)) = 5 · 217

+ 2 · 217

+ 2 · 917

+ 2 · 417

=4017

. (1.3)

Si vede facilmente che il codice C2 e piu efficiente del codice C1.

L’esempio 1 mostra la particolarita che il codice C2 che contiene la parola piu lunga

ha una lunghezza media minore, cio e dovuto al fatto che in tale codice la funzione

di assegnazione associa la parola piu lunga del codice alla probabilita minore.

Dall’esempio precedente si evince inoltre che quando si ha una conoscenza piu det-

tagliata del sistema mediante la distribuzione di probabilita P , allora e conveniente

usare un codice a lunghezza variabile. L’esempio che segue mostra maggiormente

quando detto e in modo piu generale.

Esempio 2

Sia un codice non a blocchi definito dalla sorgente S = {s1, s2, s3, s4, s5} e p(s1) = 1 − ε

e p({s2, s3, s4, s5}) = ε. Se si utilizza un codice a blocchi binario con due caratteri non si

riescono a rappresentare tutti gli eventi di S perche esso puo contenere al massimo 4 parole

(22 = 4), quindi e necessario utilizzare un codice a blocchi di 3 caratteri che permette di

rappresentare fino a 8 parole (23 = 8). E evidente che un codice a blocchi di lunghezza

tre ha sempre lunghezza media tre e cio e indipendente dalla distribuzione P. Se invece

e utilizzato un codice a lunghezza variabile definito dalla seguente funzione di codifica:

f(s1) = 0 e f(s2) = 111, f(s3) = 101, f(s4) = 001, f(s5) = 110 si ha che la lunghezza

media di tale codice e:

3

1.3 Codici univocamente decifrabile e istantanei

lc =∑n

i=1 pil(f(si)) = 1 · p(s1) + 3 · p(s2) + 3 · p(s3) + 3 · p(s4) + 3 · p(s5) =

1 · p(s1) + 3 · (p(s2) + p(s3) + p(s4) + p(s5))

lc = (1− ε) + 3 · ε = 1 + 2 · ε < 3, (1.4)

essendo ε < 1.

L’esempio 2 mostra chiaramente che quando non si ha una distribuzione P uni-

forme e piu conveniente usare un codice a lunghezza variabile perche permette di

realizzare un codice piu efficiente, se invece P definisce una distribuzione uniforme

allora in questo caso conviene utilizzare un codice a blocchi e sfruttare la teoria dei

codici che verra presentata nei capitoli seguenti che permette migliori possibilita di

individuazione e correzione di errore.


Prima di affrontare le problematiche inerenti alla correzione degli errori che possono

accadere in una trasmissione di un codice in questa sessione si affrontera il problema

della lettura di una stringa costituita dalle parole di un codice C.

Consideriamo ad esempio il codice C = {0, 01, 001}, ci si accorge subito che la stringa

001 letta da sinistra verso destra puo essere interpretata in due modi differenti: essa

puo contenere l’unica parola del codice 001 oppure la sequenza delle due parole 0

e 01. L’esempio precedente mostra un’ambiguita che puo essere risolta definendo

dei codici particolari che permettono la lettura delle stringhe in maniera unica. E

evidente che un codice a blocchi di lunghezza n non presenta tali problematiche in

quanto la lettura di ogni singola parola viene effettuata con intervalli di n caratteri.

Se un codice C e a lunghezza variabile si dice che esso e univocamente decifrabile

se, date le due parole c1, c2, ...., ck e d1, d2, ...., df , allora si ha che c1, c2, ....., ck =

4


d1, d2, ....., df se e solo se k = f e cl = dl per 1 ≤ l ≤ k, tale proprieta esprime il

fatto che una stringa che rappresenta una parola di C non puo rappresentare una

stringa di piu parole di C.

Da tale proprieta segue che un codice univocamente decifrabile e un codice che

consente una lettura di una sua stringa da sinistra a destra senza generare ambiguita.

Esempio 3

Il C = {1, 10, 100} e un codice decifrabile perche qualunque stringa formata dalle sue parole

e sempre leggibile in quanto il carattere “1” individua l’inizio di ogni singola parola. Nella

seguente stringa u = 1/10/100/1/1/1/1 si e posto il simbolo “/” per evidenziare meglio

l’inizio di ogni parola contenuta in essa.

Un’altra proprieta legata alla lettura delle stringhe di un codice C e quella legata

alla necessita di riconoscere le parole del codice appena esse sono state ricevute, se

un codice C ha questa proprieta esso e detto codice istantaneo.

Esempio 4

Il codice C = {1, 01, 001} e un codice decifrabile e istantaneo, perche al termine di ogni

parola viene posto il carattere 1 che garantisce il termine di ogni singola parola, tale codice

viene chiamato “comma code”. Il codice decifrabile descritto nell’esempio 3 invece non

ha le caratteristiche di essere istantaneo, infatti se ad esempio si e ricevuta la parola 10,

non possiamo dire subito se siamo in presenza della parola 10 o se quello che abbiamo

ricevuto e solo una parte della parola 100 cio si puo affermare solo alla ricezione del

carattere successivo.

Tutti i codici che sono istantanei sono chiaramente decifrabili, ma non e detto

che un codice decifrabile sia istantaneo, cio si deduce dalle considerazioni fatte

nell’esempio 4.

NB: Tutti i codici a blocchi sono decifrabili e istantanei.

5


I codici istantanei godono della proprieta del prefisso.

Proprieta 1 (del prefisso) In un codice istantaneo C nessuna parola e prefisso (e

posta all’inizio) di un’altra parola del codice, vale anche il viceversa. 2

La dimostrazione della proprieta 1 e immediata ed essa e importante in quanto

caratterizza i codici istantanei.

Per i codici istantanei si ha il seguente teorema.

Teorema 1 (di Kraft) Se C e un codice r-ario istantaneo costituito da n parole di

lunghezza li, con 1 ≤ i ≤ n, allora deve essere verificata la disuguaglianza di Kraft:

n∑i=1

1

rli≤ 1. (1.5)

Se esistono n interi positivi l1, l2,..., ln e r che verificano la disuguaglianza di Kraft,

allora esiste un codice istantaneo con n parole di lunghezza l1, l2, ...., ln.

Dim.

Dimostriamo la prima parte del teorema.

Sia C un codice costituito dalle parole {c1, c2, ...., cn} aventi rispettivamente lunghez-

za l1, l2, ...., ln. Sia L = max {l1, l2, ...., ln}, consideriamo la parola ci di lunghezza

li dove ci = x1x2.....xli , costruiamo una stringa di lunghezza L,

ui = x1x2.....xliyli+1yli+2.....yL,

dove i primi li caratteri sono la parola ci mentre gli ultimi L − li caratteri yj con

li + 1 ≤ j ≤ L sono caratteri scelti tra gli r caratteri dell’alfabeto del codice C

senza restrizioni e con la possibilita di essere ripetuti. Il numero totale di differenti

6


stringhe di tipo ui e rL−li (cio perche i primi li caratteri in ui rimangono sempre

invariati), inoltre si ha che tutte le stringhe ui formate non possono essere parole

del codice C in quanto esso e istantaneo e gode della proprieta del prefisso.

Ripetiamo tale procedura su ogni singola parola ci del codice per 1 ≤ i ≤ n, per

ognuna di esse si formano rL−li stringhe differenti tutte di lunghezza L. Sommando

su i si ottiene:

n∑i=1

rL−li =n∑

i=1

rL

rli(1.6)

La quantita espressa dalla (1.6) esprime il numero totale di stringhe ui che si ottiene

da ogni singola parola del codice ci con 1 ≤ i ≤ n ed esse sono tutte distinte e di

lunghezza L. Il valore rL esprime il numero totale di stringhe differenti di lunghezza

L che si possono formare con un alfabeto r-ario, ne segue che valgono le seguenti

disuguaglianze.

n∑i=1

rL

rli= rL

n∑i=1

1

rli≤ rL ⇒

n∑i=1

1

rli≤ 1. (1.7)

La (1.7) verifica la disuguaglianza di Kraft e la prima parte del teorema e provata.

Dimostriamo la seconda parte del teorema.

Determiniamo un algoritmo che permette di determinare un codice istantaneo che

abbia n parole rispettivamente di lunghezza l1, l2,..., ln. Se α1 e il numero delle

parole del nostro codice istantaneo C di lunghezza 1, allora e necessario che α1 ≤ r,

e importante notare che in caso di uguaglianza il codice avrebbe solo parole di

lunghezza uno; se α2 e il numero di parole di lunghezza 2 di C, allora tale valore

deve essere minore o uguale del numero totale di parole distinte di lunghezza 2 che si

possono formare con un alfabeto di r simboli, inoltre poiche C e un codice istantaneo

per esso vale la proprieta del prefisso ed e quindi necessario eliminare tutte le parole

7


di lunghezza 2 che hanno come prefisso le parole del codice di lunghezza 1, cioe deve

valere la seguente diseguaglianza:

α2 ≤ r2 − α1r.

Analogamente se α3 e il numero di parole del codice C con lunghezza 3 allora deve

valere la seguente disuguaglianza:

α3 ≤ r3 − α2r − α1r2. (1.8)

Dove il primo termine del secondo membro della (1.8) rappresenta il numero totale

di parole distinte di lunghezza 3 che si possono formare con un alfabeto di r simboli

a cui bisogna sottrarre le parole di lunghezza 3 che hanno come prefisso le parole del

codice di lunghezza 2 (secondo termine del secondo membro nella disuguaglianza

(1.8)) e le parole di lunghezza 3 che hanno come prefisso le parole del codice di

lunghezza 1 (terzo termine del secondo membro nella disuguaglianza (1.8)).

Se m e la massima lunghezza del codice C ( N.B. possono esistere lunghezze uguali

cioe li = lj) e consideriamo tutti i possibili αi per 1 ≤ i ≤ m, il codice istantaneo

esiste se ognuna delle seguenti disuguaglianze e vera.

α1 ≤ r

α1r + α2 ≤ r2

α1r2 + α2r + α3 ≤ r3

.

.

α1rm−1 + α2r

m−2 + ..... + αm ≤ rm

(1.9)

Vediamo cosa accade, ad esempio, se la terza disuguaglianza α1r2 + α2r + α3 ≤ r3

e vera. Tutti i suoi termini sono positivi, quindi si ha che vale anche la seguente

8


disuguaglianza α1r2 + α2r ≤ r3; e possibile dividere ambo i membri di quest’ultima

disuguaglianza per r, si ottiene α1r +α2 ≤ r2 , cioe anche la seconda disuguaglianza

delle (1.9) e vera, seguendo un analogo procedimento e facile verificare che anche la

prima disuguaglianza delle (1.9) e vera.

Sfruttando la metodologia usata nel precedente caso particolare si puo affermare che

se una delle disuguaglianze della (1.9) e vera allora sono vere tutte le disuguaglianze

che la precedono. Osserviamo l’ultima disuguaglianza delle (1.9), se dividiamo ambo

i membri per rm si ha:

α1

r+

α2

r2+ ..... +

αm

rm≤ 1,

cioe

m∑i=1

αi

ri=

n∑i=1

1

rli≤ 1.

Tale disuguaglianza e la disuguaglianza di Kraft ed e vera per le ipotesi del teorema,

quindi sono vere tutte le disuguaglianze che la precedono nella (1.9) e il teorema e

provato. 2

E importante notare che la seconda parte della dimostrazione del teorema precedente

afferma che se un codice verifica la disuguaglianza di Kraft non e detto che esso sia

istantaneo (vedi dall’esempio 6), ma afferma che se e verificata la disuguaglianza

di Kraft per i parametri l1, l2, ..., ln e r, allora e possibile costruire un codice

istantaneo r-ario con parole di lunghezza l1, l2, ...., ln mediante l’algoritmo presentato

dalla dimostrazione del teorema di Kraft.

9


Esempio 5

Consideriamo un codice 3-ario definito dall’alfabeto A = {0, 1, 2} si vuole vedere se esiste

un codice istantaneo con le seguenti lunghezze di parola: l1 = l2 = 1, l3 = 2, l4 = l5 = 4,

l6 = 5.

Come prima cosa verifichiamo se vale la disuguaglianza di Kraft:

23

+132

+033

+234

+135

=196243

≤ 1 (1.10)

La disuguaglianza e verificata, cerchiamo un codice istantaneo che verifica le lunghezze

l1 = l2 = 1, l3 = 2, l4 = l5 = 4, l6 = 5 seguendo l’algoritmo definito nella seconda parte

della dimostrazione del teorema di Kraft, le parole di lunghezza 1 sono c1 = 0, c2 = 1, la

parola di lunghezza 2 e c3 = 20, le parole di lunghezza 4 sono c4 = 2100, c5 = 2101, la

parola di lunghezza 5 e c6 = 21100. Il codice C = {0, 1, 20, 2100, 2101, 21100} e istantaneo

perche verifica la proprieta del prefisso.

Esempio 6

Il codice C = {0, 11, 100, 110} verifica la diseguaglianza di Kraft infatti si ha che:

12

+122

+223

= 1,

ma tale codice non e istantaneo perche non verifica la proprieta del prefisso.

Un codice istantaneo e anche decifrabile e dal teorema di Kraft e immediato ottenere

il seguente teorema.

Teorema 2 Se esistono n interi positivi l1, l2,..., ln e r che verificano la disu-

guaglianza di Kraft, allora esiste un codice decifrabile con n parole di lunghezza l1,

l2, ...., ln. 2

Resta da capire se per ogni codice decifrabile vale la disuguaglianza di Kraft, cioe se

la prima parte del teorema di Kraft vale anche per i codici decifrabili. La risposta

a tale quesito viene data dal seguente teorema di McMillan.

10


Teorema 3 (di McMillan) Se C = {c1, c2, ....., cn} e un codice decifrabile, allora

vale la disuguaglianza di Kraft:n∑

i=1

1

rli≤ 1. (1.11)

Dim.

Consideriamo α1, α2,..., αm il numero di parole del codice rispettivamente di lunghez-

za 1, 2,..., m. E facile verificare che il primo membro della disuguaglianza di Kraft

puo scriversi anche nel seguente modo:

n∑i=1

1

rli=

m∑j=1

αj

rj. (1.12)

Eleviamo le due sommatorie ad un valore u, intero positivo:

(n∑

i=1

1

rli

)u

=

(m∑

j=1

αj

rj

)u

=(α1

r+

α2

r2+ · · ·+ αm

rm

)u

. (1.13)

Per maggiore chiarezza l’ultimo membro della (1.13) puo essere scritto come il

prodotto di u sommatorie che rappresentano lo stesso termine:

(α1

r+

α2

r2+ · · ·+ αm

rm

)·(α1

r+

α2

r2+ · · ·+ αm

rm

)· · ·

(α1

r+

α2

r2+ · · ·+ αm

rm

). (1.14)

Lo svolgimento di tale prodotto puo essere svolto ed espresso come la somma dei

seguenti prodotti

∑i1,i2,··· ,iu

αi1αi2 · · ·αiu

ri1+i2+···+iu. (1.15)

La sommatoria della (1.15) e estesa su tutti gli i1, i2, · · · , iu con la limitazione

1 ≤ ij ≤ m con 1 ≤ j ≤ u. Posto k = i1 + i2 + ....iu la (1.15) puo anche

essere scritta nel seguente modo

11


u·m∑

k=u

∑

i1+i2+....+iu=k

αi1αi2 · · ·αiu

rk, (1.16)

Nella (1.16) il valore minimo che puo assumere k e u e il massimo e um e tale valore

all’interno della seconda sommatoria rimane sempre costante, quindi

u·m∑

k=u

1

rk

∑

i1+i2+···+iu=k

αi1αi2 · · ·αiu . (1.17)

Consideriamo adesso la quantita:

Nk =∑

i1+i2+···+iu=k

αi1αi2 · · ·αiu . (1.18)

Le quantita αi1 , αi2 ,..., αiu rappresentano tutte le possibili parole di lunghezza k

formate nel seguente modo: i primi i1 caratteri individuano una parola del codice di

lunghezza i1, i successivi i2 caratteri individuano una parola del codice di lunghezza

i2 fino ad arrivare agli ultimi iu che a loro volta sono una parola del codice di

lunghezza iu.

Figura 1.1: Stringhe della stessa lunghezza k, ma con sequenze di parole differenti e di

differente lunghezza.

Tutte queste stringhe essendo il codice decifrabile, quindi univocamente leggibile,

sono tutte distinte tra di loro come si evince dalla (fig1.1), ricordiamo che se si ha

un alfabeto r-ario il numero di tutte le possibili parole distinte di lunghezza k e rk,

da cui segue che

12

1.4 Codici ottimi

Nk =∑

i1+i2+···+iu=k

αi1αi2 · · ·αiu ≤ rk. (1.19)

Quindi la (1.17) puo essere scritta nel seguente modo:

u·m∑

k=u

1

rk

∑

i1+i2+....+iu=k

αi1αi1 ......αiu ≤u·m∑

k=u

1

rkrk =

u·m∑

k=u

1 = u ·m− u ≤ u ·m. (1.20)

In definitiva:

(n∑

i=1

1

rli

)u

≤ u ·m (1.21)

Elevando primo e secondo membro per1

usi ha:

n∑i=1

1

rli≤ (u)

1u (m)

1u (1.22)

Per la scelta arbitraria di u si vede facilmente che per u →∞ vale la disuguaglianza

di Kraft e il teorema e dimostrato. 2

1.4 Codici ottimi

Data una sorgente S0 consideriamo la famiglia C costituita da tutti i codici istantanei

che si possono associare a S0, chiaramente ad ogni codice di C e associata una sua

lunghezza media, consideriamo la lunghezza media minima lmin tra tutti i codici

istantanei Cist associati a S0, cioe

lmin = min{lCist

| ∀ Cist ∈ C} . (1.23)

Si definisce codice ottimo C un codice Cist istantaneo che ha lunghezza media lCist

uguale a lmin.

I codici ottimi godono delle seguenti tre proprieta.

13

1.4 Codici ottimi

Proprieta 2 Se C e un codice ottimo associato alla sorgente S0 = (S, P ) e c1,

c2,...., cn sono le sue parole rispettivamente di lunghezza l1, l2,...., ln allora si ha

che se pi > pj deve essere li ≤ lj ( cioe alla probabilita maggiore si associa la parola

di lunghezza minore)

Dim.

Supponiamo per assurdo che esiste un codice ottimo C per cui si ha che pi > pj e

li > lj. Costruiamo un codice C ′ ottenuto da C in cui alla parola ci e associata la

probabilita pj e alla parola cj e associata la probabilita pi mentre le altre parole ck

sono legate alla stessa probabilita pk del codice C. Calcoliamo le lunghezze medie

rispettivamente dei codici C e C ′ e consideriamo la loro differenza.

lC =n∑

k=16=i 6=j

pklk + pili + pjlj; (1.24)

¯lC′ =n∑

k=16=i6=j

pklk + pilj + pjli; (1.25)

¯lC′ − lC = pilj + pjli − pili − pjlj. (1.26)

Dopo facili calcoli si ottiene.

¯lC′ − lC = pi (lj − li)− pj (lj − li) = (pi − pj) (lj − li) (1.27)

Ricordando che li > lj, (lj − li < 0) e pi > pj (pi − pj > 0) ne segue che ¯lC′ − lC < 0

cioe ¯lC′ < lC . Si e quindi determinato un codice C ′ che e istantaneo, ma ha lunghezza

media minore della lunghezza media del codice ottimo C e cio e assurdo. 2

Proprieta 3 Sia C un codice ottimo e sia lm la maggiore lunghezza tra le lunghezze

delle parole del codice, allora esistono almeno due parole di lunghezza lm.

14

1.4 Codici ottimi

Dim.

Supponiamo per assurdo che esiste un codice ottimo C con una sola parola di

lunghezza lm. Calcoliamo la sua lunghezza media

lC =m−1∑

k=1

Pklk + Pmlm (1.28)

Consideriamo l’unica parola cm ∈ C di lunghezza lm e consideriamo il codice C ′

ottenuto da C modificando soltanto cm mediante l’eliminazione dell’ultimo carattere.

Il codice C ′ e un codice istantaneo perche gode della proprieta del prefisso e la sua

lunghezza media e:

¯lC′ =m−1∑

k=1

pklk + pm (lm − 1) . (1.29)

E evidente che ¯lC′ < lC . Si e determinato ancora una volta un codice istantaneo con

lunghezza media minore della lunghezza media del codice ottimo C e cio e assurdo.

2

Proprieta 4 Sia C un codice ottimo e cm una parola di lunghezza massima lm,

allora esiste un’altra parola ck di eguale lunghezza lm tale che i primi lm−1 caratteri

di cm e ck sono uguali.

Dim.

Per la proprieta precedente in un codice ottimo C esistano almeno due parole di

lunghezza massima lm. Supponiamo per assurdo che non esistono due parole di

lunghezza lm i cui primi lm − 1 caratteri sono uguali. Se consideriamo una di tali

parole e cancelliamo il suo ultimo carattere otteniamo un nuovo codice istantaneo

C ′ che gode della proprieta del prefisso (nessuna sua parola e prefisso di un’altra) e

la sua lunghezza media e minore della lunghezza media del codice ottimo C. 2

15

1.4 Codici ottimi

1.4.1 Algoritmo di Huffman

In questa sessione e presentato l’Algoritmo di Huffman che consente di indi-

viduare un codice ottimo data una distribuzione di probabilita P . Tale algoritmo e

valido per codici r-ari, ma qui sara presentata la procedura che riguarda solo i codici

binari.

Algoritmo di Huffman

1. Si ordina la distribuzione di probabilita P 0 = {P 01 , P 0

2 , · · · , P 0n} in modo tale

che le probabilta hanno un ordine decrescente secondo gli indici, cioe P 0i ≤ P 0

j

con i > j.

2. Le due probabilita di valore inferiore, cioe P 0n e P 0

n−1 si sommano, si ot-

tiene il valore P 0∗n−1 = P 0

n + P 0n−1. Si considera la distribuzione di probabilita

P 1 ={P 1

1 , P 12 , · · · , P 1

n−1

}in cui sono presenti tutte le probabilita di P 0 con

esclusione dei valori P 0n e P 0

n−1 al posto dei quali si e inserito il valore P 0∗n−1.

La distribuzione di probabilita P 1 e anch’essa ordinata in ordine decrescente

secondo gli indici e si ha che P 1i = P 0∗

n−1 per qualche i con 1 ≤ i ≤ n− 1.

3. Si ripete il passo precedente per altri n − 2 passi. In ogni singolo passo j si

determina una probabilita P j−1∗n−j data dalla somma delle due probabilita di

valore minore.

4. Si ottiene la distribuzione di probabilita P n−2 costituita da soli due valori.

5. Si associano alle probabilita di P n−2 le parole 1 e 0 (la scelta e arbitraria),

quindi alla distribuzione di probabilita P n−2 e associato il codice Cn−2.

6. Una delle probabilita di P n−2 e del tipo P n−2i = P n−3∗

2 = P n−32 + P n−3

3 con

i = 1, 2 (cioe del tipo P j−1∗n−j con j = n − 2), se ad essa nel passo precedente

e stato associato il carattere k ∈ {0, 1}, allora nella distribuzione P n−3 alle

16

1.4 Codici ottimi

probabilita P n−32 e P n−3

3 si associano le parole k1 e k0 (la scelta e arbitraria)

e per essa si ottiene il codice Cn−3.

7. Si ripete il procedimento precedente sino ad arrivare ad una assegnazione

di parole alla distribuzione P 0. Tali parole associate alle probabilita di P 0

definiscono un codice ottimo binario C0 e l’algoritmo e concluso.

Per maggiore chiarezza segue l’esempio 7 che permette di esplicitare tutti i passi

definiti nell’algoritmo precedente.

Esempio 7

Sia data la distribuzione di probabilita P 0 = {0.35, 0.20, 0.20, 0.15, 0.10}, le due probabilita

di valore minore sono 0.10 e 0.15, la loro somma e 0.25∗, si ottiene nuova distribuzione

di probabilita P 1 = {0.35, 0.25∗, 0.20, 0.20}. Seguendo lo stesso procedimento si sommano

0.20 e 0.20 si ottiene la distribuzione di probabilita P 2 = {0.40∗, 0.35, 0.25} e in seguito si

sommano i valori0.35 e 0.25 si ottiene P 3 = {0.60∗, 0.40}.Definiamo adesso una codifica binaria seguendo i passi 5, 6 e 7 partendo dalla distribuzione

P 3 fino ad arrivare alla distribuzione P 0. I passi dell’algoritmo sono ben riassunti dalla

tabella seguente.

0.35 01 0.35 01 0.40* 1 0.60* 0

0.20 11 0.25* 00 0.35 01 0.40 1

0.20 10 0.20 10 0.25 00

0.15 001 0.20 11

0.10 000

Tab.1

Il codice ottimo legato alla distribuzione di probabilita P 0 e C = {01, 11, 10, 001, 000}

E necessario adesso provare che il codice ottenuto dall’algoritmo di Huffmann e un

codice ottimo, cio e ottenuto dal teorema seguente.

17

1.4 Codici ottimi

Teorema 4 Se Ci e un codice ottimo ottenuto dall’algoritmo di Huffman, allora

anche Ci−1 e un codice ottimo. L’algoritmo di Huffmann genera un codice ottimo.

Dim.

Nell’ultima distribuzione di probabilita, che si ottiene eseguendo l’algoritmo di Huff-

man, e associato il codice ottimo Cn−2 = {0, 1}, quindi se in generale si prova che

l’algoritmo di Huffmann genera dal codice Ci ottimo il codice Ci−1 anch’esso ottimo,

allora si e provato il teorema.

Consideriamo il codice ottimo Ci ={c1, c2, ...., c

?m−1

}e applichiamo l’algoritmo di

Huffman al codice Ci, tenendo presente che L e la lunghezza della parola a cui si

legano la somma di due probabilia, si ottiene il codice Ci−1 = {c1, c2, ....., cm−10, cm−11},calcoliamo le lunghezze medie dei codici Ci e Ci−1:

li =m−2∑

k=1

pklk + (pm−1 + pm) L; (1.30)

li−1 =m−2∑

k=1

pklk + pm−1 (L + 1) + pm (L + 1) . (1.31)

Ricordiamo che nel codice Ci−1 le parole cm−10 cm−10 e parole hanno lunghezza

L + 1. Sottraendo membro a membro la (1.30) dalla (1.31) si ha:

li−1 − li = pm−1 + pm ⇒ li−1 = li + pm−1 + pm. (1.32)

Supponiamo per assurdo che Ci−1 non sia un codice ottimo e quindi esiste un codice

ottimo C ′i−1, associato alla distribuzione di probabilita di Ci−1, tale che l′i−1 < li−1.

Se C ′i−1 e ottimo, per le proprieta 2, 3 e 4, esisteranno due parole di lunghezza

massima e aventi i primi L′ − 1 caratteri uguali con associate le probabilita pm e

pm−1, cioe C ′i−1 =

{c′1, c

′2, ...., c

′m−10, c

′m−11

}. Applicando l’algoritmo di Huffman in

senso opposto si determina un nuovo codice C ′i =

{c′1, c

′2, ...., c

′?m−1

}. Anche per i due

codici C ′i e C ′

i−1 vale la relazione:

18

1.5 La funzione entropia

l′i−1 = l′i + pm−1 + pm. (1.33)

Poiche si e supposto che C ′i−1 e ottimo mentre per assurdo Ci−1 non lo e allora deve

valere la seguente disuguaglianza:

l′i−1 < li−1 (1.34)

Se cio e vero confrontando le equazioni (1.32) e (1.33) si ha che vale la seguente

disuguaglianza.

l′i < li (1.35)

Cio implica che Ci non e ottimo, questo e assurdo e il teorema e provato. 2


Nell’esempio 1 si e vista l’importanza della conoscenza della distribuzione delle

probabilita, da qui nasce l’esigenza di determinare una funzione che permetta di

“misurare” la conoscenza del sistema mediante la conoscenza della sua distribuzione

di probabilita. Tale funzione H e la funzione entropia che e differente dalla grandez-

za fisica usata in termodinamica. Essa nasce dagli studi relativi alla conoscenza di

“informazioni” di un sistema fatti da Shannon nel 1948.

Consideriamo la variabile random X a cui associamo gli eventi X = {x1, x2, ..., xq}.A ciascuno degli eventi xi e possibile associare una distribuzione di probabilita P =

{p1, p2, ..., pq}.La funzione entropia deve soddisfare le seguenti tre proprieta:

1. Se tutte le probabilita di P sono uguali cioe pi =1

qallora H e una funzione

crescente, cioe se q < q′ allora si ha:

19


H

(1

q,1

q, ...,

1

q

)< H

(1

q′,1

q′, ...,

1

q′

)

.

Nella realta questa proprieta esprime che maggiore e il numero di eventi q

maggiore e l’incertezza legata agli eventi.

2. H e una funzione continua cioe a piccole variazioni di probabilita corrispondono

piccole variazioni di H.

3. Vale il principio che un esperimento puo essere scomposto in una successione

di esperimenti successivi.

Esempio 7

Diamo per quest’ultima proprieta un esempio di un esperimento che e rappresentato grafi-

camente nella seguente figura. Esso ha una distribuzione di probabilita P = {12,13,16} e

puo essere scomposto nella successione dei due esperimenti di probabilita P ′ = {12,12} e

P ′′ = {23,13}.

Tale scomposizione puo essere rappresentata mediante la funzione entropia nel seguente

modo:

H

(12,13,16

)= H

(12,12

)+

12H

(23,13

).

20


Teorema 5 La sola funzione che verifica le tre proprieta 1, 2 e 3 e:

H(p1, p2, · · · , pq) = −c

q∑i=1

pi logb pi (b > 1) (1.36)

con c costante positiva.

Dim.

Poniamo

H

(1

q, · · · ,

1

q

)= f(q). (1.37)

Supponiamo di avere sm eventi legati ad una determinata variabile random. Poiche

deve valere la terza proprieta, sm puo essere scomposto in m sequenze di s eventi,

cioe:

f(sm) = mf(s). (1.38)

Fissati t e n interi positivi e sempre possibile determinare un m tale che:

2m ≤ tn < 2m+1. (1.39)

Passando ai logaritmi in base b e sfruttando le loro proprieta si ha:

logb 2m ≤ logb tn < logb 2m+1, (1.40)

m logb 2 ≤ n logb t < (m + 1) logb 2. (1.41)

Dividendo per n logb 2

m

n≤

︸︷︷︸1◦

logb t

logb 2

2◦︷︸︸︷<

m + 1

n. (1.42)

21


Poiche f(q), per le proprieta 1 e 2, e una funzione continua e crescente si ha che

applicandola alle disuguaglianze della (1.39) esse continuano a sussistere, cioe:

f(2m) ≤ f(tn) < f(2m+1), (1.43)

dividendo per nf(2):

m

n≤

︸︷︷︸1◦

f(t)

f(2)

2◦︷︸︸︷<

m + 1

n. (1.44)

Moltiplicando la 1◦ disuguaglianza della (1.44) per −1 si ottiene:

− f(t)

f(2)≤ −m

n. (1.45)

Sommando la (1.45) con la 2◦ disuguaglianza della (1.42) si ha:

logb t

logb 2− f(t)

f(2)<

1

n. (1.46)

Allo stesso modo, moltiplicando la 2◦ disuguaglianza della (1.44) per −1 si ottiene:

− f(t)

f(2)> −m

n− 1

n. (1.47)

Sommando la (1.47) con la 1◦ disuguaglianza della (1.42) si ha:

logb t

logb 2− f(t)

f(2)> − 1

n, (1.48)

da cui si ricava:

− 1

n<

logb t

logb 2− f(t)

f(2)<

1

n⇒

∣∣∣∣logb t

logb 2− f(t)

f(2)

∣∣∣∣ <1

n(1.49)

e per n →∞ si ha:

limn→∞

∣∣∣∣logb t

logb 2− f(t)

f(2)

∣∣∣∣ = 0 ⇒ logb t

logb 2=

f(t)

f(2)⇒ f(t) = f(2)

logb t

logb 2= c logb t. (1.50)

Consideriamo adesso una distribuzione di probabilita con probabilita razionali:

pi =ki∑j kj

con ki intero ∀i e∑

i

ki∑j kj

= 1 (1.51)

22


Scomponiamo l’esperimento in una successione di due eventi mediante le distribuzioni

di probabilita rappresentate nella figura seguente.

E possibile allora scrivere:

H

(1∑ki

,1∑ki

, · · · ,1∑ki

)= H (p1, p2, ..., pm) + p1c logb k1 + p2c logb k2 + · · ·

+ pmc logb km = H (p1, p2, ..., pm) + c∑

pi logb ki.

Dopo semplici calcoli si ha:

H (p1, p2, ..., pm) = H

(1∑i ki

,1∑i ki

, ...,1∑i ki

)− c

∑i pi logb ki =

c logb

∑i ki − c

∑i pi logb ki = c logb

∑j kj ·

∑i

ki∑j kj

− c∑

i

pi logb ki =

c∑

i

pi logb

∑j

kj − c∑

i

pi logb ki = −c∑

i

pi logb

ki∑i kj

= −c∑

i

pi log pi.

La condizione necessaria del teorema e provata.

Il viceversa se Hb(p1, p2, · · · , pm) = −c∑m

i=1 pi logb pi allora si ha che le proprieta

sono tutte verificate e il teorema e provato. 2

Dal teorema precedente si ha che per un sistema che ha una distribuzione di probabi-

lita P = {p1, p2, · · · , pm} la funzione entropia e definita come la quantita:

Hb(p1, p2, · · · , pm) = −m∑

i=1

pi logb pi.

23


Dove la costante c e stata normalizzata a 1. Se il valore di b in H e 2 allora l’entropia

prende il nome di entropia binaria.

1.5.1 Proprieta della funzione entropia

Siano X e Y due variabili random e sia p(xi, yj) la probabilita congiunta delle due

variabili, allora l’entropia congiunta a X e Y e definita come:

H(X, Y ) =∑i,j

p(xi, yj) log1

p(xi, yj). (1.52)

Enunciamo il seguente lemma omettendo la dimostrazione.

Lemma 1 Sia {p1, p2, · · · , pm} una distribuzione di probabilita e sia {q1, q2, ..., qm}una sequenza di numeri reali con 0 ≤ qi ≤ 1 e

∑qi ≤ 1, allora si ha che:

∑pi log

1

pi

≤∑

pi log1

qi

(1.53)

Consideriamo adesso una sequenza di teoremi che permettono di evidenziare alcune

proprieta della funzione entropia.

Teorema 6 Se X e una variabile aleatoria si ha che:

0 ≤ H(X) ≤ log q (1.54)

Dim.

Chiaramente H(X) ≥ 0. Per definizione di entropia si puo scrivere:

H(X) =

q∑i=1

pi log1

pi

≤q∑

i=1

pi log11q

=

q∑i=1

pi log q (1.55)

da cui:

H(X) ≤ log q (1.56)

2

24


Teorema 7 Siano X e Y due variabili random, allora si ha:

H(X, Y ) ≤ H(X) + H(Y ) (1.57)

Dim.

Se consideriamo la distribuzione di probabilita congiunta ad X e Y e sommo solo

secondo l’indice legato a una variabile random (cioe si varia i lasciando fissato j e

viceversa) si ha:

∑j

p(xi, yj) = p(xi), (1.58)

∑i

p(xi, yj) = p(yj). (1.59)

quindi:

H(X) + H(Y ) =∑

i

p(xi) log1

p(xi)+

∑j

p(yj) log1

p(yj)=

=∑

i,j p(xi, yj) log1

p(xi)+

∑i,j

p(xi, yj) log1

p(yj)=

=∑

i,j p(xi, yj) log1

p(xi)p(yj)≥

∑i,j

p(xi, yj) log1

p(xi, yj)= H(X, Y ).

Il teorema e provato. 2

Siano X e Y due variabili random e p(yj|xi) la distribuzione di probabilita dell’evento

Y condizionato dall’evento X, definiamo l’entropia condizionata nel seguente

modo:

H(X|Y ) =∑i,j

p(yj)p(xi|yj) log1

p(xi|yj)=

∑j

p(yj)H(X|yj) (1.60)

Teorema 8 Se X e Y sono due variabili random, allora:

H(X|Y ) = H(X,Y )−H(Y ). (1.61)

25


Dim.

Dalla precedente definizione abbiamo:

H(X|Y ) =∑i,j

p(yj)p(xi|yj) log1

p(xi|yj). (1.62)

Ricordando che:

p(xi|yj) =p(xi, yj)

p(yj). (1.63)

possiamo scrivere:

H(X|Y ) =∑i,j

p(xi, yj) logp(yj)

p(xi, yj)=

∑i,j

p(xi, yj) log1

p(xi, yj)−

∑i,j

p(xi, yj) log1

p(yj)= H(X,Y )−

∑j

p(yj) log1

p(yj)= H(X,Y )−H(Y ).


Consideriamo l’insieme dei possibili segnali che si presentano in ingresso ad un rice-

vitore E = {a1, ....., am}, supponiamo di avere associata ad esso una distribuzione

di probabilita p(ai) con 1 ≤ i ≤ m. Possiamo allora scrivere l’entropia in ingresso

come:

H(E) = −∑

i

p(ai) log p(ai) =∑

i

p(ai) log1

p(ai)(1.64)

Siano U = {u1, ..., um} l’insieme dei segnali prodotti dalla sorgente in trasmissione,

possiamo definire informazione la quantita:

I(E,U) = H(E)−H(E|U). (1.65)

Da essa e possibile definire capacita del canale come la quantita

C = maxEI(E,U). (1.66)

Essa e legata alla determinazione di una distribuzione di probabilita E tale che

rende massima I(E, U).

26

Capitolo 2

Teoria dei Codici

I Primi concetti

2.1 Introduzione

In questo capitolo vengono presentati i primi concetti legati alla teoria dei codici. Le

prime domande che si pongono sono legate alle motivazioni dell’origine della teoria

dei codici e alla sua utilita.

Quando un sistema trasmissivo invia delle informazioni ad un sistema ricevente,

possiamo pensare ad una comunicazione telefonica o trasmissioni via etere o anche

trasmissioni che provengono dall’esterno del nostro pianeta inviate da sonde, astro-

navi o shuttle, nella realta fisica del nostro universo puo accadere che tali trasmissioni

vengano distorte e il segnale trasmesso ne risulti alterato nella sua ricezione.

Il sistema su cui vengono inviate le informazioni viene chiamato canale. Esso puo

essere individuato dal mezzo trasmissivo su cui vengono inviate informazioni in una

normale comunicazione telefonica o un in invio dati tra due sistemi informatici col-

legati, il canale puo anche essere costituito dallo spazio in cui si propagano onde

27

2.1 Introduzione

elettromagnetiche che trasportano informazioni. In ogni canale esiste sempre la pre-

senza di rumore che compromette la trasmissione. Tale rumore si puo legare a

interferenze elettromagnetiche (disturbi radio, attivita solare, ecc.), competizioni di

trasmissione, fattori di disturbo random, e tanti altri fattori, ognuno legato al tipo

di trasmissione che si sta effettuando.

Un altro tipo di applicazione della teoria dei codici si ha quando si leggono in-

formazioni su un “supporto”, in questo caso il rumore puo essere legato alla non

perfetta condizione del supporto (ad esmpio sporcizia, presenza di graffi in CD o

DVD o invecchiamento del supporto) o a difficolta del sistema di lettura.

Per motivazioni legate al sistema hardware l’informazione viaggia in sequenza di

informazioni binarie e quindi essa viaggia mediante codici binari. In questi appunti

a partire da questo capitolo saranno trattati codici a blocchi.

La motivazione per cui nella maggior parte dei casi si usano codici a blocchi sta nel

fatto che l’esperienza fisica e quindi la rigorosa osservazione sperimentale, associa

ai sistemi trasmissivi una distribuzione di probabilia costante. In particolare come

detto precedentemente l’alfabeto usato e del tipo A = {0, 1} e ogni suo carattere e

chiamato bit. Ad ogni singolo bit, come rappresentato nella figura 2.1, puo essere

associata una probabilita p che esprime la probabilita che esso venga ricevuto cor-

rettamente, chiaramente la probabilita che un bit non sia trasmesso correttamente

e 1− p.

La probabilita p e chiaramente legata al sistema trasmissivo ed essa prende il nome

di efficienza del canale, negli attuali sistemi trasmissivi essa supera il valore 0.97

cioe puo assumere valori molto alti, ma e evidente che in un numero di bits molto

alto la probabilita che l’informazione venga inficiata da errore non e trascurabile.

Un canale Ch1, con efficienza p1, si dice piu efficiente del canale Ch2, di efficienza p2,

se si ha che p1 > p2.

Varie sono state nel tempo le tecniche di controllo e/o correzione di errore, alcune

28

2.1 Introduzione

P - 1 P - 1

P

P

0 0

11

Figura 2.1:

delle quali molto semplici come, ad esempio, l’aggiunta di un bit ad ogni parola di

un codice in modo tale che tutte le sue parole contengano un numero pari di bits

di valore “1”. Il codice C = {111, 011, 001, 100, 110, 010} con l’aggiunta del bit di

parita diventa C ′ = {1111, 0110, 0011, 1001, 1100, 0101}, si vede facilmente che se

si riceve la parola 0010 avendo un numero di bits di valore “1” dispari non e una

parola del codice.

Un’altra tecnica di controllo e correzione di errore, detta di ridondanza, e quella

di trasmettere piu volte la stessa parola e, in ricezione, di controllare se anche la

sequenza di ricezione ha sempre la stessa ripetizione, se cio non avviene allora si ef-

fettua la correzione scegliendo nella sequenza la parola del codice che e stata ripetuta

piu volte. Questa tecnica contrariamente alla precedente oltre ad individuare l’er-

rore permette anche di correggerlo, inoltre maggiore e il numero di ripetizioni di una

stessa parola in una sequenza, maggiore e la probabilita che la correzione sia esatta.

Esiste pero un importante inconveniente in tale tecnica, essa infatti non permette

un numero elevato di ripetizioni dato che maggiore e il loro numero, minore e la

velocita di trasmissione di informazione.

29

2.2 Probabilita e distanza


Il problema della correzione delle parole del codice e essenzialmente legato al concetto

di probabilita. La probabilita che la parola v, avente lunghezza n e appartenente

al codice a blocchi C di efficienza p, sia trasmessa correttamente e pn. Supponiamo

adesso di trasmettere la parola v ∈ C, ma di ricevere la parola w /∈ C, come risolvere

il problema della correzione di w?

E necessario definire una funzione che determini la probabilita che la parola v ∈ C

sia trasmessa e la parola w /∈ C sia ricevuta. In generale tale funzione puo essere

definita, indipendentemente dal concetto di parola inviata e ricevuta, nel seguente

modo:

φ : Kn ×Kn → [0, 1],

dove Kn esprime l’insieme di tutte le possibili parole di lunghezza n i cui caratteri

appartengono all’insieme K = {0, 1}, K rappresenta quindi l’alfabeto del codice.

Se Φ (v, w) e la probabilita che la parola v ∈ C e stata inviata e w ricevuta, allora

si ha:

Φ (v, w) = pn−d (1− p)d , (2.1)

dove d e il numero di bits differenti tra le parole v e w, n e la lunghezza delle parole

del codice C, n − d rappresenta il numero di bits trasmessi correttamente, d i bits

trasmessi in maniera errata e 1 − p e la probabilita che un singolo bit giunga in

maniera errata. La quantita d e chiamata distanza tra le parole v e w e si indica

con la simbologia d (v, w). Chiaramente non e difficile provare che tra due parole di

lunghezza n vale la seguente uguaglianza d (v, w) = d (w, v).

30


Esempio 1

Sia C un codice a blocchi di lunghezza 5. Per ogni parola v ∈ C la probabilita che v sia

ricevuta correttamente (cioe w = v) e:

Φ(v, v) = p5

Se invece la parola inviata e v = 10011 e quella ricevuta e w = 11001, allora la distanza

tra v e w e 2 e si ha che:

Φ(v, w) = p3(1− p)2

Individuiamo adesso una tecnica che permette di determinare la correzione di un

errore in ricezione. Supponiamo di aver ricevuto la parola w e che essa non appar-

tiene al codice C. Tale tecnica di correzione di errore e basata sull’individuazione

della parola v′ ∈ C tale che ad essa e associata la probabilita massima rispetto alla

parola ricevuta w mediante la funzione Φ cioe:

Φ (v′, w)max = max {Φ (v, w) : v ∈ C} . (2.2)

Quindi se si riceve una parola w non appartenente al codice a blocchi C si individua

la parola del codice v′ tale che la funzione Φ e massima al variare di v in C, fissata

w. Tale parola v′ si sostituisce a w.

E possibile che in tale tecnica si abbia un insieme di parole del codice che hanno

tutte la stessa probabilita massima, in tal caso si genera un’ambiguita, in seguito

vedremo come affrontare tale evenienza.

Consideriamo adesso un risultato che permette di associare il concetto di probabilita

definito dalla funzione Φ al concetto di distanza tra due parole.

31


Teorema 9 Sia C un codice a blocchi di lunghezza n, con1

2< p < 1 e siano v1 e

v2 due parole del codice C. Se d1 e la distanza tra v1 e la parola ricevuta w e d2 e

la distanza tra v2 e w, allora si ha che:

Φ(v1, w) < Φ(v2, w) (2.3)

se e solo se d1 > d2, vale anche il viceversa.

Dim.

La disuguaglianza

Φ(v1, w) < Φ(v2, w)

vale se e solo se:

pn−d1 (1− p)d1 < pn−d2 (1− p)d2 ;

pn−d1 (1− p)d1

pn−d2 (1− p)d2< 1;

pn−d1−n+d2 (1− p)d1−d2 < 1;

pd2−d1 (1− p)−(d2−d1) < 1;

(p

1− p

)d2−d1

< 1. (2.4)

Poiche per le ipotesi1

2< p < 1 si ha che p > 1− p ovvero:

p

1− p> 1,

32


allora la (2.4) e vera se e solo se l’esponente e negativo cioe se:

d2 − d1 < 0 ⇒ d2 < d1, (2.5)

e il teorema e provato. 2

Il teorema precedente assume una rilevanza fondamentale in quanto permette di

abbandonare il concetto di probabilita e di sostituirlo con il concetto di distanza tra

due parole.

La tecnica di correzione di errore esposta precedentemente adesso cambia nel seguente

modo: se si riceve una parola w non appartenente al codice C si individua la parola

v′ ∈ C che ha distanza minima da w e si sostituisce a w, cio equivale al fatto che la

funzione Φ(v, w), fissata w, assume valore massimo per v′ ∈ C. L’esempio seguente

chiarisce meglio tale tecnica.

Esempio 2

Sia il codice C = {01101, 01001, 10100, 10101} e supponiamo di ricevere la parola w =

00110 non appartenente al codice C. Esaminiamo la tabella seguente.

C w distanza

c1 01101 00110 3

c2 01001 00110 4

c3 10100 00110 2

c4 10101 00110 3

Tab.1

La parola del codice che ha distanza minima da w e c3 = 10100, tale parola e quella che

corregge w ed e quella che tra tutte le parole del codice C ha la massima probabilita di

essere stata inviata in trasmissione.

33

2.3 Peso ed errore

2.3 Peso ed errore

Si e precedentemente detto che l’alfabeto dei codici a blocchi e K = {0, 1}, ma tale

insieme di caratteri e anche un insieme numerico e su di esso possono essere definite

due operazioni algebriche binarie, una di somma e l’altra di prodotto definite dalla

tabella seguente.

Somma Prodotto

0 + 0 = 0 0 · 0 = 0

1 + 0 = 1 1 · 0 = 0

1 + 0 = 1 0 · 1 = 0

1 + 1 = 0 1 · 1 = 1

Tab.2

Le due operazioni di somma e prodotto danno all’insieme K le proprieta di campo.

L’insieme Kn, come precedentemente detto, e l’insieme di tutte le possibili differenti

parole binarie di lunghezza n, tale insieme e finito ed ha cardinalita uguale a 2n,

perche ogni singola componente di una parola di Kn puo assumere valori “0” o “1”.

L’insieme Kn puo anche assumere la struttura di spazio vettoriale se si interpretano

le sue parole come vettori e su di esse si definiscono le operazioni di somma vettoriale

e di prodotto esterno tra gli elementi di K e Kn mediante i concetti di spazio

vettoriale introdotti nei corsi base di algebra lineare. La somma tra le componenti

corrispondenti di due parole e data dall’operazione di somma definita su K. Un

esempio di somma tra le due parole (101) e (111) e: (101) + (111) = (010).

E importante notare che la somma di due parole uguali e uguale alla parola che

possiede in tutte le sue componenti bits di valore “0”, tale parola e detta nulla e si

34

2.3 Peso ed errore

indica con il simbolo 0, cioe ∀v ∈ Kn si ha che v + v = 0. Tale proprieta permette

di capire che la parola opposta di una qualunque parola v ∈ Kn e la parola stessa.

Si ha inoltre che vale la seguente proprieta.

Proprieta 5 Se v + w = 0, allora si ha che v = w. 2

Si e preferito evidenziare tale proprieta perche molto spesso chi comincia a studiare

questi argomenti commette l’errore di scrivere v = −w, cio e sbagliato!!!

Infatti se vale l’eguaglianza v + w = 0, allora vale anche v + w + w = w che e

equivalente a v + 0 = w ed infine si ha v = w.

Diamo adesso l’importante nozione di errore per un codice C a blocchi. Supponiamo

che e stata inviata la parola v ∈ C e si sia ricevuta la differente parola w, allora si

definisce errore tra v e w la parola u cosı definita:

u = v + w. (2.6)

Il concetto di errore legato alle parole v e w puo per certi versi sembrare “strano”,

infatti nella sua definizione si capisce facilmente che per determinare u non solo e

necessaria la parola w conosciuta in ricezione, ma anche la parola trasmessa. Questo

non deve sorprendere se si pensa che, come vedremo nel capitolo 3 e nei successivi,

la teoria dei codici in correzione di errore ha come obiettivo principale quello di

individuare, mediante tecniche matematiche, la parola u indipendentemente dalla

conoscenza di v. Se si riesce in tale obiettivo, dopo aver verificato che w /∈ C, per

determinare v basta sommare le parole w + u e si ottiene la parola inviata.

Se v ∈ Kn, allora si definisce peso di v il numero di bits che hanno valore “1” in v.

Tale valore si esprime secondo la simbologia wt(v). Ad esempio il peso della parola

v = 011001 ∈ K6 e uguale a tre, cioe wt (011001) = 3.

35

2.3 Peso ed errore

Esiste una relazione tra il peso e la distanza dell’errore. Infatti date due parole

distinte v e w, la loro distanza d(v, w) rappresenta il numero di bits tra loro differenti.

La somma u = v + w individua la parola u, diversa dalla parola nulla, che ha la

caratteristica di possedere bits di valore “1” nelle componenti in cui v e w sono tra

loro differenti, cio comporta che la parola u ha peso uguale alla distanza tra v e w

cioe:

d(v, w) = wt(u). (2.7)

Se d e la distanza tra le parole v e w, allora l’equazione (2.1) si puo anche scrivere

nel seguente modo:

Φ (v, w) = pn−d (1− p)d = pn−wt(u) (1− p)wt(u) . (2.8)

Esempio 3

Siano v = 011001 e w = 111101 parole di K6, si ha che u = v + w = 100100 allora segue

che: d(v, w) = wt(v + w) = 2.

Di seguito sono enunciate una serie di proprieta legate ai concetti di distanza e di

peso.

Proprieta 6 Date due parole v e w di Kn allora valgono le seguenti quattro pro-

prieta.

1. d(v, u) + d(u,w) ≥ d(v, w);

2. wt(v + w) ≤ wt(v) + wt(w);

36

2.4 Prime tecniche di codifica

3. wt(av) = a · wt(v) con a ∈ K;

4. d(av, aw) = a · d(v, w) con a ∈ K. 2

La prima disuguaglianza delle precedenti e la disuguaglianza triangolare.

Diamo adesso un’altra importante definizione. Si definisce distanza o distanza di

Hamming di un codice binario C l’intero dc cosı definito:

dc = min {d(v′, v′′), v′, v′′ ∈ C} = min {wt(v′ + v′′), v′, v′′ ∈ C} . (2.9)

Tale parametro, se non vi e alcuna ambiguita legata al codice C, si denotera con

la semplice simbologia d. La distanza d e uno dei tre parametri che, in seguito,

caratterizza un codice a blocchi.


La tecnica di decodifica che e presentata in questa sessione e basata sulla ricerca tra

tutte parole del codice C della parola che, in termini di distanza, e la piu vicina alla

parola che e stata ricevuta e che non appartiene al codice.

Tale tecnica prende il nome di MLD dall’inglese “Maximum Likelihood Decoding”

cioe massima probabilta di decodifica.

Il seguente esempio mostra in maniera pratica l’utilizzo di tale tecnica su un codice

estremamente banale, ma utile a scopi didattici.

37


Esempio 4

Sia il codice di lunghezza 3, C = {000, 111}. Consideriamo tutte le differenti parole di

K3, esse sono 23 e K3 = {000, 001, 010, 011, 100, 101, 110, 111}.

Parola

ricevuta

Errore

000 + w

Errore

111 + w

Decodifica

000 000∗ 111 000

001 001∗ 110 000

010 010∗ 101 000

011 011 100∗ 111

100 100∗ 011 000

101 101 010∗ 111

110 110 001∗ 111

111 111 000∗ 111

Tab.3

La prima colonna della tabella precedente rappresenta tutte le possibili parole di lunghez-

za tre che possono essere ricevute, cioe w, la seconda e terza colonna rappresentano la

somma della singola parola del codice C e la parola w cioe tali colonne rappresentano gli

errori 000 + w e 111 + w. L’ultima colonna individua la parola di C che “correggera” w.

Supponiamo che la parola 001 e ricevuta, nella terza riga della tabella si considerano gli

errori 001 e 110, tra essi si determina la parola del codice che sommata a 001 ha errore di

peso minore, cioe 000 corrispondente all’errore 001. Nella tabella gli errori di peso minore

su ogni riga vengono evidenziati mediante asterisco.

Nell’esempio 4 e importante notare che che la scelta della parola di peso minore e

dovuta al fatto che d(v, w) = wt(v+w) e a quanto affermato dal teorema 9, date due

38


parole del codice C v1 e v2 se si ha che d(v1, w) = wt(v1+w) < d(v2, w) = wt(v2+w)

allora la parola v1 ha maggiori probabilita di essere stata inviata rispetto alla parola

v2.

Il codice dell’esempio 4, come gia detto, e estremamente semplice ed inoltre per

ogni parola ricevuta non possiede alcuna ambiguita, cioe su ogni parola ricevuta w

e sempre possibile fare una correzione. In codici piu complessi puo accadere che per

una parola ricevuta si determina un insieme di errori dello stesso peso in tal caso la

tecnica MLD si scinde in due strategie di correzione.

• CMLD(complete MLD): Ricevuta w /∈ C, se vi sono piu parole del codice con

lo stesso errore minimo, allora tra tali parole se ne sceglie una arbitrariamente

o mediante tecniche ponderate.

• IMLD(incomplete MLD): Ricevuta w /∈ C, se vi sono piu parole del codice

con lo stesso errore minimo, allora si richiede la ritrasmissione del messaggio.

La ritrasmissione del messaggio puo essere anche chiesta quando si riceve una

parola w “troppo” distante da tutte le parole del codice, il“troppo” e legato

al tipo di strategia che si vuole adottare in correzione.

39


Esempio 4

Parola

ricevuta

Errore

0000 + w

Errore

1010 + w

Errore

0111 + w

Decodifica

0000 0000∗ 1010 0111 0000

1000 1000 0010 1111 −−−−0100 0100∗ 1110 0011 0000

0010 0010 1000 0101 −−−−0001 0001∗ 1011 0110 0000

1100 1100 0110 1011 −−−−1010 1010 0000∗ 1101 1010

1001 1001 0011 1110 −−−−0110 0110 1100 0001∗ 0111

0101 0101 1111 0010∗ 0111

0011 0011 1001 0100∗ 0111

1110 1110 0100∗ 1001 1010

1101 1101 0111 1010∗ 0111

1011 1011 0001∗ 1100 1010

0111 0111 1101 0000∗ 0111

1111 1111 0101 1000 0111

Tab.4

La tabella 4 e legata al codice di lunghezza 4 C = {0000, 1010, 0111} e mostra che nelle

righe 2a, 4a, 6a e 8a la tecnica IMLD chiede sempre la ritrasmissione.

40

2.5 Individuazione di errore


Un codice C individua un errore u se e solo se v + u /∈ C ∀v ∈ C.

Esempio 5

Consideriamo il seguente codice C = {001, 101, 110}, vediamo se esso individua l’errore

u = 010. Per far cio sommiamo tale errore ad ogni parola del codice e verifichiamo che

tale parola non appartiene a C.

001 + 010 = 011 /∈ C

101 + 010 = 111 /∈ C

110 + 010 = 100 /∈ C

Il codice C individua l’errore u = 010.

Consideriamo adesso l’errore u′ = 100.

001 + 100 = 101 ∈ C

101 + 100 = 001 ∈ C

110 + 100 = 010 /∈ C

Il codice C quindi individua l’errore u ma non individua l’errore u′.

Il risultato seguente individua un insieme di errori che possono essere individuati da

un codice C.

Teorema 10 Sia C codice a blocchi di lunghezza n e distanza d, allora C individua

tutti gli errori diversi dalla parola nulla e con peso minore o uguale a d− 1. Esiste

almeno un errore di peso d che non puo essere individuato da C.

Dim.

Consideriamo un errore u 6= 0 il cui peso e wt(u) ≤ d− 1 con d 6= 1, ∀ v ∈ C si ha

che:

41


d(v, v + u) = wt(v + v + u) = wt(u) ≤ d− 1 (2.10)

Poiche C ha distanza d segue che prese due generiche parole v′ ∈ C e v′′ ∈ C allora

d(v′, v′′) ≥ d, quindi se v ∈ C e vale la (2.10) allora si ha che v + u /∈ C. Vista

l’arbitrarieta della scelta di v la prima parte del teorema e provata.

Se d e la distanza del codice allora esistono almeno due parole c′ ∈ C e c′′ ∈ C

tale che d(c′, c′′) = d. Sia u = c′ + c′′ e evidente che wt(u) = d e c′′ = u + c′ ∈ C.

Si e trovato un errore u con peso d che non viene individuato da C e il teorema e

provato. 2

Se d e la distanza di un codice C, allora C si dira d - 1 error-detecting.

Esempio 6

Il codice C = {000, 111} ha distanza d = 3 ed e 2-error-detecting.

Esempio 7

Il codice C = {001, 101, 110} ha distanza d = 1. Poiche d− 1 = 0 si ha che il teorema 10,

in questo caso, non ci aiuta alla determinazione di errori individuati da C.

Dall’esempio precedente e importante notare che il teorema 10 indica che se vi e

codice C avente distanza d allora tutte le parole di peso d−1 sono errori individuati

da C, ma non e detto che non vi possano essere errori di peso maggiore o uguale

a d individuati dal codice, nell’esempio 7 si ha che d − 1 = 0, ma la parola 010 e

chiaramente un errore individuato da C come si evince dall’esempio 5.

42

2.6 Correzione di errore


In questa sessione e caratterizzato un particolare errore legato al codice C che oltre

ad essere individuato permette una correzione della parola ricevuta.

Si dice che un codice C corregge un errore u se e solo se, comunque si fissi w ∈ C

e w 6= v, vale la disuguaglianza:

d(w, v + u) > d(v, v + u) (2.11)

Esempio 8

Sia dato il codice C = {000, 111} e l’errore u = 010. Supponiamo che la parola inviata sia

v = 000. In questo caso u + v = (010) + (000) = 010, pertanto:

d(000, u + v) = d(000, 010) = wt(010) = 1

d(111, u + v) = d(111, 010) = wt(101) = 2.

Consideriamo adesso che la parola inviata e v = 111, in questo caso u+v = (010)+(111) =

101, pertanto:

d(000, u + v) = d(000, 101) = wt(101) = 2

d(111, u + v) = d(111, 101) = wt(010) = 1.

In entrambi i casi, se si effettuano le tecniche di codifica usate nella sessione 2.4 si vede

che C corregge u = 010 in modo “efficace” sia nell’ipotesi che sia inviata la parola 000 che

la parola 111 ed inoltre verifica la (2.11). Consideriamo adesso l’errore u = 110.

Per v = 000 si ha:

d(000, u + v) = d(000, 110) = wt(110) = 2

d(111, v + u) = d(111, 110) = wt(001) = 1.

43


In questo caso C non corregge l’errore u = 110 perche la parola che ha distanza minore

non e quella inviata.

Dato x ∈ R, indichiamo con bxc il massimo intero minore o uguale a x. Ad esempio:

⌊5

2

⌋= 2; b3c = 3;

⌊1

2

⌋= 0.

Anche per questo tipo di errori cerchiamo di individuare gli errori che sono corretti

da un codice C.

Teorema 11 Sia C un codice di lunghezza n e distanza d. Allora esso corregge tutti

gli errori di peso minore o uguale a

⌊d− 1

2

⌋. Esiste almeno un errore di peso pari

a 1 +

⌊d− 1

2

⌋che C non corregge.

Dim.

Sia u un errore con peso wt(u) ≤⌊

d− 1

2

⌋e due arbitrarie parole v e w in C con

v 6= w, supposto di trasmettere v. Si vuole dimostrare che:

d(v, v + u) < d(w, v + u). (2.12)

Per la disuguaglianza triangolare si ha che:

d(w, v + u) + d(v + u, v) ≥ d(w, v) ≥ d. (2.13)

Per le ipotesi si ha anche che:

d(v + u, v) = wt(v + u + v) = wt(u) ≤ d− 1

2, (2.14)

44


quindi,

d ≥ 2wt(u) + 1. (2.15)

Dalla (2.13) si ha:

d(w, v + u) + wt(v + u + v) ≥ d(w, v) ≥ d ≥ 2wt(u) + 1 (2.16)

d(w, v + u) + wt(u) ≥ 2wt(u) + 1 (2.17)

d(w, v + u) ≥ wt(u) + 1 = d(v + u, v) + 1 (2.18)

Dalla scelta arbitraria di v e w si ha che:

d(w, v + u) > d(v, v + u). (2.19)

La prima parte del teorema e provata.

Poiche la distanza di C e d allora esistono almeno due parole v e w appartenenti a

C tali che:

d(v, w) = d (2.20)

Consideriamo la parola v + w ed in essa cambiamo un numero d − 1 −⌊

(d− 1)

2

⌋

bits di valore “1” in “0”; chiamiamo u la parola che si ottiene dopo aver cambiato

tali bits. Il peso di tale parola sara:

d−{

d− 1−⌊

d− 1

2

⌋}=

⌊d− 1

2

⌋+ 1.

Consideriamo adesso d(v, v + u) e d(w, v + u):

d(v, v + u) = wt(u) =

⌊d− 1

2

⌋+ 1 (2.21)

d(w, v + u) = wt(w + v + u) = d(v + w, u) = d−{

1 +

⌊d− 1

2

⌋}(2.22)

45


Se la distanza d e dispari, allora si puo scrivere come d = 2t + 1 e si ha che:

d(v, v + u) = 1 +2t

2= 1 + t (2.23)

e

d(w, v + u) = 2t + 1− (1 + t) = t (2.24)

Pertanto:

d(v, v + u) > d(w, v + u) (2.25)

in contraddizione con la (2.19).

Se la distanza d e pari essa puo scriversi come d = 2t. In tal caso:

d(v, v + u) = 1 +

⌊2t− 1

2

⌋= 1 +

⌊t− 1

2

⌋= 1 + t− 1 = t (2.26)

e

d(w, v + u) = 2t− t = t (2.27)

Pertanto:

d(v, v + u) = d(w, v + u) (2.28)

anch’essa in contraddizione con la (2.19), quindi il codice C non corregge l’errore u

e il teorema e completamente provato. 2

Se d e la distanza di un codice C, allora C si dira

⌊d− 1

2

⌋-correttore, ad esempio

un codice di distanza sette e un codice 3-correttore.

46

Capitolo 3

Codici lineari

3.1 Introduzione

In questa sessione e presentato un tipo di codice che permette l’applicazione di molti

concetti incontrati nei corsi base di algebra lineare.

Un codice binario a blocchi C si definisce lineare se la somma di due parole v e w,

appartenenti a C e ancora una parola di C, cioe:

∀v, w ∈ C ⇒ v + w ∈ C.

Se Kn e un insieme di parole di lunghezza n che ha le proprieta di spazio vettoriale

sul campo K = {0, 1} mediante le operazioni di somma e prodotto definite nel

capitolo precedente, allora un codice lineare C puo intendersi come un sottospazio

di Kn, infatti la sua definizione implica la chiusura delle operazioni di somma e

prodotto esterno in C.

In un codice lineare molti parametri definiti nel capitolo precedente possono essere

calcolati mediante degli algoritmi piu semplici rispetto a quelli che si basano sulle

definizioni. Nel teorema seguente si vede come e possibile calcolare la distanza di un

47

3.1 Introduzione

codice senza effettuare il confronto diretto tra tutte le distinte coppie delle parole

del codice.

Teorema 12 La distanza di un codice lineare C e la piu piccola distanza tra tutte

le parole del codice, di peso maggiore di zero, e la parola nulla.

Dim.

Consideriamo la quantita t = min {d(0, c), c ∈ C}. Supponiamo per assurdo che la

distanza del codice d < t, allora esistono almeno due parole v′ e v′′ appartenenti a

C per cui si ha:

d(v′, v′′) = d.

Consideriamo la parola c = v′ + v′′, essa apparterra a C ed inoltre wt(c) = d > 0,

quindi:

wt(c) = d(0, c) = d.

Cio vuol dire che:

d ∈ {d(0, c), c ∈ C} ⇒ d ≥ t.

Si e determinato un assurdo in quanto t e il minimo di tale insieme e contempo-

raneamente si ha che d < t. 2

Esempio 1

C = {000, 111, 011, 100}, le distanze tra tutte le parole di C con peso maggiore di zero

dalla parola 000 sono d(111, 000) = 3, d(011, 000) = 2, d(100, 000) = 1 quindi la distanza

del codice e d = 1.

48

3.2 Prodotto scalare in Kn

3.2 Prodotto scalare in Kn

In Kn e possibile introdurre il prodotto scalare canonico definito nei corsi di algebra

lineare. Se v e w sono due parole di Kn, si intende come loro prodotto scalare la

somma dei prodotti delle componenti corrispondenti, ad esempio se v = (111) e

w = (010) si ha che v · w = (111) · (010) = 0 + 1 + 0 = 1. Se il prodotto scalare di

due parole e zero allora le due parole si dicono ortogonali, ad esempio se v = (111)

e w = (101) allora v · w = 1 + 0 + 1 = 0 e tali parole sono ortogonali.

Si definisce C⊥ (C ortogonale) l’insieme delle parole:

C⊥ = {v ∈ Kn : v · w = 0 ∀w ∈ C} ,

cioe l’insieme delle parole di Kn che sono ortogonali ad ogni parola di C. Tale

insieme e anch’esso un codice lineare, infatti se c′ e c′′ sono due arbitrarie parole

di C⊥ e v e una generica parola di C, allora si ha che essa e ortogonale alla parola

somma c′ + c′′, cioe:

(c′ + c′′) · v = c′ · v + c′′ · v = 0,

cio vuol dire che prese due parole arbitrarie di C⊥ allora la loro somma appartiene

a C⊥ e C-ortogonale e un codice lineare.

Un insieme di parole di C, B = {c1, c2, · · · , ck}, e un insieme di generatori di C se

per qualunque v ∈ C e possibile scrivere:

v = a1c1 + a2c2 + ... + akck.

E evidente che se l’equazione vettoriale

a1c1 + a2c2 + ... + akck = 0,

49

3.3 Matrice generatrice

e vera se e solo se ai = 0, per 1 ≤ i ≤ k, allora gli elementi di B sono detti

linearmente indipendenti ed essi formano una base di C. Il valore k, cioe il numero

di elementi in B e detto essere la dimensione di C. Essa insieme ai parametri n

(lunghezza), d (distanza) caratterizza un codice C.

In algebra lineare vale il seguente risultato, che in questi appunti e soltanto enun-

ciato.

Teorema 13 Sia C un codice lineare di lunghezza n e dimensione k, allora si ha:

dimC + dimC⊥ = n (3.1)

2

Maggiori approfondimenti degli argomenti trattati in questa sessione possono facil-

mente essere trovati in qualunque testo di algebra lineare.


Sia C un codice lineare e B = {c1, c2, ..., ck} un insieme di sue parole che costituiscono

una sua base. Costruiamo la matrice G, posizionando per riga tutti gli elementi di

B.

G =

c1

c2

.

.

ck

. (3.2)

50


La matrice (3.2) e detta matrice generatrice, essa si puo ottenere anche da una

matrice le cui righe sono costituite da parole del codice che formano un insieme di

generatori di C mediante operazioni elementari.

La riduzione di matrici mediante sequenza di operazioni elementari si rimanda ai cor-

si algebra lineare, qui invece sono presentate due particolari riduzioni che conducono

alla matrice generatrice di un codice lineare.

Sia A una matrice (k×n) su K, un elemento “1” di A si dice 1-leading se esso e un

elemento speciale (tutti gli elementi al di sotto sono “0”) e nella riga in cui si trova

tutti gli elementi alla sua sinistra assumono valore “0”. Una colonna della matrice

A si definisce colonna leading se essa contiene un 1-leading e tutti gli altri suoi

elementi sono “0”.

Esempio 2

Nella matrice A i caratteri “1” sottosegnati sono degli 1-leading, in particolare, nella se-

conda riga l’ 1-leading non ha nessun zero a sinistra in quanto primo elemento della riga,

ma rientra nella sua definizione perche appartiene all’ultima riga di A.

La matrice B contiene due colonne leading corrispondenti ai caratteri “1” sottosegnati.

A =

00011000

10011111

; B =

0 1 0

0 0 1

1 0 1

.

Una matrice A e ridotta parzialmente (REF) se tutte le sue righe nulle sono poste

al fondo di A e ogni riga non nulla ha un 1-leading che ha alla sua destra tutti gli

1-leadings delle righe sottostanti. Se una matrice non e ridotta parzialmente, allora

essa puo essere ridotta mediante le operazioni elementari:

1. Ri ⇒ Rj;

51


2. Ri ⇒ Ri + Rj.

Esempio 3

La matrice A e una matrice ridotta parzialmente.

A =

0 1 1 1 0

0 0 1 0 0

0 0 0 0 0

0 0 0 0 0

.

Esempio 4

La matrice B non e una matrice ridotta parzialmente, consideriamo le sue righe come

generatori di un codice lineare C di lunghezza n = 4.

B =

1 0 1 1

1 0 1 0

1 1 0 1

.

Riduciamo B mediante una sequenza di operazioni elementari.

{R2 ⇒ R2 + R1 R3 ⇒ R3 + R1}.

B′ =

1 0 1 1

0 0 0 1

0 1 1 0

.

52


{R2 ⇔ R3} ;

B′′ =

1 0 1 1

0 1 1 0

0 0 0 1

.

La matrice B′′ e ridotta parzialmente e le sue tre righe non nulle in cui compaiono gli

1- leading sono linearmente indipendenti quindi si e ottenuta una matrice generatrice del

codice C le cui righe formano una base di C.

Una matrice A si dice ridotta totalmente (RREF) se essa e ridotta parzialmente

e ogni suo 1-leading si trova in una leading colonna.

Esempio 5

La precedente matrice B′′ puo essere ridotta totalmente mediante la seguente operazione

elementare.

{R1 ⇒ R1 + R3} ;

B′′′ =

1 0 1 0

0 1 1 0

0 0 0 1

.

B′′′ e una matrice ridotta totalmente ed essa e anche una matrice generatrice.

53

3.4 Matrice di parita

Se un codice C ha dimensione k, allora si ha che la sua cardinalita e | C | = 2k. La

cardinalita di C e quindi pari al numero totale delle differenti parole di lunghezza k.

Cio e dovuto al fatto che se una base di C e B = {c1, c2, · · · , ck}, allora ogni parola

c di C si puo esprimere mediante un’unica combinazione lineare degli elementi di B,

cioe,

v = a1c1 + a2c2 + · · ·+ akck; (3.3)

ci sono al piu 2k distinte possibili combinazioni lineari del tipo (3.3).

Sia G una matrice generatrice di un codice C di lunghezza n e dimensione k, allora

essa sara una matrice k × n.

Una generica parola v di C si puo ottenere dal seguente prodotto riga per colonna:

v = u ·G = (a1, a2, · · · , ak) ·

c1

c2

.

ck

;

dove u = (a1, a2, · · · , ak) e una parola su K di lunghezza k (dimensione di C).

La parola v di C adesso puo essere individuata mediante la parola di lunghezza k

(a1, a2, · · · , ak)G rispetto alla matrice G.


Se C e un codice lineare, come precedentemente detto, anche il suo codice duale

C⊥ e un codice lineare. In questa sessione si determina la matrice generatrice del

54


codice duale di un codice lineare C, in particolare si chiama matrice di parita la

trasposta della matrice generatrice del codice duale.

3.4.1 Algoritmo di generazione di H

La matrice di parita e indicata con il simbolo H ed essa e individuata dal codice

lineare C, di parametri (n, k, d), mediante il seguente algoritmo.

Algoritmo

1. Sia S e un insieme di generatori del codice C e A la matrice ottenuta ponendo

per riga tutti gli elementi di S.

2. Si riduce totalmente la matrice A, si ottiene la matrice:

A′ =

G

0

,

dove G e una matrice generatrice di C, k × n e 0 le righe nulle ottenute dopo

la riduzione totale di A.

3. Sia X la matrice k × (n − k) ottenuta dalla matrice G eliminando tutte le

colonne in cui sono presenti dei 1-leading.

4. Si costruisce la matrice H (n× (n− k)) nel modo seguente:

• Nelle righe di H corrispondenti alle colonne 1-leading di G, si posizionano,

in sequenza, le righe di X. Le righe posizionate sono k.

• Nelle rimanenti n− k righe di H si posizionano in sequenza le righe della

matrice identita I(n−k).

5. Fine. 2

55


Teorema 14 La matrice di parita determinata dall’algoritmo precedente e la traspos-

ta della matrice generatrice del codice duale corrispondente al codice lineare C di

parametri (n, k, d).

Dim.

La matrice H e una matrice (n × (n − k)). Per provare il teorema basta mostrare

che il prodotto riga per colonna tra le matrici G e H e uguale ad una matrice nulla

del tipo (k × (n − k)). Senza ledere la generalita della dimostrazione a meno di

una permutazione delle colonne di G e delle righe di H si ha che e possibile scrivere

G′ = [Ik, X] e H ′ =

X

I(n−k)

. Il prodotto riga per colonna delle due matrici e:

G′ ·H ′ =[

Ik X] X

In−k

= X + X = 0; (3.4)

cio prova il teorema e la correttezza dell’algoritmo, inoltre si ha che:

HT = GC⊥ .

2

Esempio 6

Sia un codice C generato dalle parole S = {11101, 10110, 01011, 11010}, determiniamo per

C la matrice generatrice e la matrice di parita. Riduciamo totalmente la matrice:

56


AV I =

1 1 1 0 1

1 0 1 1 0

0 1 0 1 1

1 1 0 1 0

;

{R2 ⇒ R2 + R1 R4 ⇒ R4 + R1} ;

AV =

1 1 1 0 1

0 1 0 1 1

0 1 0 1 1

0 0 1 1 1

;

{R3 ⇒ R3 + R2} ;

AIV =

1 1 1 0 1

0 1 0 1 1

0 0 0 0 0

0 0 1 1 1

;

{R3 ⇔ R4} ;

57


AIII =

1 1 1 0 1

0 1 0 1 1

0 0 1 1 1

0 0 0 0 0

;

{R1 ⇒ R1 + R2} ;

AII =

1 0 1 1 0

0 1 0 1 1

0 0 1 1 1

0 0 0 0 0

;

{R1 ⇒ R1 + R3} ;

AI =

1 0 0 0 1

0 1 0 1 1

0 0 1 1 1

0 0 0 0 0

.

La matrice AI e totalmente ridotta e da essa si ricava la matrice G in cui sono presenti 3

colonne leading e quindi C ha dimensione k = 3.

58


G =

1 0 0 0 1

0 1 0 1 1

0 0 1 1 1

.

Da G eliminando le 3 leading colonne si ottiene la matrice X.

X =

0 1

1 1

1 1

.

Consideriamo adesso la matrice identita In−k = I2, posizioniamo le righe di X nelle righe

corrispondenti alle posizioni delle 1-leading colonne di G cioe nella 1a, 2a e 3a riga e nelle

rimanenti 4◦ e 5◦ riga poniamo le righe di I2. Si ottiene la matrice la matrice di parita H.

H =

0 1

1 1

1 1

1 0

0 1

.

Per ottenere la matrice generatrice del codice duale basta fare la trasposta di H, ovvero:

59


HT =

0 1 1 1 0

1 1 1 0 1

=

[XT In−k

].

Esempio 7

Consideriamo un codice di lunghezza 8 generato dall’insieme di parole S = {(11111111),

(11110000), (11001100), (10101010)} Determiniamo la matrice generatrice G e la matrice

di parita H.

Riduciamo totalmente la matrice:

AV I =

1 1 1 1 1 1 1 1

1 1 1 1 0 0 0 0

1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0

;

{R2 ⇒ R1 + R2 R3 ⇒ R3 + R1 R4 ⇒ R4 + R1} ;

AV =

1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

;

{R2 ⇔ R4} ;

60


AIV =

1 1 1 1 1 1 1 1

0 1 0 1 0 1 0 1

0 0 1 1 0 0 1 1

0 0 0 0 1 1 1 1

;

{R1 ⇒ R1 + R2} ;

AIII =

1 0 1 0 1 0 1 0

0 1 0 1 0 1 0 1

0 0 1 1 0 0 1 1

0 0 0 0 1 1 1 1

;

{R1 ⇒ R1 + R3} ;

AII =

1 0 0 1 1 0 0 1

0 1 0 1 0 1 0 1

0 0 1 1 0 0 1 1

0 0 0 0 1 1 1 1

;

{R1 ⇒ R1 + R4} ;

61


AI =

1 0 0 1 0 1 1 0

0 1 0 1 0 1 0 1

0 0 1 1 0 0 1 1

0 0 0 0 1 1 1 1

.

La matrice AI e totalmente ridotta. Da essa si determina la matrice G.

G =

1 0 0 1 0 1 1 0

0 1 0 1 0 1 0 1

0 0 1 1 0 0 1 1

0 0 0 0 1 1 1 1

.

Costruiamo la matrice X eliminando le 4 colonne leading. La dimensione di C e k = 4.

X =

1 1 1 0

1 1 0 1

1 0 1 1

0 1 1 1

.

Consideriamo la matrice identita In−k = I4 e aggiungiamo i suoi elementi nella righe

corrispondenti alle colonne di G non eliminate.

62


H =

1 1 1 0

1 1 0 1

1 0 1 1

1 0 0 0

0 1 1 1

0 1 0 0

0 0 1 0

0 0 0 1

.

La matrice generatrice del codice duale di C e HT le cui n−k = 4 righe formano una base

per C⊥.

Nella dimostrazione del teorema 14 tramite una permutazione delle colonne si trasfor-

ma la matrice generatrice ridotta totalmente in una matrice del tipo G′ = [I, X]. Ci

si pone la domanda se per un qualunque codice C, di parametri (n, k, d), e sempre

possibile determinare una matrice del tipo G′ senza effettuare permutazioni delle sue

colonne. Esistono codici che non possono avere matrici generatrici poste nella forma

assunta dalla matrice G′, tale affermazione e giustificata dall’esempio seguente.

Esempio 8

Sia il codice lineare C avente base B = {001, 100}. Tutte le sue possibili matrici generatrici

sono:

G =

1 0 0

0 0 1

; G′ =

1 0 1

0 0 1

; G′′ =

1 0 1

1 0 0

; G′′′ =

0 0 1

1 0 1

;

63


GIV =

1 0 0

1 0 1

.

Nessuna di tale matrice ha la forma G = [I,X].

Se un codice C, di dimensione k, possiede una matrice generatrice che assume la

forma G =[

Ik X]

allora esso si chamera sistematico e una sua qualunque

parola v si puo esprimere nel modo seguente:

v = u ·[

I X]

=[

u uX]. (3.5)

I primi k bits di v, (cioe u), sono chiamati bits di ricezione , gli ultimi n− k bits

(cioe (uX)) bits di parita o di controllo.

I codici che non sono sistematici possono essere riconducibili a codici sistematici

mediante una o piu permutazioni delle colonne di una delle matrici G. Ad esempio:

G =

1 0 0

0 0 1

⇒ G =

1 0 0

0 1 0

.

Il codice sistematico ottenuto e detto equivalente al codice che lo ha generato in

quanto esso mantiene la stessa dimensione, distanza e lunghezza.

64


La matrice di parita di un codice lineare C permette di “controllare” se una parola w

ricevuta e una parola del codice utilizzato, infatti se w ∈ C essa non puo appartenere

a C⊥.

Teorema 15 Condizione necessaria e sufficiente affinche w ∈ C e che w ·H = 0.

Dim.

Se c1, c2, · · · , cn−k sono parole che individuano una base di C⊥ e tci e la parola

trasposta di ci, per 1 ≤ i ≤ n − k, allora la matrice H si puo scrivere nel seguente

modo:

H =[

tc1,tc2, · · · , tcn−k

].

Se w ∈ C poiche w · ci = 0 per qualunque ci con 1 ≤ i ≤ n− k, allora si ha:

w ·H = 0,


Un’altro importante risultato che lega la distanza con le righe della matrice di parita

e dato dal seguente teorema.

Teorema 16 Sia C un codice lineare e H la sua matrice di parita. Allora C ha dis-

tanza d se e solo se, comunque si considerino d−1 righe di H, esse sono linearmente

indipendenti ed esistono almeno d righe di H linearmente dipendenti.

65

3.5 Coset

Dim.

Sia d la distanza del codice lineare C, cio vuol dire che esiste una parola v ∈ C tale

che wt(v) = d. Inoltre si ha v ·H = 0 si ha quindi che le d righe di H corrispondenti

alle posizioni delle componenti di v in cui sono presenti bits di valore “1” sono

linearmente dipendenti.

Consideriamo adesso un’arbitraria parola w con wt(w) ≤ d − 1 (con peso minore

di d) allora si ha che w · H 6= 0 perche w /∈ C, ne segue quindi che comunque si

scelgono d−1 righe di H esse saranno sempre linearmente indipendenti e il teorema

e provato. Il viceversa e banalmente dimostrabile. 2

3.5 Coset

In questa sessione e presentato un sottoinsieme di Kn che si lega al concetto pre-

sente in algebra di “laterale” o “coset” (termine inglese). Il laterale nella seguente

trattazione e presentato come strumento di teoria dei codici.

Se C ⊂ Kn e un codice lineare di lunghezza n e u una qualunque parola di Kn che

puo anche non appartenere a C, allora si definisce coset di C, determinato da u,

l’insieme:

C + u = {v + u ∈ Kn ∀v ∈ C} .

Tale insieme contiene lo stesso numero di parole del codice cioe 2k, in particolare

se u e una parola di C chiaramente si ha che C + u = C, in caso contrario esso

sara diverso da C, ma non sara un sottospazio di Kn in quanto e evidente che non

contiene la parola nulla.

66

3.5 Coset

Esempio 9

Sia il codice C = (000, 111) ⊂ K3 e u = 101, l’insieme coset sara C + u = {101, 010} Se

consideriamo u′ = 111: C + u′ = {111, 000}.Si nota che per u′ ∈ C si ha: C+u′ = C. Sia u′′ = 010 si ha che C+u′′ = {010, 101} = C+u,

da cio segue che ad ogni parola di K3 non sempre corrispondono cosets differenti.

Il seguente teorema mostrera le principali proprieta dei cosets legati ad un codice

lineare C.

Teorema 17 Sia C un codice lineare di parametri (n, k, d) e siano u e v due parole

di Kn, allora valgono le seguenti otto proprieta:

1. Se u e nel coset C + v, allora C + u = C + v.

2. La parola u ∈ C + u.

3. Se u + v ∈ C allora u e v appartengono allo stesso coset.

4. Se u + v /∈ C, allora u e v appartengono a coset differenti.

5. Ogni parola di Kn e contenuta in uno ed un solo coset.

6. Tutti i coset hanno la stessa cardinalita: |C + u| = |C|. Da cio la cardinalita

di un coset e 2k.

7. Se C ha dimensione k ci sono esattamente 2n−k coset diversi di C, e ogni coset

contiene esattamente 2k parole.

8. C e un coset.

Dim.

Dimostriamo in sequenza le proprieta del teorema.

67

3.5 Coset

1. Se u ∈ C + v deve esistere una w ∈ C tale che u = w + v. Sia t ∈ C + v, allora

esiste un t′ ∈ C tale che t = t′ + v ed inoltre t = t′ + w + u. Poiche il codice

e lineare si ha che t′ + w ∈ C, segue che t ∈ C + u. Data l’arbitrarieta di t si

ha che qualunque parola di C + v essa appartiene anche a C + u e si ha che

C + u ⊇ C + v.

Sia p una generica parola appartenente a C + u, allora esiste un p′ tale che

p = p′ + u, con p′ ∈ C, inoltre p = p′ + w + v, ma p′ + w ∈ C, essendo p′ e w

parole del codice, ne segue che p ∈ C + v e C + v ⊇ C + u, deve quindi essere

C + u = C + v.

2. La dimostrazione e immediata perche la parola nulla appartiene a C.

3. Se u+ v ∈ C allora esiste una w ∈ C tale che w = u+ v, ma poiche u = w + v,

allora si ha che u ∈ C + v e per la prima proprieta del teorema si ha che

C + u = C + v.

4. Supponiamo per assurdo che u e v appartengono allo stesso coset C + w, cio

comporta che esiste una parola t′ ∈ C tale che u = t′ + w e esiste una parola

t′′ ∈ C tale che v = t′′+w, sommando si ha u+v = t′+ t′′+w+w = t′+ t′′, ma

C e lineare, quindi t′ + t′′ ∈ C e conseguentemente u + v ∈ C il che e assurdo.

5. Supponiamo per assurdo che esiste una parola w che appartiene a due cosets

C + u e C + v con C + u 6= C + v. Cio comporta che w ∈ C + u e per la

prima proprieta w ∈ C + u = C + w, ma anche w ∈ C + v = C + w da cio

C + u = C + v il che e assurdo.

Tale proprieta mostra che cosets distinti sono disgiunti.

6. La dimostrazione e immediata.

68

3.5 Coset

7. Le parole totali di Kn sono 2n mentre le parole di C sono 2k. Da cio il numero

di coset sara2n

2k= 2n−k.

8. La dimostrazione e immediata. 2

Esempio 10

Sia dato un codice C = {0000, 1011, 0101, 1110}. Una sua matrice generatrice e

G =

1 0 1 1

0 1 0 1

.

Il codice C e individuato dai parametri (4, 2, 2), quindi il numero di coset e 2n−k = 4 e

sono:

C =

0 0 0 0

1 0 1 1

0 1 0 1

1 1 1 0

.

Per determinare il secondo coset consideriamo la parola u1 = 1000 in K4 non appartenente

a C e aggiungiamo tale parola ogni parola di C.

69

3.5 Coset

u1 + C = 1000 + C =

1 0 0 0

0 0 1 1

1 1 0 1

0 1 1 0

.

Consideriamo adesso un’altra parola, u2 = 0100, non appartenente a C o a C + u1. Il

terzo coset sara:

u2 + C = 0100 + C =

0 1 0 0

1 1 1 1

0 0 0 1

1 0 1 0

.

Ripetendo lo stesso procedimento con la parola u3 = 0010, il quarto coset sara:

u3 + C = 0010 + C =

0 0 1 0

1 0 0 1

0 1 1 1

1 1 0 0

.

Dei quattro coset, l’unico che rappresenta un codice lineare e chiaramente il primo, essendo

C stesso.

70

3.5 Coset

Adesso sfruttando le proprieta dei cosets cerchiamo di individuare una tecnica utile

alla correzione di errori.

Consideriamo un codice lineare C e assumiamo che v sia la parola inviata e w

la parola ricevuta, l’errore associato e u = v + w, tale equazione e equivalente a

u + w = v ∈ C. Per la proprieta 3 del teorema 17 si ha che l’errore u e la parola

ricevuta w appartengono a uno stesso coset di C.

Poiche gli errori di minor peso sono quelli che hanno maggiore probabilita di verifi-

carsi, vediamo adesso come la tecnica MLD puo essere utilizzata per un codice

lineare C di cui conosciamo i suoi coset.

Ricevuta la parola w, se w · H = 0 allora la parola ricevuta appartiene al codice.

Se w · H 6= 0 allora ad essa e legato un errore che appartiene allo stesso coset cui

appartiene w. Tra tutte le parole appartenente al coset C + w si sceglie la parola u

di peso minore, cioe la piu probabile, tale parola prende il nome di coset leader.

Sommando u a w si ottiene la parola v = w + u, essa e la parola che ha la maggiore

probabilita di essere stata inviata.

Esempio 11

I coset leaders corrispondenti ad ogni singolo coset dell’esempio 10 sono:

1. il coset leader di C e 0000;

2. il coset leader di C + u1 e 1000;

3. il coset leader di C + u2 e 0100;

4. il coset leader di C + u3 e 0010.

Se w = 1101 e la parola ricevuta si verifica facilmente che w ∈ C + u1 = C + 1000 e

71

3.6 Sindrome

tale coset ha coset leader la parola (1000). La correzione della parola w e v = w + u =

1101 + 1000 = 0101.

Puo accadere che in un coset vi sono piu parole con uguale peso minimo, in tal caso

si puo adoperare la tecnica CMLD in cui si effettua una scelta tra le parole di peso

minore e si definisce un coset leader o la tecnica IMLD dove se w appartiene a un

coset dove vi sono piu di una parola di minore peso allora si richiede la ritrasmissione.

E importante sottolineare che per la prima volta si e riusciti a determinare l’errore

u soltanto tramite la conoscenza della parola trasmessa w e tramite esso si puo

effettuare la correzione.

Il procedimento di correzione appena descritto, nel caso in cui il numero degli ele-

menti di un codice C e elevato, puo comportare notevoli problemi di immagaz-

zinamento dati.

3.6 Sindrome

Proprio per ovviare ai problemi di immagazzinamento dati legati alla tecnica di

correzione di errore precedentemente illustrata in questa sessione viene introdotto il

concetto di sindrome di una parola di Kn.

Sia w ∈ Kn, si definisce sindrome di w la parola s = w ·H di Kn−k.

Esempio 12

Consideriamo il codice presentato nell’esempio 10 e sia la parola w = 1101. La matrice H

di C e:

72

3.6 Sindrome

H =

1 1

0 1

1 0

0 1

.

La sindrome di w e:

s = w ·H = 1101

1 1

0 1

1 0

0 1

= 11.

Quindi essendo s = w ·H 6= 0 per il teorema 15 si ha che w /∈ C e w ∈ C + 1000.

Consideriamo una qualunque parola w′ del coset C + 1000 e facile notare che la sua

sindrome sara sempre la stessa cioe:

s = w′ ·H = w′

1 1

0 1

1 0

0 1

= 11.

Il teorema seguente spiega i risultati ottenuti nell’ultima parte dell’esempio 12.

73

3.6 Sindrome

Teorema 18 Sia C un codice lineare di parametri (n, k, d). Siano u e w due parole

di Kn e H la sua matrice di parita, allora valgono le seguenti proprieta:

1. w ·H = 0 se e solo se w ∈ C.

2. u ·H = w ·H se e solo se w e u appartengono allo stesso coset.

3. Se u e l’errore di una parola ricevuta w allora u ·H e la somma delle righe di

H che corrispondono alla posizione dei bits alterati in trasmissione.

Dim.

1. La proprieta e vera per il teorema 15.

2. Dalla relazione:

w ·H = u ·H,

si ha:

w ·H + u ·H = 0,

e quindi:

(w + u) ·H = 0 ⇔ w + u ∈ C,

quindi w e u appartengono allo stesso coset.

3. Se u = w + v e l’errore legato a w allora e evidente che u ·H individua le righe

di H in cui e avvenuto un cambiamento di carattere nei bits corrispondenti

della parola inviata. 2

74

3.6 Sindrome

Dato che parole dello stesso coset hanno la stessa sindrome, mentre parole di coset

differenti hanno sindromi differenti, allora e possibile identificare un coset con la sua

sindrome corrispondente e a tale sindrome si puo associare il coset leader corrispon-

dente. Tale corrispondenza tra sindrome e coset leader permette di individuare una

tabella, detta SDA ( Standard Decoding Array).

Se C e un codice lineare di lunghezza n e dimensione k, allora 2n−k parole di

lunghezza n− k saranno ognuna la sindrome di ogni singolo coset.

Nell’esempio seguente vedremo una tabella SDA in cui il coset leader di ogni singolo

coset viene posto come prima componente di ogni singola riga, mentre la sindrome

corrispondente e posta come seconda componente della riga. Nel caso in cui piu

parole hanno stesso minor peso all’interno di un coset, allora, in tale esempio, e

utilizzata la tecnica CMLD.

Esempio 13

Coset leaders Sindrome u·H0000 00

1000 11

0100 01

0010 10

Riferendoci all’esempio 10 in cui abbiamo calcolato i coset del codice: C = {0000, 1011,

0101, 1110} si e costruita la tabella SDA.

Se w = 0101 allora w ·H = 00 che e la sindrome di 0000. Da cio v = w+u = 0101+0000 =

0101. Se w = 1100 allora w · H = 10 che e la sindrome di 0010. Da cio v = w + u =

1100 + 0010 = 1110.

75

Capitolo 4

Codici perfetti

4.1 Cardinalita di un codice C

In questa sessione sono presentate le relazioni esistenti tra i parametri che caratter-

izzano un codice C, cioe lunghezza, distanza e dimensione, e il numero di parole pre-

senti nel codice. Inoltre sono presentati particolari codici che in seguito assumeranno

notevole importanza.

Facciamo prima alcune considerazioni legate alla distanza tra parole differenti di Kn

e la distanza d di un codice C.

Sia v una parola di Kn, consideriamo il numero di differenti t-uple (t < n) di bits

distinte prese all’interno di v. Tramite il calcolo combinatorio si ha che tale numero

di t-uple e uguale a:

n

t

=

n!

t!(n− t)!=

n(n− 1) · · · (n− t + 1)

t!. (4.1)

76


Ci si pone la seguente domanda: qual’e il numero di parole di Kn che hanno distanza

1 da v?

Il problema si puo anche porre nel seguente modo: determinare il numero di parole

di Kn che differiscono da v soltanto per un bit. Chiaramente il numero di tali parole

e n =

n

1

. In generale determinare il numero di parole di Kn che hanno distanza

t, con t < n, da v e equivalente a determinare il numero di tutte le possibili t-uple

distinte di bits presenti in v, infatti se si individuano arbitrariamente in v t bits e si

cambiano i valori di tali bits da “0” a “1” o da “1” a “0”, si ottiene una nuova parola

che ha distanza t da v. Il numero di parole che hanno distanza t da v e esattamente n

t

.

Esempio 1

Sia v = 101110101 una parola di K9. Il numero di parole che hanno distanza 1 in K9 da v

e

9

1

= 9; Il numero di parole che hanno distanza 2 in K9 da v e

9

2

=

9 · 82

= 36;

Il numero di parole che hanno distanza 3 in K9 da v e

9

3

=

9 · 8 · 73 · 2 = 84.

Da quanto detto precedentemente e ricordando che

n

0

= 1 si ha il seguente

teorema.

77


Teorema 19 Se 0 ≤ t ≤ n e v e una parola di lunghezza n, appartenente ad un

codice C, allora il numero di parole di lunghezza n e distanza al piu t da v e:

N =

n

0

+

n

1

+

n

2

+ · · ·+

n

t

. (4.2)

2

Il precedente teorema permette di determinare per ogni parola v di un codice C,

avente distanza d e lunghezza n, una “sfera” in Kn di centro v e “raggio” t tale

che al suo interno si trovano esattamente N parole. Qui e usato il termine “sfera”

per facilitare la comprensione del lettore, ma se consideriamo le parole di Kn come

punti di uno spazio a n dimensioni il concetto di “sfera” e molto piu complesso e

rientra nel campo della geometria finita che esula da un corso di teoria dei codici.

Nel seguente teorema e mostrato che se la distanza di C e d = 2t+1, allora le “sfere”

che hanno come centro le parole del codice e raggio t sono tutte disgiunte.

Teorema 20 Sia C un codice avente distanza d = 2t+1 e lunghezza n, siano v e w

due distinte parole di C, allora non esiste alcuna parola c ∈ Kn tale che d(v, c) ≤ t

e d(w, c) ≤ t.

Dim.

Supponiamo per assurdo che esista una c ∈ Kn e due parole v, w ∈ C tali che

d(v, c) ≤ t e d(w, c) ≤ t, per la disuguaglianza triangolare si ha:

d(v, w) ≤ d(v, c) + d(c, w) ≤ t + t = 2t < 2t + 1 = d.

78


Si sono determinate due parole di C, v e w che hanno distanza minore della distanza

di C cioe d(v, w) < d, questo e assurdo. 2

Il risultato precedente permette di ottenere un limite superiore alla cardinalita | C |di un codice, tale limite e legato ai parametri n e d.

Teorema 21 (Limite di Hamming) Se C e un codice di lunghezza n e distanza

d = 2t + 1 allora si ha che:

| C | ·

n

0

+

n

1

+

n

2

+ · · ·+

n

t

≤ 2n, (4.3)

ovvero:

| C | ≤ 2n

n

0

+

n

1

+

n

2

+ · · ·+

n

t

. (4.4)

Dim.

Se si considera un’arbitraria parola v ∈ C, per il teorema (19), le parole che distano

al piu t da v sono:

N =

n

0

+

n

1

+

n

2

+ · · ·+

n

t

.

79


Inoltre, per il teorema 20, nessuna di tali parole ha distanza minore o uguale a t

da una qualsiasi altra parola presente in C. Il numero di parole distinte che hanno

distanza minore o uguale a t da ogni singola parola di C e:

| C | ·

n

0

+

n

1

+

n

2

+ · · ·+

n

t

.

Il numero di parole distinte in Kn e 2n, si ha allora che:

| C | ·

n

0

+

n

1

+

n

2

+ · · ·+

n

t

≤ 2n. (4.5)


Esempio 2

Sia un codice C con n = 6 e d = 3, quindi essendo d = 2t + 1 si ha che t = 1. Per il

teorema di Hamming si ha:

|C| ≤ 2n

n

0

+

n

1

=26

1 + 6< 10. (4.6)

80


Poiche un codice binario deve contenere un numero di parole che e una potenza di due,

allora | C | ≤ 8. Questo significa che in un codice C avente distanza d = 3 e lunghezza

n = 6 al massimo vi sono otto parole.

Il teorema seguente mette in relazione le grandezze (n, k, d) che caratterizzano un

codice lineare.

Teorema 22 (Limite di Singleton) Per un codice lineare (n,k,d) si ha che d −1 ≤ n− k.

Dim.

La matrice di parita H di un codice lineare C e definita come:

H =

X

In−k

.

In essa non vi possono essere piu di n − k righe linearmente indipendenti, data la

presenza di In−k, le cui righe costituiscono una base per Kn−k. Per il teorema 16

del capitolo 3, si ha che in H comunque si scelgono arbitrariamente d− 1 righe esse

sono linearmente indipendenti, quindi segue che:

d− 1 ≤ n− k, (4.7)

81



Poniamoci adesso il seguente problema, dati i parametri (n, k, d) vediamo se e pos-

sibile determinare un codice lineare C le cui parole hanno lunghezza n, la sua

dimensione e k e la sua distanza e d.

Un codice lineare puo essere individuato mediante la sua matrice di parita, cioe

mediante una matrice H (n × (n − k)), essa ha la caratteristica di avere almeno

d righe linearmente dipendenti e comunque si scelgono d − 1 sue righe esse sono

linearmente indipendenti. Se si riesce a determinare una tale matrice H, dato che

essa e la matrice trasposta della matrice generatrice del codice duale GC⊥ =t H, da

essa, mediante l’algoritmo presentato nel capitolo 3, si puo determinare la matrice

di parita HC⊥ del codice duale che individua una matrice generatrice G =t HC⊥

(n× (n− k)) del codice C avente parametri (n, k, d).

Figura 4.1:

Nel seguente esempio e mostrato un metodo utile a determinare la matrice di parita

di un codice lineare avente parametri (n, k, d), tale tecnica in seguito permettera di

formulare il teorema di Gilbert - Varshamov.

82


Esempio 3

Vediamo se e possibile determinare un codice lineare C di parametri (15, 6, 5). Indi-

viduiamo la sua matrice di parita H (15× 9). Essa puo contenere la matrice I9, costituita

da righe linearmente indipendenti. Bisogna determinare altre sei righe di K9 in modo tale

che vi siano almeno 5 righe linearmente dipendenti e comunque si scelgono in essa 4 righe

esse devono essere linearmente indipendenti.

Cerchiamo di individuare la decima riga da aggiungere alle righe di I9, iniziamo con es-

cludere la parola nulla di K9, in quanto essa stessa e linearmente dipendente, inoltre e

necessario escludere qualsiasi parola contenuta in I9 e tutte le parole di K9 ottenute da

combinazioni lineari di due o tre righe di I9, quindi e possibile aggiungere una decima riga

se il numero totale delle parole in K9, cioe 29, e strettamente maggiore del numero di parole

che necessariamente devono essere escluse. Quindi deve valere la seguente disuguaglianza.

9

0

+

9

1

+

9

2

+

9

3

< 29.

La disuguaglianza e valida in quanto 1 + 9 + 36 + 84 < 29, quindi e possibile aggiungere

una decima riga. Sia essa la riga 111100000 che formera la matrice,

H10 =

I9

111100000

.

E importante notare come la matrice H10 ha gia d = 5 righe linearmente dipendenti, cioe la

prima, la seconda, la terza, la quarta e la decima. Determiniamo adesso H11 aggiungendo

a H10 un’undicesima riga mantenendo le proprieta richieste precedentemente, cioe in H11

non possono esistere 4 righe linearmente dipendenti. La seguente disuguaglianza, ottenuta

dalle precedenti considerazioni,

83


10

0

+

10

1

+

10

2

+

10

3

< 29,

e ancora valida e quindi aggiungiamo la riga 100011100, otteniamo la matrice H11. Iteran-

do questa procedura otteniamo la matrice di parita di C di parametri (15, 6, 5).

H10 =

I9

111100000

101000011

100011100

101000011

010101110

011000101

.

Teorema 23 (Limite di Gilbert-Varshamov) Un codice lineare C con parametri

(n, k, d) esiste se:

n− 1

0

+

n− 1

1

+ · · ·+

n− 1

d− 2

< 2n−k.

Dim.

Il codice C si puo determinare mediante la sua matrice di parita H, cioe una matrice

(n× (n−k)). Supponiamo di aver determinato una matrice Hi, dove il primo valore

che i puo assumere e n − k cioe Hn−k = In−k. In generale consideriamo un i, con

n − k ≤ i ≤ n − 1, Hi deve avere la proprieta che comunque si prendono in essa

d− 1 righe esse devono essere linearmente indipendenti. Cerchiamo di determinare

84


una matrice del tipo Hi+1 aggiungendo una riga a Hi. Tale riga deve essere scelta in

Kn−k e deve essere differente dalla parola nulla, e necessario poi escludere in Kn−k

tutte le parole che sono righe in Hi e tutte le parole che risultano combinazione

lineare di j righe di Hi con 2 ≤ j ≤ d − 2. Il numero delle righe che non possono

essere aggiunte in Hi e che appartengono a Kn−k e dato da:

Ni =

i

0

+

i

1

+

i

2

+ · · ·+

i

d− 2

.

Se Ni < 2n−k allora sara possibile determinare una matrice Hi+1. Se i + 1 < n,

allora ripetiamo quanto fatto precedentemente per Hi in modo da poter aggiungere

una nuova riga a Hi+1 e formare una matrice Hi+2. Si ha che Ni+1 e uguale a:

Ni+1 =

i + 1

0

+

i + 1

1

+

i + 1

2

+ · · ·+

i + 1

d− 2

.

Ancora una volta se Ni+1 < 2n−k allora sara possibile determinare la matrice Hi+2.

E importante notare che la disuguaglianza Ni < Ni+1 e valida. Il procedimento

descritto, se possibile, si puo iterare fino a che i = n−1, in tal caso se e anche valida

la diseguaglianza seguente,

85

4.2 Codici MDS

Nn =

n− 1

0

+

n− 1

1

+

n− 1

2

+ · · ·+

n− 1

d− 2

< 2n−k, (4.8)

allora sara possibile determinare la matrice H di C. Inoltre poiche in generale vale

sempre la disuguaglianza Ni < Ni+1 per n− k ≤ i ≤ n− 1, e possibile determinare

la matrice di parita H di C solo se e verificata la disuguaglianza (4.8) e il teorema

e provato. 2

4.2 Codici MDS

La diseguaglianza (4.7) mette in relazione tutti i parametri che caratterizzano un

codice C. Se tale diseguaglianza, per un codice lineare C, vale come eguaglianza,

allora essa caratterizza un insieme di codici in cui, fissati n e k, si ha che la loro

distanza puo assumere il suo valore massimo cioe d = n−k+1. Tali codici prendono

il nome di codici MDS dall’inglese “Maximum Distance Separable”.

I codici MDS assumono una notevole importanza in quanto a tutt’oggi sono ampia-

mente utilizzati nella lettura dati (lettori CD o DVD), tra i piu importanti si ricor-

dano i codici Reed-Solomon che si rimandano ad un corso di teoria dei codici piu

avanzato.

Il teorema seguente identifica una serie di proprieta che caratterizzano i codici MDS

e che sono tra esse equivalenti.

86

4.2 Codici MDS

Teorema 24 Per ogni codice lineare C (n, k, d) le seguenti proposizioni sono equiva-

lenti:

1. d = n− k + 1

2. Comunque si scelgano n− k righe di H esse sono linearmente indipendenti.

3. Comunque si scelgano k colonne della matrice generatrice G, esse sono linear-

mente indipendenti.

4. C e un MDS

Dim.

1. Se d = n − k + 1, dalla definizione, si ha che C e un codice MDS e vale il

viceversa.

2. Supponiamo di avere una matrice di parita H avente la proprieta che co-

munque si individuano in essa n− k righe esse sono linearmente indipendenti.

Per il teorema 16 del capitolo 3, la matrice H ha la proprieta che comunque si

scelgono d− 1 righe esse sono linearmente indipendenti e ve ne sono d linear-

mente dipendenti, allora si ha che n− k ≤ d− 1, ma per il teorema 22 anche

la disuguaglianza d− 1 ≤ n− k e valida, quindi deve essere d− 1 = n− k. E

evidente che vale anche il viceversa.

3. Sia C un codice lineare MDS, allora si ha che n−d = k−1. Se tale eguaglianza

e valida allora si ha che in ogni parola di C non possono esistere piu di k−1 zeri.

Infatti una parola di minimo peso del codice ha esattamente n− k + 1 bits di

valore “1” ed esattamente k−1 bits di valore “0”. Sia G la matrice generatrice

di C, supponiamo per assurdo che esistano k colonne linearmente dipendenti.

Se si estraggono tali colonne, esse individuano una matrice quadrata A (k ×

87

4.3 Codici estesi

k) le cui k colonne sono linearmente dipendenti, per un teorema di algebra

lineare, si ha che anche le k righe di A sono linearmente dipendenti (dimensione

dello spazio delle righe e uguale a quello delle colonne). E possibile quindi

determinare una parola u ∈ Kk, diversa dalla parola nulla, tale che u · A =

0 ∈ Kk e segue anche che la parola del codice u · G possiede k zeri, questo e

un assurdo.

4. Se C e MDS allora banalmente valgono tutte le tre condizioni precedenti. 2

4.3 Codici estesi

Consideriamo un codice lineare C di parametri (n, k, d) e ad ogni parola di C si

aggiunge il bit di parita, cioe si aggiunge un bit in modo tale che ogni sua singola

parola abbia peso pari. Il codice cosı ottenuto si denota con C∗, esso ha lunghezza

n + 1 ed e detto codice esteso di C.

La matrice generatrice di un codice esteso si puo rappresentare nel seguente modo

G∗ = [G, b], dove la sottomatrice G e la matrice generatrice di C e b e un vettore

colonna, con k componenti ciascuno dei quali assume valore “1” se il numero di bits

di valore “1” della parola corrispondente in G e dispari e valore “0” in caso contrario.

La matrice di parita H∗ del codice esteso C∗ puo essere costruita tramite la matrice

G∗ mediante il noto algoritmo oppure in modo piu semplice dalla matrice di parita

H del codice originario C. La matrice di parita di C∗ sara:

H∗ =

H J

0 1

, (4.9)

88

4.3 Codici estesi

dove J e un vettore colonna formato da bits che assumono tutti valore “1”. Per

provare che tale matrice e effettivamente la matrice di parita di C∗ basta provare

che il prodotto riga per colonna e G∗ ·H∗ = 0.

G∗ ·H∗ =[

G, b]· H J

0 1

=

[GH,GJ + b

],

il prodotto G ·H = 0, essendo G e H le matrici generatrice e di parita del codice C.

Consideriamo adesso il temine GJ + b, osserviamo che se ri e la riga i-esima della

matrice G allora si ha che:

ri · J =

1 se ri contiene un numero dispari di bits di valore “1”;

0 se ri contiene un numero pari di bits di valore “1”.

Se indichiamo con bi la componente i-esima del vettore b, essa assumera il valore:

bi =

1 se ri · J = 1;

0 se ri · J = 0.

Si ha dunque che GJ + b = 0 e quindi H∗ e la matrice di parita di C∗.

89

4.3 Codici estesi

Esempio 4

Consideriamo un codice lineare C avente matrici generatrice e di parita:

G =

1 0 0 1 0

0 1 0 0 1

0 0 1 1 1

, H =

1 0

0 1

1 1

1 0

0 1

.

Definiamo le matrici G∗ e H∗ del codice esteso di C aggiungendo il bit di parita ad ogni

riga di G e utilizzando la (4.9).

G∗ =

1 0 0 1 0 0

0 1 0 0 1 0

0 0 1 1 1 1

, H∗ =

1 0 1

0 1 1

1 1 1

1 0 1

0 1 1

0 0 1

.

90

4.4 Codici perfetti

4.4 Codici perfetti

Un codice C di lunghezza n e distanza d = 2t + 1 si dice perfetto se si ha che:

| C | = 2n

n

0

+

n

1

+

n

2

+ · · ·+

n

t

. (4.10)

Poiche la cardinalita di un codice binario deve essere uguale ad una potenza di 2

allora e immediata la seguente condizione necessaria.

Teorema 25 Condizione necessaria per l’esistenza di un codice perfetto e che:

n

0

+

n

1

+

n

2

+ .... +

n

t

,

sia potenza di 2.

Due codici perfetti che sono detti banali sono il codice C = {(000...000), (111...111)},le cui parole appartengono a Kn e il codice C = Kn.

91

4.4 Codici perfetti

Esempio 5

• Verifichiamo che il codice con n = 7 e d = 3 e perfetto.

d = 2t + 1 = 3 ⇒ t = 1 e quindi si ha che:

|C| = 27

7

0

+

7

1

=27

23= 24 = 16.

Il codice C e perfetto.

• Verifichiamo che il codice con n = 23 e d = 7 sia un codice perfetto. Se d = 2t+1 = 7,

allora segue che t = 3 e si ha:

|C| = 223

23

0

+

23

1

+

23

2

+

23

3

=223

211= 212 = 4096.

Il secondo codice dell’esempio individua un codice che in seguito sara trattato in dettaglio,

ma come codice esteso.

Il seguente teorema fu provato da Van Lint nel 1963 e da’ precise indicazioni sullo

spettro di esistenza, legato al parametro n, dei codici perfetti. In questi appunti e

omessa la dimostrazione.

92

4.4 Codici perfetti

Teorema 26 (Van Lint) Se C e un codice perfetto non banale di lunghezza n e

distanza d = 2t + 1, allora o n = 23 e d = 7, oppure n = 2r − 1 (per r ≥ 2) e d = 3.

2

Teorema 27 Se C e un codice perfetto di lunghezza n e distanza d = 2t + 1, allora

C corregge tutti gli errori di peso minore o uguale a t. 2

4.4.1 Codice di Hamming

Un codice lineare di lunghezza n = 2r − 1, con r ≥ 2, avente una matrice di parita

H le cui righe hanno lunghezza r e detto codice di Hamming.

In un codice di Hamming la matrice H e del tipo ((2r−1)× r). Se consideriamo che

le parole distinte di lunghezza r sono 2r, allora, se si esclude la parola nulla, si ha

che tutte le altre parole di lunghezza r sono tutte presenti nelle righe di H, quindi

comunque si considerano due distinte righe di H esse sono linearmente indipendenti,

inoltre in H sono presenti le righe 10000 · · · 000, 01000 · · · 000 e 11000 · · · 000, di

lunghezza r, e chiaro che esse sono linearmente dipendenti, segue che i codici di

Hamming hanno distanza d = 3 e per il teorema 26 essi sono dei codici perfetti.

Esempio 6

La matrice di parita di un codice di Hamming con r = 3 (n = 2r − 1 = 7) e:

93

4.4 Codici perfetti

1 1 1

1 1 0

1 0 1

0 1 1

1 0 0

0 1 0

0 0 1

.

La sua matrice generatrice e:

G =

1 0 0 0 1 1 1

0 1 0 0 1 1 0

0 0 1 0 1 0 1

0 0 0 1 0 1 1

.

Dato l’intero positivo r e il suo codice di Hamming corrispondente C sappiamo che

la relazione tra le dimensioni di C e il suo codice duale C⊥ e:

dimC + dimC⊥ = n,

Poiche dimC⊥ = r ed inoltre n = 2r − 1, allora si ha che:

k = dimC = 2r − 1− r.

La cardinalita del codice di Hamming C e:

94

4.4 Codici perfetti

| C | = 2k = 22r−1−r

Gli stessi risultati precedentemente ottenuti si possono ricavare considerando che C

e un codice perfetto con d = 2t + 1 = 3 e t = 1 allora si ha che:

| C | = 2n

n

0

+

n

1

=22r−1

1 + 2r − 1= 22r−1−r.

Sia un codice di Hamming C di lunghezza n = 2r − 1, se si considera una parola v

di Kn di peso uno, essa certamente non appartiene a C, poiche d = 3, e la si somma

ad un’altra parola w distinta di peso uno, allora si ottiene una parola di peso due

che non appartiene a C, quindi v e w sono due parole che appartengono a coset

differenti. Il numero di coset di C e pari a 2r, quindi le 2r − 1 parole di lunghezza

n = 2r − 1 e peso uno piu la parola nulla formano i coset leaders di un codice di

Hamming C.

In generale un codice di Hamming ha la seguente tabella SDA:

COSET LEADER u SINDROME u ·H0000 · · · 0000 00 · · · 00

I2r−1 H

95

4.4 Codici perfetti

Esempio 7

La tabella SDA del codice di Hamming dell’esempio 6 e qui sotto rappresentata.

COSET LEADER u SINDROME u ·H0000000 000

1000000 111

0100000 110

0010000 101

0001000 011

0000100 100

0000010 010

0000001 001

4.4.2 Codice di Golay esteso

In questa sessione e presentato un codice avente come parametri (24, 12, 8), esso e

generato dal codice perfetto di parametri (23, 11, 7) e si chiama codice di Golay

esteso .

Il codice di Golay esteso ha una notevole importanza perche e stato ampiamente

utilizzato dall’ente spaziale NASA negli anni ’80 soprattutto nelle trasmissioni delle

sonde Voyager.

Per definire tale codice e necessario costruire la matrice B1 di tipo (11× 11) ottenu-

96

4.4 Codici perfetti

ta dalla riga di 11 caratteri 11011100010, le successive righe di B1 sono ottenute

mediante lo spostamento (“shift”) del primo bit nell’ultima posizione.

B1 =

1 1 0 1 1 1 0 0 0 1 0

1 0 1 1 1 0 0 0 1 0 1

0 1 1 1 0 0 0 1 0 1 1

1 1 1 0 0 0 1 0 1 1 0

1 1 0 0 0 1 0 1 1 0 1

1 0 0 0 1 0 1 1 0 1 1

0 0 0 1 0 1 1 0 1 1 1

0 0 1 0 1 1 0 1 1 1 0

0 1 0 1 1 0 1 1 1 0 0

1 0 1 1 0 1 1 1 0 0 0

0 1 1 0 1 1 1 0 0 0 1

(4.11)

Consideriamo adesso un’estensione B (12× 12) della matrice B1 nel seguente modo:

97

4.4 Codici perfetti

B =

B1 J

JT 0

=

1 1 0 1 1 1 0 0 0 1 0 1

1 0 1 1 1 0 0 0 1 0 1 1

0 1 1 1 0 0 0 1 0 1 1 1

1 1 1 0 0 0 1 0 1 1 0 1

1 1 0 0 0 1 0 1 1 0 1 1

1 0 0 0 1 0 1 1 0 1 1 1

0 0 0 1 0 1 1 0 1 1 1 1

0 0 1 0 1 1 0 1 1 1 0 1

0 1 0 1 1 0 1 1 1 0 0 1

1 0 1 1 0 1 1 1 0 0 0 1

0 1 1 0 1 1 1 0 0 0 1 1

1 1 1 1 1 1 1 1 1 1 1 0

. (4.12)

Definiamo inoltre la matrice generatrice del codice di Golay esteso:

G =[

I12, B],

Il codice di Golay esteso gode delle proprieta che sono enunciate nel seguente teore-

ma.

Teorema 28 Un codice di Golay esteso C ha le seguenti proprieta:

1. Il codice C ha una lunghezza n = 24, dimensione k = 12 e | C | = 212 = 4096

parole.

98

4.4 Codici perfetti

2. La matrice B e una matrice simmetrica, cioe BT = B.

3. Due qualunque righe ri e rj di B sono tra loro ortogonali, cioe ri · rj = 0.

4. La matrice di parita di C e H =

B

I

.

5. Esiste un’altra matrice di parita per C cioe H ′ =

I

B

.

6. C e autoduale cioe C = C⊥.

7. La distanza di C e d = 8

8. Il codice C e un codice 3-correttore, cioe corregge tutti gli errori u tali che

wt(u) ≤ 3.

Dim.

Dimostriamo le proprieta del teorema in sequenza.

1. La dimostrazione e evidente osservando le caratteristiche della matrice gene-

ratrice.

2. La matrice B e evidentemente simmetrica, cio e dovuto al metodo della sua

costruzione.

3. Per provare tale proprieta basta eseguire i prodotti ri · rj, con i 6= j e 1 ≤i, j ≤ 12, e constatare la loro ortogonalita.

4. Per dimostrare che H e una matrice di parita si procede nel modo seguente:

G ·H =[

I, B] B

I

= B + B = 0.

99

4.4 Codici perfetti

5. Per dimostrare che H ′ e una matrice di parita si procede nel modo seguente:

G ·H ′ =[

I, B] I

B

= I + BBT = I + I = 0.

6. Poiche H ′ = GT , allora il codice di Golay e un codice autoduale, cioe il suo

duale e esso stesso.

7. Consideriamo una parola v di C ottenuta dalla somma di due righe distinte

di G v = ri + rj con i 6= j. Poiche le due righe sono ortogonali, allora ri e rj

hanno un numero pari di bits “1” posti nelle stesse componenti, pertanto:

wt(v) = wt(ri) + wt(rj)− 2(2x) = wt(ri) + wt(rj)− 4x,

dove 2x e il numero pari di bits di valore “1” posti nelle stesse componenti di

ri e rj, inoltre tali righe hanno un peso uguale a 8 o 12, quindi il peso di v e

un multiplo di 4.

Consideriamo adesso la parola v′ = v + rk, dove rk e un’altra qualunque riga

di G e v = ri + rj. Osserviamo che:

rk · v = (ri + rj) · rk = rk · ri + rk · rj = 0 + 0 = 0,

quindi rk e v sono ortogonali, con analoghe considerazioni fatte in precedenza

si ha che:

wt(v′) = wt(ri + rj) + wt(rk)− 4y,

dove 2y e il numero pari di bits di valore “1” presenti nelle stesse componenti

in v e rk. Una generica combinazione di righe di G permette di ottenere

100

4.4 Codici perfetti

una generica parola w di C e anch’essa, con analoghi ragionamenti fatti in

precedenza, ha un peso che e un multiplo di 4. Nella matrice G sono presenti

righe di peso 8 e 12, e necessario provare che non esistono parole di C di peso

4.

Supponiamo per assurdo che la parola w di C ha peso 4. Il codice C e

autoduale, allora ogni sua parola si puo ottenere dalle due diverse matrici

generatrici di G =[

I, B]

e G′ =[

B, I]

cioe si ha:

w = u1

[I, B

]=

[u1, u1B

],

e

w = u2

[B, I

]=

[u2B, u2

].

Dato che wt(w) = 4, supponendo che wt(u1) ≥ 2 (cioe che i primi dodici bit

di w contengano due o piu bit di valore 1), allora deve essere necessariamente

wt(u1B) ≤ 2 che equivale a dire wt(u2) ≤ 2, cio perche w si puo scrivere

sia mediante l’uso di G che di G′; nel caso contrario si ha che wt(u1) ≤ 2.

Facilmente si puo calcolare che il peso della somma di due righe di B e maggiore

o uguale a quattro, allora si ha:

wt(w) = wt(ui) + wt(uiB) ≥ 1 + 4 = 5,

dove il valore i puo assumere il valore 1 o 2, ma cio e assurdo in quanto

wt(w) = 4 e la proprieta e provata.

8. Tale proprieta e evidende essendo d = 8. 2

101

4.4 Codici perfetti

Abbiamo visto, dalla proprieta 8 del teorema precedente, che il codice di Golay

esteso e un codice 3-correttore, cioe corregge tutti gli errori di peso minore o uguale

a tre.

Ci si propone adesso di definire un algoritmo per la correzione di tali errori. Se w

e la parola ricevuta, e u l’errore utilizzato per la correzione si ha che wt(u) ≤ 3.

L’errore u puo essere denotato mediante la seguente scrittura u =[

u1, u2

], dove

u1 e u2 hanno lunghezza 12 (l (ui) = 12 per i = 1 e 2). Poiche wt(u) ≤ 3, allora

deve essere wt(u1) ≤ 1 oppure wt(u2) ≤ 1. Indichiamo con s1 la sindrome di w, se

si usa la matrice di parita H =

I

B

, allora si ha che:

s1 = w ·H = u ·H =[

u1, u2

]· I

B

= u1 + u2B.

Consideriamo i seguenti due casi.

Primo caso

Se wt(u2) ≤ 1, cioe esso puo assumere i valori 0 e 1.

• Se wt(u2) = 0 segue che u2B = 0 e quindi risulta s1 = u1 + 0, con wt(u1) ≤ 3.

In questo caso l’errore e u = [s1, 0]. E facile verificare che tale errore ha peso

minore o uguale a tre e ha sindrome uguale a w ·H, quindi e un coset leader.

• Se wt(u2) = 1 segue che u2B individua una riga bj di B e si ha s1 = u1 + bj e

conseguentemente si ha che u1 = s1 + bj.

Si cerca quindi di determinare una riga bj per cui si ha che wt(u1) = wt(s1 +

bj) ≤ 2 ( ricordiamo che wt(u) ≤ 3), se tale bj esiste, allora l’errore e u =

[s1 + bj, ej] ed esso ha la stessa sindrome di w infatti:

102

4.4 Codici perfetti

u ·H =[

s1 + bj, ej

]· I

B

= s1 + bj + bj = s1

.

Secondo caso

Consideriamo adesso la sindrome di w usando la matrice di parita

H ′ =

B

I

, allora s2 = w ·H ′ =

[u1, u2

]· B

I

= u1B + u2.

Se wt(u1) ≤ 1, allora wt(u1) puo assumere i valori 0 e 1.

• Se wt(u1) = 0 segue che u1B = 0 e quindi risulta s2 = 0 + u2, con wt(u2) ≤ 3.

In questo caso l’errore e u = [0, s2]. Anche in questo caso si puo verificare che

tale errore ha peso minore o uguale a tre e ha sindrome uguale a w ·H ′, esso

e quindi un coset leader.

• Se wt(u1) = 1 segue che u1B individua una riga bi di B, quindi s2 = u2 + bi e

conseguentemente u2 = s2 + bi.

Si cerca quindi di determinare una riga bi per cui si ha che wt(u2) = wt(s2 +

bi) ≤ 2, se tale bi esiste, allora l’errore e u = [ei, s1 ·B + bi], ed esso ha la

stessa sindrome di w infatti:

u ·H ′ =[

ei, s1 ·B + bi

]· B

I

= bi + s2 + bi = s2.

Da questa tecnica di decodifica e possibile determinare un algoritmo di decodifica

per il codice di Golay esteso.

103

4.4 Codici perfetti

Osserviamo che essendo B = BT , allora B2 = B ·BT = I ed e lecito scrivere:

s1 ·B = (u1 + u2B) ·B = u1B + u2B2 = u1B + u2 = s2. (4.13)

Cio significa che, calcolata la sindrome s1 si puo facilmente determinare la sindrome

s2.

Algoritmo di decodifica

1. Calcolo della sindrome s1 = w ·H = u1 + u2B.

2. Se wt(s1) ≤ 3 allora u =[

s1, 0]

(caso in cui wt(u2) = 0).

3. Se wt(s1 + bj) ≤ 2 per qualche riga bj di B, allora u =[

s1 + bj, ej

], dove

ej e la parola di lunghezza 12 con un bit di valore “1” nell’j-esima posizione,

tutti gli altri bits hanno valore “0”.

4. Calcolo della sindrome s2 = w ·H ′ = s1 ·B.

5. Se wt(s1 ·B) ≤ 3 (caso in cui wt(u1) = 0), allora u =[

0, s1B].

6. Se wt(s1B + bi) ≤ 2 per qualche riga bi di B, allora u =[

ei, s1B + bi

].

7. Se u non e determinato, allora si richiede la ritrasmissione.

8. Fine. 2

104

4.4 Codici perfetti

Esempio 8

Sia la parola ricevuta w = 101111101111, 010010010010. Calcoliamo la sindrome:

s = w ·H = w

I

B

= 101111101111 + 001111101110 = 100000000001,

osserviamo che wt(s) = 2 ≤ 3. Pertanto:

u =[

s, 0]

= 100000000001, 000000000000.

La parola che con maggiore probabilita e stata inviata e:

v = w + u = 001111101110, 010010010010.

Esempio 9

Sia la parola ricevuta w = 001001001101, 101000101000. Calcoliamo la sindrome:

s = w ·H = w

I

B

= 001001001101 + 111000000100 = 110001001001,

osserviamo che wt(s) = 5 > 3. Pertanto dal passo 3 dell’algoritmo di decodifica si ha:

s + b1 = 000110001100 ⇒ wt(s + b1) = 4 > 3;

s + b2 = 011111000010 ⇒ wt(s + b2) = 6 > 3;

s + b3 = 101101011110 ⇒ wt(s + b3) = 8 > 3;

s + b4 = 001001100100 ⇒ wt(s + b4) = 4 > 3;

s + b5 = 000000010010 ⇒ wt(s + b5) = 2 < 3.

Quindi:

105

4.4 Codici perfetti

u =[

s + b5, e5

]= 000000010010, 000010000000.

La parola che con maggiore probabilita e stata inviata e:

v = w + u = 001001011111, 101010101000.

106

Capitolo 5

Codici ciclici

5.1 Polinomi su K

In questo capitolo e mostrato come una parola di un codice C di lunghezza n puo

essere rappresentata mediante polinomi di grado n− 1 su K, ma prima mostriamo

alcune proprieta dei polinomi a coefficienti in K, cioe dell’insieme K[x], i cui elementi

sono denotati con la simbologia f(x), g(x), p(x) ecc. ecc. Consideriamo un generico

polinomio di grado n di K[x].

f(x) = a0 + a1x + a2x2 + · · ·+ an−2x

n−2 + an−1xn−1 + anx

n.

In K[x] puo essere considerata la classica operazione di somma tra polinomi. Poiche

in K si ha che 1 + 1 = 0, allora segue che xk + xk = 0, tutto cio fa si che il grado

della somma di due polinomi f(x) + g(x) non ha sempre il massimo tra i gradi dei

polinomi f(x) e g(x).

107

5.1 Polinomi su K

Esempio 1

Siano i polinomi di K[x] f(x) = 1 + x + x4 e g(x) = x2 + x4, si ha che:

f(x) + g(x) = 1 + x + x2,

e evidente che il polinomio somma ha grado 2 minore di 4 cioe il massimo grado dei

polinomi f(x) e g(x).

Siano adesso i polinomi l(x) = 1 + x2 + x3 e p(x) = x + x2 + x4, si ha:

l(x) + p(x) = 1 + x + x3 + x4,

in questo caso invece il polinomio somma ha grado uguale al massimo grado dei due

polinomi.

Dagli esempi precedenti si puo affermare che nell’operazione di somma tra due

generici polinomi f(x) e g(x) di K[x] si ha che:

deg(f(x) + g(x)) ≤ max {deg(f(x)), deg(g(x))} .

Nell’operazione di somma l’elemento neutro e il polinomio nullo, inoltre considerato

un generico polinomio g(x) di K[x], dato che g(x) + g(x) = 0, allora e evidente che

l’opposto di tale polinomio e il polinomio stesso.

Consideriamo in K[x] la classica operazione di prodotto di cui si ha un’applicazione

nell’esempio seguente.

Esempio 2

Siano i polinomi f(x) = 1 + x + x3 + x4 e g(x) = x + x2 + x3 consideriamo il prodotto tra

tali polinomi:

108

5.1 Polinomi su K

f(x) · g(x) = (x + x2 + x3) + x(x + x2 + x3) + x3(x + x2 + x3) + x4(x + x2 + x3) = x + x7.

Consideriamo adesso il quadrato della somma di due polinomi osserviamo che:

[f(x) + g(x)]2 = f 2(x) + f(x)g(x) + f(x)g(x) + g2(x) = f 2(x) + g2(x).

Cio significa che nel quadrato della somma di due polinomi di K[x] non si ha il

doppio prodotto.

Consideriamo adesso i polinomi f(x) e h(x) con h(x) 6= 0, allora esiste un unico

polinomio q(x) ed unico polinomio r(x), con deg(r(x)) < deg(h(x)), tali che:

f(x) = h(x)q(x) + r(x). (5.1)

Il polinomio q(x) e detto quoziente, mentre r(x) resto.

Esempio 3

Sia f(x) = x + x2 + x6 + x7 + x8 e h(x) = 1 + x + x2 + x4, si ha che:

109

5.2 Parole di C e polinomi

Quindi f(x) = h(x)(x3 + x4) + (x + x2 + x3) e in particolare il quoziente e q(x) = x3 + x4,

il resto r(x) = x + x2 + x3, e possibile notare che deg(r(x)) < deg(h(x)) = 4.


In questa sessione viene messa in corrispondenza una parola di Kn con un polinomio

di grado n−1 su K, inoltre si fa vedere come si possono rappresentare tutte le parole

di un codice C mediante i polinomi di K[x]n−1, cioe l’insieme di polinomi su K con

grado minore o uguale a n− 1.

Consideriamo il polinomio f(x) = a0 + a1x + a2x2 + .... + an−1x

n−1 che ha grado

al piu n − 1, si ricorda che i coefficienti ai assumono valori su K e alcuni possono

assumere valore “0”. A f(x) facciamo corrispondere la parola di lunghezza n v =

a0a1a2....an−1. Si e quindi definita una corrispondenza biunivoca tra i polinomi di

K[x]n−1 e le parole di Kn.

Esempio 4

Sia n = 5, consideriamo il polinomio di K[x]4 f(x) = 1+x2 +x4 ad esso si puo associare la

parola v = 10101, mentre al polinomio g(x) = 1 + x si puo associare la parola w = 11000.

Siano f(x) e h(x) due polinomi con h(x) 6= 0, se si puo scrivere f(x) = h(x)q(x) +

r(x), allora diremo che f(x) in modulo h(x) e uguale a r(x) e scriveremo che

f(x) mod h(x) = r(x).

Si dice che due polinomi f(x) e g(x) sono equivalenti in modulo h(x) e scriveremo

110


f(x) ≡ g(x) mod h(x), se e solo se entrambi divisi per h(x) 6= 0 hanno lo stesso

resto cioe se:

f(x) mod h(x) = r(x) = g(x) mod h(x)

Esempio 5

Siano i polinomi f(x) = 1 + x4 + x9 + x11, g(x) = 1 + x6 e h(x) = 1 + x5, si ha che:

Quindi x11 +x9 +x4 +1 = (x5 +1)(x6 +x4 +x)+x+1 cioe f(x) in modulo h(x) e uguale

a x + 1, inoltre si ha:

Quindi x6 + 1 = (x5 + 1)x + x + 1 e vale f(x) mod (h(x)) = x + 1 = g(x) mod (h(x)),

allora si puo scrivere che f(x) ≡ g(x) mod h(x) = x + 1.

111

5.3 Codici ciclici

Fissato un polinomio h(x) di grado n, poiche per un qualunque polinomio f(x) di

K[x] si ha che f(x) mod h(x) = r(x) e il deg(r(x)) < n, allora ad ogni polinomio

f(x) di K[x] si puo associare un polinomio r(x) di K[x]n−1 che identifica una parola

binaria di lunghezza n. In particolare tutti i polinomi equivalenti in modulo h(x)

individuano la stessa parola di Kn.

Esempio 6

Il polinomio f(x) = 1 + x4 + x9 + x11 dell’esercizio 5 essendo in modulo h(x) = 1 + x5

uguale a x + 1 corrisponde alla parola di lunghezza 5 uguale a v = 11000.

Proprieta 7 Se p(x) e un polinomio di K[x] e f(x) ≡ g(x) mod h(x), allora valgono

le due seguenti proprieta.

• f(x) + p(x) ≡ g(x) + p(x) mod (h(x));

• f(x)p(x) ≡ g(x)p(x) mod (h(x)). 2

5.3 Codici ciclici

Prima di dare la definizione di codice ciclico in questa sessione e presentato un

particolare operatore che agisce su Kn e permette di ottenere ancora una parola di

Kn.

Sia v una parola di Kn, si definisce operatore shift ciclico l’applicazione π : Kn →Kn, esso agisce sulla parola v spostando il suo ultimo bit nella prima posizione.

112

5.3 Codici ciclici

Esempio 7

Si elencano in sequenza una serie di applicazioni dell’operatore π su diverse parole v di

lunghezza n differente.

Sia v = 1100 ⇒ π(v) = 0110.

Sia v = 011011 ⇒ π(v) = 101101.

Sia v = 101 ⇒ π(v) = 110.

Sia v = 10011 ⇒ π(v) = 11001.

E facile verificare che l’operatore π e lineare, quindi segue la proprieta.

Proprieta 8 L’operatore π e lineare cioe valgono le due proprieta:

• ∀ v, w ∈ Kn, π(v + w) = π(v) + π(w).

• ∀ a ∈ K = {0, 1}, π(av) = aπ(v).

Un codice C si dice ciclico se per qualunque parola v ∈ C si ha che anche π(v) ∈ C,

cioe se si effettua lo shift ciclico su una qualunque parola di C la parola ottenuta

appartiene ancora a C.

Esempio 8

Sia il codice C = {000, 110, 101, 011}, si ha che:

π(v) = π(000) = 000 ∈ C;

π(v) = π(110) = 011 ∈ C;

π(v) = π(101) = 110 ∈ C;

π(v) = π(011) = 101 ∈ C.

113

5.3 Codici ciclici

Quindi il codice C e un codice ciclico.

Si puo notare che il codice C dell’esempio 8 oltre ad essere ciclico e anche un codice

lineare, infatti la somma di due sue parole e ancora una parola del codice. L’esempio

seguente pero mostra che non tutti i codici lineari sono anche ciclici.

Esempio 9

Sia il codice C = {000, 100, 011, 111}, si ha che:

π(v) = π(100) = 010 /∈ C;

π(v) = π(011) = 101 /∈ C.

Il codice C e lineare ma non ciclico.

Cerchiamo di determinare un codice ciclico e lineare; sia v ∈ Kn e consideriamo

l’insieme S cosı definito:

S ={v, π(v), π2(v), · · · , πn−1(v)

},

dove con πi(v) si intende una sequenza di i applicazioni dell’operatore π cioe

π(π(· · · (π(v)) · · · ). Consideriamo l’insieme di tutte le possibili combinazioni lineari

delle parole di S, cioe L(v, π(v), π2(v), · · · , πn−1(v)), tale insieme definisce un codice

C che e ciclico lineare, in quanto C = L(v, π(v), π2(v), · · · , πn−1(v)) e l’operatore

π e un’applicazione lineare. E facile anche notare che un codice cosı ottenuto e il

piu piccolo codice ciclico lineare contenente v, infatti se v appartiene ad un codice

ciclico lineare C ′, con C ′ 6= C, allora esso sempre contiene l’insieme S e l’insieme

L(v, π(v), π2(v), · · · , πn−1(v)). L’insieme S e un insieme di generatori per il codice

lineare C.

114

5.4 Codice ciclico e polinomi di Kn−1

Esempio 10

Sia la parola di K3 v = 100, consideriamo l’insieme S = {100, 010, 001}, allora si ha che

C = K3 = {000, 100, 010, 001, 110, 101, 011, 111}.

Esempio 11

Sia la parola di K4 v = 0101, π(v) = 1010 e π2(v) = 0101 = v, quindi S = {0101, 1010}.E importante notare che la ciclicita delle parole v negli esempi precedenti era n−1, adesso

e 1 poiche π2(v) = v, il codice ottenuto e C = {0000, 0101, 1010, 1111}.


Come si e visto nella seconda sessione del capitolo una qualunque parola v puo

essere scritta in forma polinomiale. Facciamo quindi corrispondere ad ogni parola v

di lunghezza n, un polinomio v(x) di grado minore o uguale a n− 1.

L’operatore π sposta l’ultimo bit di v nella prima posizione formando una nuova

parola. In una visione polinomiale di v, l’operatore π e equivalente al prodotto

xv(x). Il concetto di shift ciclico, quindi, corrisponde al prodotto del fattore x per il

polinomio v(x), procedendo in una successione di prodotti per x si puo determinare

un polinomio f(x) di grado maggiore di n − 1 che e legato ad una parola binaria

di lunghezza n + 1. Nasce la necessita di “modulare” il polinomio f(x) ottenuto

tramite il polinomio h(x) = xn + 1, cioe si considera il polinomio f(x) mod h(x)

che ha grado minore o uguale a n − 1 e corrisponde ad una parola di lunghezza n.

E importante notare che poiche xn mod (xn + 1) = 1, allora se in un polinomio e

presente il termine xn esso si puo sostituire con il termine 1.

Quanto detto consente di generare un codice ciclico lineare da un punto di vista

115


polinomiale. Sia v una parola di Kn a cui e associato il polinomio v(x), costruiamo

l’insieme S cosı definito:

S ={v(x), xv(v), x2v(x), · · · , xn−1v(x)

}. (5.2)

Nella (5.2) al polinomio xiv(x) corrisponde la parola πi(v). E evidente che in S

possono essere presenti polinomi di grado maggiore di n − 1, allora e necessario

considerare ogni polinomio di S in modulo (xn+1), per far cio si utilizza la scrittura:

S ={v(x), xv(x), · · · , xn−1v(x)

}mod (xn + 1). (5.3)

L’insieme di tutte le combinazioni lineari dei polinomi di S in modulo (xn + 1)

costituisce un codice lineare ciclico ed esso e il piu piccolo codice ciclico contenente

la parola v. L’insieme S definisce un insieme di polinomi generatori del codice

ciclico lineare C, la tecnica di costruzione utilizzata e equivalente alla tecnica in cui

si adopera l’operatore π ed essa genera lo stesso codice.

Esempio 12

Sia la parola v = 1101000 di K7 e sia h(x) = x7 + 1. Formiamo l’insieme S costituito dai

7 polinomi.

v = 1101000 ⇒ v(x) = 1 + x + x3;

π(v) = 0110100 ⇒ xv(x) = x + x2 + x4;

π2(v) = 0011010 ⇒ x2v(x) = x2 + x3 + x5;

π3(v) = 0001101 ⇒ x3v(x) = x3 + x4 + x6

π4(v) = 1000110 ⇒ x4v(x) = x4 + x5 + x7 mod (x7 + 1) = 1 + x4 + x5;

π5(v) = 0100011 ⇒ x5v(x) = x5 + x6 + x8 mod (x7 + 1) = x + x5 + x6;

π6(v) = 1010001 ⇒ x6v(x) = x6 + x7 + x9 mod (x7 + 1) = 1 + x2 + x6.

116


I sette polinomi ottenuti costituiscono l’insieme S e sono i generatori del codice ciclico

lineare C.

Una qualunque parola c(x) di un codice ciclico C ottenuto da S puo esprimersi

mediante una combinazione lineare degli elementi di S, cioe:

c(x) =[a0v(x) + a1xv(x) + a2x

2v(x) + ... + an−1xn−1v(x)

]mod (xn + 1) =

= (a0+a1x+a2x2+...+an−1x

n−1)v(x) mod (xn+1) = a(x)v(x) mod (xn+1). (5.4)

Nella (5.4) si e determinato il polinomio a(x) = a0 + a1x + a2x2 + ... + an−1x

n−1 di

grado n− 1 che permette di enunciare il seguente lemma.

Lemma 2 Se C e un codice ciclico lineare e v ∈ C, allora per ogni polinomio a(x)

di grado n− 1 si ha che

c(x) = a(x)v(x) mod (xn + 1) ∈ C. (5.5)

2

117



Consideriamo un codice ciclico e lineare C dove ogni sua parola ha una rappresen-

tazione polinomiale, tra tutte le sue parole non nulle si consideri una parola a cui

corrisponde un polinomio g(x) che ha grado minimo rispetto ad ogni altra parola di

C.

E facile provare che esiste una sola parola il cui polinomio corrispondente ha grado

minimo. Supponiamo per assurdo che esistano due parole differenti in C a cui sono

associati due polinomi di grado minimo uguale a k, siano essi g(x) e g′(x). Se

si considera la somma delle due parole, quindi anche dei due polinomi, si ottiene

c(x) = g(x)+g′(x) e per la linearita di C si ha che c(x) ∈ C, inoltre poiche la somma

dei termini di grado k e zero (xk + xk = 0) segue che deg(c(x)) < k, cio e assurdo

in quanto per la scelta fatta, g(x) e g′(x) sono due polinomi di grado minimo in C

e non puo esistere in C una parola di grado minore di k. Il polinomio di minimo

grado in C e unico.

Se C e un codice ciclico lineare si chiama polinomio generatore di C l’unico

polinomio non nullo di grado minimo corrispondente a una parola di C. Il polinomio

generatore permette di generare tutte le parole di C.

Teorema 29 Se C e un codice ciclico lineare, allora si ha che ogni parola c(x) di

C si puo esprimere nel modo seguente:

c(x) = a(x)g(x). (5.6)

Dim.

Per provare il teorema basta mostrare che il polinomio generatore divide ogni parola

118


di C. Supponiamo per assurdo che esista una parola c(x) ∈ C che non e divisibile

per g(x), allora si ha che:

c(x) = a(x)g(x) + r(x),

dalla quale e possibile ottenere:

r(x) = a(x)g(x) + c(x).

Per il lemma 2 si ha che a(x)g(x) e una parola di C ed inoltre per la linearita di C

si ha che a(x)g(x) + c(x) ∈ C ne segue che anche r(x) ∈ C, ma questo e assurdo in

quanto deg(r(x)) < deg(g(x)) e deve necessariamente essere r(x) = 0. 2

Il seguente teorema permette di legare il polinomio generatore con i concetti di

dimensione e base di un codice ciclico e lineare C.

Teorema 30 Sia C un codice ciclico lineare di lunghezza n e g(x) il suo polinomio

generatore di grado n− k = deg(g(x)), allora si ha:

1. Il codice C ha dimensione k.

2. Le parole corrispondenti a g(x), xg(x), ... ,xk−1g(x) formano una base di C.

3. La parola c(x) appartiene a C se e solo se c(x) = a(x)g(x) dove deg(a(x)) < k

(cioe g(x) e un divisore per ogni parola c(x) in C).

Dim.

Il polinomio g(x) ha grado n− k, i polinomi g(x), xg(x), ..., xk−1g(x) hanno rispet-

tivamente grado n−k, n−k+1, ..., n−1, sono diversi dal polinomio nullo e nessuno

119


di essi puo essere espresso come combinazione lineare dei precedenti essendo questi

tutti di grado inferiore, quindi, per un teorema di Algebra lineare, essi sono linear-

mente indipendenti. Per il teorema 29 si ha che ogni parola c(x) di C si puo scrivere

come c(x) = a(x)g(x), cio prova il punto 3 del teorema ed inoltre i k polinomi g(x),

xg(x), ..., xk−1g(x) formano una base di C. 2

Esempio 13

Sia g(x) = 1 + x + x3 il polinomio generatore per il codice ciclico C di lunghezza n = 7,

si ha che deg(g(x)) = n − k = 3, da cui k = n − 3 = 4 e il codice C ha dimensione 4.

Calcoliamo una base per C moltiplicando g(x) per i fattori x, x2 e x3:

g(x) = 1 + x + x3 ⇒ 1101000;

xg(x) = x + x2 + x4 ⇒ 0110100;

x2g(x) = x2 + x3 + x5 ⇒ 0011010;

x3g(x) = x3 + x4 + x6 ⇒ 0001101.

Il teorema 30 definisce per un codice ciclico lineare C una sua base ottenuta dal

polinomio generatore g(x), allora tramite i polinomi g(x), xg(x), ..., xk−1g(x), si

puo definire la matrice generatrice del codice C nella seguente forma:

G =

g(x)

xg(x)

x2g(x)

.

.

xk−1g(x)

. (5.7)

120


Esempio 14

Sia C un codice ciclico lineare di lunghezza 4, avente polinomio generatore g(x) = 1 + x2,

allora si ha che n− k = 2. Una base per C e individuata dai polinomi:

g(x) = 1 + x2 ⇒ 1010

xg(x) = x + x3 ⇒ 0101.

La matrice generatrice di C e:

G =

1 0 1 0

0 1 0 1

.

Uno dei problemi fondamentali per la determinazione di un codice ciclico lineare

che ha parametri n e k e quello di individuare il suo polinomio generatore g(x).

Diverse sono le tecniche utilizzate e i due teoremi seguenti danno indicazioni su

alcune proprieta del polinomio generatore.

Teorema 31 Se g(x) e il polinomio generatore di un codice lineare ciclico C di

lunghezza n, allora g(x) divide 1 + xn cioe 1 + xn = g(x)f(x) e vale il viceversa.

Dim.

Se dividiamo 1 + xn per g(x) si ha 1 + xn = g(x)f(x) + r(x), da cui si ottiene che

r(x) = g(x)f(x)+(1+xn). Poiche ogni polinomio deve essere considerato in modulo

(1+xn) e lecito scrivere r(x) = (g(x)f(x)+(1+xn)) mod (xn +1), tenendo presente

che (1 + xn) mod (xn + 1) ha resto zero, si ha che r(x) = g(x)f(x) mod (xn + 1),

quindi r(x) ∈ C, ma deg(r(x)) < deg(g(x)) e poiche g(x) e il polinomio di grado

minimo in C, allora r(x) deve essere il polinomio nullo. 2

121

5.6 Sindrome e matrice di parita

Teorema 32 Il polinomio generatore g(x) del piu piccolo codice lineare ciclico C,

di lunghezza n e contenente la parola corrispondente a v(x), e il massimo comune

divisore di v(x) e di (1 + xn).

Dim.

Per il lemma 2 si ha che ogni parola c(x) ∈ C si puo esprimere come c(x) =

v(x)a(x) mod (xn+1), allora in particolare per g(x) si ha g(x) = a(x)v(x) mod (xn+

1) o equivalentemente g(x) = a(x)v(x) + b(x)(xn + 1). Per i teoremi 31 e 29 si ha

che g(x) e un divisore di (1 + xn) e di v(x), quindi ogni comune divisore per v(x)

e 1 + xn deve dividere anche g(x), pertanto esso e il massimo comune divisore fra

v(x) e 1 + xn. 2

Un metodo alternativo per cercare un polinomio generatore, di un codice ciclico C di

dimensione k, consiste nel cercare di ridurre una sua matrice generatrice G in modo

che le colonne leading siano le ultime colonne di G. La riga di G corrispondente al

polinomio di minimo grado individua il polinomio generatore.


Supponiamo sia stata ricevuta la parola w, corrispondente a w(x), e che sia sta-

ta inviata la parola v, associata a v(x), allora definiamo errore polinomiale il

polinomio e(x) = v(x) + w(x). Si definisce sindrome polinomiale la quantita:

s(x) = w(x) mod (g(x)). (5.8)

Poiche g(x) ha grado n−k, allora la sindrome s(x) ha grado minore di n−k e ad essa

122


corrisponde una parola di lunghezza n− k. Supponiamo che w(x) ∈ C, allora dato

che w(x) = a(x)g(x), segue che la sua sindrome e s(x) = 0. Se invece w(x) /∈ C,

allora, poiche w(x) = v(x) + e(x), si ha che

s(x) = w(x) mod (g(x)) = [v(x) + e(x)] mod (g(x)) = e(x) mod (g(x)),

dato che v(x) mod (g(x)) = 0. Cio comporta che la sindrome della parola rice-

vuta w(x) corrisponde alla sindrome dell’errore e(x) e la definizione di sindrome

polinomiale corrisponde alla definizione di sindrome data nel capitolo 3.

Si definisce matrice di parita Hn×n−k la matrice la cui i-esima riga, ri, e la parola

di lunghezza n− k corrispondente al polinomio:

ri(x) = xi mod (g(x)) per 0 ≤ i ≤ n− 1.

La matrice di parita e:

H =

x0

x

x2

.

.

xn−1

mod (g(x)). (5.9)

Se w e la parola ricevuta, poiche w(x) = v(x) + e(x) la sindrome polinomiale si puo

ottenere anche mediante la matrice H nel seguente modo:

123


w ·H = (v + e) ·H ≡ ∑n−1i=0 (vi + ei)x

i mod (g(x)) =

=∑n−1

i=0 vixi mod (g(x)) +

∑n−1i=0 eix

i mod (g(x)) =

=∑n−1

i=0 eixi mod (g(x)) = e(x)mod(g(x)).

Ancora una volta la definizione precedente coincide con la definizione di sindrome

ottenuta tramite la matrice di parita del capitolo 3.

Esempio 15

Consideriamo un codice C di lunghezza 7 con polinomio generatore g(x) = 1 + x + x3, si

ha che n− k = 3, quindi la dimensione di C e k = 4. Costruiamo la matrice di parita nel

modo seguente:

r0(x) = 1 mod (g(x)) = 1 ⇔ 100;

r1(x) = x mod (g(x)) = x ⇔ 010;

r1(x) = x2 mod (g(x)) = x2 ⇔ 001;

r1(x) = x3 mod (g(x)) = 1 + x ⇔ 110;

r1(x) = x4 mod (g(x)) = x + x2 ⇔ 011;

r1(x) = x5 mod (g(x)) = 1 + x + x2 ⇔ 111;

r1(x) = x6 mod (g(x)) = 1 + x2 ⇔ 101.

La matrice di parita e:

H =

1 0 0

0 1 0

0 0 1

1 1 0

0 1 1

1 1 1

1 0 1

.

124

Capitolo 6

Campi finiti e codici 2 - BCH

In questo capitolo e definita la nozione di campo finito. La trattazione non sara

rigorosa, ma mirata a dare quei concetti base utili ad un corso di Teoria dei Codici

rivolto a studenti di ingegneria. Per maggiori approfondimenti si consiglia la visione

di testi di Matematica Discreta e Campi Finiti.

Quando si dice che un insieme numerico e un “campo”?

Un campo e un insieme numerico C su cui sono definite due operazioni algebriche

binarie di cui la prima, generalmente chiamata somma (+), risulta essere un grup-

po commutativo e la seconda, chiamata prodotto (×), risulta anch’essa un gruppo

commutativo sull’insieme C−{0}, cioe l’insieme numerico C con l’esclusione dell’ele-

mento neutro 0 rispetto alla somma. Esempi di insiemi numerici che sono dei campi

possono essere quelli dei numeri reali e dei numeri complessi su cui sono definite le

classiche operazioni di somma e prodotto.

125

6.1 Polinomio primitivo

Nel capitolo precedente si e definita una corrispondenza tra le parole di Kn e i

polinomi di K[x] in modulo xn + 1, cioe i polinomi di K[x]n−1. E evidente che per

tali polinomi vale la classica operazione di somma e rispetto a tale operazione si ha

che K[x]n−1 e un gruppo abeliano con elemento neutro il polinomio nullo, l’inverso

di un qualunque polinomio g(x) e se stesso. L’operazione di somma di due polinomi

di K[x]n−1 e equivalente all’operazione di somma definita precedentemente in Kn

come si vede nell’esempio seguente.

Esempio 1

Siano in K4 le due parole v = 0101 e w = 0111 corrispondenti ai polinomi v(x) = x + x3

e w(x) = x + x2 + x3, allora si ha che:

v + w = 0101 + 0111 = 0010,

equivalentemente,

v(x) + w(x) = x2.

Tale polinomio somma in K4 corrisponde alla parola 0010.


Un polinomio g(x) si dice irriducibile se esso e divisibile solo per 1 e per se stesso,

in caso contrario e detto riducibile. Nell’esempio seguente sono elencati una serie

di polinomi che sono sia riducibili che irriducibili.

126


Esempio 2

1. x e irriducibile.

2. x + 1 e irriducibile.

3. x2 e evidentemente riducibile.

4. x2 + 1 e riducibile in quanto si puo esprimere come (x + 1)2.

5. x2+x+1 e irriducibile in quanto non si puo esprimere come prodotto di due polinomi

di primo grado.

6. x3+x+1 e irriducibile in quanto non si puo esprimere come prodotto di un polinomio

di primo grado e un polinomio di secondo grado.

7. x4 + x + 1 e irriducibile.

8. x4 + 1 e riducibile in quanto puo essere scritto come (x2 + 1)2 .

Diamo adesso una definizione che assume una fondamentale importanza nella definizione

dei campi finiti. Un polinomio irriducibile di grado n > 1 e detto primitivo se esso

non divide tutti i polinomi del tipo xm + 1 con m < 2n − 1 e divide il polinomio

xm + 1 con m = 2n − 1.

Esempio 3

Consideriamo il polinomio h(x) = 1 + x + x2, n = 2, esso e irriducibile e m = 22 − 1 = 3.

Se si considerano i polinomi del tipo xm + 1, con m < 3, allora si ha che essi non sono

divisibili per h(x), mentre e divisibile x3 + 1.

127


Quindi h(x) e un polinomio primitivo.

Esempio 4

Consideriamo il polinomio irriducibile h(x) = x3 +x+1 e m = 23−1 = 7. Tutti i polinomi

xm + 1 con m < 7 non sono divisibili per h(x). Verifichiamo se esso divide il polinomio

x7 + 1:

Quindi h(x) e un polinomio irriducibile e primitivo.

128

6.2 Campi finiti di Galois

Esempio 5

Sia il polinomio h(x) = 1 + x + x2 + x3 + x4, con m = 24 − 1 = 15, esso, se primitivo, non

divide tutti i polinomi xm + 1 con m < 15, ma poiche:

x5 + 1 = (1 + x)(1 + x + x2 + x3 + x4),

allora h(x) divide x5 + 1 ed esso non e un polinomio primitivo.


Si considerino i polinomi di K[x] in modulo xn + 1 e definiamo in essi la classica

operazione di prodotto tra polinomi, cioe se f(x) e g(x) sono due polinomi arbitrari

non nulli di K[x] allora il loro prodotto e:

f(x) · g(x) mod xn + 1

e deve appartenere a K[x]n−1 − {0}, cioe dati due polinomi f(x) e g(x) non nulli, il

loro polinomio prodotto deve essere anch’esso non nullo e appartenere a K[x]n−1 −{0}.L’esempio seguente mostrera che il prodotto definito precedentemente non rispetta

sempre tale proprieta.

Esempio 6

Proviamo ad utilizzare l’operazione di moltiplicazione sui polinomi in modulo 1 + x4 cioe

sui polinomi di K[x]3 equivalenti alle parole di K4. Sia la parola v = 0101 corrispondente

al polinomio v(x) = x + x3 e consideriamo il prodotto v(x) · v(x):

129


(x + x3)2 = x2 + x6.

Consideriamo adesso tale polinomio in modulo x4 + 1 cioe:

quindi,

(x + x3)2 = (x2 + x6)mod(x4 + 1) = 0.

Il problema presentato nell’esempio 7 e legato al fatto che 1+x4 non e irriducibile e

tutti i polinomi riducibili divisibili per 1+x4 sono equivalenti in modulo al polinomio

nullo, quindi alla parola nulla.

In base a quest’ultima osservazione consideriamo i polinomi di K[x] in modulo h(x)

con h(x) polinomio primitivo di grado n > 1. Se indichiamo il polinomio x con il

simbolo β , allora e possibile usare la seguente scrittura:

130


βi = ximod(h(x)). (6.1)

Si noti che h(x), poiche e un polinomio primitivo, non divide i polinomi 1 + xm

per m < 2n − 1 e quindi βm 6= 1 per m < 2n − 1, ma divide 1 + xm, allora

1 = xm mod (h(x)) o equivalentemente βm = 1 se e solo se m = 2n − 1.

Si definisce il seguente insieme:

GF (2n) ={βi|i = 0, 1, ..., 2n − 2

} ⋃{0} . (6.2)

L’insieme GF (2n) contiene 2n elementi distinti, infatti se supponiamo che due suoi

elementi βi e βj, con i < j e 0 ≤ i, j ≤ 2n − 2 siano tali che βi = βj, allora si ha

che βi = βj−iβi, il che implica che βj−i = 1, cio accade solo se j − i e un multiplo

di 2n − 1, ma essendo 1 ≤ j − i ≤ 2n − 2 < 2n − 1 questo e impossibile e si ha che

βi 6= βj.

L’insieme GF (2n) ha la struttura di campo con le operazioni di somma e prodotto,

esso prende il nome di Campo di Galois. Ogni singolo elemento di GF (2n) si puo

mettere in corrispondenza con le parole di Kn, come vedremo nell’esempio seguente

in cui viene mostrato come si costruisce il campo di Galois GF (24) in cui sono

facilmente definite le operazioni di somma e prodotto.

131


Esempio 7

Dato il polinomio primitivo h(x) = 1 + x + x4, costruiamo il campo GF (24) ricavando i

suoi elementi come indicato nella tabella (6.1).

parola polinomio campo

0000 0 0

1000 1 1

0100 x β

0010 x2 β2

0001 x3 β3

1100 x4 = 1 + x β4

0110 x5 = x + x2 β5

0011 x6 = x2 + x3 β6

1101 x7 = x3 + x4 = 1 + x + x3 β7

1010 x8 = x + x2 + x4 = x + x2 + 1 + x = 1 + x2 β8

0101 x9 = x + x3 β9

1110 x10 = x2 + x4 = x2 + 1 + x β10

0111 x11 = x3 + x2 + x β11

1111 x12 = x4 + x3 + x2 = x + 1 + x2 + x3 β12

1011 x13 = x2 + x + x3 + x4 = x2 + x + x3 + 1 + x = 1 + x2 + x3 β13

1001 x14 = x3 + x4 + x = x3 + x + 1 + x = x3 + 1 β14

Tabella 6.1: GF (24)

La somma tra gli elementi di GF(24) e estremamente semplice in quanto definita come

somma algebrica degli elementi di GF (24). Calcoliamo il prodotto tra le due parole (0110)

e (1101), corrispondenti alle parole β5 e β7 e ai polinomi x + x2 e 1 + x + x3, si ha che:

132


(0110) · (1101) = β5 · β7 = β12 = 1111.

Cio e equivalente al prodotto dei polinomi corrispondenti in modulo h(x):

(x + x2) · (1 + x + x3) = x5 · x7 = x12 mod h(x).

Un elemento α ∈ GF (2n) e detto primitivo se ogni sua potenza m, con 1 ≤ m <

2n − 1, e diversa da 1 (αm 6= 1).

Si definisce ordine di un elemento α 6= 0 di GF (2r) il piu piccolo intero positivo m

per cui si ha che αm = 1. In particolare un elemento primitivo di GF (2r) ha ordine

2n − 1.

Sia il polinomio p(x) ∈ K[x], si dice che p(x) ammette una radice α ∈ GF se

p(α) = 0.

Esempio 8

Sia il polinomio p(x) = 1 + x3 + x4, con h(x) = 1 + x + x4 polinomio primitivo, vediamo

se β e una sua soluzione in GF (24).

p(β) = 1 + β3 + β4 = 1000 + 0001 + 1100 = 0101 = β9 6= 0000,

quindi β non e una radice di p(x).

Consideriamo adesso l’elemento β7 ∈ GF e vediamo se esso e radice di p(x). Ricordando

che β15 = 1 si ha:

p(β7) = 1 + (β7)3 + (β7)4 = 1 + β21 + β28 = 1 + (β15 · β6) + (β15 · β13) =

= 1000 + 0011 + 1011 = 0000

Quindi β7 e soluzione di p(x).

133

6.3 Polinomio minimo


Se α e un arbitrario elemento di GF (2n), allora si definisce polinomio minimo

di α il polinomio di minimo grado che ha come radice α. Il polinomio minimo

di α e denotato mediante la simbologia mα(x), oppure, dato che α = βi, per un

determinato i, con mi(x) e le due scritture sono equivalenti:

mα(x) ≡ mi(x)

Trovare il polinomio minimo di un elemento α di GF (2n) si riconduce a determinare

una combinazione lineare non banale dei vettori {1, α, α2, ..., αn} che origini la parola

nulla cioe in termini di elementi di GF (2n):

a0 + a1α + a2α2 + a3α

3 + ... + arαn = 0.

Tale combinazione lineare esiste poiche ogni elemento della combinazione lineare

rappresentata nell’equazione precedente corrisponde a una parola di Kn in cui n+1

elementi sono sempre linearmente dipendenti.

Esempio 9

Cerchiamo di determinare il polinomio minimo dell’elemento α = β3 ∈ GF (24), dove si

utilizza come polinomio primitivo h(x) = 1 + x + x4. Consideriamo l’equazione

mα(x) = m3(x) = a01+ a1α + a2α2 + a3α

3 + a4α4 = a0β

0 + a1β3 + a2β

6 + a3β9 + a4β

12 =

= a01 + a1x3 + a2(x2 + x3) + a3(x + x3) + a4(1 + x + x2 + x3). (6.3)

Bisogna determinare i valori a0, a1, .., a4 ∈ {0, 1}, vista la corrispondenza tra gli elementi

di GF (24) e le parole di K4 si ha:

134


0000 = a0(1000) + a1(0001) + a2(0011) + a3(0101) + a4(1111) (6.4)

Risolvendo per componenti rispetto a a0, a1, a2, a3, a4 si determina:

a0 + a4 = 0

a3 + a4 = 0

a2 + a4 = 0

a1 + a2 + a3 + a4 = 0

quindi:

a0 = a4

a3 = a4

a2 = a4

a1 = a4

Per determinare una combinazione non banale e necessario porre a4 = 1 e quindi si ha che

a0 = a1 = a2 = a3 = a4 = 1 e il polinomio minimo e:

m3(x) = 1 + x + x2 + x3 + x4.

Il teorema seguente mostra le principali proprieta dei polinomi minimi.

Teorema 33 Sia α 6= 0 un elemento di GF (2n) e sia mα(x) il suo minimo poli-

nomio si ha:

1. Il polinomio minimo mα(x) e irriducibile.

2. Se f(x) e un polinomio tale che f(α) = 0, allora mα(x) divide f(x).

135


3. Il polinomio minimo mα(x) e unico.

4. Il polinomio minimo mα(x) divide x2n−1 + 1.

Dim.

1. Supponiamo per assurdo che mα(x) e riducibile, in tal caso esso puo es-

sere scritto come mα(x) = q(x)p(x), poiche mα(α) = 0, allora si ha che

q(α)p(α) = 0 e quindi q(α) = 0 oppure p(α) = 0, ma deg(q(x)) < deg(mα(x))

e deg(p(x)) < deg(mα(x)), questo e assurdo in quanto mα(x) e il polinomio di

grado minore che ha α come radice.

2. Supponiamo che mα(x) non divide f(x), allora si puo scrivere:

f(x) = mα(x)q(x) + r(x),

dove deg(r(x)) < deg(mα(x)), per ipotesi f(α) = 0 quindi:

f(α) = mα(α)q(α) + r(α) = 0 · q(α) + r(α) = r(α) = 0,

cio e assurdo perche il polinomio r(x) ha α come radice ed ha grado inferiore

di mα(x).

3. Se esistono due polinomi minimi m′α(x) e mα(x), per la parte seconda del

teorema si ha che mα(x) divide m′α(x) e m′

α(x) divide mα(x), cio vuol dire che

mα(x) = m′α(x) e il polinomio minimo e unico.

4. Poiche α e un elemento di GF (2n), allora esiste un i per cui α = βi ed inoltre:

α2n−1 + 1 = (βi)2n−1 + 1 = (β2n−1)i + 1 = 1i + 1 = 1 + 1 = 0.

Pertanto, mα(x) divide x2n−1 + 1. 2

136


La seguente proprieta permette di ottenere informazioni sulle radici dei polinomi

minimi.

Proprieta 9 Sia f(x) un polinomio in K allora si ha che:

f(x)2 = f(x2). (6.5)

Dim.

La proprieta e dimostrata dalle seguenti eguaglianze:

f(x)2 =

(n∑

i=0

aixi

)2

=n∑

i=0

ai(xi)2 =

n∑i=0

ai(x2)i = f(x2).

2

La proprieta (9) permette di affermare che se α e una radice del polinomio f(x) cioe

f(α) = 0, allora anche f(α2) = 0, quindi α2 e una radice di f(x), cosı come lo e

anche α4 e in generale α2n−1.

Teorema 34 Le radici del polinomio minimo mα(x) sono α, α2, α4, · · · , α2n−1, in

particolare i polinomi m1(x) e m3(x) hanno n radici distinte e rispettivamente sono:

{β, β2, β4, ..., β2n−1}, (6.6)

{β3, β6, ..., β3(2n−1)}.

137


Dim.

La prima parte della proprieta segue dalla proprieta 9. Sia il polinomio minimo

m1(x), consideriamo due soluzioni β2ie β2j

della (6.6) e supponiamo per assurdo

che β2i= β2j

con i > j e 0 ≤ i, j ≤ n− 1, allora si ha:

β2j · β2i−2j

= β2j

,

equivalente all’equazione:

β2i−2j

= 1. (6.7)

La (6.7) vale se 2i − 2j = k(2n − 1), cioe 2i − 2j e un multiplo di 2n − 1, ma poiche

i e j variano tra 0 e n− 1, allora si ha:

2i − 2j ≤ 2n−1 − 1 < 2n − 1.

Cio mostra che 2i − 2j non e un multiplo di 2n − 1 e tutte le n soluzioni di m1(x)

sono tutte distinte. Con uguale procedura si dimostra che anche tutte le soluzioni

di m3(x) sono tutte distinte. 2

elemento di GF(24) polinomoio minimo

0 x

1 1 + x

β, β2, β4, β8 1 + x + x4

β3, β6, β9, β12 1 + x + x2 + x3 + x4

β5, β10 1 + x + x2

β7, β11, β13, β14 1 + x3 + x4

Tabella 6.2: Radici e polinomi minimi in GF(24)

138

6.4 Codici di Hamming

La precedente tabella individua le soluzioni di tutti i polinomi minimi di GF (24).


I codici di Hamming sono codici perfetti 1-correttori che hanno lunghezza l = 2n−1 e

le righe della loro matrice di parita hanno lunghezza n. In questa sezione e mostrato

che le 2n − 1 righe della matrice di parita di un codice di Hamming possono essere

rappresentate mediante gli elementi non nulli di un campo di Galois GF (2n), infatti

essendo β un elemento primitivo di GF (2n) allora per definizione le sue potenze

sono tutte distinte e individuano i 2n − 1 elementi non nulli di GF corrispondenti

alle parole non nulle di Kn.

La matrice di parita di un codice di Hamming di lunghezza l = 2n − 1 puo essere

espressa nel seguente modo:

H(2n−1)×r =

1

β

β2

.

βi

.

β2n−2

. (6.8)

Esempio 10

Se n = 3, allora l = 23 − 1 = 7. Definiamo GF (23) mediante il polinomio primitivo

p(x) = 1 + x + x3, l’elemento β corrispondente al polinomio x e alla parola di K3 010,

ricordando poi che xi mod p(x), si ottiene:

139


H =

1

β

β2

β3

β4

β5

β6

↔ H =

1 0 0

0 1 0

0 0 1

1 1 0

0 1 1

1 1 1

1 0 1

.

Quanto detto precedentemente si puo riassumere mediante il seguente teorema.

Teorema 35 Un polinomio primitivo di grado n e il generatore polinomiale di un

codice ciclico di Hamming di lunghezza 2n − 1. 2

Sia C un codice ciclico di lunghezza n con polinomio generatore g(x) e supponiamo

che α ∈ GF (2n) sia una radice di g(x), allora chiaramente si ha che g(α) = 0. Poiche

tutte le parole c(x) di C possono essere scritte come c(x) = a(x) · g(x) allora segue

che c(α) = g(α) · x(α) = 0. Per i teoremi 33 e 34 si ha che mα(x) e divisore di ogni

parola c(x) appartenente a C ed inoltre e possibile scrivere g(x) come prodotto di

polinomi minimi.

Teorema 36 Sia g(x) il polinomio generatore di un codice ciclico di lunghezza n,

allora g(x) sara il prodotto dei minimi polinomi di α1, α2, ..., αk ∈ GF (2n), se e solo

se

∀c(x) ∈ C c(α1) = c(α2) = ... = c(αk) = 0. (6.9)

2

140


Cerchiamo di individuare una tecnica utile all’individuazione e alla correzione degli

errori per i codici di Hamming.

Se c(x) e la parola che e stata inviata e w(x) la parola ricevuta, allora l’errore e(x)

e definito nel seguente modo:

w(x) = c(x) + e(x).

Se il polinomio generatore g(x) = mα(x) e il polinomio primitivo, allora α e radice

di tale polinomio (g(α) = 0) e si ha che:

w(α) = c(α) + e(α) = 0 + e(α) = αj,

dove αj e un elemento del campo GF . Pertanto il polinomio che rappresenta l’errore

e e(x) = xj e la correzione della parola ricevuta si puo scrivere come:

c(x) = w(x) + xj.

Poiche si ha che:

c(α) = w(α) + αj = αj + αj = 0.

Quindi la parola ottenuta adoperando questa tecnica e una parola del codice. E

importante notare che l’aggiunta del polinomio xj a w(x) corrisponde in termini di

parole di Kn al cambio del valore della componente j-esima nella parola ricevuta.

Esempio 11

Consideriamo il polinomio m1(x) = 1 + x + x3 (primitivo con soluzione β) e il campo di

Galois GF (23). Supponiamo di ricevere w(x) = 1 + x2 + x3 + x6, allora:

141

6.5 Codici 2-BCH

w(β) = 1 + β2 + β3 + β6 = 100 + 001 + 110 + 101 = 110 = β3

L’errore in questo caso e dato dal polinomio e(x) = x3, quindi la correzione della parola

ricevuta e:

c(x) = w(x) + e(x) = 1 + x2 + x3 + x6 + x3 = 1 + x2 + x6

6.5 Codici 2-BCH

Una importante classe di codici correttori multipli e la classe dei codici BCH ( dai

nomi di Bose, Chaudhuri e Hocquengham ). Essi sono definiti da due interi positivi

r e t, con t < 2r−1 − 1, e la loro lunghezza e n = 2r − 1, essi sono codici t-correttori

di dimensione k ≥ n− rt.

In questa sessione sono considerati solo codici BCH 2-correttori di lunghezza

2r − 1. Essi hanno come polinomio generatore il polinomio g(x) = mβ(x)mβ3(x),

dove β appartiene a GF (2r) con r ≥ 4. Poiche n = 2r − 1 e g(x) divide 1 + xn,

allora g(x) e il polinomio generatore di un codice ciclico.

Si consideri un campo GF (2r) avente come polinomio generatore g(x) = m1(x)m3(x),

dove m1(x) e m3(x) sono due polinomi minimi aventi ciascuno r soluzioni distinte.

La matrice di parita H di tali codici e definita nel modo seguente:

142

6.6 Schema di codifica per codici 2-BCH

β0 β0

β β3

β2 β6

. .

βi β3i

. .

β2r−2 β3(2r−2)

(6.10)

Poiche βi e un elemento di GF (2r), esso rappresenta una parola di lunghezza r, quin-

di H e una matrice (2r − 1)× (2r). Inoltre, poiche il deg(m1(x)) = r = deg(m3(x))

ne segue che il grado di g(x) = m1(x)m3(x) e n − k = 2r, pertanto il codice ha

dimensione k = n− 2r = 2r − 1− 2r. Si puo dimostrare (ma non verra fatto in tale

trattazione) che la distanza di tali codici e d = 2.


Consideriamo che w e la parola ricevuta e w(x) il polinomio ad essa associato in una

trasmissione che utilizza un codice 2-BCH. Ricordando che tale codice e un codice

2- correttore, allora la sindrome di w e:

w ·H =[

w(β), w(β3)]

=[

s1, s3

](6.11)

dove s1 e s3 sono due parole di lunghezza r. Nella sequenza successiva e illustrato

la tecnica che permette di individuare l’algoritmo di decodifica dei codici 2-BCH.

• Se non vi sono errori nella trasmissione di w, cioe se w ∈ C, allora si ha che

w ·H = 0 e quindi s1 = s3 = 0.

• Se si e nel caso in cui vi e solo un errore nella trasmissione della parola w,

allora l’errore utilizzato per correggere w(x) e e(x) = xi dato che tale errore,

143


se esso e nella i-esima componente di w, individua la i-esima riga di H nel

calcolo della sindrome di w:

w ·H = e ·H =[

βi, β3i

]=

[s1, s3

](6.12)

Tale caso si verifica se calcolando la sindrome si ha che s31 = s3.

• Se si e nel caso in cui vi sono due errori nella trasmissione di w ed essi sono nelle

posizioni i-sima e j-esima, con i 6= j, allora l’errore utilizzato per correggere

w(x) e e(x) = xi+xj. Infatti la sindrome di w, per il teorema 18 del capitolo 3,

e la combinazione lineare delle righe i-esima e j-esima di H, cioe:

w ·H = e ·H =[

βi + βj, β3i + β3j

]=

[s1, s3

]. (6.13)

Consideriamo il seguente sistema di equazioni risultante:

βi + βj = s1

β3i + β3j = s3.

Poiche:

β3i + β3j = (βi + βj)(β2i + βi+j + β2j),

ed inoltre:

s21 = (βi + βj)2 = β2i + β2j,

allora e possibile scrivere:

s3 = β3i + β3j = (βi + βj)(β2i + β2j + βi+j) = s1(s21 + βi+j),

144


Da cui si ottiene:

s3

s1

+ s21 = βi+j.

E possibile pensare βi e βj come radici dell’equazione di secondo grado:

x2 + (βi + βj)x + βi+j = 0.

Tale polinomio prende il nome di Polinomio di individuazione di errore

ed esso puo essere anche scritto mediante s1 e s3, cioe:

x2 + s1x + (s3

s1

+ s21) = 0 (6.14)

Pertanto nel caso di un errore di peso due calcolata la sindrome nelle sue parti

s1 e s3, mediante sostituzione si determinano le radici dell’equazione (6.14) e

si individua e(x).

Se la tecnica mostrata precedentemente non permette di determinare e(x), cioe non

si trovano soluzioni della (6.14), allora vuol dire che e accaduto un errore con peso

maggiore di due ed e necessario richiedere la ritrasmissione.

Esempio 12

Sia w la parola ricevuta la cui sindrome e composta da s1 = 0111 = w(β) e da s3 = 1010 =

w(β3). Dalla tabella 6.1 si deduce che s1 = β11 e s3 = β8, quindi:

s3

s1+ s2

1 =β8

β11+ β22 = β8β−11β15 + β7β15 = β12 + β7 = 1111 + 1101 = 0010 = β2,

e polinomio di individuazione di errore e:

x2 + β11x + β2 = 0,

le cui soluzioni numeriche, determinate mediante sostituzione, sono βi = β4 e βj = β13.

145

APPUNTI DI TEORIA DEI CODICI - pelleriti.altervista.orgpelleriti.altervista.org/doc/TC.pdf · di...

Documents

Transcript of APPUNTI DI TEORIA DEI CODICI - pelleriti.altervista.orgpelleriti.altervista.org/doc/TC.pdf · di...