UNIVERSITÀ DI CATANIA
FACOLTÀ DI INGEGNERIA
APPUNTI DI TEORIA DEI CODICI
Autori:
L. Cauchi
V. La Terra
R. Grasso
F. Gullo
c
Coperto da diritti di °copyright
Ho letto questi appunti scritti da Lucia Cauchi, Rosario Grasso, Valeria La Terra e
Francesco Gullo, studenti che hanno seguito il mio corso di “Teoria dei Codici” negli anni
accademici 2005 – 2006, 2006 – 2007 e 2008 – 2009. Lucia, Rosario e Valeria hanno
contribuito alla stesura dei primi sei capitoli, mentre Francesco ha scritto il settimo.
Ho deciso di inserirli nella mia pagina web perchè 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, Valeria La Terra e Francesco Gullo, per la loro disponibilità 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’Università 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
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
1.5
Algoritmo di Huffman . . . . . . . . . . . . . . . . . . . . . . 15
La funzione entropia . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5.1
Proprietà della funzione entropia . . . . . . . . . . . . . . . . 24
2 I Primi concetti
27
2.1
Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.2
Probabilità e distanza
2.3
Peso ed errore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4
Prime tecniche di codifica . . . . . . . . . . . . . . . . . . . . . . . . 37
2.5
Individuazione di errore . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.6
Correzione di errore . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
. . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Codici lineari
47
3.1
Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2
Prodotto scalare in K n . . . . . . . . . . . . . . . . . . . . . . . . . . 49
i
INDICE
3.3
Matrice generatrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4
Matrice di parità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.1
Algoritmo di generazione di H . . . . . . . . . . . . . . . . . . 55
3.5
Coset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.6
Sindrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
4 Codici perfetti
75
4.1
Cardinalità di un codice C . . . . . . . . . . . . . . . . . . . . . . . . 75
4.2
Codici MDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.3
Codici estesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
4.4
Codici perfetti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.4.1
Codice di Hamming . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4.2
Codice di Golay esteso . . . . . . . . . . . . . . . . . . . . . . 94
5 Codici ciclici
104
5.1
Polinomi su K . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
5.2
Parole di C e polinomi . . . . . . . . . . . . . . . . . . . . . . . . . . 107
5.3
Codici ciclici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
5.4
Codice ciclico e polinomi di K n−1 . . . . . . . . . . . . . . . . . . . . 112
5.5
Matrice generatrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
5.6
Sindrome e matrice di parità . . . . . . . . . . . . . . . . . . . . . . . 120
6 Campi finiti e codici 2 - BCH
123
6.1
Polinomio primitivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
6.2
Campi finiti di Galois . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.3
Polinomio minimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
6.4
Codici di Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
6.5
Codici 2-BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
ii
INDICE
6.6
Schema di codifica per codici 2-BCH . . . . . . . . . . . . . . . . . . 141
7 Codici Reed Solomon
144
7.1
Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
7.2
Codici Reed Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
7.3
Correzione di un codice RS(2r , δ) . . . . . . . . . . . . . . . . . . . . 153
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 } è 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 )} è una distribuzione di probabilità sugli
P
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 è r (cioè |A| = r) si dice che l’alfabeto
genera un codice r-ario, in questi appunti (soprattutto dal capitolo 2) saranno per
lo più trattati casi in cui alfabeto è 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 è detta stringa e in essa possono
esistere caratteri ripetuti. Il numero di caratteri presenti in una stringa u è detto
lunghezza della stringa ed essa è 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 è la stringa nulla.
1
1.2 Schema di codifica
Si definisce codice C = {c1 , c2 , · · · , cn } un particolare sottoinsieme finito di A∗ , cioè
C ⊂ A∗ , gli elementi ci di C sono detti parole del codice. È possibile avere codici
con parole che hanno lunghezza differente oppure codici le cui parole hanno tutte la
stessa lunghezza, in tal caso il codice è detto a blocchi.
1.2
Schema di codifica
Se S0 = (S, P ) è una sorgente di un codice, si definisce schema di codifica per S0 la
coppia ordinata (C, f ), dove f : S → C è 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 quantità:
lc =
n
X
pi l(f (si )),
(1.1)
i=1
dove l(f (si )) è la lunghezza della parola del codice f (si ) che corrisponde all’evento
si di probabilità pi , tale probabilità assume il valore della probabilità legata alla
parola f (si ). Un codice C1 si dice più 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 “più conveniente”.
Esempio 1
2
Dato l’insieme S = {a, b, c, d} con P definita nel seguente modo: p(a) =
, p(b) =
17
2
9
4
, p(c) =
e p(d) =
. Sia C1 = {0, 11, 10, 100} il codice a lunghezza variabile e
17
17
17
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 è:
2
1.2 Schema di codifica
¯l1 =
n
X
pi l(f (si )) = 2 ·
i=1
2
2
9
4
41
+1·
+3·
+2·
= .
17
17
17
17
17
(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
X
i=1
pi l(f (si )) = 5 ·
2
2
9
4
40
+2·
+2·
+2·
= .
17
17
17
17
17
(1.3)
Si vede facilmente che il codice C2 è più efficiente del codice C1 .
L’esempio 1 mostra la particolarità che il codice C2 che contiene la parola più lunga
ha una lunghezza media minore, ciò è dovuto al fatto che in tale codice la funzione
di assegnazione associa la parola più lunga del codice alla probabilità minore.
Dall’esempio precedente si evince inoltre che quando si ha una conoscenza più dettagliata del sistema mediante la distribuzione di probabilità P , allora è conveniente
usare un codice a lunghezza variabile. L’esempio che segue mostra maggiormente
quando detto e in modo più 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 perchè esso può contenere al massimo 4 parole
(22 = 4), quindi è necessario utilizzare un codice a blocchi di 3 caratteri che permette di
rappresentare fino a 8 parole (23 = 8). È evidente che un codice a blocchi di lunghezza
tre ha sempre lunghezza media tre e ciò è indipendente dalla distribuzione P. Se invece
è 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 è:
lc =
Pn
i=1 pi l(f (si ))
= 1 · p(s1 ) + 3 · p(s2 ) + 3 · p(s3 ) + 3 · p(s4 ) + 3 · p(s5 ) =
3
1.3 Codici univocamente decifrabile e istantanei
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 uniforme è più conveniente usare un codice a lunghezza variabile perchè permette di
realizzare un codice più 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 verrà presentata nei capitoli seguenti che permette migliori possibilità di
individuazione e correzione di errore.
1.3
Codici univocamente decifrabile e istantanei
Prima di affrontare le problematiche inerenti alla correzione degli errori che possono
accadere in una trasmissione di un codice in questa sessione si affronterà 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 può essere interpretata in due modi differenti: essa
può contenere l’unica parola del codice 001 oppure la sequenza delle due parole 0
e 01. L’esempio precedente mostra un’ambiguità che può essere risolta definendo
dei codici particolari che permettono la lettura delle stringhe in maniera unica. È
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 è a lunghezza variabile si dice che esso è univocamente decifrabile
se, date le due parole c1 , c2 , ...., ck e d1 , d2 , ...., df , allora si ha che c1 , c2 , ....., ck =
d1 , d2 , ....., df se e solo se k = f e cl = dl per 1 ≤ l ≤ k.
4
1.3 Codici univocamente decifrabile e istantanei
Da tale proprietà segue che un codice univocamente decifrabile è un codice che
consente una lettura di una sua stringa da sinistra a destra senza generare ambiguità.
Esempio 3
Il C = {1, 10, 100} è un codice decifrabile perchè qualunque stringa formata dalle sue parole
è 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 è posto il simbolo “/” per evidenziare meglio
l’inizio di ogni parola contenuta in essa.
Un’altra proprietà legata alla lettura delle stringhe di un codice C è quella legata
alla necessità di riconoscere le parole del codice appena esse sono state ricevute, se
un codice C ha questa proprietà esso è detto codice istantaneo.
Esempio 4
Il codice C = {1, 01, 001} è un codice decifrabile e istantaneo, perchè 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 è ricevuta la parola 10, non
possiamo dire subito se siamo in presenza della parola 10 o se quello che abbiamo ricevuto
è solo una parte della parola 100 ciò si può affermare solo alla ricezione del carattere
successivo.
Tutti i codici che sono istantanei sono chiaramente decifrabili, ma non è detto
che un codice decifrabile sia istantaneo, ciò si deduce dalle considerazioni fatte
nell’esempio 4.
NB: Tutti i codici a blocchi sono decifrabili e istantanei.
I codici istantanei godono della proprietà del prefisso.
Proprietà 1 (del prefisso) In un codice istantaneo C nessuna parola è prefisso (è
posta all’inizio) di un’altra parola del codice, vale anche il viceversa.
5
2
1.3 Codici univocamente decifrabile e istantanei
La dimostrazione della proprietà 1 è immediata ed essa è importante in quanto
caratterizza i codici istantanei.
Per i codici istantanei si ha il seguente teorema di Kraft.
Teorema 1 (di Kraft) Se C è 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
X
1
≤ 1.
r li
i=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 lunghezza l1 , l2 , ...., ln . Sia L = max {l1 , l2 , ...., ln }, consideriamo la parola ci di lunghezza
li dove ci = x1 x2 .....xli , costruiamo una stringa di lunghezza L,
ui = x1 x2 .....xli yli +1 yli +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 possibilità di essere ripetuti. Il numero totale di differenti
stringhe di tipo ui è rL−li (ciò perchè 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 è istantaneo e gode della proprietà 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:
6
1.3 Codici univocamente decifrabile e istantanei
n
X
r
L−li
=
i=1
n
X
rL
i=1
r li
(1.6)
La quantità 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
X
rL
i=1
rli
= rL
n
n
X
X
1
1
L
≤
r
⇒
≤ 1.
li
li
r
r
i=1
i=1
(1.7)
La (1.7) verifica la disuguaglianza di Kraft e la prima parte del teorema è 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 è il numero delle
parole del nostro codice istantaneo C di lunghezza 1, allora è necessario che α1 <
r; se α2 è il numero di parole di lunghezza 2 di C, allora tale valore deve essere
minore del numero totale di parole distinte di lunghezza 2 che si possono formare
con un alfabeto di r simboli, inoltre poichè C è un codice istantaneo per esso vale
la proprietà del prefisso ed è quindi necessario eliminare tutte le parole di lunghezza
2 che hanno come prefisso le parole del codice di lunghezza 1, cioè deve valere la
seguente diseguaglianza:
α2 < r2 − α1 r.
Analogamente se α3 è il numero di parole del codice C con lunghezza 3 allora deve
valere la seguente disuguaglianza:
α3 < r3 − α1 r2 − α2 r.
7
(1.8)
1.3 Codici univocamente decifrabile e istantanei
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 è la massima lunghezza del codice C ( N.B. possono esistere lunghezze uguali
cioè li = lj ) e consideriamo tutti i possibili αi per 1 ≤ i ≤ m, il codice istantaneo
esiste se ognuna delle seguenti disuguaglianze è vera.
α1 < r
α1 r + α2 < r2
α1 r2 + α2 r + α3 < r3
(1.9)
.
.
α1 rm−1 + α2 rm−2 + ..... + αm ≤ rm
Vediamo cosa accade, ad esempio, se la terza disuguaglianza α1 r2 + α2 r + α3 < r3
è vera. Tutti i suoi termini sono positivi, quindi si ha che vale anche la seguente
disuguaglianza α1 r2 + α2 r < r3 ; è possibile dividere ambo i membri di quest’ultima
disuguaglianza per r, si ottiene α1 r + α2 < r2 , cioè anche la seconda disuguaglianza
delle (1.9) è vera, seguendo un analogo procedimento è facile verificare che anche la
prima disuguaglianza delle (1.9) è vera.
Sfruttando la metodologia usata nel precedente caso particolare si può affermare che
se una delle disuguaglianze della (1.9) è 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:
8
1.3 Codici univocamente decifrabile e istantanei
α1 α2
αm
+ 2 + ..... + m ≤ 1,
r
r
r
cioè
m
X
αi
i=1
n
X
1
=
≤ 1.
i
r
r li
i=1
Tale disuguaglianza è la disuguaglianza di Kraft ed è vera per le ipotesi del teorema,
quindi sono vere tutte le disuguaglianze che la precedono nella (1.9) e il teorema è
2
provato.
È importante notare che la seconda parte della dimostrazione del teorema precedente
afferma che se un codice verifica la disuguaglianza di Kraft non è detto che esso sia
istantaneo (vedi dall’esempio 6), ma afferma che se è verificata la disuguaglianza
di Kraft per i parametri l1 , l2 , ..., ln e r, allora è possibile costruire un codice
istantaneo r-ario con parole di lunghezza l1 , l2 , ...., ln mediante l’algoritmo presentato
dalla dimostrazione del teorema di Kraft.
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:
2
1
0
2
1
196
+ 2+ 3+ 4+ 5 =
≤1
3 3
3
3
3
243
(1.10)
La disuguaglianza è 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
9
1.3 Codici univocamente decifrabile e istantanei
parola di lunghezza 2 è c3 = 20, le parole di lunghezza 4 sono c4 = 2100, c5 = 2101, la
parola di lunghezza 5 è c6 = 21100. Il codice C = {0, 1, 20, 2100, 2101, 21100} è istantaneo
perchè verifica la proprietà del prefisso.
Esempio 6
Il codice C = {0, 11, 100, 110} verifica la diseguaglianza di Kraft infatti si ha che:
1
1
2
+
+
= 1,
2 22 23
ma tale codice non è istantaneo perchè non verifica la proprietà del prefisso.
Un codice istantaneo è anche decifrabile e dal teorema di Kraft è immediato ottenere
il seguente teorema.
Teorema 2 Se esistono n interi positivi l1 , l2 ,..., ln e r che verificano la disuguaglianza 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, cioè 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 .
Teorema 3 (di McMillan) Se C = {c1 , c2 , ....., cn } è un codice decifrabile, allora
vale la disuguaglianza di Kraft:
n
X
1
≤ 1.
li
r
i=1
(1.11)
Dim.
Consideriamo α1 , α2 ,..., αm il numero di parole del codice rispettivamente di lunghezza 1, 2,..., m. È facile verificare che il primo membro della disuguaglianza di
Kraft può scriversi anche nel seguente modo:
10
1.3 Codici univocamente decifrabile e istantanei
n
m
X
X
1
αj
=
.
l
i
r
rj
i=1
j=1
(1.12)
Eleviamo le due sommatorie ad un valore u, intero positivo:
Ã
n
X
1
r li
i=1
!u
=
à m
!u
X αj
j=1
rj
=
³α
α2
α m ´u
+ 2 + ··· + m .
r
r
r
1
(1.13)
Per maggiore chiarezza l’ultimo membro della (1.13) può essere scritto come il
prodotto di u sommatorie che rappresentano lo stesso termine:
³α
1
r
+
³α
α2
αm ´ ³ α1 α2
αm ´
α2
αm ´
1
+
·
·
·
+
·
+
+
·
·
·
+
·
·
·
+
+
·
·
·
+
.
r2
rm
r
r2
rm
r
r2
rm
(1.14)
Lo svolgimento di tale prodotto può essere svolto ed espresso come la somma dei
seguenti prodotti
X
i1 ,i2 ,··· ,iu
αi1 αi2 · · · αiu
.
ri1 +i2 +···+iu
(1.15)
La sommatoria della (1.15) è 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) può anche
essere scritta nel seguente modo
u·m
X
X
k=u i1 +i2 +....+iu
αi1 αi2 · · · αiu
,
k
r
=k
(1.16)
Nella (1.16) il valore minimo che può assumere k è u e il massimo è um e tale valore
all’interno della seconda sommatoria rimane sempre costante, quindi
u·m
X
1
rk
k=u
X
αi1 αi2 · · · αiu .
i1 +i2 +···+iu =k
Consideriamo adesso la quantità:
11
(1.17)
1.3 Codici univocamente decifrabile e istantanei
Nk =
X
αi1 αi2 · · · αiu .
(1.18)
i1 +i2 +···+iu =k
Le quantità α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 è rk ,
da cui segue che
Nk =
X
αi1 αi2 · · · αiu ≤ rk .
(1.19)
i1 +i2 +···+iu =k
Quindi la (1.17) può essere scritta nel seguente modo:
u·m
X
1
rk
k=u
X
i1 +i2 +....+iu
u·m
u·m
X
1 k X
αi1 αi1 ......αiu ≤
r =
1 = u · m − u ≤ u · m. (1.20)
rk
=k
k=u
k=u
In definitiva:
12
1.4 Codici ottimi
à n
!u
X 1
≤u·m
r li
i=1
Elevando primo e secondo membro per
(1.21)
1
si ha:
u
n
X
1
1
1
≤ (u) u (m) u
l
i
r
i=1
(1.22)
Per la scelta arbitraria di u si vede facilmente che per u → ∞ vale la disuguaglianza
di Kraft e il teorema è dimostrato.
1.4
2
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 è associata una sua
lunghezza media, consideriamo la lunghezza media minima ¯lmin tra tutti i codici
istantanei Cist associati a S0 , cioè
©
ª
¯lmin = min ¯lC | ∀ Cist ∈ C .
ist
(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 proprietà.
Proprietà 2 Se C è 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 ( cioè alla probabilità maggiore si associa la parola
di lunghezza minore)
13
1.4 Codici ottimi
Dim.
Supponiamo per assurdo che esiste un codice ottimo C per cui si ha che pi > pj e
li > lj . Costruiamo un codice C 0 ottenuto da C in cui alla parola ci è associata la
probabilità pj e alla parola cj è associata la probabilità pi mentre le altre parole ck
sono legate alla stessa probabilità pk del codice C. Calcoliamo le lunghezze medie
rispettivamente dei codici C e C 0 e consideriamo la loro differenza.
l¯C =
n
X
pk lk + pi li + pj lj ;
(1.24)
pk lk + pi lj + pj li ;
(1.25)
k=16=i6=j
lC¯ 0 =
n
X
k=16=i6=j
lC¯ 0 − l¯C = pi lj + pj li − pi li − pj lj .
(1.26)
Dopo facili calcoli si ottiene.
lC¯ 0 − l¯C = 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¯ 0 − l¯C < 0
cioè lC¯ 0 < l¯C . Si è quindi determinato un codice C 0 che è istantaneo, ma ha lunghezza
media minore della lunghezza media del codice ottimo C e ciò è assurdo.
2
Proprietà 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 .
Dim.
Supponiamo per assurdo che esiste un codice ottimo C con una sola parola di
lunghezza lm . Calcoliamo la sua lunghezza media
l¯C =
m−1
X
Pk lk + Pm lm
k=1
14
(1.28)
1.4 Codici ottimi
Consideriamo l’unica parola cm ∈ C di lunghezza lm e consideriamo il codice C 0
ottenuto da C modificando soltanto cm mediante l’eliminazione dell’ultimo carattere.
Il codice C 0 è un codice istantaneo perchè gode della proprietà del prefisso e la sua
lunghezza media è:
lC¯ 0 =
m−1
X
pk lk + pm (lm − 1) .
(1.29)
k=1
È evidente che lC¯ 0 < l¯C . Si è determinato ancora una volta un codice istantaneo con
lunghezza media minore della lunghezza media del codice ottimo C e ciò è assurdo.
2
Proprietà 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 proprietà 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 0 che gode della proprietà del prefisso (nessuna sua parola è prefisso di un’altra) e
la sua lunghezza media è minore della lunghezza media del codice ottimo C.
1.4.1
2
Algoritmo di Huffman
In questa sessione è presentato l’ Algoritmo di Huffman che consente di individuare un codice ottimo data una distribuzione di probabilità P . Tale algoritmo è
valido per codici r-ari, ma qui sarà presentata la procedura che riguarda solo i codici
binari.
15
1.4 Codici ottimi
Algoritmo di Huffman
1. Si ordina la distribuzione di probabilità P 0 = {P10 , P20 , · · · , Pn0 } in modo tale
che le probabiltà hanno un ordine decrescente secondo gli indici, cioè Pi0 ≤ Pj0
con i > j.
0
2. Le due probabilità di valore inferiore, cioè Pn0 e Pn−1
si sommano, si ottie0
0∗
= Pn0 + Pn−1
. Si considera la distribuzione di probabilità
ne il valore Pn−1
©
ª
1
P 1 = P11 , P21 , · · · , Pn−1
in cui sono presenti tutte le probabilità di P 0 con
0
0∗
esclusione dei valori Pn0 e Pn−1
al posto dei quali si è inserito il valore Pn−1
.
La distribuzione di probabilità P 1 è anch’essa ordinata in ordine decrescente
0∗
secondo gli indici e si ha che Pi1 = Pn−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
j−1∗
determina una probabilità Pn−j
data dalla somma delle due probabilità di
valore minore.
4. Si ottiene la distribuzione di probabilità P n−2 costituita da soli due valori.
5. Si associano alle probabilità di P n−2 le parole 1 e 0 (la scelta è arbitraria),
quindi alla distribuzione di probabilità P n−2 è associato il codice Cn−2 .
6. Una delle probabilità di P n−2 è del tipo Pin−2 = P2n−3∗ = P2n−3 + P3n−3 con
j−1∗
i = 1, 2 (cioè del tipo Pn−j
con j = n − 2), se ad essa nel passo precedente
è stato associato il carattere k ∈ {0, 1}, allora nella distribuzione P n−3 alle
probabilità P2n−3 e P3n−3 si associano le parole k1 e k0 (la scelta è 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 probabilità di P 0
definiscono un codice ottimo binario C0 e l’algoritmo è concluso.
16
1.4 Codici ottimi
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 probabilità P 0 = {0.35, 0.20, 0.20, 0.15, 0.10}, le due probabilità
di valore minore sono 0.10 e 0.15, la loro somma è 0.25∗ , si ottiene nuova distribuzione
di probabilità 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 probabilità 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 probabilità P 0 è C = {01, 11, 10, 001, 000}.
È necessario adesso provare che il codice ottenuto dall’algoritmo di Huffmann è un
codice ottimo, ciò è ottenuto dal teorema seguente.
Teorema 4 Se Ci è un codice ottimo ottenuto dall’algoritmo di Huffman, allora
anche Ci−1 è un codice ottimo. L’algoritmo di Huffmann genera un codice ottimo.
17
1.4 Codici ottimi
Dim.
All’ultima distribuzione di probabilità che si ottiene eseguendo l’algoritmo di Huffman è associato il codice Cn−2 = {0, 1} che è senz’altro ottimo, 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 è provato il teorema.
©
ª
Consideriamo il codice ottimo Ci = c1 , c2 , ...., c?m−1 , sia L = l(cm−1 ). Applichiamo
l’algoritmo di Huffman al codice Ci si ottiene il codice Ci−1 = {c1 , c2 , ....., cm−1 0, cm−1 1}
e calcoliamo le lunghezze medie dei codici Ci e Ci−1 :
¯li =
m−2
X
pk lk + (pm−1 + pm ) L;
(1.30)
k=1
¯li−1 =
m−2
X
pk lk + pm−1 (L + 1) + pm (L + 1) .
(1.31)
k=1
Ricordiamo che nel codice Ci−1 le ultime due 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
0
0
ottimo Ci−1
, associato alla distribuzione di probabilità di Ci−1 , tale che ¯li−1
< ¯li−1 .
0
Se Ci−1
è ottimo, per le proprietà 2, 3 e 4, esisteranno due parole di lunghezza
massima ed aventi i primi lm − 1 caratteri uguali e associate alle probabilità pm e
ª
©
0
= c01 , c02 , ...., c0m−1 0, c0m−1 1 . Applicando l’algoritmo di Huffman in
pm−1 , cioè Ci−1
ª
©
0?
senso opposto si determina un nuovo codice Ci0 = c01 , c02 , ...., cm−1
. Anche per i due
0
codici Ci0 e Ci−1
vale la relazione:
¯l0 = ¯l0 + pm−1 + pm .
i
i−1
18
(1.33)
1.5 La funzione entropia
0
Poichè si è supposto che Ci−1
è ottimo mentre per assurdo Ci−1 non lo è allora deve
valere la seguente disuguaglianza:
¯l0 < ¯li−1
i−1
(1.34)
Se ciò è vero confrontando le equazioni (1.32) e (1.33) si ha che vale la seguente
disuguaglianza.
¯l0 < ¯li
i
(1.35)
Ciò implica che Ci non è ottimo, questo è assurdo e il teorema è provato.
1.5
2
La funzione entropia
Nell’esempio 1 si è vista l’importanza della conoscenza della distribuzione delle
probabilità, da qui nasce l’esigenza di determinare una funzione che permetta di
“misurare” la conoscenza del sistema mediante la conoscenza della sua distribuzione
di probabilità. Tale funzione H è la funzione entropia che è differente dalla grandezza 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 è possibile associare una distribuzione di probabilità P =
{p1 , p2 , ..., pq }.
La funzione entropia deve soddisfare le seguenti tre proprietà:
1. Se tutte le probabilità di P sono uguali cioè pi =
1
allora H è una funzione
q
crescente, cioè se q < q 0 allora si ha:
µ
H
1 1
1
, , ...,
q q
q
¶
µ
<H
19
1
1 1
, 0 , ..., 0
0
q q
q
¶
1.5 La funzione entropia
.
Nella realtà questa proprietà esprime che maggiore è il numero di eventi q
maggiore è l’incertezza legata agli eventi.
2. H è una funzione continua cioè a piccole variazioni di probabilità corrispondono
piccole variazioni di H.
3. Vale il principio che un esperimento può essere scomposto in una successione
di esperimenti successivi.
Esempio 7
Diamo per quest’ultima proprietà un esempio di un esperimento che è rappresentato gra1 1 1
ficamente nella seguente figura. Esso ha una distribuzione di probabilità P = { , , } e
2 3 6
1 1
0
può essere scomposto nella successione dei due esperimenti di probabilità P = { , } e
2 2
2 1
P 00 = { , }.
3 3
Tale scomposizione può essere rappresentata mediante la funzione entropia nel seguente
modo:
µ
H
1 1 1
, ,
2 3 6
¶
µ
=H
1 1
,
2 2
20
¶
1
+ H
2
µ
2 1
,
3 3
¶
.
1.5 La funzione entropia
Teorema 5 La sola funzione che verifica le tre proprietà 1, 2 e 3 è:
H(p1 , p2 , · · · , pq ) = −c
q
X
pi logb pi
(b > 1)
(1.36)
i=1
con c costante positiva.
Dim.
Poniamo
µ
H
1
1
,··· ,
q
q
¶
= f (q).
(1.37)
Supponiamo di avere sm eventi legati ad una determinata variabile random. Poichè
deve valere la terza proprietà, sm può essere scomposto in m sequenze di s eventi,
cioè:
f (sm ) = mf (s).
(1.38)
Fissati t e n interi positivi è sempre possibile determinare un m tale che:
2m ≤ tn < 2m+1 .
(1.39)
Passando ai logaritmi in base b e sfruttando le loro proprietà 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
2◦
z }| {
m logb t m + 1
≤
<
.
n
|n{z } logb 2
1◦
21
(1.42)
1.5 La funzione entropia
Poichè f (q), per le proprietà 1 e 2, è una funzione continua e crescente si ha che
applicandola alle disuguaglianze della (1.39) esse continuano a sussistere, cioè:
f (2m ) ≤ f (tn ) < f (2m+1 ),
(1.43)
dividendo per nf (2):
2◦
z }| {
m f (t) m + 1
≤
<
.
n
|n{z } f (2)
(1.44)
1◦
◦
Moltiplicando la 1 disuguaglianza della (1.44) per −1 si ottiene:
−
f (t)
m
≤− .
f (2)
n
(1.45)
Sommando la (1.45) con la 2◦ disuguaglianza della (1.42) si ha:
logb t
f (t)
1
−
< .
logb 2 f (2)
n
(1.46)
Allo stesso modo, moltiplicando la 2◦ disuguaglianza della (1.44) per −1 si ottiene:
−
f (t)
m 1
>− − .
f (2)
n
n
(1.47)
Sommando la (1.47) con la 1◦ disuguaglianza della (1.42) si ha:
logb t
f (t)
1
−
>− ,
logb 2 f (2)
n
(1.48)
¯
¯
¯ logb t
¯ 1
1
logb t
f (t)
1
f
(t)
¯<
− <
−
< ⇒ ¯¯
−
n
logb 2 f (2)
n
logb 2 f (2) ¯ n
(1.49)
da cui si ricava:
e per n → ∞ si ha:
¯
¯
¯ logb t
f (t) ¯¯
logb t
f (t)
log t
¯
lim ¯
−
=0⇒
=
⇒ f (t) = f (2) b = c logb t.
¯
n→∞ logb 2
f (2)
logb 2
f (2)
logb 2
(1.50)
Consideriamo adesso una distribuzione di probabilità con probabilità razionali:
ki
pi = P
j
kj
con ki
intero ∀i e
X
i
22
k
Pi
j
kj
=1
(1.51)
1.5 La funzione entropia
Scomponiamo l’esperimento in una successione di due eventi mediante le distribuzioni di probabilità rappresentate nella figura seguente.
È possibile allora scrivere:
µ
¶
1
1
1
H P , P ,··· , P
= H (p1 , p2 , ..., pm ) + p1 c logb k1 + p2 c logb k2 + · · ·
ki
ki
ki
P
+ pm c logb km = H (p1 , p2 , ..., pm ) + c pi logb ki .
Dopo semplici calcoli si ha:
µ
¶
P
1
1
1
H (p1 , p2 , ..., pm ) = H P , P , ..., P
− c i pi logb ki =
i ki
i ki
i ki
X
P ki
P
P
P
−c
pi logb ki =
c logb i ki − c i pi logb ki = c logb j kj · i P
j kj
i
X
X
X
X
X
ki
c
pi logb
kj − c
pi logb ki = −c
pi logb P
= −c
pi log pi .
k
j
i
i
j
i
i
i
La condizione necessaria del teorema è provata.
P
Il viceversa se Hb (p1 , p2 , · · · , pm ) = −c m
i=1 pi logb pi allora si ha che le proprietà
sono tutte verificate e il teorema è provato.
2
Dal teorema precedente si ha che per un sistema che ha una distribuzione di probabilità P = {p1 , p2 , · · · , pm } la funzione entropia è definita come la quantità:
Hb (p1 , p2 , · · · , pm ) = −
m
X
i=1
23
pi logb pi .
1.5 La funzione entropia
Dove la costante c è stata normalizzata a 1. Se il valore di b in H è 2 allora l’entropia
prende il nome di entropia binaria.
1.5.1
Proprietà della funzione entropia
Siano X e Y due variabili random e sia p(xi , yj ) la probabilità congiunta delle due
variabili, allora l’entropia congiunta a X e Y è definita come:
H(X, Y ) =
X
p(xi , yj ) log
i,j
1
.
p(xi , yj )
(1.52)
Enunciamo il seguente lemma omettendo la dimostrazione.
Lemma 1 Sia {p1 , p2 , · · · , pm } una distribuzione di probabilità e sia {q1 , q2 , ..., qm }
P
qi ≤ 1, allora si ha che:
una sequenza di numeri reali con 0 ≤ qi ≤ 1 e
X
pi log
X
1
1
≤
pi log
pi
qi
(1.53)
Consideriamo adesso una sequenza di teoremi che permettono di evidenziare alcune
proprietà della funzione entropia.
Teorema 6 Se X è una variabile aleatoria si ha che:
0 ≤ H(X) ≤ log q
(1.54)
Dim.
Chiaramente H(X) ≥ 0. Per definizione di entropia si può scrivere:
H(X) =
q
X
i=1
q
q
X
1
1 X
pi log ≤
pi log 1 =
pi log q
pi
q
i=1
i=1
(1.55)
da cui:
H(X) ≤ log q
(1.56)
2
24
1.5 La funzione entropia
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 probabilità congiunta ad X e Y e sommo solo
secondo l’indice legato a una variabile random (cioè si varia i lasciando fissato j e
viceversa) si ha:
X
p(xi , yj ) = p(xi ),
(1.58)
p(xi , yj ) = p(yj ).
(1.59)
j
X
i
quindi:
X
1
1
+
p(yj ) log
=
p(x
)
p(y
)
i
j
i
j
X
P
1
1
= i,j p(xi , yj ) log
+
p(xi , yj ) log
=
p(xi )
p(yj )
i,j
X
P
1
1
= i,j p(xi , yj ) log
≥
p(xi , yj ) log
= H(X, Y ).
p(xi )p(yj )
p(x
,
y
)
i
j
i,j
H(X) + H(Y ) =
X
p(xi ) log
Il teorema è provato.
2
Siano X e Y due variabili random e p(yj |xi ) la distribuzione di probabilità dell’evento
Y condizionato dall’evento X, definiamo l’entropia condizionata nel seguente
modo:
H(X|Y ) =
X
p(yj )p(xi |yj ) log
i,j
X
1
=
p(yj )H(X|yj )
p(xi |yj )
j
(1.60)
Teorema 8 Se X e Y sono due variabili random, allora:
H(X|Y ) = H(X, Y ) − H(Y ).
25
(1.61)
1.5 La funzione entropia
Dim.
Dalla precedente definizione abbiamo:
H(X|Y ) =
X
p(yj )p(xi |yj ) log
i,j
1
.
p(xi |yj )
(1.62)
Ricordando che:
p(xi |yj ) =
p(xi , yj )
.
p(yj )
(1.63)
possiamo scrivere:
X
X
p(yj )
1
H(X|Y ) =
p(xi , yj ) log
=
p(xi , yj ) log
−
p(xi , yj )
p(xi , yj )
i,j
i,j
X
X
1
1
p(xi , yj ) log
= H(X, Y ) −
p(yj ) log
= H(X, Y ) − H(Y ).
p(y
)
p(y
)
j
j
i,j
j
Il teorema è provato.
2
Consideriamo l’insieme dei possibili segnali che si presentano in ingresso ad un ricevitore E = {a1 , ....., am }, supponiamo di avere associata ad esso una distribuzione
di probabilità p(ai ) con 1 ≤ i ≤ m. Possiamo allora scrivere l’entropia in ingresso
come:
H(E) = −
X
p(ai ) log p(ai ) =
i
X
p(ai ) log
i
1
p(ai )
(1.64)
Siano U = {u1 , ..., um } l’insieme dei segnali prodotti dalla sorgente in trasmissione,
possiamo definire informazione la quantità:
I(E, U ) = H(E) − H(E|U ).
(1.65)
Da essa è possibile definire capacità del canale come la quantità
C = maxE I(E, U ).
(1.66)
Essa è legata alla determinazione di una distribuzione di probabilità E tale che
rende massima I(E, U ).
26
Capitolo 2
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 utilità.
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, astronavi o shuttle, nella realtà fisica del nostro universo può 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 può
essere individuato dal mezzo trasmissivo su cui vengono inviate informazioni in una
normale comunicazione telefonica o un in invio dati tra due sistemi informatici collegati, il canale può anche essere costituito dallo spazio in cui si propagano onde
elettromagnetiche che trasportano informazioni. In ogni canale esiste sempre la presenza di rumore che compromette la trasmissione. Tale rumore si può legare a
27
2.1 Introduzione
interferenze elettromagnetiche (disturbi radio, attività 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 informazioni su un “supporto”, in questo caso il rumore può essere legato alla non perfetta
condizione del supporto (ad esmpio sporcizia, presenza di graffi in CD o DVD o
invecchiamento del supporto) o a difficoltà 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 probabilià costante. In particolare come
detto precedentemente l’alfabeto usato è del tipo A = {0, 1} e ogni suo carattere è
chiamato bit. Ad ogni singolo bit, come rappresentato nella figura 2.1, può essere
associata una probabilità p che esprime la probabilità che esso venga ricevuto correttamente, chiaramente la probabilità che un bit non sia trasmesso correttamente
è 1 − p.
La probabilità p è chiaramente legata al sistema trasmissivo ed essa prende il nome
di efficienza del canale, negli attuali sistemi trasmissivi essa supera il valore 0.97
cioè può assumere valori molto alti, ma è evidente che in un numero di bits molto
alto la probabilità che l’informazione venga inficiata da errore non è trascurabile.
Un codice C1 , con efficienza p1 , si dice più efficiente del codice C2 , di efficienza p2 ,
se si ha che p1 > p2 .
Varie sono state nel tempo le tecniche di controllo e/o correzione di errore, alcune
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
28
2.1 Introduzione
0
0
P
P
P
1
-1
-1
1
P
Figura 2.1: Efficienza di canale
di valore “1”. Il codice C = {111, 011, 001, 100, 110, 010} con l’aggiunta del bit di
parità diventa C 0 = {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 è una
parola del codice.
Un’altra tecnica di controllo e correzione di errore, detta di ridondanza, è quella
di trasmettere più volte la stessa parola e, in ricezione, di controllare se anche la
sequenza di ricezione ha sempre la stessa ripetizione, se ciò non avviene allora si
effettua la correzione scegliendo nella sequenza la parola del codice che è stata ripetuta più volte. Questa tecnica contrariamente alla precedente oltre ad individuare
l’errore permette anche di correggerlo, inoltre maggiore è il numero di ripetizioni di
una stessa parola in una sequenza, maggiore è la probabilità che la correzione sia
esatta. Esiste però un importante inconveniente in tale tecnica, essa infatti non permette un numero elevato di ripetizioni dato che maggiore è il loro numero, minore
è la velocità di trasmissione di informazione.
29
2.2 Probabilità e distanza
2.2
Probabilità e distanza
Il problema della correzione delle parole del codice è essenzialmente legato al concetto
di probabilità. La probabilità che la parola v, avente lunghezza n e appartenente
al codice a blocchi C di efficienza p, sia trasmessa correttamente è pn . Supponiamo
adesso di trasmettere la parola v ∈ C, ma di ricevere la parola w ∈
/ C, come risolvere
il problema della correzione di w?
È necessario definire una funzione che determini la probabilità che la parola v ∈ C
sia trasmessa e la parola w ∈
/ C sia ricevuta. In generale tale funzione può essere
definita, indipendentemente dal concetto di parola inviata e ricevuta, nel seguente
modo:
φ : K n × K n → [0, 1],
dove K n 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) è la probabilità che la parola v ∈ C è stata inviata e w ricevuta, allora
si ha:
Φ (v, w) = pn−d (1 − p)d ,
(2.1)
dove d è il numero di bits differenti tra le parole v e w, n è 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 è la probabilità che un singolo bit giunga in
maniera errata. La quantità d è chiamata distanza tra le parole v e w e si indica
con la simbologia d (v, w). Chiaramente non è difficile provare che tra due parole di
lunghezza n vale la seguente uguaglianza d (v, w) = d (w, v).
30
2.2 Probabilità e distanza
Esempio 1
Sia C un codice a blocchi di lunghezza 5. Per ogni parola v ∈ C la probabilità che v sia
ricevuta correttamente (cioè w = v) è:
Φ(v, v) = p5
Se invece la parola inviata è v = 10011 e quella ricevuta è w = 11001, allora la distanza
tra v e w è 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 appartiene al codice C. Tale tecnica di correzione di errore è basata sull’individuazione
della parola v 0 ∈ C tale che ad essa è associata la probabilità massima rispetto alla
parola ricevuta w mediante la funzione Φ cioè:
Φ (v 0 , 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 0 tale che la funzione Φ è massima al variare di v in C, fissata
w. Tale parola v 0 si sostituisce a w.
È possibile che in tale tecnica si abbia un insieme di parole del codice che hanno
tutte la stessa probabilità massima, in tal caso si genera un’ambiguità, in seguito
vedremo come affrontare tale evenienza.
Consideriamo adesso un risultato che permette di associare il concetto di probabilità
definito dalla funzione Φ al concetto di distanza tra due parole.
31
2.2 Probabilità e distanza
1
< p < 1 e siano v1 e
2
v2 due parole del codice C. Se d1 è la distanza tra v1 e la parola ricevuta w e d2 è
Teorema 9 Sia C un codice a blocchi di lunghezza n, con
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;
µ
Poichè per le ipotesi
p
1−p
¶d2 −d1
< 1.
1
< p < 1 si ha che p > 1 − p ovvero:
2
p
> 1,
1−p
32
(2.4)
2.2 Probabilità e distanza
allora la (2.4) è vera se e solo se l’esponente è negativo cioè se:
d2 − d1 < 0
⇒
d2 < d1 ,
(2.5)
e il teorema è provato.
2
Il teorema precedente assume una rilevanza fondamentale in quanto permette di
abbandonare il concetto di probabilità 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 0 ∈ C che ha distanza minima da w e si sostituisce a w, ciò equivale al fatto
che la funzione Φ(v, w), fissata w, assume valore massimo per v 0 ∈ 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 è c3 = 10100, tale parola è quella che
corregge w ed è quella che tra tutte le parole del codice C ha la massima probabilità di
essere stata inviata in trasmissione.
33
2.3 Peso ed errore
2.3
Peso ed errore
Si è precedentemente detto che l’alfabeto dei codici a blocchi è K = {0, 1}, ma tale
insieme di caratteri è 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 proprietà di campo.
L’insieme K n , come precedentemente detto, è l’insieme di tutte le possibili differenti
parole binarie di lunghezza n, tale insieme è finito ed ha cardinalità uguale a 2n ,
perchè ogni singola componente di una parola di K n può assumere valori “0” o “1”.
L’insieme K n può 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 K n mediante i concetti di spazio
vettoriale introdotti nei corsi base di algebra lineare. La somma tra le componenti
corrispondenti di due parole è data dall’operazione di somma definita su K. Un
esempio di somma tra le due parole (101) e (111) è: (101) + (111) = (010).
È importante notare che la somma di due parole uguali è uguale alla parola che
possiede in tutte le sue componenti bits di valore “0”, tale parola è detta nulla e si
34
2.3 Peso ed errore
indica con il simbolo 0, cioè ∀v ∈ K n si ha che v + v = 0. Tale proprietà permette
di capire che la parola opposta di una qualunque parola v ∈ K n è la parola stessa.
Si ha inoltre che vale la seguente proprietà.
Proprietà 5 Se v + w = 0, allora si ha che v = w.
2
Si è preferito evidenziare tale proprietà perchè molto spesso chi comincia a studiare
questi argomenti commette l’errore di scrivere v = −w, ciò è sbagliato!!!
Infatti se vale l’eguaglianza v + w = 0, allora vale anche v + w + w = w che è
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 è 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 può per certi versi sembrare “strano”,
infatti nella sua definizione si capisce facilmente che per determinare u non solo è
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 ∈ K n , 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 ∈ K 6 è uguale a tre, cioè 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, ciò comporta che la parola u ha peso uguale alla distanza tra v e w
cioè:
d(v, w) = wt(u).
(2.7)
Se d è la distanza tra le parole v e w, allora l’equazione (2.1) si può 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 K 6 , si ha che u = v + w = 100100 allora segue
che: d(v, w) = wt(v + w) = 2.
Di seguito sono enunciate una serie di proprietà legate ai concetti di distanza e di
peso.
Proprietà 6 Date due parole v e w di K n allora valgono le seguenti quattro proprietà.
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
4. d(av, aw) = a · d(v, w)
a ∈ K;
con
a ∈ K.
2
La prima disuguaglianza delle precedenti è 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 0 , v 00 ), v 0 , v 00 ∈ C} = min {wt(v 0 + v 00 ), v 0 , v 00 ∈ C} .
(2.9)
Tale parametro, se non vi è alcuna ambiguità legata al codice C, si denoterà con
la semplice simbologia d. La distanza d è uno dei tre parametri che, in seguito,
caratterizza un codice a blocchi.
2.4
Prime tecniche di codifica
La tecnica di decodifica che è presentata in questa sessione è basata sulla ricerca tra
tutte parole del codice C della parola che, in termini di distanza, è la più vicina alla
parola che è stata ricevuta e che non appartiene al codice.
Tale tecnica prende il nome di MLD dall’inglese “Maximum Likelihood Decoding”
cioè massima probabiltà 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
2.4 Prime tecniche di codifica
Esempio 4
Sia il codice di lunghezza 3, C = {000, 111}. Consideriamo tutte le differenti parole di K 3 ,
esse sono 23 e K 3 = {000, 001, 010, 011, 100, 101, 110, 111}.
Parola ri-
Errore
Errore
cevuta
000 + w
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 lunghezza
tre che possono essere ricevute, cioè w, la seconda e terza colonna rappresentano la somma
della singola parola del codice C e la parola w cioè tali colonne rappresentano gli errori 000+
w e 111 + w. L’ultima colonna individua la parola di C che “correggerà” w. Supponiamo
che la parola 001 è 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,
cioè 000 corrispondente all’errore 001. Nella tabella gli errori di peso minore su ogni riga
vengono evidenziati mediante asterisco.
Nell’esempio 4 è importante notare che che la scelta della parola di peso minore è
dovuta al fatto che d(v, w) = wt(v +w) e a quanto affermato dal teorema 9, date due
38
2.4 Prime tecniche di codifica
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 probabilità di essere stata inviata rispetto alla parola
v2 .
Il codice dell’esempio 4, come già detto, è estremamente semplice ed inoltre per
ogni parola ricevuta non possiede alcuna ambiguità, cioè su ogni parola ricevuta w
è sempre possibile fare una correzione. In codici più complessi può 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 più 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 più parole del codice
con lo stesso errore minimo, allora si richiede la ritrasmissione del messaggio.
La ritrasmissione del messaggio può essere anche chiesta quando si riceve una
parola w “troppo” distante da tutte le parole del codice, il“troppo” è legato al
tipo di strategia che si vuole adottare in correzione.
39
2.4 Prime tecniche di codifica
Esempio 4
Parola ri-
Errore
Errore
Errore
cevuta
0000 + w
1010 + w
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 è 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
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 ciò 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 u0 = 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 u0 .
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 può essere individuato da C.
41
2.6 Correzione di errore
Dim.
Consideriamo un errore u 6= 0 il cui peso è wt(u) ≤ d − 1 con d 6= 1, ∀ v ∈ C si ha
che:
d(v, v + u) = wt(v + v + u) = wt(u) ≤ d − 1
(2.10)
Poichè C ha distanza d segue che prese due generiche parole v 0 ∈ C e v 00 ∈ C allora
d(v 0 , v 00 ) ≥ d, quindi se v ∈ C e vale la (2.10) allora si ha che v + u ∈
/ C. Vista
l’arbitrarietà della scelta di v la prima parte del teorema è provata.
Se d è la distanza del codice allora esistono almeno due parole c0 ∈ C e c00 ∈ C
tale che d(c0 , c00 ) = d. Sia u = c0 + c00 è evidente che wt(u) = d e c00 = u + c0 ∈ C.
Si è trovato un errore u con peso d che non viene individuato da C e il teorema è
provato.
2
Se d è la distanza di un codice C, allora C si dirà d - 1 error-detecting.
Esempio 6
Il codice C = {000, 111} ha distanza d = 3 ed è 2-error-detecting.
Esempio 7
Il codice C = {001, 101, 110} ha distanza d = 1. Poichè d − 1 = 0 non troveremo errori.
2.6
Correzione di errore
In questa sessione è 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)
42
(2.11)
2.6 Correzione di errore
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 è 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.
In questo caso C non corregge l’errore u = 110 perchè la parola che ha distanza minore
non è quella inviata.
Dato x ∈ R, indichiamo con bxc il massimo intero minore o uguale a x. Ad esempio:
¹ º
¹ º
5
1
= 2; b3c = 3;
= 0.
2
2
Anche per questo tipo di errori cerchiamo di individuare gli errori che sono corretti
da un codice C.
43
2.6 Correzione di errore
Teorema 11 Sia C un codice di lunghezza n e distanza d. Allora esso corregge tutti
¹
º
d−1
gli errori di peso minore o uguale a
. Esiste almeno un errore di peso pari
2
¹
º
d−1
a 1+
che C non corregge.
2
Dim.
º
d−1
e due arbitrarie parole v e w in C con
Sia u un errore con peso wt(u) ≤
2
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)
quindi,
d ≥ 2wt(u) + 1.
(2.15)
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 (2.13) si ha:
Dalla scelta arbitraria di v e w si ha che:
44
2.6 Correzione di errore
d(w, v + u) > d(v, v + u).
(2.19)
La prima parte del teorema è provata.
Poichè la distanza di C è d allora esistono almeno due parole v e w appartenenti a
C tali che:
d(v, w) = d
(2.20)
º
(d − 1)
Consideriamo la parola v + w ed in essa cambiamo un numero 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 sarà:
½
¹
d−1
d− d−1−
2
º¾
¹
º
d−1
=
+ 1.
2
Consideriamo adesso d(v, v + u) e d(w, v + u):
¹
º
d−1
d(v, v + u) = wt(u) =
+1
2
½
¹
º¾
d−1
d(w, v + u) = wt(w + v + u) = d(v + w, u) = d − 1 +
2
(2.21)
(2.22)
Se la distanza d è dispari, allora si può scrivere come d = 2t + 1 e si ha che:
d(v, v + u) = 1 +
2t
=1+t
2
(2.23)
e
d(w, v + u) = 2t + 1 − (1 + t) = t
(2.24)
d(v, v + u) > d(w, v + u)
(2.25)
Pertanto:
in contraddizione con la (2.19).
45
2.6 Correzione di errore
Se la distanza d è pari essa può scriversi come d = 2t. In tal caso:
¹
º
¹
º
1
2t − 1
d(v, v + u) = 1 +
=1+ t−
=1+t−1=t
2
2
(2.26)
d(w, v + u) = 2t − t = t
(2.27)
d(v, v + u) = d(w, v + u)
(2.28)
e
Pertanto:
anch’essa in contraddizione con la (2.19), quindi il codice C non corregge l’errore u
e il teorema è completamente provato.
2
¹
º
d−1
Se d è la distanza di un codice C, allora C si dirà
-correttore, ad esempio
2
un codice di distanza sette è un codice 3-correttore.
46
Capitolo 3
Codici lineari
3.1
Introduzione
In questa sessione è 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 è ancora una parola di C, cioè:
∀v, w ∈ C
⇒
v + w ∈ C.
Se K n è un insieme di parole di lunghezza n che ha le proprietà di spazio vettoriale
sul campo K = {0, 1} mediante le operazioni di somma e prodotto definite nel
capitolo precedente, allora un codice lineare C può intendersi come un sottospazio
di K n , 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 più semplici rispetto a quelli che si basano sulle
definizioni. Nel teorema seguente si vede come è 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 è la più piccola distanza tra tutte
le parole del codice, di peso maggiore di zero, e la parola nulla.
Dim.
Consideriamo la quantità t = min {d(0, c), c ∈ C}. Supponiamo per assurdo che la
distanza del codice d < t, allora esistono almeno due parole v 0 e v 00 appartenenti a
C per cui si ha:
d(v 0 , v 00 ) = d.
Consideriamo la parola c = v 0 + v 00 , essa apparterrà a C ed inoltre wt(c) = d > 0,
quindi:
wt(c) = d(0, c) = d.
Ciò vuol dire che:
d ∈ {d(0, c), c ∈ C}
⇒
d ≥ t.
Si è determinato un assurdo in quanto t è il minimo di tale insieme e contemporaneamente 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 è d = 1.
48
3.2 Prodotto scalare in K n
3.2
Prodotto scalare in K n
In K n è possibile introdurre il prodotto scalare canonico definito nei corsi di algebra
lineare. Se v e w sono due parole di K n , 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 è 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 ∈ K n : v · w = 0 ∀w ∈ C} ,
cioè l’insieme delle parole di K n che sono ortogonali ad ogni parola di C. Tale
insieme è anch’esso un codice lineare, infatti se c0 e c00 sono due arbitrarie parole
di C ⊥ e v è una generica parola di C, allora si ha che essa è ortogonale alla parola
somma c0 + c00 , cioè:
(c0 + c00 ) · v = c0 · v + c00 · v = 0,
ciò vuol dire che prese due parole arbitrarie di C ⊥ allora la loro somma appartiene
a C ⊥ e C-ortogonale è un codice lineare.
Un insieme di parole di C, B = {c1 , c2 , · · · , ck }, è un insieme di generatori di C se
per qualunque v ∈ C è possibile scrivere:
v = a1 c1 + a2 c2 + ... + ak ck .
È evidente che se l’equazione vettoriale
a1 c1 + a2 c2 + ... + ak ck = 0,
49
3.3 Matrice generatrice
è 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, cioè il numero
di elementi in B è 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 è soltanto enunciato.
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 facilmente essere trovati in qualunque testo di algebra lineare.
3.3
Matrice generatrice
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.


