Rappresentazione digitale e codifica informazione

Probabilità di fallimento e overhead nella rilevazione degli errori

Può succedere che, nel momento in cui viene rilevato un errore in un chunk r, tutti gli r bit devono essere ritrasmessi con il loro bit di parità. Quindi r+1 viene ritrasmesso con una probabilità che dipende dalla probabilità di occorrenza di questo singolo errore.

I seguenti grafici mostrano che la probabilità di fallimento (failure probability) di un qualunque sistema di rilevazione di errore cresce all'aumentare della lunghezza dei chunk a cui applichiamo i bit di parità. Da notare che i due grafici sono espressi, il primo in scala lineare, e il secondo in scala logaritmica.

Cosa succede al contrario dell'efficienza, cioè l'overhead, cioè il costo aggiuntivo per il sistema di rilevazione di errore? Vediamo che l'overhead presenta un minimo perché all'inizio aumentiamo in efficienza avendo r che non è un solo bit bensì due, tre, quattro, ecc. ma oltre un certo limite prevale il...

rischio di dover ritrasmettere perché la probabilità di avere un errore singolo diventa non trascurabile e da quel momento in poi c'è anche l'effetto del costo della ritrasmissione che ci dice che tanto più lungo è il segmento da ritrasmettere tanto più costa. Potremmo anche, per ciascuno dei valori (che sui grafici troviamo nell'asse verticale) costruire un grafico che ci mostri per, ad esempio, r = 1 quanto vale l'overhead e quanto vale la failure probability. Poi possiamo continuare per r = 2, r = 3, e così via. Possiamo allora costruirci un grafico che abbia l'overhead nell'asse orizzontale e la failure probability in quello verticale e che utilizzi il valore di r come parametro per muoverci in questo spazio, cioè per ogni valore di r avremo un punto nel grafico. Di solito questo spazio, che si chiama spazio di progetto, va esplorato mettendo in campo le tecniche di cui si dispone e le alternative.

di scelte progettuali cercando di stimare quanto valgono i due parametri da mettere a confronto scegliendo il miglior compromesso tra di loro.

L'overhead dice di quanti bit si allunga il flusso complessivo tenendo conto dei bit di parità e delle esigenze di trasmissione. Quindi ci dice quanto aumenta relativamente, cioè ad ordine del flusso originale quanti altri bit vengono aggiunti. Quando l'overhead è pari a 1 (punto più alto nel grafico) corrisponde al caso in cui a ogni bit aggiungiamo un suo bit di parità e allora la lunghezza del flusso raddoppia.

CORREZIONE DEGLI ERRORI

Un codice che oltre a rivelare gli errori riesce a correggerli in modo tale che non ci sia bisogno della ritrasmissione. Quello che ci serve sono i codici separabili, cioè quei codici che riservano un certo numero di bit per rappresentare l'informazione e un certo numero di bit che invece hanno funzione di controllo e che se si trattassero di un solo bit di

parità si tratterebbe di un bit in grado di dirci se la parola è giusta o sbagliata, e quindi decide se buttarla o tenerla o ritrasmetterla. In questo caso vorremo che questi bit di controllo ci dicessero anche come correggere la parola senza farla ritrasmettere o scartarla. L'ipotesi è sempre quella di errori singoli, allora vediamo di quanti bit di controllo abbiamo bisogno per tutelarci da questi errori. Immaginiamo di avere una parola di n bit in cui chiamiamo r il numero di bit di informazione e m il numero di bit di controllo, per cui n = m + r. Siccome consideriamo gli errori singoli, che tipo di informazione dobbiamo avere per riuscire a correggere un errore eventuale? Dove sta l'errore, perché in binario se noi sappiamo in che posizione sta l'errore allora lo sappiamo anche correggere perché basta fare il complemento del bit. Quindi quello che pretendiamo dai bit di controllo per costruire un codice a correzione di errore è

che sappiamo dirci dov'è l'errore. Le possibili posizioni di una parola di codice sono n, cioè m + r perché ogni codice che abbia delle proprietà di rivelazione o di correzione di errore deve riuscire a tutelare anche i bit di controllo perché anche un errore sui bit di controllo è grave dato che porterebbe ad un fraintendimento della condizione di errore. Le situazioni di errore che il pezzo di parola m deve discriminare sono n + 1 perché deve anche essere in grado di dirci se la parola è corretta. Allora questi m bit devono riuscire a codificare n + 1 cose diverse. Le configurazioni di questi, allora per sapere quanti bit di controllo noi dobbiamo aggiungere dobbiamo fare in modo che: m bit sono 2^m Quindi, 2 è il minimo numero di bit di controllo m che teoricamente riuscirebbe ad aggiungere alla parola le informazioni necessarie a correggerla. Riusciamo a capire qual è la massima efficienza che riusciamo.

adottenere concettualmente. La seguente tabella è costruita per ogni valore di r, cioè noi possiamo dire quanto vale r, quindi quanti sono i bit di informazione e poi vedere quanti bit di controllo m soddisfino la relazione.

Se abbiamo un solo bit di informazione, quindi r = 1. Se avessimo un solo bit di controllo, quindi m = 1, sarebbe 2 = 2, ma secondo la relazione dovremmo avere r + m + 1, cioè almeno 3. Allora un solo bit di controllo non basta. Infatti, un solo bit sarebbe come aggiungere il bit di parità che ci porta ad avere distanza di Hamming pari a 2 e non pari a 3 (come invece ci serve per poter correggere). Con m = 2, abbiamo 2 = 4, e r + m + 1 = 1 + 2 + 1 = 4 e quindi si rispetta la relazione. Questo vuol dire che se m è pari a 2 riesce a fornirci tutte le informazioni necessarie a correggere gli errori se la parola utilizzava per l'informazione un solo bit.

Se abbiamo due bit di informazione, quindi r = 2. Allora proviamo ancora

confrontando il numero di bit di controllo con il numero di bit di informazione. In generale, il numero di bit di controllo aumenta più lentamente rispetto al numero di bit di informazione perché i bit di controllo sono utilizzati per rilevare gli errori e non per trasmettere informazioni effettive.sfruttando l'efficienza di un esponenziale che quindi rende logaritmica la relazione. Il bit di parità non cresce. Quanti bit di controllo ci servono per ottenere distanza di Hamming pari a 2? Sempre 1. Quanti bit di controllo ci servono per averla pari a 3? Bisogna seguire quella relazione. La correzione d'errore è molto più complicata perché l'informazione che voglio avere è molto più complicata e che cresce all'aumentare della lunghezza della parola e quindi necessariamente deve crescere il numero di bit necessario a codificare quell'informazione. Alla parte di controllo di una parola, si applica la teoria dell'informazione come alla parte di informazione. Il bit di parità non si deve aggiungere ad m perché la regola assunta è che i bit di controllo devono codificare anche se nella parola ci sia l'assenza di errore, quindi questo codice, oltre a dirci dove sta l'errore.

sarà anche in grado di dirci se l’errore non c’è. quindi siccome il bit di parità ci diceva solo se l’errore fosse presente o meno ora non ci serve più perché questa funzione è incorporata in m.

Vedremo che tutti questi bit di controllo potrebbero essere definiti bit di parità ma vengono ricavati in un modo particolare. Perché dobbiamo ricavarli in modo particolare? Immaginiamo di prendere un codice {00,01,10,11} non ridonante con due bit. Se voglio aggiungere il bit di parità devo mantenere nella parola il numero di bit a 1 pari, cioè:

00 + 0 000• → 01 + 1 011• → 10 + 1 101• → 11 + 0 110•

Quello che ottengo è il codice di parità {000,011,101,110}. A questo punto sappiamo che se i bit di informazione sono due abbiamo bisogno di tre bit di controllo se vogliamo poter correggere l’errore.

Immaginiamo che il primo dei tre bit di controllo sia un bit di parità.

A questo punto potremmo pensare di aggiungere un altro bit di parità ma se usassimo lo stesso criterio considerando tutta la parola a cui applicare il bit di parità otterremmo: 000 + 0 0000• → 011 + 0 0110• → 101 + 0 1010• → 110 + 0 1100• Se invece pretendessimo di calcolare il bit di parità sul codice originale, otterremmo di nuovo gli stessi valori per i bit di parità: 000 + 0 0000• → 011 + 1 0111• → 101 + 1 1011• → 110 + 0 1100• Allora questo vuol dire che aggiungere bit in modo banale non aggiunge informazioni, quindi, non sono questi i criteri che vanno utilizzati. Vediamo come costruire un codice a correzione di errore che abbia l'efficienza massima teorica. Si ricorda che se il numero di bit di controllo che riusciamo ad aggiungere è m, di meglio non si può fare perché questa informazione data dagli m bit è indispensabile a riuscire a correggere la parola. Di seguitorappresento le posizioni in cui posso andare a scrivere i bit: Quindi questo è come un casellario in cui ogni quadretto dovrà ospitare un bit a partire da sinistra (scelta arbitraria visto che non si ha a che fare con la notazione posizionale). I numeri sopra tali quadretti indicano le posizioni dei bit. Ora in colonna rappresento le posizioni in codifica binaria. Il bit meno significativo lo scrivo in alto, poi vado verso il basso. A questo punto evidenzio i bit in posizione delle potenze intere di due. Come le riconosco? Hanno un solo 1 nella loro codifica binaria. Quindi, come le potenze intere di dieci in notazione decimale, tutte le potenze intere di due hanno un solo 1 e tutti zeri. Tali posizioni le evidenzio con il colore grigio (caselle colorate). Immaginiamo di avere un codice non ridondante che abbia un solo bit di informazione (r = 1) e che partendo da sinistra i bit di informazione possono essere messi solo nelle caselle non evidenziate. Quindi questo singolo bit lo

potremmo mettere nella posizione n = 3, cioè la prima posizione