Codici correttori

Luca Giuzzi

Codici correttori

Un'introduzione

~ Springer

LUCA GruZZI

Dipartimento di Matematica Politecnico di Bari - Bari

ISBN lO 88-470-0539-6 Springer Milan Berlin Heidelberg New York

ISBN 13 978-88-470-0539-6 Springer Milan Berlin Heidelberg New York

Springer-Verlag fa parte di Springer Science+ Business Media

springer.com

© Springer-Verlag Italia, Milano 2006

Quest'opera è protetta dalla legge sul diritto d'autore. Tutti i diritti, in particolare quelli relativi alla tra­duzione, alla ristampa, all'uso di figure e tabelle, alla citazione orale, alla trasmissione radiofonica o te­levisiva, alla riproduzione su microfilm o in database, alla diversa riproduzione in qualsiasi altra forma (stampa o elettronica) rimangono riservati anche nel caso di utilizzo parziale. Una riproduzione di que­st'opera, oppure di parte di questa, è anche nel caso specifico solo ammessa nei limiti stabiliti dalla legge sul diritto d'autore, ed è soggetta all'autorizzazione dell'Editore. La violazione delle norme comporta sanzioni previste dalla legge.

L'utilizzo di denominazioni generiche, nomi commerciali, marchi registrati, ecc., in quest'opera, anche in assenza di particolare indicazione, non consente di considerare tali denominazioni o marchi liberamente utilizzabili da chiunque ai sensi della legge sul marchio.

Impianti forniti dall'autore Progetto grafico della copertina: Simona Colombo Stampa: Arti Grafiche Nidasio, Assago (Mi) Stampato in Italia

Indice

Prefazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. XI

Introduzione ..... . .... . .......... . .... . .......... . .... . ........... XIII

Parte I Teoria generale

1 Teoria della comunicazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 3 1.1 Sistemi di comunicazione .................................... 3 1.2 Il caso privo di rumore ...................................... 4 1.3 Il caso con rumore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 8 1.4 Modelli di canale ........................................... lO 1.5 Conclusioni. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 16

2 Protocolli e codici. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 17 2.1 Comunicazione a pacchetto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 18 2.2 Alfabeti. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 20 2.3 Codici a lunghezza variabile. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 25 2.4 Adattamento dei codici alla sorgente .......................... 30 Esercizi ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 33

3 Codici a blocchi. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 35 3.1 Blocchi di informazione. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 35 3.2 Metrica di Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 36 3.3 Algoritmi di codifica e decodifica. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 37 3.4 Efficienza di un codice. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 40 3.5 Distanza minima. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 41 3.6 Limitazioni. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 45 3.7 Codici equivalenti. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 48 Esercizi ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 51

VI Indice

Parte II Codici lineari

4 Codici lineari .................................................. 55 4.1 Generalità. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 56 4.2 Codici lineari astratti. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 57 4.3 Proprietà dei codici lineari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 59 4.4 Matrice generatrice di un codice lineare. . . . . . . . . . . . . . . . . . . . . . .. 61 4.5 Equivalenza e isomorfismo ................................... 63 4.6 Ortogonalità e codice duale .... . .......... . .... . .......... . .. 72 4.7 Controllo di parità. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 77 4.8 Enumeratori dei pesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 78 4.9 Codici di Hamming ......................................... 83 4.10 Decodifica del codice di Hamming binario. . . . . . . . . . . . . . . . . . . . .. 85 4.11 Decodifica mediante matrice standard . . . . . . . . . . . . . . . . . . . . . . . .. 86 4.12 Decodifica assistita con sindrome ............................. 89 4.13 Codici lineari e canali di comunicazione. . . . . . . . . . . . . . . . . . . . . . .. 93 4.14 Alcune limitazioni sui codici lineari ........................... 96 Esercizi ...................................... . .... . .......... . .. 101

5 Codici ciclici ................................................... 103 5.1 Sottospazi ciclici ............................................ 103 5.2 Rappresentazione mediante polinomi .......................... 104 5.3 Polinomio generatore di un codice ciclico ....................... 107 5.4 Matrice generatrice di un codice ciclico ........................ 109 5.5 Polinomio di controllo di parità ............................... 110 5.6 Codifica dei codici ciclici ..................................... 113 5.7 Decodifica dei codici ciclici ..... . .......... . .... . ............. 115 Esercizi ......................................................... 122