c
 1 


 c2 




.
G =
.






 . 


ck
50
(3.2)
3.3 Matrice generatrice
La matrice (3.2) è detta matrice generatrice, essa si può 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 corsi 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 è 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 seconda riga l’ 1-leading non ha nessun zero a sinistra in quanto primo elemento della riga,
ma rientra nella sua definizione perchè appartiene all’ultima riga di A.
La matrice B contiene due colonne leading corrispondenti ai caratteri “1” sottosegnati.


A=

00011000

 0 1 0 



B=
 0 0 1 .


1 0 1
;
10011111
Una matrice A è 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 è ridotta parzialmente,
allora essa può essere ridotta mediante le operazioni elementari:
1. Ri ⇒ Rj ;
51
3.3 Matrice generatrice
2. Ri ⇒ Ri + Rj .
Esempio 3
La matrice A è una matrice ridotta parzialmente.

 0 1

 0 0

A =
 0 0


0 0

1 1 0 

1 0 0 

.
0 0 0 


0 0 0
Esempio 4
La matrice B non è una matrice ridotta parzialmente, consideriamo le sue righe come
generatori di un codice lineare C di lunghezza n = 4.


 1 0 1 1 



B =
 1 0 1 0 .


1 1 0 1
Riduciamo B mediante una sequenza di operazioni elementari.
{R2 ⇒ R2 + R1
R3 ⇒ R3 + R1 }.

