Prof.ssa Carla Fiori
Lezioni di
Algebra e Teoria dei Codici
Università di Modena e Reggio Emilia
Dipartimento di Scienze Fisiche, Informatiche, Matematiche
Questo documento è stato scritto in LATEX utilizzando l’editor LYX. I diagrammi invece sono stati prodotti utilizzando XY-Pic.
Quest’opera è stata rilasciata sotto la licenza Creative Commons AttribuzioneNon commerciale-Non opere derivate 2.5 Italia. Per leggere una copia della licenza
visita il sito web
http://creativecommons.org/licenses/by-nc-nd/2.5/it/
o spedisci una lettera a Creative Commons, 171 Second Street, Suite 300, San
Francisco, California, 94105, USA. Per ulteriori informazioni si prega di contattare Emanuele Bardelli, Marco Corghi e Dario Prandi agli indirizzi <mailto:51242@
unimore.it>, <mailto:[email protected]> o <mailto:[email protected]>.
\
=
$
BY:
Alcuni diritti riservati 2006-2007
This work is licensed under the Creative Commons Attribution-NoncommercialNo Derivative Works 2.5 Italy License. To view a copy of this license, visit
http://creativecommons.org/licenses/by-nc-nd/2.5/it/
or send a letter to Creative Commons, 171 Second Street, Suite 300, San Francisco,
California, 94105, USA. For further information, please contact Emanuele Bardelli,
Marco Corghi e Dario Prandi at these e-mail addresses <mailto:51242@unimore.
it>, <mailto:[email protected]> or <mailto:[email protected]>.
\
=
$
BY:
Some Rights Reserved 2006-2007
Prefazione
Questi appunti raccolgono le lezioni del corso di Algebra e Teoria dei Codici , insegnamento fondamentale per la Laurea Magistrale in Matematica Computazionale e Modellistica, 6 cfu, 36 ore. Il docente, prof.ssa Carla Fiori, rende
reperibili questi appunti nella propria pagina web perchè siano a disposizione di
tutti gli studenti quale ausilio didattico.
i
Indice
Prefazione
i
Capitolo 1. Presentazione del corso
1. Programma del corso
2. Prerequisiti
3. Testi di riferimento
1
1
1
2
Capitolo 2. Generalità sui Codici
1. Introduzione
2. Trasmissione di un messaggio
3. Problemi di trasmissione
4. Canali di trasmissione. Canali simmetrici
5. Esempi. Codici: Fiscale, ISBN, Morse, ASCII.
3
3
4
5
7
9
Capitolo 3. Codici a Blocchi
1. Definizioni
2. Codici che rivelano e correggono errori. Distanza di Hamming.
3. Efficienza e Rapporto di separazione
4. Relazioni fra i parametri di un codice
5. (n, k)-codici, codici MDS, codici equivalenti
14
14
15
22
23
28
Capitolo 4. Codici Lineari
1. Definizioni e prime proprietà
2. Matrici generatrici
3. Codifica nei codici lineari
4. Decodifica dei codici lineari. Tabella standard
5. Codice duale e matrice di controllo
6. Decodifica dei codici lineari per sindrome
7. Codici lineari 1-correttori
8. L’enumeratore dei pesi di un codice lineare
9. Codice esteso
35
35
37
43
45
47
53
58
60
61
Capitolo 5. Codici Ciclici
1. Definizioni e proprietà
2. Polinomio generatore e matrice generatrice
3. Schemi di codifica
62
62
64
71
ii
INDICE
4. Polinomio di controllo e matrice di controllo
5. Decodifica
6. Codici BCH
iii
75
77
79
Capitolo 6. Codici di Hamming e codici perfetti
1. Definizioni e Proprietà
2. Codici di Hamming binari
3. Codici perfetti
84
84
87
88
Capitolo 7. Codici di Goppa
90
Capitolo 8. Codici correttori e gruppi di permutazioni
1. Gruppi come codici e distanza di Hamming
2. Gruppi strettamente k-transitivi
3. Uncoverings
4. Algoritmo di decodifica per gruppi strettamente k-transitivi
5. Uncovering dei gruppi di Mathieu M11 e M12
6. Estensione a gruppi non strettamente k-transitivi
7. Simboli ripetuti
8. Ottimizzazione
91
91
92
93
95
98
99
101
103
Capitolo 9. Elementi di Crittografia
1. Introduzione
2. Crittosistemi a chiave pubblica
3. Vantaggi, svantaggi, applicazioni dei crittosistemi a chiave pubblica
4. Il sistema RSA
5. La firma elettronica, autenticazione con il sistema RSA
6. Sicurezza del sistema RSA
107
107
109
110
111
121
122
CAPITOLO 1
Presentazione del corso
1. Programma del corso
(1)
(2)
(3)
(4)
(5)
(6)
(7)
Codici a blocchi.
Codici lineari.
Codici ciclici.
Codici di Hamming.
Codici correttori e gruppi di permutazioni.
Elementi di Crittografia.
Gruppi e insiemi di permutazioni equidistanti.
Per contestualizzare maggiormente gli argomenti trattati nei punti (1) − (5),
nelle parti (6) e (7) vengono presentati alcuni temi strettamente legati alla teoria
dei codici quali la crittografia o, in ambito più strettamente algebrico, lo studio di
particolari insiemi finiti di permutazioni.
2. Prerequisiti
Si ritengono note le definizioni e le principali proprietà delle seguenti nozioni.
• Numerazioni in basi diverse. Numerazione binaria.
• Strutture Algebriche e relative sottostrutture. Omomorfismo fra strutture
algebriche.
• Gruppo. Laterali di un sottogruppo. Gruppi ciclici.
• Permutazioni e loro proprietà.
• Anello. Ideali di un anello. Anello dei polinomi.
• Corpo e campo. Caratteristica di un campo. Campi di Galois. Divisione
di polinomi su un campo K. Ampliamenti algebrici dei campi. Polinomi
minimi.
• Struttura algebrica delle classi resto modulo n.
1
3. TESTI DI RIFERIMENTO
2
3. Testi di riferimento
Il materiale didattico è fornito dal docente con appunti e articoli sugli argomenti
trattati. Per i capitoli 2, 3, 4, 5, 6, 7, 9 si segnalano i seguenti testi di riferimento.
(1) L. Berardi, Algebra e teoria dei codici correttori, Milano, F. Angeli, 1994.
(2) M. W. Baldoni, C. Ciliberto, G. M. Piacentini Cattaneo, Aritmetica,
Crittografia e Codici, Milano, Springer-Verlag, 2006.
(3) L. Giuzzi, Codici Correttori, Milano, Springer, 2006.
CAPITOLO 2
Generalità sui Codici
1. Introduzione
00
Ti svegli una mattina, e nella semioscurità vedi una figura con uno strano
cappello accucciata in un angolo della stanza. Dopo un po’ i tuoi occhi focalizzano
e ti accorgi che in realtà sono i tuoi vestiti buttati su una sedia. Noti poi che la
tua amata se n’è andata e trovi un biglietto sul cuscino che dice 00 I LOVE XOU00 .
Quasi certamente questo ti rassicurerà, perchè presumerai che nel buio la Y sembri
una X. Certo, non sei sicuro al 100%. Potrebbe anche essere che in realtà la X
sia una L e che sei stato abbandonato per il tuo caro amico(o almeno così credevi)
Lou.00
(Pretzel, 1992)
Questo esempio racchiude l’essenza della teoria dei codici: trasmettendo messaggi c’è sempre una possibilità d’errore a cui ogni sistema di comunicazione deve
far fronte, in modo da essere affidabile.
I sistemi di comunicazione per trasferire messaggi sono molteplici: si può pensare ad una comunicazione via telegrafo o via telefono, ad un trasferimento di dati
da un computer ad un altro, ad un messaggio inviato attraverso un cavo ottico o
ad una antenna satellitare, ecc. ... .
Qualunque sia il sistema di comunicazione utilizzato, uno dei problemi più
frequenti è la presenza del rumore nel canale di comunicazione, ossia la presenza
di un insieme di segnali di disturbo e interferenze, estranei a quelli trasmessi.
Questi disturbi possono introdurre degli errori nelle informazioni trasmesse e ciò
che si riceve può differire da quanto è stato trasmesso.
La probabilità che nel corso di una trasmissione si verifichino degli errori non
può mai ridursi a zero, occorre pertanto individuare delle strategie che permettano di scoprire e correggere eventuali errori entrati durante la trasmissione del
messaggio.
3
2. TRASMISSIONE DI UN MESSAGGIO
4
La teoria dei codici affronta questo tipo di problemi ed elabora tecniche volte ad
identificare e a correggere gli eventuali errori commessi nel corso della trasmissione
dei dati, oltre che a permettere di codificare e decodificare velocemente i dati che
si vogliono inoltrare.
Queste tecniche richiedono però di trasmettere dati aggiuntivi (ridondanza)
che se da un lato permettono di verificare se c’è stato un errore ed eventualmente
correggerlo, dall’altro complicano ed appesantiscono le operazioni di trasmissione. Affinchè il sistema sia efficace è necessario trovare il giusto equilibrio tra la
ridondanza e la correttezza dell’informazione.
I codici correttori e rivelatori di errori sono importanti per le applicazioni ma,
al contempo, interessanti dal punto di vista teorico-matematico perchè senza la
matematica non si possono costruire buoni codici.
La branca della matematica su cui poggia la teoria dei codici è l’algebra e,
in particolare, sono le strutture algebriche finite. Ad esempio, l’ambito in cui si
sviluppa la teoria più interessante dei codici a blocchi è quello dei campi di Galois.
Molti indicano il 1948 quale anno di nascita della Teoria dei Codici perchè è
l’anno della pubblicazione dell’articolo Mathematical theory of communication di
C. E. Shannon in cui viene provata l’esistenza di codici capaci di correggere un
buon numero di errori. Da questi inizi la teoria dei codici ha avuto un enorme
sviluppo che dura tuttora (le pubblicazioni su questo argomento sono migliaia).
2. Trasmissione di un messaggio
M
Trasmettitore
Ricevitore
M
Codificatore
M
x
Decodificatore
x
y
M
x
y
C
A
N
A
L
E
disturbi
Trasmettitore (o sorgente) = emette il messaggio M .
Codificatore = traduce il messaggio in modo che possa attraversare il canale
di comunicazione (di norma trasforma i messaggi in segnali elettrici): M → x.
3. PROBLEMI DI TRASMISSIONE
5
Canale = è il mezzo usato per far viaggiare i segnali.
Decodificatore = ritrasforma i segnali nel messaggio M e lo invia al ricevitore.
Ricevitore = riceve il messaggio.
Rumore = disturbi di vario tipo.
Nella trasmissione di un messaggio, la prima necessità è quella di riconoscere
se il messaggio ricevuto contiene errori e in tal caso correggerli.
La scienza che si occupa dei metodi per individuare e correggere gli eventuali
errori immessi durante la trasmissione dei messaggi è la teoria dei codici.
La scienza che si occupa dei metodi per cifrare un messaggio è la crittografia.
3. Problemi di trasmissione
Per introdurre le varie problematiche che si devono affrontare, iniziamo con
due esempi.
Esempio 2.3.1. Supponiamo si voglia trasmettere un messaggio in lingua italiana. Per codificare associamo ad ogni lettera dell’alfabeto italiano il suo numero
d’ordine scritto in forma binaria.
a → 1 = 1 · 20 = 1
b → 2 = 1 · 21 + 0 · 20 = 10
c → 3 = 1 · 21 + 1 · 20 = 11
...............
z → 21 = 1 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 = 10101
Nel canale viene immessa la sequenza binaria. Il decodificatore associa alla
sequenza binaria la lettera dell’alfabeto italiano e la invia al ricevitore. E’ ovvio
che codificatore e decodificatore devono conoscere ed utilizzare lo stesso metodo
per codificare e decodificare. Trasmettere la lettera a significa
a → 1 → CANALE → 1 → a
Trasmettere la lettera z significa
z → 10101 → CANALE → 10101 → ?
Pur supponendo non vi siano stati errori durante la trasmissione, incontriamo
il primo ostacolo: poichè le lettere dell’alfabeto sono rappresentate da blocchi (di
0 ed 1) di lunghezza diversa, se trasmettiamo la sequenza 10101, il decodificatore
3. PROBLEMI DI TRASMISSIONE
6
non sa se la sequenza è relativa ad una sola lettera o se sono state trasmesse più
lettere in successione. Ad esempio:
10101 → 10101 = z
10101 → 10 10 1 = bba
10101 → 10 101 = be
Nasce dunque il problema della suddivisione delle sequenze ricevute. Per risolvere questo problema basta codificare tutte le lettere con sequenze aventi
la stessa lunghezza che dovrà essere almeno quella necessaria per rappresentare
la sequenza più lunga, nel nostro esempio la z. Per fare ciò è sufficiente aggiungere
all’inizio di ogni sequenza tanti zeri quanti ne occorrono per arrivare alla lunghezza
prestabilita (nel nostro esempio, scegliendo la lunghezza minima, per arrivare ad
avere cinque simboli). Stabilito che tutte le lettere dell’alfabeto saranno trasmesse
con delle sequenze di cinque simboli, la codifica diventa:
a → 00001
b → 00010
c → 00011
.........
z → 10101
e per decodificare non ci sono più ambiguità:
00001 → a
00010 → b
00011 → c
.........
10101 → z.
Esempio 2.3.2. Un collega di un’altra città sta eseguendo un esperimento di
chimica e, via posta elettronica, ci trasmette 0 se la reazione chimica è POSITIVA,
ci trasmette 1 se la reazione chimica è NEGATIVA. Nella trasmissione c’è però
una probabilità p di errore, ovviamente 0 ≤ p ≤ 1. Supponiamo sia p = 0, 01;
significa che presumiamo capiti una volta su 100 che venga trasmesso 1 invece
di 0 o viceversa. Se noi riceviamo 0 non possiamo dunque essere sicuri che la
reazione chimica sia POSITIVA. Per affrontare questo problema, introduciamo una
ridondanza ossia introduciamo degli elementi che 00 appesantiscono00 la trasmissione
ma riducono la probabilità di errore.
Chiediamo al collega di trasmettere 00 se è POSITIVA e di trasmettere 11 se
è NEGATIVA. Supponiamo che sia POSITIVA.
La probabilità di ricevere 11, ossia che nella trasmissione vengano effettuati due
errori è p2 = 0, 0001 e dunque, rispetto a prima, è molto ridotta. La probabilità di
ricevere 01 oppure 10, ossia che venga effettuato un solo errore, è 2 · 0, 99 · 0, 01 =
4. CANALI DI TRASMISSIONE. CANALI SIMMETRICI
7
0, 0198. La probabilità di ricevere 00, informazione corretta, è 0, 99·0, 99 = 0, 9801.
Inoltre se riceviamo 01 oppure 10 siamo certi che vi è un errore di trasmissione e
perciò possiamo richiedere al collega di riinviare il messaggio. Dunque solo in un
caso su 10000 potremo essere tratti in errore.
Se non ci sono problemi di tempo e di costi per l’utilizzo del canale di trasmissione, possiamo ancora migliorare la situazione fissando un intero positivo dispari
n e chiedendo di inviare una sequenza di n cifre 0 se è POSITIVA e una sequenza
di n cifre 1 se è NEGATIVA. Ciò aiuterà a decodificare POSITIVA se la sequenza
di arrivo contiene più cifre 0 che 1 e decodifiare NEGATIVA se contiene più cifre
1 che 0, (Principio di massima Somiglianza).
La probabilità di errore diventa
X n Pn =
pn−i (1 − p)i .
i
n
0≤i<b 2 c
che tende a zero per n che tende all’infinito.
4. Canali di trasmissione. Canali simmetrici
Sia A = {a1 , a2 , . . . , aq } un insieme di simboli/segnali che pensiamo come lettere di un alfabeto. Per canale di trasmissione, o di comunicazione, si intende un
sistema fisico Γ in grado di accettare in entrata (input) le lettere di A e, in corrispondenza di ciascuna lettera accettata, emettere in uscita (output) un elemento
ancora di A.
Si ritiene esclusa la possibilità che all’immissione di una lettera dell’alfabeto
non corrisponda l’emissione di una lettera.
Quando nel canale di trasmissione si immettono successivamente le lettere
ai1 , ai2 , . . . , ain e in uscita si trovano nell’ordine le lettere aj1 , aj2 , . . . , ajn , si dice
che è stata trasmessa la parola āi = (ai1 , ai2 , . . . , ain ) e che è stata ricevuta la parola a¯j = (aj1 , aj2 , . . . , ajn ); in queste ipotesi, il numero di componenti corrispondenti
diverse tra la parola trasmessa e quella ricevuta prende il nome di numero di errori
commesso nella trasmissione della parola āi .
Comunque prese due lettere ai , aj denotiamo con P (aj , ai ) la probabilità che
immettendo nel canale Γ la lettera ai si trovi in uscita la lettera aj e supponiamo
che tale probabilità dipenda soltanto dalla coppia (ai , aj ). In queste ipotesi il canale
si dice senza memoria e, posto
pij = P (aj , ai )
la matrice
P = (pij )
4. CANALI DI TRASMISSIONE. CANALI SIMMETRICI
8
si chiama matrice del canale Γ. Poichè ogni riga di P contiene le probabilità
di tutte le lettere che in uscita possono corrispondere all’immissione della lettera
relativa alla riga scelta, la somma degli elementi su ogni riga di P è uguale ad 1,
ossia
q
X
pij = 1 .
0 ≤ pij ≤ 1 ,
j=1
Nell’ambito dei canali di comunicazione senza memoria sono particolarmente
importanti i canali simmetrici. Un canale di questo tipo è definito dalla proprietà che la probabilità p che una lettera ai in entrata sia trasformata in uscita
in una lettera diversa aj non dipende da ai e aj ma è la stessa per tutte le coppie
di lettere distinte. Ciò significa che nella matrice del canale P risulta pij = p per
ogni coppia (i, j), i 6= j. Il numero p si chiama probabilità di errore del canale.
La matrice di un canale simmetrico rispetto ad un alfabeto A con q lettere è
dunque del tipo


1 − (q − 1)p
p
···
p


p
1 − (q − 1)p · · ·
p
.
P =
.
.
.
.