6 Radici e idempotente di un codice ciclico ....................... 125 6.1 Radici di un codice ciclico .................................... 125 6.2 Idempotente di un codice ciclico .............................. 128 6.3 Classi ciclotomiche e codici ciclici minimali ..................... 130 6.4 Insiemi di definizione ........................................ 133 6.5 Descrizione dei codici ciclici mediante traccia ................... 137 Esercizi ........................................... . .......... . .. 138

7 Errori concentrati o burst ...................................... 139 7.1 Descrizione dei burst di errore ................................ 140 7.2 Limitazioni ................................................ 142 7.3 Campi di ordine non primo .................................. 144 7.4 Codici ciclici per errori burst ................................. 145 7.5 Codici fortemente correttori e codici di Fire .................... 150

Indice VII

Esercizi ......................................................... 153

8 Trasfonnata di Fourier e codici BCH ........................... 155 8.1 Trasformata di Fourier e polinomio di Mattson-Solomon ......... 155 8.2 Costruzione BCH ........................................... 158 8.3 Descrizione compressa dell'errore ............................. 161 8.4 L'equazione chiave .......................................... 162 8.5 Polinomio sindrome per codici BCH ........................... 165 8.6 L'algoritmo Euclideo Esteso .................................. 167 8.7 Decodifica dei codici BCH ................................... 172 Esercizi ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

9 Codici di Reed-Solornon .......... . .......... . .... . ............ 177 9.1 Costruzione di Reed-Solomon ................................ 177 9.2 Codifica e decodifica dei codici di Reed-Solomon ................ 180 9.3 Il problema dalla correzione .................................. 180 9.4 Algoritmo di Welch-Berlekamp ............................... 182 9.5 Codici di Reed-Solomon come BCH ........................... 184 9.6 Decodifica a lista ........................................... 189 9.7 Decodifica a lista dei codici di Reed-Solomon ................... 190 9.8 Applicazioni dei codici di Reed-Solomon ....................... 195 Esercizi ......................................................... 196

lO Cancellature o erasures ........................................ 199 10.1 Il canale q-ario con cancellatura .............................. 199 10.2 Decodifica di cancellature .................................... 200 10.3 Codici di Reed-Solomon e canali con cancellatura ............... 202 Esercizi ......................................................... 207

Il Disegni e codici ................................................ 209 11.1 Strutture di incidenza ..... . .... . .......... . .... . ............ 209 11.2 Disegni .................................................... 211 11.3 Matrici di incidenza ......................................... 215 11.4 Piani proiettivi ............................................. 219 11.5 Codici da disegni ........................................... 220 11.6 Piani proiettivi e codici ...................................... 223 Esercizi ......................................................... 226

12 Codici di Golay ................................................ 227 12.1 Codice di Golay binario esteso e disegni di Mathieu ............. 227 12.2 Unicità del (24,2 12 , 8)-codice binario .......................... 231 12.3 Codice binario di Golay ...................................... 234 12.4 L'esacodice e la codifica del codice di Golay .................... 237 12.5 Decodifica a logica di maggioranza ............................ 239 12.6 Codice ternario di Golay ..................................... 239

VIII Indice

Esercizi ......................................................... 242

13 Codici di Reed-Miiller ......................................... 243 13.1 Codici di Reed-Muller q-ari .... . .......... . .... . ............. 243 13.2 Il caso binario .............................................. 245 13.3 Codici del primo ordine ...................................... 247 13.4 Codice ortogonale ........................................... 248 13.5 Geometria e codici di Reed-Muller ............................ 251 Esercizi ......................................................... 252

14 Modifica e combinazione di codici .............................. 253 14.1 Accorciamento .............................................. 253 14.2 Estensione ......... . .... . .... . .......... . .... . ............. 255 14.3 Allungamento .............................................. 256 14.4 Punzonatura ............................................... 257 14.5 Aumento e epurazione ....................................... 258 14.6 Condivisione temporale ...................................... 258 14.7 Somma .................................................... 260 14.8 Codifica seriale ............................................. 260 14.9 Costruzione lulu + vi ........................................ 261 14.10 Codici prodotto ............................................ 262 14.11 Intrecciamento ............................................. 265 Esercizi ......................................................... 266