B0

 1 0 1 1 


.
=
0
0
0
1




0 1 1 0
52
3.3 Matrice generatrice
{R2 ⇔ R3 } ;


 1 0 1 1 



B 00 = 
 0 1 1 0 .


0 0 0 1
La matrice B 00 è ridotta parzialmente e le sue tre righe non nulle in cui compaiono gli
1- leading sono linearmente indipendenti quindi si è 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 è ridotta parzialmente
e ogni suo 1-leading si trova in una leading colonna.
Esempio 5
La precedente matrice B 00 può essere ridotta totalmente mediante la seguente operazione
elementare.
{R1 ⇒ R1 + R3 } ;

B 000

 1 0 1 0 



=
 0 1 1 0 .


0 0 0 1
B 000 è una matrice ridotta totalmente ed essa è anche una matrice generatrice.
53
3.4 Matrice di parità
Se un codice C ha dimensione k, allora si ha che la sua cardinalità è | C | = 2k . La
cardinalità di C è quindi pari al numero totale delle differenti parole di lunghezza k. Ciò
è dovuto al fatto che se una base di C è B = {c1 , c2 , · · · , ck }, allora ogni parola c di C si
può esprimere mediante un’unica combinazione lineare degli elementi di B, cioè,
v = a1 c1 + a2 c2 + · · · + ak ck ;
(3.3)
ci sono al più 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
sarà una matrice k × n.
Una generica parola v di C si può ottenere dal seguente prodotto riga per colonna:


 c1 


 c2 


v = u · G = (a1 , a2 , · · · , ak ) · 
;
 . 