..
..
..
..
p
p
· · · 1 − (q − 1)p
In particolare sono molto usati i canali simmetrici binari denotati con BSC
(Binary Symmetric Channel). In essi l’alfabeto dispone solo di due simboli, per
esempio 0 ed 1; poichè ciascuna lettera in entrata ha la stessa probabilità p di
essere trasformata nell’altra in uscita, la matrice del canale è data da
1−p
p
P =
.
p
1−p
La matrice di un canale simmetrico binario viene schematizzata con la seguente
figura
1
1−P
/
v: 0
HH
v
HH
vv
HH
vv
HH vvv P
HvHv
vv HHH P
v
HH
v
HH
vv
HH
vv
v
H$
v
v
/
0 HH
1−P
1
5. ESEMPI. CODICI: FISCALE, ISBN, MORSE, ASCII.
9
5. Esempi. Codici: Fiscale, ISBN, Morse, ASCII.
Riportiamo alcuni esempi di codici i cui nomi sono certamente noti al lettore.
Esempio 2.5.1. Il Codice Fiscale Italiano è un codice su un alfabeto di 36
lettere (le 26 dell’alfabeto inglese e le cifre decimali da 0 a 9). Le sue parole servono
a codificare qualunque persona o ente abbia rapporti con il sistema fiscale italiano.
Nel caso di una persona fisica la parola corrispondente è composta da 16 lettere:
le prime 6 si riferiscono a cognome e nome, il secondo gruppo di 5 individua la
data di nascita e il sesso, il successivo gruppo di 4 individua la località italiana
o lo stato estero di nascita e l’ultima, che è di controllo, si calcola mediante un
opportuno algoritmo sulle prime 15.
Precisamente:
• Le prime tre lettere sono le prime tre consonanti del cognome.
• Il secondo gruppo di tre lettere sono la prima, la terza e la quarta consonante del nome.
• Seguono le ultime due cifre dell’anno di nascita.
• La lettera seguente indica il mese di nascita secondo le corrispondenze
Gennaio = A
Maggio = E
Settembre = P
Febbraio = B
Giugno = H
Ottobre
= R
Marzo
= C
Luglio = L
Novembre = S
Aprile
= D
Agosto = M
Dicembre = T
• Le due cifre successive indicano il giorno di nascita ed il sesso : per i
soggetti di sesso maschile, il giorno di nascita rimane invariato (con i
numeri da 1 a 31, facendo precedere dalla cifra 0 i giorni del mese da 1 a
9). Per i soggetti di sesso femminile, il giorno di nascita viene aumentato
di 40 (per cui i numeri che compaiono vanno da 41 a 71).
• I quattro simboli successivi indicano il comune italiano o lo stato estero
di nascita.
• Il sedicesimo carattere ha una funzione di controllo. Esso viene determinato nel seguente modo: a ciascuno dei primi quindici simboli viene
assegnato un valore numerico; se un simbolo occupa una posizione di ordine pari, ad esso si associa un numero secondo l’ordine naturale (cioè
alla lettera A o allo zero viene associato il valore zero; alla lettera B o
al numero 1 viene associato il valore 1, e così via per tutte le lettere e i
numeri); se invece un simbolo occupa una posizione di ordine dispari, ad
esso viene associato un valore numerico secondo la tabella sotto riportata. I valori numerici così determinati, vengono addizionati e la somma si
divide per il numero 26. Il carattere di controllo si ottiene convertendo
tale cifra nel carattere corrispondente l’ordine naturale.
5. ESEMPI. CODICI: FISCALE, ISBN, MORSE, ASCII.
A
B
C
D
E
F
G
H
I
Tabella di conversione dei caratteri
o zero = 1
| J o 9 =
o
1 = 0
|
K =
o
2 = 5
|
L =
o
3 = 7
|
M =
o
4 = 9
|
N =
o
5 = 13
|
O =
o
6 = 15
|
P =
o
7 = 17
|
Q =
o
8 = 19
|
R =
di ordine dispari.
21
|
S =
2
|
T =
4
|
U =
18
|
V =
20
|
W =
11
|
X =
3
|
Y =
6
|
Z =
8
|
10
12
14
16
10
22
25
24
23
Esempio 2.5.2. Il codice ISBN ( International Standard Book Number ) è un
codice a blocchi C di lunghezza 10 sull’alfabeto di 11 lettere costituito dalle cifre
decimali da 0 a 9 e dalla lettera X ed è usato per codificare i libri in commercio.
Quasi ogni libro, infatti, che non sia troppo vecchio, presenta stampata sul retro
della copertina una successione di dieci cifre, che è il suo ISBN e cioè la parola
di C ad esso associata. Lo schema di codifica, ad esempio, di un libro scritto in
inglese è il seguente: la prima lettera a1 di una parola a è zero e corrisponde alla
lingua inglese; le due lettere successive a2 a3 individuano la casa editrice; le sei
lettere successive a4 a5 a6 a7 a8 a9 indicano un numero assegnato al libro dalla casa
editrice; l’ultima lettera a10 è di controllo ed è uguale al resto r della divisione per
11 dell’intero
a1 + 2a2 + 3a3 + 4a4 + 5a5 + 6a6 + 7a7 + 8a8 + 9a9
se 0 ≤ r ≤ 9, è invece uguale ad X se risulta r = 10. Come si vede, l’ultima lettera
di una parola del codice ISBN è l’unica che può assumere il valore X. Per esempio,
il libro di E.F.Assmus e J.D.Key dal titolo Designs and Their Codes, pubblicato
dalla Cambridge University Press, ha ISBN uguale a 0 − 521 − 41361 − 3. Ciò
significa che la casa editrice Cambridge University Press è codificata con 00 5200 .
Da notare che i trattini che separano alcuni gruppi di cifre dell’ISBN non hanno
alcun significato al fine della codifica. Per maggiori informazioni sul codice ISBN
vedere il sito web: http://www.alice.it/bookshop/law.bks/codiinte.htm .
Esempio 2.5.3. Il codice Morse è un codice a lunghezza variabile sull’alfabeto
di tre lettere : punto, linea, spazio
Γ = {•, −, spazio}
Esso serve a codificare le lettere dell’alfabeto inglese ed è stato molto usato nel
passato soprattutto per trasmettere messaggi con il telegrafo senza fili. Il codice,
riportato in tabella, è stato costruito in modo che una sua parola è tanto più lunga
quanto la lettera corrispondente è meno frequente nella lingua inglese.
5. ESEMPI. CODICI: FISCALE, ISBN, MORSE, ASCII.
A •E •
I ••
M -Q --•U •• Y -•--
B - •••
F - •• - •
J •--N
-•
R
•-•
V ••• Z - - ••
C -•-•
G - -•
K -•O --S •••
W •--
D
H
L
P
T
X
11
- ••
• • ••
• - ••
•--•
- •• -
Si noti, per esempio, che nella lingua inglese la lettera E è più frequente della
Z e quindi la parola del codice 00 •00 corrispondente ad E è relativamente più corta
di quella 00 − − • •00 corrispondente a Z. Questo semplice accorgimento si presta
chiaramente a rendere più veloce la codifica, la trasmissione e la decodifica dei
messaggi. Lo spazio che figura fra le lettere di Γ non è mai utilizzato per la
codifica di una singola lettera ma è essenziale per dividere tra loro le parole del
codice presenti in un messaggio codificato. Più precisamente, quando si codifica
una frase, bisogna inserire esattamente uno spazio tra due lettere dell’alfabeto
codificato ed almeno due spazi fra due parole. Per esempio, se usiamo il simbolo
@ per indicare uno spazio, l’espressione
CODICE M ORSE
si codifica con
− • − • @ − − − @ − • • @ • •@ − • − •@ • @@ − −@ − − − @ • − • @ • • • @•
Osserviamo che il codice Morse non distingue le lettere minuscole dalle maiuscole.
Il codice Morse è un codice introdotto per la trasmissione di testo su linee telegrafiche e queste trasmettono solo un tipo di segnale: presenza o assenza di corrente.
Se si rappresenta con il simbolo 00 100 la presenza di corrente e con il simbolo 00 000
l’assenza, vigono le seguenti regole di modulazione:
(1) Il punto 00 •00 corrisponde all’unità fondamentale di tempo di trasmissione
e viene indicato con 00 100 .
(2) La linea 00 −00 corrisponde ad un segnale continuato di durata tripla rispetto
quello del punto e dunque corrisponde ad inviare la sequenza 111.
(3) Facendo corrispondere il simbolo 0 alla pausa della durata di un punto,
in ogni lettera i singoli simboli di punto e linea sono separati da 0, in ogni
parola le singole lettere sono fra loro separate da 000 e due parole sono
fra loro separate da 0000000.
Esempio 2.5.4. L’American Standard Code for Information Interchange, noto
come Codice ASCII, dal 1968 è il codice standard per i computer. E’ un codice
a blocchi sull’alfabeto F = {0, 1} formato da tutte le parole di lunghezza sette e,
quindi, contiene esattamente 27 = 128 parole. Esso è stato costruito per codificare
le lettere dell’alfabeto inglese maiuscole e minuscole, le cifre decimali da 0 a 9 e una
5. ESEMPI. CODICI: FISCALE, ISBN, MORSE, ASCII.
12
serie di altri simboli e istruzioni allo scopo di permettere all’architettura interna
di un computer di operare solo con i simboli 0 ed 1. Al codice standard iniziale
a 7 bit sono seguite estensioni a 8 bit con lo scopo di raddoppiare il numero di
caratteri rappresentabili. ASCII esteso (8 bit) ha 256 configurazioni: le prime 128
(da 00000000 a 01111111) sono associate ai caratteri dell’ASCII standard, le altre
128 (da 10000000 a 11111111) sono associate a lettere accentate, a caratteri grafici,
a simboli matematici e scientifici, eccetera.
Nella Tabella 1 si riporta, secondo il codice ASCII, la traduzione in numeri
dei simboli più comunemente usati durante la scrittura di un testo. Si parte da 32
perchè gli interi minori di 32 e il 127 sono caratteri di controllo; il 32 corrisponde
al carattere di spazio.
Nella Tabella 2 sono elencate le parole del codice ASCII che corrispondono
alle cifre da 0 a 9 e alle lettere maiuscole dell’alfabeto scritte in forma binaria.
Per esempio la sequenza
VA BENE !
viene trasformata in
0101011001000001001000000100001001000101010011100100010100100001
Tabella 1
32
33 !
34 00
35 #
36 $
37 %
38 &
39 0
40 (
41 )
42 ∗
43 +
44
45
46
47
48
49
50
51
52
53
54
55
,
−
.
/
0
1
2
3
4
5
6
7
56
57
58
59
60
61
62
63
64
65
66
67
8
9
:
;
<
=
>
?
@
A
B
C
68
69
70
71
72
73
74
75
76
77
78
79
D 80 P 92 .\ 104 h
E 81 Q 93 ] 105 i
F 82 R
94 ˆ 106 j
G 83 S 95 _ 107 k
H 84 T
96 8
108 l
I 85 U 97 a 109 m
J 86 V
98 b 110 n
K 87 W 99 c 111 o
L 88 X 100 d 112 p
M 89 Y 101 e 113 q
N 90 Z 102 f 114 r
O 91 [ 103 g 115 s
116
117
118
119
120
121
122
123
124
125
126
t
u
v
w
x
y
z
{
|
}
∼
5. ESEMPI. CODICI: FISCALE, ISBN, MORSE, ASCII.
Tabella 2
(spazio) 00100000
2 00110010
6 00110110
A 01000001
E 01000101
I 01001001
M 01001101
Q 01010001
U 01010101
Y 01011001
!
3
7
B
F
J
N
R
V
Z
00100001
00110011
00110111
01000010
01000110
01001010
01001110
01010010
01010110
01011010
0
4
8
C
G
K
O
S
W
00110000
00110100
00111000
01000011
01000111
01001011
01001111
01010011
01010111
1
5
9
D
H
L
P
T
X
00110001
00110101
00111001
01000100
01001000
01001100
01010000
01010100
01011000
13
CAPITOLO 3
Codici a Blocchi
Per superare i problemi evidenziati dagli esempi del paragrafo 3 del capitolo
precedente, i codici studiati sono principalmente codici a blocchi ossia codici in cui
le parole hanno tutte la stessa lunghezza.
Un altro notevole vantaggio che si ha nel considerare codici a blocchi, è che
ogni blocco viene codificato e decodificato in modo indipendente ed autonomo sia
da quelli che lo precedono che da quelli che lo seguono. Pertanto per descrivere
l’azione generale di codifica e di decodifica dei blocchi, basta descriverla su uno
solo di essi.
1. Definizioni
Definizione 3.1.1. Sia Aq = {x1 , x2 , . . . , xq } un insieme finito di cardinalità
|Aq | = q ≥ 2 e sia n un intero positivo. Si definisce codice a blocchi di lunghezza n ed ordine q (o codice q-ario) un qualunque sottoinsieme non vuoto C
di Anq .
L’insieme Aq è detto alfabeto di C; una parola del codice è una n-pla ordinata di simboli dell’alfabeto e viene denotata con x = x1 x2 · · · xn oppure x =
(x1 , x2 , · · · , xn ) o semplicemente con (x1 , x2 , · · · , xn ), i simboli xi che formano la
n-pla vengono detti componenti o coordinate della parola. L’ordine |C| = M di C
si dice grandezza del codice. Anq è detto spazio delle parole di lunghezza n e
ordine q.
I codici a blocchi rispondono all’esigenza di avere tutte le parole con la stessa
lunghezza e di avere la possibilità di prefissare la lunghezza n a seconda dell’esigenza del caso.
Esistono codici in cui variano grandezza del codice e lunghezza delle parole,
sono detti codici a lunghezza variabile.
14
2. CODICI CHE RIVELANO E CORREGGONO ERRORI. DISTANZA DI HAMMING.
15
Noi tratteremo solo codici a blocchi e pertanto nel seguito li chiameremo soltanto codici.
2. Codici che rivelano e correggono errori. Distanza di Hamming.
R. Hamming (1915 − 1998) è fra i primi a studiare tecniche per aumentare
l’efficienza di un codice. Lo scopo è quello di trovare metodi affinchè un codice sia
in grado non solo di scoprire ma anche di correggere errori. Illustriamo l’esempio
considerato dallo stesso Hamming e noto come codice (7, 4) di Hamming.
Supponiamo di dover trasmettere dei messaggi formati da numeri da 0 a 15
scritti in base 2 e quindi di trasmettere quaterne di cifre 0 e 1. Il nostro codice
è binario perchè ha per alfabeto il campo di Galois GF (2) = A2 = {0, 1} ed è
|C| = M = 24 = 16.
Se la parola da trasmettere è la quaterna (a1 , a2 , a3 , a4 ), noi trasmettiamo la
7-upla
(a1 , a2 , a3 , a4 , a1 + a3 + a4 , a1 + a2 + a4 , a1 + a2 + a3 )
in cui le somme sono fatte ovviamente in GF (2).
Ad esempio invece di trasmettere la quaterna (0, 1, 0, 0) viene trasmessa la
settupla (0, 1, 0, 0, 0, 1, 1). In pratica si costruisce un codice di lunghezza n = 7,
immergendo C = A42 in A72 mediante l’applicazione iniettiva
ϕ : A42 → A72
che ad (a1 , a2 , a3 , a4 ) ∈ A42 associa l’elemento (a1 , a2 , a3 , a4 , a1 + a3 + a4 , a1 + a2 +
a4 , a1 + a2 + a3 ) ∈ A72 .
A partire dal codice C = A42 si costruisce il codice ϕ(C) ⊆ A72 ; poichè C e
ϕ(C) sono in corrispondenza biunivoca, 00 identifichiamo00 C con ϕ(C) ⊆ A72 ossia
parleremo di C come il codice le cui parole sono delle 7-ple.
Vediamo cosa abbiamo guadagnato nel passare da sequenze costituite da quattro simboli a parole costituite da sette simboli. Osserviamo che se (x1 , x2 , · · · , x7 )
è una parola del codice, si ha

 x1 + x3 + x4 + x5 = 0
x1 + x2 + x4 + x6 = 0
 x +x +x +x =0
1
2
3
7
Infatti, per esempio, il primo membro della prima equazione è x1 +x3 +x4 +x5 =
2x1 + 2x3 + 2x4 che in A2 vale 0.
Il sistema lineare di equazioni costruito e considerato sul campo GF (2), è detto
sistema delle condizioni di parità del codice. Se riceviamo il messaggio
2. CODICI CHE RIVELANO E CORREGGONO ERRORI. DISTANZA DI HAMMING.
16
(x1 , x2 , · · · , x7 ) ed esso non verifica il sistema lineare sopra scritto, di sicuro vi è
un errore di trasmissione. Dunque il codice è in grado di scoprire errori.
Supponiamo ora di sapere, o di ritenere assai probabile, che nel trasmettere una
7-pla di C si possa verificare al massimo un errore. Poichè x5 = x1 + x3 + x4 , x6 =
x1 + x2 + x4 , x7 = x1 + x2 + x3 , il sistema di equazioni soprascritto è tale che i casi
possibili sono tutti e soli i seguenti:
• se (x1 , x2 , · · · , x7 ) non verifica nessuna delle equazioni del sistema lineare,
l’errore è al primo posto;
• se (x1 , x2 , · · · , x7 ) verifica la prima equazione del sistema lineare ma non
le altre due, l’errore è al secondo posto;
• se (x1 , x2 , · · · , x7 ) verifica la seconda equazione del sistema lineare ma non
le altre due, l’errore è al terzo posto;
• se (x1 , x2 , · · · , x7 ) verifica la terza equazione del sistema lineare ma non
le altre due , l’errore è al quarto posto;
• se (x1 , x2 , · · · , x7 ) verifica la seconda e la terza equazione del sistema
lineare ma non la prima, l’errore è al quinto posto;
• se (x1 , x2 , · · · , x7 ) verifica prima e la terza equazione del sistema lineare
ma non la seconda, l’errore è al sesto posto;
• se (x1 , x2 , · · · , x7 ) verifica la prima e la seconda equazione del sistema
lineare ma non la terza, l’errore è al settimo posto;
Dunque se sappiamo che c’è un solo errore, il sistema ci consente anche di
individuare dove è l’errore e quindi di correggerlo perchè, essendo il codice binario,
basta sostituire 0 a 1, o viceversa, nel posto in cui c’è l’errore.
Esempio 3.2.1. Supponiamo di ricevere la parola p = (0, 1, 0, 1, 0, 1, 0), che
contiene errori perchè non soddisfa il sistema lineare, supponiamo inoltre di sapere
che l’errore è uno solo. Poichè p non soddisfa nessuna delle tre equazioni del
sistema, si ha che l’errore è in x1 e perciò la parola corretta è p = (1, 1, 0, 1, 0, 1, 0).
(L’errore è nella prima coordinata perchè se l’errore fosse in x2 allora sarebbe
verificata la prima equazione, se l’errore fosse in x3 sarebbe verificata la seconda
equazione, se l’errore fosse in x4 sarebbe verificata la terza equazione, mentre la
7-upla ricevuta non soddisfa nessuna delle tre equazioni del sistema).
Il motivo per cui il codice (7, 4) di Hamming funziona è che, come si verifica
immediatamente, due diverse parole differiscono in almeno tre coordinate.
Cerchiamo di capire con un esempio. Sia (x1 , x2 , · · · , x7 ) una parola del codice
che durante la trasmissione subisce un errore in una sola coordinata, sia ad esempio
la prima. Al posto di p = (x1 , x2 , · · · , x7 ) riceviamo p0 = (x01 , x2 , · · · , x7 ). Poichè
ogni parola del codice differisce da p in almeno tre coordinate, p0 differisce dalle
parole del codice diverse da p in almeno due coordinate. Allora correggiamo l’errore
2. CODICI CHE RIVELANO E CORREGGONO ERRORI. DISTANZA DI HAMMING.
17
andando a considerare la parola del codice 00 più somigliante00 a quella ricevuta.
L’unica parola del codice che differisce da (x01 , x2 , · · · , x7 ) in una sola coordinata
(e quindi più somigliante) è la p = (x1 , x2 , · · · , x7 ).
Le considerazioni fatte ora per il codice (7, 4) di Hamming si generalizzano.
Per formalizzare queste problematiche introduciamo le seguenti definizioni.
Definizione 3.2.2. Siano p = (x1 , x2 , · · · , xn ), p0 = (y1 , y2 , · · · , yn ) ∈ Anq . Si
definisce distanza di Hamming di p da p0 il numero di coordinate in cui p e p0
differiscono, si indica con d(p, p0 ). In simboli
d(p, p0 ) = |{i | xi 6= yi }|.
La distanza di Hamming è un’applicazione d : Anq × Anq → R che soddisfa
le tre proprietà caratteristiche di una metrica tra punti del piano o dello spazio.
Infatti comunque prese tre parole p, p0 , p00 del codice, si ha :
(1) d(p, p0 ) ≥ 0; d(p, p0 ) = 0 se e solo se p = p0
(positività)
0
0
(2) d(p, p ) = d(p , p)
(simmetria)
(3) d(p, p0 ) ≤ d(p, p00 ) + d(p00 , p0 )
(disuguaglianza triangolare).
La validità di 1) e di 2) è immediata. Proviamo la 3).
Siano p = (x1 , x2 , · · · , xn ), p0 = (y1 , y2 , · · · , yn ), p00 = (z1 , z2 , · · · , zn ), occorre
provare che
|{i | xi 6= yi }| ≤ |{i | xi 6= zi }| + |{i | zi 6= yi }|.
Se in i si ha xi 6= yi , allora zi può essere uguale al più ad uno fra xi e yi e
pertanto ogni i che compare al primo membro compare anche in almeno uno degli
addendi del secondo membro. Ciò prova la validità della disuguaglianza.
Definizione 3.2.3. Si chiama distanza minima di un codice C, e si indica
con d = d(C), il minimo delle distanze tra due parole distinte qualsiasi di C. In
simboli
d = d(C) = min{d(p, p0 ), ∀ p, p0 ∈ C, p 6= p0 }.
La distanza minima di un codice, come faremo vedere nel seguito, è il parametro su cui si basano le indicazioni di quanti errori un codice può individuare e/o
correggere.
Definizione 3.2.4. Si dice che il codice C è un (n, M, d)q - codice se è :
• definito su un alfabeto di q simboli,
• di lunghezza n,
• di grandezza M = |C|,
• con distanza minima d.
2. CODICI CHE RIVELANO E CORREGGONO ERRORI. DISTANZA DI HAMMING.
18
I numeri q, n, M, d sono i parametri del codice.
Ad esempio il codice (7, 4) di Hamming è un (7, 16, 3)2 - codice.
La scrittura C ⊆ Anq significa che le parole del codice hanno lunghezza n (perchè
sono delle n-ple) e sono sull’alfabeto Aq di q simboli; pertanto, in seguito, la
scrittura (n, M, d)q verrà spesso semplificata a seconda di quali sono i parametri
necessari per la comprensione dell’argomento trattato.
Per studiare la relazione tra la distanza di Hamming e il problema della correzione degli errori di trasmissione, iniziamo con la seguente definizione.
Definizione 3.2.5. Un codice C si dice h-correttore se h è il numero massimo
di errori che il codice è in grado di correggere. Il codice si dice h-rivelatore se h
è il numero massimo di errori che il codice è in grado di rivelare.
Ad esempio il codice (7, 4) di Hamming è 1-correttore e 2-rivelatore.
Teorema 3.2.6. Un codice C di lunghezza n è h-rivelatore se e solo se ha
distanza minima d = h + 1.
Dimostrazione. Sia d = h+1. Se in una parola trasmessa p entra un numero
t di errori, t ≤ h, la sequenza p0 in uscita non è una parola del codice perchè
d(p, p0 ) = t < d e pertanto i t errori sono rivelati. Se invece entra un numero di
errori maggiore o uguale a d = h + 1, la sequenza che si riceve può essere un’altra
parola del codice e quindi gli errori non vengono rivelati e pertanto se d = h + 1 il
codice è h-rivelatore.
Viceversa, sia h il massimo numero di errori che il codice rivela. Allora una
qualunque parola di C deve avere almeno h + 1 componenti diverse da quella
trasmessa, ossia d(C) ≥ h + 1 e poichè h è il massimo numero di errori che il codice
può rivelare, in C esistono almeno due parole che hanno distanza esattamente h+1
da cui d(C) = h + 1.
)c-correttore, dove
Teorema 3.2.7. Un codice C con distanza minima d è b( d−1
2
d−1
d−1
b( 2 )c indica la parte intera di 2 .
Dimostrazione. Supponiamo che in una parola trasmessa p entri un numero
di errori minore o uguale a b( d−1
)c e sia p0 la n-pla ricevuta. Si ha d(p, p0 ) ≤
2
b( d−1
)c. Proviamo che per ogni altra parola p00 di C si ha d(p0 , p00 ) ≥ b( d−1
)c + 1
2
2
da ciò segue che la parola p è la più somigliante a p0 . Supponiamo per assurdo
)c. Allora si ha
che esista una parola p00 di C, p00 6= p, tale che d(p0 , p00 ) ≤ b( d−1
2
d−1
0
0 00
d(p , p)+d(p , p ) ≤ 2b( 2 )c ≤ d−1, e questo, per la disuguaglianza triangolare,
implica d(p, p00 ) ≤ d − 1 ma ciò è assurdo perchè d(C) = d.
2. CODICI CHE RIVELANO E CORREGGONO ERRORI. DISTANZA DI HAMMING.
19
Corollario 3.2.8. Sia C un codice con distanza minima d.
(1) C scopre t errori ⇔ t < d, ossia d ≥ t + 1 .
(2) C corregge t errori ⇔ d ≥ 2t + 1.
Dimostrazione.
(1) Un codice scopre t errori se e solo se, alterando una
parola del codice in r ≤ t coordinate, non si ottiene mai un’altra parola
del codice. Questo accade se e solo se due parole del codice hanno distanza
almeno t + 1.
(2) Un codice corregge t errori se e solo se alterando una parola del codice in
r ≤ t coordinate, la n-pla così ottenuta ha distanza maggiore di t da una
qualunque altra parola del codice. Questo accade se e solo se due parole
del codice hanno distanza almeno 2t + 1.
L’insieme Anq può essere pensato come uno spazio di dimensione n e pertanto se
in Anq si considera la distanza di Hamming d, allora la coppia (Anq , d) è uno spazio
metrico e possiamo dare la seguente definizione.
Definizione 3.2.9. Sia r un intero positivo. Per ogni x ∈ Anq , si definisce sfera
di centro x e raggio r l’insieme di tutti gli elementi y ∈ Anq tali che d(x, y) ≤ r.
In simboli
S(x, r) = {y | y ∈ Anq , d(x, y) ≤ r}.
La definizione ora data permette di caratterizzare geometricamente i codici
h-correttori sulla base del principio di massima somiglianza.
Teorema 3.2.10. Sia C ⊆ Anq un codice. C è h-correttore se e solo se comunque
prese due parole distinte p e p0 di C, si ha S(p, h) ∩ S(p0 , h) = ∅.
Dimostrazione. Sia C h-correttore e siano p, p0 ∈ C, p 6= p0 . Per il corollario
3.2.8 si ha d(p, p0 ) ≥ 2h+1. Supponiamo per assurdo che sia S(p, h)∩S(p0 , h) 6= ∅
e sia x ∈ S(p, h)∩S(p0 , h). Ciò significa che d(p, x) ≤ h, d(p0 , x) ≤ h e quindi per
la proprietà della disuguaglianza triangolare si ha d(p, p0 ) ≤ h + h < 2h + 1 = d
e ciò è assurdo.
Viceversa, sia S(p, h) ∩ S(p0 , h) = ∅ per ogni p, p0 ∈ C, p 6= p0 . Supponiamo per
assurdo che esistano p, p0 ∈ C tali che d(p, p0 ) ≤ 2h. Non può essere d(p, p0 ) ≤ h
perchè in tal caso p0 ∈ S(p, h) contro l’ipotesi S(p, h) ∩ S(p0 , h) = ∅. Sia allora
h + 1 ≤ d(p, p0 ) ≤ 2h, poniamo d(p, p0 ) = h + t con 1 ≤ t ≤ h. Senza ledere in
generalità possiamo supporre che le (h + t) componenti in cui p e p0 differiscono
siano le prime h + t . Sia z ∈ Anq avente le prime h componenti uguali a p
e le successive t componenti ( dalla (h + 1)-esima alla (h + t)-esima ) uguali a
quelle di p0 ; tutte le altre componenti di z siano uguali a quelle di p e p0 . Si ha
2. CODICI CHE RIVELANO E CORREGGONO ERRORI. DISTANZA DI HAMMING.
20
d(z, p) = t ≤ h e perciò z ∈ S(p, h), inoltre d(z, p0 ) = h e perciò z ∈ S(p0 , h).
Risulta dunque z ∈ S(p, h) ∩ S(p0 , h) e ciò è assurdo per l’ipotesi fatta. Rimane
così provato che è d(p, p0 ) ≥ 2h + 1 per ogni p, p0 ∈ C e pertanto per il corollario
3.2.8 il codice C è h-correttore.
Se un codice C è h-correttore e durante la trasmissione entrano al più h errori,
allora ogni n-pla p0 ricevuta appartiene ad una ed una sola sfera S(p, h) e quindi p
è la parola di C più vicina a p0 . Dire che per la decodifica si applica il principio di
massima somiglianza significa decodificare ogni n-pla ricevuta p0 come
la parola p centro della sfera S(p, h) a cui p0 appartiene.
Il numero h degli errori che un (n, M, d)-codice C garantisce di poter correggere
(Teorema 3.2.10) è detto raggio di impacchettamento di C perchè coincide con il
massimo intero r tale che
S(p, r) ∩ S(p0 , r) = ∅
per ogni coppia di parole distinte p, p0 ∈ C.
Esempio 3.2.11. Sia C = {c1 , c2 , c3 , c4 }, con
c1 = (00000), c2 = (10110), c3 = (01011), c4 = (11101).
La distanza minima di questo codice è d = 3; pertanto per il teorema 3.2.7, è
sempre possibile correggere esattamente un errore. Sia ora S l’insieme di tutte
le possibili sequenze di lunghezza 5 su A = {0, 1}; ovviamente |S| = 25 = 32.
Consideriamo tutte le sfere di raggio 1 e centro nelle parole di C.
Sc1 = {(00000), (10000), (01000), (00100), (00010), (00001)}
Sc2 = {(10110), (00110), (11110), (10010), (10100), (10111)}
Sc3 = {(01011), (11011), (00011), (01111), (01001), (01010)}
Sc4 = {(11101), (01101), (10101), (11001), (11111), (11100)}.
L’unione di tali sfere contiene solo 24 delle possibili 32 sequenze di lunghezza 5,
sia S ∗ l’insieme delle sequenze che non cadono in alcuna delle sfere:
S ∗ = {(11000), (01100), (10001), (00101), (01110), (00111), (10011), (11010)}.
Supponiamo che sia stata ricevuta la parola u = (00011); calcoliamo la distanza
da ogni parola di C, risulta :
d(c1 , u) = 2, d(c2 , u) = 3, d(c3 , u) = 1, d(c4 , u) = 4.
Poichè u ∈ Sc3 , si può decodificare u con p = c3 . Se fosse stata ricevuta la parola
v = (11000), le distanze dalle parole del codice sarebbero :
d(c1 , v) = 2, d(c2 , v) = 3, d(c3 , v) = 3, d(c4 , v) = 2.
2. CODICI CHE RIVELANO E CORREGGONO ERRORI. DISTANZA DI HAMMING.
21
A questo punto non saremmo in grado di correggere automaticamente l’errore,
l’unica informazione sarebbe che ci sono almeno due errori perchè v non è una
parola del codice.
Il seguente teorema mette in luce che può risultare più conveniente avere codici
con distanza minima pari anzichè dispari.
Teorema 3.2.12. Sia C un codice con distanza minima d pari, d = 2h+2, h ∈
N. Allora C oltre ad essere h-correttore è anche almeno (h + 1)-rivelatore.
Dimostrazione. Poichè C ha distanza minima d = 2h+2, per il teorema 3.2.7
il codice corregge h = b d−1
c = d2 − 1 errori. Proviamo che C rivela (h + 1) = d2
2
errori. Se in una parola p trasmessa entrano d2 errori, la sequenza ricevuta non
appartiene a nessuna sfera avente centro in una parola del codice e raggio h perchè
h < d2 , quindi i d2 errori sono rivelati. Essi non possono essere corretti perchè la
sequenza ricevuta potrebbe essere equidistante da due parole del codice.
Esempio 3.2.13. Sia C un codice binario 1-correttore con distanza minima
d ≥ 3. Siano p e q due parole del codice aventi distanza minima ossia d(p, q) = d.
(1) Se durante la trasmissione entra un errore, la sequenza in uscita appartiene alla sfera S(p, 1) o alla sfera S(q, 1) a seconda che sia stata trasmessa
p oppure q. Sia nel caso che d sia dispari sia nel caso che d sia pari, per il
principio di massima somiglianza l’errore viene corretto e il decodificatore
associa alla sequenza ricevuta il centro della sfera a cui essa appartiene
che è la parola trasmessa.
(2) Supponiamo ora di trasmettere p e che entrino due errori. Analizziamo
la situazione distinguendo il caso in cui d è dispari e il caso in cui d è pari.
• 1◦ caso: la distanza minima di C è dispari. Sia d = 3 e siano p =
(11101), q = (00001) due parole del codice tali che d(p, q) = 3.
Poichè abbiamo supposto che trasmettendo p entrino due errori, supponiamo arrivi la sequenza p0 = (00101) che appartiene alla sfera
S(q, 1) per cui i due errori non solo non vengono rivelati ma la sequenza verrebbe decodificata come la parola q quando invece è stata
trasmessa p.
• 2◦ caso: la distanza minima di C è pari. Sia d = 4 e siano p =
(11101), q = (00000) due parole del codice tali che d(p, q) = 4.
Come per il caso precedente, supponiamo che nel trasmettere p entrino due errori e si riceva la sequenza p0 = (00101) . Risulta d =
(p0 , p) = 2, d(p0 , q) = 2; ciò significa che p0 non appartiene nè alla sfera
S(p, 1) nè alla sfera S(q, 1). Dunque se entrano due errori, anche in
questo caso, non si è in grado di correggerli ma però vengono rivelati
perchè d(p, p0 ) = 2 mentre la distanza minima è 4.
3. EFFICIENZA E RAPPORTO DI SEPARAZIONE
22
Esplicitiamo ulteriormente con la seguente nota.
Nota 3.2.14. Sia C un codice con distanza minima d e h-correttore. Supponiamo venga trasmessa la parola p e si riceva p0 in cui sono entrati h + 1
errori.
• Se d è pari allora C rivela gli h + 1 errori. Infatti sia d = 2t + 2, poichè C
c = t ossia d = 2h + 2.
è h-correttore, per il teorema 3.2.7 si ha h = b d−1
2
Gli h + 1 errori vengono rivelati (anche se non corretti) perchè p0 non può
appartenere a nessuna sfera di centro q ∈ C e raggio h ossia d(p0 , q) > h,
infatti se fosse d(p0 , q) ≤ h si avrebbe
2h + 2 = d ≤ d(p, q) ≤ d(p, p0 ) + d(p0 , q) ≤ (h + 1) + h = 2h + 1
e ciò è assurdo.
• Se d è dispari, l’errore non è rivelato e la decodifica potrebbe essere errata
perchè p0 potrebbe appartenere ad una sfera di centro q ∈ C e raggio h e in
questo caso p verrebbe decodificata con la parola q. Infatti sia d = 2t + 1,
poichè C è h-correttore, per il Teorema 3.2.7 si ha h = b d−1
c = t ossia
2
d = 2h + 1 e pertanto
2h + 1 = d ≤ d(p, q) ≤ d(p, p0 ) + d(p0 , q) ≤ (h + 1) + h = 2h + 1
non porta ad un assurdo.
3. Efficienza e Rapporto di separazione
Efficienza di un codice.
Osserviamo che la lunghezza n del codice C ⊆ Anq si può vedere come una
misura del costo del codice : più la parola di un codice è lunga, più tempo ed
energia occorrono per inviare i messaggi e quindi maggiore è la spesa di gestione.
La grandezza M del codice C, si può vedere come una misura della ricchezza del
codice : più parole ha un codice, maggiore e più varia è la sua possibilità di
trasmettere informazioni. Il rapporto qualità/prezzo può essere rappresentato dal
numero
logq M
R=
n
Il numero R si dice efficienza o rapporto di informazione del codice. Occorre
tenerlo il più possibile vicino ad 1 perchè il codice sia poco costoso, ma per renderlo
efficiente di scoprire e/o correggere errori non deve essere troppo vicino ad 1.
Nota 3.3.1. Se k < n è la lunghezza minima della sequenza per poter esprimere
tutti i messaggi (ossia Akq è il vocabolario minimo), allora si ha R = nk poichè risulta
M = q k . Inoltre da M ≤ q n segue R ≤ 1.
4. RELAZIONI FRA I PARAMETRI DI UN CODICE
23
Rapporto di separazione.
Se d è la distanza minima del codice, un’altra misura è il numero
d
δ=
n
detto rapporto di separazione del codice. Più grande è δ (ossia più grande è
la distanza minima d), più il codice ha possibilità di correggere gli errori.
4. Relazioni fra i parametri di un codice
Sia C ⊆ Anq un (n, M, d)q -codice .
I parametri del codice a blocchi non variano in modo indipendente ma sono
correlati fra loro. E’ dunque importante stabilire delle relazioni che esprimano
questi legami, non solo per determinare la possibile esistenza di un codice, ma
anche per stabilire quando è che un codice è migliore di un altro in considerazione
delle esigenze del caso, per esempio a parità di prestazioni è preferibile il codice
più corto perchè meno costoso.
Le principali relazioni fra i parametri riguardano la limitazione superiore e la
limitazione inferiore di M in termini di n e d.
Teorema 3.4.1 (Stima di Singleton). Sia C ⊆ Anq con distanza minima d.
Allora risulta
|C| ≤ q n−d+1
Dimostrazione. Comunque prese due parole p, p0 ∈ C, p 6= p0 , esse hanno
al più (n − d)-componenti uguali perchè d(p, p0 ) ≥ d. Ne segue che comunque si
fissano n − d + 1 posti i1 , . . . , in−d+1 , nel codice non esistono due parole distinte
aventi la stessa (n − d + 1)-pla nei posti fissati. Quindi fissati comunque n − d + 1
posti, possiamo associare ad ogni parola la (n − d + 1)-pla (ci1 , . . . , cin−d+1 ) che
si trova nei posti fissati, inoltre a parole distinte corrispondono (n − d + 1)-ple
distinte. Da ciò segue che l’applicazione
ϕ : C → An−d+1
,
q
ϕ(c) = (ci1 , . . . , cin−d+1 )
è iniettiva e pertanto |C| ≤ |An−d+1
| = q n−d+1 .
q
Corollario 3.4.2. Nella stima di Singleton vale l’uguaglianza se e solo se per
ogni n − d + 1 componenti le parole del codice assumono su di esse tutti i possibili
valori.
4. RELAZIONI FRA I PARAMETRI DI UN CODICE
24
Un’altra stima superiore per |C| si può ottenere riprendendo il concetto di sfera
di centro x ∈ C e raggio r (def. 3.2.9). Calcoliamo anzittutto la cardinalità ( o
volume) di una sfera.
Teorema 3.4.3. Il numero degli elementi della sfera S(x, r) è
|S(x, r)| =
r X
n
i=0
i
(q − 1)i
Dimostrazione. Sia 0 ≤ t ≤ n e sia σ(x, t) = {y | y ∈ Anq , d(x, y) = t}.
Allora la sfera di centro x e raggio r è tale che
r
[
S(x, r) =
σ(x, t).
t=0
0
0
Poichè per t 6= t si ha σ(x, t) ∩ σ(x, t ) = ∅, risulta
|S(x, r)| =
r
X
|σ(x, t)|
t=0
e pertanto per calcolare |S(x, r)| basta calcolare |σ(x, t)|.
Se x = (x1 , . . . , xn ) è il centro, σ(x, t) è data da tutte le n-ple y = (y1 , . . . , yn )
tali che d(x, y) = t. Fissiamo t posti della n-pla x, ad esempio i primi t. Il numero
delle n-ple che differiscono dalla x = (x1 , . . . , xn ) nei primi t posti è (q − 1)t , infatti
in ognuno dei t posti fissati possono comparire come componenti i (q − 1) elementi
di Aq diversi dalla componente che compare in quel posto in x. I t posti possono
essere fissati in tanti modi quante sono le combinazioni semplici di n elementi presi
a t a t . Allora
n
|σ(x, t)| =
(q − 1)t .
t
Segue che la cardinalità di una sfera è
r X
n
|S(x, r)| =
(q − 1)i .
i
i=0
Grazie al precedente risultato, si ottiene la seguente limitazione detta anche
limitazione per impacchettamento di sfere.
Teorema 3.4.4 (Stima di Hamming). Sia C ⊆ Anq un codice h-correttore.
Allora risulta
qn
|C| ≤ Ph n
i
i=0 i (q − 1)
4. RELAZIONI FRA I PARAMETRI DI UN CODICE
25
Dimostrazione. Per il corollario 3.2.8 si ha d ≥ 2h + 1 e pertanto per ogni
coppia di parole x, y ∈ C, le due sfere S(x, h) e S(y, h) non hanno elementi in
comune. D’altra parte, Anq contiene l’unione S di tutte le sfere S(x, h) al variare
di x ∈ C ed essendo tali sfere in numero di |C| e a due a due disgiunte, S contiene
|C| · |S(x, r)| elementi e quindi
|C| · |S(x, r)| ≤ q n .
Nota 3.4.5. La stima di Hamming è quasi sempre migliore di quella di Singleton. Infatti si dimostra che se C ⊆ An2 è un codice con distanza minima d, i
parametri per cui la stima di Singleton è migliore di quella di Hamming sono solo
i seguenti.
• d = 2 e n qualunque;
• d = 4 e n = 4, 5, 6;
• d = 6 e N = 6, 7;
• d pari, d ≥ 8 e n = d.
Un’altra stima superiore per |C| si ottiene considerando il massimo valore
possibile della distanza tra due parole distinte del codice.
Teorema 3.4.6 (Stima di Plotkin). Sia C ⊆ Anq con distanza minima d e tale
che qd − n(q − 1) > 0. Allora si ha
|C| ≤
qd
.
qd − n(q − 1)
Dimostrazione. Per la dimostrazione si rinvia a [2] pag. 413.
I codici C per i quali nella stima di Hamming vale l’uguaglianza si dicono
perfetti. Ad esempio il codice (7, 4) di Hamming è perfetto.
Definizione 3.4.7. Sia C ⊆ Anq un codice h-correttore. C si dice perfetto se
|C| = Ph
i=0
qn
n
(q − 1)i
i
I seguenti codici sono detti codici perfetti banali.
(1) C = Anq verifica l’uguaglianza per h = 0.
(2) C tale che |C| = 1 , in questo caso ogni n-pla viene decodificata nell’unica
parola del codice.
4. RELAZIONI FRA I PARAMETRI DI UN CODICE
26
(3) C = {(00 · · · 0), (11 · · · 1)} binario di lunghezza n dispari, costituito dalle
sole due parole aventi come componenti tutti 0 oppure tutti 1, corregge
n−1
errori ed è perfetto.
2
Nota 3.4.8. Dalla definizione 3.4.7 seguono immediatamente le seguenti caratterizzazioni e le seguenti condizioni necessarie di esistenza.
(1) Un codice C h-correttore è perfetto se e solo se l’unione di tutte le sfere
S(x, h), x ∈ C, coincide con l’insieme di tutte le parole possibili.
(2) Un codice C h-correttore è perfetto se e solo se la famiglia {S(x, h)}x∈C
delle sfere di centro x ∈ C e raggio h costituisce una partizione di Fq .
(3) Un codice C h-correttore è perfetto se e solo se ogni n-pla di Anq ha una
distanza minore od uguale ad h da una ed una sola parola di C .
(4) Condizione necessaria affinchè un codice C ⊆ Anq , h-correttore, sia perfetto
è che
h X
n
(q − 1)i | q n .
i
i=0
(5) Condizione necessaria per l’esistenza di un codice C ⊆ Anq 1-correttore
perfetto è che
(1 + n(q − 1)) | q n .
(6) Non esistono codici binari 1-correttori perfetti di lunghezza pari .
Esempio 3.4.9. Consideriamo il piano proiettivo di ordine 2 o piano di Fano.
P = {1, 2, 3, 4, 5, 6, 7} è l’insieme dei punti.
1
2
4
6
5
3
7
per 5,5 cm
B = {B1 = {1, Formato
2, 4}, B5,5
2 = {2, 3, 5}, B3 = {3, 4, 6}, B4 = {4, 5, 7}, B5 = {5, 6, 1}, B6 =
{6, 7, 2}, B7 = {7, 1, 3}} è l’insieme
Altezza delle
figura 4rette.
cm width=4 cm
La matrice d’incidenza A del piano di Fano è :
4. RELAZIONI FRA I PARAMETRI DI UN CODICE
B1
B2
B3
B4
B5
B6
B7
1
1
0
0
0
1
0
1
2
1
1
0
0
0
1
0
3
0
1
1
0
0
0
1
4
1
0
1
1
0
0
0
5
0
1
0
1
1
0
0
6
0
0
1
0
1
1
0
27
7
0
0
0
1
0
1
1
A partire da questa matrice d’incidenza, costruiamo un codice binario 1-correttore
perfetto C nel modo seguente.
Le parole di C sono:
(1) Le sette righe della matrice A che denoteremo con ci .
(2) Le sette righe della matrice Ā ottenuta da A scambiando tra loro i simboli
0 e 1. Ad esempio la prima riga di Ā dà la parola 0010111. Denotiamo
con c̄i tali parole.
(3) Le parole 0 = (0000000) ed 1 = (1111111).
Per come costruite le parole e ricordando le proprietà del piano proiettivo, è facile
verificare che C ha distanza minima d = 3. Il codice è 1-correttore e |C| = 16. C è
perfetto perchè :
27
qn
27
= 7
= 16 = |C|
=
Ph n
i
1+7
(2 − 1)0 + 71 (2 − 1)1
0
i=0 i (q − 1)
Dopo aver considerato tre limitazioni superiori per |C|, riportiamo una limitazione inferiore .
Teorema 3.4.10 (Stima di Gilbert-Varshamov). Sia M = |C| il massimo per
cui esiste un codice C ⊆ Anq con distanza minima d. Si ha
M ≥ Pd−1
i=0
qn
n
(q − 1)i
i
Dimostrazione. Costruiamo un codice C che verifica l’uguaglianza. Consideriamo una qualunque x1 ∈ Anq e mettiamola in C. Scegliamo una seconda parola
x2 ∈ Anq che abbia distanza almeno d da x1 e mettiamola in C. Scegliamo una
terza parola x3 ∈ Anq che abbia distanza almeno d sia da x1 che da x2 . Procediamo
allo stesso modo. Dopo aver scelto le prime h parole x1 , . . . , xh aventi tutte a due
a due distanza almeno d tra di loro, scegliamo la (h + 1)-esima parola xh+1 avente
distanza almeno d da tutte le parole x1 , . . . , xh , sempre che questo sia possibile.
Infatti il procedimento avrà termine perchè ad un certo punto non ci sarà più
spazio per scegliere ancora una parola. A questo punto si è costruito un codice C
5. (N, K)-CODICI, CODICI MDS, CODICI EQUIVALENTI
28
che ha la seguente proprietà: l’unione di tutte le sfere S(x, d − 1) con centri nei
punti x ∈ C coincide con tutto Anq , se così non fosse avremmo potuto continuare.
Il codice costruito è tale che
M · |S(x, d − 1)| ≥ q n
da cui segue la stima per M .
Quanto esposto fino ad ora giustifica il fatto che ad un buon codice si richiedono
le seguenti proprietà:
• lunghezza n abbastanza piccola per permettere una trasmissione veloce
delle sue parole;
• un numero M di parole abbastanza grande per codificare una buona
quantità di messaggi;
• distanza minima abbastanza grande per correggere il maggior numero
possibile di errori.
Ovviamente queste richieste sono fra loro contrastanti e perciò non è possibile
ottimizzare uno dei parametri senza avere preventivamente fissato gli altri due.
Questo tipo di problema è quello comunemente noto con il nome di problema
fondamentale della teoria dei codici.
5. (n, k)-codici, codici MDS, codici equivalenti
Esistono codici nei quali una parola rimane individuata univocamente assegnando un numero di simboli minore della lunghezza delle parole.
Definizione 3.5.1. Siano i1 , i2 , . . . , ik interi positivi tali che 1 ≤ i1 < i2 <
. . . < ik ≤ n. I posti i1 , i2 , . . . , ik sono detti posti di informazione per un codice
C ⊆ Anq se, comunque si fissi una k-upla (y1 , y2 , . . . , yk ), yi ∈ Aq , esiste una ed una
sola parola di C tale che nel posto i1 compaia y1 , nel posto i2 compaia y2 , . . . , nel
posto ik compaia yk .
Definizione 3.5.2. Un codice C ⊆ Anq avente k posti di informazione si dice
(n, k)-codice oppure codice sistematico.
5. (N, K)-CODICI, CODICI MDS, CODICI EQUIVALENTI
29
Se esistono k posti d’informazione, l’applicazione di C in Akq che ad ogni parola
di C associa la k-upla che si presenta nei k posti d’informazione è biunivoca perchè
la k-upla individua la parola univocamente e pertanto M = |C| = q k . I k simboli
che compaiono nella k-upla sono detti di informazione mentre i rimanenti n − k
simboli sono detti di controllo o ridondanti. In un (n, k)-codice le sequenze
emesse dal codificatore di sorgente vengono suddivise in k-uple e ad ogni k-upla
vengono aggiunti n−k simboli di controllo mediante un fissato algoritmo; in questo
modo ogni k-upla viene trasformata in una n-upla. Poichè in un (n, k)-codice è
possibile distinguere i simboli di informazione da quelli ridondanti, questi codici
sono anche detti separabili. Il rapporto nk viene detto tasso di informazione
di un (n, k)-codice.
Teorema 3.5.3. Se C ⊆ Anq è un (n, k)-codice allora |C| = q k .
Dimostrazione. Segue dalla biezione esistente fra C e Akq .
Esempio 3.5.4. Sia C il codice formato dalle parole: C = {0011, 0101, 1101}.
Dire se C è un (4, 2)-codice.
Risposta - NO, perchè non vale il Teorema 3.5.3, infatti |C| 6= 22 .
Analizziamo il codice solo in base alla definizione di (n, k)-codice.
(1) I posti {1, 2} non sono di informazione, infatti delle possibili coppie 00, 01,
10, 11 in C manca 10.
(2) I posti {1, 4} non sono di informazione perchè manca la coppia 00 e la
coppia 01 figura due volte.
Analogamente per le altre coppie di posti e dunque poichè C non ha due posti di
informazione non è un (4, 2)-codice.
Esempio 3.5.5. Consideriamo il codice C = {0011, 0101, 1100, 1011}. I posti
{1, 2} sono di informazione come anche i posti {1, 3}; al contrario comunque si
considerino altri due posti, essi non sono di informazione. C è un (4, 2)-codice.
Esempio 3.5.6. I codici
C1 = {0000, 1100, 1010, 1001, 0110, 0101, 0011, 1111}
C2 = {1000, 0100, 0010, 0001, 1110, 1011, 1101, 0111}.
sono entrambi dei (4, 3)-codici perchè tre qualsiasi posti sono di informazione.
Teorema 3.5.7 (Limitazione di Singleton). Se C ⊆ Anq è un (n, k)-codice allora
d ≤ n − k + 1.
5. (N, K)-CODICI, CODICI MDS, CODICI EQUIVALENTI
30
Dimostrazione. Se C è un (n, k)-codice con distanza minima d, allora per
3.4.1 e 3.5.3 si ha
|C| ≤ q n−d+1 e |C| = q k .
Queste relazioni implicano k ≤ n − d + 1 da cui d ≤ n − k + 1 .
La disuguaglianza di 3.5.7 dà una limitazione superiore per la distanza minima
di un (n, k)-codice. Se, da un lato, al crescere della ridondanza n−k può aumentare
la capacità del codice di correggere errori, dall’altro al crescere della ridondanza
diminuisce il tasso di informazione nk il quale dà la misura della percentuale di
informazione contenuta in una n-upla.
Come già detto, in un buon codice dovrebbero essere grandi sia nk (e quindi
poca ridondanza) sia la distanza minima (più grande è d più il codice ha possibilità
di correggere errori). Poichè le due cose si contrappongono, occorre trovare codici
in cui i parametri siano in un giusto equilibrio.
Definizione 3.5.8. Un (n, k)-codice si dice ottimale oppure MDS ( a massima distanza separabile) se, comunque presi k posti, essi sono di informazione.
Teorema 3.5.9. Condizione necessaria e sufficiente affinchè un (n, k)-codice
C con distanza minima d sia un codice MDS è che sia d = n − k + 1 .
Dimostrazione. Sia C un codice MDS. Supponiamo per assurdo che sia d <
n−k+1 ossia d ≤ n−k, allora esistono in C due parole x e y tali che d(x, y) ≤ n−k;
queste due parole hanno almeno k componenti uguali e pertanto esistono k posti
che non sono di informazione contro l’ipotesi che C sia MDS. Deve pertanto essere
d = n − k + 1.
Viceversa, sia d = n − k + 1. Se per assurdo C non fosse MDS, ci sarebbero
k posti non di informazione. Siano x e y le parole aventi componenti uguali nei k
posti non di informazione. Si ha d(x, y) ≤ n − k < d e ciò è assurdo perchè d è la
distanza minima del codice.
Esempio 3.5.10. I codici C1 e C2 dell’esempio 3.5.6 sono (4, 3)-codici ottimali.
Infatti hanno entrambi distanza minima d = 4 − 3 + 1 = 2.
Esempio 3.5.11. Sia (F, +) un gruppo additivo di ordine q. Prendendo F come
alfabeto, consideriamo il codice C di lunghezza n, definito da
n
X
C = {(x1 , x2 , . . . , xn ) | xi ∈ F,
xi = 0}.
i=1
5. (N, K)-CODICI, CODICI MDS, CODICI EQUIVALENTI
31
Se in ogni n-pla fissiamo n − 1 elementi, rimane univocamente determinato l’elemento n-simo perchè deve risultare x1 + x2 + · · · + xn = 0.
Dunque C è un codice con n − 1 posti d’informazione e pertanto è un (n, n − 1)codice. Poichè è possibile scrivere qualsiasi elemento in funzione dei rimanenti
n − 1, il codice C è MDS. Allora la distanza minima è d = n − (n − 1) + 1 = 2.
Poichè n − 1 posti qualsiasi sono di informazione, ogni parola ha un solo simbolo
di controllo.
Esempio 3.5.12. Codice a ripetizione : è così detto un codice C in cui i
simboli che compaiono in una qualsiasi parola sono tutti uguali tra loro.
Se C è un codice a ripetizione di lunghezza n, allora il codice è un (n, 1)-codice;
infatti un solo simbolo è sufficiente per individuare una parola. Inoltre C è un
codice MDS perchè qualsiasi posto è di informazione. La distanza minima è allora
c errori.
d = n − 1 + 1 = n. Il codice C corregge allora fino a b n−1
2
NOTA - Il codice a ripetizione è un codice con molta ridondanza e quindi
poco conveniente perchè per trasmettere una informazione si devono usare troppi
simboli; inoltre contiene solo q parole (supposto che l’alfabeto abbia q simboli).
Esempio 3.5.13. Costruzione di un (p, 2)-codice MDS con alfabeto F =
GF (p), p primo.
La costruzione che presentiamo è il caso p = 3. Sia F = {0, 1, 2}.
Passo 1. Si scrivono le parole aventi le componenti tutte uguali fra loro:
000, 111, 222
Passo 2 . Pensando le tre parole precedenti scritte in colonna, si considera come
quarta parola la diagonale 012 . Si costruiscono altre due parole sommando 1 ad
ogni componente di essa (somma modulo 3) :
012, 120, 201
Passo 3 . Si ripete il passo 2. e si ottengono :
021, 102, 210
Quando sulla diagonale otteniamo una parola già presa in considerazione, (000),
il processo termina e ciò accade al passo p, quando abbiamo ottenuto tutte le p2
parole del codice: C = {000, 111, 222, 012, 120, 201, 021, 102, 210}.
Definizione 3.5.14. Due codici C1 , C2 ⊆ Anq si dicono equivalenti se è possibile ottenere tutte le parole di C2 da quelle di C1 applicando un numero finito di
volte le seguenti operazioni:
(1) permutazione delle n posizioni (1, 2, . . . , n) in tutte le parole di C1 ;
5. (N, K)-CODICI, CODICI MDS, CODICI EQUIVALENTI
32
(2) permutazione dei simboli dell’alfabeto applicata, in tutte le parole, alle
componenti che occupano una posizione fissata.
Se C ⊆ Anq , |C| = M , le parole di C possono essere scritte come righe di una
tabella avente M righe ed n colonne. L’operazione 1) corrisponde ad una permutazione delle colonne della tabella, l’operazione 2) corrisponde ad una permutazione
dei simboli dell’alfabeto Aq applicata ad una colonna della tabella.
Esempio 3.5.15. Consideriamo i seguenti due codici binari:
C1 :
00000
C2 :
00100
01101
00011
10110
11111
11011
11000
Verifichiamo che C2 è equivalente a C1 . Applicando ai simboli che compaiono nella
terza posizione delle parole di C2 la permutazione 0 7→ 1, 1 7→ 0 , si ottiene il
codice C3 :
C3 :
0 0 0 0 0
0 0 1 1 1
1 1 0 1 1
1 1 1 0 0
Applicando alle colonne di C3 la permutazione 1 7→ 1, 2 7→ 4, 3 7→ 3, 4 7→ 2, 5 7→ 5
si ottengono le parole
0 0
0 1
1 1
1 0
che sono le parole
0
1
0
1
di
0 0
0 1
1 1
1 0
C1 .
Esempio 3.5.16. Consideriamo il codice ternario
C:
0 1 2
1 2 0
2 0 1
proviamo che esso è equivalente ad un codice a ripetizione.
Applichiamo ai simboli della prima posizione (colonna) la permutazione
0 7→ 0, 1 7→ 2, 2 7→ 1 ;
ai simboli della seconda posizione applichiamo la permutazione
0 7→ 1, 1 7→ 0, 2 7→ 2 ;
5. (N, K)-CODICI, CODICI MDS, CODICI EQUIVALENTI
33
ai simboli della terza posizione applichiamo la permutazione
0 7→ 2, 1 7→ 1, 2 7→ 0 .
Si ottiene
0 0 0
2 2 2
1 1 1
che sono le parole del codice ternario a ripetizione di lunghezza 3.
Il concetto di codici equivalenti è importante perchè due codici equivalenti
correggono lo stesso numero di errori. Ciò segue dal fatto che le operazioni
descritte per costruire codici equivalenti non cambiano la distanza tra due qualsiasi
parole e perciò neanche la distanza minima. Due codici equivalenti hanno dunque
le stesse proprietà metriche, così come hanno la stessa ridondanza e la stessa
efficienza.
Teorema 3.5.17. Dato un codice C ⊆ Anq esiste sempre un codice C1 ⊆ Anq
equivalente a C e contenente una qualsiasi fissata parola v ∈ Anq \ C.
Dimostrazione. Sia p una qualunque parola di C. Applicando al più n
permutazioni sui simboli, dalla parola p si ottiene la parola v.
Esempio 3.5.18. Dato il codice binario
C = {001, 101, 110, 011},
costruire un codice C1 equivalente a C e tale che 000 ∈ C1 .
Soluzione - Basta applicare ai simboli che compaiono al terzo posto la permutazione 0 7→ 1, 1 7→ 0 . Infatti si ottiene :
000, 100, 111, 010
che sono le parole di un codice equivalente a C.
Da quanto esposto fino ad ora, appare evidente che nella teoria dei codici
correttori è importante avere:
(1) Codici capaci di correggere un prefissato numero di errori.
(2) Codici di facile codifica e di facile decodifica.
5. (N, K)-CODICI, CODICI MDS, CODICI EQUIVALENTI
34
Per affrontare questi problemi occorre avere codici che abbiano una struttura
algebrica 00 ricca 00 . Per rendersi conto di ciò, basta pensare ad un codice C costruito
su un alfabeto di 10 simboli ed avente 100 posti di informazione. C contiene 10100
parole, la codifica e la decodifica sono teoricamente possibili, ma non praticamente
per l’elevato numero di parole di C. Se poi si vuole determinare la distanza minima
100
si devono fare 102 confronti !!!
Anche per superare questi problemi, sono stati introdotti i codici lineari che
senza dubbio sono una delle più importanti famiglie di codici.
CAPITOLO 4
Codici Lineari
L’importanza dei codici lineari sta nel fatto che l’insieme delle parole ha una
forte struttura algebrica e per questo sono facilitate molte operazioni quali:
• calcolare i parametri del codice;
• codificare e trasmettere i messaggi;
• decodificare i messaggi;
• scoprire e correggere errori;
• calcolare la probabilità di una corretta decodifica.
1. Definizioni e prime proprietà
Sia Fq = GF (q), q = pt , p primo, t ≥ 1, un campo di Galois. Nel seguito con
Fq si intenderà sempre il campo GF (q) e sarà l’alfabeto su cui è definito il codice.
Sotto questa ipotesi la struttura algebrica più naturale da usare su Fqn è quella di
spazio vettoriale sul campo Fq ; ricordiamo che in questo caso gli elementi di Fqn si
chiamano vettori di ordine n sul campo Fq i cui elementi si dicono scalari.
Definizione 4.1.1. Un codice C si dice lineare se è un sottospazio vettoriale
di Fqn .
Esempio 4.1.2. Costruiamo un codice lineare binario C di dimensione due
e lunghezza 5. Consideriamo F2 = GF (2) e definiamo C come il sottospazio
vettoriale di F25 avente per base B = {b1 = (1 0 1 1 1), b2 = (1 1 1 1 0)}.
Risulta C = {λb1 + µb2 | λ, µ ∈ F2 } e pertanto
(0
(1
(0
(1
0)
0)
1)
1)
→
→
→
→
0 · b1 + 0 · b2
1 · b1 + 0 · b2
0 · b1 + 1 · b2
1 · b1 + 1 · b2
= (0
= (1
= (1
= (0
0
0
1
1
0
1
1
0
0
1
1
0
0)
1)
0)
1)
Quindi C = {(0 0 0 0 0), (1 0 1 1 1), (1 1 1 1 0), (0 1 0 0 1)}. Questo codice ha
distanza minima d = 2.
35
1. DEFINIZIONI E PRIME PROPRIETÀ
36
Si osservi che dalla definizione segue
• C è un codice lineare se e solo se la somma di due parole e il prodotto di
una parola per uno scalare è ancora una parola del codice.
• Se C è un codice lineare di dimensione k allora C è un (n, k)-codice (vedi
teorema 4.2.2) ed è isomorfo a Fqk e pertanto |C| = q k . Inoltre se C ha
distanza minima d si ha k ≤ n − d + 1, d ≤ n − k + 1, |C| ≤ q n−d+1 .
• Un codice lineare contiene sempre la parola (0, 0, . . . , 0) perchè 00 contiene00
sempre il vettore nullo.
• Il numero dei sottospazi k dimensionali di V = Fqn è
(q n − 1)(q n−1 − 1) · · · (q n−k+1 − 1)
(q k − 1)(q k−1 − 1) · · · (q − 1)
e pertanto vi sono esattamente sk possibili (n, k)-codici differenti.
sk =
Nota 4.1.3. Come mostra il seguente esempio, spazi vettoriali isomorfi possono
dare codici con distanza minima diversa e perciò non equivalenti.
Esempio 4.1.4. Sia F = GF (2). Sia C1 = {λ(1, 0, 0) + µ(0, 1, 0), ∀ λ, µ ∈ F }
il sottospazio di F 3 di dimensione 2 generato da v1 = (1, 0, 0) e v2 = (0, 1, 0).
Sia ora C2 = {λ(1, 1, 0) + µ(1, 0, 1), ∀ λ, µ ∈ F } il sottospazio di F 3 di
dimensione 2 generato da w1 = (1, 1, 0) e w2 = (1, 0, 1).
C1 e C2 come spazi vettoriali sono isomorfi ma non lo sono come codici. Infatti
risulta d(C1 ) = 1 mentre d(C2 ) = 2 come si verifica facilmente esplicitando le parole
dei due codici. C1 e C2 sono dei (3, 2)-codici lineari binari e quindi contengono
22 = 4 parole .
C1 = {(0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 1, 0)}, C2 = {(0, 0, 0), (1, 0, 1), (1, 1, 0), (0, 1, 1)}.
Definizione 4.1.5. Si definisce peso di Hamming w(x) di un vettore x ∈ Fqn
il numero delle componenti non nulle di x.
Teorema 4.1.6. Sia C un codice lineare con distanza minima d. Si ha
• d(x, y) = w(x − y), ∀ x, y ∈ C
• d è uguale al minimo peso delle sue parole non nulle.
Dimostrazione. Siano x, y ∈ C, poichè d(x, y) è il numero di posti in cui le
componenti di x e y sono diverse, si ha che d(x, y) è il numero delle componenti
non nulle della parola x − y ∈ C ossia d(x, y) = w(x − y).
Sia ora d la distanza minima di C, allora esistono due parole x, y ∈ C tali
che d(x, y) = d cioè w(x − y) = d(x, y), quindi il peso minimo è d oppure
un intero minore di d. Se esistesse una parola y ∈ C con w(y) < d, seguirebbe
d(y, 0) = w(y) < d, e perciò d non sarebbe la distanza minima.
2. MATRICI GENERATRICI
37
Il teorema ora dimostrato mette in evidenza l’importanza della nozione di peso di Hamming. Per un codice non lineare trovare la minima distanza significa
calcolare la distanza
di ogni coppia di parole del codice ossia occorre calcolare
|C|
e confrontare 2 distanze, mentre per i codici lineari il problema si risolve con
il calcolo del peso delle singole parole del codice ossia è sufficiente calcolare e
confrontare i |C| − 1 pesi di Hamming delle parole non nulle di C.
Abbiamo dimostrato che un codice con distanza minima d pari, oltre a correggere d2 − 1 errori, rivela d2 errori (vedi teorema 3.2.11). E’ dunque utile il seguente
risultato.
Teorema 4.1.7. Un codice lineare binario C ⊆ F2n con distanza minima d
dispari esiste se e solo se esiste un codice binario C1 ⊆ F2n+1 avente distanza
minima d + 1 e con |C| = |C1 |. Inoltre C1 è lineare.
Dimostrazione. Si rinvia a [1] pag. 126.
2. Matrici generatrici
L’operazione di codifica di un messaggio mediante un codice lineare è una
trasformazione lineare e pertanto un vantaggio nel considerare codici lineari è
quello di avere la possibilità di una rapida descrizione del codice e della facile
decodifica delle parole. Uno dei metodi con cui ciò si realizza è la 00 costruzione00 di
una matrice che lo rappresenta.
Ad esempio
Nello spazio vettoriale V = F25 i vettori v1 = (1 0 0 0 1), v2 = (1 1 0 1 0), v3 =
(1 1 1 0 1) formano una base per un (5, 3)-codice binario C (associato al sottospazio
F23 di V = F25 ). Sia

 