15 Limitazioni asintotiche ......................................... 267 15.1 Famiglie di codici ........................................... 267 15.2 Limitazioni universali sui codici ............................... 268 15.3 Insiemi di Wozencraft ....................................... 277

Parte III Argomenti avanzati

16 Codici Algebrico-Geometrici ................................... 283 16.1 Codici di valutazione ........................................ 283 16.2 Costruzione dei codici geometrici ............................. 285 16.3 Stime sui codici geometrici ................................... 288 16.4 Codice Hermitiano .......................................... 290 16.5 Sequenze di codici asintoticamente buone ...................... 292 16.6 Decodifica dei codici di Goppa ................................ 295

17 Codici LDPC e grafi di Tanner ... . .......... . .... . ............. 299 17.1 Matrici sparse e grafi ........................................ 299 17.2 Grafi di Tanner ............................................. 300 17.3 Codici LDPC ............................................... 302 17.4 Grafi espansori ............................................. 304

Indice IX

17.5 Decodifica mediante scambio sequenziale ....................... 305

18 Codici convoluzionali . .......................................... 309 18.1 Motivazione ................... . .......... . .... . ............ 309 18.2 Codificatori convoluzionali ................................... 310 18.3 Funzioni generatrici ......................................... 313 18.4 Matrici generatrici .......................................... 315 18.5 Traliccio di Wolf e codici lineari .............................. 317 18.6 Decodifica di Viterbi per codici lineari ......................... 320 18.7 Tralicci per codici convoluzionali .............................. 323

Parte IV Appendici

A Call1pi finiti . ................................................... 327 A.1 Anelli ..................................................... 327 A.2 Campi ..................................................... 330 A.3 Anelli di polinomi ........................................... 332 A.4 Estensioni di campo ......................................... 336 A.5 Struttura dei campi finiti .................................... 340 A.6 Polinomi irriducibili su campi finiti ............................ 343 A.7 Automorfismi di un campo finito .............................. 345 A.8 Traccia e norma ............................................ 346 A.9 Radici dell'unità e polinomi ciclotomici ........................ 348

B GeoIlletria proiettiva e Curve algebriche ....................... 351 B.1 Spazi affini e proiettivi ...................................... 351 B.2 Insiemi algebrici e varietà .................................... 353 B.3 Funzioni razionali ........................................... 354 B.4 Curve ..................................................... 355 B.5 Divisori .................................................... 356 B.6 Il genere e il teorema di Riemann-Roch ........................ 357

Soluzioni degli esercizi . ............................................ 359 Capitolo 2 ....................................................... 359 Capitolo 3 ....................................................... 361 Capitolo 4 ....................................................... 363 Capitolo 5 ....................................................... 364 Capitolo 6 ....................................................... 365 Capitolo 7 ....................................................... 367 Capitolo 8 ....................................................... 368 Capitolo 9 ....................................................... 371 Capitolo lO .... . .... . .......... . .... . .......... . .... . ............ 374 Capitolo 11 ...................................................... 379

X Indice

Capitolo 12 ...................................................... 381 Capitolo 13 ...................................................... 383 Capitolo 14 ...................................................... 384

Bibliografia . ....................................................... 387

Elenco dei simboli ................................................. 393

Indice analitico .................................................... 397

Prefazione

o hatejul errar, melancholy's child! Why dost thou show, to the apt thoughts oj men, the things that are not?

W. SHAKESPEARE, JULIUS CAESAR