ck
dove u = (a1 , a2 , · · · , ak ) è una parola su K di lunghezza k (dimensione di C). La parola
v di C adesso può essere individuata mediante la parola di lunghezza k (a1 , a2 , · · · , ak )G
rispetto alla matrice G.
3.4
Matrice di parità
Se C è un codice lineare, come precedentemente detto, anche il suo codice duale C ⊥ è un
codice lineare. In questa sessione si determina la matrice generatrice del codice duale di
un codice lineare C, in particolare si chiama matrice di parità la trasposta della matrice
generatrice del codice duale.
54
3.4 Matrice di parità
3.4.1
Algoritmo di generazione di H
La matrice di parità è indicata con il simbolo H ed essa è individuata dal codice lineare
C, di parametri (n, k, d), mediante il seguente algoritmo.
Algoritmo
1. Sia S è 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:

A0 = 

G
,
0
dove G è 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
identità I(n−k) .
5. Fine.
2
Teorema 14 La matrice di parità determinata dall’algoritmo precedente è la trasposta
della matrice generatrice del codice duale corrispondente al codice lineare C di parametri
(n, k, d).
55
3.4 Matrice di parità
Dim.
La matrice H è una matrice (n × (n − k)). Per provare il teorema basta mostrare che
il prodotto riga per colonna tra le matrici G e H è uguale ad una matrice nulla del tipo
(k × (n − k)). Senza ledere la generalità della dimostrazione a meno di una permutazione
delle colonne di G e delle righe di H si ha che è possibile scrivere G0 = [Ik , X] e H 0 =


X

. Il prodotto riga per colonna delle due matrici è:
I(n−k)
h
G0 · H 0 =
i
Ik X



X
 = X + X = 0;
(3.4)
In−k
ciò prova il teorema e la correttezza dell’algoritmo, inoltre si ha che:
H T = 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 parità. Riduciamo totalmente la matrice:

AV I
{R2 ⇒ R2 + R1

 1 1 1

 1 0 1

=
 0 1 0


1 1 0
R4 ⇒ R4 + R1 } ;
56
0 1 

1 0 

;
1 1 


1 0
3.4 Matrice di parità

AV
 1 1

 0 1

=
 0 1


0 0

1 0 1 

0 1 1 

;
0 1 1 


1 1 1
{R3 ⇒ R3 + R2 } ;


AIV
 1 1 1

 0 1 0

=
 0 0 0


0 0 1
0 1 

1 1 

;
0 0 


1 1
{R3 ⇔ R4 } ;

AIII

 1 1 1

 0 1 0

=
 0 0 1


0 0 0
{R1 ⇒ R1 + R2 } ;
57
0 1 

1 1 

;
1 1 


0 0
3.4 Matrice di parità

AII
 1 0

 0 1

=
 0 0


0 0

1 1 0 

0 1 1 

;
1 1 1 


0 0 0
{R1 ⇒ R1 + R3 } ;


AI
 1 0 0

 0 1 0

=
 0 0 1


0 0 0
0 1 

1 1 

.
1 1 


0 0
La matrice AI è totalmente ridotta e da essa si ricava la matrice G in cui sono presenti 3
colonne leading e quindi C ha dimensione k = 3.


 1 0 0 0 1

G =
 0 1 0 1 1

0 0 1 1 1


.


Da G eliminando le 3 leading colonne si ottiene la matrice X.
58
3.4 Matrice di parità


 0 1 



X =
 1 1 .


1 1
Consideriamo adesso la matrice identità In−k = I2 , posizioniamo le righe di X nelle righe
corrispondenti alle posizioni delle 1-leading colonne di G cioè 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 parità H.


0 1




 1 1 





H =
 1 1 .




 1 0 


0 1
Per ottenere la matrice generatrice del codice duale basta fare la trasposta di H, ovvero:

HT
=

0 1 1 1 0
1 1 1 0 1
59
=
h
i
XT
In−k
.
3.4 Matrice di parità
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 parità H.
Riduciamo totalmente la matrice:

AV I
{R2 ⇒ R1 + R2
 1 1

 1 1

=
 1 1


1 0
R3 ⇒ R3 + R1

1 1 1 1 1 1 

1 1 0 0 0 0 

;
0 0 1 1 0 0 


1 0 1 0 1 0
R4 ⇒ R4 + R1 } ;


AV
 1 1 1

 0 0 0

=
 0 0 1


0 1 0
1 1 1 1 1 

0 1 1 1 1 

;
1 0 0 1 1 


1 0 1 0 1
{R2 ⇔ R4 } ;

AIV
 1 1

 0 1

=
 0 0


0 0

1 1 1 1 1 1 

0 1 0 1 0 1 

;
1 1 0 0 1 1 


0 0 1 1 1 1
60
3.4 Matrice di parità
{R1 ⇒ R1 + R2 } ;

AIII
 1 0

 0 1

=
 0 0


0 0

1 0 1 0 1 0 

0 1 0 1 0 1 

;
1 1 0 0 1 1 


0 0 1 1 1 1
{R1 ⇒ R1 + R3 } ;


AII
 1 0 0

 0 1 0

=
 0 0 1


0 0 0
1 1 0 0 1 

1 0 1 0 1 

;
1 0 0 1 1 


0 1 1 1 1
{R1 ⇒ R1 + R4 } ;

AI

 1 0 0

 0 1 0

=
 0 0 1


0 0 0
1 0 1 1 0 

1 0 1 0 1 

.
1 0 0 1 1 


0 1 1 1 1
61
3.4 Matrice di parità
La matrice AI è totalmente ridotta. Da essa si determina la matrice G.


 1 0 0

 0 1 0

=

G
 0 0 1


0 0 0
1 0 1 1 0 

1 0 1 0 1 

.
1 0 0 1 1 


0 1 1 1 1
Costruiamo la matrice X eliminando le 4 colonne leading. La dimensione di C è k = 4.

 1 1

 1 1

=

X
 1 0


0 1

1 0 

0 1 

.
1 1 


1 1
Consideriamo la matrice identità In−k = I4 e aggiungiamo i suoi elementi nella righe
corrispondenti alle colonne di G non eliminate.
62
3.4 Matrice di parità












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 è H T le cui n − k = 4 righe formano una base
per C ⊥ .
Nella dimostrazione del teorema 14 tramite una permutazione delle colonne si trasforma
la matrice generatrice ridotta totalmente in una matrice del tipo G0 = [I, X]. Ci si pone
la domanda se per un qualunque codice C, di parametri (n, k, d), è sempre possibile determinare una matrice del tipo G0 senza effettuare permutazioni delle sue colonne. Esistono
codici che non possono avere matrici generatrici poste nella forma assunta dalla matrice
G0 , tale affermazione è 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

; G0 = 

1 0 1

; G00 = 
0 0 1

1 0 1
1 0 0
63

; G000 = 

0 0 1
1 0 1
;
3.4 Matrice di parità

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
h
i
G = Ik X allora esso si chamerà sistematico e una sua qualunque parola v si può
esprimere nel modo seguente:
h
v =u·
i
h
=
I X
i
u uX
(3.5)
.
I primi k bits di v, (cioè u), sono chiamati bits di ricezione , gli ultimi n − k bits (cioè
(uX)) bits di parità o di controllo.
I codici che non sono sistematici possono essere riconducibili a codici sistematici mediante
una o più permutazioni delle colonne di una delle matrici G. Ad esempio:

G=


1 0 0

⇒
G=
0 0 1

1 0 0
.
0 1 0
Il codice sistematico ottenuto è detto equivalente al codice che lo ha generato in quanto
esso mantiene la stessa dimensione, distanza e lunghezza.
64
3.4 Matrice di parità
La matrice di parità di un codice lineare C permette di “controllare” se una parola w
ricevuta è una parola del codice utilizzato, infatti se w ∈ C essa non può appartenere a
C ⊥.
Teorema 15 Condizione necessaria e sufficiente affinchè w ∈ C è che w · H = 0.
Dim.
Se c1 , c2 , · · · , cn−k sono parole che individuano una base di C ⊥ e t ci è la parola trasposta
di ci , per 1 ≤ i ≤ n − k, allora la matrice H si può scrivere nel seguente modo:
h
H =
i
tc ,
1
tc ,
2
··· ,
tc
n−k
.
Se w ∈ C poichè w · ci = 0 per qualunque ci con 1 ≤ i ≤ n − k, allora si ha:
w · H = 0,
e il teorema è provato.
2
Un’altro importante risultato che lega la distanza con le righe della matrice di parità è
dato dal seguente teorema.
Teorema 16 Sia C un codice lineare e H la sua matrice di parità. Allora C ha distanza 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.
Dim.
Sia d la distanza del codice lineare C, ciò 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
65
3.5 Coset
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 perchè w ∈
/ C, ne segue quindi che comunque si scelgono d − 1 righe
di H esse saranno sempre linearmente indipendenti e il teorema è provato. Il viceversa è
2
banalmente dimostrabile.
3.5
Coset
In questa sessione è presentato un sottoinsieme di K n che si lega al concetto presente in
algebra di “laterale” o “coset” (termine inglese). Il laterale nella seguente trattazione è
presentato come strumento di teoria dei codici.
Se C ⊂ K n è un codice lineare di lunghezza n e u una qualunque parola di K n che può
anche non appartenere a C, allora si definisce coset di C, determinato da u, l’insieme:
C + u = {v + u ∈ K n
∀v ∈ C} .
Tale insieme contiene lo stesso numero di parole del codice cioè 2k , in particolare se u è
una parola di C chiaramente si ha che C + u = C, in caso contrario esso sarà diverso da C,
ma non sarà un sottospazio di K n in quanto è evidente che non contiene la parola nulla.
Esempio 9
Sia il codice C = (000, 111) ⊂ K 3 e u = 101, l’insieme coset sarà C + u = {101, 010} Se
consideriamo u0 = 111: C + u0 = {111, 000}.
Si nota che per u0 ∈ C si ha: C+u0 = C. Sia u00 = 010 si ha che C+u00 = {010, 101} = C+u,
da ciò segue che ad ogni parola di K 3 non sempre corrispondono cosets differenti.
66
3.5 Coset
Il seguente teorema mostrerà le principali proprietà 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
K n , allora valgono le seguenti otto proprietà:
1. Se u è 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 K n è contenuta in uno ed un solo coset.
6. Tutti i coset hanno la stessa cardinalità: |C + u| = |C|. Da ciò la cardinalità di un
coset è 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 è un coset.
Dim.
Dimostriamo in sequenza le proprietà del teorema.
1. Se u ∈ C + v deve esistere una w ∈ C tale che u = w + v. Sia t ∈ C + v, allora esiste
un t0 ∈ C tale che t = t0 + v ed inoltre t = t0 + w + u. Poichè il codice è lineare si
ha che t0 + w ∈ C, segue che t ∈ C + u. Data l’arbitrarietà di t si ha che qualunque
parola di C + u essa appartiene anche a C + v e si ha che C + v ⊇ C + u.
Sia p una generica parola appartenente a C +u, allora esiste un p0 tale che p = p0 +u,
con p0 ∈ C, inoltre p = p0 + w + v, ma p0 + w ∈ C, essendo p0 e w parole del codice,
ne segue che p ∈ C + v e C + u ⊇ C + v, deve quindi essere C + u = C + v.
67
3.5 Coset
2. La dimostrazione è immediata perchè la parola nulla appartiene a C.
3. Se u + v ∈ C allora esiste una w ∈ C tale che w = u + v, ma poichè u = w + v, allora
si ha che u ∈ C + v e per la prima proprietà del teorema si ha che C + u = C + v.
4. Supponiamo per assurdo che u e v appartengono allo stesso coset C +w, ciò comporta
che esiste una parola t0 ∈ C tale che u = t0 + w e esiste una parola t00 ∈ C tale che
v = t00 + w, sommando si ha u + v = t0 + t00 + w + w = t0 + t00 , ma C è lineare, quindi
t0 + t00 ∈ C e conseguentemente u + v ∈ C il che è 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. Ciò comporta che w ∈ C + u e per la prima proprietà
w ∈ C + u = C + w, ma anche w ∈ C + v = C + w da ciò C + u = C + v il che è
assurdo.
Tale proprietà mostra che cosets distinti sono disgiunti.
6. La dimostrazione è immediata.
7. Le parole totali di K n sono 2n mentre le parole di C sono 2k . Da ciò il numero di
2n
coset sarà k = 2n−k .
2
8. La dimostrazione è immediata.
2
Esempio 10
Sia dato un codice C = {0000, 1011, 0101, 1110}. Una sua matrice generatrice è

G =

1 0 1 1
.
0 1 0 1
Il codice C è individuato dai parametri (4, 2, 2), quindi il numero di coset è 2n−k = 4 e
sono:
68
3.5 Coset

 0 0

 1 0

C=
 0 1


1 1

0 0 

1 1 

.
0 1 


1 0
Per determinare il secondo coset consideriamo la parola u1 = 1000 in K 4 non appartenente
a C e aggiungiamo tale parola ogni parola di C.

 1 0

 0 0

u1 + C = 1000 + C = 
 1 1


0 1

0 0 

1 1 

.
0 1 


1 0
Consideriamo adesso un’altra parola, u2 = 0100, non appartenente a C o a C + u1 . Il terzo
coset sarà:

 0 1 0

 1 1 1

u2 + C = 0100 + C = 
 0 0 0


1 0 1

0 

1 

.
1 


0
Ripetendo lo stesso procedimento con la parola u3 = 0010, il quarto coset sarà:
69
3.5 Coset

 0 0

 1 0

u3 + C = 0010 + C = 
 0 1


1 1

1 0 

0 1 

.
1 1 


0 0
Dei quattro coset, l’unico che rappresenta un codice lineare è chiaramente il primo, essendo
C stesso.
Adesso sfruttando le proprietà 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 è u = v + w, tale equazione è equivalente a u + w = v ∈ C. Per
la proprietà 3 del teorema 17 si ha che l’errore u e la parola ricevuta w appartengono a
uno stesso coset di C.
Poichè gli errori di minor peso sono quelli che hanno maggiore probabilità di verificarsi,
vediamo adesso come la tecnica MLD può 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 è 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,
cioè la più probabile, tale parola prende il nome di coset leader.
Sommando u a w si ottiene la parola v = w + u, essa è la parola che ha la maggiore
probabilità di essere stata inviata.
Esempio 11
I coset leaders corrispondenti ad ogni singolo coset dell’esempio 10 sono:
70
3.6 Sindrome
1. il coset leader di C è 0000;
2. il coset leader di C + u1 è 1000;
3. il coset leader di C + u2 è 0100;
4. il coset leader di C + u3 è 0010.
Se w = 1101 è la parola ricevuta si verifica facilmente che w ∈ C + u1 = C + 1000 e
tale coset ha coset leader la parola (1000). La correzione della parola w è v = w + u =
1101 + 1000 = 0101.
Può accadere che in un coset vi sono più parole con uguale peso minimo, in tal caso si può
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
più di una parola di minore peso allora si richiede la ritrasmissione.
È importante sottolineare che per la prima volta si è riusciti a determinare l’errore u
soltanto tramite la conoscenza della parola trasmessa w e tramite esso si può effettuare la
correzione.
Il procedimento di correzione appena descritto, nel caso in cui il numero degli elementi di
un codice C è elevato, può comportare notevoli problemi di immagazzinamento 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 K n .
Sia w ∈ K n , si definisce sindrome di w la parola s = w · H di K n−k .
71
3.6 Sindrome
Esempio 12
Consideriamo il codice presentato nell’esempio 10 e sia la parola w = 1101. La matrice H
di C è:


1
1




 0 1 


H=
.
 1 0 




0 1
La sindrome di w è:


 1 1 


 0 1 


s = w · H = 1101 
 = 11.
 1 0 




0 1
Quindi essendo s = w · H 6= 0 per il teorema 15 si ha che w ∈
/ C e w ∈ C + 1000.
Consideriamo una qualunque parola w0 del coset C+1000 è facile notare che la sua sindrome
sarà sempre la stessa cioè:


1
1




 0 1 


s = w0 · H = w0 
 = 11.
 1 0 




0 1
72
3.6 Sindrome
Il teorema seguente spiega i risultati ottenuti nell’ultima parte dell’esempio 12.
Teorema 18 Sia C un codice lineare di parametri (n, k, d). Siano u e w due parole di K n
e H la sua matrice di parità, allora valgono le seguenti proprietà:
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 è l’errore di una parola ricevuta w allora u · H è la somma delle righe di H che
corrispondono alla posizione dei bits alterati in trasmissione.
Dim.
1. La proprieta è 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 è l’errore legato a w allora è evidente che u · H individua le righe di H
in cui è avvenuto un cambiamento di carattere nei bits corrispondenti della parola
inviata.
2
73
3.6 Sindrome
Dato che parole dello stesso coset hanno la stessa sindrome, mentre parole di coset differenti hanno sindromi differenti, allora è possibile identificare un coset con la sua sindrome
corrispondente e a tale sindrome si può associare il coset leader corrispondente. Tale corrispondenza tra sindrome e coset leader permette di individuare una tabella, detta SDA (
Standard Decoding Array).
Se C è 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
è posta come seconda componente della riga. Nel caso in cui più parole hanno stesso minor
peso all’interno di un coset, allora, in tale esempio, è utilizzata la tecnica CMLD.
Esempio 13
Coset leaders
Sindrome u·H
0000
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 è costruita la tabella SDA.
Se w = 0101 allora w ·H = 00 che è la sindrome di 0000. Da ciò v = w +u = 0101+0000 =
0101. Se w = 1100 allora w · H = 10 che è la sindrome di 0010. Da ciò v = w + u =
1100 + 0010 = 1110.
74
Capitolo 4
Codici perfetti
4.1
Cardinalità di un codice C
In questa sessione sono presentate le relazioni esistenti tra i parametri che caratterizzano un
codice C, cioè lunghezza, distanza e dimensione, e il numero di parole presenti nel codice.
Inoltre sono presentati particolari codici che in seguito assumeranno notevole importanza.
Facciamo prima alcune considerazioni legate alla distanza tra parole differenti di K n e la
distanza d di un codice C.
Sia v una parola di K n , 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 è
uguale a:



n
t
=
n!
n(n − 1) · · · (n − t + 1)
=
.
t!(n − t)!
t!
(4.1)
Ci si pone la seguente domanda: qual’è il numero di parole di K n che hanno distanza 1 da
v?
75
4.1 Cardinalità di un codice C
Il problema si può anche porre nel seguente modo: determinare il numero di parole di
K n che differiscono da v soltanto per un bit. Chiaramente il numero di tali parole è


n
. In generale determinare il numero di parole di K n che hanno distanza t, con
n=
1
t < n, da v è 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


n
.
numero di parole che hanno distanza t da v è esattamente 
t
Esempio 1
Sia v = 101110101 una parola di K 9 . Il numero di parole che hanno distanza 1 in K 9 da v
 
 
9
9
9·8
è   = 9; Il numero di parole che hanno distanza 2 in K 9 da v è   =
= 36;
2
1
2
 
