Matematica Discreta II Lezione del giorno 28 novembre 2007 Teoria dei codici a rilevazione e correzione d’errore.

Matematica Discreta II

Lezione del giorno 28 novembre 2007

Teoria dei codici a rilevazione e correzione d’errore.

Supponiamo che un soggetto A (mittente) debba spedire un’informazione ad un soggetto B (destinatario) attraverso un canale di comunicazione.

Poiché i canali attuali sono per lo più digitali, è necessario effettuare prima una codifica dell’informazione: se supponiamo, per semplicità, che il canale di comunicazione sia un canale binario, saranno spediti attraverso tale canale dei blocchi di n cifre binarie a

a

……a

con a

=0,1 (supporremo anche che la lunghezza n di ogni blocco sia costante).

Ognuno di tali blocchi in termini combinatori è una parola di lunghezza n sull’alfabeto {0,1}.

Denoteremo con {0,1}

l’insieme di tutte le parole di lunghezza n sull’alfabeto {0,1}: è noto che la cardinalità di tale insieme è {0,1}

=2

.

Se l’informazione da spedire attraverso il canale è composta da elementi minimi di informazione (messaggi) contenuti in un insieme M (che possono per esempio essere singoli caratteri alfanumerici, oppure blocchi di alcuni di essi, o in generale qualunque elemento che contenga un’informazione di qualche natura), la codifica consiste nell’associare ad ogni elemento di M una parola di lunghezza n in {0,1}

: tale parola viene spedita lungo il canale, ricevuta da B, il quale effettua la decodifica, risalendo all’elemento di S che rappresenta l’informazione originaria (ovviamente per garantire l’univocità della decodifica, due elementi distinti di S devono avere codifiche diverse in {0,1}

).

In termini formali, dunque, la codifica è una funzione iniettiva f: M  {0,1}

, mentre la decodifica è una funzione g: {0,1}

 M tale che g(f(m))=m per ogni messaggio mM (quindi la composizione gf è la funzione identica di M).

L’iniettività della codifica f implica che M≤ 2

, dunque n≥log

M.

Il rapporto log

M/n è il cosiddetto rateo di informazione (information rate) della codifica: il suo valore massimo è 1 (e si ottiene per M=2

ossia quando la codifica f è biunivoca ed il numero dei messaggi possibili coincide con il numero delle possibile parole di {0,1}

). Se tale rapporto è <1 allora vi sono alcune parole di {0,1}

non utilizzate per la codifica dei messaggi e quindi è “minore”

la percentuale di informazione che viene codificata: ovviamente per ragioni di economicità delle risorse è opportuno che il rateo di informazione sia il più possibile vicino ad 1.

Fissato il numero M dei messaggi possibili, il maggior rateo di informazione si ha per la lunghezza n minima fra quelle tali che n≥log

M, quindi per n=log

M (dove per ogni numero reale x si definisce il “ceiling” x come il minimo intero ≥x).

Esempio: Se i messaggi possibili sono le lettere dell’alfabeto italiano, si ha log

M=log

21=5, dunque il massimo rateo di informazione si ha codificando con parole di lunghezza 5 (21 di esse sono le codifiche, 11 restano inutilizzate: il rateo è allora log

21/5=0,88=88%.

Ovviamente si potrebbe pensare di aumentare il numero di messaggi possibili codificando anche (per un massimo di 11) i segni di interpunzione (virgola, punto, spazio etc.) e aumentando il rateo.

Tutto ciò vale se il canale è “perfetto” cioè se trasmette le parole senza errori.

Spesso però il canale di trasmissione può però essere disturbato da interferenze, rumori etc., e

dunque una parola v{0,1}

trasmessa dal mittenete A può essere modificata da alcuni errori ed

essere ricevuta come parola diversa w{0,1}

dal destinatario B.

Chiameremo errore (di trasmissione) la modifica di 1 singolo bit della parola inviata: quindi un bit 0 che si trasforma in 1 o viceversa.

Nascono così 2 tipi di problemi:

1) Rilevazione dell’errore: la codifica permette a B di rilevare se si è verificato qualche errore ? 2) Correzione dell’errore: la codifica permette a B di rilevare se si è verificato qualche errore ed anche di correggerlo, cioè di trovare la parola originariamente inviata ?