L'obiettivo di un sistema di comunicazione è quello di consentire di trasferire in­formazione da un punto in un altro separato nello spazio e nel tempo. Il rischio essenziale in questo contesto è quello che il messaggio che deve essere trasmesso venga ad alterarsi. L'alterazione del messaggio può essere causata sia da ragioni intrinseche al meccanismo utilizzato per comunicare (deperimento del mezzo fisi­co, interferenze dovute a fenomeni naturali) sia da difetti nell'apparato utilizzato. I linguaggi naturali presentano in modo naturale una resistenza a "piccoli errori" in quanto tendono a codificare quanto viene trasmesso in modo ridondante. Ad esempio, nella frase "Sì, sicuramente" la cancellazione o alterazione di una sola lettera non compromette l'intelligibilità della natura della risposta. In un sistema digitale, in cui per motivi economici e pratici si ricerca la massima concisione, il medesimo messaggio può essere codificato con un semplice 1, mentre la risposta negativa corrisponde ad uno O. Il problema nasce nel momento in cui il valore del bit viene ad essere invertito a causa di un errore di trasmissione: il significato di quanto ricevuto viene ad essere esattamente l'opposto di quanto originariamente desiderato e non c'è modo di accorgersi dell'inconveniente. La teoria dei codici si ripropone di fornire dei metodi per evitare che questo genere di eventualità possa verificarsi.

Consideriamo ora un esempio leggermente più complicato del precedente: sup­poniamo che si debbano trasmettere indicazioni su di un percorso stradale da seguire e che ad ogni svincolo sia possibile muoversi in esattamente 4 direzioni: Nord, Sud, Est ed Ovest. Una codifica binaria naturale per fornire indicazioni in questo caso è quella descritta in Figura 1. Osserviamo, in particolare, che due dire-

N

O E S

00 lO 01

11

Fig. 1. Codifica di 4 direzioni mediante 2 bit

XII Prefazione

zioni "contigue" (ad esempio N ed E) sono rappresentate da simboli che differiscono in una sola posizione, mentre direzioni "opposte" (ad esempio E ed O) differiscono in due posizioni. D'altro canto, se in fase di ricezione si verificasse un unico errore, la parola 00 potrebbe risultare trasformata in 01 oppure lO e non vi sarebbe alcun modo per il destinatario del messaggio di accorgersi del problema. Un modo per ovviare a questo inconveniente è quello di ritrasmettere più volte (almeno tre) il medesimo messaggio e, per ogni posizione, far selezionare la direzione che "è stata ricevuta più volte".

Una soluzione diversa (e più efficace) è di codificare le medesime 4 direzioni come in Figura 2. In questo caso ogni due parole differiscono in almeno 3 posizio-

N

O E S