9
9·8·7
Il numero di parole che hanno distanza 3 in K 9 da v è   =
= 84.
3·2
3


Da quanto detto precedentemente e ricordando che 
n
 = 1 si ha il seguente teorema.
0
Teorema 19 Se 0 ≤ t ≤ n e v è una parola di lunghezza n, appartenente ad un codice C,
allora il numero di parole di lunghezza n e distanza al più t da v è:

N =

n
0

+

n

+
1

n
2

 + ··· + 

n
.
(4.2)
t
2
76
4.1 Cardinalità di un codice C
Il precedente teorema permette di determinare per ogni parola v di un codice C, avente
distanza d e lunghezza n, una “sfera” in K n di centro v e “raggio” t tale che al suo interno si
trovano esattamente N parole. Qui è usato il termine “sfera” per facilitare la comprensione
del lettore, ma se consideriamo le parole di K n come punti di uno spazio a n dimensioni
il concetto di “sfera” è molto più complesso e rientra nel campo della geometria finita che
esula da un corso di teoria dei codici.
Nel seguente teorema è mostrato che se la distanza di C è 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 ∈ K n tale che d(v, c) ≤ t e
d(w, c) ≤ t.
Dim.
Supponiamo per assurdo che esista una c ∈ K n 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.
Si sono determinate due parole di C, v e w che hanno distanza minore della distanza di C
cioè d(v, w) < d, questo è assurdo.
2
Il risultato precedente permette di ottenere un limite superiore alla cardinalità | C | di un
codice, tale limite , è legato ai parametri n e d.
Teorema 21 (Limite di Hamming) Se C è un codice di lunghezza n e distanza d =
2t + 1 allora si ha che:
77
4.1 Cardinalità di un codice C

| C | · 

n


+
0
n


n
+
1


 + ··· + 
2
n
 ≤ 2n ,
(4.3)
 .
(4.4)
t
ovvero:
|C |≤ 


n

+
0
2n


n
+
1

n

 + ··· + 
n
2

t
Dim.
Se si considera un’arbitraria parola v ∈ C, per il teorema (19), le parole che distano al più
t da v sono:


N =
n

+
0

n

+
1

n

 + ··· + 
2

n
.
t
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 è:


| C | · 
n
0

+

n

+
1

n
 + ··· + 
2
Il numero di parole distinte in K n è 2n , si ha allora che:
78


n
t
 .
4.1 Cardinalità di un codice C

| C | · 

n


+
0
n


n
+
1


 + ··· + 
2
n
 ≤ 2n .
(4.5)
t
Il teorema è provato.
2
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| ≤ 


n
0
2n
=

+
n
26
= 9.
1+6
(4.6)

1
Poichè 9 non è una potenza del due e tutti i codici binari devono avere una cardinalità pari
ad una potenza di 2, 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 parità H di un codice lineare C è definita come:
79
4.1 Cardinalità di un codice C


H =
X
.
In−k
In essa non vi possono essere più di n − k righe linearmente indipendenti, data la presenza
di In−k , le cui righe costituiscono una base per K n−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,
e il teorema è provato.
(4.7)
2
Poniamoci adesso il seguente problema, dati i parametri (n, k, d) vediamo se è possibile
determinare un codice lineare C le cui parole hanno lunghezza n, la sua dimensione è k e
la sua distanza è d.
Un codice lineare può essere individuato mediante la sua matrice di parità, cioè 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 è la matrice trasposta della
matrice generatrice del codice duale GC⊥ =t H, da essa, mediante l’algoritmo presentato
nel capitolo 3, si può determinare la matrice di parità HC⊥ del codice duale che individua
una matrice generatrice G =t HC⊥ (n × (n − k)) del codice C avente parametri (n, k, d).
Nel seguente esempio è mostrato un metodo utile a determinare la matrice di parità di un
codice lineare avente parametri (n, k, d), tale tecnica in seguito permetterà di formulare il
80
4.1 Cardinalità di un codice C
Figura 4.1:
teorema di Gilbert - Varshamov.
Esempio 3
Vediamo se è possibile determinare un codice lineare C di parametri (15, 6, 5). Individuiamo
la sua matrice di parità H (15 × 9). Essa può contenere la matrice I9 , costituita da righe
linearmente indipendenti. Bisogna determinare altre sei righe di K 9 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 escludere la parola nulla di K 9 , in quanto essa stessa è linearmente dipendente, inoltre è necessario
escludere qualsiasi parola contenuta in I9 e tutte le parole di K 9 ottenute da combinazioni
lineari di due o tre righe di I9 , quindi è possibile aggiungere una decima riga se il numero totale delle parole in K 9 , cioè 29 , è strettamente maggiore del numero di parole che
necessariamente devono essere escluse. Quindi deve valere la seguente disuguaglianza.



9
0

+

9
1

+

9
2
81

+

9
3
 < 29 .
4.1 Cardinalità di un codice C
La disuguaglianza è valida in quanto 1 + 9 + 36 + 84 < 29 , quindi è possibile aggiungere
una decima riga. Sia essa la riga 111100000 che formerà la matrice,

H10 = 

I9
.
111100000
È importante notare come la matrice H10 ha già d = 5 righe linearmente dipendenti, cioè la
prima, la seconda, la terza, la quarta e la decima. Determiniamo adesso H11 aggiungendo
a H10 un’undicesima riga mantenendo le proprietà richieste precedentemente, cioè in H11
non possono esistere 4 righe linearmente dipendenti. La seguente disuguaglianza, ottenuta
dalle precedenti considerazioni,



10
0

+

10

+
1

10

+
2

10
 < 29 ,
3
è ancora valida e quindi aggiungiamo la riga 100011100, otteniamo la matrice H11 . Iterando
questa procedura otteniamo la matrice di parità di C di parametri (15, 6, 5).

H10









=









I9
111100000
101000011
100011100
110000011
000101110
000001111
82









.








4.1 Cardinalità di un codice C
Teorema 23 (Limite di Gilbert-Varshamov) Un codice lineare C con parametri (n, k, d)
esiste se:



n−1

+

n−1
0

 + ··· + 
1

n−1
 < 2n−k .
d−2
Dim.
Il codice C si può determinare mediante la sua matrice di parità H, cioè una matrice
(n × (n − k)). Supponiamo di aver determinato una matrice Hi , dove il primo valore che i
può assumere è n−k cioè Hn−k = In−k . In generale consideriamo un i, con n−k ≤ i ≤ n−1,
Hi deve avere la proprietà che comunque si prendono in essa d − 1 righe esse devono
essere linearmente indipendenti. Cerchiamo di determinare una matrice del tipo Hi+1
aggiungendo una riga a Hi . Tale riga deve essere scelta in K n−k e deve essere differente
dalla parola nulla, è necessario poi escludere in K n−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 K n−k è
dato da:

Ni = 

i
0

+

i

+
1

i
2

 + ··· + 

i
.
d−2
Se Ni < 2n−k allora sarà 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 è uguale a:
83
4.2 Codici MDS

Ni+1 = 

i+1


+
i+1
0


+
i+1
1


 + ··· + 
2
i+1
.
d−2
Ancora una volta se Ni+1 < 2n−k allora sarà possibile determinare la matrice Hi+2 . È
importante notare che la disuguaglianza Ni < Ni+1 è valida. Il procedimento descritto, se
possibile, si può iterare fino a che i = n − 1, in tal caso se è anche valida la diseguaglianza
seguente,

Nn = 

n−1

+

n−1
0
1

+

n−1
2

 + ··· + 

n−1
 < 2n−k ,
(4.8)
d−2
allora sarà possibile determinare la matrice H di C. Inoltre poichè in generale vale sempre
la disuguaglianza Ni < Ni+1 per n − k ≤ i ≤ n − 1, è possibile determinare la matrice di
parità H di C solo se è verificata la disuguaglianza (4.8) e il teorema è provato.
4.2
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 può assumere
il suo valore massimo cioè d = n − k + 1. Tali codici prendono il nome di codici MDS
dall’inglese “Maximum Distance Separable”.
84
4.2 Codici MDS
I codici MDS assumono una notevole importanza in quanto a tutt’oggi sono ampiamente
utilizzati nella lettura dati (lettori CD o DVD), tra i più importanti si ricordano i codici
Reed-Solomon che si rimandano ad un corso di teoria dei codici più avanzato.
Il teorema seguente identifica una serie di proprietà che caratterizzano i codici MDS e che
sono tra esse equivalenti.
Teorema 24 Per ogni codice lineare C (n, k, d) le seguenti proposizioni sono equivalenti:
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 linearmente
indipendenti.
4. C è un MDS
Dim.
1. Se d = n − k + 1, dalla definizione, si ha che C è un codice MDS e vale il viceversa.
2. Supponiamo di avere una matrice di parità H avente la proprietà che comunque si
individuano in essa n − k righe esse sono linearmente indipendenti. Per il teorema 16
del capitolo 3, la matrice H ha la proprietà che comunque si scelgono d − 1 righe
esse sono linearmente indipendenti e ve ne sono d linearmente dipendenti, allora si
ha che n − k ≤ d − 1, ma per il teorema 22 anche la disuguaglianza d − 1 ≤ n − k è
valida, quindi deve essere d − 1 = n − k. È evidente che vale anche il viceversa.
3. Sia C un codice lineare MDS, allora si ha che n − d = k − 1. Se tale eguaglianza è
valida allora si ha che in ogni parola di C non possono esistere più 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
85
4.3 Codici estesi
per assurdo che esistano k colonne linearmente dipendenti. Se si estraggono tali
colonne, esse individuano una matrice quadrata A (k × 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 è uguale a
quello delle colonne). È possibile quindi determinare una parola u ∈ K k , diversa
dalla parola nulla, tale che u · A = 0 ∈ K k e segue anche che la parola del codice
u · G possiede k zeri, questo è un assurdo.
4. Se C è MDS allora banalmente valgono tutte le tre condizioni precedenti.
4.3
2
Codici estesi
Consideriamo un codice lineare C di parametri (n, k, d) e ad ogni parola di C si aggiunge
il bit di parità, cioè 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 è detto codice
esteso di C.
La matrice generatrice di un codice esteso si può rappresentare nel seguente modo G∗ =
[G, b], dove la sottomatrice G è la matrice generatrice di C e b è 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 è dispari e valore “0” in caso contrario.
La matrice di parità H ∗ del codice esteso C ∗ può essere costruita tramite la matrice G∗
mediante il noto algoritmo oppure in modo più semplice dalla matrice di parità H del
codice originario C. La matrice di parità di C ∗ sarà:

H∗ = 

H J
0
86
1
,
(4.9)
4.3 Codici estesi
dove J è un vettore colonna formato da bits che assumono tutti valore “1”. Per provare
che tale matrice è effettivamente la matrice di parità di C ∗ basta provare che il prodotto
riga per colonna è G∗ · H ∗ = 0.
G∗ · H ∗ =
h
i
G, b

·

H J
0
1
=
h
i
GH, GJ + b
,
il prodotto G · H = 0, essendo G e H le matrici generatrice e di parità del codice C.
Consideriamo adesso il temine GJ + b, osserviamo che se ri è la riga i-esima della matrice
G allora si ha che:

 1 se ri contiene un numero dispari di bits di valore “1”;
ri · J =
 0
se ri contiene un numero pari di bits di valore “1”.
Se indichiamo con bi la componente i-esima del vettore b, essa assumerà il valore:

 1 se ri · J = 1;
bi =
 0 se r · J = 0.
i
Si ha dunque che GJ + b = 0 e quindi H ∗ è la matrice di parità di C ∗ .
87
4.4 Codici perfetti
Esempio 4
Consideriamo un codice lineare C avente matrici generatrice e di parità:





 0 1 





H = 1 1 
.




 1 0 


0 1


 1 0 0 1 0

G =
 0 1 0 0 1

0 0 1 1 1

1 0


,


Definiamo le matrici G∗ e H ∗ del codice esteso di C aggiungendo il bit di parità ad ogni
riga di G e utilizzando la (4.9).




G∗
4.4
 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 0 1
Codici perfetti
Un codice C di lunghezza n e distanza d = 2t + 1 si dice perfetto se si ha che:
|C |= 


n
0


+
n
2n

+

n
2
1
88
 .

 + ··· + 
n
t

(4.10)
4.4 Codici perfetti
Poichè la cardinalità di un codice binario deve essere uguale ad una potenza di 2 allora è
immediata la seguente condizione necessaria.
Teorema 25 Condizione necessaria per l’esistenza di un codice perfetto è che:



n

+

n
0

+
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 K n e il codice C = K n .
Esempio 5
• Verifichiamo che il codice con n = 7 e d = 3 è perfetto.
d = 2t + 1 = 3 ⇒ t = 1 e quindi si ha che:
|C| = 


7
27
=

+
0
7
1
89

27
= 24 = 16.
23
4.4 Codici perfetti
Il codice C è 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| = 


23
0
223
 

+
23
1
+

23
 =

+
2
23
223
= 212 = 4096.
211

3
Il secondo codice dell’esempio individua un codice che in seguito sarà 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 è omessa la
dimostrazione.
Teorema 26 (Van Lint) Se C è 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 è un codice perfetto di lunghezza n e distanza d = 2t + 1, allora C
corregge tutti gli errori di peso minore o uguale a t.
90
2
4.4 Codici perfetti
4.4.1
Codice di Hamming
Un codice lineare di lunghezza n = 2r − 1, con r ≥ 2, avente una matrice di parità H le
cui righe hanno lunghezza r è detto codice di Hamming.
In un codice di Hamming la matrice H è 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, è 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 parità di un codice di Hamming con r = 3 (n = 2r − 1 = 7) è:

 1 1

 1 1



 1 0


 0 1


 1 0


 0 1


0 0
La sua matrice generatrice è:
91

1 

0 



1 


1 .


0 


0 


1
4.4 Codici perfetti

0 0 1 1 1 

0 0 1 1 0 

.
1 0 1 0 1 


0 1 0 1 1

 1 0

 0 1

G =
 0 0


0 0
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 ⊥ è:
dimC + dimC ⊥ = n,
Poichè dimC ⊥ = r ed inoltre n = 2r − 1, allora si ha che:
k = dimC = 2r − 1 − r.
La cardinalità del codice di Hamming C è:
| C | = 2k = 22
r −1−r
Gli stessi risultati precedentemente ottenuti si possono ricavare considerando che C è un
codice perfetto con d = 2t + 1 = 3 e t = 1 allora si ha che:
|C |= 


n
0
2n
r
 =

+
n

1
92
22 −1
r
= 22 −1−r .
r
1+2 −1
4.4 Codici perfetti
Sia un codice di Hamming C di lunghezza n = 2r − 1, se si considera una parola v di K n
di peso uno, essa certamente non appartiene a C, poichè 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 è pari a 2r , quindi le 2r − 1 parole di lunghezza n = 2r − 1 e peso uno più 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 · H
0000 · · · 0000
00 · · · 00
I2r −1
H
Esempio 7
La tabella SDA del codice di Hamming dell’esempio 6 è qui sotto rappresentata.
COSET LEADER u
SINDROME u · H
0000000
000
1000000
111
0100000
110
0010000
101
0001000
011
0000100
100
0000010
010
0000001
001
93
4.4 Codici perfetti
4.4.2
Codice di Golay esteso
In questa sessione è presentato il codice perfetto esteso avente come parametri
(24, 12, 8), esso è generato dal codice perfetto di parametri (23, 11, 7) e si chiama
codice di Golay esteso .
Il codice di Golay ha una notevole importanza perchè è stato ampiamente utilizzato
dall’ente spaziale NASA negli anni ’80 soprattutto nelle trasmissioni delle sonde
Voyager.
Per definire tale codice è necessario costruire la matrice B1 di tipo (11 × 11) ottenuta 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































(4.11)
0 1 1 0 1 1 1 0 0 0 1
Consideriamo adesso un’estensione B (12 × 12) della matrice B1 nel seguente modo:
94
4.4 Codici perfetti


B=
B1
JT













 


J
=


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

















.
















(4.12)
1 1 1 1 1 1 1 1 1 1 1 0
Definiamo inoltre la matrice generatrice del codice di Golay esteso:
h
G=
i
I12 , B
,
Il codice di Golay esteso gode delle proprietà che sono enunciate nel seguente teorema.
Teorema 28 Un codice di Golay esteso C ha le seguenti proprietà:
1. Il codice C ha una lunghezza n = 24, dimensione k = 12 e | C | = 212 = 4096
parole.
95
4.4 Codici perfetti
2. La matrice B è una matrice simmetrica, cioè B T = B.
3. Due qualunque righe ri e rj di B sono tra loro ortogonali, cioè ri · rj = 0.


B
.
4. La matrice di parità di C è H = 
I

5. Esiste un’altra matrice di parità per C cioè H 0 = 

I
.
B
6. C è autoduale cioè C = C ⊥ .
7. La distanza di C è d = 8
8. Il codice C è un codice 3-correttore, cioè corregge tutti gli errori u tali che
wt(u) ≤ 3.
Dim.
Dimostriamo le proprietà del teorema in sequenza.
1. La dimostrazione è evidente osservando le caratteristiche della matrice generatrice.
2. La matrice B è evidentemente simmetrica, ciò è dovuto al metodo della sua
costruzione.
3. Per provare tale proprietà basta eseguire i prodotti ri · rj , con i 6= j e 1 ≤
i, j ≤ 12, e constatare la loro ortogonalità.
4. Per dimostrare che H è una matrice di parità si procede nel modo seguente:
h
G·H =
i
I, B



B
I
96
 = B + B = 0.
4.4 Codici perfetti
5. Per dimostrare che H 0 è una matrice di parità si procede nel modo seguente:
G · H0 =
i
h
I, B



I
 = I + BB T = I + I = 0.