Ovviamente il problema 2) potrebbe essere risolto chiedendo al mittente (in caso di rilevazione dell’errore) la ritrasmissione del messaggio: spesso però il canale è “one-way” (unidirezionale) quindi sarebbe opportuno che B fosse in grado di correggere da solo l’errore.

Tali problemi si possono risolvere aumentando la lunghezza n delle parole che codificano in messaggi: in qualche modo i “bits di ridondanza” aggiunti possono essere utilizzati per rilevare e correggere gli errori, a costo di una maggiore “spesa” nella trasmissione.

Esempio.

1) Supponiamo che l’informazione trasmessa sia una risposta SI oppure NO, dunque M={SI, NO}.

La codifica più “economica” (rateo di informazione=1=100%) è quella che utilizza parole di lunghezza n=1: per esempio

SI  1 , NO  0

Tale codifica non riesce però a rilevare nessun errore: se B riceve la parola 1, la parola originariamente inviata potrebbe essere sia 0 che 1.

Se consideriamo la seguente codifica con parole di lunghezza 2 (rateo di informazione =0,5=50%):

SI  10 , NO  01

Tale codifica riesce a rilevare un errore su un singolo bit: in ognuna delle 2 parole 10, 01, se si modifica un singolo bit non si ottiene l’altra, ma si ottiene una delle parole 00, 11 che non sono codifiche possibili, e dunque si è certi di un errore di trasmissione.

Tale codifica però non riesce a correggere un errore su un singolo bit: se B riceve la parola 00, rileva l’errore in un bit, ma non è in grado di trovare con certezza la parola originariamente inviata (potrebbe essere sia 01, con errore nel secondo bit, che 10, con errore nel primo bit).

Se consideriamo allora la seguente codifica con parole di lunghezza 3 (rateo di informazione

=1/3=33,33%) ottenuta “ripetendo” 3 volte il bit di informazione SI  000 , NO  111

tale codifica riesce a rilevare un massimo di 2 errori: in ognuna delle 2 parole 000, 111, se si modifica 1 bit oppure 2 bits non si ottiene l’altra, ma si ottiene una delle 6 parole che non sono codifiche possibili, e dunque si è certi di un errore di trasmissione.

Inoltre tale codifica riesce a correggere un errore su un singolo bit: non è possibile ottenere la stessa parola modificando 1 singolo bit nelle parole 000, 111, quindi si può, in caso di rilevazione di errore su 1 singolo bit, ricavare con certezza la parola originariamente inviata.

2) Supponiamo che l’informazione trasmessa sia un’indicazione di direzione in una delle direzioni cardinali N,S,E,O, dunque dunque M={N,S,E,O}.

La codifica più “economica” (rateo di informazione=1=100%) è quella che utilizza parole di lunghezza n=2: per esempio

N  00, S  01, E  10, O  11

Con ragionamenti simili a quelli dell’esempio precedente, si deduce che la codifica con parole di lunghezza 6 (rateo di informazione =2/6=33,33%) ottenuta “ripetendo” 3 volte i bits di informazione:

N  000000 , S  010101, E  101010, O  111111

riesce a rilevare un massimo di 2 errori e a correggere un errore su un singolo bit.

Ma la seguente codifica con parole di lunghezza 5 (rateo di informazione =2/5=40%):

N  00000 , S  01101, E  10110, O  11011

riesce ad ottenere gli stessi risultati in termini di rilevazione e correzione di errori, con maggiore rateo di informazione.

L’origine storica della teoria dei codici a rilevazione d’errore e i codici a correzione d’errore si fa risalire ad Hamming (1948), in un periodo in cui egli si occupava della memorizzazione di informazioni su schede perforate, ognuna contenente una parola binaria di 32 bits: avendo osservato che talvolta una scheda conteneva (al più) un singolo bit errato, cercò una teoria formale che permettesse di scoprire automaticamente l’errore ed eventualmente correggerlo.

Come si vede dagli esempi precedenti, per la rilevazione e la correzione degli errori non è importante la codifica dei messaggi (cioè il modo di assegnare ad ogni messaggio una parola di lunghezza n sull’alfabeto {0,1}) ma piuttosto la struttura dell’insieme delle parole che codificano i messaggi.

Definiremo allora codice di lunghezza n un qualunque sottoinsieme non vuoto C dell’insieme

{0,1}

delle parole di lunghezza n sull’alfabeto {0,1} (supporremo sempre che C contenga almeno 2

parole, quindi C>1).