v1
1 0 0 0 1
G =  v2  =  1 1 0 1 0  .
v3
1 1 1 0 1
Comunque preso un vettore m = (m1 m2 m3 ) di F23 rappresentante il messaggio da
trasmettere, possiamo trovare la parola p di C che gli corrisponde, ossia il vettore
di F25 che sarà trasmesso, calcolando
p = m1 v1 + m2 v2 + m3 v3 = mG.
2. MATRICI GENERATRICI
38
Se ad esempio m = (1 0 1) , verrà trasmesso


1 0 0 0 1
mG = (1 0 1)  1 1 0 1 0  = (0 1 1 0 0).
1 1 1 0 1
Generalizziamo
Sia C ⊆ Fqn un codice lineare di dimensione k ≤ n, sia {e1 , e2 , . . . , ek } una base
di C e sia {b1 , b2 , . . . , bn } una base di Fqn . Ogni vettore ei può essere scritto in modo
unico come combinazione lineare dei vettori bi :

e1 = e11 b1 + e12 b2 + · · · + e1n bn


 e2 = e21 b1 + e22 b2 + · · · + e2n bn
..

.


ek = ek1 b1 + ek2 b2 + · · · + ekn bn
Pertanto è unica la matrice
e11 · · ·
 e21 · · ·
G=
 ...

e1k · · ·
e2k · · ·

e1n
e2n 


ek1 · · · ekk · · · ekn
G è di tipo k × n, ha rango k essendo {ei } una base di C.
Definizione 4.2.1. Sia C ⊆ Fqn un codice lineare di dimensione k. Si definisce
matrice generatrice di C una matrice di tipo k×n le cui righe sono le componenti
dei vettori di una base di C rispetto una base di Fqn .
Osserviamo che, se invece di prendere una base del codice prendessimo un sistema di generatori x1 , . . . , xh , h ≥ k, perverremmo con lo stesso procedimento
sopra descritto , ad una matrice di tipo h × n di rango k, che può ancora considerarsi una matrice generatrice. La restrizione sulla indipendenza delle righe della
matrice generatrice non è strettamente necessaria, è utile per minimizzare l’ingombro algoritmico e di registrazione dei dati. Per questo quando si parla di matrice
generatrice si intende quella costruita a partire da una base del codice.
Di norma come base di V = Fqn si considera la base canonica.
Un vantaggio che si ha considerando codici lineari è che la loro descrizione è
molto più semplice attraverso la matrice G che non con l’elenco delle parole del
codice. Se ad esempio C è un (50, 40)-codice lineare binario allora
|C| = 240 = (24 )10 > 1010
2. MATRICI GENERATRICI
39
mentre G, avendo 40 righe e 50 colonne, ha 2000 elementi.
Teorema 4.2.2. Un codice lineare C ⊆ Fqn di dimensione k è un (n, k)-codice.
Dimostrazione. Siano {ei }, i = 1, · · · , k e {bj }, j = 1, · · · , n, basi rispettivamente di C e di Fqn e sia


e11 · · · e1k · · · e1n
 e21 · · · e2k · · · e2n 

G=

 ...
ek1 · · · ekk · · · ekn
la matrice generatrice di C rispetto alle basi fissate. Poichè G ha rango k, in essa
esiste almeno un minore di ordine k non nullo. Sia ad esempio
e11 · · · e1k e21 · · · e2k .
..
e
k1 · · · ekk
Proviamo che i primi k posti sono di informazione.
Si deve provare che assegnata una qualsiasi k-upla (a1 , · · · , ak ) c’è una ed una
sola parola x = (x1 x2 · · · xk )G = x1 e1 + · · · + xk ek (x è una n-upla) che ha a1
come prima componente, a2 come seconda componente, . . . , ak come k-esima
componente. Ciò equivale a provare che il sistema

x1 e11 + x2 e21 + · · · + xk ek1 = a1


 x1 e12 + x2 e22 + · · · + xk ek2 = a2
(x1 x2 · · · xk )G =
..

.


x1 e1k + x2 e2k + · · · + xk ekk = ak
ha una ed una sola soluzione e questo segue dal fatto che esso è un sistema lineare
di k equazioni in k incognite con determinante della matrice dei coefficienti non
nullo per ipotesi. Inoltre le rimanenti (n−k) componenti ak+1 , . . . , an di tale parola
sono combinazioni lineari di x1 , . . . , xk tramite i coefficienti eij , e pertanto sono
univocamente determinate.
Corollario 4.2.3. Un codice lineare di dimensione k è MDS se e solo se ogni
minore di ordine k di una sua matrice generatrice è non nullo.
Dimostrazione. Segue dal teorema precedente poichè un (n, k)-codice è M DS
se k posti qualsiasi sono di informazione.
2. MATRICI GENERATRICI
40
Come già osservato nell’esempio 4.1.4, due qualunque (n, k)-codici lineari sono
sempre isomorfi come spazi vettoriali ma un isomorfismo fra spazi vettoriali non
assicura che venga conservata la struttura metrica e pertanto non è detto che
due qualunque (n, k)-codici lineari siano equivalenti perchè possono avere distanza
minima diversa. La definizione di equivalenza tra codici data in 3.5.14 per due
codici a blocchi qualsiasi vale, ovviamente, anche per i codici lineari ma in generale
con questa definizione non è detto venga conservata la proprietà di linearità ossia
un codice lineare può risultare equivalente a un codice non lineare. Ad esempio :
Sia C = {(0, 1), (0, 0)}, esso è un (2, 1)-codice binario lineare. Come codice, per
la definizione 3.5.14 esso è equivalente al (2, 1)-codice C1 = {(1, 1), (1, 0)}, ma C1
non è lineare non essendo sottospazio vettoriale.
Quanto osservato motiva il fatto che la 3.5.14 si modifichi per i codici lineari
nel senso seguente.
Definizione 4.2.4. Due codici lineari C1 , C2 ⊆ Fqn si dicono equivalenti se è
possibile ottenere tutte le parole di uno di essi da quelle dell’altro applicando un
numero finito di volte le seguenti operazioni:
(1) permutazione delle n posizioni (1, 2, . . . , n);
(2) moltiplicazione dei simboli che compaiono in una data posizione per uno
scalare non nullo.
Rispetto alla 3.5.14 viene modificata la proprietà (2) perchè è importante passare da un codice lineare ad un codice equivalente che sia ancora lineare ed abbia
la stessa distanza minima. Ricordando che un codice lineare si può 00 identificare00
con una sua matrice generatrice, se sui simboli che compaiono in una colonna della
matrice generatrice di un codice lineare C si applicasse una permutazione qualsiasi,
si otterrebbe un codice che, anche se fosse ancora lineare, potrebbe avere distanza
minima diversa. Vediamo un esempio.
Esempio 4.2.5. Sia C ⊆ F33 un codice di dimensione 2 con matrice generatrice
1 1 0
G=
0 1 2
Si ha C = {λ(1, 1, 0) + µ(0, 1, 2)} = {(λ, λ + µ, 2µ), λ, µ ∈ GF (3)}. Per (λ, µ) 6=
(0, 0) ogni parola di C ha almeno due componenti non nulle e quindi d(C) = 2.
Operando sui simboli del secondo posto (seconda colonna) tramite la permutazione
0 7→ 1, 1 7→ 0, 2 7→ 2 la matrice G viene trasformata in
1 0 0
G1 =
0 0 2
2. MATRICI GENERATRICI
41
che è matrice generatrice di un codice C1 ⊆ F33 con d(C1 ) = 1. I codici C e C1 sono
isomorfi come spazi vettoriali ma non come codici perchè hanno distanza minima
diversa.
E’ possibile operare su una matrice generatrice di un codice lineare in modo da
avere una matrice generatrice dello stesso codice o di un codice lineare equivalente.
Teorema 4.2.6. Due matrici G e G1 ad elementi in GF (q) e di tipo k ×
n generano (n, k)-codici lineari equivalenti se una delle due matrici può essere
ottenuta dall’altra tramite una sequenza finita di trasformazioni dei seguenti tipi:
(1) scambiare due righe;
(2) moltiplicare gli elementi di una riga per un elemento non nullo di GF (q);
(3) sommare ad una riga un’altra riga moltiplicata per un elemento non nullo
di GF (q);
(4) permutare due colonne;
(5) moltiplicare gli elementi di una colonna per un elemento non nullo di
GF (q).
Dimostrazione. Le operazioni (1), (2), (3) danno un cambiamento di base
dello spazio vettoriale, dunque si ha lo stesso spazio vettoriale, cioè lo stesso codice
rappresentato dalla matrice di partenza.
L’operazione (4) equivale ad una permutazione delle posizioni (1, 2, . . . , n).
L’operazione (5) equivale a moltiplicare le componenti di tutte le parole che
occupano una posizione fissata per un elemento non nullo di GF (q).
Nota 4.2.7. Si osservi che sommare ad una colonna un’altra colonna moltiplicata per un elemento non nullo di GF (q), non preserva l’equivalenza di codici.
Dunque in una matrice generatrice il ruolo ricoperto dalle righe e dalle colonne
non è simmetrico.
La matrice generatrice di un codice lineare non è unica perchè dipende dalle basi
fissate. E’ quindi importante scegliere matrici generatrici il più semplice possibile
ma equivalenti ossia che generino codici equivalenti. Per un codice lineare C ⊆ Fqn
di dimensione k si può scegliere la seguente matrice detta forma standard o
forma ridotta normale.

1 0 . . . 0 x1,k+1 . . . x1,n
 0 1 . . . 0 x2,k+1 . . . x2,n 

S=
 ...


0 0 . . . 1 xk,k+1 . . . xk,n
2. MATRICI GENERATRICI
42
In forma più compatta questa matrice si può scrivere nel seguente modo
S = (Ik |A)
dove Ik è la matrice unitaria di ordine k ed è data dalle prime k colonne di S,
mentre A è la matrice rimanente. La convenienza di una matrice in questa forma
è che, una volta codificato il vettore a = (a1 , . . . , ak ) si ottiene un vettore che nelle
prime k componenti coincide con a. Dunque la ridondanza del codice è esattamente
nelle rimanenti (n − k) componenti.
Si osservi che la forma standard di una matrice generatrice non è unica. Per
esempio una permutazione qualsiasi delle colonne della matrice A porta alla costruzione di un’altra matrice T , generatrice di un codice equivalente a C perchè T
è sempre in forma standard ( [3], pag. 64).
Corollario 4.2.8. Per ogni (n, k)-codice (o codice sistematico) sopra un campo Fq esiste una matrice standard
G = (Ik |A)
le cui righe generano C oppure generano un (n, k)-codice C1 equivalente a C. Viceversa se C ammette una matrice standard allora è un codice sistematico.
Esempio 4.2.9. Sia C un codice lineare su GF (2) avente matrice generatrice

1 0 1 1 1
G= 0 1 1 0 1 
1 1 0 0 0

(1) Trasformare G in forma normale.
(2) Determinare quante parole contiene C.
(3) Trovare la distanza minima d.
Soluzione (1) Poichè il minore costituito dalle prime tre colonne è nullo, non è possibile
trasformare G in forma standard usando solo trasformazioni elementari sulle righe. Per avere le prime tre colonne linearmente indipendenti,
applichiamo alle posizioni (ossia alle colonne di G) la permutazione
1 7→ 4, 2 7→ 2, 3 7→ 3, 4 7→ 1, 5 7→ 5,
otteniamo la matrice


1 0 1 1 1
Ḡ =  0 1 1 0 1 
0 1 0 1 0
3. CODIFICA NEI CODICI LINEARI
43
che ha le prime tre colonne linearmente indipendenti e perciò si può operare sulle righe. Sostituendo la terza riga con la somma della seconda e
terza riga, si ottiene


1 0 1 1 1
 0 1 1 0 1 
0 0 1 1 1
Sostituendo alla prima riga la somma della prima con la terza riga e
sostituendo alla seconda riga la somma della seconda e terza riga, si ottiene


1 0 0 0 0
 0 1 0 1 0 
0 0 1 1 1
che è una matrice in forma standard e genera un codice equivalente a
quello dato.
(2) C ha lunghezza 5 e dalla G si deduce che k = 3, pertanto C è un (5, 3)codice binario e dunque |C| = 23 = 8.
(3) La parola (10000) appartiene a C ed ha peso 1 e perciò d = 1.
3. Codifica nei codici lineari
Codificare un messaggio in un (n, k)-codice significa associare ad un messaggio
costituito da k simboli una parola data da una n-upla in modo che ad ogni k-upla
corrisponda una ed una sola parola.
Per i codici lineari l’algoritmo di codifica è quello di seguito illustrato.
Sia C ⊆ Fqn , Fq = GF (q), un (n, k)-codice lineare avente matrice generatrice


e11 · · · e1k · · · e1n
 e21 · · · e2k · · · e2n 

G=
 ...

ek1 · · · ekk · · · ekn
Supponiamo che i primi k posti siano di informazione. Le parole del codice C
sono le n-uple che si ottengono combinando linearmente le righe di G tramite le
k-uple di elementi di Fq . Codifichiamo ogni messaggio m = (m1 , m2 , . . . , mk ) nella
parola di C che si ottiene moltiplicando m per G, dunque m viene codificata in
3. CODIFICA NEI CODICI LINEARI
e11 · · ·
 e21 · · ·
c = (m1 , m2 , · · · , mk ) 
 ...

e1k · · ·
e2k · · ·
44

e1n
e2n 
 = (c1 , c2 , · · · , cn )

ek1 · · · ekk · · · ekn
ossia
c=m·G
dove il prodotto è, come di consueto, righe per colonne, cioè l’i-esima coordinata
del prodotto m · G è il prodotto scalare ci = m1 e1,i + m2 e2,i + · · · + mk ek,i . In definitiva l’operazione di codifica procede per semplici operazioni algebriche di somma
e prodotto.
L’algoritmo descritto associa ad ogni messaggio una ed una sola parola del
codice e pertanto costituisce uno schema di codifica per un (n, k)-codice lineare.
La codifica di un codice lineare è ancora più semplice se la matrice generatrice
è in forma standard. Sia G = (Ik |A). Si ha
(m1 , . . . , mk )(Ik |A) = (m1 , m2 , . . . , mk , m1 e1,k+1 +. . .+mk ek,k+1 , . . . m1 e1n +. . .+mk ekn )
Il messaggio m = (m1 , . . . , mk ) viene codificato nella parola c = (c1 , . . . , cn ), con
ci = mi , 1 ≤ i ≤ k, e (ck+1 , . . . , cn ) = (m1 , . . . , mk )A.
I simboli ck+1 , . . . , cn sono di controllo.
Esempio 4.3.1. Sia C il codice lineare ternario con matrice generatrice G scritta
in forma standard :


1 0 0 1 2 0
G =  0 1 0 0 1 1 .
0 0 1 2 0 1
Codificare la sequenza 102101210122 emessa dalla sorgente.
Soluzione - Da G si deduce che C ha lunghezza 6 ed ha tre simboli di informazione
e pertanto C è un (6, 3)-codice ternario. Ogni tre simboli della sequenza data
rappresentano un messaggio e perciò nella codifica ad ogni blocco di tre simboli
vengono aggiunti tre simboli di controllo. Dividiamo la sequenza emessa dalla
sorgente in blocchi di lunghezza 3:
102, 101, 210, 122
e codifichiamo ogni blocco. Si ha:
(102) · G = (102222)
(101) · G = (101021)
(210) · G = (210221)
4. DECODIFICA DEI CODICI LINEARI. TABELLA STANDARD
45
(122) · G = (122211)
e pertanto verrà trasmessa la sequenza
102222101021210221122211
4. Decodifica dei codici lineari. Tabella standard
Sia C ⊆ Fqn un (n, k)-codice lineare costruito su Fq = GF (q). Il gruppo (C, +)
è un sottogruppo di (Fqn , +) e |C| = q k e pertanto (C, +) in (Fqn , +) ha m = q n−k
laterali C1 = C, C2 , . . . , Cm . Si ha :
• Ogni elemento di Fqn appartiene ad uno ed un solo laterale Ci , i = 1, . . . , m
e perciò un qualsiasi vettore y ricevuto appartiene ad un solo Ci , ossia
y = ai + c, essendo c una parola del codice C ed ai un elemento di Fqn .
• Se è stata trasmessa la parola x e si riceve y, si ha e = y − x = ai + c − x =
ai + c̄, che è un elemento di Ci quindi l’errore 00 e 00 è un elemento dello
stesso laterale a cui appartiene l’elemento ricevuto.
• Poichè l’errore più probabile è quello di peso minimo, il decodificatore sceglie come vettore errore il vettore e∗ di peso minimo fra i vettori
appartenenti a Ci e decodifica la n-upla ricevuta come y − e∗ .
Per ogni laterale Ci , i = 1, . . . , m, occorre fissare una parola ai ∈ Ci quale
leader (o direttrice) del laterale. Il leader deve essere scelto fra i vettori di peso
minimo appartenenti a quel laterale.
Teorema 4.4.1. Sia C ⊆ Fqn . Se y ∈ Fqn appartiene al laterale Ci , ossia
se y = ai + cj , essendo ai il leader del laterale Ci e cj una parola di C, allora
d(y, cj ) ≤ d(y, c) per ogni c ∈ C.
Dimostrazione. Da y = ai +cj si ha d(y, cj ) = d(ai +cj , cj ) = w(ai +cj −cj ) =
w(ai ), inoltre d(y, c) = d(ai + cj , c) = w(ai + cj − c). Poichè ai + cj − c ∈ Ci ed ai
è il leader di Ci , segue che w(ai ) ≤ w(ai + cj − c), quindi d(y, cj ) ≤ d(y, c) ossia cj
è la parola di C più vicina al vettore ricevuto y.
I laterali del gruppo (C, +) permettono di decodificare i codici lineari tramite
una tabella , detta tabella standard, costruita nel seguente modo.
Tutti gli elementi di Fqn si distribuiscono in una matrice-tabella Σ = (σij ) con
q n−k righe e q k colonne. Ogni riga contiene gli elementi di un laterale di C in modo
tale che valgono le seguenti proprietà.
(1) La prima riga contiene tutti gli elementi del codice C, iniziando dal vettore
nullo ossia σ11 = (00 · · · 0).
4. DECODIFICA DEI CODICI LINEARI. TABELLA STANDARD
46
(2) Per ogni indice di riga i, nella prima colonna (ossia come elemento σi1 )
si scrive la parola ai scelta come il leader del laterale Ci ; ai deve essere
scelto fra i vettori di peso minimo appartenenti a quel laterale.
(3) Per ogni coppia di indici (i, j) è σij = ai + σ1j , pertanto la riga i-esima
contiene tutti gli elementi del laterale ai + C.
Un semplice algoritmo per costruire una tabella standard Σ di C è il seguente:
• primo passo: distribuire le parole di C sulla prima riga di Σ con l’unica
condizione σ11 = 0;
• secondo passo: scegliere una parola a2 di peso minimo in Fqn − C e
porre σ21 = a2 ;
• terzo passo: distribuire sulla seconda riga di Σ le parole di a2 + C in
modo che sia σ2j = a2 + σ1j ;
• quarto passo: scegliere una parola a3 di peso minimo in Fqn \{C∪(a2 +C)}
e porre σ31 = a3 ;
• quinto passo: distribuire sulla terza riga di Σ le parole di a3 + C in modo
che sia σ3j = a3 + σ1j ;
. . . continuare in questo modo fino all’esaurimento delle parole di Fqn .
La tabella così costruita contiene ogni elemento di Fqn una ed una sola volta.
Se il decodificatore riceve un elemento y ∈ Ci , trova y nella tabella e decodifica y
come la parola del codice che si trova nella stessa colonna, cioè come y − ai che è
la parola del codice più vicina ad y.
Esempio 4.4.2. Sia C = {0000, 1011, 0101, 1110} un (4, 2)-codice binario
lineare. La tabella standard è:
C1 = C
C2
C3
C4
(0
(1
(0
(0
0
0
1
0
0
0
0
1
0)
0)
0)
0)
(1
(0
(1
(1
0
0
1
0
1
1
1
0
1)
1)
1)
1)
(0
(1
(0
(0
1
1
0
1
0
0
0
1
1)
1)
1)
1)
(1
(0
(1
(1
1
1
0
1
1
1
1
0
0)
0)
0)
0)
Se ad esempio viene ricevuto y = (1111), allora la parola trasmessa è c =
y − (0100) = (1111) − (0100) = 1011 che è proprio la parola di C che si trova nella
stessa colonna di y.
Nel paragrafo 6 di questo capitolo, si vedrà che questo schema di decodifica può
essere semplificato usando il concetto di codice duale e di sindrome di un vettore.
5. CODICE DUALE E MATRICE DI CONTROLLO
47
5. Codice duale e matrice di controllo
Per trovare metodi che semplifichino la decodifica di un codice lineare, occorre
introdurre alcune nozioni.
Poichè l’insieme delle parole di un codice lineare costituisce un sottospazio
di uno spazio vettoriale finito, in questi spazi vettoriali non si può introdurre la
nozione di prodotto scalare in senso euclideo; è però ugualmente possibile definire
la nozione di prodotto scalare e il concetto di ortogonalità fra vettori.
Definizione 4.5.1. Comunque presi x, y ∈ Fqn
x • y = (x1 , x2 , . . . , xn ) • (y1 , y2 , . . . , yn ) =
n
X
xi yi
i=1
è detto prodotto scalare di x e y.
Due vettori si dicono ortogonali se il loro prodotto scalare è nullo.
Un vettore si dice isotropo se è ortogonale a se stesso.
Si ricordi che nella definizione precedente la somma è calcolata in GF (q).
Inoltre è facile verificare che, comunque presi x, y, z ∈ Fqn , λ ∈ Fq , si ha
(1) x • y = y • x
(2) x • (y + z) = x • y + x • z
(3) (λx) • y = λ(x • y) .
Si noti che a differenza di quanto accade nella geometria euclidea, quando si
opera00 in un campo finito il prodotto scalare di un vettore non nullo per se stesso
può essere zero. Per esempio, in GF (2) risulta (1, 1, 0, 0) • (1, 1, 0, 0) = 1 + 1 = 0.
00
Definizione 4.5.2. Sia C ⊆ Fqn un sottospazio di dimensione k. Si definisce
spazio ortogonale a C e si denota con C ⊥ l’insieme
C ⊥ = {x ∈ Fqn | x • c = 0 ∀ c ∈ C}.
C ⊥ prende il nome di codice duale o ortogonale a C. Se C = C ⊥ , il codice C si
dice autoduale .
Nota 4.5.3.
(1) C ⊥ è un sottospazio vettoriale di Fqn perchè è chiuso rispetto alle operazioni
di addizione di vettori e di moltiplicazione di un vettore per uno scalare.
(2) A differenza degli spazi vettoriali definiti su R, i sottospazi C e C ⊥ di Fqn
possono avere in comune vettori diversi dal vettore nullo, tali vettori sono
i vettori isotropi.
(3) (C ⊥ )⊥ = C.
5. CODICE DUALE E MATRICE DI CONTROLLO
48
(4) Sia C ⊆ Fqn autoduale, allora x • y = 0 per ogni coppia di parole di C non
necessariamente distinte e pertanto si ha
n
dim C = dim C ⊥ = k =
2
Ricordiamo che se A è una matrice, con At si indica la matrice trasposta di A,
ossia la matrice che ha per colonne le righe di A.
Teorema 4.5.4. Sia C ⊆ Fqn un (n, k)-codice generato dalla matrice G. Allora
un vettore x ∈ Fqn è una parola del codice duale C ⊥ se e solo se è ortogonale a tutti
i vettori riga di G:
x ∈ C⊥ ⇔
xGt = 0
dove 0 è la matrice 1 × k i cui elementi sono tutti nulli.
Dimostrazione. Sia x ∈ C ⊥ , allora x è ortogonale ad ogni parola di C e in
particolare alle parole che costituiscono una base di C e pertanto xGt = 0.
Viceversa, sia xGt = 0. Allora x è ortogonale a tutti i vettori e1 , e2 , . . . , ek che
costituiscono una base di C. Poichè per ogni parola c ∈ C si ha c = λ1 e1 +. . .+λk ek
segue che
x • c = x • (λ1 e1 + . . . + λk ek ) = λ1 (x • e1 ) + . . . + λk (x • ek ) = 0.
Pertanto x è ortogonale ad ogni parola c ∈ C e quindi x ∈ C ⊥ .
Teorema 4.5.5. Se C ⊆ Fqn è un (n, k)-codice lineare allora C ⊥ è un
(n, n − k)-codice lineare.
Dimostrazione. Dal teorema precedente segue che i vettori x ∈ C ⊥ sono
tutti e soli i vettori di Fqn ortogonali ai vettori di una base {ei }, i = 1, . . . , k, di C.
Questi vettori sono dati da tutte e sole le soluzioni del sistema