B
6. Poichè H 0 = GT , allora il codice di Golay è un codice autoduale, cioè il suo
duale è 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. Poichè 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 è 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 è
un multiplo di 4.
Consideriamo adesso la parola v 0 = v + rk , dove rk è 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 0 ) = wt(ri + rj ) + wt(rk ) − 4y,
dove 2y è 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
97
4.4 Codici perfetti
una generica parola w di C e anch’essa, con analoghi ragionamenti fatti in
precedenza, ha un peso che è un multiplo di 4. Nella matrice G sono presenti
righe di peso 8 e 12, è 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 è
autoduale, allora ogni sua parola si può ottenere dalle due diverse matrici
h
i
h
i
generatrici di G = I, B e G0 = B, I cioè si ha:
h
w = u1
i
h
=
I, B
i
,
u1 , u 1 B
e
h
w = u2
i
B, I
h
=
i
u2 B, u2
.
Dato che wt(w) = 4, supponendo che wt(u1 ) ≥ 2 (cioè che i primi dodici bit
di w contengano due o più bit di valore 1), allora deve essere necessariamente
wt(u1 B) ≤ 2 che equivale a dire wt(u2 ) ≤ 2, ciò perchè w si può scrivere
sia mediante l’uso di G che di G0 ; nel caso contrario si ha che wt(u1 ) ≤ 2.
Facilmente si può calcolare che il peso della somma di due righe di B è maggiore
o uguale a quattro, allora si ha:
wt(w) = wt(ui ) + wt(ui B) ≥ 1 + 4 = 5,
dove il valore i può assumere il valore 1 o 2, ma ciò è assurdo in quanto
wt(w) = 4 e la proprietà è provata.
8. Tale proprietà è evidende essendo d = 8.
98
2
4.4 Codici perfetti
Abbiamo visto, dalla proprietà 8 del teorema precedente, che il codice di Golay
esteso è un codice 3-correttore, cioè 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
è la parola ricevuta, e u l’errore utilizzato per la correzione si ha che wt(u) ≤ 3.
h
i
L’errore u può essere denotato mediante la seguente scrittura u = u1 , u2 , dove
u1 e u2 hanno lunghezza 12 (l (ui ) = 12 per i = 1 e 2). Poichè wt(u) ≤ 3, allora
deve essere wt(u1 ) ≤ 1 oppure wt(u2 ) ≤ 1. Indichiamo con s1 la sindrome di w, se


I
, allora si ha che:
si usa la matrice di parità H = 
B
h
s1 = w · H = u · H =
i
u1 , u 2


·
I
B
 = u1 + u2 B.
Consideriamo i seguenti due casi.
Primo caso
Se wt(u2 ) ≤ 1, cioè esso può assumere i valori 0 e 1.
• Se wt(u2 ) = 0 segue che u2 B = 0 e quindi risulta s1 = u1 + 0, con wt(u1 ) ≤ 3.
In questo caso l’errore è u = [s1 , 0]. È facile verificare che tale errore ha peso
minore o uguale a tre e ha sindrome uguale a w · H, quindi è un coset leader.
• Se wt(u2 ) = 1 segue che u2 B 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 è u =
[s1 + bj , ej ] ed esso ha la stessa sindrome di w infatti:
99
4.4 Codici perfetti
h
u·H =
i
s1 + bj , ej


·
I
B
 = s1 + bj + bj = s1
.
Secondo caso
Consideriamo
di parità

 adesso la sindrome di w usandola matrice

h
i
B
B
, allora s2 = w · H 0 = u1 , u2 · 
 = u1 B + u2 .
H0 = 
I
I
Se wt(u1 ) ≤ 1, allora wt(u1 ) può assumere i valori 0 e 1.
• Se wt(u1 ) = 0 segue che u1 B = 0 e quindi risulta s2 = 0 + u2 , con wt(u2 ) ≤ 3.
In questo caso l’errore è u = [0, s2 ]. Anche in questo caso si può verificare che
tale errore ha peso minore o uguale a tre e ha sindrome uguale a w · H 0 , esso
è quindi un coset leader.
• Se wt(u1 ) = 1 segue che u1 B 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 è u = [ei , s1 · B + bi ], ed esso ha la
stessa sindrome di w infatti:
u · H0 =
i
h
ei , s1 · B + bi

·

B
I
 = bi + s2 + bi = s2 .
Da questa tecnica di decodifica è possibile determinare un algoritmo di decodifica
per il codice di Golay esteso.
100
4.4 Codici perfetti
Osserviamo che essendo B = B T , allora B 2 = B · B T = I ed è lecito scrivere:
s1 · B = (u1 + u2 B) · B = u1 B + u2 B 2 = u1 B + u2 = s2 .
(4.13)
Ciò significa che, calcolata la sindrome s1 si può facilmente determinare la sindrome
s2 .
Algoritmo di decodifica
1. Calcolo della sindrome s1 = w · H = u1 + u2 B.
h
2. Se wt(s1 ) ≤ 3 allora u =
i
s1 , 0
(caso in cui wt(u2 ) = 0).
h
3. Se wt(s1 + bj ) ≤ 2 per qualche riga bj di B, allora u =
i
s1 + bj , ej , dove
ej è 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 0 = s1 · B.
h
5. Se wt(s1 · B) ≤ 3 (caso in cui wt(u1 ) = 0), allora u =
i
0, s1 B .
i
h
6. Se wt(s1 B + bi ) ≤ 2 per qualche riga bi di B, allora u =
ei , s1 B + bi .
7. Se u non è determinato, allora si richiede la ritrasmissione.
8. Fine.
2
101
4.4 Codici perfetti
Esempio 8
Sia la parola ricevuta w = 101111101111, 010010010010. Calcoliamo la sindrome:

s = w·H = w

I
 = 101111101111 + 001111101110 = 100000000001,
B
osserviamo che wt(s) = 2 ≤ 3. Pertanto:
h
u=
i
s, 0
= 100000000001, 000000000000.
La parola che con maggiore probabilità è stata inviata è:
v = w + u = 001111101110, 010010010010.
Esempio 9
Sia la parola ricevuta w = 001001001101, 101000101000. Calcoliamo la sindrome:

s = w·H = w

I
 = 001001001101 + 111000000100 = 110001001001,
B
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:
102
4.4 Codici perfetti
h
u=
i
s + b5 , e5
= 000000010010, 000010000000.
La parola che con maggiore probabilità è stata inviata è:
v = w + u = 001001011111, 101010101000.
103
Capitolo 5
Codici ciclici
5.1
Polinomi su K
In questo capitolo è mostrato come una parola di un codice C di lunghezza n può
essere rappresentata mediante polinomi di grado n − 1 su K, ma prima mostriamo
alcune proprietà dei polinomi a coefficienti in K, cioè 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 + a1 x + a2 x2 + · · · + an−2 xn−2 + an−1 xn−1 + an xn .
In K[x] può essere considerata la classica operazione di somma tra polinomi. Poichè
in K si ha che 1 + 1 = 0, allora segue che xk + xk = 0, tutto ciò 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).
104
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 ,
è evidente che il polinomio somma ha grado 2 minore di 4 cioè 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 può 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 è il polinomio nullo, inoltre considerato
un generico polinomio g(x) di K[x], dato che g(x) + g(x) = 0, allora è evidente che
l’opposto di tale polinomio è 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:
105
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) + g 2 (x) = f 2 (x) + g 2 (x).
Ciò 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).
Il polinomio q(x) è 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:
106
(5.1)
5.2 Parole di C e polinomi
Quindi f (x) = h(x)(x3 + x4 ) + (x + x2 + x3 ) e in particolare il quoziente è q(x) = x3 + x4 ,
il resto r(x) = x + x2 + x3 , è possibile notare che deg(r(x)) < deg(h(x)) = 4.
5.2
Parole di C e polinomi
In questa sessione viene messa in corrispondenza una parola di K n 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 , cioè l’insieme di polinomi su K con
grado minore o uguale a n − 1.
Consideriamo il polinomio f (x) = a0 +a1 x+a2 x2 +....+an−1 xn−1 che ha grado al più
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 = a0 a1 a2 ....an−1 .
Si è quindi definita una corrispondenza biunivoca tra i polinomi di K[x]n−1 e le parole
di K n .
Esempio 4
Sia n = 5, consideriamo il polinomio di K[x]4 f (x) = 1 + x2 + x4 ad esso si può associare la
parola v = 10101, mentre al polinomio g(x) = 1 + x si può associare la parola w = 11000.
Siano f (x) e h(x) due polinomi con h(x) 6= 0, se si può scrivere f (x) = h(x)q(x) +
r(x), allora diremo che f (x) in modulo h(x) è 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
f (x) ≡ g(x) mod h(x), se e solo se entrambi divisi per h(x) 6= 0 hanno lo stesso
107
5.2 Parole di C e polinomi
resto cioè 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 cioè f (x) in modulo h(x) è 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 può scrivere che f (x) ≡ g(x) mod h(x) = x + 1.
Fissato un polinomio h(x) di grado n, poichè 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
108
5.3 Codici ciclici
f (x) di K[x] si può 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 K n .
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.
Proprietà 7 Se p(x) è un polinomio di K[x] e f (x) ≡ g(x) mod h(x), allora valgono
le due seguenti proprietà.
• f (x) + p(x) ≡ g(x) + p(x) mod (h(x));
• f (x)p(x) ≡ g(x)p(x) mod (h(x)).
5.3
2
Codici ciclici
Prima di dare la definizione di codice ciclico in questa sessione è presentato un
particolare operatore che agisce su K n e permette di ottenere ancora una parola di
K n.
Sia v una parola di K n , si definisce operatore shift ciclico l’applicazione π : K n →
K n , esso agisce sulla parola v spostando il suo ultimo bit nella prima posizione.
109
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.
È facile verificare che l’operatore π è lineare, quindi segue la proprietà.
Proprietà 8 L’operatore π è lineare cioè valgono le due proprietà:
• ∀ v, w ∈ K n , π(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,
cioè 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.
110
5.3 Codici ciclici
Quindi il codice C è un codice ciclico.
Si può notare che il codice C dell’esempio 8 oltre ad essere ciclico è anche un codice
lineare, infatti la somma di due sue parole è ancora una parola del codice. L’esempio
seguente però 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 è lineare ma non ciclico.
Cerchiamo di determinare un codice ciclico e lineare; sia v ∈ K n 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
π cioè
π(π(· · · (π(v)) · · · ). Consideriamo l’insieme di tutte le possibili combinazioni lineari
delle parole di S, cioè L(v, π(v), π 2 (v), · · · , π n−1 (v)), tale insieme definisce un codice
C che è ciclico lineare, in quanto C = L(v, π(v), π 2 (v), · · · , π n−1 (v)) e l’operatore
π è un’applicazione lineare. È facile anche notare che un codice così ottenuto è il
più piccolo codice ciclico lineare contenente v, infatti se v appartiene ad un codice
ciclico lineare C 0 , con C 0 6= C, allora esso sempre contiene l’insieme S e l’insieme
L(v, π(v), π 2 (v), · · · , π n−1 (v)). L’insieme S è un insieme di generatori per il codice
lineare C.
111
5.4 Codice ciclico e polinomi di K n−1
Esempio 10
Sia la parola di K 3 v = 100, consideriamo l’insieme S = {100, 010, 001}, allora si ha che
C = K 3 = {000, 100, 010, 001, 110, 101, 011, 111}.
Esempio 11
Sia la parola di K 4 v = 0101, π(v) = 1010 e π 2 (v) = 0101 = v, quindi S = {0101, 1010}.
È importante notare che la ciclicità delle parole v negli esempi precedenti era n − 1, adesso
è 1 poichè π 2 (v) = v, il codice ottenuto è C = {0000, 0101, 1010, 1111}.
5.4
Codice ciclico e polinomi di K n−1
Come si è visto nella seconda sessione del capitolo una qualunque parola v può
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 π è 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 può determinare
un polinomio f (x) di grado maggiore di n − 1 che è legato ad una parola binaria
di lunghezza n + 1. Nasce la necessità di “modulare” il polinomio f (x) ottenuto
tramite il polinomio h(x) = xn + 1, cioè 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.
È importante notare che poichè xn mod (xn + 1) = 1, allora se in un polinomio è
presente il termine xn esso si può sostituire con il termine 1.
112
5.4 Codice ciclico e polinomi di K n−1
Quanto detto consente di generare un lineare da un punto di vista polinomiale. Sia
v una parola di K n a cui è associato il polinomio v(x), costruiamo l’insieme S così
definito:
©
ª
S = v(x), xv(v), x2 v(x), · · · , xn−1 v(x) .
(5.2)
Nella (5.2) al polinomio xi v(x) corrisponde la parola π i (v). È evidente che in S
possono essere presenti polinomi di grado maggiore di n − 1, allora è necessario
considerare ogni polinomio di S in modulo (xn +1), per far ciò si utilizza la scrittura:
©
ª
S = v(x), xv(x), · · · , xn−1 v(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 è il più 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 è equivalente alla tecnica in cui
si adopera l’operatore π ed essa genera lo stesso codice.
Esempio 12
Sia la parola v = 1101000 di K 7 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 ⇒ x2 v(x) = x2 + x3 + x5 ;
π 3 (v) = 0001101 ⇒ x3 v(x) = x3 + x4 + x6
π 4 (v) = 1000110 ⇒ x4 v(x) = x4 + x5 + x7 mod (x7 + 1) = 1 + x4 + x5 ;
π 5 (v) = 0100011 ⇒ x5 v(x) = x5 + x6 + x8 mod (x7 + 1) = x + x5 + x6 ;
113
5.4 Codice ciclico e polinomi di K n−1
π 6 (v) = 1010001 ⇒ x6 v(x) = x6 + x7 + x9 mod (x7 + 1) = 1 + x2 + x6 .
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 può esprimersi
mediante una combinazione lineare degli elementi di S, cioè:
£
¤
c(x) = a0 v(x) + a1 xv(x) + a2 x2 v(x) + ... + an−1 xn−1 v(x) mod (xn + 1) =
= (a0 +a1 x+a2 x2 +...+an−1 xn−1 )v(x) mod (xn +1) = a(x)v(x) mod (xn +1). (5.4)
Nella (5.4) si è determinato il polinomio a(x) = a0 + a1 x + a2 x2 + ... + an−1 xn−1 di
grado n − 1 che permette di enunciare il seguente lemma.
Lemma 2 Se C è 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
114
5.5 Matrice generatrice
5.5
Matrice generatrice
Consideriamo un codice ciclico e lineare C dove ogni sua parola ha una rappresentazione 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.
È 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 0 (x). Se
si considera la somma delle due parole, quindi anche dei due polinomi, si ottiene
c(x) = g(x) + g 0 (x) e per la linearità di C si ha che c(x) ∈ C, inoltre poichè la
somma dei termini di grado k è zero (xk + xk = 0) segue che deg(c(x)) < k, ciò
è assurdo in quanto per la scelta fatta, g(x) e g 0 (x) sono due polinomi di grado
minimo in C e non può esistere in C una parola di grado minore di k. Il polinomio
di minimo grado in C è unico.
Se C è 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 è un codice ciclico lineare, allora si ha che ogni parola c(x) di
C si può esprimere nel modo seguente:
c(x) = a(x)g(x).
115
(5.6)
5.5 Matrice generatrice
Dim.
Per provare il teorema basta mostrare che il polinomio generatore divide ogni parola
di C. Supponiamo per assurdo che esista una parola c(x) ∈ C che non è divisibile
per g(x), allora si ha che:
c(x) = a(x)g(x) + r(x),
dalla quale è possibile ottenere:
r(x) = a(x)g(x) + c(x).
Per il lemma 2 si ha che a(x)g(x) è una parola di C ed inoltre per la linearità di C
si ha che a(x)g(x) + c(x) ∈ C ne segue che anche r(x) ∈ C, ma questo è 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−1 g(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
(cioè g(x) è un divisore per ogni parola c(x) in C).
116
5.5 Matrice generatrice
Dim.
Il polinomio g(x) ha grado n − k, i polinomi g(x), xg(x), ..., xk−1 g(x) hanno rispettivamente grado n − k, n − k + 1, ..., n − 1, sono diversi dal polinomio nullo e nessuno
di essi può essere espresso come combinazione lineare dei precedenti essendo questi
tutti di grado inferiore, quindi, per un teorema di Algebra lineare, essi sono linearmente indipendenti. Per il teorema 29 si ha che ogni parola c(x) di C si può scrivere
come c(x) = a(x)g(x), ciò prova il punto 3 del teorema ed inoltre i k polinomi g(x),
xg(x), ..., xk−1 g(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;
x2 g(x) = x2 + x3 + x5 ⇒ 0011010;
x3 g(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−1 g(x), si
può definire la matrice generatrice del codice C nella seguente forma:
117
5.5 Matrice generatrice


g(x)


 xg(x)


 x2 g(x)

G=

.



.


xk−1 g(x)







.






(5.7)
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 è individuata dai polinomi:
g(x) = 1 + x2 ⇒ 1010
xg(x) = x + x3 ⇒ 0101.
La matrice generatrice di C è:

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 è quello di individuare il suo polinomio generatore g(x).
Diverse sono le tecniche utilizzate e i due teoremi seguenti danno indicazioni su
alcune proprietà del polinomio generatore.
Teorema 31 Se g(x) è il polinomio generatore di un codice lineare ciclico C di
lunghezza n, allora g(x) divide 1 + xn cioè 1 + xn = g(x)f (x) e vale il viceversa.
118
5.5 Matrice generatrice
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 ). Poichè ogni polinomio deve essere considerato in modulo
(1 + xn ) è 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 poichè g(x) è il polinomio di grado
minimo in C, allora r(x) deve essere il polinomio nullo.
2
Teorema 32 Il polinomio generatore g(x) del più piccolo codice lineare ciclico C,
di lunghezza n e contenente la parola corrispondente a v(x), è 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 può 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) è 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 è 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.
119
5.6 Sindrome e matrice di parità
5.6
Sindrome e matrice di parità
Supponiamo sia stata ricevuta la parola w, corrispondente a w(x), e che sia stata 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 quantità:
s(x) = w(x) mod (g(x)).
(5.8)
Poichè g(x) ha grado n−k, allora la sindrome s(x) ha grado minore di n−k e ad essa
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 è s(x) = 0. Se invece w(x) ∈
/ C,
allora, poichè 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. Ciò comporta che la sindrome della parola ricevuta 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 parità Hn×n−k la matrice la cui i-esima riga, ri , è la parola
di lunghezza n − k corrispondente al polinomio:
ri (x) = xi mod (g(x))
La matrice di parità è:
120
per
0 ≤ i ≤ n − 1.
5.6 Sindrome e matrice di parità


x0


 x


 x2

H=
 .



 .

xn−1







 mod (g(x)).






(5.9)
Se w è la parola ricevuta, poichè w(x) = v(x) + e(x) la sindrome polinomiale si può
ottenere anche mediante la matrice H nel seguente modo:
P
i
w · H = (v + e) · H ≡ n−1
i=0 (vi + ei )x mod (g(x)) =
P
Pn−1
i
i
= n−1
i=0 vi x mod (g(x)) +
i=0 ei x mod (g(x)) =
P
i
= n−1
i=0 ei x 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 parità 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 è k = 4. Costruiamo la matrice di parità nel
modo seguente:
r0 (x) = 1 mod (g(x)) = 1 ⇔ 100;
r1 (x) = x mod (g(x)) = x ⇔ 010;
121
5.6 Sindrome e matrice di parità
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 parità è:

 1 0

 0 1



 0 0


H= 1 1


 0 1


 1 1


1 0
122

0 

0 



1 


0 .


1 


1 


1
Capitolo 6
Campi finiti e codici 2 - BCH
In questo capitolo è definita la nozione di campo finito. La trattazione non sarà
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 è un “campo”?
Un campo è un insieme numerico C su cui sono definite due operazioni algebriche
binarie di cui la prima, generalmente chiamata somma (+), risulta essere un gruppo commutativo e la seconda, chiamata prodotto (×), risulta anch’essa un gruppo
commutativo sull’insieme C −{0}, cioè l’insieme numerico C con l’esclusione dell’elemento 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.
123
6.1 Polinomio primitivo
Nel capitolo precedente si è definita una corrispondenza tra le parole di K n e i
polinomi di K[x] in modulo xn + 1, cioè i polinomi di K[x]n−1 . È evidente che per
tali polinomi vale la classica operazione di somma e rispetto a tale operazione si ha
che K[x]n−1 è un gruppo abeliano con elemento neutro il polinomio nullo, l’inverso
di un qualunque polinomio g(x) è sè stesso. L’operazione di somma di due polinomi
di K[x]n−1 è equivalente all’operazione di somma definita precedentemente in K n
come si vede nell’esempio seguente.
Esempio 1
Siano in K 4 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 K 4 corrisponde alla parola 0010.
6.1
Polinomio primitivo
Un polinomio g(x) si dice irriducibile se esso è divisibile solo per 1 e per se stesso,
in caso contrario è detto riducibile. Nell’esempio seguente sono elencati una serie
di polinomi che sono sia riducibili che irriducibili.
124
6.1 Polinomio primitivo
Esempio 2
1. x è irriducibile.
2. x + 1 è irriducibile.
3. x2 è evidentemente riducibile.
4. x2 + 1 è riducibile in quanto si può esprimere come (x + 1)2 .
5. x2 +x+1 è irriducibile in quanto non si può esprimere come prodotto di due polinomi
di primo grado.
6. x3 +x+1 è irriducibile in quanto non si può esprimere come prodotto di un polinomio
di primo grado e un polinomio di secondo grado.
7. x4 + x + 1 è irriducibile.
8. x4 + 1 è riducibile in quanto può 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 è 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 è 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 è divisibile x3 + 1.
125
6.1 Polinomio primitivo
Quindi h(x) è 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) è un polinomio irriducibile e primitivo.
126
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 poichè:
x5 + 1 = (1 + x)(1 + x + x2 + x3 + x4 ),
allora h(x) divide x5 + 1 ed esso non è un polinomio primitivo.
6.2
Campi finiti di Galois
Si considerino i polinomi di K[x] in modulo xn + 1 e definiamo in essi la classica
operazione di prodotto tra polinomi, cioè se f (x) e g(x) sono due polinomi arbitrari
non nulli di K[x] allora il loro prodotto è:
f (x) · g(x) mod xn + 1
e deve appartenere a K[x]n−1 − {0}, cioè 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 mostrerà che il prodotto definito precedentemente non rispetta
sempre tale proprietà.
Esempio 6
Proviamo ad utilizzare l’operazione di moltiplicazione sui polinomi in modulo 1 + x4 cioè
sui polinomi di K[x]3 equivalenti alle parole di K 4 . Sia la parola v = 0101 corrispondente
al polinomio v(x) = x + x3 e consideriamo il prodotto v(x) · v(x):
127
6.2 Campi finiti di Galois
(x + x3 )2 = x2 + x6 .
Consideriamo adesso tale polinomio in modulo x4 + 1 cioè:
quindi,
(x + x3 )2 = (x2 + x6 )mod(x4 + 1) = 0.
Il problema presentato nell’esempio 7 è legato al fatto che 1 + x4 non è 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 è possibile usare la seguente scrittura:
128
6.2 Campi finiti di Galois
β i = xi mod(h(x)).
(6.1)
Si noti che h(x), poichè è 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, ciò accade solo se j − i è un multiplo
di 2n − 1, ma essendo 1 ≤ j − i ≤ 2n − 2 < 2n − 1 questo è 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 può
mettere in corrispondenza con le parole di K n , 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.
129
6.2 Campi finiti di Galois
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 ) è 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:
130
6.2 Campi finiti di Galois
(0110) · (1101) = β 5 · β 7 = β 12 = 1111.
Ciò è 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 ) è detto primitivo se ogni sua potenza m, con 1 ≤ m <
2n − 1, è diversa da 1 (αm 6= 1).
Si definisce ordine di un elemento α 6= 0 di GF (2r ) il più 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 β è una sua soluzione in GF (24 ).
p(β) = 1 + β 3 + β 4 = 1000 + 0001 + 1100 = 0101 = β 9 6= 0000,
quindi β non è una radice di p(x).
Consideriamo adesso l’elemento β 7 ∈ GF e vediamo se esso è 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 è soluzione di p(x).
131
6.3 Polinomio minimo
6.3
Polinomio minimo
Se α è 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 α è 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 cioè in termini di elementi di GF (2n ):
a0 + a1 α + a2 α2 + a3 α3 + ... + ar αn = 0.
Tale combinazione lineare esiste poichè ogni elemento della combinazione lineare
rappresentata nell’equazione precedente corrisponde a una parola di K n 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) = a0 1 + a1 α + a2 α2 + a3 α3 + a4 α4 = a0 β 0 + a1 β 3 + a2 β 6 + a3 β 9 + a4 β 12 =
= a0 1 + a1 x3 + 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 K 4 si ha:
132
6.3 Polinomio minimo
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
 a +a =0


