Codici Correttori

\lettrine{I}{l presente} testo \`e finalizzato a fornire un'introduzione generale alla teoria algebrica dei codici ed \`e 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 \danger\ \`e pi\`u specificamente orientato a studenti degli anni superiori. Il piano dell'opera \`e il seguente. \begin{enumerate} \item 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. \item Nel Capitolo \ref{chap:prelim} si introducono le nozioni di codice a blocchi di correzione, codifica e decodifica di un messaggio, nonch\'e di equivalenza fra codici. \item I capitoli dal \ref{chap:Lineari} al \ref{chap:limitazioni} costituiscono il cuore del lavoro: in essi vengono studiate numerose famiglie di codici lineari e si mostra il loro impiego e quali propriet\`a debbano sempre essere soddisfatte. \item Il Capitolo \ref{chap:Lineari} \`e finalizzato ad introdurre i codici lineari, visti come spazi vettoriali, e a presentarne le propriet\`a generali; \item Oggetto dei capitoli \ref{chap:ciclici} e \ref{chap:alciclici} 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 \`e studiata nel dettaglio nel Capitolo \ref{chap:Burst}. \item Nel Capitolo \ref{chap:BCH} si definisce la costruzione BCH e si studiano i codici da essa derivati. Uno degli aspetti pi\`u importanti di tale costruzione \`e che consente di fissare \emph{a priori} il numero di errori che un codice deve poter correggere. \item I codici di Reed--Solomon, oggetto del Capitolo \ref{chap:RS}, costituiscono forse la pi\`u importante famiglia di codici lineari a blocchi: sono infatti implementati in svariati dispositivi di comunicazione digitale. Fra i motivi del loro successo vi \`e l'esistenza di eccellenti algoritmi di correzione specifici, ma anche la possibilit\`a di utilizzarli per correggere errori di cui si conosce la posizione ma non l'entit\`a. Metodologie per affrontare quest'ultimo problema sono introdotte nel Capitolo \ref{chap:erasure}. \item Nel Capitolo \ref{chap:descodici} si presenta come sia possibile costruire dei codici a partire da strutture di tipo geometrico--combinatorico; tali costruzioni sono utilizzate anche nel Capitolo \ref{chap:golay} per costruire i codici sporadici di Golay e mostrare che sono perfetti. \item I codici di Reed--M\"uller sono una possibile generalizzazione dei codici di Reed--Solomon; nel Capitolo \ref{cha:geom} mostriamo come costruirli e, nel caso binario, ne deriviamo alcune propriet\`a. \item Non sempre \`e 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 \ref{cha:derivazione}. \item Nel capitolo conclusivo di questa parte del libro, il \ref{chap:limitazioni}, si presentano alcune limitazioni assolute al comportamento di un codice e si dimostra che, quantomeno a livello teorico, \`e sempre possibile costruire dei codici con il miglior comportamento possibile. \item I capitoli della terza parte del volume (dal \ref{chap:AGcodes} al \ref{chap:conv}) 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 considerate sono quella dei codici Algebrico--Geometrici (Capitolo \ref{chap:AGcodes}), dei codici LDPC (Capitolo \ref{chap:LDPC}) e quella dei codici convoluzionali (Capitolo \ref{chap:conv}). \item Concludono il testo due appendici: una (Appendice \ref{app:algebra}) sui campi finiti, l'altra sulle curve algebriche (Appendice \ref{app:curve}). \end{enumerate} I capitoli dal \ref{chap:Protocolli} al \ref{cha:derivazione} sono corredati di esercizi svolti. Nello svolgimento degli stessi si \`e cercato, ove opportuno, di mostrare come i problemi possano essere impostati utilizzando il sistema di \emph{computer algebra} GAP \cite{GAP4}. Tale sistema \`e liberamente disponibile in rete (si veda la bibliografia per l'indirizzo) ed \`e finalizzato allo studio di strutture algebriche finite. \par Un sentito ringraziamento va alla Professoressa Silvia Pellegrini, che ha seguito la genesi e lo sviluppo di quest'opera con preziosissimi consigli e incoraggiamenti.