e11 x1 + e12 x2 + · · · + e1n xn = 0


 e21 x1 + e22 x2 + · · · + e2n xn = 0
..

.


ek1 x1 + ek2 x2 + · · · + ekn xn = 0
Questo è un sistema lineare omogeneo di k equazioni in n incognite con rango
della matrice dei coefficienti uguale a k quindi ha q n−k autosoluzioni delle quali
esattamente n−k linearmenti indipendenti. Segue che n−k autosoluzioni qualsiasi,
linearmente indipendenti, sono una base di C ⊥ e perciò dim C ⊥ = n − k.
dim C + dim (C ⊥ ) = n
5. CODICE DUALE E MATRICE DI CONTROLLO
49
Definizione 4.5.6. Sia C un (n, k)-codice lineare. Una matrice generatrice di
C è detta matrice di controllo (o matrice di controllo di parità ) del codice
C, si denota con H ed è di tipo (n − k) × n.
⊥
Teorema 4.5.7. Un vettore x ∈ Fqn , x = (x1 x2 · · · xn ), è una parola del codice
C se e solo se xH t = 0, dove 0 è la matrice 1 × (n − k) i cui elementi sono tutti
nulli. In simboli:
x ∈ C ⇔ xH t = 0
Dimostrazione. Un vettore x ∈ Fqn è una parola di C se e solo se è ortogonale
a C ⊥ ossia se e solo se è ortogonale a tutti i vettori y ∈ C ⊥ ossia se e solo se è
ortogonale a tutti i vettori di una base di C ⊥ . Poichè le componenti dei vettori
di una base di C ⊥ sono le righe di H, un vettore x è una parola di C se e solo se
xH t = 0.
Dunque la conoscenza di H permette di controllare facilmente se un vettore
di Fqn è una parola del codice C e pertanto C può essere completamente descritto
da una sua matrice di controllo di parità. Questo è il motivo per cui H si chiama
matrice di controllo di C e le equazioni del sistema xH t = 0 sono dette equazioni
di controllo.
Così come la matrice generatrice, anche la matrice di controllo di un codice non
è unica, in generale. Se come matrice generatrice di C si sceglie quella standard
allora la costruzione della matrice H è semplice ed immediata.
Teorema 4.5.8. Sia G = (Ik | A) una matrice generatrice standard di un
(n, k)-codice lineare C. Allora H = (−At | In−k ) è una matrice di controllo per C.
Dimostrazione. Sia

1 0 . . . 0 e1,k+1 . . . e1,n
 0 1 . . . 0 e2,k+1 . . . e2,n 

G=
 ...


0 0 . . . 1 ek,k+1 . . . ek,n
una matrice generatrice rispetto alle basi {ei } di C e {bj } di Fqn , per i = 1, . . . , k; j =
1, . . . , n. Un vettore x = (x1 , . . . , xn ) ∈ Fqn è una parola di C ⊥ se e solo se xGt = 0,
cioè se e solo se è soluzione del sistema

x1 + e1,k+1 xk+1 + · · · + e1,n xn = 0


 x2 + e2,k+1 xk+1 + · · · + e2,n xn = 0
..

.


xk + ek,k+1 xk+1 + · · · + ek,n xn = 0
5. CODICE DUALE E MATRICE DI CONTROLLO
50
Esso ha n − k autosoluzioni linearmente indipendenti perchè è lineare omogeneo di
k equazioni in n incognite con caratteristica della matrice dei coefficienti uguale a
k. Troviamo le (n − k) autosoluzioni assegnando alle incognite xk+1 , . . . , xn successivamente i valori (1, 0, . . . , 0), (0, 1, . . . , 0), (0, 0, . . . , 1). In questo modo otteniamo
una base di C ⊥ data dai vettori:
(−e1,k+1 , −e2,k+1 , . . . , −ek,k+1 , 1, 0, . . . , 0)
(−e1,k+2 , −e2,k+2 , . . . , −ek,k+2 , 0, 1, . . . , 0)
...
...
...
(−e1,n , −e2,n , . . . , −ek,n , 0, 0, . . . , 1)
e pertanto la matrice


−e1,k+1 −e2,k+1 . . . −ek,k+1 1 0 . . . 0
 −e1,k+2 −e2,k+2 . . . −ek,k+2 0 1 . . . 0 
 = (−At | In−k )
H=
..


.
−e1,k+n −e2,k+n . . . −ek,k+n 0 0 . . . 1
è una matrice di controllo per C.
Esempio 4.5.9.
(1) La matrice di controllo del codice binario (7, 4) di Hamming è


1 0 1 1 1 0 0
H =  1 1 0 1 0 1 0  = (−At | In−k )
1 1 1 0 0 0 1
la quale ha effettivamente rango 3.
(2) Sia C il (7, 4)-codice sopra

0
 0
G=
 2
2
Z3 con matrice generatrice

0 0 2 1 1 0
0 1 1 0 2 0 

1 0 2 0 2 0 
0 0 1 0 0 1
Per trovare una matrice del tipo G0 = (I4 |A) che generi un codice D equivalente a C, permutiamo le colonne di G in modo che assumano l’ordine
5, 3, 2, 7, 1, 4, 6, ossia applichiamo alle posizioni (colonne) la permutazione
1 7→ 5, 2 7→ 3, 3 7→ 2, 4 7→ 6, 5 7→ 1, 6 7→ 7, 7 7→ 4,
5. CODICE DUALE E MATRICE DI CONTROLLO
ossia moltiplichiamo a destra

0 0
 0 0

 0 1

P = 0 0
 1 0

 0 0
0 0
In questo modo si ottiene
D equivalente a C

1 0 0 0 0 2

0 1 0 0 0 1
G0 = 
 0 0 1 0 2 2
0 0 0 1 2 1
51
G per la matrice di permutazione

0 0 1 0 0
1 0 0 0 0 

0 0 0 0 0 

0 0 0 0 1 
0 0 0 0 0 

0 1 0 0 0 
0 0 0 1 0
una matrice standard G0 che genera un codice

1
2 
 = (I4 |A),
2 
0
Una matrice generatrice di D⊥ è

0 0
0
t

1 2
H = (−A | I3 ) =
2 1
Moltiplicando H 0 a destra

0 0
 0 0

 0 1

Pt =  0 0

 1 0
 0 0
0 0
si ottiene la seguente matrice

1 1

0 1
H=
0 1

0
 0
A=
 2
2
2
1
2
1

1
2 
.
2 
0
allora

1 1 1 0 0
1 2 0 1 0 .
1 0 0 0 1
per la matrice di permutazione

0 0 1 0 0
1 0 0 0 0 

0 0 0 0 0 

0 0 0 1 0 

0 0 0 0 0 
0 0 0 0 1 
0 1 0 0 0
generatrice per C ⊥ :

0 0 0 1 0
2 0 1 2 1 .
1 1 2 0 0
Osserviamo che GH t = 0; inoltre H ha, come previsto, rango n − k = 3.
Esempio 4.5.10. Trovare la matrice di controllo di un codice lineare binario C
assegnato tramite la matrice


1 0 0 1 1
G =  0 1 0 1 0 .
0 0 1 0 1
5. CODICE DUALE E MATRICE DI CONTROLLO
Un vettore x ∈ F25 è ortogonale a C se
forma estesa significa:

+x4 +x5
 x1
+x2
+x4

+x3
+x5
52
e solo se xGt = 0. Se x = (x1 x2 x3 x4 x5 ), in
= 0
= 0 ,
= 0

 x1 = x2 + x3
x4 = x2

x5 = x3
E pertanto C ⊥ = {x | x = (x2 + x3 , x2 , x3 , x2 , x3 )}.
Una base di C ⊥ è {(1, 1, 0, 1, 0), (1, 0, 1, 0, 1)} quindi una matrice di controllo di C
è
1 1 0 1 0
H=
.
1 0 1 0 1
Un vettore x ∈ F25 è una parola di C se e solo se xH t = 0 ossia
x1 +x2
+x4
= 0
x1
+x3
+x5 = 0
Queste due equazioni sono equazioni di controllo del codice C.
Come mostra il seguente teorema, partendo da una matrice di controllo si può
anche calcolare la distanza minima del codice lineare.
Teorema 4.5.11. Sia H una matrice di controllo di un (n, k)-codice lineare
C ⊆ Fqn . Allora la distanza minima del codice è il minimo ordine di un insieme
linearmente dipendente di colonne della matrice H.
Dimostrazione. Si rinvia a [1] pag. 146 − 148.
Corollario 4.5.12. Sia H una matrice di controllo di un (n, k)-codice lineare
C ⊆ Fqn con distanza minima d. Si ha :
(1) d − 1 colonne di H sono sempre linearmente indipendenti.
(2) H ha rango almeno d − 1.
Dimostrazione. Segue dal teorema precedente.
Nel Corollario 3.2.8 si è dimostrato che un (n, k)-codice con distanza minima
d = 2h + 1 è h-correttore. Allora, per il teorema precedente, la costruzione di un
codice h-correttore equivale alla costruzione di una matrice H di tipo (n−k)×n con
rango n − k e tale che 2h colonne qualsiasi di essa siano linearmente indipendenti.
In particolare, costruire un (n, k)-codice lineare 1-correttore equivale a costruire
una matrice H di tipo (n − k) × n con rango (n − k) e nella quale due colonne
qualsiasi siano linearmente indipendenti.
6. DECODIFICA DEI CODICI LINEARI PER SINDROME
53
Esempio 4.5.13. Consideriamo la seguente matrice H di rango 3 e con elementi
in GF (3) :


2 0 0 1 1
H =  0 2 0 0 2 .
0 0 1 2 0
Le colonne di H sono a due a due linearmente indipendenti e ne esistono tre
linearmente dipendenti (ad esempio la prima, la seconda e la quinta) e pertanto 3
è il minimo numero di colonne linearmente dipendenti. Quindi H è una matrice
di controllo di un (5, 2)-codice ternario con d = 3. Questo codice è 1-correttore
perchè d = 2 · 1 + 1.
Se d è la distanza minima di un (n, k)-codice C la limitazione di Singleton
d ≤ n − k + 1 ci dà una condizione necessaria per l’esistenza di C ma ciò non
assicura che C esista. In generale, il problema dell’esistenza di un codice avente
parametri assegnati è difficile. Se il codice è lineare, un modo per affrontarlo è
quello di dare condizioni per l’esistenza di una matrice di controllo di C.
Teorema 4.5.14. Si ha
(1) Un (n, k)-codice lineare C ⊆ F2n avente distanza minima d esiste se vale
n−1
n−1
1+
+ ...,
< 2n−k
1
d−2
(2) Un (n, k)-codice lineare C ⊆ Fqn avente distanza minima d esiste se vale
d−2
X
s n−1
(q − 1)
< q n−k
s
s=0
Dimostrazione. Si rinvia a [1] pag. 149, 150.
6. Decodifica dei codici lineari per sindrome
La nozione di codice ortogonale si rivela particolarmente utile per costruire
algoritmi di decodifica specifici per i codici lineari.
Definizione 4.6.1. Sia H una matrice di controllo del (n, k)-codice lineare
C ⊆ Fqn . Si definisce sindrome di un vettore x ∈ Fqn il vettore
s = x · H t ∈ Fqn−k .
6. DECODIFICA DEI CODICI LINEARI PER SINDROME
54
Nota 4.6.2. L’utilità della matrice di controllo H associata al codice C ⊆ Fqn
discende dal teorema 4.5.7:
un vettore v dello spazio vettoriale Fqn è una parola del codice C se e solo se
t
vH = 0.
Allora se durante la trasmissione di una parola non entrano errori, la
sua sindrome è zero, ma non vale il viceversa. Infatti potrebbero entrare
un numero di errori tale da trasformare la parola trasmessa in un’altra parola del
codice. In questo caso, pur essendo zero la sindrome della parola ricevuta, essa è
diversa dalla parola trasmessa. Senza fare nessuna ipotesi sul numero massimo di
errori che possono entrare in una parola durante la trasmissione e sulla distanza
minima del codice, in effetti non si può dire se la parola ricevuta è quella trasmessa.
Ma se, per esempio, sappiamo che in ogni parola entra al più un errore durante la
trasmissione e che d = 3, allora una parola non può diventare un’altra parola del
codice durante la trasmissione e quindi se la sindrome della parola ricevuta è zero,
si è certi che la parola ricevuta è quella trasmessa, mentre se la sindrome è diversa
da zero è entrato un errore.
La sindrome di un vettore può essere di aiuto per correggere errori eventualmente entrati durante la trasmissione delle parole, ma è anche un valido aiuto per
semplificare notevolmente il metodo di decodifica per i codici lineari basato sui
laterali di un sottogruppo. Vale infatti il seguente teorema.
Teorema 4.6.3. Sia H una matrice di controllo di un (n, k)-codice lineare
C ⊆ Fqn . Allora due vettori x, y ∈ Fqn sono in uno stesso laterale di C se e solo se
hanno la stessa sindrome.
Dimostrazione. Siano x, y ∈ Fqn , risulta
x + C = y + C ⇔ y − x ∈ C ⇔ (y − x)H t = 0 ⇔ yH t − xH t = 0 ⇔ xH t = yH t
.
Dal teorema ora dimostrato si ha in particolare che le sindromi sono in corrispondenza biunivoca con i laterali di C e che la sindrome di un qualsiasi vettore
di un laterale Ci è uguale alla sindrome del leader scelto per Ci . Assegnata H, la
corrispondenza che associa ad ogni leader la sua sindrome è biunivoca, ciò semplifica la decodifica tramite la tabella standard. L’algoritmo di decodifica diventa il
seguente.
Algoritmo
• Passo
• Passo
• Passo
di
1.
2.
3.
decodifica mediante sindrome.
Si calcola la sindrome s = y · H t del vettore ricevuto y.
Si trova il leader ai avente come sindrome s.
Si decodifica y come la parola y − ai .
6. DECODIFICA DEI CODICI LINEARI PER SINDROME
55
Esempio 4.6.4. Sia C il (4, 2)-codice lineare binario avente come matrice generatrice
1 1 1 0
G=
.
0 1 1 1
Operando sulle righe, la G può essere trasformata nella matrice standard
1 0 0 1
0
G =
= (I2 |A).
0 1 1 1
Una matrice di controllo per C è allora:
0 1 1 0
H=
= (−At |I4−2 ).
1 1 0 1
Costruiamo ora la TABELLA standard:
a1
a2
a3
a4
=0
=1
=0
=0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0
0
0
0
0
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
0
1
1
0
0
1
0
0
0
0
1
1
1
1
1
La sindrome dei leader a1 , a2 , a3 , a4 è rispettivamente
s1 = a1 H t = (00), s2 = a2 H t = (01), s3 = a3 H t = (11), s4 = a4 H t = (10).
Supponiamo si riceva il vettore y = (0101). Si ha yH t = (10) = s4 , allora y viene
decodificato nella parola y − a4 = 0111.
Lo schema di decodifica mediante sindrome necessita quindi di una matrice
con due sole colonne, la prima delle quali formata dalle parole leader, la seconda
formata dalle sindromi delle parole leader. E’ chiaro quindi che, se C è abbastanza
grande, la decodifica mediante sindrome è molto più veloce rispetto quella con
tabella standard.
Esempio 4.6.5. Sia C il (6, 3)-codice binario le
controllo di parità sono date, rispettivamente, da



1 1 0 1 0 0
1
G =  0 1 1 0 1 0 , H =  0
1 0 1 0 0 1
0
cui matrici generatrice e di

0 0 1 0 1
1 0 1 1 0 .
0 1 0 1 1
6. DECODIFICA DEI CODICI LINEARI PER SINDROME
Tale codice ha
leader
000000
000001
000010
000100
001000
010000
100000
001100
56
distanza minima d = 3. La tabella standard di C è
110100
110101
110110
110000
111100
100100
010100
111000
011010
011011
011000
011110
010010
001010
111010
010110
101001
101000
101011
101101
100001
111001
001001
100101
101110
101111
101100
101010
100110
111110
001110
100010
110011
110010
110001
110111
111011
100011
010011
111111
011101
011100
011111
011001
010101
001101
111101
010001
000111
000110
000101
000011
001111
010111
100111
001011
Possiamo semplificare il procedimento limitandoci a considerare la corrispondenza
biunivoca fra i leader e le rispettive sindromi. Rappresentiamo questa corrispondenza con la seguente tabella formata
• dalla colonna dei vettori leader scelti fra quelli di peso minimo nella
F6
rispettiva classe Ci , i = 1, 2, . . . , 8 (Ci sono gli elementi del quoziente C2 );
• dalla colonna s delle sindromi
leader
s
000000 000
000001 101
000010 011
000100 110
001000 001
010000 010
100000 100
001100 111
Supponiamo di ricevere la parola y = (100011). Calcoliamo s(y) = yH t = (010);
poichè (010) è la sindrome del leader a6 della classe C6 , decodifichiamo y come
y − ai = (100011) − (010000) = (110011).
Nota 4.6.6. L’algoritmo di decodifica tramite sindrome, richiede di precomputare e memorizzare la corrispondenza fra tutte le possibili sindrome e i leader
delle classi. Se il codice C utilizza parole molto lunghe, può occupare notevole
spazio. Se il codice è binario, un metodo di implementazione finalizzato a ridurre l’occupazione di memoria di un decodificatore è quello presentato nel seguente
algoritmo di decodifica.
Algoritmo di Decodifica 00 passo-passo00 per codici binari
(1) Costruire la tabella Σ che associa ad ogni sindrome s il peso minimo di
un elemento con sindrome s; denotiamo tale numero con Σ(s).
(2) Porre i = 1.
6. DECODIFICA DEI CODICI LINEARI PER SINDROME
57
(3) Calcolare la sindrome del vettore ricevuto s = yH t e determinare, tramite
la tabella Σ, il peso w = Σ(s) del corrispondente leader di classe.
(4) • Se w = 0, allora non sono individuati errori, il procedimento di
decodifica termina restituendo la parola p = y.
• Se w 6= 0 e Σ((y + ei )H t ) ≤ Σ(yH t ), sostituire y con y + ei dove ei
è un vettore le cui componenti sono tutte 0 tranne la i-esima.
(5) Porre i = i + 1.
(6) Se i > n, segnalare che non si è riusciti a correggere l’errore.
(7) Tornare al passo 3.
Nel funzionamento dell’algoritmo, il punto fondamentale è che, durante tutto
il processo di decodifica, il peso dell’errore non può mai crescere. Dopo al più n
passi, rimane determinato un vettore che può cadere nella classe il cui leader ha
peso nullo; se questo si verifica, allora il vettore è stato decodificato correttamente.
Esempio 4.6.7. Sia C il codice dell’esempio 4.6.5. Al posto della tabella che
associa ad ogni leader di classe la corrispettiva sindrome, è sufficiente considerare
la tabella in cui i leader delle classi laterali sono sostituiti con i propri pesi.
s w(Cj )
000
0
101
1
011
1
110
1
001
1
010
1
100
1
111
2
Teorema 4.6.8. Se C ⊆ F2n è un codice lineare binario allora la sindrome
di una parola ricevuta è una matrice riga avente come elementi la somma degli
elementi delle colonne di H corrispondenti ai posti in cui sono entrati errori.
Dimostrazione. Sia x la parola di C trasmessa. Allora xH t = 0. Supponiamo
che entrino degli errori e sia e il vettore errore il quale ha tante componenti non
nulle quanti sono gli errori entrati; infatti la parola ricevuta è y = x + e e si ha
yH t = (x + e)H t = xH t + eH t = eH t .
Sia e = (0, . . . , 1a , . . . , 1b , . . . , 0).
7. CODICI LINEARI 1-CORRETTORI
58
Se
h1,1
 h2,1
H=
..

.

...
...
h1,a
h2,a
...
...
h1,b
h2,b
...
...

h1,n
h2,n 


hn−k,1 . . . hn−k,a . . . hn−k,b . . . hn−k,n
segue
yH t = eH t =
h1,a + h1,b
h2,a + h2,b
...
hn−k,a + hn−k,b
Dal teorema ora dimostrato segue che se le colonne di una matrice di controllo
H di un codice binario C sono a due a due linearmente indipendenti (cioè distinte
e non nulle), allora si può decidere dove è un singolo errore e correggerlo.
D’altra parte se le colonne di H sono a due a due linearmente indipendenti e
ne esistono tre linearmente dipendenti, allora d = 3 e C è 1-correttore.
7. Codici lineari 1-correttori
La decodifica tramite tabella standard è molto utile nei codici lineari che correggono almeno 2 errori mentre la decodifica nei codici lineari 1-correttori può
essere fatta più semplicemente.
Schema di Decodifica per i codici lineari 1-correttori q-ari
Sia C ⊆ Fqn un codice lineare con d(C) ≥ 3, ossia sia C un codice 1-correttore.
Sia H una sua matrice di controllo e supponiamo che in ogni parola entri al più
un errore ossia che per ogni errore e dovuto al canale si abbia w(e) ≤ 1.
Sia trasmessa una parola x ∈ C e sia ricevuto il vettore y = x + e. Si ha
yH t = (x + e)H t = xH t + eH t = eH t , cioè la sindrome del vettore ricevuto
uguaglia la sindrome del vettore errore. Se eH t = 0, poichè e non può essere una
parola (non nulla) di C, essendo w(e) ≤ 1, il decodificatore decide che e = 0 e
quindi y è la parola trasmessa.
Supponiamo ora che eH t 6= 0. In questo caso necessariamente e 6= 0 e
dall’ipotesi w(e) ≤ 1 segue che e ha un’unica componente non nulla, sia e =
(0, 0, . . . , ei , 0, . . . , 0). In questo caso si ha
eH t = h1,i ei h2,i ei . . . hn−k,i ei = ei h1,i h2,i . . . hn−k,i
cioè la sindrome è il prodotto tra un elemento di GF (q), che dà la 00 grandezza00 dell’errore, e la colonna di H corrispondente alla componente dove è entrato l’errore.
In questo caso la n-upla y ricevuta viene decodificata nella parola
x = y − e = (y1 , . . . , yi , . . . , yn ) − (0, . . . , 0, ei , 0, . . . , 0) =
7. CODICI LINEARI 1-CORRETTORI
59
= (yi , . . . , yi−1 , yi − ei , yi+1 , . . . , xn ).
In sintesi:
Passo 1. Si calcola la sindrome yH t del vettore y ricevuto.
Passo 2. Se yH t = 0, si suppone y sia proprio la parola trasmessa.
Passo 3. Se yH t = s 6= 0, si confronta s con ogni colonna di H.
Passo 4. Se s è multiplo di una colonna, sia la i-esima, di H secondo
lo scalare ei , allora l’errore è dato dalla n-upla avente come componente
i-esima ei e tutte le altre componenti nulle. Si decodifica y come la parola
x = y − e.
• Passo 5. Se non si verifica nessuno dei casi detti, la n-upla ricevuta contiene almeno due errori e quindi non si può risalire alla parola
trasmessa.
•
•
•
•
Se il codice è binario lo schema di decodifica diventa:
Schema di Decodifica per i codici lineari 1-correttori binari
• Passo 1. Si calcola la sindrome yH t del vettore y ricevuto.
• Passo 2. Se yH t = 0, si suppone che la parola trasmessa coincida con il
vettore ricevuto.
• Passo 3. Se yH t 6= 0 e yH t è uguale ad una colonna, la j-esima, di H,
si ha che la j-esima componente del vettore ricevuto è errata e si corregge
l’errore.
• Passo 4. Se yH t 6= 0 e yH t non è uguale ad una colonna di H, certamente
sono entrati almeno due errori e non è possibile correggerli.
Esempio 4.7.1. Consideriamo il (5, 2)-codice ternario dell’esempio 4.5.13. Supponiamo che venga trasmessa la parola x = (1 0 1 1 0) e che in uscita arrivi il
vettore y = (1 0 0 1 0). Si ha
yH t = 0 0 2 = 2 0 0 1
che implica l’esistenza di un errore di 00 grandezza 00 2 nella terza posizione. Allora
x = (1 0 0 1 0) − (0 0 2 0 0) = (1 0 1 1 0).
Nota 4.7.2. L’affidabilità che offre il canale è molto importante. Se si usa ad
esempio un codice 1-correttore, l’evento che in una parola possano entrare due o più
errori deve avere una probabilità quasi nulla. Infatti se in una parola entrano due
errori, la sindrome del vettore ricevuto può essere ancora uguale ad una colonna di
H, in tal caso i due errori non vengono rivelati e la decodifica è errata. Ciò dipende
dal fatto che, se è trasmessa una parola x ed arriva la sequenza y contenente due
errori, la sequenza y viene decodificata nella parola x0 che differisce da y per una
8. L’ENUMERATORE DEI PESI DI UN CODICE LINEARE
60
sola componente, se esiste nel codice una parola x0 con d(y, x0 ) = 1, e ciò può
accadere se d(x, x0 ) = 3.
Ad esempio riferendoci sempre al codice ternario dell’esempio 4.5.13, supponiamo di trasmettere ancora la parola x = (1 0 1 1 0) e di ricevere y = (1 0 0 0 0),
contenente due errori. Risulta yH t = (2 0 0), che è uguale alla prima colonna
di H, così che y verrebbe decodificata nella parola (0 0 0 0 0). In questo caso la
decodifica risulterebbe errata.
8. L’enumeratore dei pesi di un codice lineare
Nello studio di un codice lineare C di lunghezza n, uno dei problemi centrali
è il calcolo del numero wi = wi (C) di tutte le parole di C di peso i, per ogni
i = 1, 2, . . . , n. A tale proposito spesso si considera il polinomio
n
X
X
W (x, y) = WC (x, y) =
xw(a) y n−w(a) =
wi xi y n−i ,
a∈C
i=0
che prende il nome di enumeratore dei pesi di C.
Una importante relazione fra l’enumeratore dei pesi W (x, y) di C e l’enumeratore dei pesi W ⊥ (x, y) del codice duale di C, è data dal seguente teorema di cui
non riportiamo la dimostrazione.
Teorema 4.8.1 ( F. J. MacWilliams, 1963 ). Siano W (x, y) e W ⊥ (x, y) gli
enumeratori dei pesi rispettivamente di un (n, k)-codice C su Fq e del suo duale.
Allora risulta
W ⊥ (x, y) = q −k W (y − x, y + (q − 1)x)
e quindi, se C è autoduale, risulta
W (x, y) = q −n/2 W (y − x, y + (q − 1)x).
Nota 4.8.2. In alcuni casi la conoscenza dei pesi delle parole di una matrice
generatrice G di un codice lineare fornisce informazioni sui coefficienti del polinomio enumeratore dei pesi. Per esempio, se due parole a e b di un codice binario C
hanno peso pari 2s e 2t, rispettivamente, detto m il numero degli indici j tali che
aj = bj = 1, risulta
w(a + b) = 2s − m + 2t − m = 2(s + t − m).
Ne segue che, se le parole di G hanno tutte peso pari, allora si dice che C è un
codice pari , cioè tutte le sue parole hanno peso pari. Analogamente si prova che,
se C è autoortogonale e tutte le parole di G hanno peso divisibile per 4, la stessa
9. CODICE ESTESO
61
proprietà è vera per tutte le parole di C. In questo caso C si dice doppiamente
pari .
9. Codice esteso
Per ogni parola p = (a1 , a2 , . . . , an ) a componenti in Fq , si dice controllo di
parità di p l’opposto della somma delle sue componenti, cioè a0 = −(a1 + a2 +
· · · + an ). Considerato l’ (n, k)-codice C, rimane determinato l’ (n + 1, k)-codice C¯
definito da
C¯ = {p0 = (a0 , a1 , a2 , . . . , an ) | p ∈ C}
che è detto codice esteso di C. Tutte le parole del codice esteso hanno controllo di
parità nullo e pertanto ha senso prenderlo in considerazione solo quando le parole
di C non hanno tutte controllo di parità uguale a zero. Per esempio, il codice
ASCII esteso è proprio il codice esteso di C = F27 .
Osserviamo che, se C ha matrice controllo di parità H, allora


1 1 ··· 1
 0


H̄ = 
.
 ..