2
4




 a +a +a +a =0
1
2
3
4
quindi:



a0 = a4





 a3 = a4
 a =a


2
4




 a =a
1
4
Per determinare una combinazione non banale è necessario porre a4 = 1 e quindi si ha che
a0 = a1 = a2 = a3 = a4 = 1 e il polinomio minimo è:
m3 (x) = 1 + x + x2 + x3 + x4 .
Il teorema seguente mostra le principali proprietà dei polinomi minimi.
Teorema 33 Sia α 6= 0 un elemento di GF (2n ) e sia mα (x) il suo minimo polinomio si ha:
1. Il polinomio minimo mα (x) è irriducibile.
2. Se f (x) è un polinomio tale che f (α) = 0, allora mα (x) divide f (x).
133
6.3 Polinomio minimo
3. Il polinomio minimo mα (x) è unico.
n −1
4. Il polinomio minimo mα (x) divide x2
+ 1.
Dim.
1. Supponiamo per assurdo che mα (x) è riducibile, in tal caso esso può essere scritto come mα (x) = q(x)p(x), poichè 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 è assurdo in quanto mα (x) è il polinomio di
grado minore che ha α come radice.
2. Supponiamo che mα (x) non divide f (x), allora si può 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,
ciò è assurdo perchè il polinomio r(x) ha α come radice ed ha grado inferiore
di mα (x).
3. Se esistono due polinomi minimi m0α (x) e mα (x), per la parte seconda del
teorema si ha che mα (x) divide m0α (x) e m0α (x) divide mα (x), ciò vuol dire che
mα (x) = m0α (x) e il polinomio minimo è unico.
4. Poichè α è un elemento di GF (2n ), allora esiste un i per cui α = β i ed inoltre:
n −1
α2
n −1
+ 1 = (β i )2
n −1
Pertanto, mα (x) divide x2
n −1
+ 1 = (β 2
+ 1.
)i + 1 = 1i + 1 = 1 + 1 = 0.
2
134
6.3 Polinomio minimo
La seguente proprietà permette di ottenere informazioni sulle radici dei polinomi
minimi.
Proprietà 9 Sia f (x) un polinomio in K allora si ha che:
f (x)2 = f (x2 ).
(6.5)
Dim.
La proprietà è dimostrata dalle seguenti eguaglianze:
2
f (x) =
à n
X
!2
ai x
i=0
i
=
n
X
i 2
ai (x ) =
i=0
n
X
ai (x2 )i = f (x2 ).
i=0
2
La proprietà (9) permette di affermare che se α è una radice del polinomio f (x) cioè
f (α) = 0, allora anche f (α2 ) = 0, quindi α2 è una radice di f (x), così come lo è
n−1
anche α4 e in generale α2
.
n−1
Teorema 34 Le radici del polinomio minimo mα (x) sono α, α2 , α4 , · · · , α2
, in
particolare i polinomi m1 (x) e m3 (x) hanno n radici distinte e rispettivamente sono:
n−1
},
n−1 )
}.
{β, β 2 , β 4 , ..., β 2
{β 3 , β 6 , ..., β 3(2
135
(6.6)
6.3 Polinomio minimo
Dim.
La prima parte della proprietà segue dalla proprietà 9. Sia il polinomio minimo
i
j
m1 (x), consideriamo due soluzioni β 2 e β 2 della (6.6) e supponiamo per assurdo
i
j
che β 2 = β 2 con i > j e 0 ≤ i, j ≤ n − 1, allora si ha:
j
i
j
j
β 2 · β 2 −2 = β 2 ,
equivalente all’equazione:
i
j
β 2 −2 = 1.
(6.7)
La (6.7) vale se 2i − 2j = k(2n − 1), cioè 2i − 2j è un multiplo di 2n − 1, ma poichè
i e j variano tra 0 e n − 1, allora si ha:
2i − 2j ≤ 2n−1 − 1 < 2n − 1.
Ciò mostra che 2i − 2j non è 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 )
136
6.4 Codici di Hamming
La precedente tabella individua le soluzioni di tutti i polinomi minimi di GF (24 ).
6.4
Codici di Hamming
I codici di Hamming sono codici perfetti 1-correttori che hanno lunghezza l = 2n −1 e
le righe della loro matrice di parità hanno lunghezza n. In questa sezione è mostrato
che le 2n − 1 righe della matrice di parità 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 K n .
La matrice di parità di un codice di Hamming di lunghezza l = 2n − 1 può essere
espressa nel seguente modo:

H(2n −1)×r








=









1
β
β2
.
βi
.








.








(6.8)
n −2
β2
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 K 3 010,
ricordando poi che xi mod p(x), si ottiene:
137
6.4 Codici di Hamming


1




 β 




 2 
 β 




H =  β3 




 β4 




 β5 




6
β

↔
 1 0

 0 1



 0 0


H= 1 1


 0 1


 1 1


1 0

0 

0 



1 


0 .


1 


1 


1
Quanto detto precedentemente si può riassumere mediante il seguente teorema.
Teorema 35 Un polinomio primitivo di grado n è 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. Poichè
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 37 e 38 si ha che mα (x) è divisore di ogni
parola c(x) appartenente a C ed inoltre è 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) sarà 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
138
6.4 Codici di Hamming
Cerchiamo di individuare una tecnica utile all’individuazione e alla correzione degli
errori per i codici di Hamming.
Se c(x) è la parola che è stata inviata e w(x) la parola ricevuta, allora l’errore e(x)
è definito nel seguente modo:
w(x) = c(x) + e(x).
Se il polinomio generatore g(x) = mα (x) è il polinomio primitivo, allora α è radice
di tale polinomio (g(α) = 0) e si ha che:
w(α) = c(α) + e(α) = 0 + e(α) = αj ,
dove αj è un elemento del campo GF . Pertanto il polinomio che rappresenta l’errore
è e(x) = xj e la correzione della parola ricevuta si può scrivere come:
c(x) = w(x) + xj .
Poichè si ha che:
c(α) = w(α) + αj = αj + αj = 0.
Quindi la parola ottenuta adoperando questa tecnica è una parola del codice. È
importante notare che l’aggiunta del polinomio xj a w(x) corrisponde in termini di
parole di K n 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:
139
6.5 Codici 2-BCH
w(β) = 1 + β 2 + β 3 + β 6 = 100 + 001 + 110 + 101 = 110 = β 3
L’errore in questo caso è dato dal polinomio e(x) = x3 , quindi la correzione della parola
ricevuta è:
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 è 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 è 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. Poichè n = 2r − 1 e g(x) divide 1 + xn ,
allora g(x) è il polinomio generatore di un codice ciclico.
Si consideri un campo GF (2r ) e il codice BCH 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 parità H di tali codici è definita nel modo seguente:
140
6.6 Schema di codifica per codici 2-BCH



















β0
β0
β
β
β2
β6
.
.
βi
β 3i
.
.
r −2
β2

















3
(6.10)
r −2)
β 3(2
Poichè β i è un elemento di GF (2r ), esso rappresenta una parola di lunghezza r, quindi H è una matrice (2r − 1) × (2r). Inoltre, poichè il deg(m1 (x)) = r = deg(m3 (x))
ne segue che il grado di g(x) = m1 (x)m3 (x) è n − k = 2r, pertanto il codice ha
dimensione k = n − 2r = 2r − 1 − 2r. Si può dimostrare (ma non verrà fatto in tale
trattazione) che la distanza di tali codici è d = 5.
6.6
Schema di codifica per codici 2-BCH
Consideriamo che w è la parola ricevuta e w(x) il polinomio ad essa associato in una
trasmissione che utilizza un codice 2-BCH. Ricordando che tale codice è un codice
2- correttore, allora la sindrome di w è:
h
w·H =
i
3
w(β), w(β )
h
=
i
s1 , s3
(6.11)
dove s1 e s3 sono due parole di lunghezza r. Nella sequenza successiva è illustrato
la tecnica che permette di individuare l’algoritmo di decodifica dei codici 2-BCH.
• Se non vi sono errori nella trasmissione di w, cioè se w ∈ C, allora si ha che
w · H = 0 e quindi s1 = s3 = 0.
• Se si è nel caso in cui vi è solo un errore nella trasmissione della parola w,
allora l’errore utilizzato per correggere w(x) è e(x) = xi dato che tale errore,
141
6.6 Schema di codifica per codici 2-BCH
se esso è nella i-esima componente di w, individua la i-esima riga di H nel
calcolo della sindrome di w:
i
h
w·H =e·H =
i
β ,β
i
h
=
3i
(6.12)
s1 , s3
Tale caso si verifica se calcolando la sindrome si ha che s31 = s3 .
• Se si è 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(x) = xi +xj . Infatti la sindrome di w, per il teorema 18 del capitolo 3,
è la combinazione lineare delle righe i-esima e j-esima di H, cioè:
h
w·H =e·H =
i
i
j
3i
β + β ,β + β
3j
h
=
i
s 1 , s3
.
Consideriamo il seguente sistema di equazioni risultante:

 β i + β j = s1
 β 3i + β 3j = s .
3
Poichè:
β 3i + β 3j = (β i + β j )(β 2i + β i+j + β 2j ),
ed inoltre:
s21 = (β i + β j )2 = β 2i + β 2j ,
allora è possibile scrivere:
s3 = β 3i + β 3j = (β i + β j )(β 2i + β 2j + β i+j ) = s1 (s21 + β i+j ),
142
(6.13)
6.6 Schema di codifica per codici 2-BCH
Da cui si ottiene:
s3
+ s21 = β i+j .
s1
È 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 può essere anche scritto mediante s1 e s3 , cioè:
x2 + s1 x + (
s3
+ s21 ) = 0
s1
(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), cioè non
si trovano soluzioni della (6.14), allora vuol dire che è accaduto un errore con peso
maggiore di due ed è necessario richiedere la ritrasmissione.
Esempio 12
Sia w la parola ricevuta la cui sindrome è 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
β8
+ s21 = 11 + β 22 = β 8 β −11 β 15 + β 7 β 15 = β 12 + β 7 = 1111 + 1101 = 0010 = β 2 ,
s1
β
e polinomio di individuazione di errore è:
x2 + β 11 x + β 2 = 0,
le cui soluzioni numeriche, determinate mediante sostituzione, sono β i = β 4 e β j = β 13 .
143
Capitolo 7
Codici Reed Solomon
7.1
Introduzione
In questo capitolo sono presentati i codici BCH, ma prima di trattare tali codici
consideriamo l’insieme dei polinomi appartenenti a GF (2r )[x], cioè i polinomi del
tipo
a0 + a1 x + a2 x2 + · · · + am xm ,
(7.1)
dove i coefficienti ai ∈ GF (2r ) per 0 ≤ i ≤ m. È chiaro che il polinomio della (7.1),
se ha grado minore di 2r − 1, può essere messo in corrispondenza biunivoca con la
parola di lunghezza n = 2r − 1 a0 a1 a2 · · · an .
Esempio 1
Il polinomio f (x) = 1 + β 2 x + β 4 x3 + x5 a coefficienti in GF (23 ) è messo in corrispondenza
biunivoca con la parola di lunghezza n = 23 − 1 = 7 1β 2 0β 4 010
144
7.1 Introduzione
Sia un α ∈ GF (2r ), è evidente che il polinomio minimo di α in GF (2r )[x] è mα =
x + α. Se α1 , α2 , α3 , ..., αt sono t elementi distinti, diversi da zero e appartenenti a
GF (2r ) e se C è un codice ciclico lineare di lunghezza n = 2r − 1, avente la proprietà
che ogni sua parola c(x) ∈ C ha αi , per 1 ≤ i ≤ t, come radice, cioè c(αi ) = 0, allora,
per quanto detto nei capitoli precedenti, si ha che il polinomio generatore di C è
g(x) = (x + α1 )(x + α2 )...(x + αt ) e tale polinomio ha grado t = n − k. Ogni parola
di c(x) ∈ C, inoltre, può essere rappresentata mediante il prodotto c(x) = a(x)g(x)
dove a(x) è un polinomio di grado minore di n − deg(g(x)), si lascia poi al lettore
la prova che g(x) divide il polinomio xn + 1.
Teorema 37 Se il polinomio generatore g(x) di un codice ciclico lineare, di lunghezza n = 2r − 1, ha grado deg(g(x)) = n − k, allora la dimensione di tale codice
è k, le sue parole hanno caratteri in GF (2r ), la sua cardinalità è |C| = 2rk e la sua
matrice generatrice è:


 g(x) 


 xg(x) 


G=
.
 ... 




xk−1 g(x)
(7.2)
Dim.
Tutte le implicazioni del teorema, ad eccezione della cardinalità del codice C, seguono dal teorema 30. La cardinalità di C è 2rk perchè ogni parola del codice può
essere espressa mediante una combinazione lineare delle k parole presenti in G nel
seguente modo
145
7.1 Introduzione
c(x) = a0 g(x) + a1 xg(x) + a2 x2 g(x) + · · · + ak−1 xk−1 g(x),
e ogni ai ∈ GF (2r ) per 0 ≤ i ≤ k − 1, quindi si ha che |C| = 2rk .
(7.3)
2
Esempio 2
Sia il campo GF (23 ) generato dal polinomio primitivo 1 + x + x3 consideriamo il codice
ciclico di lunghezza n = 7 e polinomio generatore:
g(x) = (β + x)(β + x2 )
= β 3 + β 4 x + x2 .
(7.4)
Tale codice ha matrice generatrice:

β3 β4 1 0 0 0


 0 β3 β4 1 0 0


3
4
G=
1 0
0 0 β β


 0 0 0 β3 β4 1

0 0 0 0 β3 β4

0


0


0



0

1
Il seguente lemma è in questo corso ritenuto uno strumento tecnico che sarà utilizzato
in seguito sia per ricavare la distanza dei codici BCH, che negli algoritmi di decodifica
utilizzati da tali codici.
Lemma 3 Se α1 , α2 , α3 , ..., αt sono t elementi diversi da zero appartenenti a GF (2r ),
allora si ha che:
146
7.1 Introduzione

2
1 α1 α1

1 α2 α2
2

det  . .
.
 .. ..
..


1 αt αt2

...
α1t−1 

Y
. . . α2t−1 

=
(αi + αj ).

.. 
...
.  16j<i6t

t−1
. . . αt
(7.5)
2
Esempio 2
Sia il campo di Galois GF (24 ) generato dal polinomio generatore x4 + x + 1, allora la
seguente matrice ha determinante:


2
4
β 
1 β


2
7
2
10
7
10
12 4 6
7
7
det 
β 14 
 = (β + β )(β + β )(β + β ) = β β β = β
1 β


1 β 10 β 5
Il seguente teorema permette di individuare un’importante disuguaglianza tra la
distanza di un codice BCH e il numero delle radici del polinomio generatore.
Teorema 38 Se g(x) = (β m+1 + x)(β m+2 + x)(β m+3 + x) . . . (β m+δ−1 + x), con
β i ∈ GF (2r ), m + 1 6 i 6 m + δ − 1, è il polinomio generatore di un codice BCH di
lunghezza n = 2r − 1, allora si ha che d > δ
Dim.
La matrice di parità per tale codice è:
147
7.1 Introduzione


1
1

 m+1
 β
β m+2


2
(m+1)2
H=
β (m+2)
 β

..
..

.
.


n−1
n−1
β (m+1)
β (m+2)
...
...
...
...
1
β
m+δ−1
2
β (m+δ−1)
..
.
n−1





,





(7.6)
. . . β (m+δ−1)
dove la matrice di parità H è una matrice n × (δ − 1). Per provare il teorema è necessario provare che comunque si determinano δ −1 righe in H esse sono linearmente
indipendenti.
Si determinino in H δ − 1 righe arbitrarie, esse permettono di determinare una
matrice quadrata A di dimensione (δ − 1) × (δ − 1)


m+1 j1
m+2 j1
)
(β
)
 (β

 (β m+1 )j2
(β m+2 )j2

A=
..
..

.
.


(β m+1 )jδ−1 (β m+2 )jδ−1
...
...
(β
m+δ−1 j1
(β
m+δ−1 j2
)
...




.



)
..
.
(7.7)
. . . (β m+δ−1 )jδ−1
Se si calcola il determinante di A e si tengono conto delle proprietà dei determinanti,
si ha che il determinante di A è uguale al determinante della matrice B moltiplicato
per la quantità (β m+1 )j1 +j2 +...+jδ−1 , dove B è ottenuta da A dividendo le sue righe
rispettivamente per le quantità (β m+1 )j1 , · · · (β m+1 )jδ−1 .


j1
(β m+1 )j1 +j2 +...+jδ−1
j1 2
j1 δ−2
(β )
. . . (β )

1 β


j2 2
j2 δ−2 
1 β j 2
(β
)
.
.
.
(β
)


· det  .
.
..
..
..
..

 ..
.
.
.
.




jδ−1 δ−2
jδ−1 2
jδ−1
)
) . . . (β
(β
1 β
148
(7.8)
7.2 Codici Reed Solomon
Si ha che il determinante di A è uguale a (β m+1 )j1 +j2 +...+jδ−1
Q
(βij + βkj ) ed è certa-
mente diverso da zero, infatti (β m+1 )j1 +j2 +...+jδ−1 e |B| sono rispettivamente diversi
da zero, il primo perchè è un elemento diverso da zero di GF (2r ), mentre il secondo
per il lemma 3 perchè gli elementi β j , con m + 1 ≤ j ≤ m + δ − 1 sono a due a due
distinti e diversi da zero, quindi d > δ.
7.2
2
Codici Reed Solomon
I codici BCH definiti dal teorema 38 individuano i codici di Reed - Solomon
indicati anche con la simbologia RS(2r , δ) e per tali codici vale il seguente teorema
utile a definire i parametri n, k e d.
Teorema 39 Se C è un codice di Reed-Solomon RS(2r , δ), allora si ha che:
1. n = 2r − 1
2. k = 2r − δ
3. d = δ
4. |C| = 2rk
149
7.2 Codici Reed Solomon
Dim.
1. La dimostrazione è banale.
2. Il grado di g(x) è n − k = δ − 1, quindi segue che k = 2r − δ.
3. Per il teorema 38 si ha che d > δ, ma per il teorema del limite di Singleton si
ha che d − 1 6 n − k, sostituendo i valori di n e k in tale disuguaglianza si ha
che d 6 δ e quindi d = δ.
4. La dimostrazione è banale.
2
Poichè d = δ si ha che n−k = δ −1 = d−1 e ciò vuol dire che i codici Reed-Solomon
sono dei codici MDS .
La problematica legata alla rappresentazione delle parole di un codice RS(2r , δ) all’interno di una struttura hardware che utilizza simbologie binarie impone una nuova
rappresentazione di tali parole con parole binarie equivalenti. Tale rappresentazione
binaria può essere ottenuta sostituendo i caratteri appartenenti a GF (2r ) nelle parole del codice RS(2r , δ) con corrispondenti parole binarie di lunghezza r, quindi una
parola di lunghezza 2r −1 del codice RS(2r , δ), dopo tale sostituzione avrà lunghezza
r(2r − 1).
Esempio 2
Sia il campo GF (22 ) generato dal polinomio primitivo h(x) = 1 + x + x2 , tale campo ha
quattro parole la cui rappresentazione binaria è
GF (22 ) = {0 = 00; 1 = 10; β = 01; β 2 = 11}.
150
(7.9)
7.2 Codici Reed Solomon
00
000
00 00 00
10
β10
01 10 00
β0
β 2 β0
11 01 00
β 20
1β 2 0
10 11 00
01
0β1
00 01 10
11
ββ 2 1
01 11 10
β1
β 2 01
11 00 10
β 21
111
10 10 10
0β
0β 2 β
00 11 01
1β
βββ
01 01 01
ββ
β 2 1β
11 10 01
β 2β
10β
10 00 01
0β 2
01β 2
00 10 11
1β 2
β0β 2
01 00 11
ββ 2
β 2β 2β 2
11 11 11
β 2β 2
1ββ 2
10 01 11
Tabella 7.1: Parole binarie di un codice RS(4, 2)
151
7.2 Codici Reed Solomon
Sia g(x) = β + x il polinomio minimo che genera il codice RS(4, 2) avente lunghezza n = 3,
dimensione k = 2 e distanza d = 2, inoltre |C| = 16. La matrice generatrice di tale codice
è


β 1 0

G=
0 β 1
La tabella 7.1 da’ una rappresentazione delle parole di RS(4, 2). In essa nella prima colonna
sono rappresentate tutte le possibili combinazioni lineari delle righe di G, nella seconda
colonna le parole di RS(4, 2) sono espresse mediante l’alfabeto individuato dagli elementi
di GF (22 ) e nella terza colonna le parole sono espresse mediante l’alfabeto binario. In
quest’ultima colonna gli elementi di GF (22 ) sono sono stati sostituiti da parole binarie di
lunghezza due secondo le corrispondenze in GF (22 ) (7.9).
Consideriamo adesso in un codice RS(2r , δ) tutte le sue parole che hanno gli ultimi
s caratteri uguali a zero. Una qualunque combinazione lineare di queste parole deve
generare una parola avente gli ultimi s caratteri uguali a zero, allora è possibile
eliminare in tali parole gli ultimi s caratteri ottenendo così un sotto codice C(s) di
RS(2r , δ), detto codice s-ridotto, avente lunghezza n0 = 2r −1−s. Dalla tabella 7.1
si può vedere che le uniche parole del codice RS(4, 2) che hanno l’ultimo carattere
uguale a zero sono {000; β10; β 2 β0; 1β 2 0}, da esse si ricava il codice 1-ridotto:
C(1) = {00; β1; β 2 β; 1β 2 }.
Teorema 40 Sia un codice RS(2r , δ) e sia C(s) un suo codice s-ridotto avente
parametri (n0 , k 0 , d0 ), allora si ha che
1. La lunghezza n0 è 2r − 1 − s;
152
7.3 Correzione di un codice RS(2r , δ)
2. La matrice generatrice di C(s) è






0
G =



g(x)


xg(x) 



...


k−s−1
x
g(x)
(7.10)
3. La dimensione k 0 è 2r − δ − s
4. La distanza d0 è δ
5. |C(s)| = 2rk
0
Dim.
Per provare tale teorema è solo necessario provare che la distanza di C(s) è uguale a
δ. È chiaro che essendo C(s) un sotto codice di RS(2r , δ), allora si ha che d0 ≥ d = δ.
Per il teorema 22 si ha che d0 − 1 ≤ n0 − k 0 , utilizzando i valori di n0 e k 0 , si ha che
d0 ≤ n0 − k 0 + 1 = δ, quindi d0 = δ.
2
Il teorema precedente permette di determinare un codice di minore lunghezza del
codice RS(2r , δ), che ha una dimensione minore, ma che mantiene la distanza di
RS(2r , δ), inoltre poichè d0 − 1 = n0 − k 0 = δ − 1, allora si ha che tale codice è anche
un codice M DS.
7.3
Correzione di un codice RS(2r , δ)
Il problema dell’algoritmo di correzione dei codici 2-BCH era legato all’individuazione dei bits che erano stati alterati in trasmissione. Tale problema permetteva di
153
7.3 Correzione di un codice RS(2r , δ)
correggere la parola ricevuta modificando i bits alterati da 0 a 1 oppure da 1 a 0.
Con i codici BCH non solo è necessario individuare la posizione dei caratteri alterati, ma è anche necessario determinare gli elementi di GF (2r ) che devono essere
sommati a tali caratteri per ottenere la correzione della parola. Nella correzione
degli errori di un codice BCH si ha quindi la necessità non solo di individuare la posizione dell’errore mediante una quantità detta localizzatore di errore, ma anche
la grandezza necessaria per effettuare la correzione, ad esempio il localizzatore di
errore che assume valore β i individua la posizione i + 1, mentre la grandezza β m è
la quantità che bisogna aggiungere al carattere i + 1-esimo della parola ricevuta che
non appartiene al codice
Esempio 3
Sia il campo di Galois GF (23 ) avente polinomio primitivo 1+x+x3 e sia v(x) = β 3 β 4 β 0 0000
la parola inviata e w(x) = β 3 β 4 β 5 0000. È evidente che è stato alterato il terzo carattere
della parola v(x) cioè il localizzatore di errore è β 2 , mentre la quantità che bisogna aggiungere al terzo carattere è la grandezza β 4 = β 0 + β 5 quindi la parola errore che deve essere
sommata a w(x) è e(x) = 00β 4 0000.
Sia un codice Reed-Solomon RS(2r , δ), poichè ha distanza d = δ esso è un codice
t = b δ−1
c correttore. Sia w(x) una parola ricevuta non appartenente al codice e
2
siano a1 a2 . . . ae i localizzatori di errore e b1 b2 . . . be le grandezze ad essi legati, dove
e ≤ t è il numero di caratteri che sono stati alterati in w(x), cioè poniamo ai = 0
per e + 1 6 i 6 t .
La sindrome di w(x) è s = sm+1 sm+2 . . . sm+δ−1 dove sj = w(β j ), m + 1 6 j 6
m + δ − 1 e con β j radici del polinomio generatore g(x).
Per quanto detto precedentemente otteniamo
154
7.3 Correzione di un codice RS(2r , δ)
w(β j ) = v(β j ) + e(β j ) = e(β j ) =
X
(bi aji ),
(7.11)
i
un sistema non lineare avente 2e incognite e δ − 1 equazioni. Tale sistema essendo
non lineare è di difficile soluzione. Cerchiamo di risolvere il problema individuando
un polinomio che permette di individuare i localizzatori di errore. Tale polinomio
sarà del tipo:
σA (x) = (a1 + x)(a2 + x) . . . (ae + x),
(7.12)
che può anche essere scritto nel seguente modo
σA (x) = σ0 + σ1 x + . . . + σe−1 xe−1 + xe .
(7.13)
È possibile moltiplicare ambo i membri del polinomio (7.13) per le quantità bi aji ,
con 1 6 i 6 e, si ottengono le seguenti equazioni:
bi aji σA (x) = σ0 bi aji + σ1 bi aji x + . . . + σe−1 bi aji xe−1 + bi aji xe .
(7.14)
Se in σA si pone x = ai , allora si ha che σ(ai ) = 0, per 1 ≤ i ≤ e, e dall’equazione
(7.14) si ha che
0 = σ0 bi aji + σ1 bi aj+1
+ . . . + σe−1 bi aij+e−1 + bi aij+e .
i
Sommando le (7.15) rispetto a i si ottiene
155
(7.15)
7.3 Correzione di un codice RS(2r , δ)
0 = σ0
t
X
bi aji
+ σ1
i=1
t
X
bi aj+1
i
+ . . . + σe−1
i=1
t
X
bi aij+e−1
i=1
+
t
X
bi aij+e ;
i=1
0 = σ0 sj + σ1 sj+1 + . . . + σe−1 sj+e−1 + sj+e ;
(7.16)
sj+e = σ0 sj + σ1 sj+1 + . . . + σe−1 sj+e−1 .
L’ultima equazione delle (7.16) definisce, per m + 1 6 j 6 m + e, un sistema di
equazioni lineari nell’incognite σi , con 1 ≤ i ≤ e − 1, che si può rappresentare in
forma matriciale nel seguente modo:





sm+1 sm+2 . . . sm+e   σ0  sm+e+1 


 

sm+2 sm+3 . . . sm+e+1   σ1  sm+2+e 


 

 .
 .  =  . .
.
.
.
 ..

 

..
..
.. 

  ..   .. 


 

sm+e sm+e+1 . . . sm+2e
σe−1
sm+2e
(7.17)
Tale sistema è un sistema di e equazioni in e incognite e la sua matrice incompleta
può essere scritta nel seguente modo:







M =





1
...
a1
...
a21
..
.
...
..
.
ae−1
...
1
|
{z
Q
6=0,

1 
m+1

...
0 
 b1 a1
e−1
ae 
1
a
.
.
.
a


1
1
..  
  ..

 .
b2 am+1
.  . .
2
.
.. 
2 
.
.
.


ae 
.
. ,
..   . .
..
 ...


.
. 
..  
e−1
 1 ae . . . ae
. 

|
{z
}
0
...
be am+1
e
6=0,ai 6=aj ,i6=j
ae−1
|
{z
}
e
6=0,det6=0
}
(ai +aj )
tale matrice ha determinante diverso da zero, quindi per il teorema di Cramer si
ha che esiste un’unica soluzione σ̄0 , σ̄1 , . . . , σ̄e−1 del sistema (7.17), tale soluzione
156
7.3 Correzione di un codice RS(2r , δ)
permette di individuare il polinomio (7.13) e quindi i localizzatori ā1 , ā2 , . . . , āe . Il
sistema (7.11) adesso è un sistema di equazioni lineari nelle incognite b1 b2 . . . be come
è rappresentato sotto.
 

m+1
ā1
ām+1
2

ām+2 ām+2
2
 1
 .
..
 ..
.


ām+e
ām+e
1
2
|
{z
...


ām+1
e
 b1 
sm+1 
  

 b2  sm+2 
. . . ām+2
e
  

.=
.
..
.. 
 ..   . . . 
.
. 
  

  

. . . ām+e
b
s
e
m+e
e
}
M 00
Tale sistema è un sistema che ha e equazioni e e incognite e, per il lemma 3, si ha
che il determinante della sua matrice incompleta è diverso da zero, quindi per il
teorema di Cramer si ha che tale sistema ammette un’unica soluzione b̄1 , b̄2 , . . . , b̄e
individuata dalle grandezze legate ai localizzatori ā1 , ā2 , . . . , āe . I localizzatori e le
grandezze determinate permettono di correggere la parola ricevuta w(x).
157
7.3 Correzione di un codice RS(2r , δ)
PUBBLICATO IN PROPRIO PRESSO IL DIPARTIMENTO DI MATEMATICA E INFORMATICA, FACOLTA’ DI INGEGNERIA, UNIVERSITA’ DI CATANIA,
IL 06/02/2008.
158
Indice analitico
alfabeto, 1
codice sistematico, 64
Algoritmo di Huffman, 15
codice univocamente decifrabile, 4
BCH, 140
BCH 2-correttori, 140
bits di parità, 64
codici 2-BCH, 141
codici di Hamming, 137
codici MDS, 84, 150
codici Reed Solomon, 149
Campi di Galois, 127
Campo di Galois, 129
capacità del canale, 26
colonna leading, 51
coset, 66
coset leader, 70
caratteri, 1
CMLD, 39
dimensione, 50
codice, 2
distanza, 30, 31, 37, 48
codice s-ridotto, 152
distanza di Hamming, 37
codice ciclico, 109, 113
disuguaglianza triangolare, 37
codice di Golay esteso , 94
efficienza del canale, 28
codice di Hamming, 91
entropia condizionata, 25
codice equivalente, 64
entropia congiunta, 24
codice esteso, 86
errore, 35, 41, 42
codice istantaneo, 5
errore polinomiale, 120
codice lineare, 47
codice ortogonale, 49
codice ottimo, 13
codice perfetto, 89
funzione di assegnazione, 2
funzione entropia, 19
generatori, 49
159
INDICE ANALITICO
grandezza, 154
shift ciclico, 109
sindrome, 71
IMLD, 39
sindrome polinomiale, 120
leading, 51
sorgente di un codice, 1
Limite di Gilbert-Varshamov, 83
teorema di Kraft, 6
Limite di Hamming, 77
teorema di McMillan, 10
Limite di Singleton, 79
localizzatore di errore, 154
lunghezza media, 2
matrice di parità, 54
matrice generatrice, 53, 117
MLD, 37
ordine di un elemento, 131
peso, 35
Polinomio di individuazione di errore, 143
polinomio generatore, 115
polinomio irriducibile, 124
polinomio minimo, 132, 135
polinomio primitivo, 125, 126
proprietà del prefisso, 5
radice, 131
ridotta parzialmente, 51
ridotta totalmente, 53
schema di codifica, 2
SDA, 74
160