001000 I lO [Iill 01 [§ID

ll[Iill

Fig. 2. Codifica con ridondanza

ni. Supponiamo ora che venga trasmesso 00000 e che vi sia un unico errore, per cui quanto ricevuto è 00010. Immediatamente, dalla sola conoscenza delle parole "lecite", è possibile rendersi conto che si è verificata un'interferenza. Si dice che il codice identifica un errore. D'altro canto 00010 può essere ottenuto da 00000 semplicemente modificando 1 bit, mentre per ottenerlo da una qualsiasi altra pa­rola è necessario supporre che almeno 2 posizioni siano state alterate. È dunque ragionevole correggere l'errore decodificando quanto ricevuto come la direzione N.

Lo studio di metodi per codificare messaggi in modo tale che sia possibi­le identificare (e correggere) eventuali errori di trasmissione, senza richiedere la ritrasmissione del tutto, è l'oggetto della teoria dei codici.

Introduzione

Whose liquor hath this virtuous praperty, To take fram thence all errar with his might, and make his eyeballs roll with wonted sight.

W. SHAKESPEARE, A MIDSUMMER N!GHT'S DREAM

Il presente testo è finalizzato a fornire un'introduzione generale alla teoria algebrica dei codici ed è destinato a studenti del terzo anno di un corso Laurea di primo livello in Matematica, Fisica o Ingegneria, oppure del primo/secondo anno di Laurea Specialistica. Il materiale indicato con il simbolo A è più specificamente orientato a studenti degli anni superiori.

Il piano dell'opera è il seguente.

1. Nei primi due capitoli si richiamano alcune nozioni di teoria matematica della comunicazione; tale teoria fornisce la giustificazione delle tecniche di correzione di errore che sono l'oggetto del resto del testo.

2. Nel Capitolo 3 si introducono le nozioni di codice a blocchi di correzione, codifica e decodifica di un messaggio, nonché di equivalenza fra codici.

3. I capitoli dal 4 al 15 costituiscono il cuore del lavoro: in essi vengono studiate numerose famiglie di codici lineari e si mostra il loro impiego e quali proprietà debbano sempre essere soddisfatte.

4. Il Capitolo 4 è finalizzato ad introdurre i codici lineari, visti come spazi vettoriali, e a presentarne le proprietà generali;

5. Oggetto dei capitoli 5 e 6 sono un tipo particolare di codici lineari: i codici ciclici. Tali codici si possono descrivere in modo estremamente conciso e si rivelano particolarmente utili per correggere alcune tipologie di errore, quali gli errori concentrati. Questa classe di errore è studiata nel dettaglio nel Capitolo 7.

6. Nel Capitolo 8 si definisce la costruzione BCH e si studiano i codici da essa derivati. Uno degli aspetti più importanti di tale costruzione è che consente di fissare a priori il numero di errori che un codice deve poter correggere.

7. I codici di Reed-Solomon, oggetto del Capitolo 9, costituiscono forse la più importante famiglia di codici lineari a blocchi: sono infatti implementati in svariati dispositivi di comunicazione digitale. Fra i motivi del loro successo vi è l'esistenza di eccellenti algoritmi di correzione specifici, ma anche la possibilità di utilizzarli per correggere errori di cui si conosce la posizione ma non l'entità.

XIV Introduzione

Metodologie per affrontare quest'ultimo problema sono introdotte nel Capitolo lO.

8. Nel Capitolo 11 si presenta come sia possibile costruire dei codici a partire da strutture di tipo geometrico-combinatorico; tali costruzioni sono utilizzate anche nel Capitolo 12 per costruire i codici sporadici di Golay e mostrare che sono perfetti.

9. I codici di Reed-Muller sono una possibile generalizzazione dei codici di Reed­Solomon; nel Capitolo 13 mostriamo come costruirli e, nel caso binario, ne deriviamo alcune proprietà.

lO. Non sempre è facile ottenere direttamente un codice che abbia i parametri richiesti per un ben definito problema pratico. Tecniche per determinare codici con il comportamento desiderato, a partire da codici altrimenti noti, sono presentate nel Capitolo 14.

11. Nel capitolo conclusivo di questa parte del libro, il 15, si presentano alcune limitazioni assolute al comportamento di un codice e si dimostra che, quan­tomeno a livello teorico, è sempre possibile costruire dei codici con il miglior comportamento possibile.

12. I capitoli della terza parte del volume (dal 16 al 18) sono destinati a fornire un'idea generale su alcune classi di codici che sono correntemente oggetto di intensa ricerca. Tali capitoli non vogliono essere esaustivi ma semplicemente stimolare il lettore interessato ad approfondire l'argomento. Le classi consi­derate sono quella dei codici Algebrico-Geometrici (Capitolo 16), dei codici LDPC (Capitolo 17) e quella dei codici convoluzionali (Capitolo 18).

13. Concludono il testo due appendici: una (Appendice A) sui campi finiti, l'altra sulle curve algebriche (Appendice B).

I capitoli dal 2 al 14 sono corredati di esercizi svolti. Nello svolgimento degli stessi si è cercato, ove opportuno, di mostrare come i problemi possano essere impostati utilizzando il sistema di computer algebra GAP [36]. Tale sistema è liberamente disponibile in rete (si veda la bibliografia per l'indirizzo) ed è finalizzato allo studio di strutture algebriche finite.

Un sentito ringraziamento va alla Professoressa Silvia Pellegrini, che ha seguito la genesi e lo sviluppo di quest'opera con preziosissimi consigli e incoraggiamenti.

Luca Giuzzi Brescia e Bari, 13 settembre 2006

Introduzione

Whose liquor hath this virtuous praperty, To take fram thence all errar with his might, and make his eyeballs roll with wonted sight.

W. SHAKESPEARE, A MIDSUMMER N!GHT'S DREAM

Il presente testo è finalizzato a fornire un'introduzione generale alla teoria algebrica dei codici ed è destinato a studenti del terzo anno di un corso Laurea di primo livello in Matematica, Fisica o Ingegneria, oppure del primo/secondo anno di Laurea Specialistica. Il materiale indicato con il simbolo A è più specificamente orientato a studenti degli anni superiori.

Il piano dell'opera è il seguente.

1. Nei primi due capitoli si richiamano alcune nozioni di teoria matematica della comunicazione; tale teoria fornisce la giustificazione delle tecniche di correzione di errore che sono l'oggetto del resto del testo.

2. Nel Capitolo 3 si introducono le nozioni di codice a blocchi di correzione, codifica e decodifica di un messaggio, nonché di equivalenza fra codici.

3. I capitoli dal 4 al 15 costituiscono il cuore del lavoro: in essi vengono studiate numerose famiglie di codici lineari e si mostra il loro impiego e quali proprietà debbano sempre essere soddisfatte.

4. Il Capitolo 4 è finalizzato ad introdurre i codici lineari, visti come spazi vettoriali, e a presentarne le proprietà generali;

5. Oggetto dei capitoli 5 e 6 sono un tipo particolare di codici lineari: i codici ciclici. Tali codici si possono descrivere in modo estremamente conciso e si rivelano particolarmente utili per correggere alcune tipologie di errore, quali gli errori concentrati. Questa classe di errore è studiata nel dettaglio nel Capitolo 7.

6. Nel Capitolo 8 si definisce la costruzione BCH e si studiano i codici da essa derivati. Uno degli aspetti più importanti di tale costruzione è che consente di fissare a priori il numero di errori che un codice deve poter correggere.

7. I codici di Reed-Solomon, oggetto del Capitolo 9, costituiscono forse la più importante famiglia di codici lineari a blocchi: sono infatti implementati in svariati dispositivi di comunicazione digitale. Fra i motivi del loro successo vi è l'esistenza di eccellenti algoritmi di correzione specifici, ma anche la possibilità di utilizzarli per correggere errori di cui si conosce la posizione ma non l'entità.

XVI Introduzione

Metodologie per affrontare quest'ultimo problema sono introdotte nel Capitolo lO.

8. Nel Capitolo 11 si presenta come sia possibile costruire dei codici a partire da strutture di tipo geometrico-combinatorico; tali costruzioni sono utilizzate anche nel Capitolo 12 per costruire i codici sporadici di Golay e mostrare che sono perfetti.

9. I codici di Reed-Muller sono una possibile generalizzazione dei codici di Reed­Solomon; nel Capitolo 13 mostriamo come costruirli e, nel caso binario, ne deriviamo alcune proprietà.

lO. Non sempre è facile ottenere direttamente un codice che abbia i parametri richiesti per un ben definito problema pratico. Tecniche per determinare codici con il comportamento desiderato, a partire da codici altrimenti noti, sono presentate nel Capitolo 14.

11. Nel capitolo conclusivo di questa parte del libro, il 15, si presentano alcune limitazioni assolute al comportamento di un codice e si dimostra che, quan­tomeno a livello teorico, è sempre possibile costruire dei codici con il miglior comportamento possibile.

12. I capitoli della terza parte del volume (dal 16 al 18) sono destinati a fornire un'idea generale su alcune classi di codici che sono correntemente oggetto di intensa ricerca. Tali capitoli non vogliono essere esaustivi ma semplicemente stimolare il lettore interessato ad approfondire l'argomento. Le classi consi­derate sono quella dei codici Algebrico-Geometrici (Capitolo 16), dei codici LDPC (Capitolo 17) e quella dei codici convoluzionali (Capitolo 18).

13. Concludono il testo due appendici: una (Appendice A) sui campi finiti, l'altra sulle curve algebriche (Appendice B).

I capitoli dal 2 al 14 sono corredati di esercizi svolti. Nello svolgimento degli stessi si è cercato, ove opportuno, di mostrare come i problemi possano essere impostati utilizzando il sistema di computer algebra GAP [36]. Tale sistema è liberamente disponibile in rete (si veda la bibliografia per l'indirizzo) ed è finalizzato allo studio di strutture algebriche finite.

Un sentito ringraziamento va alla Professoressa Silvia Pellegrini, che ha seguito la genesi e lo sviluppo di quest'opera con preziosissimi consigli e incoraggiamenti.

Luca Giuzzi Brescia e Bari, 7 settembre 2006