H
0
¯
è una matrice controllo di parità per C.
CAPITOLO 5
Codici Ciclici
I codici ciclici sono una famiglia di codici lineari fra le più importanti perchè essi
possono essere implementati in modo molto semplice. Questi codici sono tali che se
contengono una parola allora contengono anche tutte le sue permutazioni cicliche
e per questo si possono rappresentare algebricamente facendo uso dei polinomi
[x]
poichè esiste un isomorfismo fra gli spazi vettoriali Fqn e (xFnq−1)
.
Con abuso di linguaggio denoteremo un polinomio p(x) ∈ Fq [x] e la
[x]
sua classe nell’anello (xFnq−1)
con lo stesso simbolo.
Ogni codice di questa famiglia gode di notevoli proprietà fra cui:
• può essere costruito a partire da un singolo vettore;
• ammette degli algoritmi di decodifica efficienti;
• può rivelarsi particolarmente efficace per correggere alcune tipologie di
errore.
Per tutto il capitolo con Fq indicheremo il campo di Galois GF (q).
1. Definizioni e proprietà
Definizione 5.1.1. Un codice lineare C ⊆ Fqn si dice ciclico se applicando
una permutazione ciclica ad una qualsiasi sua parola c si ottiene un’altra parola
di C:
c = (c0 , c1 , . . . , cn−1 ) ∈ C ⇒ (cn−1 , c0 , . . . , cn−2 ) ∈ C
Sia Fq [x] l’anello dei polinomi nella variabile x e sia (xn − 1) l’ideale di Fq [x]
[x]
generato da xn − 1. Fissato il polinomio xn − 1, sia Rn [x] = ( (xFnq−1)
, +, ·) l’anello
n
quoziente dei polinomi su Fq modulo l’ideale (x − 1).
Tenendo presente che:
• i polinomi che si ottengono in corrispondenza degli elementi di Fqn sono
tutti e soli quelli di grado minore di n,
62
1. DEFINIZIONI E PROPRIETÀ
63
• ogni laterale proprio dell’ideale (xn − 1) di Fq [x] contiene un unico polinomio di grado minore di n,
ogni polinomio a coefficienti in Fq viene sostanzialmente identificato con il resto
della sua divisione per xn − 1.
Sia f : Fqn → Rn [x] l’applicazione definita da
f (c) = c0 + c1 x + . . . , cn−1 xn−1
per ogni c = (c0 , . . . , cn−1 ) ∈ Fqn .
Si ha :
(1) L’applicazione f è biettiva. Infatti Rn [x] ha come elementi i polinomi di
Fq [x] di grado minore o uguale ad n − 1 (si ricordi che se il prodotto di
due polinomi ha grado maggiore o uguale ad n, occorre prendere il suo
resto nella divisione per (xn − 1)). Dunque ogni parola può essere vista
come una n-upla di Fqn o, equivalentemente, come un polinomio di Rn [x].
(2) Rn [x] è uno spazio vettoriale di dimensione n isomorfo allo spazio vettoriale Fqn . Infatti la biezione f precedente è chiaramente un isomorfismo
di spazi vettoriali e C(x) è un sottospazio vettoriale di Rn [x].
Quanto osservato assicura che la definizione 5.1.1 equivale a
c(x) ∈ C ⇒ xc(x) ∈ C
e ciò porta immediatamente ad una caratterizzazione algebrica dei codici
ciclici.
(3) In Rn [x] moltiplicare un polinomio c(x) per x corrisponde a permutare
ciclicamente le componenti della n-pla corrispondente a c(x) (ossia a shiftare di un posto a destra). Infatti, poichè in Rn [x] risulta xn = 1, si
ha
xc(x) = c0 x + c1 x2 + . . . + cn−2 xn−1 + cn−1 xn =
= cn−1 + c0 x + c1 x2 + . . . + cn−2 xn−1 .
Esempio 5.1.2. Consideriamo il codice lineare binario di lunghezza 3:
C = {(000), (110), (101), (011)}
Esso può essere rappresentato come insieme di polinomi nella variabile x:
C = {0, 1 + x, 1 + x2 , x + x2 }.
Shiftando di un posto a destra le componenti di ogni terna, si ottiene l’insieme
{(000), (011), (110), (101)} ossia si ottiene sempre una parola di C e dunque C è
un codice ciclico. Alla stessa conclusione si arriva se in Rn [x] si moltiplica per x
ogni parola-polinomio di C, infatti si ha .
0·x = 0, (1+x)·x = x+x2 , (1+x2 )·x = x+x3 = x+1, (x+x2 )·x = x2 +x3 = x2 +1.
2. POLINOMIO GENERATORE E MATRICE GENERATRICE
64
Teorema 5.1.3. Un codice lineare C di lunghezza n è ciclico se e solo se è un
ideale di Rn [x].
Dimostrazione. Sia C un ideale di Rn [x]. Allora comunque preso c(x) ∈ C
si ha xc(x) ∈ C e pertanto C è ciclico.
Viceversa, sia C ciclico. Essendo C lineare, se c1 (x), c2 (x) ∈ C allora c1 (x) −
c2 (x) ∈ C. Inoltre essendo C ciclico, se c(x) ∈ C anche xc(x), x2 c(x), . . . , xn−1 c(x) ∈
C, pertanto per la linearità di C, anche λ0 c(x) + λ1 xc(x) + . . . + λn−1 xn−1 c(x) =
(λ0 +λ1 x+. . .+λn−1 xn−1 )c(x) è una parola di C. Facendo variare i coefficienti λi in
Fq , l’espressione (λ0 + λ1 x + . . . + λn−1 xn−1 ) fornisce tutti i polinomi di Rn [x]. Il prossimo teorema assicura che ogni codice ciclico C ∈ Fqn è un ideale principale di Rn [x] ossia Rn [x] è un anello ad ideali principali. Poichè C = {0} è un
ideale principale di Rn [x], nel seguito supporremo C =
6 {0}.
Teorema 5.1.4. Sia g(x) un polinomio monico non nullo di grado minimo
appartenente ad un codice ciclico C di lunghezza n. Allora ogni elemento c(x) ∈ C
può essere scritto nella forma c(x) = f (x)g(x) per un opportuno f (x) ∈ Rn [x].
Dimostrazione. Supponiamo per assurdo che c(x) ∈ C non sia multiplo di
g(x). Poichè g(x) è di grado minimo in C, si ha c(x) = q(x)g(x)+r(x) con gr[r(x)] <
gr[g(x)]. Poichè c(x), q(x)g(x) ∈ C e C è lineare, segue che r(x) = c(x)−q(x)g(x) ∈
C. Se r(x) 6= 0 si ha un assurdo perchè r(x) ha grado minore di g(x).
2. Polinomio generatore e matrice generatrice
Definizione 5.2.1. Si definisce polinomio generatore di un codice ciclico C
un polinomio g(x) ∈ C non nullo, monico, di grado minimo.
Teorema 5.2.2. Il polinomio generatore di un codice ciclico è unico.
Dimostrazione. Supponiamo per assurdo che g(x) e g1 (x) siano due generatori del codice ciclico C e dunque monici e di grado minimo. Poichè C è un ideale,
segue che il polinomio g(x) − g1 (x) appartiene a C e ha grado minore del grado di
g(x) e g1 (x) e ciò è assurdo.
Per la ricerca del polinomio generatore, vengono in aiuto i seguenti teoremi.
Teorema 5.2.3. Se g(x) è il polinomio generatore di un codice ciclico di
lunghezza n, allora g(x) divide xn − 1.
2. POLINOMIO GENERATORE E MATRICE GENERATRICE
65
Dimostrazione. Supponiamo per assurdo che g(x) non divida xn − 1. Allora
xn − 1 = g(x)q(x) + r(x) con r(x) non nullo e di grado minore di g(x). Poichè
g(x)q(x) ∈ C e r(x) = −g(x)q(x) (mod(xn − 1)), segue r(x) ∈ C ma ciò è assurdo
perchè g(x) è di grado minimo in C.
Teorema 5.2.4. Sia g(x) un polinomio monico divisore di xn − 1. Allora g(x)
genera il codice ciclico C = {f (x)g(x), f (x) ∈ Rn [x]}.
Dimostrazione. Sia C = {f (x)g(x), f (x) ∈ Rn [x]}. Basta provare che g(x)
è il polinomio di grado minimo appartenente a C. Sia g1 (x) ∈ C un polinomio
monico di grado minimo, sia cioè un generatore di C. Per il teorema precedente
g1 (x) è un divisore di xn − 1. Poichè g1 (x) ∈ C si ha g1 (x) = f (x)g(x) ∈ Rn [x] e
in Fq [x] diventa g1 (x) = f (x)g(x) + p(x)(xn − 1). Poichè g(x) divide xn − 1, dalla
relazione precedente segue che g(x) divide g1 (x). D’altra parte g1 (x) divide g(x)
essendo g1 (x) il generatore di C. Allora g(x) = g1 (x) perchè i due polinomi sono
monici.
Teorema 5.2.5. Sia C un codice ciclico di lunghezza n generato da g(x) di
grado n − k. Allora ogni parola c(x) ∈ C si può esprimere in modo unico nella
forma c(x) = f (x)g(x), con f (x) ∈ Rn [x], gr(f (x)) ≤ k − 1.
Dimostrazione. Per la definizione di codice ciclico, ogni parola di C è del
tipo c(x) = f (x)g(x). Distinguiamo due casi.
1◦ caso. Sia gr(f (x)) ≤ k − 1. Occorre solo provare l’unicità della rappresentazione. Supponiamo c(x) = f (x)g(x) = f1 (x)g(x), si ha [f (x) − f1 (x)]g(x) = 0 e
quindi necessariamente f (x) = f1 (x).
2◦ caso. Sia gr(f (x)) ≥ k. Allora gr(c(x)) ≥ k + (n − k) = n e si ha c(x) =
f (x)g(x) = q(x)(xn − 1) + r(x), con gr(r(x)) ≤ n − 1 oppure gr(r(x)) = 0. Poichè
g(x) divide xn − 1 si ha che g(x) è un divisore di r(x) ed esiste un unico polinomio
f1 (x) tale che r(x) = f1 (x)g(x) con gr(f1 (x)) ≤ k − 1. Si ha quindi c(x) =
f (x)g(x) = q(x)(xn − 1) + f1 (x)g(x), che in Rn [x] diventa c(x) = f1 (x)g(x).
Ricordando le proprietà degli ideali e tenendo presente il teorema 5.2.3, si ha
che il numero degli (n, k)-codici ciclici su Fq è uguale al numero dei polinomi di
Fq [x] che dividono xn − 1, a meno di una costante moltiplicativa non nulla.
Se i polinomi fattori irriducibili di xn −1 sono h, ossia xn −1 = f1 (x)f2 (x) · · · fh (x),
allora i codici ciclici di lunghezza n sono 2h (includendo anche i banali) e si ottengono scegliendo come polinomio generatore uno qualsiasi dei 2h fattori di xn − 1.
Poichè i codici banali sono due, quello contenente la sola parola nulla e Rn [x], si
ha che i codici ciclici non banali sono 2h − 2.
Quindi dopo aver scomposto xn − 1 in fattori irriducibili, è facile costruire tutti
i codici ciclici di lunghezza n.
2. POLINOMIO GENERATORE E MATRICE GENERATRICE
66
Nel seguito consideriamo codici ciclici di lunghezza n su Fq = GF (q) di
caratteristica p, q = pt , con n e q primi fra loro, cioè M CD(n, q) = 1.
Questo perchè si vuole che i fattori irriducibili in cui si scompone xn − 1 siano distinti. Se fosse M CD(n, q) = pr 6= 1, si avrebbe n = apr con r intero e
r
M CD(a, q) = 1 e sarebbe xn − 1 = (xa − 1)p . Sotto l’ipotesi M CD(n, q) = 1 i
fattori irriducibili nei quali si scompone xn − 1 sono tutti distinti.
Esempio 5.2.6. Determinare i codici ciclici binari di lunghezza 3.
Fissato x3 + 1, è R3 [x] = F2 [x]/(x3 + 1). Poichè x3 + 1 = (x + 1)(x2 + x + 1), oltre
ai codici banali ci sono 2h − 2 = 22 − 2 = 2 codici ciclici binari di lunghezza 3.
• Se g(x) = (1 + x) il codice C da esso generato è
C = {0; 1 + x; 1 + x2 ; x + x2 }
perchè gli elementi di C sono i prodotti di g(x) per i polinomi di R3 [x] di
grado minore o uguale a 1, ossia g(x) per i polinomi 0; 1; x; 1 + x.
• Se consideriamo come polinomio generatore g(x) = 1 + x + x2 , si ottiene
il codice
C1 = {0; 1 + x + x2 }
I codici C e C1 , come terne (c0 c1 c2 ) di elementi di GF (2), sono rappresentati da:
C = {(0 0 0), (1 1 0), (1 0 1), (0 1 1)}
e
C1 = {( 0 0 0), (1 1 1)}
Esempio 5.2.7. Determinare i codici ciclici ternari di lunghezza 4.
Il polinomio x4 − 1 ∈ F3 [x] ha la seguente scomposizione in fattori irriducibili:
x4 − 1 = (x − 1)(x + 1)(x2 + 1)
e quindi i polinomi a coefficienti in F3 che dividono x4 − 1, sono
1; x − 1; x + 1; x2 + 1; (x − 1)(x + 1); (x − 1)(x2 + 1); (x + 1)(x2 + 1); x4 − 1.
Esistono dunque otto codici ciclici di lunghezza 4 su F3 (compresi i due banali)
generati dagli otto polinomi soprascritti. D’altra parte 8 = 23 essendo tre i fattori
irriducibili in cui si scompone x4 − 1.
Esempio 5.2.8. Determinare tutti i possibili codici ciclici binari di lunghezza
7.
Questi codici sono sottospazi di F27 . Consideriamo f (x) = x7 − 1. In F2 il
polinomio f (x) si fattorizza in fattori irriducibili nel seguente modo:
x7 − 1 = (x + 1)(x3 + x2 + 1)(x3 + x + 1)
perciò i divisori monici di f (x) sono tutti e soli i seguenti:
g1 (x) = 1; g2 (x) = x + 1; g3 (x) = x3 + x2 + 1; g4 (x) = x3 + x + 1;
2. POLINOMIO GENERATORE E MATRICE GENERATRICE
67
g5 (x) = (x + 1)(x3 + x2 + 1); g6 (x) = (x + 1)(x3 + x + 1);
g7 (x) = (x3 + x2 + 1)(x3 + x + 1); g8 (x) = f (x).
Ne segue che F27 contiene esattamente otto codici ciclici (compresi i banali).
Ad esempio, g6 (x) genera il codice ciclico
C = {0000000; 1011100; 0101110; 0010111; 1001011; 1100101; 1110010; 0111001}
Analogamente g7 (x) genera il codice:
C = {0000000; 1111111}.
Esempio 5.2.9. Costruire un (15, 9)-codice ciclico binario.
Occorre trovare un polinomio monico divisore di x15 − 1 e di grado n − k =
15 − 9 = 6. Poichè g(x) = x6 + x5 + x4 + x3 + 1 = (1 + x + x2 )(1 + x + x4 ) soddisfa
queste condizioni, esso genera un (15, 9)-codice ciclico.
Quale aiuto per la costruzione dei codici ciclici binari, riportiamo la seguente
tavola di fattorizzazione di xn − 1 su GF (2) per n ≤ 25.
2. POLINOMIO GENERATORE E MATRICE GENERATRICE
68
Tavola della Fattorizzazione di xn − 1 su GF (2) per n ≤ 25.
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Fattorizzazione
1+x
(1 + x)2
(1 + x)(1 + x + x2 )
(1 + x)4
(1 + x)(1 + x + x2 + x3 + x4 )
(1 + x)2 (1 + x + x2 )2
(1 + x)(1 + x + x3 )(1 + x2 + x3 )
(1 + x)8
(1 + x)(1 + x + x2 )(1 + x3 + x6 )
(1 + x)2 (1 + x + x2 + x3 + x4 )2
(1 + x)(1 + x + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 )
(1 + x)4 (1 + x + x2 )4
(1 + x)(1 + x + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 )
(1 + x)2 (1 + x + x3 )(1 + x2 + x3 )2
(1 + x)(1 + x + x2 )(1 + x + x2 + x3 + x4 )(1 + x + x4 )(1 + x3 + x4 )
(1 + x)16
(1 + x)(1 + x + x2 + x4 + x6 + x7 + x8 )(1 + x3 + x4 + x5 + x8 )
(1 + x)2 (1 + x + x2 )2 (1 + x3 + x6 )2
(1 + x)(1 + x + x2 + x3 + x4 + · · · + x16 + x17 + x18 )
(1 + x)4 (1 + x + x2 + x3 + x4 )4
(1 + x)(1 + x + x2 )(1 + x2 + x3 )(1 + x + x3 )(1 + x2 + x4 + x5 + x6 )(1 + x+
+x2 + x4 + x6 )
(1 + x)2 (1 + x + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 )2
(1 + x)(1 + x + x5 + x6 + x7 + x9 + x11 )(1 + x2 + x4 + x5 + x6 + x10 + x11 )
(1 + x)8 (1 + x + x2 )8
(1 + x)(1 + x + x2 + x3 + x4 )(1 + x5 + x10 + x15 + x20 )
Matrice Generatrice
Un codice ciclico è lineare e pertanto ad esso si può associare una matrice
generatrice. Illustriamo due metodi per costruirla.
Primo metodo - Come mostra il prossimo teorema, la forma naturale per
la matrice generatrice di un codice ciclico è quella detta 00 a scala 00 ossia ottenuta
considerando k scorrimenti ciclici del vettore corrispondente ai coefficienti del polinomio generatore. In particolare, la sottomatrice quadrata ottenuta considerando
le prime k colonne è triangolare superiore e ha determinante non nullo. Pertanto,
le prime k posizioni sono posti di informazione e bastano a ricostruire, in assenza
2. POLINOMIO GENERATORE E MATRICE GENERATRICE
69
di errori, la parola originariamente trasmessa. Questa forma ciclica non risulta
quasi mai standard.
Teorema 5.2.10. Sia C un codice ciclico di lunghezza n generato dal polinomio
monico g(x) = g0 + g1 x + · · · + gn−k−1 xn−k−1 + xn−k . Allora una sua matrice
generatrice è


 
g(x)
g0 g1 · · · · · · gn−k−1
1
0
···
0
 xg(x)   0 g0 · · · · · ·
···
gn−k−1 1
···
0 
= . .
G=
.
.
.
.
.
.
.
.. 

  .. ..
..
..
..
..
..
..
..
. 
xk−1 g(x)
0
0
···
g0
···
···
· · · gn−k−1 1
Dimostrazione. G ha rango k perchè le righe sono linearmente indipendenti.
Dobbiamo provare che ogni parola di C si può esprimere come combinazione lineare
dei vettori riga di G. Dalla definizione di codice ciclico segue che un elemento
c = (c0 , c1 , . . . , cn−1 ) ∈ Fqn appartiene a C se e solo se il polinomio c(x) = c0 +
c1 x + . . . + cn−1 xn−1 ad esso associato è della forma c(x) = g(x)f (x) mod(xn − 1),
con f (x) ∈ Rn [x], gr(f (x)) ≤ k − 1, ossia se e solo se
c(x) = g(x)(f0 + f1 x + . . . + fk−1 xk−1 ) =
= f0 g(x) + f1 xg(x) + . . . + fk−1 xk−1 g(x) =
= f0 (g0 , g1 , . . . , 1, . . . , 0)+
+f1 (0, g0 , g1 , . . . , 1, . . . , 0)+
+f2 (0, 0, g0 , . . . , 1, . . . , 0)+
+......+
+fk−1 (0, 0, . . . , g0 , . . . , 1).
Segue che una qualsiasi parola c ∈ C si può esprimere come combinazione lineare
delle righe di G e pertanto G è una matrice generatrice di C.
Corollario 5.2.11. Un codice ciclico C avente come polinomio generatore un
polinomio di grado n − k, ha dimensione k e pertanto è un (n, k)-codice.
Secondo metodo - Per un codice ciclico è sempre possibile costruire una matrice generatrice in una forma standard, detta 00 antisistematica00 , particolarmente
comoda in fase di implementazione di algoritmi di decodifica perchè una copia
della parola originale si trova nelle ultime k posizioni trasmesse.
Teorema 5.2.12. Sia C un codice ciclico di lunghezza n generato dal polinomio
g(x) con gr(g(x)) = n − k. Per C è sempre possibile determinare una matrice
generatrice della forma G = (A|Ik ).
2. POLINOMIO GENERATORE E MATRICE GENERATRICE
70
Dimostrazione.
• Dividiamo i monomi xi per g(x), con n − k ≤ i ≤ n − 1, si ottiene
xi = qi (x)g(x) + ri (x)
dove i polinomi ri (x) hanno grado minore di n − k oppure sono nulli.
• Consideriamo una matrice avente come righe i coefficienti delle parole
pi (x) = qi (x)g(x) = −ri (x)+xi ordinate per i = n − k, n − k +1, . . . , n − 1,
inoltre ordiniamo ogni polinomio in senso crescente. Se
ri (x) = r0,i + r1,i x + · · · + rn−k−1,i xn−k−1
si ha
pi (x) = −ri (x) + xi = −r0,i − r1,i x − · · · − rn−k−1,i xn−k−1 + xi ∈ C
• La matrice cercata è la matrice di tipo k × n

−r0,n−k
−r1,n−k · · · −rn−k−1,n−k
 −r0,n−k+1 −r1,n−k+1 · · · −rn−k−1,n−k+1
G=
..
..
..
..

.
.
.
.
−r0,n−1
−r1,n−1
···
−rn−k−1,n−1

0 ··· 0
1 ··· 0 
.. .. .. 
. . . 
0 0 ··· 1
1
0
..
.
Ogni riga di G è una parola del codice C generato da g(x), inoltre G ha rango k e
quindi le righe sono linearmente indipendenti. G è dunque una matrice generatrice
di C ed è del tipo G = (A | Ik ) in cui le righe di A corrispondono a −ri (x), n − k ≤
i ≤ n − 1.
Esempio 5.2.13. Sia C un codice ciclico binario di lunghezza 7 generato dal
polinomio g(x) = 1 + x + x3 . Trovare la matrice generatrice di C applicando sia il
primo metodo che il secondo metodo.
Soluzione - Poichè gr(g(x)) = n − k, risulta 3 = 7 − 4 e pertanto C è un
(7, 4)-codice.
Primo metodo
 


g(x)
1 1 0 1 0 0 0
 xg(x)   0 1 1 0 1 0 0 

 
G=
 x2 g(x)  =  0 0 1 1 0 1 0 
x3 g(x)
0 0 0 1 1 0 1
Secondo metodo
Poichè gr(g(x)) = 3, dividiamo per g(x) i monomi x3 , x4 , x5 , x6 . Si ottiene
x3
x4
x5
x6
=
=
=
=
(x3 + x + 1) + (x + 1)
x(x3 + x + 1) + (x2 + x)
(x2 + 1)(x3 + x + 1) + (x2 + x + 1)
(x3 + x + 1)(x3 + x + 1) + (x2 + 1)
3. SCHEMI DI CODIFICA
71
Considerando i polinomi resto r3 = 1+x, r4 = x+x2 , r5 = 1+x+x2 , r6 = 1+x2 ,
con il secondo metodo, si ottiene la matrice:


−1 −1
0 1 0 0 0
 0 −1 −1 0 1 0 0 

Ḡ = 
 −1 −1 −1 0 0 1 0 
−1
0 −1 0 0 0 1
3. Schemi di codifica
Sia C un (n, k)-codice ciclico generato da g(x) di grado n − k.
Primo metodo di codifica
Al messaggio m = (m0 , m1 , . . . , mk−1 ) associamo il polinomio m(x) = m0 +
m1 x + . . . + mk−1 xk−1 . Per 5.2.5 il messaggio m(x) può essere codificato nella
parola c(x) = m(x)g(x).
Secondo metodo di codifica
Per questo secondo metodo, illustreremo due modi di codifica: il primo utilizza
la matrice generatrice standard mentre il secondo opera solo con polinomi ossia
non occorre scrivere la matrice generatrice. In entrambi i casi i posti di
informazione sono gli ultimi k posti ed è importante notare che in questi posti
ritroviamo inalterati i k simboli di informazione del messaggio da codificare. Questo fatto assicura che per l’operazione di codifica è sufficiente un algoritmo che
determini le componenti dei soli n − k posti di controllo.
1◦ modo - Sia m = (m0 , m1 , . . . , mk−1 ) il messaggio da codificare.
Sia G = (A|Ik ) la matrice generatrice standard di tipo k × n del (n, k)-codice
C ottenuta a partire dal polinomio generatore g(x). Una matrice di questo tipo
si può sempre costruire come illustrato nel paragrafo 2 di questo capitolo (vedi
teorema 5.2.12).
• Si codifica il messaggio m come c = mG.
Poichè G è standard, si ha c = (c0 , . . . , cn−k−1 , m0 , . . . mk−1 ) e dunque i simboli
di informazione m0 , m1 , . . . mk−1 rimangono inalterati e occupano le ultime k
posizioni mentre i simboli di controllo sono i primi n − k.
2◦ modo - Sia m = (m0 , m1 , . . . , mk−1 ) il messaggio da codificare e sia m(x) =
m0 + m1 x + · · · + mk−1 xk−1 il polinomio ad esso associato. Dividiamo il polinomio
xn−k m(x) per il polinomio generatore g(x); si ottiene xn−k m(x) = q(x)g(x) + r(x)
da cui c(x) = q(x)g(x) = −r(x) + xn−k m(x).Consideriamo c(x) ordinato secondo
potenze crescenti,
c(x) = −r0 − r1 x − r2 x2 − . . . − rn−k−1 xn−k−1 + mn−k xn−k + mn−1 xn−1 .
3. SCHEMI DI CODIFICA
72
• Il messaggio m viene codificato nella parola
c = (−r0 , −r1 , . . . , −rn−k−1 , mn−k , . . . , mn−1 ).
che ha i k simboli di informazione m0 , m1 , . . . mk−1 negli ultimi k posti e gli n − k
simboli di controllo, che sono i coefficienti di −r(x), nelle prime n − k posizioni.
Esempio 5.3.1. Sia C un codice ciclico binario di lunghezza 7 generato da
g(x) = 1 + x + x3 . Costruiamo la matrice generatrice standard come descritto nel
teorema 5.2.12. Con l’algoritmo euclideo determiniamo:
x3
x4
x5
x6
=
=
=
=
Si ottiene così la seguente

1
 0
G = (A|Ik ) = 
 1
1
1 · (x3 + x + 1) + (1 + x)
x · (x3 + x + 1) + (x + x2 )
(x2 + 1) · (x3 + x + 1) + (1 + x + x2 )
(x3 + x + 1) · (x3 + x + 1) + (1 + x2 )
matrice generatrice (vedi anche esempio 5.2.13):



1 1 0
1 0 1 0 0 0
 0 1 1 
1 1 0 1 0 0 


;
A=

 1 1 1 
1 1 0 0 1 0
1 0 1
0 1 0 0 0 1
Le righe di A corrispondono ai vettori dei coefficienti dei polinomi resto 1 +
x; x + x2 ; 1 + x + x2 ; 1 + x2 .
Sia dato il messaggio m = (1110) e codifichiamo utilizzando il secondo schema.
• Codifica con il secondo schema, 1◦ modo.
Per codificare m utilizziamo la matrice standard G. Il messaggio viene
codificato in c = mG = (0101110).
• Codifica con il secondo schema, 2◦ modo.
Ad m si associa il polinomio m(x) = 1 + x + x2 . Si considera il polinomio
xn−k m(x) e si divide per g(x); nel nostro caso si ottiene x3 (1 + x + x2 ) =
(x + x2 )(1 + x + x3 ) + x, e pertanto la parola associata ad m(x) è c(x) =
xn−k m(x)−r(x) = x3 (1+x+x2 )−x = x+x3 +x4 +x5 , ossia c = (0101110).
Algoritmo di Codifica
Descriviamo un algoritmo di codifica per un (n, k)-codice ciclico basato su quanto
esposto nel 2◦ modo del secondo metodo (vedi [3] pag. 114).
Siano dati
• Un (n, k)-codice ciclico C con polinomio generatore g(x) = g0 + g1 x + · · · +
gn−k−1 xn−k−1 + xn−k .
• Un messaggio m = (m0 m1 · · · mk−1 ).
3. SCHEMI DI CODIFICA
73
Determinare un vettore c = (c0 c1 . . . cn−k−1 ) di simboli di controllo tale che m sia
codificato in (c0 c1 . . . cn−k−1 m0 m1 . . . mk−1 ) ∈ C.
Posto g = (g0 g1 . . . gn−k−1 ) l’algoritmo è il seguente.
(1) Si pone c0j = 0 per 0 ≤ j ≤ n − k − 1.
(2) Per ogni i, 1 ≤ i ≤ k, procediamo come segue:
(i−1)
(i−1)
1◦ caso : mk−i = cn−k−1 . Allora si pone cij = cj−1 per n − k − 1 ≤ j ≤ 1
e ci0 = 0.
(i−1)
(i−1)
2◦ caso : mk−i 6= cn−k−1 . Allora si pone cij = cj−1 + gj per n − k − 1 ≤
j ≤ 1 e ci0 = g0 .
(3) Il vettore cercato è il vettore ottenuto per i = k.
Il grande vantaggio di questo algoritmo è che non si richiede di memorizzare
tutta la matrice generatrice G = (A|Ik ) e nemmeno di calcolare a priori i polinomi
ri (x).
Esempio 5.3.2. Consideriamo il (7, 4)-codice ciclico binario C generato da
g(x) = 1 + x + x3 (vedi esempio 5.3.1). Sia m = (m0 m1 m2 m3 ) = (1 0 1 1)
il messaggio da trasmettere. Determinare un vettore c = (c0 c1 c2 ) di simboli di
controllo tale che p = (c0 c1 c2 m0 m1 m2 m3 ) ∈ C.
Soluzione - Consideriamo g = (g0 g1 g2 ) = (1 1 0) e calcoliamo
i
0
1
2
3
4
Primo passo i = 1:
ci0 ci1 ci2
0 0 0
1 1 0
1 0 1
1 0 0
1 0 0
m4−i
m3
m2
m1
m0
=1
=1
=0
=1
(c00 c01 c02 ) = (0 0 0) e m3 = 1 6= c02 = 0 allora
c12 = c01 + g2 = 0 + 0 = 0
c11 = c00 + g1 = 0 + 1 = 1
c10 = g0 = 1
Secondo passo i = 2:
(c10 c11 c12 ) = (1 1 0) e m2 = 1 6= c12 = 0 allora
c22 = c11 + g2 = 1 + 0 = 1
c21 = c10 + g1 = 1 + 1 = 0
c20 = g0 = 1
Terzo passo i = 3:
(c20 c21 c22 ) = (1 0 1) e m1 = 0 6= c22 = 1 allora
3. SCHEMI DI CODIFICA
74
c32 = c21 + g2 = 0 + 0 = 0
c31 = c20 + g1 = 1 + 1 = 0
c30 = g0 = 1
Quarto passo i = 4:
(c30 c31 c32 ) = (1 0 0) e m0 = 1 6= c32 = 0 allora
c42 = c31 + g2 = 0 + 0 = 0
c41 = c30 + g1 = 1 + 1 = 0
c40 = g0 = 1
Il vettore cercato è (1 0 0) e pertanto il messaggio viene codificato in
p = (1 0 0 1 0 1 1) ∈ C.
Esempio 5.3.3. Sia g(x) = 1 + x4 + x6 + x7 + x8 il polinomio generatore di un
(15, 7)-codice ciclico binario C. Per codificare il messaggio
m = (m0 m1 m2 m3 m4 m5 m6 ) = (1 0 1 1 0 1 1)
consideriamo g = (g0 g1 g2 g3 g4 g5 g6 g7 ) = (1 0 0 0 1 0 1 1) e calcoliamo
i
0
1
2
3
4
5
6
7
ci0 ci1 ci2 ci3 ci4 ci5 ci6 ci7
0 0 0 0 0 0 0 0
1 0 0 0 1 0 1 1
0 1 0 0 0 1 0 1
1 0 1 0 1 0 0 1
0 1 0 1 0 1 0 0
1 0 1 0 0 0 0 1
1 1 0 1 1 0 1 1
0 1 1 0 1 1 0 1
m7−i
1 = m6
1 = m5
0 = m4
1 = m3
1 = m2
0 = m1
1 = m0
Il vettore cercato è (0 1 1 0 1 1 0 1) e pertanto il messaggio m = (1 0 1 1 0 1 1) è
codificato in p = (0 1 1 0 1 1 0 1 1 0 1 1 0 1 1) ∈ C.
Come si è visto, per la codifica di un codice ciclico è necessario moltiplicare
e/o dividere polinomi a coefficienti in GF (q). Per fare questo vengono in aiuto
degli apparecchi elettronici chiamati registri a scorrimento lineare ( linear shift
register ). Per la loro descrizione si rinvia a [1] pag. 206 − 215.
4. POLINOMIO DI CONTROLLO E MATRICE DI CONTROLLO
75
4. Polinomio di controllo e matrice di controllo
In un codice ciclico C, oltre al polinomio generatore g(x) c’è un altro polinomio
di Rn [x] che individua univocamente il codice. Questo polinomio gioca un ruolo
analogo a quello della matrice di controllo per i codici lineari.
Sia g(x) un divisore di xn − 1, ossia xn − 1 = g(x)h(x) nell’anello Fq [x] e quindi
g(x)h(x) = 0 in Rn [x]. Poichè h(x) è un divisore di xn − 1, esso genera un codice
ciclico.
Se g(x) = g0 + g1 x + . . . + gn−k−1 xn−k−1 + xn−k è di grado n − k, allora h(x)
ha grado k ed è del tipo h(x) = xk + hk−1 xk−1 + . . . + h1 x + h0 .
Teorema 5.4.1. Una parola c appartiene al codice ciclico C generato da g(x)
se e solo se c(x)h(x) = 0 in Rn [x], con g(x)h(x) = xn − 1 in Fq [x].
Dimostrazione. Se c è una parola di C, allora il polinomio c(x) associato a
c è un multiplo di g(x), cioè c(x) = p(x)g(x) da cui c(x)h(x) = p(x)g(x)h(x) =
p(x)(xn − 1) in Fq [x]. Ciò significa c(x)h(x) = 0 in Rn [x].
Viceversa, supponiamo c(x)h(x) = 0 in Rn [x]. Ciò significa che in Fq [x] è
c(x)h(x) = p(x)(xn − 1) = p(x)g(x)h(x) da cui segue c(x) = p(x)g(x) e quindi
c(x) è una parola del codice.
Definizione 5.4.2. Sia C ⊆ Fqn un codice ciclico generato da g(x). Si definisce
polinomio di controllo di C il polinomio h(x) tale che g(x)h(x) = xn − 1 in Fq [x]
ossia g(x)h(x) = 0 in Rn [x].
Se dim C = k ( ossia gr(g(x)) = n − k e gr(h(x)) = k ) allora il codice generato
da h(x) ha dimensione n − k che è la stessa dimensione del codice duale C ⊥ , ma in
generale non coincide con esso. Questo perchè l’essere c(x)h(x) = 0 in Rn [x] non
equivale all’ortogonalità dei vettori c ed h associati a c(x) ed h(x), rispettivamente.
E’ però vero che, in ogni caso, il codice generato da h(x) è equivalente a C ⊥ , come
mostra il prossimo teorema.
Teorema 5.4.3. Sia C un (n, k)-codice ciclico generato da g(x) ed avente come
polinomio di controllo
h(x) = h0 + h1 x + . . . + hk xk .
Allora la matrice di tipo (n − k) × n

hk hk−1 · · ·
 0
hk hk−1
H=
..
..
 ...
.
.
0
0
0

· · · · · · h0
0 ··· 0
··· ···
0
h0 · · · 0 
..
..
..
..
..
.. 
.
.
.
.
.
. 
· · · hk hk−1 · · · · · · h0
4. POLINOMIO DI CONTROLLO E MATRICE DI CONTROLLO
76
è una matrice di controllo per C. Inoltre C ⊥ è un codice ciclico generato dal
polinomio
h̄ = hk + hk−1 x + . . . + h0 xk .
Dimostrazione. Le righe di H sono evidentemente indipendenti. Sia G la
matrice generatrice di C individuata dall’unico polinomio generatore c(x) per cui
è c(x)h(x) = xn − 1. In c(x)h(x) sono allora nulli i coefficienti di xs , per ogni
s 6= 0, n, e ciò implica che GH t = 0, cioè H è una matrice di controllo di C.
Osserviamo ora che risulta
h̄ = xk h(x−1 ),
c̄(x) = cn−k + cn−k−1 x + cn−k−2 x2 + · · · + c1 xn−k−1 + c0 xn−k = xn−k c(x−1 ),
1 − xn = xn (x−n − 1) = xn c(x−1 )h(x−1 ) = xk h(x−1 )xn−k c(x−1 ) = h̄(x)c̄(x),
cioè h̄(x) divide xn − 1. Dalla 5.3.1 segue allora che C ⊥ è ciclico con polinomio
generatore h̄(x) e il teorema è completamente dimostrato.
Definizione 5.4.4. Sia h(x) = h0 + h1 x + . . . + hk xk polinomio di controllo
del (n, k)-codice ciclico C. Si chiama polinomio reciproco di h(x) il polinomio
h̄ = hk + hk−1 x + . . . + h0 xk .
Esempio 5.4.5. Sia C un codice ciclico binario di lunghezza 7 generato da
g(x) = 1 + x + x3 . Si ha:
(1) C ha dimensione 4.
7 +1
(2) Il polinomio di controllo è h(x) = xg(x)
= 1 + x + x2 + x4 ; esso genera
un codice ciclico C1 di dimensione 3.
(3) Una matrice generatrice di C (costruita con il primo metodo, teorema
5.2.10) è


1 1 0 1 0 0 0
 0 1 1 0 1 0 0 

G=
 0 0 1 1 0 1 0 
0 0 0 1 1 0 1
(4) Una matrice di controllo di

1
H= 0
0
Cè

0 1 1 1 0 0
1 0 1 1 1 0 
0 1 0 1 1 1
(5) Il polinomio reciproco di h(x) è il polinomio h̄(x) = xk h( x1 ) = x4 (1 +
1
+ x14 ) = x4 + x3 + x2 + 1.
x2
1
x
+
5. DECODIFICA
77
(6) Determiniamo una matrice generatrice di C nella forma standard antisistematica G0 = (A|Ik ), utilizzando il secondo metodo (teorema 5.2.12). Le
righe di G0 sono date dai coefficienti dei polinomi −ri (x)+xi , dove ri (x) è il
resto della divisione di xi per g(x), essendo n − k ≤ i ≤ n − 1. La prima, la
seconda, la terza, la quarta riga di G0 sono date rispettivamente dai coefficienti dei polinomi (x+1)+x3 , (x2 +x)+x4 , (x2 +x+1)+x5 , (x2 +1)+x6 .
Risulta pertanto:


1 1 0 1 0 0 0
 0 1 1 0 1 0 0 

G0 = 
 1 1 1 0 0 1 0  = (A|I4 ).
1 0 1 0 0 0 1
(7) Se la matrice generatrice di C è G0 allora la matrice di controllo è


1 0 0 1 0 1 1
H = (I3 | − At ) =  0 1 0 1 1 1 0 
0 0 1 0 1 1 1
5. Decodifica
Se il codice ciclico viene usato solo come codice rivelatore di errori, si procede
come segue.
Se si riceve un vettore y(x), il decodificatore deve stabilire se è oppure no un
elemento del codice. Per fare ciò si può usare il polinomio di controllo e vedere
n −1
, la relazione y(x)h(x) = 0
se y(x)h(x) = 0 in Rn [x]. Inoltre, poichè h(x) = xg(x)
(xn − 1) che significa y(x)
≡ 0 mod (xn − 1). Pertanto se
equivale a 0 = y(x)
g(x)
g(x)
y(x)h(x) = 0, dividendo y(x) per g(x) si ottiene come resto 0. Allora, per vedere
se ci sono errori, il decodificatore può dividere il vettore ricevuto per g(x), invece
di moltiplicarlo per h(x).
Gli schemi di decodifica veri e propri dipendono dal singolo tipo di codice. In
ogni caso anche la decodifica di un codice ciclico può essere implementata in modo
conciso in termini di polinomi.
Fissiamo un (n, k)-codice ciclico C ⊆ Fqn con polinomio generatore g(x). Per
quanto visto precedentemente, è sempre possibile rappresentare l’operazione di
codifica mediante una matrice generatrice G della forma G = (A|Ik ) e pertanto è
la matrice di controllo di C è del tipo
H = (In−k | − At ).
Considerando i polinomi resto ri (x) si vede immediatamente che
5. DECODIFICA
H=
1 0
0
0 1
0
0 0
1
r0 ( x)
r1 ( x)
78
rk −1 ( x)
Teorema 5.5.1. Sia C ⊆ Fqn un (n, k)-codice ciclico generato da g(x) e sia H
una sua matrice di controllo del tipo H = (In−k | − At ). Sia v ∈ Fqn un vettore e
s la sua sindrome rispetto ad H. Siano v(x) e s(x) le rispettive rappresentazioni
polinomiali. Allora s(x) è il resto della divisione di v(x) per g(x).
Dimostrazione. Si rinvia a [3] pag. 116.
In altre parole, il teorema assicura che la sindrome di una sequenza può essere
determinata semplicemente eseguendo una divisione fra polinomi mediante l’algoritmo euclideo. Questo può risultare molto più agevole da implementare che non
l’usuale prodotto fra matrice e vettore.
Esempio 5.5.2. Sia C il (7, 4)-codice ciclico binario generato dal polinomio
g(x) = 1 + x + x3 . Una sua matrice generatrice del tipo G = (A|I4 ) è (vedi esempio
5.2.13)


1 1 0 1 0 0 0
 0 1 1 0 1 0 0 

G=
 1 1 1 0 0 1 0 
1 0 1 0 0 0 1
e pertanto una matrice di controllo è data da


1 0 0 1 0 1 1
H =  0 1 0 1 1 1 0  = (I3 | − At )
0 0 1 0 1 1 1
Supponiamo di aver ricevuto la sequenza r = (1 0 1 1 0 1 1). La sindrome di r è
s = rH t = (0 0 1). Troviamola ora in altro modo: consideriamo la rappresentazione
polinomiale di r : r(x) = 1 + x2 + x3 + x5 + x6 . Dividendo r(x) per g(x) si ottiene
: r(x) = (x3 + x2 + x + 1)g(x) + x2 . Come previsto, il polinomio associato alla
sindrome di r è s(x) = x2 e pertanto la sindrome è (0 0 1) come già trovato nel
modo 00 classico00 .
Per maggiori approfondimenti si rinvia a [3] pag. 117 − 123.
6. CODICI BCH
79
6. Codici BCH
I codici BCH, dalle iniziali dei loro inventori R. C. Bose, D. K. Ray-Chaudhuri,
A. Hocquenghem, sono codici ciclici pluri-correttori (1959 − 60).
Scegliendo 00 opportunamente00 il polinomio generatore, si può fare in modo che,
entro certi limiti, la distanza minima del codice sia maggiore di un intero prefissato.
Fissato un campo Fq , si vuole costruire un codice su Fq che abbia distanza
minima d ≥ δ, dove δ è un intero arbitrario. L’idea base è quella di lavorare in
un’estensione algebrica di Fq .
Definizione 5.6.1. Un codice ciclico di lunghezza n su Fq è detto codice
BCH con distanza garantita δ se è generato da un polinomio g(x) che è il
minimo comune multiplo dei polinomi minimi (su Fq ) degli elementi
αl , αl+1 , . . . , αl+δ−2
con α radice primitiva n-esima dell’unità e l ≥ 0 intero fissato.
Poichè l’elemento α è una radice n-esima dell’unità, anche ogni sua potenza αj
è radice n-esima dell’unità. Pertanto
x − αj
divide sempre xn − 1; perciò il polinomio g(x) della definizione 5.6.1 deve, anche
esso, dividere xn − 1 e il codice generato ha lunghezza n e dimensione n−gr(g(x)).
Dalla definizione segue che il polinomio g(x) che genera il codice BCH è il
polinomio di grado minimo su GF (q) avente αl , αl+1 , . . . , αl+δ−2 come radici.
Definizione 5.6.2. Sia C un codice BCH di lunghezza n su Fq , con distanza
garantita δ. C è detto BCH in senso stretto se nella definizione 5.6.1 si ha l = 1
Ossia C è generato da g(x) tale che :
(1) g(x) | xn − 1 ,
(2) α radice primitiva n-sima dell’unità,
(3) g(x) = m.c.m.(f1 (x), f2 (x), . . . , fδ−1 (x)) con fi (x) polinomio minimo di
αi , 1 ≤ i ≤ δ − 1.
In generale, con il simbolo BCHq (n, δ) si indica un codice BCH in senso stretto
q-ario di lunghezza n e distanza garantita δ.
Il numero δ non è necessariamente la distanza minima del codice BCH, ma
ne dà una limitazione inferiore, come afferma il seguente teorema di cui, per la
dimostrazione, si rinvia a [3] pag. 159.
Teorema 5.6.3 (Limitazione BCH). Sia C un codice BCH sopra Fq di distanza
garantita δ. Allora C ha distanza minima d ≥ δ.
6. CODICI BCH
80
Ricordiamo che per determinare una radice primitiva n-esima dell’unità, in
generale, si deve trovare l’estensione algebrica Fqm ⊇ Fq definita dal più piccolo
intero m tale che n divida q m − 1. Determinato m, sia q m − 1 = kn e sia ξ un
m
elemento primitivo di Fqm . Poichè ξ q −1 = ξ nk = 1, si ha che α = ξ k è una radice
primitiva n-esima dell’unità.
Per costruire un codice BCH si deve lavorare contemporaneamente su due
campi : il campo Fq cui appartengono le componenti delle parole del codice e su
cui è definito lo spazio vettoriale C ⊆ Fqn , e il campo Fqm in cui giacciono le radici
dell’unità utilizzate nella costruzione e detto campo di calcolo del codice.
Esempio 5.6.4. Costruire il codice BCH2 (15, 7).
La lunghezza del codice è 15, pertanto serve una radice 15-esima dell’unità:
indichiamo con α questa radice. Poichè 4 è il più piccolo intero positivo tale che
15 divide 24 − 1, scegliamo come α un elemento primitivo di F24 . Poichè 16 = 24 ,
possiamo scegliere una radice del seguente polinomio di grado 4, irriducibile in
GF (2):
x4 + x + 1
Per avere δ = 7, occorre considerare un polinomio g(x) generatore del codice BCH
che abbia come radici (1 + 7 − 2) sei potenze consecutive di α.
(1) In GF (24 ) gli elementi α, α2 , α3 , α4 , α5 , α6 sono radici 15-esime dell’unità.
Le radici α, α2 , α4 hanno come polinomio minimo irriducibile su GF (2) il
polinomio p(x) = 1 + x + x4 ; α5 ha come polinomio minimo irriducibile
su GF (2) il polinomio q(x) = 1 + x + x2 ; α6 ha come polinomio minimo
irriducibile su GF (2) il polinomio r(x) = 1 + x + x2 + x3 + x4 . Il codice
BCH cercato è allora generato dal minimo comune multiplo dei polinomi
p(x), q(x), r(x) ossia è generato dal polinomio g(x) = 1 + x + x2 + x4 +
x5 + x8 + x10 . Poichè g(x) è una parola del codice di peso 7, si ha che in
questo caso d = δ. Inoltre, poichè l = 1, il codice è BCH in senso stretto.
(2) In GF (24 ) gli elementi α9 , α10 , α11 , α12 , α13 , α14 sono sei potenze consecutive di α e sono radici 15-esime dell’unità. Le radici α9 , α12 hanno come polinomio minimo irriducibile su GF (2) il polinomio p(x) = 1+x+x2 +x3 +x4 ;
α10 ha come polinomio minimo irriducibile su GF (2) il polinomio q(x) =
1 + x + x2 ; α11 , α13 , α14 hanno come polinomio minimo irriducibile su
GF (2) il polinomio r(x) = 1 + x3 + x4 . Il codice BCH cercato è allora
generato dal minimo comune multiplo dei polinomi p(x), q(x), r(x) ossia è
generato dal polinomio g(x) = 1 + x2 + x5 + x6 + x8 + x9 + x10 . Poichè g(x)
è una parola del codice di peso 7, come nel caso precedente si ha d = δ
ma il codice non è BCH in senso stretto perchè l = 9.
6. CODICI BCH
81
Per costruire un codice BCH, è di grande utilità considerare le classi ciclotomiche del campo di calcolo del codice; infatti con queste si determinano immediatamente i polinomi minimi con cui ottenere il polinomio generatore del
codice.
Esempio 5.6.5. Costruire un codice BCH binario di lunghezza 15.
Sia α un elemento primitivo di GF (24 ), ne segue che α è una radice primitiva
15-esima dell’unità. Le classi ciclotomiche modulo 15 su GF (2) sono:
C0 = {0}, C1 = {1, 2, 4, 8}, C3 = {3, 6, 9, 12}, C5 = {5, 10}, C7 = {7, 11, 13, 14}.
Se mi (x) è il polinomio minimo di αi , ossia mi (αi ) = 0, posto mi (x) = mαi (x),
otteniamo:
m0 (x) =
m1 (x) =
m3 (x) =
m5 (x) =
m7 (x) =
(x − 1)
(x − α)(x − α2 )(x − α4 )(x − α8 )
(x − α3 )(x − α6 )(x − α9 )(x − α12 )
(x − α5 )(x − α10 )
(x − α7 )(x − α11 )(x − α13 )(x − α14 ) .
Ovviamente ogni mi (x) è divisore di x15 − 1 e perciò se g(x) è il prodotto di un
certo numero di polinomi mi (x), allora g(x) è un divisore di x15 − 1 e quindi genera
un codice ciclico. Se g(x) ha δ − 1 potenze consecutive di α come radici, allora il
codice C da esso generato ha distanza garantita δ.
Se costruiamo l’ampliamento GF (24 ) di GF (2) tramite il polinomio 1 + x + x4 ,
ossia 1 + α + α4 = 0, otteniamo
m1 (x) = (x2 + α2 x + αx + α3 )(x2 + α8 x + α4 x + α12 ) =
= x4 + (α8 + α4 + α2 + α)x3 + (α12 + α10 + α9 + α6 + α5 + α3 )x2 +
+(α14 + α13 + α11 + α7 )x + 1
= x4 + x + 1 ;
analogamente
m3 (x) = x4 + x3 + x2 + x + 1
m5 (x) = x2 + x + 1
m7 (x) = x4 + x3 + 1 .
• Se fissiamo g(x) = m3 (x)m5 (x)m7 (x), le potenze α9 , α10 , α11 , α12 , α13 , α14
sono radici di g(x) potenze consecutive e perciò g(x) genera un codice
BCH con distanza garantita δ = 7 perchè 9 + δ − 2 = 14. In questo caso
si tratta di un (15, 5)-codice perchè g(x) ha grado 10.
• Se fissiamo g(x) = m1 (x)m3 (x)m5 (x), le potenze α, α2 , α3 , α4 , α5 , α6 sono
radici di g(x) potenze consecutive e perciò otteniamo ancora un (15, 5)codice con distanza garantita δ = 7 perchè 1 + δ − 2 = 6.
6. CODICI BCH
82
• Se fissiamo g(x) = m1 (x)m3 (x) otteniamo un (15, 7)-codice ciclico, avendo
g(x) grado 8. Inoltre, essendo α, α2 , α3 , α4 radici di g(x) potenze consecutive, C è un BCH codice con distanza garantita δ = 5.
Si ha g(x) = m1 (x)m3 (x) = x8 + x7 + x6 + x4 + 1 ed essendo 5 il peso di
g(x), si ha d(C) = δ = 5.
• Se fissiamo g(x) = m0 (x)m1 (x)m3 (x), otteniamo ancora un (15, 6)-codice
con distanza garantita δ = 6.
In generale, se g(x) ha come radice α e genera un codice BCH con distanza
garantita δ, il codice generato da m0 (x)g(x) ha distanza garantita δ + 1.
Esempio 5.6.6. Costruire un codice BCH ternario di lunghezza 8.
Poichè 8 | 32 − 1, sia α un elemento primitivo di GF (32 ), ossia α è una radice
primitiva ottava dell’unità. Le classi ciclotomiche modulo 8 su GF (3) sono:
C0 = {0}, C1 = {1, 3}, C2 = {2, 6}, C4 = {4}, C5 = {5, 7}.
Se denotiamo con mi (x) il polinomio minimo di αi , si ha:
m0 (x) =
m1 (x) =
m2 (x) =
m4 (x) =
m5 (x) =
(x − 1)
(x − α)(x − α3 )
(x − α2 )(x − α6 )
(x − α4 )
(x − α5 )(x − α7 ) .
Se fissiamo g(x) = m2 (x)m5 (x), otteniamo un codice C che è BCH C con distanza
garantita δ = 4, essendo α5 , α6 , α7 radici di g(x) e potenze consecutive. Inoltre
poichè g(x) ha peso esattamente 4, si ha d(C) = δ = 4. Il codice C è un (8, 4)-codice
perchè il grado di g(x) è 4.
Esempio 5.6.7. Costruire un codice BCH codice ternario di lunghezza 13.
Il minimo ordine m di un ampliamento algebrico di GF (3) tale che 3m −1 = 13k
è 3, infatti 33 − 1 = 2 · 13.
Sia α un elemento primitivo di GF (33 ), ad esempio α sia radice del polinomio
3
x + 2x2 + 1; allora β = αk = α2 è radice 13-esima primitiva dell’unità.
Le classi ciclotomiche modulo 13 su GF (3) sono:
C0 = {0}, C1 = {1, 3, 9}, C2 = {2, 5, 6}, C4 = {4, 10, 12}, C7 = {7, 8, 11}.
Se denotiamo con mi (x) il polinomio minimo di β i , si ha:
m0 (x) =
m1 (x) =
m2 (x) =
m4 (x) =
m7 (x) =
(x − 1)
(x − β)(x − β 3 )(x − β 9 ) = x3 + 2x2 + 2x + 2
(x − β 2 )(x − β 5 )(x − β 6 ) = x3 + 2x + 2
(x − β 4 )(x − β 10 )(x − β 12 ) = x3 + 2x2 + x + 2
(x − β 7 )(x − β 8 )(x − β 11 ) = x3 + x2 + 2 .
6. CODICI BCH
83
• Se fissiamo g(x) = m0 (x)m1 (x)m2 (x) = x7 + x6 + 2x5 + x4 + 2x + 2,
otteniamo un codice C che è BCH con distanza garantita δ = 5.
• Se fissiamo g(x) = m1 (x)m2 (x), otteniamo un codice C che è BCH con
distanza garantita δ = 4.
Esempio 5.6.8. Costruire un codice C = BCH2 (9, 2).
Per poterlo costruire occorre anzittutto una radice primitiva nona dell’unità su
F2 . Il campo di spezzamento di x9 − 1 è F26 perchè il più piccolo intero tale che
9|2m − 1 è m = 6. Indichiamo con ξ un generatore del gruppo moltiplicativo di F26
e sia
x6 + x4 + x3 + x + 1
il polinomio minimo di ξ in GF (2) (è irriducibile e ha grado 6 perchè determina
l’estensione F26 di F2 ). Il periodo di ξ è 26 − 1 = 63. Ne segue che α = ξ 63/9 = ξ 7 è
una radice primitiva nona dell’unità. Poichè 1 + δ − 2 = 1 + 2 − 2 = 1, per costruire
il codice BCH richiesto occorre una radice radice nona dell’unità; consideriamo
pertanto la radice α. Essa ha polinomio minimo
x6 + x3 + 1.
Il codice BCH cercato, essendo generato dal minimo comune multiplo dei polinomi
minimi, in questo caso, è generato da g(x) = (x6 + x3 + 1) e poichè gr(g(x)) =
n − k = 6, la dimensione del codice cercato è 9 − 6 = 3. Da g(x) = x6 + x3 + 1
possiamo scrivere esplicitamente una matrice generatrice per C :


1 0 0 1 0 0 1 0 0
G= 0 1 0 0 1 0 0 1 0 
0 0 1 0 0 1 0 0 1
Le otto parole di C sono date da
• il vettore nullo (peso 0);
• le tre righe della matrice G (peso 3);
• le tre combinazioni delle righe di G a due a due (peso 6);
• il vettore ottenuto sommando tutte e tre le righe di G (peso 9).
Ne segue che il codice C ha distanza minima 3, strettamente maggiore della distanza
garantita.
Una limitazione superiore per la distanza minima di un codice BCH è data dal
seguente teorema che riportiamo senza dimostrazione.
Teorema 5.6.9. Sia C un codice BCH primitivo binario di distanza garantita
δ. Allora la distanza minima d di C soddisfa
δ ≤ d ≤ 2δ − 1.
CAPITOLO 6
Codici di Hamming e codici perfetti
I codici di Hamming sono codici lineari 1-correttori perfetti e per questo particolarmente adatti a situazioni in cui è necessaria la correzione di un singolo errore.
Costituiscono una famiglia di codici molto importante perchè per essi è facile sia
la codifica che la decodifica. Scoperti dallo stesso Hamming nel 1948, l’approccio da noi seguito non è quello originale ma è basato sull’insieme dei sottospazi
1-dimensionali di uno spazio vettoriale.
Il lavoro di Hamming, dal titolo Error Detecting and Error Correcting Codes,
fu pubblicato nel 1950 sulla rivista Bell System Tech. J., vol. 29, n.2, 1950.
R.W.Hamming (1915 − 1998), matematico americano, diede importanti contributi nel campo dell’informatica e delle telecomunicazioni. Mentre lavorava sui
computer presso i laboratori della Bell telephone, dove collaborava con Shannon,
Hamming si rese conto che veniva sprecato molto tempo a causa dell’incapacità
del computer di gestire gli errori. Se veniva rivelato un singolo errore, il computer abbandonava il lavoro per iniziarne un altro, senza mai tornare al precedente.
Hamming poteva accedere ai computer solo nel fine settimana; per questo qualche volta al lunedì trovava il suo lavoro non svolto ed era costretto ad aspettare
un’intera settimana per farlo eseguire di nuovo al computer. Questo lo indusse a
studiare il problema del rilevamento di errori, ovvero a come correggerli.
1. Definizioni e Proprietà
Descriviamo i codici di Hamming tramite una loro matrice di controllo .
r
−1
Definizione 6.1.1. Sia n = qq−1
, k = n − r, r ≥ 2. Un codice C è detto codice
di Hamming di ordine r su Fq se è un (n, n − r)- codice la cui matrice di
controllo H è una matrice r × n tale che ogni colonna è linearmente indipendente
da ogni altra colonna.
84
1. DEFINIZIONI E PROPRIETÀ
85
Per la definizione data, le colonne di una matrice di controllo H di un codice di
Hamming sono tutte le r-ple di elementi di Fq a due a due linearmente indipendenti.
r −1 q r −1
Segue che, data una matrice di controllo H di un ( qq−1
, q−1 − r)-codice, tutte
le altre si possono ottenere da H tramite trasformazioni elementari su righe e
colonne e pertanto, a meno di equivalenze, i codici di Hamming sono codici lineari
individuati univocamente dai loro parametri.
Il rango della matrice di controllo H è sempre 2 perchè due qualunque colonne
c1 , c2 sono linearmente indipendenti e ne contiene tre linearmente dipendenti perchè
il sottospazio generato da c1 +c2 è, a sua volta, rappresentato in H. Per il corollario
4.5.12 ne segue che tutti i codici di Hamming hanno distanza minima d = 3
e sono pertanto 1-correttori e 2-rivelatori.
Ne segue che le sfere di centro le parole del codice e raggio 1 sono a due a due
disgiunte e, poichè ognuna di esse contiene esattamente n(q − 1) + 1 parole di
r −1
Fqn , ricordando che n = qq−1
, risulta
q n−r [1 + n(q − 1)] = q n = |Fqn |
e pertanto il codice è un codice perfetto. Vale dunque il seguente teorema.
Teorema 6.1.2. I codici di Hamming sono 1-correttori e perfetti.
Un po’ di conti. Sia n − k = r, determiniamo il numero massimo di r-ple a
due a due linearmente indipendenti che si possono costruire con q elementi. Il
numero di r-ple distinte non nulle che si ottengono con q elementi è q r − 1 ; ma
per ogni r-pla fissata ci sono (q − 2) altre r-ple linearmente dipendenti da essa e
pertanto l’insieme di tutte le r-ple si suddivide in sottoinsiemi disgiunti ognuno
con (q − 1) r-ple a due a due linearmente dipendenti. Quindi delle (q r − 1) r-ple
non nulle, esattamente (q r − 1)/(q − 1) sono a due a due linearmente indipendenti.
Ne segue che il massimo numero di r-ple a due a due linearmente indipendenti è
n = (q r − 1)/(q − 1) e pertanto k = n − r = [(q r − 1)/(q − 1)] − r.
Un metodo semplice per scrivere una matrice di controllo di un codice q-ario di
Hamming è quello di scegliere come colonne tra le r-ple non nulle possibili, quelle
che hanno il primo elemento non nullo uguale ad 1. Ovviamente ciò equivale a
scegliere una r-pla in ogni sottoinsieme di (q − 1) r-ple a due a due linearmente
indipendenti.
La decodifica dei codici q-ari di Hamming viene fatta usando lo schema di
decodifica descritto nel paragrafo 4.6 per i codici lineari 1-correttori.
Si può dimostrare che un codice q-ario di Hamming di lunghezza (q r −1)/(q −1)
è equivalente ad un codice ciclico se r e (q − 1) sono primi tra loro.
1. DEFINIZIONI E PROPRIETÀ
86
Nel teorema 6.2.3 mostreremo invece che ogni codice binario di Hamming è
equivalente ad un codice ciclico.
Osserviamo infine che una parola non nulla p del codice ha peso w(p) e presenta
lettere diverse da zero nelle posizioni i1 , i2 , . . . , iw se e solo se in H le colonne di
posto i1 , i2 , . . . , iw sono linearmente dipendenti.
Esempio 6.1.3. Sia q = 3, r = 2. Il codice di Hamming che si ottiene è un
32 −1
− 2) = (4, 2)-codice ternario. Per scrivere una matrice di controllo,
3−1
diamo la rappresentazione in base 3 dei numeri compresi fra 1 e 8.
2 −1
( 33−1
,
1
3
5
7
=
1 · 30
= 1 · 31 + 0 · 30
= 1 · 31 + 2 · 30
= 2 · 31 + 1 · 30
=
=
=
=
0
1
1
2
1
0
2
1
2
4
6
8
=
2 · 30
= 1 · 31 + 1 · 30
= 2 · 31 + 0 · 30
= 2 · 31 + 2 · 30
=
=
=
=
0
1
2
2
2
1
0
2
Si osservi che la coppia (0 2) è proporzionale alla coppia (0 1); così come (2 0) è
proporzionale a (1 0); (1 2) è proporzionale a (2 1); (2 2) è proporzionale a (1 1),
ovviamente nell’aritmetica modulo 3. Una matrice di controllo del (4, 2)-codice
ternario di Hamming è allora
0 1 1 1
H=
1 0 1 2
Esempio 6.1.4. Se q = 5 ed r = 2 si ha un (6, 4)-codice di Hamming di ordine
5 avente come matrice di controllo
0 1 1 1 1 1
H=
1 0 1 2 3 4
Supponiamo di ricevere y = (2 0 3 0 3 1). Si ha yH t = (2 3) = 2(1 4). Si deduce
che l’errore è nella sesta componente e la 00 grandezza00 di tale errore è 2 per cui la
parola trasmessa è
x = y − (0 0 0 0 0 2) = (2 0 3 0 3 4).
2. CODICI DI HAMMING BINARI
87
2. Codici di Hamming binari
Un caso particolarmente interessante di codici di Hamming è quello binario.
In questo caso la matrice di controllo H contiene tutti e soli i vettori non nulli di
F2r . In altre parole
si definisce codice binario di Hamming un (2r −1, 2r −1−r)-codice avente come
matrice di controllo una matrice H le cui colonne sono tutte le r-ple non nulle di
elementi di GF (2).
Ad esempio per r = 2 si ottiene un (3, 1)-codice; per r = 3 si ottiene un
(7, 4)-codice; per r = 4 si ottiene un (15, 11)-codice.
Esempio 6.2.1. Per avere la matrice di controllo di un (7, 4)-codice di Hamming
è sufficiente scrivere una matrice le cui colonne sono la rappresentazione in base
due dei numeri 1, 2, 3, 4, 5, 6, 7. Si ha


0 0 0 1 1 1 1
H= 0 1 1 0 0 1 1 
1 0 1 0 1 0 1
Prima di dimostrare il prossimo teorema, ricordiamo alcuni noti risultati di
algebra:
• Sia K un campo di caratteristica p e sia α un elemento non nullo di K.
Un polinomio monico m(x) a coefficienti in GF (p) di grado minimo tale
che m(α) = 0 è detto polinomio minimo di α rispetto a GF (p) e si denota
con mα (x).
• Il polinomio minimo di un elemento non nullo α di GF (q) = GF (ph ) è
Y
mα (x) =
(x − β).
β∈C(α)
• Se f (x) ∈ GF (p)[x] è tale che f (α) = 0, α ∈ GF (ph ), allora mα (x) divide
f (x).
Teorema 6.2.2. I (2r − 1, 2r − 1 − r)-codici C binari di Hamming sono codici
ciclici generati dal polinomio minimo mα (x) di un elemento primitivo a di GF (2r ).
Dimostrazione. Sia α un elemento primitivo del campo GF (2r ). Dalla definizione di codice binario di Hamming segue che una sua matrice di controllo di
lunghezza 2r − 1 si può rappresentare come
r
H = 1 α α2 · · · α2 −2
Per 4.5.7 un vettore c = (c0 , c1 , . . . , cn−1 ) è in C se e solo se cH t = 0 e, passando ai
polinomi, c(x) = c0 +c1 x+. . .+cn−1 xn−1 è in C se e solo se c0 +c1 α+. . .+cn−1 αn−1 =
3. CODICI PERFETTI
88
0, cioè se e solo se c(α) = 0. Dalle proprietà algebriche prima ricordate, segue
che mα (x) divide ogni polinomio-parola c(x) ∈ C, quindi mα (x) è il polinomio
generatore di C.
Nota 6.2.3. Il codice duale di un codice di Hamming binario è un codice
equidistante ossia è un codice in cui tutte le parole diverse da 0 hanno il medesimo
peso che è 3 (vedi [3] pag. 84 − 85).
3. Codici perfetti
Ricordiamo che la proprietà di un codice di essere perfetto dipende esclusivamente dai suoi parametri.
I parametri dei codici perfetti sopra alfabeti con un numero primo di simboli
sono stati completamente determinati, si veda [3] pag. 242.
Altri codici perfetti, oltre a quelli di Hamming, sono stati scoperti nel 1949 da
Golay. Uno è un (23, 12)-codice binario 3-correttore con distanza d = 7; l’altro è un
(11, 6)-codice ternario 2-correttore con distanza d = 5. Questi due codici di Golay,
insieme ai codici di Hamming, sono gli unici codici lineari perfetti non banali.
I codici di Golay e i codici di Golay estesi sono codici sporadici associati ai
disegni di Mathieu . Sono particolarmente interessanti anche perchè hanno una
struttura algebrica molto ricca e perciò si prestano ad essere decodificati con facilità tanto che le prime sonde interplanetarie utilizzavano codici di Golay per la
trasmissione dei dati.
Sull’esistenza di codici perfetti possiamo affermare che.
• Sono codici perfetti banali il codice C = F n , i codici contenenti una sola
parola, i codici di ripetizione binari di lunghezza dispari.
• I codici di Hamming (classe infinita di codici lineari perfetti non banali),
• Il codice lineare binario G23 e il codice lineare ternario G11 di Golay (sono
codici lineari perfetti non banali).
Nel 1973 i lavori di J.H.van Lint e A.Tietavainen provarono il seguente risultato.
Teorema 6.3.1. Se q è potenza di un primo, ogni codice q-ario perfetto non
banale ha i parametri di un codice di Hamming o di uno dei due codici di Golay.
3. CODICI PERFETTI
89
Nel caso lineare, il precedente teorema porta alla seguente caratterizzazione dei
codici perfetti non banali.
Teorema 6.3.2. Ogni codice lineare perfetto non banale è equivalente ad un
codice di Hamming o ad uno dei due codici di Golay.
Rimane aperto il problema nel caso in cui l’alfabeto non sia un campo di Galois.
In questo caso, il risultato più significativo è stato trovato nel 1982 ed è dato dal
seguente teorema.
Teorema 6.3.3. Per h ≥ 3, h 6= 6, 8, il solo codice non banale h-correttore
perfetto sopra un alfabeto qualsiasi è il (23, 12)-codice binario di Golay.
Per h = 1 il problema è lontano dall’essere risolto. E’ stato dimostrato il
seguente teorema.
Teorema 6.3.4. Non esiste un codice 1-correttore perfetto di lunghezza 7 sopra
un alfabeto di 6 simboli.
CAPITOLO 7
Codici di Goppa
I codici di Goppa sono codici lineari di cui ci limitiamo a dare la definizione.
Per una loro trattazione si rinvia a [2] pag. 427.
Il motivo per cui, prima di concludere la parte dedicata ai codici, si vogliono
citare i codici Goppa, è che nella teoria dei codici essi aprono la strada all’uso di
idee e tecniche di geometria algebrica.
Definizione 7.0.5. Sia Fq un campo finito, sia m un intero positivo e f (x)
un polinomio monico di grado t > 0 su Fqm . Sia inoltre L = {γ1 , γ2 , . . . , γn } un
insieme di n elementi distinti di Fqm tali che f (γh ) 6= 0, per h = 1, . . . , n. Il codice
di Goppa C(L, f (x))q,m è il sottoinsieme delle n-ple (c1 , c2 , . . . , cn ) di elementi di
Fq tali che
n
X
ci
≡ 0 (mod f (x)).
x − γi
i=1
90
CAPITOLO 8
Codici correttori e gruppi di permutazioni
I primi studi relativi ad applicazioni degli insiemi di permutazioni alla teoria
dei codici risalgono agli anni 1970. Solo negli ultimi anni ha preso vigore anche
lo studio di codici correttori che sono gruppi di permutazioni, si veda ad esempio
il lavoro di R.F.Bailey Error-correcting codes from permutation groups, Discrete
Mathematics 309, 4253 − 4265, 2009.
1. Gruppi come codici e distanza di Hamming
Considerato un codice le cui parole hanno lunghezza n, dire che il codice è
un gruppo significa che le parole del codice sono permutazioni dell’alfabeto A =
{1, 2, . . . , n} e pertanto significa considerare un sottogruppo del gruppo simmetrico
Sn . Ogni parola del codice può allora essere rappresentata con una stringa i cui
elementi sono, rispettivamente, le immagini degli elementi 1, 2, . . . , n considerati
nel loro ordine naturale. Ad esempio, in S9 , la stringa
123456789
rappresenta la permutazione identità, mentre la stringa
231794685
indica la seguente permutazione di S9
1 2 3 4 5 6 7 8 9
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
2 3 1 7 9 4 6 8 9
Se le parole di un codice C sono permutazioni su n elementi, risulta molto utile
interpretare la distanza di Hamming in termini di punti fissi.
Teorema 8.1.1. Siano g, h ∈ Sn , allora si ha
d(g, h) = n − |F ix(gh−1 )|
dove Fix(g) denota l’insieme dei punti fissi di g.
91
2. GRUPPI STRETTAMENTE K-TRANSITIVI
92
Dimostrazione. Moltiplicando per h−1 sia g che h si ottiene
d(g, h) = d(gh−1 , id.)
ossia la distanza di Hamming fra g ed h è il numero di posti in cui gh−1 differisce
dall’identità e questo numero è proprio n − |F ix(gh−1 )|.
Dal teorema precedente segue che la distanza minima di un insieme C di
permutazioni è uguale a
d(C) = ming,h∈C,g6=h {n − |F ix(gh−1 )|} = n − maxg,h∈C,g6=h |F ix(gh−1 )|
e pertanto se C = G è un gruppo di permutazioni si ha
d(G) = n − maxg,h∈C,g6=h |F ix(gh−1 )|.
2. Gruppi strettamente k-transitivi
In quest’ambito, un ovvio punto di partenza sono i gruppi strettamente ktransitivi perchè la distanza minima di questi gruppi è facile da calcolare.
Se G è un gruppo di permutazioni su A = {1, . . . , n}, ossia G di grado n, si
dice che G è strettamente k-transitivo se comunque prese due k-ple ordinate di
elementi distinti di A, esiste uno ed un solo elemento di G che manda la prima
k-pla nella seconda. Nel seguito, poichè gli studi sono finalizzati ad applicazioni
nella teoria dei codici, si supporrà sempre k ≥ 2.
I gruppi strettamente k-transitivi, k ≥ 2, sono tutti classificati:
k ≥ 6 : Sk , Sk+1 , Ak+2 .
k = 5 : S5 , S6 , A7 , il gruppo di Mathieu M12 .
k = 4 : S4 , S5 , A6 , il gruppo di Mathieu M11 .
k=3:
• Il gruppo proiettivo lineare su GF (q) ∪ {∞}
P GL(2, q) = {α : x → ax+b
, a, b, c, d ∈ GF (q), ad − bc 6= 0}.
cx+d
• Il gruppo Gσ su GF (q) ∪ {∞}, q = p2m , p 6= 2 così definito
(
)
∗
α : x → ax+b
,
a,
b,
c,
d
∈
GF
(q),
ad
−
bc
∈
H
;
cx+d
Gσ =
β : x → aσ(x)+b
, a, b, c, d ∈ GF (q), ad − bc ∈ GF (q)∗ \ H ∗
cσ(x)+d
m
dove σ : x → xp è l’automorfismo involutorio di GF (q), H ∗ gruppo dei
quadrati non nulli di GF (q).
3. UNCOVERINGS
93
k = 2 : Il gruppo delle affinità sulla retta affine
AG(1, F ) = {α :→ ax + b, a, b ∈ F, a 6= 0},
dove F è un quasicorpo finito.
Teorema 8.2.1. Sia G un gruppo di permutazioni strettamente k-transitivo di
grado n. Allora la distanza minima di G è n − k + 1.
Dimostrazione. Per definizione di stretta k-transitività, solo l’identità fissa
k punti e pertanto il massimo numero di punti fissati da un elemento di G che non
sia l’identità è k − 1. Quindi la distanza minima è n − (k − 1) = n − k + 1.
Esempio 8.2.2. Il gruppo simmetrico Sn è sia strettamente n-transitivo che
strettamente (n−1)-transitivo, mentre il gruppo alterno An è strettamente (n−2)transitivo. Pertanto la distanza minima di Sn è n − (n − 1) + 1 = 2, mentre la
distanza minima di An è n − (n − 2) + 1 = 3.
Se considerato come codice, il gruppo simmetrico non è molto utile perchè può
correggere h = b(d − 1)/2c = b(2 − 1)/2c = 0 errori. Il gruppo alterno può invece
correggere 1 errore.
3. Uncoverings
La capacità correttiva di un codice che è un gruppo strettamente k-transitivo
G di grado n è
d−1
(n − k + 1) − 1
n−k
c=b
c=b
c
h=b
2
2
2
e pertanto il metodo di decodifica presentato da Bailey e qui riportato, assume
come condizione iniziale che si siano verificati al più h = b n−k
c errori, cioè che
2
almeno n − h simboli siano corretti. Per la stretta k-transitività, ogni k-pla di simboli corretti identifica univocamente la parola del codice, tuttavia, non sappiamo
in quali t ≤ h posizioni siano gli errori, occorre dunque un metodo per scegliere un
insieme di k-ple in modo da poter essere certi che almeno una non contenga errori.
Ovvero, abbiamo bisogno di un insieme di k-sottoinsiemi di A = {1, 2, . . . , n} tali
che ogni t-sottoinsieme, t ≤ h, sia disgiunto da almeno un k-sottoinsieme.
Definizione 8.3.1. Un insieme U di k-sottoinsiemi di A = {1, 2, . . . , n} è detto
un (n, k, h)-uncovering se per ogni h-sottoinsieme R ⊂ A, esiste S ∈ U tale che
R ∩ S = ∅.
3. UNCOVERINGS
94
Esempio 8.3.2. Consideriamo il gruppo P GL(2, 7) strettamente 3-transitivo su
A = {1, 2, 3, 4, 5, 6, 7, 8}, si ha n = 8, k = 3, h = b(8 − 3)/2c = 2. Se consideriamo
U = {(1, 2, 3), (4, 5, 6), (2, 3, 7), (1, 7, 8)}, esso è un (8, 3, 2)-uncovering. Infatti per
ogni (a, b) con a, b ∈ A, in U esiste almeno un elemento che ha intersezione vuota
con (a, b).
Per velocizzare la decodifica, occorre che l’uncovering sia il più piccolo possibile.
Il problema diventa quindi quello di trovare il più piccolo uncovering possibile per
un dato insieme di parametri, ossia un minimo (n, k, h)-uncovering.
Il problema complementare, ossia quello di trovare un insieme di m-sottoinsiemi
di A tale che ogni h-sottoinsieme di A (con h < m) sia contenuto in almeno un
m-sottoinsieme, è molto interessante e studiato nell’ambito della teoria dei disegni.
Un tale insieme è noto come (n, m, h)-covering design, e gli insiemi di m elementi
sono detti blocchi del disegno. Ne segue che prendendo i complementari dei blocchi
di un (n, m, h)-covering design si ottiene un (n, n − m, h)-uncovering. Per questo
motivo chiameremo coblocchi gli elementi di un uncovering.
Per quanto detto, per la ricerca degli uncoverings è utile la letteratura sui
coverings design. Ad esempio, esiste in internet una raccolta di coverings design per
piccoli parametri: la Jolla Covering Repository 1. Molte delle costruzioni contenute
nella raccolta sono descritte in un articolo di Gordon2, mentre un quadro più
generale si trova nel lavoro di MacWilliams-Mullin3
Esempio 8.3.3. Consideriamo il gruppo P GL(2, 7) strettamente 3-transitivo su
A = {1, 2, 3, 4, 5, 6, 7, 8}, si ha n = 8, k = 3, h = b(8 − 3)/2c = 2. Se consideriamo
U = {(1, 2, 3), (4, 5, 6), (2, 3, 7), (1, 7, 8)}, esso è un (8, 3, 2)-uncovering. Infatti per
ogni (a, b) con a, b ∈ A, in U esiste almeno un elemento che ha intersezione vuota
con (a, b).
1Gordon,
D.M.,La Jolla Covering Repository, htpp://www.ccrwest.org/cover.html
D., Kuperberg G., Patashnik O., New constructions for covering designs, J. Comb.
Des., 3, 1995, 269 − 284.
3
MacWilliams F., Mullin R.,Coverings and packings, Contemporary Design Theory: A
collection of survey, New York, John Wiley et Sons, 1992.
2Gordon
4. ALGORITMO DI DECODIFICA PER GRUPPI STRETTAMENTE k-TRANSITIVI
95
4. Algoritmo di decodifica per gruppi strettamente k-transitivi
Algoritmo di decodifica
Sia G un gruppo di permutazioni strettamente k-transitivo su A, |A| = n. Sia
h = b(n − k)/2c e sia U un uncovering di G.
Supponiamo di ricevere la parola w = w1 w2 . . . wn . Consideriamo S1 ∈ U e
per i ∈ S1 analizziamo le componenti wi della parola ricevuta (ricordiamo che S1
è un k-sottoinsieme di A). Innanzitutto controlliamo che, in quelle posizioni, non
ci siano simboli ripetuti. Se non ce ne sono, per la stretta k-transitività di G,
esiste un’unica permutazione di G che manda wi nel posto i, per ogni i ∈ S1 , ossia
c’è una sola parola del codice con componente wi nel posto i, per ogni i ∈ S1 .
Cerchiamo questa parola tra gli elementi di G, sia p, e calcoliamo la sua distanza
dalla parola w ricevuta. Se la distanza è d(p, w) ≤ h allora p è la parola corretta
ossia decodifichiamo w con la parola p e terminiamo la procedura di decodifica.
Se invece d(p, w) > h, consideriamo un altro elemento S2 ∈ U e ripetiamo la
procedura. Ovviamente se in qualche passo t le componenti di w individuate da
St ∈ U presentano un simbolo ripetuto, è certo che nella trasmissione si è verificato
un errore e consideriamo immediatamente un altro elemento di U.
Il seguente schema descrive l’Algoritmo di decodifica sopra riportato.
START
Scelta di una
k-upla di
Ricerca della parola p
individuata dalla k-upla
La distanza di p dalla
parola ricevuta è ≤ h
SI
STOP
Figura widht 11.5 cm per 9.0 cm
Scelta di un’altra
k-upla di
NO
4. ALGORITMO DI DECODIFICA PER GRUPPI STRETTAMENTE k-TRANSITIVI
96
Esempio 8.4.1. Sia G = P GL(2, 7) e consideriamo l’uncovering U dell’esempio
8.3.2, ricordiamo che h = 2. Supponiamo di trasmettere la parola (permutazione)
g=12345678
e che venga ricevuta la parola
w=42365678.
Consideriamo S1 = (1, 2, 3) ∈ U e troviamo l’elemento di P GL(2, 7) che manda la
terna (1, 2, 3) in (w1 , w2 , w3 ) = (4, 2, 3). E’ la parola
p = 4 2 3 6 8 7 5 1.
Poichè d(p, w) = 4, la parola p non si accetta perchè d(p, w) > h. Consideriamo
allora un altro elemento dell’uncovering, sia S2 = (4, 5, 6) ∈ U, in w le componenti
relative ai posti indicati da S2 sono (w4 , w5 , w6 ) = (6, 5, 6) perciò non può esservi
nessuna permutazione di G con quei valori essedoci una ripetizione. Consideriamo
quindi un altro elemento dell’uncovering, sia S3 = (2, 3, 7) ∈ U, in w nelle posizioni
indicate da S3 troviamo le componenti (2, 3, 7); in G la permutazione che manda
(2, 3, 7) in (2, 3, 7) è la permutazione
g = 1 2 3 4 5 6 7 8,
poichè d(g, w) = 2(≤ h) la parola g è quella corretta per decodificare w.
E’ possibile trovare degli uncoverings per tutti i gruppi strettamente k-transitivi
fatta eccezione per il gruppo simmetrico Sn perchè la sua capacità correttiva è zero.
Costruzione di un uncovering per il gruppo alterno.
Consideriamo come codice il gruppo alterno An , esso è strettamente (n − 2)transitivo e pertanto è 1-correttore poichè risulta h = b(n − k)/2c = 1. Sia
Ω = {1, 2, . . . , n}, per costruire un uncovering occorre determinare un insieme U i
cui elementi sono degli (n − 2)-sottoinsiemi di Ω con la proprietà che ogni elemento
di Ω non appartenga ad almeno uno dei sottoinsiemi elementi di U.
Sia T l’insieme i cui elementi sono coppie di elementi di Ω e definito come
segue:
• Se n è pari, consideriamo T costituito dalle 21 n coppie disgiunte di elementi
di Ω.
• Se n è dispari, consideriamo T costituito dalle 12 (n − 1) coppie disgiunte
di elementi di Ω e dalla coppia formata dal rimanente elemento di Ω e da
un qualsiasi altro elemento.
Per avere un (n, n − 2, 1)-uncovering U basta considerare gli (n − 2)-sottoinsiemi
di Ω che sono i complementari delle coppie appartenenti a T .
4. ALGORITMO DI DECODIFICA PER GRUPPI STRETTAMENTE k-TRANSITIVI
97
Esempio 8.4.2. Consideriamo il gruppo alterno A7 , il (7, 5, 1)-uncovering di
A7 costruito con il metodo precedente è il seguente
U = {(3, 4, 5, 6, 7), (1, 2, 5, 6, 7), (1, 2, 3, 4, 7), (2, 3, 4, 5, 6)}.
Supponiamo di trasmettere la permutazione
g=2314675
e che venga ricevuta la parola
w=2314475
in cui è presente un errore nella quinta posizione. Decodifichiamo utilizzando
l’uncovering U. Consideriamo S1 = (3, 4, 5, 6, 7) ∈ U e cerchiamo in A7 l’elemento
che nei posti (3, 4, 5, 6, 7) ha come componenti rispettivamente (1, 4, 4, 7, 5) (ossia
la permutazione che manda (3, 4, 5, 6, 7) rispettivamente in (1, 4, 4, 7, 5)). Poichè
le componenti che stanno nel quarto e quinto posto sono uguali, in A7 non può
esservi nessuna permutazione con quelle componenti.
Consideriamo ora S2 = (1, 2, 5, 6, 7) ∈ U e cerchiamo in A7 l’elemento che
nei posti (1, 2, 5, 6, 7) ha come componenti rispettivamente (2, 3, 4, 7, 5) (ossia la
permutazione che manda (1, 2, 5, 6, 7) rispettivamente in (2, 3, 4, 7, 5)). E’ la permutazione
p=2361475
(l’unica altra possibilità di permutazione su Ω sarebbe stata p0 = 2 3 1 6 4 7 5 che
è di classe dispari e dunque non appartenente ad A7 ).
Poichè d(p, w) = 2(> h) la parola p non è accettata.
Consideriamo ora S3 = (1, 2, 3, 4, 7) ∈ U e cerchiamo in A7 l’elemento che
nei posti (1, 2, 3, 4, 7) ha come componenti rispettivamente (2, 3, 1, 4, 5) (ossia la
permutazione che manda (1, 2, 3, 4, 7) rispettivamente in (2, 3, 1, 4, 5)). E’ la permutazione
p = 2 3 1 4 6 7 5.
Poichè d(p, w) = 1(≤ h) la parola p è accettata ossia decodifichiamo w con p che
è proprio la parola g trasmessa.
Nota 8.4.3. Il metodo di decodifica descritto con l’algoritmo presentato in
questo paragrafo, non è il metodo di decodifica noto come permutation decoding .
5. UNCOVERING DEI GRUPPI DI MATHIEU M11 E M12
98
5. Uncovering dei gruppi di Mathieu M11 e M12
I gruppi di Mathieu sono cinque gruppi finiti scoperti dal matematico francese
Emile Mathieu (1835 − 1890). Questi gruppi vengono denotati con Mn , per i
valori n = 11, 12, 22, 23, 24. In particolare, M12 è strettamente 5-transitivo e ha
grado 12; M11 è lo stabilizzatore di un elemento di M12 e pertanto è strettamente
4-transitivo e di grado 11. Esistono vari metodi per costruirli, ma, per M12 , quello
presentato per il seguente schema è sicuramente il più semplice da ricordare 4
1
2
3
4
7
5
6
8
9
10
11
12
Generatori per M12
Figura widht 4.0 cm per 7.0 cm
Il gruppo M12 è generato dalle due permutazioni ottenute nel seguente modo:
• Una permutazione è la composizione dei 2-cicli formati dai numeri che
sono alle estremità dei segmenti rappresentati con I—J ossia
(1 2)(3 4)(5 6)(7 8)(9 10)(11 12).
• L’altra permutazione è la composizione dei 3-cicli ottenuti leggendo in
senso antiorario i numeri posti attorno ai punti rappresentati con • ossia
(1 3 2)(4 7 5)(8 9 11).
M12 è strettamente 5-transitivo su n = 12 elementi, ha distanza minima d =
12 − 5 + 1 = 8 e pertanto è 3-correttore.
M11 è strettamente 4-transitivo su n = 11 elementi, ha distanza minima d =
11 − 4 + 1 = 8 e pertanto è 3-correttore.
Se i gruppi M12 e M11 sono utilizzati come codici, essendo strettamente transitivi,
per la loro decodifica si può usare il metodo degli uncoverings. Riportiamo di
seguito un (12, 5, 3)-uncovering per M12 e un (11, 4, 3)-uncovering per M11 .
4Le
origini di questo diagramma sono nella teoria di Groethendieck 00 dessin d’enfants00 . G.
Jones,1998; Characters and syrfaces: a survey. The Atlas of finite Groups: Ten Years On
(eds Curtis e Wilson), London Mathematical Society Lecture Notes Series (249). Cambridge
University Press .
6. ESTENSIONE A GRUPPI NON STRETTAMENTE k-TRANSITIVI
(12, 5, 3)-uncovering per M12
1 2 3 4
5
1 2 6 11 12
1 3 7 8
9
1 4 6 7 10
1 5 8 9 11
2 4 8 9 12
2 5 7 10 11
3 4 7 11 12
3 5 6 10 12
3 6 8 9 11
6 7 8 9 10
99
(11, 4, 3)-uncovering per M11
1 2 3 4
1 2 5 6
3 4 5 6
7 8 9 10
7 8 9 11
7 8 10 11
7 9 10 11
8 9 10 11
6. Estensione a gruppi non strettamente k-transitivi
L’algoritmo presentato nel paragrafo 8.4 vale per i gruppi strettamente ktransitivi, tuttavia è possibile darne una generalizzazione applicabile ai gruppi
non strettamente k-transitivi.
Definizione 8.6.1. Sia G un gruppo su un insieme finito A. Una base per G
è un insieme B = {x1 , . . . , xb } ⊆ A tale che G(x1 ,...,xb ) =< 1 >, ossia lo stabilizzatore di B è l’elemento identità. Una base non ridondante è una base tale che
G(x1 ,...,xi ,xi+1 ) 6= G(x1 ,...,xi ) per i = 1, . . . , b − 1.
Esempio 8.6.2. In un gruppo G strettamente k-transitivo su A, ogni k-pla di
elementi di A costituisce una base non ridondante.
Esempio 8.6.3. Sia G = GL(n, q) il gruppo generale lineare che agisce sui
vettori non nulli di Fqn . Una base dello spazio vettoriale Fqn costituisce una base
non ridondante per G.
Teorema 8.6.4. Sia G un gruppo e sia (x1 , . . . , xb ) una sua base. Considerati due elementi g, h ∈ G, se (x1 , . . . , xb )g = (x1 , . . . , xb )h allora g = h, ossia
l’azione di un elemento g ∈ G su una base (x1 , . . . , xb ) determina univocamente
quell’elemento.
6. ESTENSIONE A GRUPPI NON STRETTAMENTE k-TRANSITIVI
100
Dimostrazione. Siano g, h ∈ G e sia (x1 , . . . , xb ) una base di G. Se xgi =
−1
xhi per ogni i = 1, . . . , b, allora xgh
= xi per ogni i = 1, . . . , b, ossia gh−1 ∈
i
G(x1 ,...,xb ) =< 1 >, e pertanto gh−1 = 1 da cui segue g = h.
Il teorema ora dimostrato assicura che se un gruppo G viene utilizzato come
codice e nella trasmissione si riceve una parola contenente errori in posizioni diverse
da quelle individuate da una base, nella operazione di decodifica gli errori vengono
corretti. Ne consegue che per generalizzare l’algoritmo di decodifica presentato nel
paragrafo 8.4 per i gruppi strettamente k-transitivi, basta sostituire 00 k-pla00 con
00
base00 . La nozione di 00 uncovering00 dovrà invece essere sostituita con quella più
generale di 00 uncovering-by-bases00 .
Definizione 8.6.5. Sia G un gruppo su A, |A| = n, con capacità correttiva h.
Si dice che U è un uncovering-by-bases per G se U è un insieme di basi per G
tali che ogni h-sottoinsieme di A è disgiunto da almeno una base.
Chiaramente, nel caso in cui G sia un gruppo strettamente k-transitivo, un
uncovering-by-bases è un (n, k, h)-uncovering.
L’algoritmo che utilizza gli uncovering-by-bases si differenzia da quello che
utilizza gli uncovering per due aspetti
• ammette la possibilità che le basi dell’uncovering abbiano dimensioni
diverse;
• l’esistenza di un elemento del gruppo che, nelle posizioni individuate da
una data base, concordi con la parola ricevuta non assicura la correttezza
e pertanto l’algoritmo include un controllo di non esistenza.
Algoritmo di decodifica
Sia G un gruppo di permutazioni su A, |A| = n. Sia U un uncovering-by-bases di
G.
Supponiamo di ricevere la parola w = w1 w2 . . . wn . Consideriamo una base
B1 ∈ U e per i ∈ B1 analizziamo le componenti wi della parola ricevuta . Innanzitutto controlliamo che, in quelle posizioni, non ci siano simboli ripetuti. Supposto
che queste componenti siano tutte distinte, verifichiamo se in G esiste un elemento
che manda wi nel posto i, per ogni i ∈ B1 , ossia se c’è una parola del codice con
componente wi nel posto i, per ogni i ∈ B1 . Se questa parola esiste, sia p. Calcoliamo la sua distanza dalla parola w ricevuta. Se la distanza è d(p, w) ≤ h allora
possiamo concludere che la parola trasmessa è p ossia decodifichiamo w con la parola p e terminiamo la procedura di decodifica. Se invece d(p, w) > h, consideriamo
un’altra base B2 ∈ U e ripetiamo la procedura. Ovviamente se in qualche passo t
7. SIMBOLI RIPETUTI
101
le componenti di w individuate da St ∈ U presentano un simbolo ripetuto, è certo che nella trasmissione si è verificato un errore e consideriamo immediatamente
un’altra base.
Non è detto che per un qualunque gruppo G esista sempre un uncovering-bybases, ma, come assicura il prossimo teorema, ciò è vero per ogni gruppo finito.
Teorema 8.6.6. Per ogni gruppo finito G su un insieme A, |A| = n, esiste
sempre un uncovering-by-bases.
Dimostrazione. Sia d la distanza minima di G, h = b(d−1)/2c. Supponiamo
per assurdo che esista un h-sottoinsieme R ⊆ A che intersechi ogni base di G. Allora
lo stabilizzatore puntuale di R̄ = A\R non è banale perchè R̄ non contiene una
base. Esiste pertanto g ∈ G, g diverso dall’ identità, che fissa R̄ punto per punto
e perciò |F ix(g)| ≥ |R̄| = n − r. Ma il massimo numero di punti fissati da un
elemento che non sia l’identità è n − d < n − r e pertanto si ha un assurdo.
Si noti che il teorema ora dimostrato assicura solo l’esistenza di un uncoveringby-bases ma non fornisce nessuna indicazione costruttiva.
7. Simboli ripetuti
Supponiamo di usare un gruppo come codice e di trasmettere pertanto come
parola una permutazione. Se la parola ricevuta contiene errori, allora potrebbe non
essere più una permutazione, ossia potrebbe contenere uno o più simboli ripetuti.
Esaminiamo come i simboli ripetuti possono aiutare nella decodifica, in particolare
possono essere di aiuto nel ridurre il numero di passi da eseguire. Per illustrare
questo, utilizziamo il caso del gruppo di Mathieu M12 . La dimensione di questo
codice è tale che le possibilità in cui possono presentarsi gli errori sono in numero
sufficientemente piccolo da poterle esaminare una ad una. Per codici più grandi,
si può comunque applicare quanto illustreremo per M12 , basta isolare nelle parole
alcune cifre dove sappiamo esserci un errore e applicare un algoritmo simile alle
rimanenti cifre per individuare errori e in un numero minore di passi.
Consideriamo il gruppo M12 , ricordiamo che M12 è 3-correttore. Per la decodifica, se una parola ricevuta è una permutazione allora applichiamo l’Algoritmo
presentato nel paragrafo 8.4. Se si riceve una parola che non è una permutazione,
si può migliorare l’algoritmo andando a considerare i posti dove figurano simboli
ripetuti. Ad esempio, se i tre errori sono tre repliche dello stesso simbolo (il simbolo si presenta quindi quattro volte), allora sappiamo che i rimanenti otto simboli
sono corretti e perciò (essendo il gruppo strettamente 5-transitivo) possiamo immediatamente trovare l’unica parola del codice individuata da una qualunque 5-pla
7. SIMBOLI RIPETUTI
102
presa fra gli otto simboli corretti. In un solo passo si è così giunti a decodificare
correttamente la parola ricevuta.
Analizziamo nel dettaglio il caso del gruppo M12 quando la parola ricevuta non
è una permutazione. Supponiamo venga trasmessa la parola identità
1 2 3 4 5 6 7 8 9 10 11 12
1◦ caso: la parola ricevuta contiene tre errori.
• Un simbolo ripetuto, due simboli spostati:
esempio: 1 1 4 3 5 6 7 8 9 10 11 12
Occorre un (10, 5, 2)-uncovering perchè sappiamo che almeno uno dei due
1 è un errore.
• Due diversi simboli ripetuti, un simbolo spostato:
esempio: 1 1 3 3 2 6 7 8 9 10 11 12
Occorre un (8, 5, 1)-uncovering.
• Tre diversi simboli ripetuti:
esempio: 1 1 3 3 5 5 7 8 9 10 11 12
Sappiamo che ci sono tre errori nelle prime sei posizioni, possiamo quindi
considerare cinque qualsiasi delle ultime sei posizioni per individuare la
parola del codice trasmessa.
• Un simbolo ripetuto tre volte:
esempio: 1 1 1 1 5 6 7 8 9 10 11 12
Possiamo considerare cinque qualsiasi delle ultime otto posizioni per individuare la parola del codice trasmessa.
• Un simbolo ripetuto due volte, un altro simbolo ripetuto:
esempio: 1 1 1 4 4 6 7 8 9 10 11 12
Possiamo considerare cinque qualsiasi delle ultime sette posizioni per
individuare la parola del codice trasmessa.
• Un simbolo ripetuto due volte, un simbolo spostato:
esempio: 1 1 1 2 5 6 7 8 9 10 11 12
Occorre un (9, 5, 1)-uncovering.
• Un simbolo ripetuto due volte, entrambi in posizioni non corrette, un
simbolo spostato:
esempio: 3 3 1 4 5 6 7 8 9 10 11 12
Occorre un (10, 5, 2)-uncovering.
2◦ caso: la parola ricevuta contiene due errori.
• Due simboli ripetuti:
esempio: 1 1 3 3 5 6 7 8 9 10 11 12
Occorre un (8, 5, 1)-uncovering perchè sappiamo che almeno uno dei due
1 è un errore.
• Un simbolo ripetuto due volte:
esempio: 1 1 1 4 5 6 7 8 9 10 11 12
8. OTTIMIZZAZIONE
103
Occorre un (9, 5, 1)-uncovering.
3◦ caso: la parola ricevuta contiene un errore.
• Un simbolo ripetuto:
esempio: 1 1 3 4 5 6 7 8 9 10 11 12
Occorre un (10, 5, 1)-uncovering.
Riportiamo gli uncovering che, dall’analisi fatta, occorrono per la decodifica.
(12, 5, 3)-uncovering per M12
1 2 3 4
5
1 2 6 11 12
1 3 7 8
9
1 4 6 7 10
1 5 8 9 11
2 4 8 9 12
2 5 7 10 11
3 4 7 11 12
3 5 6 10 12
3 6 8 9 11
6 7 8 9 10
(10, 5, 2)-uncovering per M12
1 2 3 4 5
1 2 7 8 10
1 5 6 7 9
2 3 6 8 9
3 4 7 9 10
4 5 6 8 10
(9, 5, 1)-uncovering per M12
1 2 3 4 5
1 6 7 8 9
5 6 7 8 9
(8, 5, 1)-uncovering per M12
1 2 3 4 5
1 2 6 7 8
4 5 6 7 8
8. Ottimizzazione
Fino ad ora, quando si è considerato un uncovering-by-bases non si è tenuto
conto in quale ordine prendere le basi. Tuttavia, applicando l’algoritmo di decodifica, l’ordine con cui si considerano le basi è importante perchè influisce sui tempi
di prestazione. Sebbene gli uncovering siano sempre stati presentati in ordine lessicografico, non c’è ragione per cui questo ordinamento debba essere usato nella
pratica. Vediamo come ordinare un uncovering-by-bases in modo ottimale.
Sia G un gruppo di grado n e h-correttore. Sia U, |U| = u, un uncovering-bybases così ordinato: (B1 , B2 , . . . , Bu ). Per un dato insieme E, |E| ≤ h, di posizioni
d’errore, indichiamo con i il numero delle prove che si devono effettuare per trovare
8. OTTIMIZZAZIONE
104
la prima base disgiunta da E (quindi i è il numero di volte in cui deve essere eseguito
l’algoritmo). Possiamo allora calcolare il numero medio di prove, che dipenderà
dall’ordine con cui si prendono le basi.
Per contare il numero medio delle prove necessarie per j ≤ h errori, definiamo
la successione sj = (s1j , s2j , . . . , suj ), dove sij è il numero di sottoinsiemi di ordine
j di {1, 2, . . . , n} disgiunti da Bi ma non da B1 , . . . , Bi−1 . Pertanto il numero medio
di prove è
Pu
is
ij .
aj = i=1
n
j
Esempio 8.8.1. Si consideri il gruppo di Mathieu M12 , esso ha grado 12 e capacità correttiva 3. Consideriamo il (12, 5, 3)-uncovering del paragrafo precedente
in ordine lessicografico. Supponiamo che si verifichino tre errori e di ricevere la
sequenza
35, 31, 30, 23, 17, 21, 20, 15, 17, 8, 3
Utilizzando la formula precedente troviamo che il numero medio di prove è a3 =
1016
.
220
Un modo per ottimizzare l’ordine con cui considerare gli elementi di un uncovering, è quello di minimizzare il numero ah . In generale non è un problema di
facile risoluzione, tuttavia, esiste un metodo relativamente semplice per migliorare
l’efficienza di un dato ordinamento.
Algoritmo di decodifica 00 ottimizzato00
Consideriamo l’uncovering nell’ordine (B1 , B2 , . . . , Bu ) che determina la successione s = (s1 , s2 , . . . , su ). Assumiamo j = h e supponiamo s1 ≥ s2 ≥ . . . ≥ sl e
che sia
sl < sl+1
ovvero che sia il primo punto in cui la successione si incrementa. Otteniamo un
nuovo ordinamento (B10 , B20 , . . . , Bu0 ) scambiando Bl e Bl+1 e lasciando inalterati
tutti gli altri elementi. In questo modo abbiamo
0
= B1 , . . . , Bl−1
= Bl−1
B10
0
0
Bl
= Bl+1 , Bl+1
= Bl .
0
Bl+2
= Bl+2 , . . . , Bu0 = Bu
Questo nuovo ordinamento genera la successione s = (s01 , . . . , s0u . Osserviamo
che:
• s01 = s1 , . . . , s0l−1 e s0l+2 = sl+2 , . . . , s0u = su ;
• s0l ≥ sl+1 e s0l+1 ≤ sl ;
• s0l + s0l+1 = sl + sl+1 .
8. OTTIMIZZAZIONE
105
Questo nuovo ordine è effettivamente un miglioramento, come assicura il seguente teorema.
Teorema 8.8.2. Con riferimento alle notazioni sopra riportate, si ha
u
u
X
X
0
isi <
isi .
i=1
i=1
Dimostrazione. Poichè s01 = s1 , . . . , s0l−1 e s0l+2 = sl+2 , . . . , s0u = su , è sufficiente mostrare che
ls0l + (l + 1)s0l+1 < lsl + (l + 1)sl+1 .
Dalle disuguaglianze sl < sl+1 , s0l ≥ sl+1 e s0l+1 ≤ sl , si ha sl < sl+1 ≤ s0l , pertanto
s0l = sl + d per qualche d > 0. Ricordando che s0l + s0l+1 = sl + sl+1 , otteniamo
s0l − sl = sl+1 − s0l+1 = d.
Pertanto si ha che l(s0l − sl = l(sl+1 − s0l+1 ) < (l + 1)(sl+1 − s0l+1 ), da cui otteniamo
ls0l + (l + 1)s0l+1 < lsl + (l + 1)sl+1 .
Rimane dunque provato che l’algoritmo di decodifica 00 ottimizzato00 precedentemente riportato, riduce effettivamente il numero medio di prove. Possiamo
pertanto iterarlo per ottenere una successione decrescente.
Esempio 8.8.3. Consideriamo l’uncovering dell’esempio 8.8.1. Il quinto termine della successione ottenuta è più piccolo del sesto e perciò cambiamo l’ordine
nell’uncovering scambiando la quinta base con la sesta, otteniamo
(12, 5, 3)-uncovering per M12
1 2 3 4 5
1 2 6 11 12
1 3 7 8 9
1 4 6 7 10
2 4 8 9 12
1 5 8 9 11
2 5 7 10 11
3 4 7 11 12
3 5 6 10 12
3 6 8 9 11
6 7 8 9 10
Questo nuovo ordine genera la seguente successione:
35, 31, 30, 23, 23, 15, 20, 15, 17, 8, 3.
8. OTTIMIZZAZIONE
106
Iteriamo poi l’algoritmo di decodifica 00 ottimizzato00 finchè non otteniamo il seguente ordine:
(12, 5, 3)-uncovering per M12
1 2 3 4 5
1 2 6 11 12
1 3 7 8 9
1 4 6 7 10
2 4 8 9 12
2 5 7 10 11
3 5 6 10 12
3 4 7 11 12
1 5 8 9 11
3 6 8 9 11
6 7 8 9 10
che genera la seguente successione decrescente:
35, 31, 30, 23, 23, 23, 20, 13, 11, 8, 3.
Con questo ordine il numero medio di prove (per tre errori) è ora
988
.
220
Si noti che il teorema 8.8.2 non assicura l’esistenza di ordinamento migliore,
ma assicura che il miglior ordinamento possibile eve generare una successione decrescente. Un’esaustiva ricerca fatta utilizzando GAP, ha rivelato che per M12 il
959
valore minimo per il numero medio di prove è 220
e che 288 degli 11! possibili
ordinamenti generano quel valore.
CAPITOLO 9
Elementi di Crittografia
Da sempre, soprattutto in tempi di guerra, si è sentita la necessità di trovare
stratagemmi per inviare messaggi in modo da non farli scoprire all’avversario. Un
modo può essere quello di nascondere il messaggio: questa tecnica prende il nome
di stenografia. Un altro modo per spedire un messaggio senza che il nemico lo
possa capire, si ottiene nascondendo non il messaggio ma il suo significato: in
questo caso si parla di crittografia.
1. Introduzione
Compito primario della crittografia è quello di fornire strumenti che permettano
la trasmissione di informazioni in modo che solo persone autorizzate siano in grado
di capirle.
Il problema di sviluppare metodi efficienti per comunicare in modo segreto e sicuro è diventato estremamente attuale con lo sviluppo dei sistemi di comunicazione
(in particolare di quelli elettronici e informatici).
GLOSSARIO di CRITTOGRAFIA
Testo in chiaro, messaggio in chiaro: Messaggio originale che si vuole
mandare in modo segreto, oppure stringa di simboli che rappresenta il messaggio
o il testo che si vuole cifrare.
Testo cifrato, messaggio cifrato: Versione alterata, nascosta del testo in
chiaro.
Crittare, cifrare, crittografare: Passare dal testo in chiaro al testo cifrato.
Decifrare : Passare dal testo cifrato al testo in chiaro.
Cifratura : Metodo usato per modificare il testo in chiaro nel testo cifrato.
107
1. INTRODUZIONE
108
Decifratura : Passaggio dal testo cifrato al testo in chiaro, si tratta del
processo inverso della cifratura.
Chiave : Determina una ben precisa trasformazione di cifratura, ma anche la
regola inversa di decifratura, fra tutte quelle possibili che si possono usare: nel
primo caso si parla di chiave per cifrare, nel secondo di chiave per decifrare.
Crittologia : Scienza della cifratura dei messaggi.
Crittoanalisi : Scienza dell’interpretazione di messaggi cifrati.
Compito del crittologo è di inventare sistemi (detti crittosistemi) per trasformare un messaggio in chiaro in un messaggio cifrato. Compito del crittoanalista
è di contrastare questa operazione trovando dei modi per interpretare i messaggi
cifrati riportandoli in chiaro senza autorizzazione.
Messaggi Unitari : Generalmente i messaggi, sia quelli in chiaro sia quelli
cifrati, vengono spezzati in messaggi unitari che possono essere costituiti da una
singola lettera o da blocchi di lettere. Il vantaggio di dividere un messaggio in
blocchi di lunghezza prefissata è quello di evitare la possibilità di riconoscere facilmente inizio e fine di parole, rendendo così più difficile la crittoanalisi basata sulle
frequenze.
Crittografia simmetrica : Sin dall’antichità, i metodi classici per cifrare
sono costruiti in modo che mittente e destinatario abbiano una chiave comune con
la quale il mittente cifra e il destinatario decifra; un algoritmo di questo tipo si
dice simmetrico.
Crittografia asimmetrica o a Chiave Pubblica : Dai tempi dei tempi
occorre arrivare al 1975 per avere una grande svolta nella crittografia, ciò avviene
con l’introduzione di algoritmi in cui solo il destinatario ha bisogno di una chiave
segreta; questo tipo di algoritmo è detto asimmetrico o a chiave pubblica. I sistemi
asimmetrici furono proposti da W.Diffie e M. Hellman dell’Università di Stanford
in un lavoro pubblicato nel 1976 dal titolo New directions in Cryptography.
In un cifrario a chiave pubblica, per calcolare in un tempo ragionevolmente
breve la decifratura di un messaggio, è necessario essere in possesso di altre informazioni oltre a quelle rese pubbliche, ossia, per decifrare senza avere opportune
informazioni aggiuntive occorre un tempo di calcolo incredibilmente lungo. Anche
i sistemi asimmetrici sono comunque attaccabili e nella prospettiva di computer
con capacità di calcolo molto più avanzate rispetto a quelle attuali, la crittografia
si sta orientando verso nuove metodologie che trovano riferimento nella crittografia
quantistica.
2. CRITTOSISTEMI A CHIAVE PUBBLICA
109
Crittografia Quantistica : La crittografia quantistica rappresenta, dopo
quella a chiave pubblica, una seconda vera rivoluzione perchè, ad oggi, risulta
inattaccabile. La crittografia quantistica sfrutta delle peculiarità della meccanica quantistica nella fase dello scambio delle chiavi per evitare che queste possano
essere intercettate da un attaccante senza che i due interlocutori se ne accorgano.
Il principio che sta alla base della crittografia quantistica è il principio di indeterminazione di Heisenberg. Questo principio afferma che non è possibile conoscere,
simultaneamente e con precisione assoluta, alcune particolari coppie di caratteristiche di un oggetto quantistico, come ad esempio la posizione e la velocità di un
elettrone. Se si cerca di misurare esattamente la posizione, si perde la possibilità
di verificare la velocità dell’elettrone. Se invece si misura con precisione assoluta
la velocità, si perdono inevitabilmente informazioni sul luogo in cui l’elettrone si
trova.
Secondo la meccanica quantistica, per quante tecniche nuove e più precise si
possano sviluppare per eseguire queste misure, il limite rimane e non è concettualmente eliminabile.
Realizzando una chiave quantistica (cioè realizzata con elementi come i fotoni
che rispondono alle leggi della meccanica quantistica) chi volesse, non autorizzato, cercare di decriptare il messaggio, modificherebbe inevitabilmente la chiave,
oltretutto in maniera puramente casuale quindi incontrollabile e verrebbe quindi
certamente scoperto. Nell’ambito della crittografia quantistica, un algoritmo che
permette lo scambio di una chiave tra due utenti e garantisce che questa non possa
essere intercettata da terzi senza che i due interlocutori se ne accorgano, è chiamato BB84, dal nome dei suoi ideatori: Bennet e Brassard che lo realizzarono nel
1984.
2. Crittosistemi a chiave pubblica
I sistemi di crittografia a chiave pubblica, come già detto, sono stati ideati da
Diffie e Hellman nel 1975. Essi utilizzano una chiave pubblica che permette la cifratura ma non la decifratura di un messaggio. Ogni utente pubblica la propria chiave
di cifratura per permettere a chiunque voglia comunicare con lui segretamente di
poterlo fare.
Per descrivere i cifrari a chiave pubblica, supponiamo che ogni partecipante P
al sistema di cifratura abbia una coppia di chiavi:
• una chiave pubblica C = CP per cifrare;
• una chiave privata (segreta) D = DP per decifrare;
3. VANTAGGI, SVANTAGGI, APPLICAZIONI DEI CRITTOSISTEMI A CHIAVE PUBBLICA
110
con la proprietà che non è possibile calcolare DP conoscendo CP . Tutte le chiavi
pubbliche sono utilizzabili pubblicamente, esse possono essere raccolte in un archivio pubblico al pari di un elenco telefonico. Al contrario le chiavi private sono
note solo ai loro proprietari.
Per comodità denotiamo con C(m) il testo cifrato ottenuto dal messaggio m
usando la chiave C.
Supponiamo che ogni partecipante ad un sistema di cifratura asimmetrica abbia
sia la chiave pubblica sia quella privata:
(1) Se P1 vuole mandare il messaggio m a P2 , allora P1
• trova la chiave pubblica CP2 di P2 ,
• cifra il messaggio m usando CP2 ,
• manda CP2 (m) a P2 .
(2) P2 è in grado di decifrare il testo cifrato CP2 (m) poichè P2 (e solo P2 )
conosce la chiave DP2 :
DP2 (CP2 (m)) = m.
(3) Nessun altro partecipante può decifrare CP2 (m), perchè nessuno può dedurre DP2 nè da CP2 nè da CP2 (m).
3. Vantaggi, svantaggi, applicazioni dei crittosistemi a chiave pubblica
Vantaggi
I vantaggi offerti dai sistemi di cifratura a chiave pubblica sono molteplici.
• Non è necessario nessun scambio di chiavi tra i partecipanti. Si può mandare un messaggio segreto senza nessun bisogno di scegliere prima, insieme
al destinatario, una chiave segreta.
• Occorre un numero di chiavi relativamente piccolo. Usando sistemi simmetrici, ogni coppia di partecipanti deve avere una chiave segreta personale,
quindi se ci sono n partecipanti occorrono n(n−1)
chiavi diverse. Invece,
2
usando un algoritmo asimmetrico, ogni partecipante ha bisogno di sole
due chiavi e solo una di queste deve essere tenuta segreta, quindi con n
partecipanti il numero delle chiavi è solo 2n.
• Nuovi utenti possono entrare nel sistema senza alcun problema per i vecchi. Invece con un sistema simmetrico, se entra un nuovo utente, tutti i
vecchi partecipanti devono scambiare una chiave segreta con lui. In un
sistema asimmetrico, i vecchi utenti non devono scambiare alcun dato con
il neoutente.
4. IL SISTEMA RSA
111
Svantaggi
• Nessun algoritmo asimmetrico è inattaccabile e allo stesso tempo veloce.
• Un algoritmo a chiave pubblica richiede la custodia di chiavi e pertanto
ci deve essere la garanzia che le chiavi pubbliche siano autentiche.
Applicazioni
Le applicazioni dei sistemi a chiave pubblica sono molteplici, ad esempio:
• l’autentica elettronica della firma;
• l’accesso ad archivi segreti o a sistemi di sicurezza;
• l’accesso a servizi come carte di credito, programmi televisivi a pagamento, ecc. .
4. Il sistema RSA
RSA è un sistema di crittografia a chiave pubblica ideato da Diffie e Hellman
ma chiamato sistema RSA dai nomi di coloro che, nel 1977, per primi lo hanno
realizzato : R. Rivest, A.Shamir, L.Adleman.
Negli anni, sono stati realizzati altri algoritmi asimmetrici ma l’algoritmo RSA
è certamente il più conosciuto e quello studiato in modo più approfondito.
RICHIAMI di MATEMATICA
• Indicatore di Eulero φ(n). Dato un numero naturale n, con φ(n) (indicatore di Eulero) si indica il numero dei numeri naturali minori di n e primi
con n. Esempio: φ(1) = 1 (per convenzione), φ(2) = 1, φ(3) = 2, φ(4) =
2, φ(6) = 2, φ(10) = 4, φ(15) = 8.
• Se p è un numero primo, allora : φ(p) = p − 1.
• Se p e q sono due numeri primi distinti, allora : φ(pq) = (p − 1)(q − 1).
• Teorema di Eulero : Se m ed n sono due numeri naturali primi fra loro
allora mφ(n) ≡ 1 mod n.
• Teorema : Se a e b sono due interi primi tra loro, allora esiste un intero
c tale che b · c ≡ 1 mod a.
Teorema 9.4.1. Sia n prodotto di numeri primi distinti: n = p1 p2 · · · pr . Se
a, b ∈ N∗ sono tali che pi − 1 divide ab − 1 per ogni i = 1, 2, . . . , r, allora
mab ≡ m mod n
per ogni intero m (anche se m non è primo con n).
4. IL SISTEMA RSA
112
Dimostrazione. Sia n = p1 p2 · · · pr con pi numero primo per ogni i = 1, 2, . . . , r
e pi 6= pj per i 6= j. Iniziamo con il dimostrare che per ogni m ∈ N∗ risulta
mab ≡ m mod p1 .
Distinguiamo due casi.
1◦ caso - Gli interi m e p1 non sono primi fra loro. Allora m è multiplo di p1
perchè p1 è un numero primo; ovviamente anche mab è multiplo di p1 e pertanto
si ha
m ≡ 0 mod p1 , mab ≡ 0 mod p1
da cui segue
mab ≡ m mod p1 .
2◦ caso - Gli interi m e p1 sono primi fra loro. Allora:
(1) dall’ipotesi si ha che ab−1 è divisibile per (p1 −1), ossia ab ≡ 1 mod (p1 −1)
ab = 1 + k(p1 − 1).
(2) Da (1) si ha mab = m·mk(p1 −1) = m·(mp1 −1 )k . Poichè (p1 −1) = φ(p1 ), dal
Teorema di Eulero precedentemente richiamato si ha mφ(p1 ) ≡ 1 mod p1 ,
ossia mp1 −1 ≡ 1 mod p1 . Ne segue che mab ≡ m · 1k mod p1 ossia
mab ≡ m mod p1 .
Rimane così provato che
mab ≡ m mod p1
per ogni m ∈ N∗ .
Quanto dimostrato per il numero primo p1 , vale per ogni numero primo
pi tale che ab − 1 è divisibile per pi − 1 e pertanto, poichè n = p1 p2 · · · pr è
prodotto di numeri primi distinti soddisfacenti la proprietà richiesta, per
ogni i = 1, 2, . . . , r si ha che pi divide l’intero mab − m e, per i 6= j, anche
il prodotto pi pj divide mab − m. Ne segue che per n = p1 p2 · · · pr si ha
mab ≡ m mod n
per ogni m ∈ N∗ .
GENERAZIONE delle CHIAVI
Poichè ogni partecipante al sistema RSA deve essere fornito di due chiavi, prima
di descrivere l’algoritmo vediamo come si generano le chiavi pubbliche e le chiavi
private.
E’ consigliabile affidare ad un centro addetto questa operazione. Per ogni
partecipante il centro sceglie due numeri primi distinti p e q ognuno dei quali sia
di almeno 100 cifre e li moltiplica ottenendo n = pq.
4. IL SISTEMA RSA
113
Successivamente calcola φ(n) = φ(pq) = (p − 1)(q − 1) e infine il centro sceglie
un numero naturale e primo con φ(n), ossia M CD(e, p − 1) = M CD(e, q − 1) = 1,
e calcola d tale che
e · d mod φ(n) = 1.
Ora il partecipante al sistema riceve le sue due chiavi:
- Chiave pubblica: la coppia di numeri (n, e).
- Chiave privata: il numero d.
Osservazioni
• Nessun partecipante ha bisogno di conoscere i numeri p, q, φ(n). Anche
per questo è consigliabile non lasciare al singolo il compito di scegliere
la sua chiave ma lasciare il compito ad un centro addetto che poi cancellerà immediatamente i dati usati per il calcolo delle chiavi, ciò eviterà
che qualcuno possa impadronirsi di p, q, φ(n) e quindi calcolare la chiave
segreta.
• Il numero e può essere scelto in modo opportuno affinchè sia facile calcolare me mod n. Ad esempio:
– E’ stato proposto di scegliere sempre come numero e il quarto numero
4
di Fermat F4 = 22 +1 = 65537 perchè la sua rappresentazione binaria
è semplicemente 10000000000000001 e quindi è relativamente facile
calcolare me . Ovviamente l’altro numero della chiave pubblica, ossia
il numero n, è diverso per ogni partecipante al sistema e questo è
sufficiente per garantire che le chiavi segrete siano tutte diverse.
– Un altro modo è quello di prendere un numero primo che non divida
φ(n).
– Un terzo modo di procedere è quello di scegliere a caso un numero e,
calcolare M CD(e, φ(n)) usando l’algoritmo di Euclide, e poi dividere
e per questo M CD. A questo punto si calcola il numero d (chiave
segreta) corrispondente ad e usando l’algoritmo di Euclide. Ovviamente calcolare φ(n) non è un problema perchè p e q sono primi fra
loro.
• Con la chiave pubblica si può trovare la chiave segreta solo se si riesce a
fattorizzare n nei suoi fattori primi p e q, ma ad oggi non si conoscono
algoritmi per fattorizzare numeri grandi in tempi ragionevoli. Si tenga
conto che RSA utilizza numeri primi che hanno da 100 a 200 cifre e quindi, anche con gli algoritmi più evoluti, risulta davvero difficile riuscire a
fattorizzare n in tempi ragionevoli.
4. IL SISTEMA RSA
114
ALGORITMO RSA
L’algoritmo RSA è una diretta applicazione del Teorema di Eulero precedentemente richiamato.
Supponiamo che A voglia inviare un messaggio a B. Anzitutto A deve conoscere
la chiave pubblica di B che supponiamo sia la coppia (n, e).
• Il messaggio deve essere codificato in una sequenza di uno o più interi
positivi mi tali che per ogni i sia mi < n e M CD(mi , n) = 1.
In realtà la richiesta che sia M CD(mi , n) = 1 è una condizione che semplifica la
procedura, ma non è necessaria, come dimostra il Teorema 9.4.1 . La richiesta non
fa perdere in generalità.
Per codificare in modo che i messaggi mi soddisfino alle richieste soprascritte,
esistono vari modi; nella maggior parte dei computers si usa il sistema ASCII (vedi
esempio 2.5.4). Senza soffermarci sulla procedura di codifica, supponiamo che il
messaggio sia stato codificato nell’intero positivo m con m < n e M CD(m, n) = 1.
CIFRATURA
Nota la chiave pubblica (n, e) del destinatario B, al testo in chiaro m si applica
la formula
me mod n = t
in questo modo A ottiene il testo cifrato t da trasmettere a B.
DECIFRATURA
Il signor B riceve t e decifra applicando la sua chiave privata con la formula
td mod n = m.
Questo metodo per cifrare e decifrare funziona perchè applica il Teorema di
Eulero e il Teorema 9.4.1. Infatti da t ≡ me mod n segue td ≡ med mod n.
Da ed ≡ 1 mod φ(n) si ha ed = 1 + kφ(n) e pertanto med = m1+kφ(n) da cui
td ≡ m1+kφ(n) mod n. Poichè M CD(m, n) = 1 e m < n, per il Teorema di Eulero
si ha m1+kφ(n) ≡ m mod n e quindi
td ≡ m mod n.
Poichè m < n non c’è ambiguità nella determinazione del numero congruo a
t mod n perchè fra 0 e n − 1 ce ne è uno solo.
d
Esempio 9.4.2. Supponiamo che Carla voglia inviare un messaggio a Ugo con
il metodo RSA.
4. IL SISTEMA RSA
115
(1) Generiamo le chiavi di Ugo. Scegliamo due numeri primi molto grandi p e
q. Come già detto, solitamente questi vengono scelti dal centro di calcolo
e poi cancellati. Nel nostro esempio, per ragioni di calcolo, scegliamo
numeri piccoli: sia p = 17 e q = 11.
(2) Calcoliamo n = pq = 17 · 11 = 187 e scegliamo un numero naturale e tale
che sia primo con φ(n) = (p − 1)(q − 1) = 160, sia e = 7.
(3) Calcoliamo d tale che e · d mod φ(n) = 1, ossia tale che 7 · d mod 160 = 1,
pertanto d = 23.
Ugo ha come chiave pubblica la coppia (n, e) = (187, 7) e come chiave
privata d = 23.
(4) Per cifrare il messaggio da inviare, Carla deve prima trasformare il messaggio in un numero m. Supponiamo che Carla utilizzi il sistema ASCII
e, per semplicità, supponiamo che il messaggio sia costituito dalla sola
lettera V . Questa lettera nel codice ASCII è rappresentata dal numero 86
ossia m = 86 (e risulta 86 < 187).
(5) Carla per cifrare il messaggio m = 86, prende la chiave pubblica di Ugo che
è (n, e) = (187, 7) e calcola t = 867 mod 187. Per eseguire questo calcolo
conviene usare le proprietà del calcolo modulare esponenziale. Poichè
7 = 1 + 2 + 22 = 1 + 2 + 4, si ha
867 mod 187 = (861 mod 187) · (862 mod 187) · (864 mod 187)
e poichè 862 = 7396 ≡ 103 mod 187 e 864 = 54700816 ≡ 137 mod 187,
si ha
867 = 86 · 103 · 137 = 1213546 ≡ 103 mod 187.
Il messaggio che Carla invia e Ugo riceve è t = 103.
(6) Una eventuale spia, vedendo il messaggio t = 103 non riesce a capire cosa
è stato inviato (nel codice ASCII t = 103 corrisponde alla virgola). Ugo,
invece, avendo la chiave privata, riesce a decifrarlo.
(7) Per decifrare il messaggio e ottenere m, Ugo deve solo calcolare la congruenza
td mod n
ossia
10323 mod 187.
Poichè 23 = 1 + 2 + 22 + 24 = 1 + 2 + 4 + 16, si deve calcolare
{(1031 mod187) · (1032 mod187) · (1034 mod187) · (10316 mod187)} mod 187
e poichè
1032 mod 187 = 137, 1034 mod 187 = 69, 10316 mod 187 = 103
si ha
{(103 · 137 · 69 · 103} mod 187, 100286877 mod 187 = 86
e dunque Ugo decifra che il messaggio inviatogli da Carla è m = 86 che
nel codice ASCII è la lettera V.
4. IL SISTEMA RSA
116
Esempio 9.4.3. Carla e Francesco utilizzano il sistema RSA per scambiarsi un
messaggio. Francesco ha ricevuto da Carla questo messaggio: qual è il corso che
ti è piaciuto di più ?
Francesco vuole rispondere con il seguente messaggio
algebra
Per inviare la risposta a Carla, Francesco dovrà procedere come segue.
(1) Trasforma ogni lettera del messaggio in un intero in base all’equivalenza
numerica a due cifre di cui alla tabella sotto riportata (la corrispondenza
lettera-numero assegna ad ogni lettera un numero di due cifre ).
Tabella - Equivalenza lettere-numeri a due cifre o binaria
a → 00 = 00000 j → 09 = 01001 s → 18 = 10010
b → 01 = 00001 k → 10 = 01010 t → 19 = 10011
c → 02 = 00010
l → 11 = 01011 u → 20 = 10100
d → 03 = 00011 m → 12 = 01100 v → 21 = 10101
e → 04 = 00100 n → 13 = 01101 w → 22 = 10110
f → 05 = 00101 o → 14 = 01110 x → 23 = 10111
g → 06 = 00110 p → 15 = 01111 y → 24 = 11000
h → 07 = 00111 q → 16 = 10000 z → 25 = 11001
i → 08 = 01000 r → 17 = 10001
La sequenza di numeri corrispondenti al messaggio algebra è
00 11 06 04 01 17 00
(2) Guarda l’elenco delle chiavi pubbliche e trova
Chiave pubblica di Carla (nC , eC ) = (1003, 3).
(3) Ora Francesco suddivide il messaggio da inviare in messaggi unitari mi in
modo che l’intero associato ad ogni messaggio unitario sia minore di nC =
1003 e relativamente primo con 1003. Osserva che dividendo il messaggio
algebra in blocchi di due lettere (ossia digrafi) nel modo seguente
al ge br ax,
i numeri corrispondenti ai singoli messaggi unitari sono
0011
0604
0117
0023,
ossia, rispettivamente, i numeri m1 = 11, m2 = 604, m3 = 117, m4 = 23
che sono tutti minori di 1003 e relativamente primi con 1003. Per trovare
il MCD tra questi numeri e 1003, Francesco utilizzerà l’algoritmo euclideo
delle divisioni successive perchè non conosce la fattorizzazione di nC in
fattori primi. Si noti che Francesco ha dovuto aggiungere al messaggio
unitario finale la lettera x, in modo da farlo diventare un digrafo. Se
avesse pensato di dividere il messaggio in blocchi di tre lettere anzichè di
4. IL SISTEMA RSA
117
due, ci sarebbero dei messaggi unitari mi cui corrispondono degli interi
maggiori di nC :
alg → m1 = 606 < 1003,
ebr → m2 = 40117 > 1003,
axx → m3 = 2323 > 1003,
e pertanto non varrebbe M CD(mi , nC ) = 1 che è una condizione che
semplifica la procedura.
Dunque si considera la suddivisione del messaggio algebra in blocchi di
due lettere e pertanto i messaggi unitari in chiaro saranno rappresentati
dai seguenti numeri:
m1 = 11,
m2 = 604,
m3 = 117,
m4 = 23.
(4) Ora inizia l’operazione di cifratura vera e propria per l’invio del messaggio
a Carla in modo tale che quest’ultima lo possa decifrare e sia l’unica a
poterlo fare in un tempo ragionevole. Per cifrare il messaggio da spedire
a Carla, Francesco eleva ogni mi alla potenza eC . Il messaggio cifrato
che Francesco invia sarà dunque rappresentato dai seguenti numeri ti , i =
1, 2, 3, 4.
t1 = me1C mod nC = 113 mod 1003 = 328,
t2 = me2C mod nC = 6043 mod 1003 = 797,
t3 = me3C mod nC = 1173 mod 1003 = 825,
t4 = me4C mod nC = 233 mod 1003 = 131.
Ora Francesco ha terminato la sua operazione e invia a Carla il messaggio
cifrato costituito dai messaggi unitari
t1 = 328,
t2 = 797,
t3 = 825,
t4 = 131,
(5) Carla ha ricevuto il messaggio e deve procedere alla decifratura, cioè per
ogni ti deve scoprire il messaggio originario mi sapendo che
ti = mei C mod nC .
Carla, e solo lei, ha la chiave segreta dC che, ricordiamo, soddisfa alle
proprietà
• 1 ≤ dC < φ(nC ) = (p − 1)(q − 1),
• dC è soluzione della congruenza eC dC ≡ 1 (modφ(nC )).
Inoltre, la congruenza soprascritta ha un’unica soluzione perchè
M CD(eC , φ(nC )) = 1. Nel nostro caso la soluzione, chiave segreta di
Carla, è
dC = 619
infatti nC = 1003 = 17 · 59, φ(1003) = 16 · 58 = 928, e pertanto la
soluzione della congruenza 3x ≡ 1 mod 928, è dC = 619.
(6) Per decifrare, Carla eleva ogni ti a dC = 619, cioè calcola
328619 ,
797619 ,
825619 ,
131619 .
4. IL SISTEMA RSA
118
L’esponente 619 è grande allora per il calcolo Carla scrive 619 in base 2:
619 = (1001101011)2 = 512 + 64 + 32 + 8 + 2 + 1.
Ne segue che, per ogni i = 1, 2, 3, 4, si ha
32
8
2
1
t619
= t512
· t64
i
i
i · ti · ti · ti · ti .
Per i = 1 le potenze si calcolano facilmente utilizzando la seguente tabella
relativa a t1 = 328 :
k
1
2
22
23
24
25
26
27
28
29
C1k mod 1003
328
3282 mod 1003 = 263
=4
2632 mod 1003 = 965
=8
9652 mod 1003 = 441
= 16 4412 mod 1003 = 902
= 32 9022 mod 1003 = 171
= 64 1712 mod 1003 = 154
= 128 1542 mod 1003 = 647
= 256 6472 mod 1003 = 358
= 512 3582 mod 1003 = 783
Dai calcoli riportati nella tabella, si ottiene
328619 = 328512 · 32864 · 32832 · 3288 · 3282 · 3281 ≡
≡ 783 · 154 · 171 · 441 · 263 · 328 ≡ 11 mod 1003.
Si noti che, elevando t1 = 328 all’esponente dC = 619, si ottiene il numero
11 = m1 , cioè il numero corrispondente al messaggio originario. Carla procede allo stesso modo con gli altri tre blocchi del messaggio e, in
definitiva, ottiene
328619 mod 1003 = 11,
825619 mod 1003 = 117,
797619 mod 1003 = 604,
131619 mod 1003 = 23.
Questi numeri vanno pensati a quattro cifre, ossia
0011,
0604,
0117,
0023,
e corrispondono ai quattro blocchi di messaggio originali che erano dei
digrafi e pertanto Carla deve dividere ciascuno in due parti e ciascuna delle
due parti rappresenta una lettera. Utilizzando la tabella dell’equivalenza
lettere-numeri riportata al punto (1), Carla ottiene
00 11 06 04 01 17 00 23
a l g e b r a x
e quindi riesce a capire quale è il corso che è piaciuto di più a Francesco.
4. IL SISTEMA RSA
119
Nota 9.4.4. Abbiamo detto che il messaggio unitario deve essere minore di
n. Dimostriamo con un esempio che la condizione è necessaria. Consideriamo il
messaggio
no
e supponiamo di inviarlo a Francesco che ha come chiave pubblica la coppia (nF =
77, eF = 13). Consideriamo l’intera parola no come messaggio unitario (digrafo):
(1) trasformiamo il messaggio in un numero associando ad ogni lettera il suo
equivalente numerico (vedi Tabella al punto (1) dell’esempio 9.4.3). Il
numero associato risulta essere
1314
che è maggiore di nF = 77;
(2) per cifrare eleviamo 1314 alla potenza eF = 13. Si ottiene
131413 ≡ 26 mod 77 ,
t = 26.
(3) Francesco riceve il messaggio
26
Per decifrare questo messaggio Francesco utilizza la sua chiave segreta che
è dF = 37 ( soluzione della congruenza 13 · dF ≡ 1 mod φ(77), cioè 13 ·
dF ≡ 1 mod 60).
Elevando 26 alla potenza 37 e calcolando mod 77, si ottiene 5 che
Francesco interpreta come
f
e quindi non ritrova il messaggio che gli è stato inviato (vedi tabella
equivalenza lettere-numeri riportata nell’esempio 9.4.3).
Dunque è necessario che il messaggio unitario sia minore di nF , altrimenti è impossibile decifrare il messaggio.
Nota 9.4.5. Nell’esempio 9.4.3 abbiamo visto che per inviare a Carla il messaggio algebra, Francesco lo ha suddiviso in digrafi. Per fare ciò ha dovuto procedere
per tentativi, verificando che i numeri corrispondenti ai singoli digrafi fossero tutti
minori di nC e primi con esso.
C’è però un metodo migliore per scegliere in che modo suddividere il messaggio. Non conviene dividere il messaggio originario algebra, ma conviene dividere
il messaggio numerico ottenuto associando un numero a due cifre ad ogni lettera.
Anzi, c’è un modo naturale di suddividerlo, vediamo quale.
Dopo che si è trasformato il messaggio in una serie di numeri, ciascuno a due cifre, consideriamo il numero (detto messaggio numerico) costituito dalla successione
di tutte le cifre. Suddividiamo questo numero in blocchi di k cifre dove
k = numero di cifre di nC diminuito di una unità .
4. IL SISTEMA RSA
120
In questo modo, senza dover esaminare il messaggio, il singolo messaggio numerico
unitario è automaticamente minore di nC . Non solo, questo modo di procedere è
noto a tutti perchè tutti conoscono nC e sanno che il mittente del messaggio divide
il messaggio numerico in blocchi ottenuti in questo modo.
Vediamo un esempio.
Esempio 9.4.6. Supponiamo che Francesco debba inviare a Carla il messaggio
vieni qui
(1) Francesco trasforma il messaggio, trascurando la spaziatura, nella sequenza di numeri di due cifre (Tabella dell’esempio 9.4.3)
21 08 04 13 08 16 20 08
che scriveremo come
2108041308162008.
Ciò non crea ambiguità perchè sappiamo che ogni numero associato ad una
lettera del messaggio originario è costituito da due cifre. Quello ottenuto
è il messaggio numerico.
(2) Come già scritto nell’esempio 9.4.3, le chiavi pubblica e privata di Carla sono, rispettivamente, (nC = 1003, eC = 3) e dC = 619. Osservato
che il numero nC = 1003 ha quattro cifre, Francesco spezza il messaggio
numerico in gruppi di 4 − 1 = 3 cifre, ossia in trigrafi, come segue:
210 804 130 816 200 823.
Si noti che Francesco ha aggiunto 23, corrispondente alla lettera x, in
modo che tutti i messaggi numerici unitari siano costituiti da tre cifre.
In questo modo ha spezzato il messaggio numerico in messaggi numerici
unitari che sicuramente sono minori di nC = 1003. Si osservi che questa
suddivisione non è una suddivisione del messaggio originario vieni qui
perchè i blocchi numerici unitari di tre cifre non corrispondono a nessun
gruppo di lettere. Occorre inoltre controllare che ogni mi sia relativamente
primo con 1003. E’ facile verificare che l’unica eccezione è quella di 816.
Ciò però non ha importanza perchè vale il Teorema 9.4.1 che ci assicura
che la condizione M CD(mi , 1003) è solo di utilità ma non strettamente
necessaria. In definitiva i singoli messaggi numerici unitari sono
m1 = 210, m2 = 804, m3 = 130, m4 = 816, m5 = 200, m6 = 823.
Si noti che le operazioni fin qui fatte non corrispondono a nessun tipo di
cifratura, infatti la trasformazione di un messaggio in una successione di
numeri è standard così come la ripartizione dello stesso in gruppi di tre
cifre, che dipende dal valore di nC che è pubblico.
5. LA FIRMA ELETTRONICA, AUTENTICAZIONE CON IL SISTEMA RSA
121
(3) Si cifrano i messaggi numerici unitari e si ottiene:
t1 = me1C mod nC , 2103 mod 1003 = 301,
t1 = 301,
t2 = me2C mod nC , 8043 mod 1003 = 975,
t2 = 975,
eC
3
t3 = m3 mod nC , 130 mod 1003 = 430,
t3 = 430,
t4 = me4C mod nC , 8163 mod 1003 = 357,
t4 = 357,
eC
3
t5 = m5 mod nC , 200 mod 1003 = 72,
t5 = 72,
t6 = me6C mod nC , 8233 mod 1003 = 445,
t6 = 445.
(4) Carla riceve la seguente successione di messaggi unitari:
t1 = 301, t2 = 975, t3 = 430, t4 = 357, t5 = 72, t6 = 445.
Per decifrare, Carla eleva ogni ti alla sua chiave segreta dC = 619, ossia
calcola
301619 , 975619 , 430619 , 357619 , 72619 , 445619
e trova
301619 mod 1003 = 210 = m1 ,
430619 mod 1003 = 130 = m3 ,
72619 mod 1003 = 200 = m5 ,
In definitiva, Carla ottiene la sequenza di
ora raggruppa a due a due ottenendo
975619 mod 1003 = 804 = m2 ,
357619 mod 1003 = 816 = m4 ,
445619 mod 1003 = 823 = m6 .
cifre 210804130816200823 che
21, 08, 04, 13, 08, 16, 20, 08, 23
e quindi Carla riesce a leggere il messaggio vieni quix che capisce significa
vieni qui.
5. La firma elettronica, autenticazione con il sistema RSA
Il sistema RSA consente di risolvere il problema della autenticazione elettronica
di una firma. Ad esempio, se Francesco riceve un messaggio da una persona che
si firma Carla, deve essere certo che sia stata proprio Carla ad inviarglielo. Se
(nC , eC ) e dC sono la chiave, rispettivamente, pubblica e privata di Carla, per
risolvere questo problema si procede come segue.
(1) Carla scrive il messaggio m1 contenente la sua firma F e, perchè la firma
possa essere autenticata, aggiunge il messaggio m2 con m2 = F dC ( mod nC ),
(ricordiamo che solo lei conosce dC ). Poi, con le solite modalità di cifratura, invia a Francesco il messaggio cifrato.
(2) Francesco, con le solite modalità, decifra il messaggio e per verificare
l’autenticità della firma calcola me2C (mod nC ).
6. SICUREZZA DEL SISTEMA RSA
122
(3) Se me2C (mod nC ) = F, allora la firma è autentica
me2C ≡ (F dC )eC = F dC eC ≡ F( mod nC ).
La firma è quella di Carla perchè solo lei conosce la propria chiave privata
che è la sola compatibile con eC e nC utilizzati da Francesco.
Si noti che per l’autentica della firma si usano solo le chiavi relative a colui che
spedisce il messaggio (ovviamente per cifrare e decifrare il messaggio occorrono, al
solito, anche le chiavi del destinatario).
Esempio 9.5.1. Carla invia un documento firmato a Francesco.
• Chiave pubblica di Carla : (nC = 77, eC = 13),
• Chiave privata di Carla : dC = 37.
(Poichè 77 = 11·7, la chiave privata di Carla è dC = 37 perchè 37·13 ≡ 1(mod 60),
dove 60 = φ(77).)
Supponiamo che la firma di Carla sia F = 5.
(1) Nell’inviare il messaggio a Francesco, Carla ha autenticato la sua firma
aggiungendo il messaggio
47 (ottenuto calcolando 537 mod 77).
(2) Francesco verifica l’autenticità della firma calcolando
4713 mod 77 (= 5).
(3) La firma è autentica perchè Francesco ottiene 5 che è la firma di Carla .
6. Sicurezza del sistema RSA
La sicurezza del sistema RSA sta nel fatto che non esiste a tutt’oggi un algoritmo efficiente per fattorizzare numeri grandi. Se A invia a B un messaggio m,
un estraneo che tentasse di decifrarlo abusivamente dovrebbe trovare la fattorizzazione della chiave pubblica nB di B. Nel caso che nB sia prodotto di due numeri
primi ciascuno con 100 e più cifre, anche utilizzando i più sofisticati algoritmi e
i calcolatori più veloci, occorrerebbero anni di calcolo per fattorizzare nB e pertanto si ritiene che la fattorizzazione di nB sia impossibile per un estraneo non
autorizzato. Questo però è vero in generale, ma non sempre, come ha mostrato il
seguente episodio.
Nell’agosto 1977, dalle colonne della pagina Mathematical Games di M. Gardner, i tre inventori del sistema RSA sfidarono i lettori della rivista Scientific American a decifrare un messaggio corrispondente ad un numero a 129 cifre, operazione
6. SICUREZZA DEL SISTEMA RSA
123
che secondo loro avrebbe richiesto miliardi di anni. Offrivano 100 dollari di premio a chi avesse trovato la soluzione. Per decifrare il loro messaggio originale era
necessario fattorizzare il numero
n = 11438162575788886766923577997614661201021829672124236256256184293
5706935245733897830597123563958705058989075147599290026879543541,
che era stato pubblicato assieme al numero e = 9007, ossia (n, e) era la chiave
pubblica di Rivest, Shamir e Adleman. Per garantire che il messaggio proveniva
proprio dai tre studiosi, fu aggiunta la seguente autenticazione della loro firma
ottenuta usando la chiave segreta dell’algoritmo
1671786115038084424601527138916839824543690103235831121783503844
6929062655448792237114490509578608655662496577974840004057020373.
Elevando questo numero alla potenza 9007 e riducendo modulo n si otteneva il
numero
0609181920001915122205180023091419001
5140500082114041805040004151212011819
corrispondente alla frase
First solver wins one hundred dollars,
che era la garanzia che il messaggio proveniva proprio da Rivest, Shamir, Adleman.
Diciassette anni dopo il matematico Arjen K. Lenstra insieme ad un gruppo
di qualche centinaio di persone, in soli otto mesi riuscì a trovare la soluzione. La
tecnica usata per affrontare il problema è quella che prende il nome di crivello
quadratico polinomiale multiplo, una tecnica che permette di suddividere il lavoro
in tante parti più piccole. Per organizzare questo lavoro, Lenstra si servì di centinaia di collaboratori in tutto il mondo impegnando migliaia di calcolatori, il tutto
coordinato via internet. Ognuno di questi collaboratori mandò a Lenstra i risultati
della parte di lavoro da loro svolta. Unendo il tutto, con un supercalcolatore in
due giorni furono trovati i due fattori, uno di 64 cifre e uno di 65 cifre. Questo
permise a Lenstra di decifrare il messaggio di Rivest, Shamir e Adleman.
Il messaggio diceva
the magic words are sqeamish ossifrage.
A detta degli stessi autori, si tratta di parole senza senso, ma essi non si aspettavano che le parole potessero mai essere decifrate. Quella che sembrava una sfida
impossibile, dopo 17 anni si era invece rivelata possibile. Si può allora concludere
che la crittografia è ancora una scienza sperimentale. Un sistema ritenuto sicuro
oggi può non esserlo domani!