Teocod (revisionato)

Teoria dell’informazione e codici

Ing. Pazzo

20 settembre 2009

2

Si consiglia di affiancare il materiale presente in questo riassunto agli appunti presi a lezione. Que-sto perché (ovviamente!) non si vuole avere alcuna presunzione di esaustività, né di assoluta corret-tezza: nonostante le revisioni fin’ora effettuate, potrebbero infatti essere ancora presenti molti errori eimprecisioni.

2

Indice

1 Introduzione alla Teoria dell’Informazione 71.1 Schema del collegamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 La teoria dell’informazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.3 Eventi, variabili aleatorie, bit d’informazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

1.3.1 Informazione associata a due eventi indipendenti . . . . . . . . . . . . . . . . . . . . . 91.3.2 Entropia di una variabile aleatoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.3.3 Probabilità condizionata, probabilità marginale, distribuzione congiunta . . . . . . . 121.3.4 Entropia congiunta, entropia condizionata . . . . . . . . . . . . . . . . . . . . . . . . . 13

2 Codifica di sorgenti discrete 192.1 Osservazione simbolo per simbolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2 Osservazione per gruppi di simboli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3 Entropia di una sorgente stazionaria: due definizioni . . . . . . . . . . . . . . . . . . . . . . . 202.4 Ridondanza e confronto fra sorgenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212.5 Tecniche di compressione dei dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.5.1 Codici a prefisso e disuguaglianza di Kraft . . . . . . . . . . . . . . . . . . . . . . . . . 242.5.2 Un’applicazione della disuguaglianza di Kraft: i codici a prefisso di Shannon-Fano . 26

2.6 Teorema della codifica di sorgente (I teorema di Shannon) . . . . . . . . . . . . . . . . . . . . 262.7 Codice di Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.8 Codifica a blocchi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.9 Codifica a corse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.10 Codice di Lempel-Ziv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.11 Considerazioni finali: lossy o lossless? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3 La codifica di canale e la capacità 313.1 Canale discreto senza memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2 Capacità di canale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

3.2.1 Canale deterministico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.2.2 Canale binario simmetrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.2.3 Canale binario a cancellazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.2.4 Canale Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.2.5 Canale binario non simmetrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.3 Capacità di canale con blocchi di simboli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.4 Disuguaglianza del data processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.5 Disuguaglianza di Fano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.6 Codifica di canale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.7 Teorema della codifica di canale (secondo teorema di Shannon) . . . . . . . . . . . . . . . . . 443.8 Variabili aleatorie continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.9 Entropia differenziale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

3.9.1 Teorema: la distribuzione uniforme ha entropia massima (caso intervallo limitato) . 473.9.2 Teorema: la distribuzione gaussiana ha entropia massima (caso intervallo illimitato) 483.9.3 Teorema: la distribuzione esponenziale negativa ha entropia massima (caso interval-

lo [0,+∞] ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

3

4 INDICE

4 Il limite di Shannon 514.1 Capacità del canale additivo gaussiano bianco . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.2 Caso tempo-continuo a banda limitata (formula di Hartley-Shannon) . . . . . . . . . . . . . . 53

4.2.1 Incorrelazione del rumore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554.3 Il limite di Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.4 Antipodal Signalling AWGN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574.5 Hard decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.6 Unquantized output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.7 Low SNR region . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.8 Trattamento dei segnali passa-banda e water-filling . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.8.1 Caso tempo-discreto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5 I codici di canale: codici a blocco 695.1 Codici a blocco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

5.1.1 Alcune definizioni e terminologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705.2 Concetti elementari di algebra lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715.3 Codici a blocco lineari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715.4 La matrice generatrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 735.5 Codici sistematici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.6 Matrice di controllo parità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.7 Codici estesi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765.8 Codici purgati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775.9 Il Singleton Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 775.10 Codici di Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785.11 La decodifica e la Teoria della Decisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785.12 Decodifica ottima per codici a blocco su canale BSC . . . . . . . . . . . . . . . . . . . . . . . . 795.13 Rilevazione degli errori e standard array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805.14 Capacità di correzione di un codice (canale BSC) . . . . . . . . . . . . . . . . . . . . . . . . . . 825.15 Criterio ML per canali additivi gaussiani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 845.16 Union Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855.17 Codici accorciati (shortened codes) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885.18 Codici a blocco lineari ciclici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 895.19 Codificatore per codici ciclici (sistematici e non) . . . . . . . . . . . . . . . . . . . . . . . . . . 925.20 Calcolo della sindrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925.21 Applicazioni notevoli dei codici ciclici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

5.21.1 CRC: Cyclic Redundancy Check Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945.21.2 Codici Hamming ciclici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955.21.3 Codice di Golay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955.21.4 Codici BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

5.22 Codici di Reed-Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955.23 Codici per la rilevazione di errori burst . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 965.24 Codici MLSR (Maximum Length Shift-Register Codes) . . . . . . . . . . . . . . . . . . . . . . . . 96

6 Codici a traliccio 996.1 Codici convoluzionali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 996.2 Diagramma a traliccio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1006.3 Decodifica dei codici convoluzionali con hard decisions su BSC . . . . . . . . . . . . . . . . . . 1016.4 Algoritmo di Viterbi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

6.4.1 Complessità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1026.4.2 Altri aspetti implementativi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

6.5 Codici convoluzionali punturati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1036.6 Codici convoluzionali sistematici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1036.7 Codici convoluzionali catastrofici (paura eh!?) . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4

INDICE 5

7 Altri aspetti riguardanti i codici di canale 1057.1 Interleaving . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

7.1.1 Interleaving a blocco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1057.2 Codici concatenati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1067.3 Turbo-codici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1067.4 LDPC: Low Density Parity Check . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

7.4.1 QC-LDPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

5

6 INDICE

6

Capitolo 1

Introduzione alla Teoriadell’Informazione

1.1 Schema del collegamento

Figura 1.1: Lo schema del collegamento

Nessun riassunto di Teoria dell’Informazione deve iniziare senza aver prima visto lo schema del col-legamento! Questo schemino essenziale mostra il percorso che l’informazione compie, dalla sorgenteall’utilizzatore finale; gli step sono i seguenti:

∙ sorgente: trattasi della sorgente dell’informazione: può essere un’entità analogica1 (un suono), maanche un’informazione in formato digitale come un documento, un brano audio, etc. . .

∙ codificatore di sorgente: ha il compito di rappresentare i dati in maniera più sintetica, in modo chesi possa spedire quanta più informazione possibile nel minor tempo possibile. Possono essere di duetipi, in base a se viene persa informazione (esempio: codifica JPEG) o meno (esempio: compressioneZIP);

∙ codificatore di canale: ha il compito di proteggere, con l’aggiunta di simboli di ridondanza, i datidai disturbi che possono essere fonte di errori;

∙ canale: l’etere, un filo, oppure un supporto di memorizzazione di massa (hard-disk);

∙ decodificatore di canale: componente duale del codificatore di canale;

∙ decodificatore di sorgente: componente duale del codificatore di sorgente;

∙ l’utilizzatore finale: colui che desidera fruire dell’informazione.

1In tal caso sarà necessario un convertitore A/D.

7

8 CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

1.2 La teoria dell’informazione

The information is the difference which makes a difference.L’informazione è quella differenza che fa la differenza.

Gregory Bateson

Che cos’è l’informazione? In una comunicazione, che avviene attraverso un dato alfabeto di simboli,l’informazione viene associata a ciascun simbolo trasmesso e viene definita come la riduzione di incertezzache si poteva avere a priori sul simbolo trasmesso. L’informazione non è semplicemente una variazione:una sequenza del tipo

... 01010101010101010...

varia continuamente, ma non porta informazione perché è assolutamente prevedibile. In questo senso,l’informazione è legata alla non prevedibilità di un certo evento: ad esempio, se affermiamo che ’Oggi, inquesto punto, non sono caduti degli aerei’, non diamo una grande informazione perché si presuppone chequesto accada per la stragrande maggioranza del tempo. Viceversa l’affermazione ’Oggi, in questo punto,sono caduti degli aerei’ ha una componente informativa molto più preziosa (anche se un po’ drammatica).

La Teoria dell’informazione è quel settore delle telecomunicazioni che si occupa di definire le basi teo-riche su cui si fonda la scienza dell’informazione. La sua nascita è relativamente recente: essa vienesolitamente fatta risalire al 1948, anno in cui Claude Shannon pubblicò sul Bell System Technical Jour-nal Una teoria matematica della comunicazione in cui introduceva per la prima volta in modo sistematico lostudio dell’informazione e della comunicazione. Grazie alla sua affascinante teoria, Shannon è riuscito adefinire e specificare in maniera quantitativa i meccanismi di compressione, codifica e trasmissione deidati, mostrandocene i limiti ultimi.

1.3 Eventi, variabili aleatorie, bit d’informazione

L’informazione è fortemente legata al concetto di evento e il concetto di evento a quello di variabilealeatoria (v.a. o r.m.2). Indicheremo con X una generica variabile aleatoria e con X l’insieme di tutti gli Lvalori che essa può assumere

X = x1, x2, . . . , xL

In questo contesto, L viene detta cardinalità di X . A ciascun possibile risultato dell’esperimento ’incarnato’dalla variabile aleatoria viene associato un valore e una probabilità:

p (X = x1) = p (x1) = p1

p (X = x2) = p (x2) = p2

...

p (X = xL) = p (xL) = pL

Chiaramente, per le basilari proprietà del calcolo aleatorio, si deve avere che

∑i

pi = 1 (1.1)

L’informazione ’portata’ dall’esperimento x è pari a:

I(x) = log21

p(x)= − log2 p(x) (1.2)

Graficando la curva otteniamo la figura 1.2. L’unità di misura per I è il cosiddetto Shannon (Sh) dettoanche ’bit di informazione’.

2Random Variable.

8

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE 9

Figura 1.2: Grafico probabilità/informazione

1.3.1 Informazione associata a due eventi indipendenti

L’informazione associata a due eventi indipendenti è pari alla somma delle informazioni degli eventipresi singolarmente. Se si ha quindi

xi, xj → Statisticamente indipendenti

la probabilità congiunta saràp(xi, xj) = p(xi)p(xj)

e l’informazione pari a:

I(xi, xj) = log21

p(xi)p(xj)= log2

1p(xi)

+ log21

p(xj)= I(xi) + I(xj) (1.3)

1.3.2 Entropia di una variabile aleatoria

La mia più grande preoccupazione era come chiamarla. Pensa-vo di chiamarla informazione, ma la parola era fin troppo usata,così decisi di chiamarla incertezza. Quando discussi della cosacon John Von Neumann, lui ebbe un’idea migliore. Mi disse cheavrei dovuto chiamarla entropia, per due motivi: ’Innanzitutto,la tua funzione d’incertezza è già nota nella meccanica statisticacon quel nome. In secondo luogo, e più significativamente, nes-suno sa cosa sia con certezza l’entropia, così in una discussionesarai sempre in vantaggio’.

Claude Shannon

Nella teoria dell’informazione - e in rapporto alla teoria dei segnali - l’entropia misura la quantità diincertezza o informazione presente in un segnale aleatorio, che può essere interpretata anche come laminima complessità descrittiva di una variabile aleatoria, ovvero il limite inferiore della compressionedei dati. L’entropia (che chiameremo H(x)) è inoltre definita come la media statistica dell’informazioneportata da tutti i possibili valori che può assumere una variabile aleatoria:

H(x) = E[I(x)] = ∑x∈X

p(x)I(x) = ∑x∈X

p(x) log21

p(x)= − ∑

x∈Xp(x) log2 p(x) (1.4)

9


ESEMPIO:Calcoliamo l'entropia di una distribuzione Bernoulliana3:

X = x1, x2

Associamo a x1 la probabilità p e a x2 la probabilità q = 1− p. L'entropia sarà quindi:

H (x) = p log21p+ q log2

1q= p log

1p+ (1− p) log

11− p

Andando a gra�care otteniamo la �gura 1.3.

Figura 1.3: Entropia di una variabile aleatoria bernoulliana

L’entropia ha alcune importanti proprietà:

∙ anzitutto è sempre maggiore di zero. Possiamo accorgercene osservando la definizione 1.4: p(x) è

una quantità sicuramente non negativa, così come è sempre positivo il termine log21

p(x);

∙ l’entropia dipende solo dalla probabilità p(x);

∙ se la cardinalità dell’insieme degli eventi è L, varrà

H(x) ≤ log2 L (1.5)

e l’uguaglianza varrà soltanto nel caso di distribuzione uniforme:

p(x1) = p(x2) = . . . = p(xL) =1L

Si ha infatti:

H (x)− log2 L = ∑x

p (x) log21

p (x)+ log

1L︸︷︷︸

=− log2 L

= ∑x

p (x) log21

p (x)+

=1︷︸︸︷∑x

p (x) ⋅ log1L=

∑x

p (x)[

log21

p (x)+ log

1L

]= ∑

xp (x)

[log2

1p (x) L

]︸︷︷︸

proprietà dei logaritmi!

3La variabile casuale bernoulliana, dal nome dello scienziato svizzero Jakob Bernoulli (1654-1705), è la più semplice di tutte levariabili casuali. È una variabile dicotomica, dunque con due sole possibili realizzazioni (0 e 1), cui sono associate le rispettiveprobabilità p e 1− p.

10


Applicando una proprietà notevole dei logaritmi:

log21

p (x) Llog2 e

= ln1

p (x) L︸︷︷︸cambio di base

⇒ log21

p (x) L= log2 e ⋅ ln 1

p (x) L

Ora ci giochiamo il Jolly: osserviamo che la retta di equazione χ− 1 sovrasta la curva ln χ per ognivalore di χ (le due curve si toccano solamente in χ = 1)4. Possiamo quindi scrivere:

log2 χ = ln χ ⋅ log2 e ⩽ (χ− 1) ⋅ log2 e

log21

p (x) L= log2 e ⋅ ln 1

p (x) L⇒ log2

1p (x) L︸︷︷︸

la χ dell’equaz. precedente

⩽ log2 e ⋅(

1p (x) L

− 1)

(1.6)

Sfruttando questa disuguaglianza nella nostra equazione arriviamo ad affermare che:

H (x)− log2 L = ∑x

p (x)[

log21

p (x) L

]⩽ log2 e ⋅∑

xp (x)

(1

p (x) L− 1)= log2 e

[∑x

1L−∑

xp (x)

]︸︷︷︸

1−1=0

= 0

Infine:H (x)− log2 L ⩽ 0⇒ H (x) ⩽ log2 L

Questo risultato ci suggerisce una proprietà importante: la distribuzione uniforme (quella che rendepossibile la sostituzione del segno ≤ con l’uguaglianza) è un’estremale per l’entropia e garantisce lamassima incertezza.

ESERCIZIO:

Siano a e b due vettori di uguale lunghezza n, con elementi tutti positivi. Per ipotesi si ha che:

n

∑i=1

ai =n

∑i=1

bi = 1

Vogliamo dimostrare chen

∑i=1

ai log2 ai ≥n

∑i=1

ai log2 bi

cioè che:n

∑i=1

ai log2biai≤ 0

Per risolvere questo esercizio sfruttiamo la relazione ricavata nel paragrafo poco sopra e applichiamo le ipotesi:

n

∑i=1

ai log2biai

⩽n

∑i=1

ai

(biai− 1)

log2 e︸︷︷︸sicuramente minore di log2

biai

= log2 e ⋅n

∑i=1

(bi − ai) = log2 e ⋅(

n

∑i=1

bi −n

∑i=1

ai

)︸︷︷︸

=0

= 0

4Si osservi infatti che:

In χ = 1 le funzioni valgono entrambe 0

Derivata di χ− 1 ⇒ 1

Derivata di ln χ⇒ 1χ

⎧⎨⎩per χ > 1→ 1

χ< 1, la funzione ln χ cresce più lentamente di χ− 1 andando nella direzione positiva delle χ

per 0 < χ < 1→ 1χ

> 1, la funzione ln χ cala più velocemente di χ− 1 andando nella direzione negativa delle χ

11


ESERCIZIO:

Siano ai e bi due successioni e sia

aii→∞−−→ a

Si dimostri che si ha (regola di Cesaro5):

bn =1n

n

∑i=1

ain→∞−−−→ a (1.7)

Si deve insomma dimostrare che

∀ε > 0 ∃ N (ε) : ∣an − a∣ < ε ∀ n > N (ε)

Soluzione6:

bn − a =1n

n

∑i=1

ai − a

∣bn − a∣ = 1n

n

∑i=1∣ai − a∣ = 1

n

⎛⎝N(ε)

∑i=1∣ai − a∣+

n

∑i=N(ε)+1

∣ai − a∣

⎞⎠ ⩽1n

(N(ε)

∑i=1∣ai − a∣+ ε (n− N (ε)− 1)

)

∣bn − a∣ ⩽(

1n

N(ε)

∑i=1∣ai − a∣+ ε

n(n− N (ε)− 1)

)n→∞−−−→ ε

bnn→∞−−−→ a + ε ≈ a

1.3.3 Probabilità condizionata, probabilità marginale, distribuzione congiunta

Cosa succede se siamo in presenza di più variabili aleatorie? Possiamo definire alcune probabilitàspeciali che ’intersechino’ eventualità riferite ad entrambe? Ebbene sì!

Date le v.a. X e Y possiamo ad esempio definire la seguente probabilità congiunta

pX,Y (x, y) = p (x, y) = p (X = x, Y = y) (1.8)

la quale rappresenta la probabilità che, contemporaneamente, X assuma valore x e Y valore y. Le probabilitàriferite ad una sola delle due v.a. vengono invece dette marginali:{

pX (x) = p (x) = p (X = x)pY (y) = p (y) = p (Y = y)

(1.9)

Infine, abbiamo la probabilità condizionata, ovvero quella che si verifichi un dato evento sapendo a prioriche se n’è verificato un altro: di seguito riportiamo l’espressione della probabilità che X assuma valore xsapendo che Y ha assunto valore y

p(x∣y) = p(X = x∣Y = y) (1.10)

La seguente equazione mette in relazione la probabilità congiunta con quella condizionata:

p (x ∣y ) p (y) = p (y ∣x ) p (x) = p (x, y) (1.11)

Invece quella riportata di seguito relaziona la probabilità marginale con quella congiunta:

p(x) = ∑y∈Y

p(x, y) (1.12)

Ovviamente continua a valere la proprietà per la quale la somma di tutte le probabilità deve restituire 1:

∑x∈X

∑y∈Y

p(x, y) = 1 (1.13)

12


Figura 1.4: Esempio delle relazioni che intercorrono fra le probabilità congiunte e marginali

ESEMPIO:In �gura 1.4 viene riportato un esempio delle relazioni che intercorrono fra le probabilità congiunte e

marginali. Si nota ad esempio che, per ogni colonna ed ogni riga, sommando le probabilità congiunte

otteniamo le probabilità marginali segnate, appunto, a margine della tabella. Sfruttando la relazione

1.11 possiamo ad esempio provare a calcolare la probabilità condizionata:

p (x1, y2) = p (x1 ∣y2 ) p (y2)⇒ p (x1 ∣y2 ) =p (x1, y2)

p (y2)=

1/21/2

= 1

Guardando la tabella, d'altronde, sappiamo che la probabilità che X e Y assumano contempora-

neamente valori x2 e y2 è nulla: quindi, se si palesa l'evento y2, sicuramente si sarà veri�cato

x1.

1.3.4 Entropia congiunta, entropia condizionata

Definita la probabilità congiunta e la probabilità condizionata, possiamo ragionare sull’entropia: datele variabili aleatorie X e Y possiamo definire l’entropia di ciascuna

H (X) = −∑x

p (x) log2 p (x)

H (Y) = −∑y

p (y) log2 p (y)

ma possiamo anche definire:

∙ l’entropia congiunta:H(X, Y) = −∑

x∑y

p(x, y) log2 p(x, y) (1.14)

∙ l’entropia condizionata: una volta che abbiamo calcolato

H(X∣Y = y) = −∑x

p(x∣y) log2 p(x∣y) (1.15)

possiamo definire entropia condizionata la seguente quantità:

H (X ∣Y ) = Ey [H (X ∣Y = y)] = ∑y

p (y) H (X ∣Y = y ) = −∑x

∑y

p (y)

H(X∣Y=y )︷︸︸︷p (x ∣y ) log2 p (x ∣y ) =

= −∑x

∑y

p (x, y)︸︷︷︸=p(y)p(x∣y )

log2 p (x ∣y )

5Ernesto Cesàro (Napoli, 12 marzo 1859 - Torre Annunziata, 12 settembre 1906) è stato un matematico italiano, noto per i suoicontributi alla geometria differenziale e alla teoria delle serie infinite.

6Si tratta della mia personalissima dimostrazione, quindi potrebbe non fare testo ed essere errata. Prendetela con le molle!

13


Queste quantità godono di alcune interessanti proprietà:

∙ prima proprietà:H (X, Y) = H (X ∣Y ) + H (Y) = H (Y ∣X ) + H (X)

Dimostrazione:

H (X ∣Y ) + H (Y) = −∑x

∑y

p(x, y) log2 p(x ∣y )︸︷︷︸H(X∣Y )

−∑y

p (y) log2 p (y)︸︷︷︸H(Y)

=

= −∑x

∑y

p(x, y) log2 p(x ∣y )−∑y

∑x

p(x, y)︸︷︷︸p(y)

log2p(x, y)p(x ∣y ) =

= ∑x

∑y

p(x, y)[− log2 p(x ∣y )− log2

p(x, y)p(x ∣y )

]= −∑

x∑y

p(x, y)[

log2

(p(x ∣y ) p(x, y)

p(x ∣y )

)]=

= −∑x

∑y

p(x, y) log2 p(x, y) = H (X, Y)

∙ seconda proprietà: l’incertezza che abbiamo sulla variabile X data la variabile Y è non superioreall’incertezza che abbiamo sulla sola X. Si ha ovvero:

H (X ∣Y ) ⩽ H (X) ⇒ con = solo se X e Y sono indipendenti

Dimostrazione:

−∑x

∑y

p (x, y) log2 p (x ∣y )︸︷︷︸H(X∣Y )

−(−∑

xp (x) log2 p (x)

)︸︷︷︸

H(X)

⩽ 0

∑x

∑y

p (x, y) log21

p (x ∣y ) −∑x

∑y

p (x, y)︸︷︷︸p(x)

log21

p (x)⩽ 0

∑x

∑y

p (x, y)(

log2p (y)

p (x, y)− log2

1p (x)

)⩽ 0

∑x

∑y

p (x, y)(

log2p (y) p (x)

p (x, y)

)⩽ log2 e ∑

x∑y

p (x, y)(

p (y) p (x)p (x, y)

− 1)=

= log2 e ∑x

∑y

p (y) p (x)− p (x, y)︸︷︷︸=0

= 0

∙ terza proprietà (chain rule, regola della catena): consideriamo tre variabili aleatorie X1, X2, X3. Allorasi ha, applicando due volte la chain rule:

H(X1, X2, X3) = H(X1∣X2, X3) + H(X2, X3) = H(X1∣X2, X3) + H(X2∣X3) + H(X3) (1.16)

Possiamo, volendo, iterare il procedimento e considerare k variabili aleatorie (e, infine, applicare laseconda delle nostre proprietà):

H (X1, X2, . . . , Xk) =k

∑i=1

H (Xi ∣Xi−1, Xi−2, . . . , X1 ) ⩽k

∑i=1

H (Xi) (1.17)

La sommatoriak∑

i=1H nel secondo passaggio non deve turbare: il risultato è esattamente l’estensione

della 1.16 perché l’addizione è commutativa. Era scontato? Scusate.

14


∙ quarta proprietà: la desumiamo dalla proprietà 1 e dalla proprietà 2.

H(X, Y) ≤ H(X) + H(Y) (1.18)

A parole: l’incertezza sulla coppia non può essere superiore a quella che abbiamo guardando se-paratamente gli elementi (nella coppia, infatti, possono esservi regole o legami che diminuisconol’incertezza). Generalizzando:

H(X1, X2, X3, . . . , XK) ≤k

∑i=1

Xi (1.19)

ESEMPIO:Consideriamo nuovamente la �gura 1.4 e facciamo qualche calcoletto7:

∙ entropia di X: è l'entropia di una variabile bernoulliana con probabilità p = 1/4. Essendo

un'entropia notevole si scrive direttamente

H(X) = ℋ(

14

)∙ entropia congiunta:

H (X, Y) =14

log2 4 +14

log2 4 +12

log2 2 + 0 =32

∙ entropia condizionata (y1):

H (X ∣Y = y1 ) = −∑x

p (x ∣y1 ) log2 p (x ∣y1 ) = −∑x

p (x, y1)

p (y1)log2

p (x, y1)

p (y1)=

= −

⎛⎜⎜⎜⎝p(x1,y1)︷︸︸︷0, 250, 5

log20, 250, 5

+

p(x2,y1)︷︸︸︷0, 250, 5

log20, 250, 5

⎞⎟⎟⎟⎠ = −(

12(−1) +

12(−1)

)= 1

∙ entropia condizionata (y2):

H (X ∣Y = y2 ) = −∑x

p (x ∣y2 ) log2 p (x ∣y2 ) = −∑x

p (x, y2)

p (y2)log2

p (x, y2)

p (y2)=

= −

⎛⎜⎜⎜⎝p(x1,y2)︷︸︸︷

0, 50, 5

log20, 50, 5

+ 0

⎞⎟⎟⎟⎠ = 0 ⇒ non c'è incertezza!

A prima vista i seguenti risultati

H (X) = ℋ(

14

)= 0, 8113 < 1 H (X ∣Y = y1 ) = 1

potrebbero turbarci, visto che abbiamo detto (nella proprietà 2) che il condizionamento non aumenta

l'entropia. In realtà non abbiamo violato alcuna regola perché non è corretto considerare la sola y1:

dovendo ragionare in termini medi, dobbiamo includere anche y2:

H (X ∣Y ) = H (X ∣Y = y1 ) p (y1) + H (X ∣Y = y2 ) p (y2) = 0, 5 < ℋ(

14

)Ecco quindi che tutto torna!

7Ricordiamo che l’unità di misura dell’entropia è lo Shannon [Sh].

15


ESERCIZIO:

NOTA: non ho le soluzioni 'u�ciali' di questo esercizio. Quanto scritto di seguito costituisce la mia

soluzione, ma può essere errata!

Date due variabili aleatorie discrete X e Y con alfabeto X = Y = {−1, 1} e distribuzione di probabilità

congiunta di tipo:

p(x, y) = keβxy

1. Determinare la costante k.Siccome si deve avere che:

k ∑x

∑y

eβxy = 1

Allora:

k ∑x

(∑y

eβxy

)= k ∑

x

(e−βx + eβx

)= k

(e−β + eβ + e−β + eβ

)= 2k

(e−β + eβ

)= 1⇒ k =

12e−β + 2eβ

2. Determinare le probabilità marginali p(x) e p(y).Probabilità p(x):

p(x) = k(

e−βx + eβx)

Probabilità p(y):

p(y) = k(

e−βy + eβy)

I valori numerici sono riportati in tabella 1.1: si nota in particolare che le probabilità marginali hanno

distribuzione uniforme.

x = 1 x = −1 prob. marginale

y = 1 keβ ke−β k(eβ + e−β) =12

y = −1 ke−β keβ k(eβ + e−β) =12

prob. marginale k(eβ + e−β) =12

k(eβ + e−β) =12

Tabella 1.1: Probabilità congiunte e marginali

3. Determinare le entropie H(X), H(Y), H(X, Y).Le entropie H(X) e H(Y) saranno entrambe pari al valore (massimo) log2 2 = 1 in quanto le distribuzioni

di probabilità marginali sono uniformemente distribuite. L'entropia congiunta sarà sicuramente inferiore o

uguale a 2 visto che vige la regola

H(X, Y) ≤ H(X) + H(Y) = 2

Svolgendo i calcoli:

H (X, Y) = −∑x

∑y

p (x, y) log2 p (x, y) = −∑x(p (x,−1) log2 p (x,−1) + p (x, 1) log2 p (x, 1)) =

= − (p (1,−1) log2 p (1,−1) + p (1, 1) log2 p (1, 1) + p (−1,−1) log2 p (−1,−1) + p (−1, 1) log2 p (−1, 1)) =

= −k(

e−β log2 e−β + eβ log2 eβ + eβ log2 eβ + e−β log2 e−β)= −

(e−β log2 e−β + eβ log2 eβ

)e−β + eβ

16


ESERCIZIO:

NOTA: non ho le soluzioni 'u�ciali' di questo esercizio. Quanto scritto di seguito costituisce la mia

soluzione, ma può essere errata!

Due variabili aleatorie discrete X1 e X2 sono caratterizzate da distribuzioni p1(x) e p2(x) e da alfabeti

X1 = {1, . . . , m}

X2 = {m + 1, . . . , n}

A partire da queste due si de�nisce una terza variabile aleatoria:

X =

{X1 con probabilità α

X2 con probabilità 1− α

Si chiede di:

1. Determinare la distribuzione di X, detta p(x), in funzione di α, p1(x) e p2(x).Risultato:

p(x) = αp1 (x) + (1− α) p2 (x)

2. Determinare l'entropia H(X) in funzione di α.Risultato:

H (X) ≜ −∑x

p (x) log2 p (x) =

= −αm

∑x=1

p1 (x) log2 [αp1 (x)]− (1− α)n

∑x=m+1

p2 (x) log2 [(1− α) p2 (x)] =

= −α log2 α− αm

∑x=1

p1 (x) log2 p1 (x)− (1− α) log2 (1− α)− (1− α)n

∑x=m+1

p2 (x) [p2 (x)] =

= −α log2 α + αH (X1)− (1− α) log2 (1− α) + (1− α) H (X2) =

= αH (X1) + (1− α) H (X2) + α log21α+ (1− α) log2

11− α

=

= αH (X1) + (1− α) H (X2) +ℋ(α)

3. Determinare le entropie H(X1) e H(X2).

Vedi punto precedente.

17


18

Capitolo 2

Codifica di sorgenti discrete

Figura 2.1: Sorgente tempo-discreta

Intendiamo con questo sorgenti tempo-discrete (vedi figura 2.1); per ipotesi supporremo che le variabilialeatorie (simboli) emesse dalla sorgente posseggano tutti lo stesso alfabeto e che la distribuzione p(x)(probability mass function) per tali variabili non muti nel tempo. Chiameremo quindi questo caso DMS(Discrete Memoryless Source) in quanto:

∙ la sorgente è discreta (emette simboli appartenenti ad un certo alfabeto);

∙ la sorgente è senza memoria (ogni simbolo è indipendente dall’altro);

∙ la p(x) è tempo-invariante.

In particolare, le variabili aleatorie vengono dette i.i.d. (indipendenti e identicamente distribuite) così chepossiamo scrivere:

p(

Xn1 = x(1), Xn2 = x(2), . . . , XnM = x(M))=

M

∏i=1

p(

Xni = x(i))=

M

∏i=1

p(

x(i))

{ni → istante d’osservazione

x(i) → uno dei possibili valori dell’alfabeto

(2.1)

2.1 Osservazione simbolo per simbolo

Avremo in uscita le nostre variabili aleatorie e tutte avranno la stessa entropia. Infatti:

∙ entropia della variabile aleatoria X1:

H (X1) = −∑x

p (x) log2 p (x)

∙ entropia della variabile aleatoria X2:

H(X2) = H(X1) = H(X)

Si noti che nel caso DMS ha senso la notazione H(X), la quale non indica un preciso istante:H(X) viene detta entropia di una DMS e indica quantitativamente l’informazione mediamente portata(trasmessa) da un simbolo.

19

20 CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

2.2 Osservazione per gruppi di simboli

Immaginiamo ora di osservare gruppi di K simboli alla volta. Ogni gruppo sarà interpretabile comeuna variabile aleatoria multidimensionale: chiameremo a tal proposito X(K)

i il vettore di K simboli diposizione i (diremo anche che è l’i-esimo supersimbolo). Supponendo che i nostri supersimboli sianostazionari (dato che la DMS lo è) potremo calcolarne l’entropia:

H(

X(K))= H (X1, X2, . . . , XK) =

K

∑i=1

H (Xi) = K ⋅ H (X)

[Shannon

supersimbolo

]Con un semplicissimo passaggio algebrico possiamo anche scrivere:

H(X(K))

K= H(X) (2.2)

Rimuovendo l’ipotesi di mancanza di memoria1, ma mantenendo quella di stazionarietà, abbiamoinvece:

H(

X(K))= H (X1, X2, . . . , XK)

!!<

K

∑i=1

H (Xi) = K ⋅ H (X)⇒ H(

X(K))< K ⋅ H (X)

H(

X(K))

K︸︷︷︸Entropia/simbolo (caso con memoria)

< H (X)︸︷︷︸Entropia/simbolo (caso NO memoria)

La presenza di memoria ha fatto calare l’entropia: ciò equivale ad affermare che, all’interno di un vettore(cioè di un supersimbolo), un simbolo è meno incerto se c’è memoria.

2.3 Entropia di una sorgente stazionaria: due definizioni

Possiamo dare due differenti definizioni dell’entropia (per simbolo) di una sorgente stazionaria:

∙ la prima si formula immaginando di guardare un numero enorme di simboli (k → ∞) e di passareal limite la relazione 2.2:

H∞ (X) = limk→∞

H(

X(k))

k(2.3)

Questo procedimento equivale a effettuare una media sull’entropia dei simboli appartenenti ad unsupersimbolo X(k) enorme (ovvero grande a tal punto da inglobare tutta sequenza con il passaggioal limite);

∙ la seconda definizione si ricava col calcolo dell’entropia di un simbolo molto ’lontano’ una volta notitutti i precedenti:

H′∞ (X) = limk→∞

H (Xk ∣Xk−1Xk−2 . . . X1 ) (2.4)

Dimostriamo ora che i due limiti esistono finiti e che coincidono:

H∞(X) = H′∞(X) (2.5)

Dimostrare che il secondo limite esiste è relativamente facile e lo si fa sfruttando in maniera astuta l’ipotesidi stazionarietà. Sicuramente possiamo scrivere

0 ⩽ H (Xk ∣Xk−1Xk−2 . . . X1 ) ⩽ H (Xk ∣Xk−1Xk−2 . . . X2 )︸︷︷︸Un simbolo in meno (X1)!

in quanto l’entropia è sempre maggiore o uguale zero e, rimuovendo un simbolo (in questo caso X1), nonpuò che aumentare (o al limite rimanere costante) visto che la presenza di X1, unitamente al fatto chec’è memoria, costituiva un’informazione in più nell’ambito della nostra sequenza. Se la nostra sorgente è

1Le variabili aleatorie smettono di essere indipendenti fra loro.

20

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE 21

stazionaria, i pedici temporali possono essere amabilmente traslati di una posizione senza che si modifichiil risultato:

H (Xk ∣Xk−1Xk−2 . . . X2 ) = H (Xk−1 ∣Xk−2Xk−3 . . . X1 )︸︷︷︸Traslazione di una posizione

Ora possiamo immaginare di iterare questi passaggi, rimuovendo di volta in volta un simbolo e successi-vamente traslando2; l’entropia, ad ogni rimozione, sarà sempre ≤ rispetto al passo precedente: abbiamoquindi una successione di elementi non decrescenti e finiti, cosicché esiste il limite. I due limiti, inoltre,coincidono: possiamo dimostrarlo tramite la chain rule (vedi la 1.17) e la regola di Cesàro in quanto si ha,portando k all’infinito3:

H(

X(k))

k=

1k

k

∑i=1

H (Xi ∣Xi−1 . . . X1 )Cesa ro−−−−→ H′∞ (X)

Se la sorgente è DMS si ha il seguente caso particolare:

H′∞(X) = H(X) (2.6)

In termini generali possiamo quindi scrivere:

0 ⩽ H∞ (X) ⩽ H (X) ⩽ log2 L (2.7)

Come abbiamo già più volte sottolineato, il segno ≤ fra H′∞(X) e H(X) diventa un = nel caso senzamemoria; il segno ≤ fra H(X) e log2 L, invece, diventa un = nel caso di distribuzione uniforme (simbolitutti equiprobabili): tale tipologia di p.d.f.4 è infatti quella che massimizza l’entropia e la porta al suovalore limite.Concludendo, si ha massimo flusso informativo in caso di:

∙ assenza di memoria;

∙ indipendenza dei simboli;

∙ equiprobabilità dei simboli.

Un esempio potrebbe essere costituito da una sorgente binaria (bernoulliana) senza memoria e con simboliequiprobabili.

2.4 Ridondanza e confronto fra sorgenti

Si definisce ridondanza di sorgente la quantità:

ℛ =Hmax − H∞ (X)

Hmax= 1− H∞ (X)

log2 L⩽ 1 (2.8)

Come si può notare dalla formula, questo parametro è compreso fra 0 e 1 (compresi): il numeratore puòinoltre essere scritto nel seguente modo

Hmax − H∞ (X) =

due effetti provocano la ridondanza!︷︸︸︷Hmax − H (X)︸︷︷︸

dovuto alla non equiprobabilità

+ H (X)− H∞ (X)︸︷︷︸legato alla memoria della sorgente

(2.9)

Nel caso particolare di Hmax = H∞ (X) i simboli sono indipendenti ed equiprobabili: infatti, nella 2.9,entrambi i contributi messi in evidenza diventano pari a zero.

Hmax − H (X)︸︷︷︸equiprobabili (Hmax=H(X))

+ H (X)− H∞ (X)︸︷︷︸sorgente senza memoria (H(X)=H∞(X))

= 0⇒ ℛ = 0

2FFffatto?3Il termine H (Xi ∣Xi−1 . . . X1 ) è l’ak dell’enunciato della regola di Cesaro.4Probability Density Funciton.

21


Tramite il parametro ridondanza possiamo fare interessanti paragoni fra due sorgenti; consideriamo, atitolo d’esempio, due sorgenti tempo-discrete: la prima sia una sorgente avente symbol-rate Bs1 e entropiaH∞(X), mentre la seconda sia una sorgente ’ottima’ (generatrice di simboli indipendenti ed equiprobabili)con symbol-rate Bs1 e entropia massima (log2 L). Avremo, con semplicissime considerazioni:

sorgente 1→ Bs1 ⋅ H∞ (X)

sorgente 2→ Bs2 ⋅ log2 L

}[Shannon

sec

]Imponendo che i due flussi informativi si equivalgano otteniamo

Bs1 ⋅ H∞ (X) = Bs2 ⋅ log2 L⇒ Bs1

Bs2=

log2 LH∞ (X)

=Hmax

H∞ (X)

Osservando questa relazione possiamo fare due interessanti osservazioni:

∙ la sorgente 1 diventa equivalente alla sorgente ’ideale’, ed emette quindi massimo contenuto infor-mativo, solo se H∞(X) = Hmax;

∙ se la sorgente è un po’ ridondante (entropia non massima) sarà necessario emettere più simboli, equindi più bit, per ottenere la stessa informazione della sorgente ottima (che ha massima efficienza).

ESEMPIO:Consideriamo lingua italiana: il nostro alfabeto ha 22 simboli (21 lettere più lo spazio). Se essi fossero

indipendenti ed equiprobabili, l'entropia della nostra lingua sarebbe:

Hmax = log2 L = 4, 46Sh

simbolo

Questo signi�ca che servirebbero in media 4,46 bit per rappresentare ciascun carattere o, anche, che

ciascun carattere porterebbe un quantitativo d'informazione pari a 4,46 Shannon. In realtà le lingue

umane non possono avere entropia massima in virtù del fatto che esistono regole grammaticali e

regole lessicali: la loro presenza rende i caratteri non equiprobabili e questo, di conseguenza, abbassa

l'entropia

H < Hmax

Considerando ad esempio il testo dell'Inferno di Dante, l'entropia risulta essere pari a 3,97 Shannon per

simbolo, quantitativo sensibilmente inferiore rispetto ai 4,46 teorici. Quanto detto potrebbe generare,

nel cuore dell'impulsivo lettore, un moto di indignazione e protesta verso il linguaggio umano, così

dannatamente ridondante: non vi è tuttavia da scaldarsi visto che, in realtà, ciò ci permette di

correggere gli errori sulla base della storia passata dei simboli. Chiunque, infatti, potrebbe capire che

in questa frase

Oggi avevo sete e ho bevuto dell'aqua.

manca la lettera 'c'. Perché possiamo dirlo? Perché la storia passata dei simboli, ovvero le lettere

precedenti, ci suggeriscono che la parola non riconosciuta si riferisce a qualcosa di liquido ('Avevo

sete') che contiene le lettere 'a', 'q' e 'u'. Inoltre, sappiamo che è molto probabile trovare una 'c'

prima della 'q' (simboli non equiprobabili !) per cui il gioco è fatto!

2.5 Tecniche di compressione dei dati

Una sorgente ridondante non è la soluzione migliore per la trasmissione di dati, visto che l’idealesarebbe avere simboli indipendenti, equiprobabili e assenza di memoria. Possiamo tuttavia migliorarel’efficienza di una sorgente (ovvero aumentarne l’entropia) tramite un dispositivo, denominato codifica-tore di sorgente (vedi figura 2.2), da posporre alla sorgente stessa per cercare, a parità di informazione, didiminuire il più possibile il numero di bit da trasmettere. In questo consiste l’operazione di compressionedei dati.

22


Figura 2.2: Schema di trasmissione col codificatore di sorgente

Indicheremo con C(x) una parola di codice, ovvero una stringa binaria lunga l(x) bit. L’operazione dicodifica (codifica di sorgente) dev’essere chiaramente invertibile dal ricevente per poter fruire dell’informa-zione. Una delle condizioni che si deve avere perché il codice sia invertibile (necessaria ma non sufficiente)è che a due simboli diversi corrispondano due codeword diverse (codice non singolare):

C (xi) ∕= C(xj)

, ∀i ∕= j (2.10)

Un codice non singolare potrebbe non essere decodificabile in maniera univoca (e quindi non invertibi-le, vedi esempio di seguito); si parla invece di codice univocamente decodificabile (invertibile) se, data unasequenza qualunque, si ha:

C (x1) , C (x2) , . . . , C (xM) ⇔univocamente

x1, x2, . . . , xM (2.11)

Eventualmente, le parole di codice possono essere di lunghezza diversa (codice a lunghezza variabile): sidefinisce allora la lunghezza media di un codice:

ℒ(C) = E[l(x)] = ∑x∈X

l(x)p(x) (2.12)

Inoltre, un codice si dice a prefisso (o codice istantaneo)5 se nessuna parola di codice C(x) è prefissodi un’altra. Tali codici sono sempre univocamente decodificabile. Questo aspetto verrà approfondito nelparagrafo 2.5.1.

ESEMPIO:

Si osservi la tabella 2.1. Il codice 1 è non singolare, in quanto ad ogni simbolo è associata una

Simbolo p(x) Codice 1 Codice 2 Codice 3

x1 1/2 1 1 0

x2 1/4 00 01 01

x3 1/8 01 001 011

x4 1/8 10 0000 111

Tabella 2.1: Qualche esempio per la nomenclatura dei codici

codeword diversa. Stesa cosa possiamo dire dei codici 2 e 3 (i quali, come vedremo di seguito, hanno

un'ulteriore e importante proprietà). La lunghezza media del codice 1 è:

1 ⋅ 12+ 2 ⋅ 1

4+ 2 ⋅ 1

8+ 2 ⋅ 1

8=

32

5In quanto la codifica è istantanea.

23


Il codice 1 non è tuttavia invertibile perché non è univocamente decodi�cabile: per esempio

1001

potrebbe contemporaneamente essere x1x2x1 oppure x4x3, ma non possiamo saperlo. Come si può fa-

cilmente veri�care, i codici 2 e 3 sono invece univocamente decodi�cabili in quanto non vi è ambiguità.

In particolare:

∙ il codice 2 è a pre�sso in quanto nessuna codeword è pre�sso di altre. Inoltre esso ha lunghezza

media

2 ⋅ 12+ 2 ⋅ 1

4+ 2 ⋅ 3

8=

74

Tale lunghezza ci soddisfa? Abbastanza perché è mediamente inferiore a quella ipotetica (si

poteva supporre che con 4 simboli avremmo avuto bisogno di 2 bit per simbolo), visto che

abbiamo usato un diabolico trucco, cioè quello di dare alle parole più probabili una lunghezza

minore!

∙ il codice 3 è decodi�cabile, ma dobbiamo per forza attendere che �nisca la sequenza per poter

comprendere quale sia stata la parola codi�cata (cosa che non accadeva nel codice 2): ad

esempio, potremmo confondere x2 con x3 se non trasmettiamo l'ultimo bit di quest'ultima

parola di codice.

2.5.1 Codici a prefisso e disuguaglianza di Kraft

Per i codici a prefisso, siccome nessuna parola è prefisso di un’altra, le parole di codice possono essereassociate alle foglie di un albero. Consideriamo il codice 2 (tabella 2.1): una possibile rappresentazione adalbero è riportata in figura 2.3. Tale albero ha 21 nodi di ordine 1, 22 nodi di ordine 2 (potenziali, in realtà

Figura 2.3: Albero di un codice a prefisso

poi sono soltanto 2), etc. . . Generalizzando, ogni albero ha sempre 2k potenziali nodi di ordine k.

TEOREMA: disuguaglianza di Kraft(-McMillan)6

6Da Wikipedia: In coding theory, Kraft’s inequality gives a condition for the existence of a uniquely decodable code for a given set of codewordlengths. Its applications to prefix codes and trees often find use in computer science and information theory. More specifically, Kraft’s inequalitylimits the lengths of codewords in a prefix code: if one takes an exponential function of each length, the resulting values must look like a probabilitymass function. Kraft’s inequality can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being moreexpensive.

∙ If Kraft’s inequality holds with strict inequality, the code has some redundancy.

∙ If Kraft’s inequality holds with strict equality, the code in question is a complete code.

∙ If Kraft’s inequality does not hold, the code is not uniquely decodable.

24


Per ogni codice a prefisso con parole di lunghezza l1 ≤ l2 ≤ l3 ≤ . . . ≤ lL bit si ha:

L

∑i=1

2−li ≤ 1 (2.13)

Inoltre, esiste sempre un codice a prefisso con lunghezza l1 ≤ l2 ≤ l3 ≤ . . . ≤ lL in grado di soddisfare ladisuguaglianza di cui sopra.

Dimostrazione: iniziamo col dimostrare la necessarietà. Il codice a prefisso con parole di lunghezzal1 ≤ l2 ≤ l3 ≤ . . . ≤ lL può essere generato da un albero che si estende al massimo fino all’ordine lL, con2lL potenziali nodi. Se però posizioniamo una parola di codice all’ordine li andiamo in realtà ad eliminaretutti i potenziali rami ’figli’ di quella parola, i quali sono 2lL−li . Abbastanza ovvio è il fatto che il numerodi nodi che andremo in tutto a eliminare non potrà essere maggiore del numero totale di nodi 2lL :

L

∑i=1

2lL−li ⩽ 2lL

Se ora dividiamo per 2lL quel che otteniamo è la disuguaglianza di Kraft. Ora passiamo a dimostrare lasufficienza: supponiamo che le nostre lunghezze abbiano soddisfatto la disuguaglianza. . . riusciamo oraa costruire un codice a prefisso? Immaginiamo di avere l’albero completo e di posizionare presso un suonodo una certa parola di codice C1 di lunghezza l1. Così facendo avremo seccato 2lL−l1 nodi, ovvero il

2lL−l1

2lL= 2−l1%

dei nodi di ordine massimo (cioè i più ’figli di tutti’7). Questo implica che sarà rimasta una percentualepari a

(1− 2−l1)%

di nodi di ordine massimo. Possiamo ora posizionare una parola di lunghezza l2? Certamente sì perchéKraft ci garantisce che sicuramente un nodo di lunghezza l2 sarà sopravvissuto (sono sopravvissuti quellidi ordine massimo, ovvero i figli, quindi sicuramente sono ’vivi’ anche quelli di ordine l2, cioè i padri).Giunti qui ci siamo mangiati già

2−l1 + 2−l2

nodi di ordine massimo (in percentuale). Questa quantità è però inferiore ad 1 per la disuguaglianza diKraft, quindi esisteranno ancora dei nodi di ordine lL (massimo) e quindi anche nodi di ordine inferiore(padri): esisterà ad esempio un nodo di ordine l3 per posizionare la terza parola, la quale farà seccare2lL−l3 nodi di ordine massimo. Rimarrà quindi il

2−l1 + 2−l2 + 2−l3

percento dei nodi di ordine massimo. Siccome la disuguaglianza di Kraft è tuttavia ancora soddisfatta,sarà presente un nodo-padre di ordine l4 per la quarta parola visto che alcuni nodi-figli di ordine massimosono ancora vivi, etc. . . Al passo k la disuguaglianza di Kraft sarà ancora soddisfatta e varrà

k

∑i=1

2−li︸︷︷︸% nodi (ordine max) morti

⩽ 1︸︷︷︸totale

Quindi i nodi sono sempre sufficienti per poter posizionare le nostre parole di codice!Concludendo, la disuguaglianza di Kraft ci dice come prendere le lunghezze delle parole; tal McMil-

lan ha dimostrato che qualunque codice univocamente decodificabile ha lunghezze che soddisfano taledisuguaglianza.

7Detto così è ambiguo eh. . . ?

25


2.5.2 Un’applicazione della disuguaglianza di Kraft: i codici a prefisso di Shannon-Fano

I codici di Shannon-Fano8 sono un particolare tipo di codici a prefisso con lunghezze lk intere sceltesecondo la relazione:

log21

p (x)⩽ l (x) < log2

1p (x)

+ 1⇔ l (x) =⌈

log21

p (x)

⌉= ⌈I(x)⌉ l (x) intero (2.14)

Mostriamo che tali codici soddisfano la disuguaglianza di Kraft verificando la prima parte della disugua-glianza soprastante:

l(x) ⩾ log21

p(x)⇒ 2l(x) ⩾ 2log2

1p(x) ⇒ 2l(x) ⩾

1p(x)

⇒ 2−l(x) ⩽ p(x)

Applicando al sommatoria a destra e sinistra otteniamo proprio la nostra diseguaglianza!

∑x

2−l(x) ⩽ ∑x

p(x) = 1

ESEMPIO:Se proviamo a costruire il relativo codice a pre�sso scopriamo che una possibile soluzione è quella del

codice avente albero come quello in �gura 2.3 con probabilità C(x1) = 0, 5; C(x2) = 0, 25; C(x3) =0, 125; C(x4) = 0, 125.

2.6 Teorema della codifica di sorgente (I teorema di Shannon)

Nella teoria dell’informazione, il Primo teorema di Shannon (o Teorema della codifica di sorgente), stabili-sce dei limiti alla massima compressione possibile di un insieme di dati e definisce il significato operativodell’entropia. Il teorema stabilisce che, per una serie di variabili aleatorie indipendenti ed identicamentedistribuite (i.i.d.) di lunghezza che tende ad infinito, non è possibile comprimere i dati in un messaggiopiù corto dell’entropia totale senza rischiare di perdere informazione. Al contrario, compressioni arbitra-riamente vicine al valore di entropia sono possibili, con probabilità di perdita di informazione piccola apiacere (a patto di inventarsi un codice molto buono!).

Un’altra possibile formulazione di questo teorema può essere: qualunque codice univocamente decodi-ficabile applicato ai simboli Xn di una sorgente stazionaria ha lunghezza media non inferiore all’entropiadella sorgente H(X):

E[l(x)] ≥ H(X) (2.15)

Inoltre esistono codici per i quali:E ⌈l(x)⌉ ⩾ H(X) + 1 (2.16)

Dimostrazione (1∘ parte): facciamo l’ipotesi che il codice sia univocamente decodificabile (la disugua-glianza di Kraft deve quindi per forza essere rispettata). Possiamo scrivere, usando le definizioni:

H (X)− E [l (x)] = ∑x

p (x) log1

p (x)−∑

xp (x) l (x) = ∑

xp (x) log

1p (x)

−∑x

p (x) log2 2l(x)︸︷︷︸=l(x) Che trucco!

=

= ∑x

p (x) log1

p (x) 2l(x)=∑

xp (x) log

2−l(x)

p (x)⩽ log2 e ∑

xp (x)

[2−l(x)

p (x)− 1

]

Dove nell’ultimo passaggio abbiamo usato la disequazione

log2 x ⩽ (x− 1) log2 e (2.17)

8Robert Mario Fano (Torino, 1917 - vivente) è un informatico e ingegnere italiano-statunitense. È docente emerito di ingegneriaelettronica e di scienza dell’informazione presso il Massachusetts Institute of Technology. Fano è noto prevalentemente per il suolavoro sulla teoria dell’informazione, avendo sviluppato (in collaborazione con Claude Shannon) i codici di Shannon-Fano. Neiprimi anni ’60, fu partecipe dello sviluppo dei sistemi di computer in time-sharing ed ha prestato servizio come direttore del ProjectMAC del MIT fin dalla sua fondazione nel 1963 e fino al 1968.

26


già dimostrata nel paragrafo 1.3.2. Ora possiamo applicare la disuguaglianza di Kraft (verificata peripotesi) e scrivere:

log2 e ∑x

p (x)

[2−l(x)

p (x)− 1

]= log2 e ∑

x

(2−l(x) − p (x)

)= log2 e︸︷︷︸

⩾0

⩽0︷︸︸︷⎛⎜⎜⎜⎝ ∑x

2−l(x)

︸︷︷︸⩽1 PER KRAFT!

−1

⎞⎟⎟⎟⎠ ⩽ 0

Dimostrazione (2∘ parte): troviamo ora almeno un codice che soddisfi la 2.16. Scegliamo ad esempioil codice di Shannon-Fano (equazione 2.14) e moltiplichiamo a sinistra e a destra per p(x):

log21

p (x)⩽ l (x) < log2

1p (x)

+ 1 ⇒ p (x) l (x) < p (x) log21

p (x)+ p (x)

Ora applichiamo l’operatore sommatoria:

∑x

p (x) l (x)︸︷︷︸E[l(x)]

< ∑x

p (x) log21

p (x)︸︷︷︸H(X)

+∑x

p (x)︸︷︷︸1

E [l (x)] < H (X) + 1

Perfetto!

Si tenga tuttavia presente che i codici di Shannon-Fano non sono i codici ottimi: osserviamo infatti ilseguente

ESEMPIO:Abbiamo una sorgente binaria che emette i due simboli in tabella 2.2. Secondo Shannon-Fano do-

vremmo usare ben 4 bit d'informazione per la parola meno probabile, principio che a prescindere non

è sbagliato in quanto conviene usare le parole di codice più corte per i simboli più probabili, ma che in

questo caso si rivela una scelta piuttosto stupidina9 in quanto basterebbe un unico bit per codi�care

sia x1 che x2.

p(x) I(x) l(x) (Shannon-Fano)

x1 0,1 3,32 4 (!!!)

x2 0,9 0,15 1

Tabella 2.2: Caso sfortunato di Shannon-Fano

2.7 Codice di Huffman

Nel 1951 a David Huffman e ad un suo collega al corso del MIT di Teoria dell’Informazione vennedata la scelta tra una tesi scritta o un esame. Il docente, Robert M. Fano, assegnò una tesi sul problemadi trovare il codice binario più efficiente. Huffman, incapace di dimostrare un qualsiasi codice che fosse ilpiù efficiente, si stava rassegnando all’idea di dover studiare per l’esame, quando gli venne l’idea di usareun albero binario ordinato in base alla frequenza, e così dimostrò velocemente che questo metodo era ilpiù efficiente.

Un’idea simile era stata usata in precedenza nella codifica di Shannon-Fano, ma Huffman sistemò lasua più grande lacuna costruendo un albero ascendente anziché uno discendente.

La codifica di Huffman, pubblicata su A Method for the Construction of Minimum-Redundancy Codes (UnMetodo per la Costruzione di Codici a Ridondanza Minima), usa un metodo specifico per scegliere la

9Bricconcello!

27


rappresentazione di ciascun simbolo ed è stato dimostrato che è il più efficiente sistema di compressionedi questo tipo: nessun’altra mappatura di simboli in stringhe binarie può produrre un risultato più brevenel caso in cui le frequenze di simboli effettive corrispondono a quelle usate per creare il codice. Oggi lacodifica di Huffman è spesso usata come complemento di altri metodi di compressione: sono esempi ilDeflate (l’algoritmo di PKZIP, e dei successori ZIP e WinRar) e codec multimediali quali JPEG ed MP3.

I passi per costruire un codice di Huffman sono 3:

1. si ordinano le probabilità in ordine decrescente;

2. si uniscono le due minori in un nuovo nodo (unico) e a questo nodo viene associata la somma delleprobabilità;

3. si ripetono i punti 1 e 2 fino all’esaurimento.

Iterando questo procedimento otterremo in men che non si dica il grafico binario che garantisce lalunghezza media del codice migliore in assoluto.

2.8 Codifica a blocchi

Figura 2.4: Schema della codifica a blocchi

Nella codifica a blocchi, invece dei simboli, codifichiamo gruppi di simboli ovvero dei supersimboli(vedi figura 2.4). I limiti teorici riguardanti il numero medio di bit per supersimbolo rimangono peròinvariati rispetto ai casi visti fin’ora:

H(

X(k))⩽ E

[l(

X(k))]

< H(

X(k))+ 1 (2.18)

Se dividiamo per k otteniamo:

H(

X(k))

k︸︷︷︸Per k→∞ diventa H∞(X)

⩽E[l(

X(k))]

k︸︷︷︸Per k→∞ diventa H∞(X)

<H(

X(k))+ 1

k=

H(

X(k))

k+

1k

(2.19)

Il primo (entropia della sorgente) e il secondo termine (numero medio di bit per simbolo) vengono acoincidere; codificando i blocchi possiamo perciò avvantaggiarci della memoria del codice e avvicinarcisempre di più al limite ’destro’ della nostra doppia disequazione (1/k sempre più piccolo).

Se poi aggiungiamo l’ipotesi di sorgente DMS si ha che:

H(X(k)) = kH(X) (2.20)

quindi la 2.19 diventa

kH (X)

k⩽

E[l(

X(k))]

k<

kH (X)

k+

1k

H (X) ⩽E[l(

X(k))]

k< H (X) +

1k

Il vantaggio ulteriore è che, oltre ad aversi 1/k→ 0 per k→ ∞, potremo contare su un’entropia maggiorevista la disequazione H∞(X) ≤ H(X) (vantaggio ulteriore rispetto al caso di simbolo-per-simbolo, chemediamente andrà peggio come mostriamo nel seguente esempio).

28


ESEMPIO:Sorgente binaria senza memoria con la distribuzione di probabilità mostrata in tabella 2.3. L'entropia

p(x)

x1 0,1x2 0,9

Tabella 2.3: Distribuzione di probabilità del nostro esempio

è pari a

H(X) = 0, 47

Shannon per simbolo. Non abbiamo tuttavia altra scelta che usare un bit per simbolo, visto che

abbiamo scelto la codi�ca simbolo-per-simbolo. . . La cosa è abbastanza deludente perché siamo ben

lontani dall'entropia H(X), ma che succede se codi�chiamo supersimboli costituiti da due simboli

'elementari' (tabella 2.4)?

p(X(2))

x1x1 0,01x1x2 0,09x2x1 0,09x2x2 0,81

Tabella 2.4: Distribuzione di probabilità del nostro esempio, con supersimboli

Ora possiamo costruire il nostro alberino post-natalizio con il metodo di Hu�man (vedi �gura

2.5): calcolando la lunghezza media otteniamo 1, 29 bit per supersimbolo, ovvero 1, 29/2 = 0, 645

Figura 2.5: L’alberino post-natalizio

bit/simbolo, risultato molto più vicino a H(X) e sicuramente più soddisfacente dell'1 bit/simbolo un

po' schifoso trovato con la codi�ca simbolo-per-simbolo.

2.9 Codifica a corse

Quando la dipendenza statistica fra i simboli successivi si manifesta con la presenza di sequenze,più o meno lunghe, di simboli eguali (corse), come avviene per il segnale fax con successioni di pixelbianchi e neri, può convenire una codifica delle lunghezze di tali corse (magari secondo Huffman) edell’informazione relativa ai simboli che le costituiscono.

2.10 Codice di Lempel-Ziv

I codici di sorgente fin’ora esaminati richiedono la conoscenza delle statistiche della sorgente (e vengo-no per questo chiamati codici entropici, visto che l’entropia è matematicamente calcolabile a partire dalladistribuzione di probabilità). Un codice universale che non richiede tale conoscenza statistica, dando

29


in generale prestazioni inferiori (tali tipologie di codici si dicono universali), è quello di Lempel-Ziv che,data la grande versatilità, è uno standard de facto per la compressione di dati. Tale procedimento è infattiutilizzato nella codifica delle immagini in formato GIF (e, facoltativamente, nei file TIFF) ed è il risultatodelle modifiche apportate nel 1984 da Terry Welch ai due algoritmi sviluppati nel 1977 e nel 1978 da JacobZiv e Abraham Lempel, e chiamati rispettivamente LZ77 e LZ78. Funziona costruendo un dizionario nelquale sono elencate le diverse frasi (generalmente di lunghezza diversa) ottenute scorrendo la sorgente(supposta binaria in questo caso). Ciascuna frase è data dalla concatenazione di una precedente con unacifra binaria (1 oppure 0). Successivamente si codificano le frasi con parole di lunghezza fissa, che indica-no la posizione in binario della frase precedente seguita dal nuovo bit della sorgente. Si può dimostrareche la codifica di lunghe sequenze di n bit è efficiente, cioè il numero di bit richiesto si avvicina a nH∞(X).

ESEMPIO:Abbiamo la sequenza:

101011110101111100100111011100001101100000101

La suddivisione in frasi dà

1-0-10-11-110-101-111-100-1001-1101-1100-00-11011-000-001-01

cioè 16 diverse frasi ciascuna codi�cabile con 5 bit: i primi 4 sono l'indice della parola del dizionario che

costituisce tutti i bit tranne quello più a destra (il meno signi�cativo, per intenderci), mentre l'ultimo

è il bit che bisogna aggiungere alla parola indicata dai primi 4 bit per ottenere quella corrente. Ad

esempio:

Posizione nel dizionario | Frase nel dizionario | Codeword

0000 | - | -

0001 | 1 | 0000 1

0010 | 0 | 0000 0

0011 | 10 | 0001 0

0100 | 11 | 0001 1

La frase 10 si ottiene concatenando la frase di posizione 0001 (cioè 1) con uno 0 (1#0 = 10), mentre

la frase 11 si ottiene concatenando quella di posizione 0001 (sempre 1) con un 1 (1#1=11).

2.11 Considerazioni finali: lossy o lossless?

I codici illustrati fin’ora vengono applicati a sorgenti discrete e non comportano perdita d’informa-zione: vengono quindi chiamati codici lossless, ovvero senza perdita. Esistono tuttavia anche tecniche dicodifica lossy (JPEG, MP3) le quali comprimono moltissimo e - in sostanza - si basano sulla legge deigrandi numeri10. Per esempio, consideriamo una sorgente binaria con probabilità p{x = 1} = 90% ep{x = 0} = 10%: guardando lunghissime sequenze potremo molto probabilmente constatare la presenzadi (circa) un 90% di ’1’ e un 10% di ’0’. Ipotizziamo inoltre di considerare n-ple di 1000 bit: le parolepossibili sono 21000, ma fra tutte quelle possibili saranno molto frequenti quelle che hanno circa il 90% di’1’ e il 10% di ’0’. Una possibile scelta sarebbe quella elencare tale relativamente piccolo sottoinsieme ditutte le 21000 parole possibili e codificare soltanto quelle. Così facendo risparmieremmo tantissimi bit inquanto dovremmo codificare un numero molto piccolo di sequenze se confrontato con tutte quelle possi-bili; l’altra faccia della medaglia è l’incapacità di codificare tutte le sequenze, con la conseguente perditadi informazione.

Tale perdita d’informazione è assolutamente inevitabile se abbiamo delle sorgenti continue: primadi poterle codificare dovrò campionarle e questo genererà un errore di quantizzazione impossibile darecuperare.

10La legge dei grandi numeri, detta anche legge empirica del caso oppure teorema di Bernoulli (in quanto la sua prima formu-lazione è dovuta a Jakob Bernoulli), descrive il comportamento della media di una sequenza di n variabili casuali indipendenti ecaratterizzate dalla stessa distribuzione di probabilità (n misure della stessa grandezza, n lanci della stessa moneta ecc.) al tenderead infinito della numerosità della sequenza stessa (n). In altre parole, grazie alla legge dei grandi numeri, possiamo fidarci che lamedia che calcoliamo a partire da un numero sufficiente di campioni sia sufficientemente vicina alla media vera.

30

Capitolo 3

La codifica di canale e la capacità

Se il codificatore di sorgente è ’di qualità’ e ha fatto il suo lavoro (quindi non l’abbiamo comprato alLidl) non vi sarà più molta ridondanza all’uscita. Non abbiamo però finito il lavoro: dobbiamo trasportarequesti bit a destinazione! Purtroppo il canale che tali bit dovranno attraversare è tutt’altro che ideale efavorisce intrinsecamente, al suo interno, delle transazioni probabilistiche che si manifestano in disturbi(interferenze, rumori, etc. . . ). Il canale quindi non è deterministico: non sappiamo cosa esce, ma sappiamocosa potrebbe uscire.

3.1 Canale discreto senza memoria

Figura 3.1: Canale discreto senza memoria

Detto anche DMC (Discrete Memoryless Channel) ha la caratteristica si poterci far osservare anche soloun simbolo alla volta, senza dover specificare l’indice temporale nelle varie formule in cui compare l’ope-ratore di probabilità: per questo, considerando lo schema in figura 3.1, possiamo ad esempio dire che Ykdipenderà soltanto da Xk e da nessun’altro simbolo.

Volendo, possiamo graficare la probabilità che un certo simbolo X generi il relativo Y in uscita dalcanale facendo uso di un grafo bipartito, dove ad ogni freccia sono associate delle probabilità (vedi figura3.2). Tutte le probabilità di transizione dal nodo generico i al nodo generico j possono perciò essere postein una matrice P, detta matrice di transizione, i cui elementi saranno molto semplicemente

pij = p{

Y = yj ∣X = xi}

(3.1)

Supponiamo di conoscere solamente la P di una certa sorgente: trasmettiamo i nostri simboli X at-traverso il canale e vediamo che accade alle Y. Ebbene, si può dimostrare che si ha una riduzione diincertezza legata all’osservazione del canale:

H(X∣Y) ≤ H(X) (3.2)

Tale riduzione di incertezza1 può essere quantificata con un parametro che chiameremo informazionemutua:

I(X; Y) = H(X)− H(X∣Y) (3.3)

Com’è facile accorgersi, questo parametro viene quantificato in Shannon per simbolo. Inoltre, soggiacealle seguenti proprietà:

1Come sappiamo, l’incertezza e l’informazione sono entrambe legate al concetto di entropia.

31

32 CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

Figura 3.2: Il grafo bipartito

Figura 3.3: Esempio con grafo bipartito

1. è sicuramente maggiore di zero, anche perché è obbligatorio che s’abbia H(X) ≥ H(X∣Y);

2. vale I(X; Y) = I(Y; X) = H(Y)− H(Y∣X). Dimostrazione:

H (X)− H (Y ∣X ) = H (X)− [H (X, Y)− H (Y)] = H (Y)− H (X ∣Y )

3.2 Capacità di canale

Abbastanza ragionevole è che i migliori canali siano quelli che fanno ’passare’ molta informazione. Macome facciamo a quantificare tale capacità per i nostri canali? Semplice: con la capacità di canale2! Taleparametro è pari a:

C = maxp(x)

I(X; Y) (3.4)

Provando a dare in pasto al canale più informazione rispetto alla sua capacità inevitabilmente perde-remo qualcosa: la capacità è infatti un metro di misura per la massima quantità di informazione chepossiamo convogliare nel nostro canale.

Nei prossimi paragrafi ricaveremo la capacità di canale in alcuni casi notevoli.

3.2.1 Canale deterministico

Detto anche canale noiseless, è un canale inesistente perché privo di qualsiasi effetto di non idealità: ogninodo j (d’ingresso) del grafo bipartito finisce in un nodo i con probabilità 1, quindi non sono possibili

2Gioco di parole da quattro soldi. Anzi tre.

32

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ 33

’fraintendimenti’. In tal caso, l’informazione mutua è pari a

I(X; Y) = H(X)− H(X∣Y) = H(X) (3.5)

in quanto l’entropia condizionata è nulla. La capacità del canale è perciò quella massima possibile(eventualità assolutamente plausibile per qualcosa di ideale, come abbiamo in questo caso):

C = maxp(x)

I(X; Y) = maxp(x)

H(X) = log2 N (Ottenuta con distribuzione uniforme) (3.6)

Prendendo lo stesso grafo del canale noiseless e aggiungendo qualche nuova transizione (rompendo cioèla corrispondenza 1-a-1 e aggiungendo del rumore), la capacità non potrà far altro che calare.

3.2.2 Canale binario simmetrico

Figura 3.4: Canale binario simmetrico

Detto anche BSC (Binary Symmetric Channel), è forse il caso notevole per eccellenza (vedi figura 3.4).Calcoliamo l’informazione mutua:

I (X; Y) = H (X)− (X ∣Y ) = H (X)−

⎡⎢⎣p (y1)

ℋ(p)︷︸︸︷p (X ∣Y = y1) +p (y2)

ℋ(p)︷︸︸︷p (X ∣Y = y2)

⎤⎥⎦︸︷︷︸

Caso della variabile bernoulliana!

= H (X)−ℋ(p)

(3.7)Ora siamo pronti a ricavare anche la capacità:

C = maxp(x)

I(X; Y) = maxp(x)

[H (X)−ℋ (p)] = 1−ℋ (p) (Ottenuta con bit d’ingresso equiprobabili) (3.8)

Il risultato commentato è riportato in figura 3.5.

3.2.3 Canale binario a cancellazione

Detto anche BEC (Binary Erasure Channel), comporta la possibilità che - in uscita al canale - alcuni valorisi cancellino (erasure). Il caso tipico in cui questa schematizzazione è valida è quello della trasmissione deipacchetti agli alti livelli della pila OSI; in generale si avrà un campo che serve a controllare l’integrità ditali pacchetti: in base a tale campo potremo conservare il nostro pacchetto oppure scegliere di buttarlo via(cioè cancellarlo).

Calcolo della capacità: iniziamo con il determinare l’informazione mutua.

I(X; Y) = H(X)− H(X∣Y) = H(Y)− H(Y∣X) =

= H (X)−

⎡⎢⎣p (y1) H (X ∣Y = y1 )︸︷︷︸=0 (il risultato è certo: x1)

+p (y2) H (X ∣Y = y2 )︸︷︷︸=0 (il risultato è certo: x2)

+p (e)

stessa prob. per x1 e x2︷︸︸︷H (X ∣Y = e )︸︷︷︸

=1: caso di massima incertezza

⎤⎥⎦(3.9)

33


Figura 3.5: Capacità in funzione di p per il BSC

Figura 3.6: Binary Erasure Channel

Calcoliamo p(e):

p (e) = p (e ∣x1 ) p (x1)︸︷︷︸=q

+p (e ∣x2 ) p (x2)︸︷︷︸=q

= q

⎛⎝p (e ∣x1 ) + p (e ∣x1 )︸︷︷︸=1

⎞⎠ = q

Quindi, in ultima analisi:I(X; Y) = H(X)− q (3.10)

Ora siamo pronti a sfruttare la definizione di capacità per calcolare quest’ultima:

C = maxp(x)

[H(X)− q] = 1− q Ottenuta con ingressi equiprobabili (3.11)

3.2.4 Canale Z

Si faccia riferimento alla figura 3.10 e si abbiano le seguenti probabilità a priori:

P(X = x1) = 1− π

P(X = x2) = π

34


Figura 3.7: Canale Z

Iniziamo col calcolarci l’informazione mutua:

I (X; Y) = H (Y)− H (Y ∣X )

Il secondo addendo (il più semplice da ricavare) è pari a:

H (Y ∣X ) = H (Y ∣X = x1 )︸︷︷︸=0, no incertezza!

p (x1) + H (Y ∣X = x2 ) p (x2) = H (Y ∣X = x2 )︸︷︷︸=ℋ(p)

p (x2)︸︷︷︸=π

= πℋ (p)

Il primo addendo può invece essere sviluppato nel seguente modo:

H (Y) = −p (y1) log2 p (y1)− p (y2) log2 p (y2) = ℋ (p (y2))

Ora con un po’ di pazienza ci troviamo:

p (y2) = p (y2 ∣X = x1 )︸︷︷︸=0 (impossibile)

p (x1) + p (y2 ∣X = x2 )︸︷︷︸=1−p

p (x2)︸︷︷︸=π

= (1− p)π

Indi per cui, facendo un passo indietro:

H (Y) = ℋ (p (y2)) = ℋ ((1− p)π)

Rimettendo insieme i pezzi abbiamo ottenuto finalmente la nostra informazione mutua:

I(X; Y) = ℋ [(1− p)π]− πℋ(p) = f (π, p)

Su p non possiamo agire, mentre possiamo mettere le mani su π: massimizziamo quindi la funzionetramite quest’ultima variabile. Calcoliamo la derivata:

∂ f (π, p)∂π

= 0 troviamo il massimo!

∂ f (π, p)∂π

=∂

∂π{ℋ [(1− p)π]− πℋ(p)} = ∂

∂π(ℋ [(1− p)π])−ℋ(p)

Ora sfruttiamo la preziosissima regolina:

ddxℋ (x) = log2

1− xx

(3.12)

Otteniamo:∂

∂π(ℋ [(1− p)π])−ℋ(p) = (1− p) log2

1− π (1− p)π (1− p)

−ℋ (p) = 0

35


Portando di là dall’uguale il termine ℋ(p) ed elaborando ancora:

(1− p) log21− π (1− p)

π (1− p)ℋ (p)

(1− p) log2

(1− π (1− p)

π

)− (1− p) log2 (1− p) = −p log2 p− (1− p) log2 (1− p)︸︷︷︸

ℋ(p)

(1− p) log2

(1− π (1− p)

π

)= −p log2 p

log2

(1− π (1− p)

π

)= − p

1− plog2 p = log2 p−

p1−p

Uguagliando gli argomenti dei logaritmi:

1− π (1− p)π

= p−p

1−p

1− π (1− p) = p−p

1−p

π = π0 =1

1− p + p−p

1−p

In definitiva, la capacità del canale Z è solo funzione di p e la sua espressione è più complicata nel caso dicanale simmetrico. Andando a graficare la capacità C (ottenuta inserendo come parametro π0) in funzioneotteniamo la figura 3.8.

Figura 3.8: Capacità del canale Z in funzione della probabilità p

3.2.5 Canale binario non simmetrico

Anche questa volta sia:P(X = x1) = 1− π

P(X = x2) = π

Come al solito partiamo dalla definizione di informazione mutua:

C = maxπ

I (X; Y) = H (Y)− H (Y ∣X )

Elaboriamo il secondo addendo (come al solito è il più facile):

H (Y ∣X ) = H (Y ∣X = x1)︸︷︷︸ℋ(p)

p (x1)︸︷︷︸π

+ H (Y ∣X = x2)︸︷︷︸ℋ(q)

p (x2)︸︷︷︸1−π

= πℋ (p) + (1− π)ℋ (q)

36


Figura 3.9: Canale binario non simmetrico

Passiamo ora al primo:

H (Y) = −p (y1) log2 p (y1)− p (y2) log2 p (y2) = ℋ (p (y1))

Ma abbiamo anche che p (y1) è pari a:

p (y1) = p (y1 ∣X = x1 )︸︷︷︸1−p

p (x1)︸︷︷︸π

+ (y1 ∣X = x2 )︸︷︷︸1−π

p (x2)︸︷︷︸ε

= (1− p)π + (1− π) ε

Di conseguenza:

H(Y) = ℋ[(1− p)π + (1− π)ε]

Quindi, rimettendo insieme i cocci, si ha:

I (X; Y) = ℋ [π (1− p) + (1− π) ε]︸︷︷︸H(Y)

− (πℋ (p) + (1− π)ℋ (ε))︸︷︷︸H(Y∣X )

Ora vogliamo trovare il massimo di questa funzione, visto che ci servirà per trovare il massimo del-l’informazione mutua e quindi la capacità: per trovare il massimo sfruttiamo le ben note derivate escriviamo

∂

∂πf (π, p, ε) = 0

[(1− p)− ε] log21− π (1− p)− ε (1− π)

π (1− p) + ε (1− π)︸︷︷︸d

d xℋ(x)=log21−x

x

−ℋ (p) +ℋ (ε) = 0

log21− π (1− p)− ε (1− π)

π (1− p) + ε (1− π)=ℋ (p)−ℋ (ε)

(1− p)− ε

1− π (1− p)− ε (1− π)

π (1− p) + ε (1− π)= 2

ℋ(p)−ℋ(ε)(1−p)−ε ≜ γ (p, ε)

Dopo svariati calcoli (che qui per brevità non riporteremo) si avrà quindi:

π0 =1− ε (1 + γ)

(1− p− ε) (1 + γ)

Ora sostituiamo π0 nell’espressione dell’informazione mutua ed ecco che abbiamo trovato la capacità delcanale non simmetrico.

I (X; Y) = ℋ [π0 (1− p) + (1− π0) ε]− π0ℋ (p)− (1− π0)ℋ (ε)

Si può verificare che i calcoli sono stati fatti correttamente provando a imporre p = ε e appurando che ilrisultato va a coincidere con il BSC.

37


Figura 3.10: Canale ’strano’

ESERCIZIO:

Si vuole calcolare la capacità del canale indicato in �gura 3.10: non è un canale banale in quanto la simmetria

può aiutarci solo parzialmente. Se chiamiamo per ipotesi Q la probabilità che all'ingresso del canale si presenti

x2 o x3Q = p (X = x2) = p (X = x3)

allora avremo che la probabilità di trasmissione di x1 sarà:

p(X = x1) = 1− 2Q

Passiamo ora alla determinazione della capacità vera e propria:

C = maxQ

I (X; Y) = maxQ{H (Y)− H (Y ∣X )}

Il secondo addendo può essere sviluppato nel seguente modo:

H (Y ∣X ) = H (Y ∣X = x1 )︸︷︷︸=0 no incertezza

p (x1) + H (Y ∣X = x2 )︸︷︷︸=ℋ(p)

p (x2) + H (Y ∣X = x3 )︸︷︷︸=ℋ(p)

p (x3) = 2Qℋ (p)

Ora passiamo al primo addendo, che è risaputamente più complicato:

H (Y) = −p (y1) log2 p (y1)− p2log2 p (y2)︸︷︷︸=Q

−p (y3) log2 p (y3)︸︷︷︸=Q

= −p (y1) log2 p (y1)− 2Qlog2Q

La probabilità p(y1) sarà:

p (y1) = p (y1 ∣X = x1 )︸︷︷︸evento certo ( = 1)

p (x1) + p (y1 ∣X = x2 )︸︷︷︸impossibile! ( = 0)

p (x2) + p (y1 ∣X = x3 )︸︷︷︸impossibile! ( = 0)

p (x3) = p (x1) = 1− 2Q

Sostituendo:

H (Y) = −p (y1) log2 p (y1)− 2Qlog2Q = − (1− 2Q) log2 (1− 2Q)− 2Qlog2Q

Ora possiamo ricavare l'espressione generale dell'informazione mutua:

I (X; Y) = H (Y)− H (Y ∣X ) = − (1− 2Q) log2 (1− 2Q)− 2Qlog2Q− 2Qℋ (p)

Ricordando ora la relazione notevoled

dxlog2x =

1x ln 2

possiamo calcolare la derivata dell'informazione mutua al �ne di ricavare il massimo di quest'ultima:

d

dQI (X; Y) =

d

dQ{− (1− 2Q) log2 (1− 2Q)− 2Qlog2Q− 2Qℋ (p)} =

= (1− 2Q)2

(1− 2Q) ln 2+ 2log2 (1− 2Q)− 2Q

1Q ln 2

− 2log2Q− 2ℋ (p) =

= 2log2 (1− 2Q)− 2log2Q− 2ℋ (p) = 0

38


Sempli�cando e riordinando:log2 (1− 2Q)− log2Q−ℋ (p) = 0

log21− 2Q

Q= ℋ (p)

1− 2QQ

= 2ℋ(p) ≜ β (p)⇒ Q =1

2 + β

Ora che abbiamo trovato il valore di Q che massimizza l'informazione mutua, possiamo andare a sostituirlo nella

relativa espressione per scoprire la capacità del canale (in funzione di β e quindi di p):

C = − (1− 2Q) log2 (1− 2Q)− 2Qlog2Q− 2Qℋ (p) =

= −(

1− 21

2 + β

)log2

(1− 2

12 + β

)− 2

12 + β

log21

2 + β− 2

12 + β

ℋ (p)︸︷︷︸≜log2β

=

= − β

2 + βlog2

(β

2 + β

)− 2

2 + βlog2

12 + β

− 22 + β

log2β =

= − 12 + β

log2

(β

2 + β

)β

− 12 + β

log2

(1

2 + β

)2− 1

2 + βlog2β2 =

= − 12 + β

[log2

(β

2 + β

)β

+ log2

(1

2 + β

)2+ log2β2

]=

= − 12 + β

[log2

(β

2 + β

)β

+ log2

(β

2 + β

)2]= − 1

2 + βlog2

(β

2 + β

)2+β

= log22 + β

β

3.3 Capacità di canale con blocchi di simboli

Figura 3.11: Canale discreto senza memoria: caso di gruppi di simboli

Come da tradizione, vediamo cosa succede se vediamo la cosa non simbolo per simbolo bensì a blocchidi simboli (vedi figura 3.11). Allora in tal caso si ha:

I(X(n); Y(n)) ≤ n ⋅ C (3.13)

dove C è la capacità che si ha nel caso simbolo-per-simbolo.Dimostrazione: l’informazione mutua intesa per supersimboli è definita come

I(

X(n); Y(n))= H

(Y(n)

)− H

(Y(n)

∣∣∣X(n))

Possiamo tuttavia elaborare il secondo addendo in maniera astuta:

H(

Y(n)∣∣∣X(n)

)= H (Y1Y2Y3 . . . Yn ∣X1X2X3 . . . Xn ) −−−−−−−−−−−−−−−−−−−−−−→

usiamo la regola della catena (chain rule)

→ H (Y1 ∣Y2 . . . YnX1 . . . Xn ) + H (Y2 ∣Y3 . . . YnX1 . . . Xn ) + . . . + H (Yn ∣X1 . . . Xn ) =

=n

∑i=1

H

⎛⎝Yi

∣∣∣∣∣∣Yi−1Yi−2 . . . Y1 X1 . . . Xn︸︷︷︸tocca tenercele!

⎞⎠Siccome tuttavia il canale è senza memoria, la generica variabile aleatoria Yi dipende solo dalla Xi quindipossiamo riscrivere l’ultima sommatoria in questa maniera:

n

∑i=1

H

⎛⎝Yi

∣∣∣∣∣∣Yi−1Yi−2 . . . Y1 X1 . . . Xn︸︷︷︸tocca tenercele!

⎞⎠ =n

∑i=1

H (Yi ∣Xi )

39


Ora invece soffermiamoci sull’altro addendo: anche in questo caso possiamo sfruttare l’ipotesi di assenzadi memoria e i calcoli si rivelano abbastanza semplici.

H(

Y(n))= H (Y1Y2Y3 . . . Yn) ⩽ ∑

iH (Yi)

Mettendo insieme gli ingredienti:

I(

X(n); Y(n))⩽ ∑

iH (Yi)− H (Yi ∣Xi ) =

n

∑i=1

I (Xi; Yi)︸︷︷︸ciascun termine ⩽C

⩽ nC

3.4 Disuguaglianza del data processing

Consideriamo la figura 3.12.

Figura 3.12: Y dipende da X, Z dipende da X solo per mezzo di Y

La disuguaglianza del data processing afferma che se prendiamo un’informazione e la elaboriamo inrealtà non la stiamo aumentando: anzi, al massimo possiamo perderne! Si ha infatti:

I(X; Z) ≤ I(Y; Z)

I(X; Z) ≤ I(X; Y)(3.14)

Dimostrazione:I (X; Z) = H (Z)− H (Z ∣X )

I (Y; Z) = H (Z)− H (Z ∣Y )

H (Z ∣X ) ⩽ H (Z ∣Y )

Da qui capiamo che, per conoscere la Z, è più ’notevole’ la Y della X. Forti di questa informazione eguardando le prime due definizioni di I(X; Z), I(Y; Z) si ha immediatamente:

I(X; Z) ≤ I(Y; Z)

3.5 Disuguaglianza di Fano

Figura 3.13: Apparato per illustrare la disuguaglianza di Fano

Osserviamo la figura 3.13: supponiamo di voler capire la X guardando la Y e, a tal proposito, infiliamoun blocchetto decisore nella catena. Tale elemento funziona secondo alcuni criteri che per semplicità

40


considereremo alla stregua di una certa funzione g(). Chiameremo x il simbolo che il decisore ha stimatoper X in un certo istante: chiaramente il DMC può aver indotto degli errori e quindi non sempre accadràche x = x. Sia quindi

pe = p(x ∕= x)

la probabilità d’errore; si ha allora la seguente diseguaglianza, detta diseguaglianza di Fano

H(X∣Y) ≤ ℋ(Pe) + Pe log2(Nx − 1) (3.15)

dove Nx è la cardinalità dell’alfabeto X che si riferisce ai simboli che trasmettiamo.Dimostrazione: chiamiamo E la variabile aleatoria ’errore’, la quale si rivela essere una variabile bernoul-liana con probabilità Pe {

1 se x ∕= x (Errore)

0 se x = x (No errore)⇒ P (E = 1) = Pe

Quanto vale l’entropia di E?

REGOLINA!⇒ H (X, Y) = H (X ∣Y ) + H (Y) = H (Y ∣X ) + H (X)

H (X, E ∣Y ) = H (X ∣E , Y) + H (E ∣Y ) = H (E∣X, Y) + H (X ∣Y )(3.16)

Conoscere Y3 equivale a conoscere X (grazie al decisore): se conosciamo sia X che X sappiamo concertezza se c’è errore oppure no, quindi l’entropia associata a questo caso sarà nulla → H(E∣X, Y) = 0.Ora cerchiamo di sviluppare le espressioni dei due addendi che compaiono nella 3.16; secondo le regoledi base sull’entropia di variabili aleatorie si ha:

H(E∣Y) ≤ H(E) = ℋ(Pe)

Infatti l’incertezza su E conoscendo Y sarà sicuramente minore o uguale di quella che abbiamo senzanessuna informazione. Inoltre possiamo sviluppare H(X∣E, Y), cioè l’altro addendo:

H (X ∣E , Y) = H (X ∣E = 1 , Y) p (E = 1)︸︷︷︸Pe

+H (X ∣E = 0 , Y) p (E = 0)︸︷︷︸1−Pe

Possiamo tuttavia eliminare il termine H (X ∣E = 0 , Y) p (E = 0) in quanto se qualcuno ci dice che nonvi è stato errore e conosciamo la Y allora sicuramente X = X e dunque non abbiamo alcuna incertezza(= entropia nulla). Non è la stessa cosa per il termine H (X ∣E = 1 , Y): conosciamo la Y e la X e siamoal corrente della presenza di un errore, ma non sappiamo quale scegliere fra gli Nx − 1 altri elementidell’alfabeto X . Siamo quindi in grado di affermare che l’incertezza sulla X è legata all’entropia massima(riferita al caso di alfabeto a Nx − 1 simboli) secondo la relazione:

H(X∣E = 1, Y) ≤ log2 Nx − 1

Rimettendo insieme i pezzi:

H (X ∣Y ) + H (E ∣X, Y )︸︷︷︸=0

= H (X ∣E , Y)︸︷︷︸⩾Pe log2(Nx−1)

+ H (E ∣Y )︸︷︷︸⩾ℋ(Pe)

⩾ ℋ (Pe) + Pe log2 (Nx − 1)

3Tale variabile aleatoria fa sempre parte della condizione nell’equazione 3.16. Per interpretare correttamente i calcoli bisognaforzare la sua presenza a destra dell’operatore pipe (∣) e sfruttare le note regoline dell’entropia sulle altre due variabili aleatorie (X eY).

41


Figura 3.14: Interpretazione grafica della disuguaglianza di Fano

Ecco la disuguaglianza di Fano! Possiamo dare un’interpretazione grafica di questa disuguaglianza4

(vedi figura 3.14), nonché cercare un legame con la capacità:

C = maxp(x)

[I (X; Y)] = maxp(x)

[H (X)− H (X ∣Y )]⇒ C ⩾ H (X)− H (X ∣Y )

H (X) ⩽ C + H (X ∣Y ) ⩽ C +ℋ (Pe) + Pe log2 (Nx − 1)(3.17)

Ecco trovato, in funzione di C, un bound superiore per l’entropia H(X). Anche qui possiamo dare un’in-terpretazione grafica di quanto trovato (vedi figura 3.15): notiamo che non possiamo immettere troppainformazione nel canale se vogliamo lavorare nella zona cerchiata di rosso, dove si sbaglia poco (Pe piccolao - meglio ancora - nulla). Possiamo certo provare a spedire più informazione (aumentare H(X)), ma apatto di accettare una probabilità d’errore Pe maggiore.

3.6 Codifica di canale

Siamo finalmente giunti al nucleo di questo capitolo: la codifica di canale. La codifica di canale è intelecomunicazioni il processo volto a garantire la trasmissione ottimale di un messaggio, trasmesso attra-verso un canale con rumore, mediante l’aggiunta di una ridondanza che ’protegga’ il dato da trasmettere.Dopo la sorgente e il codificatore di sorgente, come sappiamo, esiste un elemento (codificatore di canale)che si occupa di codificare i supersimboli che arrivano con periodo T dalla sorgente5. Immaginiamo cheogni supersimbolo sia un vettore di k bit (cardinalità dell’alfabeto d’ingresso: L = 2k), che w sia uno degli

4Di seguito riporto un mio tentativo di calcolo del massimo, tutto da verificare:

∂

∂pe

{pe log2

1pe

+ (1− pe) log21

(1− pe)+ pe log2 (N − 1)

}=

= log21pe

+ pepe

ln 2− log2

1(1− pe)

+ (1− pe)(1− pe)

ln 2+ log2 (N − 1) + pe

1(N − 1) ln 2

=

= log21− pe

pe+

p2e

ln 2+

(1− pe)2

ln 2+ log2 (N − 1) + pe

1(N − 1) ln 2

=

= log2(1− pe) (N − 1)

pe+

2p2e − 2pe + 1

ln 2+

pe

(N − 1) ln 2=

= log2(1− pe) (N − 1)

pe+

(2p2

e − 2pe + 1)(N − 1) + pe

(N − 1) ln 2

5Se ogni supersimbolo è costituito da n simboli, ogni simbolo arriverà con periodo T/n.

42


Figura 3.15: Limite superiore per l’entropia

L possibili vettori e che i bit siano equiprobabili cosicché si abbia

H(W) = log2 L

Possiamo allora dividere per n (numero di simboli in un supersimbolo) così da ottenere:

H(W)

n=

log2 Ln

= Rc (3.18)

dove Rc è la code-rate, ovvero la quantità d’informazione per simbolo entrato nel canale. La sostanza,tuttavia, non è cambiata: il codificatore non ha trovato il modo di immettere più informazione nel canale,visto che per Fano si deve ancora avere Rc < C. Il codificatore mappa piuttosto queste k-ple in delle n-plee, se è ben fatto, farà in modo di rendere il più possibile distanti6 (cioè differenti) in modo da minimizzarela probabilità che la W, stimata al ricevitore, sia errata. Tale probabilità verrà di seguito indicata con

pe = p(W ∕= W) (3.19)

Mentre quella di seguito è la probabilità d’errore condizionata dal fatto che sappiamo quale vettore è statoinviato:

pe∣i = p(W ∕= W∣W = wi) (3.20)

Definiamo inoltre la massima probabilità di errore:

λ = maxi

pe∣i (3.21)

Il criterio con il quale il codificatore effettua il mapping dei vettori dipende dal codice C utilizzato, il qualeè definito in maniera univoca:

∙ dalle parole di codice;

∙ dal modo in cui le parole di codice sono accoppiate;

∙ da com’è costituito il decoder (componente duale del codificatore di sorgente).

6Nel senso di Hamming.

43


3.7 Teorema della codifica di canale (secondo teorema di Shannon)

Il secondo teorema di Shannon o teorema della codifica di canale stabilisce che, per quanto un canaledi comunicazione sia affetto da rumore, è possibile trasmettere dati (informazioni) con probabilità dierrore piccola a piacere fino ad una frequenza massima7 attraverso il canale stesso. Questo sorprendenterisultato fu presentato per la prima volta da Claude Shannon nel 19488 e, sostanzialmente, descrive lamassima possibile efficienza di un qualunque metodo di correzione degli errori in funzione del livello dirumore. La teoria non spiega come costruire un codice ottimo, ma stabilisce solo quali siano le prestazionidi tale codice ottimo9.

Formalizzando matematicamente, il teorema sostiene che

∀ε > 0, Rc =log2 L

n< C ∃ Codice C : Pe < ε per n sufficientemente elevato (3.22)

Dimostriamo questo teorema tenendo presente la simbologia in figura 3.16. Ricordiamo il teorema del

Figura 3.16: Schema di riferimento per la dimostrazione del secondo teorema di Shannon

data processing e scriviamo10:

I(

W; Y(n))⩽ I

(X(n); Y(n)

)⩽ nC

Possiamo quindi dire che:

I(

W; Y(n))= H (W)− H

(W∣∣∣Y(n)

)⩽ nC

Se applichiamo l’ipotesi che i simboli siano equiprobabili H(W) = log2 L e quindi:

log2 L ⩽ H(

W∣∣∣Y(n)

)+ nC

Ora entra in gioco la disuguaglianza di Fano:

log2 L ⩽ H(

W∣∣∣Y(n)

)+ nC ⩽ ℋ (Pe)︸︷︷︸

incertezza: è avvenuto un errore?

+ Pe log2 (L− 1)︸︷︷︸c’è errore: incertezza sui rimanenti L−1 simboli

+nC

Proseguendo con la catena di disuguaglianze:

ℋ (Pe)︸︷︷︸⩽1

+Pe log2 (L− 1) + nC ⩽ 1 + P2 log2 (L− 1) + nC < 1 + Pe log2 L + nC

Rimettiamo insieme i pezzi:

log2 L ⩽ H(

W∣∣∣Y(n)

)+ nC < 1 + Pe log2 L + nC

Se ora dividiamo per n otteniamo:

log2 Ln

= Rc <1 + Pe log2 L + nC

n=

1n+ PeRc + C

7La capacità di Shannon, nota anche come limite di Shannon, di un canale di comunicazione è il massimo tasso di trasferimento didati che può fornire il canale per un dato livello di rapporto segnale/rumore, con un tasso di errore piccolo a piacere.

8Shannon diede solo una traccia della dimostrazione. La prima dimostrazione rigorosa è dovuta a Amiel Feinstein nel 1954.9Utilizzando i più recenti codici Turbo (o gli LDPC) e la potenza computazionale disponibile sugli odierni DSP, è oggi possibile

avvicinarsi a meno di 1/10 di decibel rispetto al limite di Shannon.10Si ricorda che C si riferisce al singolo simbolo!

44


Mandando Pe a 0 e imponendo n≫ 1

Rc <1n+ PeRc + C ⇒ Rc < C

Questo significa che per un generico codice, anche se potentissimo (Pe → 0) e sufficientemente lungo(n≫ 1), la code-rate non potrà comunque mai superare il limite asintotico imposto dal teorema di Shannon(cioè la capacità). Per graficare la code-rate in funzione della probabilità d’errore non imponiamo chePe → 0, ma manteniamo l’ipotesi n≫ 1: otteniamo

Rc > PeRc + C (3.23)

da cui

Pe > 1− CRc

(3.24)

Figura 3.17: Probabilità di errore e code-rate

Graficando quanto ottenuto (vedi figura 3.17) possiamo dedurre la morale della favola, ovvero che viè un limite all’informazione trasportabile attraverso un canale: oltre tale limite l’informazione va perduta,quindi possiamo ridurre la Pe a piacere con tecniche sempre più raffinate (e allungando a dismisura il co-dice), ma non potremo mai superare i limiti teorici imposti da Shannon (e quindi esagerare con la code-rate).

Il secondo teorema di Shannon ha numerose applicazioni, sia nel campo delle telecomunicazioni chein quello dell’archiviazione di dati ed è alla base della moderna Teoria dell’informazione.

3.8 Variabili aleatorie continue

Non sempre si usano variabili aleatorie discrete e, anzi, le variabili aleatorie diventano continue acausa di fenomeni fisici come il rumore gaussiano. Per una variabile continua la densità di probabilità è unafunzione continua tale per cui (vedi figura 3.18):

p (a ⩽ x ⩽ b) =b∫

a

pX (x) dx (3.25)

Per passare da variabile continua a discreta è sufficiente quantizzare la funzione continua prendendonecampioni con spaziatura ∆; il criterio con il quale vengono tratti questi campioni è quello del teorema del

45


Figura 3.18: Densità di probabilità di una variabile aleatoria continua

valor medio: si assegna in pratica al generico campione xn la seguente probabilità

P (xn) = ∆ ⋅ pX(xi) =∫∆

pX (x) dx ⇒∑i

p (xi) = 1 (3.26)

cosicché, come indicato, la sommatoria delle probabilità associate a ciascun campione restituisca esatta-mente 1. Il teorema del punto medio ci garantisce che il rettangolino di larghezza ∆ su cui integriamoavrà la stessa area della funzione calcolata nell’intervallo (P (xn) = ∆ ⋅ pX(xi)). Calcoliamo ora l’entropiadella nostra variabile aleatoria ’discretizzata’ X:

H(X)= −∑

iP (xi) log2 P (xi) = −∑

i∆ ⋅ p (xi)︸︷︷︸

teorema valor medio

log2 (∆ ⋅ p (xi)) =

= −∆ ∑i

px (xi) log2 p (xi)− ∆ ∑i

p (xi)︸︷︷︸=1

log2 ∆ =

= −∆ ∑i

p (xi) log2 p (xi)− log2 ∆ −−−−−−−−−−−−−−→quantizzazione fitta ∆→0

∞∫−∞

p (xi) log2 p (xi)︸︷︷︸definiz. di integrale secondo Riemann

+ ∞︸︷︷︸!??!!

Che acciderbolina sta a significare quell’∞? Sembra una roba astrusissima, ma in realtà ha senso perchésignifica che servono ∞ bit per rappresentare una variabile continua. Questo non ci dà fastidio ancheperché di seguito tratteremo sempre differenze di entropia (come nell’informazione mutua) tali per cui il +∞si cancella.

3.9 Entropia differenziale

L’entropia differenziale, definita per variabili aleatorie continue, è definita così:

h (X) ≜

∞∫−∞

p (x) log21

p (x)dx =

∞∫−∞

p (x) log2 p (x) dx (3.27)

Tale parametro ci dà un’indicazione di quanto sia random la nostra variabile aleatoria. Chiaramenteesistono anche. . .

1. l’entropia differenziale congiunta:

h (x, y) = −∫∫R2

p (x, y) log2 p (x, y) dxdy (3.28)

46


2. l’entropia differenziale condizionata:

h (x ∣y ) = −∫∫R2

p (x, y) log2 p (x ∣y ) dxdy (3.29)

L’entropia differenziale condizionata è sicuramente minore o uguale dell’entropia condizionata sem-plice11.

ESEMPIO:Calcoliamo l'entropia di�erenziale per la variabile X uniformemente distribuita su [a, b]:

h (X) = −∫x

p (x) log2 p (x) dx = −b∫

a

1b− a

log2 (b− a) dx = log2 (b− a)

ESERCIZIO:

Dimostrare che si ha la seguente relazione per la distanza di Kullback-Leiber12:

−∫

p (x) log2 p (x) dx ⩽ −∫

p (x) log2 q (x) dx

cioè che (distanza di Kullback-Leiber)→∞∫−∞

p (x) log2q (x)p (x)

dx ⩽ 0(3.30)

Dimostrazione: il trucco è sempre lo stesso, ovvero usare la disequazione 1.6:

∞∫−∞

p (x) log2q (x)p (x)

dx ⩽ log2 e∞∫−∞

p (x)[

q (x)p (x)

− 1]dx = 0

L'uguaglianza si ha solo se q(x) = p(x) ∀x.

3.9.1 Teorema: la distribuzione uniforme ha entropia massima (caso intervallo limi-tato)

Vogliamo dimostrare cheh(X) ≤ log2(b− a) (3.31)

e cioè che la distribuzione uniforme, avente entropia differenziale log2(b− a), è quella ad entropia massima(cosa peraltro abbastanza ragionevole).Dimostrazione: sfruttiamo la distanza di Kullback-Leiber.∫

p (x) log21

p (x)dx ⩽

∫p (x) log2

1q (x)

dx

Se p(x) è una distribuzione generica e q(x) quella uniforme si ha:

hgenerica (X) =∫

p (x) log21

p (x)dx ⩽

∫p (x) log2 (b− a) dx = log2 (b− a)

∫p (x) dx = log2 (b− a)

11Dimostrazione di mio pugno e senza pretese di correttezza:

−∫x

∫y

p (x, y) log2 p (x ∣y ) dxdy ⩽ −∫x

p (x) log2 p (x) dx

−∫x

∫y

p (x, y) log2p (y)

p (x, y)dxdy ⩽

∫x

∫y

p (x, y) log2 p (x) dxdy

−∫x

∫y

p (x, y)(

log2p (y) p (x)

p (x, y)

)dxdy ⩽ − log2 e

∫x

∫y

p (x, y)(

p (y) p (x)p (x, y)

− 1)

dxdy = 0

12Questa quantità viene usata per vedere quanto una distribuzione è simile ad un’altra:

∙ se è pari a zero, le distribuzioni coincidono;

∙ se è maggiore di zero, le distribuzioni sono diverse;

∙ se è MOOOOLTO maggiore di zero, le distribuzioni sono parecchio differenti.

47


3.9.2 Teorema: la distribuzione gaussiana ha entropia massima (caso intervallo illi-mitato)

Rimuoviamo ora l’ipotesi di intervallo finito [a, b] e estendiamoci da −∞ a +∞. Allora in tal caso ladistribuzione avente entropia massima (pari a log2

√2πσ2e) è quella gaussiana e si ha:

h(X) < log2

√2πσ2e (3.32)

Dimostrazione: anzitutto dobbiamo ricavare l’entropia differenziale di una distribuzione gaussiana.

hgaussiana (X) = −∞∫−∞

pgaussiana (x)︸︷︷︸1√

2πσ2exp

{− (x−µ)2

2σ2

} log2 pgaussiana (x) dx =

= −∞∫−∞

pgaussiana (x) log2

(1√

2πσ2exp

{− (x− µ)2

2σ2

})dx =

= −∞∫−∞

pgaussiana (x) ⋅[

log21√

2πσ2+ ln

(exp

{− (x− µ)2

2σ2

})⋅ log2 e

]dx =

=

∞∫−∞

pgaussiana (x) ⋅[

log2

√2πσ2 +

(x− µ)2

2σ2 ⋅ log2 e

]dx =

= log2

√2πσ2

∞∫−∞

pgaussiana (x) dx

︸︷︷︸=1

+log2 e2σ2

∞∫−∞

pgaussiana (x) ⋅ (x− µ)2

︸︷︷︸definizione E[(X−µ)2]=var X=σ2

dx =

= log2

√2πσ2 +

log2 e2

= log2

√2πσ2 + log2

√e = log2

√2πσ2e

Ora dobbiamo dimostrare che è quella avente l’entropia differenziale maggiore rispetto a tutte le altredensità di probabilità. Abbiamo già dimostrato che si ha:

h (X) =∫

p (x) log21

p (x)dx ⩽

∫p (x) log2

1q (x)

dx

Se ora al posto di q(x) (che è generica) mettiamo la distribuzione di probabilità gaussiana:

∫p (x) log2

1p (x)

dx ⩽∫

p (x) log21

pgaussiana (x)dx

Ma l’uguaglianza vale solo se p(x) = pgaussiana(x) e in tal caso si ha:

∫pgaussiana (x) log2

1pgaussiana (x)

dx = log2

√2πσ2e

A parità di µ e σ2, quindi, la massima incertezza la si ha con la gaussiana. Si noti che l’entropia dif-ferenziale dipende da σ, cosa abbastanza prevedibile visto che se la campana è spanciata l’incertezza èmaggiore. Il valor medio µ invece non influisce proprio un tubo.

48


3.9.3 Teorema: la distribuzione esponenziale negativa ha entropia massima (casointervallo [0,+∞] )

Anzitutto calcoliamo l’entropia differenziale della distribuzione esponenziale negativa (s’intende chegli integrali di seguito sono calcolati da [0,+∞]):

h (X) = −∫

p (x) log2 p (x) dx = −∫

p (x) log2

(λe−λx

)dx = −

∫p (x) ⋅ log2 e ⋅ ln λe−λx dx =

= −∫

p (x) ⋅ log2 e ⋅ (ln λ− λx) dx =− log2 e ⋅ ln λ∫

p (x) ⋅ dx︸︷︷︸=1

+λ log2 e∫

xp (x)dx︸︷︷︸1/λ

=

= − log2 e ⋅ ln λ + log2 e = log2 e ⋅ (1− ln λ)

Ora dimostriamo, con la solita disequazione, che è quella ad entropia maggiore. Con p(x) e q(x) generichesi ha:

h (X) =∫

p (x) log21

p (x)dx∫

p (x) log21

q (x)dx

Quindi se scegliamo al posto di q(x) la distribuzione esponenziale negativa, l’uguaglianza vale solo sep(x) = q(x) e si ha:

h (X)∫

pesp - neg (x) log21

pesp - neg (x)dx = hesp - neg (X)

49


50

Capitolo 4

Il limite di Shannon

In questo capitolo tratteremo la parte più avanzata della Teoria dell’Informazione, soffermandocisull’analisi del canale additivo gaussiano bianco e su altri importanti aspetti.

4.1 Capacità del canale additivo gaussiano bianco

Abbiamo visto nel paragrafo 3.2 come calcolare la capacità di alcuni canali notevoli. Fra questi siè deciso di posticipare la trattazione di quello additivo gaussiano bianco a questo paragrafo in quanto sipossono trarre da esso molti spunti per ulteriori nozioni di Teoria dell’Informazione.

Figura 4.1: Rumore additivo gaussiano bianco

In figura 4.1 viene mostrato lo schema di riferimento: Z è una distribuzione continua gaussiana a valormedio nullo e varianza σ2 così che possiamo scrivere

Z ∼ N (0, σ2) (4.1)

Visto che Y = X + Z, anche Y sarà (come Z) una variabile aleatoria caratterizzata da una distribuzionecontinua. All’interno di questo schema un vincolo è costituito dalla potenza del rumore e da quella delsegnale che trasmettiamo, le quali dipendono dai seguenti momenti del second’ordine:

E[

X2]= S (signal)

E[

Z2]= N = σ2 (noise)

A quanto è pari l’informazione mutua di questo canale?

I (X; Y) = h (Y)− h (Y ∣X ) = h (Y)︸︷︷︸Dipende dalla v.a. Y

−log2

√2πeσ2

Si noti che si è usato il simbolo h (entropia differenziale) in quanto le variabili in gioco sono continue e cheè stato utilizzato il risultato ottenuto nel paragrafo 3.9.2. Ciò che ci autorizza a scrivere direttamente che

51

52 CAPITOLO 4. IL LIMITE DI SHANNON

l’entropia h(Y∣X) è pari a log2

√2πeσ2 è il fatto che la distribuzione Y è la somma di un valore associato

a X (costante e pari a x) e di un valore Z (distribuzione gaussiana), dunque è anch’essa una distribuzionegaussiana1 e si ha:

{Y ∣X = x (costante)} ∼ N(

x, σ2)

Ma l’entropia differenziale dipende solo dalla varianza: se effettuiamo una media sui valori di tutte le xotteniamo quindi un valor medio esattamente pari a log2

√2πeσ2.

Calcoliamo ora la capacità, ovvero il massimo dell’informazione mutua; dovendo noi massimizzare lah(Y), faremo l’ipotesi che anche la Y sia una variabile gaussiana imponendo che anche X lo sia, cosicchépossiamo scrivere:

C = maxp(x)

I (X; Y) = log2

√2πeσ2

y − log2

√2πeσ2 = log2

√2πeσ2

y√

2πeσ2= log2

√σ2

y√

σ2=

12

log2

σ2y

σ2

Se facciamo l’ipotesi (ragionevole) che rumore e segnale utile facciano capo a due variabili indipendentied entrambe gaussiane, allora la varianza di Y = X + Z è uguale alla somma delle varianze di X e Y:

C = maxp(x)

I (X; Y) =12

log2

σ2y

σ2 =12

log2σ2

x + σ2

σ2 =12

log2

(1 +

σ2x

σ2

)Possiamo ora esprimere la varianza σ2

x in funzione dei nostri vincoli, dato che si ha

σ2x = E

[X2]− E2 [X]

Volendo noi massimizzare σ2x , cioè la potenza del segnale utile, l’unica è annullare E2[X]. Così facendo

otteniamo:σ2

x = E[X2] = S (4.2)

Sostituendo nella formula della capacità di canale otteniamo:

C =12

log2

(1 +

SN

)(4.3)

Provando a graficare la capacità in funzione del rapporto segnale-rumore SN otteniamo la figura 4.2. Con

ragionamenti al limite possiamo trovare la pendenza, cioè il coefficiente angolare, della retta indicata come’asintoto’:

Figura 4.2: Capacità in funzione del rapporto segnale rumore

SN

(dB) = 10log10SN⇒ S

N= 10

S/N (dB)10 ⇒ C =

12

log2

(1 + 10

S/N (dB)10

) S/N (dB) grande−−−−−−−−−→ C =12

log210S/N (dB)

10

1Attenzione: Y di per sé non è gaussiana. Lo è soltanto se consideriamo un valore costante di X che chiamiamo x, in quantosommando una costante ad una qualsiasi variabile aleatoria gaussiana otteniamo un’altra variabile aleatoria gaussiana, ma con unvalor medio differente (per ricavarlo dobbiamo sommare la costante al valor medio della variabile aleatoria di partenza).

52

CAPITOLO 4. IL LIMITE DI SHANNON 53

Applicando ora le proprietà dei logaritmi si ha:

C =12

log210S/N (dB)

10 =S/N (dB)

20log210

Dunque la retta tratteggiata in figura 4.2 ha coefficiente angolare1

20log2 10; la cattiva notizia è invece che

la capacità cresce logaritmicamente con il rapporto S/N. Peccato: è una crescita piuttosto lenta. . .

4.2 Caso tempo-continuo a banda limitata (formula di Hartley-Shannon)

Figura 4.3: Schema del caso tempo-continuo a banda limitata

Esaminiamo lo schema in figura 4.3: abbiamo un segnale utile x(t) che attraversa un canale additivogaussiano bianco e quindi riceve un contributo di rumore n(t). Per ipotesi supporremo la banda limitatatra −B e B (ecco quindi spiegata la presenza del filtro). In figura 4.4 possiamo invece vedere le densitàspettrali di potenza.

Figura 4.4: Spettri dei segnali (raffiguriamo solo la parte tra −B e B tanto ci pensa il filtro ad eliminare tutto il resto!)

Considereremo fissata e pari ad S la potenza del segnale utile:

B∫−B

Gx ( f ) d f = S =⟨

x2 (t)⟩ Ergodicità

= E[

X2 (t)]

Considerazioni analoghe possiamo farle per il rumore:

B∫−B

Gn ( f ) d f = N =⟨

n2 (t)⟩= N0B = σ2 Ergodicità

= E[n2 (t)

]Ora serviamoci della nostra arma segreta: il teorema del campionamento! Esso, ci ricordiamo, afferma chesi ha reversibilità nella conversione A/D se la frequenza di campionamento fs è almeno il doppio dellabanda del segnale B:

fs ≥ 2B (4.4)

53


Scegliamo esattamente la frequenza fs = 2B e campioniamo il nostro segnale all’interno di una finestratemporale T. Otteniamo perciò, con un periodo pari a 1/ fs, dei campioni che andremo a raccogliere neivettori x, y, n: ognuno di questi vettori conterrà 2BT campioni

x− = x1, x2, . . . , x2BT

y−= y1, y2, . . . , y2BT

n− = n1, n2, . . . , n2BT

Sul singolo istante di campionamento si ha:

yi = xi + ni

Sia xi che ni sono campioni di processi ergodici:

E[

x2i

]= E

[x2 (ti)

]=⟨

x2 (t)⟩= S

ni = N(

0, σ2)⇔ N = σ2 = E

[n2

i

]Si noti che, come indicato, ni è il campione una variabile aleatoria gaussiana. Nonostante vengano tra-smessi dei vettori, ha comunque senso calcolare la capacità simbolo per simbolo in quanto si dimostra chegli ni sono indipendenti (vedi paragrafo 4.2.1) e quindi il canale può essere considerato senza memoria;se supponiamo inoltre che anche gli xi siano indipendenti allora siamo completamente liberi di ragionarecampione per campione. Ricordando dal paragrafo 4.1 che la capacità (in Shannon per campione) è

C =12

log2

(1 +

SN

)allora avremo, in Shannon per vettore (cioè in Shannon per T secondi)

C = 2BT12

log2

(1 +

SN

)= BT log2

(1 +

SN

)e, nell’unità di tempo (Shannon/secondo),

C = B log2

(1 +

SN

)(4.5)

Quest’ultima relazione (4.5) viene chiamata formula di Hartley-Shannon: portando la B a denominatoredella C otteniamo una relazione

CB

= log2

(1 +

SN

)= log2

(1 +

SN0B

)che può essere facilmente graficata come mostrato in figura 4.5. Purtroppo, come si nota, anche quiemerge che la capacità aumenta logaritmicamente con il rapporto segnale-rumore (SNR). Se fissiamoora S e N0

2 possiamo provare a mandare al limite B→ ∞: la capacità C in tal caso tende a

C = limB→∞

Blog2

(1 +

SN0B

)= lim

B→∞log2

(1 +

SN0B

)BLIMITE NOTEVOLE−−−−−−−−−−−→

limx→∞

(1+ αx )

x=eα

limB→∞

log2eS

N0 =S

N0log2e

Anche questo risultato è riportato in figura 4.5: altra brutta notizia - pure la banda alla fine non paga piùdi tanto. . . anzi, anche con tutta la banda del mondo a disposizione la capacità arriva ad un valore limiteinvalicabile!

2Si noti che N0 non è adimensionale: ha unità di misura Watt/Hertz.

54


Figura 4.5: Capacità su banda in funzione dell’SNR e capacità in funzione della banda

4.2.1 Incorrelazione del rumore

Il generico ni è stato ottenuto campionando n(t), rumore bianco avente banda tra −B e B, su T e confrequenza fs = 2B. Ma è proprio vero che i campioni del vettore n sono indipendenti? Dimostriamolo!Il segnale N è gaussiano, dunque indipendenza e incorrelazione coincidono: dimostriamo quindi che icampioni sono incorrelati calcolando il seguente valor medio

E[ninj

]i ∕=j = E

[ni (ti) nj (ti)

]i ∕=j ≜ Rn

(ti − tj

)funzione di autocorrelazione del processo di rumore

La nostra funzione Rn, come sappiamo da Comunicazioni Elettriche LB, è una sinc avente forma:

Rn(τ) = BN0sinc(2Bτ) (4.6)

La distanza temporale fra un campione e l’altro sarà 12B dunque ti− tj sarà sicuramente un multiplo intero

di tale distanza. Possiamo quindi scrivere:

ti = i ⋅ TS =i

2B

Rn(ti − tj

)= Rn

(i− j2B

)= N sinc

(2B

i− j2B

)= N sinc (i− j)︸︷︷︸

sinc di un numero intero→0

= 0

Dunque fra campioni non c’è correlazione: questo implica che siano indipendenti! Si noti che ciò è legatoa due ipotesi:

1. il rumore è bianco (sennò addio antitrasformata!);

2. il campionamento è esattamente a frequenza fs = 2B.

Come sappiamo l’informazione trasmessa dipende dall’entropia ed essa è tanto maggiore quanto icampioni sono imprevedibili: il massimo risultato si ha quindi nel caso di campioni xi indipendenti. Sedunque prendiamo un segnale utile molto simile al rumore (cioè gaussiano, visto che la distribuzionegaussiana massimizza l’entropia), e dunque abbiamo indipendenza statistica fra i campioni, massimizzia-mo l’informazione per il canale AWGN (Additive White Gaussian Noise). Lo strumento con il quale renderei campioni meno ridondanti possibili, lo sappiamo, è il codificatore di sorgente mentre, per proteggerel’informazione dai disturbi del canale, c’è il codificatore di canale. Ora possiamo quindi parlare di un si-stema di trasmissione completo, come mostrato in figura 4.6; se lo osserviamo ai morsetti della nuvolettatratteggiata vediamo dei simboli in ingresso bn e dei simboli in uscita b′n: se la rate dei bn è inferiore allacapacità di canale allora Shannon ci garantisce che esisteranno dei codici coi i quali è possibile renderearbitrariamente piccola la probabilità di errore Pe dei bit consegnati all’utente (cosa non vera viceversa).

Ma riusciamo a trovare un legame fra le nostre quantità statisticamente determinate, la potenza e lacapacità di un sistema? Riusciamo ad avere un limite di riferimento per capire quanto più in là possiamospingerci in questa sistematica riduzione di Pe?

55


Figura 4.6: Sistema di trasmissione completo

4.3 Il limite di Shannon

Sappiamo che la capacità vale:

C = Blog2

(1 +

SN

)= Blog2

(1 +

SN0B

)Se l’energia per bit di sorgente spedito è Eb abbiamo che la potenza del segnale è pari a

S = Eb ⋅ Br =EbTb

(4.7)

dove Tb è il tempo di bit.

C = Blog2

(1 +

EbBr

N0B

)Il termine Eb

N0è la quantità di energia per bit di sorgente, ovvero il quantitativo di energia che spendiamo

per bit trasmesso; il termine BrB = η, misurato in bit/s/Hertz, è invece detto efficienza spettrale ed è

importantissimo per capire quanto stiamo sfruttando il canale. Volendo stare, con la nostra bit-rate, al disotto della capacità (non vorremo mica perdere informazione nel canale, vero?) otteniamo:

Br < C = Blog2

(1 +

EbBr

N0B

)⇒ η =

Br

B< log2

(1 +

EbN0

η

)2η < 1 +

EbN0

η

EbN0

>2η − 1

η

Quindi la nostra potenza trasmessa dev’essere sufficiente per garantire una trasmissione corretta dei dati;inoltre, l’efficienza spettrale ha un valore limite e insuperabile ricavabile nel seguente modo:

limη→0

2η − 1η

Limite notevole= ln 2 ≃ 0, 69 ≃ −1, 6 dB (4.8)

56


Fissata la potenza per bit trasmesso, non è possibile andare oltre una certa efficienza spettrale (vedi figura4.7) ma, cosa ancor più importante, fissata l’efficienza spettrale non è possibile trasmettere a menodi una certa potenza (vedi figura 4.8). Non sarà inoltre mai possibile, neanche con il codificatore dicanale più furbo del mondo, trasmettere in maniera corretta un’informazione con un rapporto segnalerumore inferiore a −1, 6 dB. . . e già ci va grassa perché significa che, comunque, possiamo correttamentecomunicare anche con segnali meno potenti del rumore (SNR < 0 dB)!

Figura 4.7: Punti ammissibili e non ammissibili e limite di Shannon (1)

In figura 4.8 si notano inoltre due zone notevoli:

∙ quella dei sistemi limitati in banda (esempio: i sistemi cellulari) → si ha a disposizione una buonaquantità di potenza ma non si ha molta banda, quindi bisogna fare in modo di aumentare al massimol’efficienza spettrale (parte in alto a destra del grafico);

∙ quella dei sistemi limitati in potenza (esempio: le sonde dello spazio profondo)→ abbiamo un’au-tonomia limitata (non possiamo assolutamente sprecare energia) tuttavia non abbiamo problemi dibanda (parte in basso a sinistra del grafico).

4.4 Antipodal Signalling AWGN

Supponiamo di voler trasmettere dei bit tramite un meccanismo che associa a questi ultimi dei simboliantipodali:

0′′ → +1→ x(t)

1′′ → −1→ −x(t)(4.9)

Immaginiamo inoltre che la forma d’onda x(t) sia ∈ R e consista in una semplice rect:

x(t) = rect(

tT

)cos 2π f0t (4.10)

Il nostro schema diventa quello in figura 4.9, dove il filtro in uscita dal canale rumoroso (il rumore siagaussiano, ergodico e bianco) è da considerarsi adattato3 e dunque con risposta impulsiva h(t) pari a

h(t) = K ⋅ x∗(t0 − t) (4.11)

Il parametro K è un fattore di attenuazione/amplificazione che influisce sia sul segnale utile S che sulrumore N: l’SNR, dunque, non dipende da K.

3In questo modo abbiamo l’SNR ottimo.

57


Figura 4.8: Punti ammissibili e non ammissibili e limite di Shannon (2)

Figura 4.9: Schema della trasmissione antipodale

Per linearità il segnale y(t) avrà forma:

y(t) = ±x(t) ∗ h(t) + ν(t) ∗ h(t) (4.12)

Calcoliamo le due convoluzioni:

x (t) ∗ h (t) =∞∫−∞

x (τ) h (t− τ)︸︷︷︸Kx∗(t0−t+τ)

dτ =

∞∫−∞

Kx (τ) x (t0 − t + τ)︸︷︷︸x=x∗perchè ∈R

dτ

x (t) ∗ ν (t) =∞∫−∞

ν (τ) h (t− τ) dτ

58


Sostituendo nella 4.12 e osservando l’uscita ad un determinato istante t0 otteniamo:

y (t0) = y0 = ±∞∫−∞

Kx (τ) x (t0 − t0 + τ) dτ+

∞∫−∞

ν (τ) h (t0 − τ) dτ

︸︷︷︸n(t0)≡n0

= ±K∞∫−∞

x2 (τ) dτ

︸︷︷︸Energia Ex

+n (t0) = ±KEx +n (t0)

Per via del fatto che il rumore è gaussiano e bianco, allora anche di n(t0) possiamo dire la stessa cosa edesaminare valor medio e varianza:

E [n (t0)] = E

⎡⎣ ∞∫−∞

ν (τ) h (t0 − τ)dτ

⎤⎦ =

∞∫−∞

E [ν (τ)]︸︷︷︸=0 per ipotesi

h (t0 − τ)dτ = 0

var [n (t0)] = E[n2 (t0)

]− E2 [n (t0)]︸︷︷︸

=0

= E

⎡⎣ ∞∫−∞

∞∫−∞

ν (τ) ν (ξ) h (t0 − τ) h (t0 − ξ)dτdξ

⎤⎦ =

=

∞∫−∞

∞∫−∞

E [ν (τ) ν (ξ)]︸︷︷︸Rν(τ−ξ)

h (t0 − τ) h (t0 − ξ)dτdξ

Ora possiamo sfruttare il fatto che l’autocorrelazione è l’antitrasformata dello densità spettrale di potenza,la quale è per ipotesi costante (lo spettro è bianco, vedi la figura 4.9); ma la trasformata di una costante èla delta di Dirac, dunque si ha:

Rν (x) = ℱ−1 {G0 ( f )} = N0

2δ (x) (4.13)

Sostituendo nuovamente nell’espressione della varianza:

var [n (t0)] =

∞∫−∞

∞∫−∞

R0 (τ − ξ) h (t0 − τ) h (t0 − ξ)dτdξ =

∞∫−∞

∞∫−∞

N0

2δ (τ − ξ) h (t0 − τ) h (t0 − ξ)dτdξ

La delta di Dirac ha la ben gradita proprietà di ’ammazzare’ un integrale (in quanto impone z = τ), quindisi ha:

var [n (t0)] =

∞∫−∞

N0

2h (t0 − τ) h (t0 − τ)dτ =

∞∫−∞

N0

2h2 (t0 − τ)dτ =

N0

2

∞∫−∞

K2x2 (t0 − t0 + τ)dτ =N0

2K2Ex

Dunque ora possiamo scrivere che n(t0) è una variabile aleatoria gaussiana avente i seguenti parametri:

n(t0) ∼= N(

0,N0

2K2Ex

)(4.14)

Per semplificarci i calcoli supponiamo che

K =1√Ex

Dunque ora si ha, più semplicemente:

n(t0) ∼= N(

0,N0

2

)(4.15)

Inoltre possiamo riscrivere nel seguente modo la risposta impulsiva

h(t) =1√Ex

x(t0 − t) (4.16)

e la generica espressione di y(t0):y(t0) = ±

√Ex + n0 (4.17)

Dunque ora lo schema è quello in figura 4.10.

59


Figura 4.10: Schema della trasmissione antipodale (una volta elaborato)

4.5 Hard decision

Strutturiamo il sistema affinché prenda delle hard-decision e aggiungiamo quindi un comparatore asoglia in cascata al morsetto trasportante y0: tale comparatore propenderà per

d =

{+1 (bit ’0’) se y0 > 0

−1 (bit ’1’) se y0 < 0

Assumendo che i bit trasmessi siano equiprobabili, proviamo a valutare la probabilità d’errore:

pe = Pr{

d = +1∣∣trasmesso un ′1′

}Pr{′1′}+ Pr

{d = −1

∣∣trasmesso uno ′0′}

Pr{′1′} =

=12(Pr{

d = +1∣∣trasmesso un ′1′

}+ Pr

{d = −1

∣∣trasmesso uno ′0′})

=

=12

⎛⎜⎜⎝Pr{−√

Ex + n0 > 0}

︸︷︷︸soprasoglia

+Pr{√

Ex + n0 < 0}

︸︷︷︸sottosoglia

⎞⎟⎟⎠ =12

(Pr{√

Ex < n0

}+ Pr

{−√

Ex > n0

})=

=12

erfc

{12

√Ex√2σ2

n+

12

√Ex√2σ2

n

}=

12

erfc√

Ex√2σ2

n

σ2n=

N02=

12

erfc√

Ex√N0

In figura 4.11 possiamo vedere la gaussiana e localizzare le erfc citate nelle formule precedenti. Inparticolare si ricorda che la funzione erfc ha la seguente forma analitica:

erfc (x) ≜1√π

∞∫x

e−t2dt (4.18)

Dunque possiamo verificare la correttezza dei nostri calcoli ricavando:

Figura 4.11: La gaussiana e le erfc da considerare

60


pe

{n0 >

√Ex

}=

∞∫√

Ex

1√2πσ2

ne− t2

2σ2n dt dt=

√2σnds−−−−−−→

s= t√2σn

∞∫√

Ex2σ2

n

1√2πσ2

ne−s2√

2σnds =

∞∫√

Ex2σ2

n

1√π

e−s2ds =

12

erfc

(√Ex

2σ2n

)

Quanto fatto fin’ora, a pensarci bene, ricorda il canale BSC con p pari alla pe così faticosamente calcolatapoco fa (vedi figura 4.12). Sappiamo quindi bene qual è la sua capacità:

C = 1−ℋ(p) = 1 + p log2 p + (1− p) log2(1− p) (4.19)

Figura 4.12: La similitudine con il canale BSC

4.6 Unquantized output

Nel paragrafo precedente abbiamo utilizzato un decisore: l’abbiamo fatto molto a cuor leggero, senzasottolineare il fatto che, ahimè, la scelta a soglia è molto drastica e - ponendosi come una vera e propriaquantizzazione - ci fa perdere una parte della nostra informazione. Che accade allora se eliminiamo ildecisore? La capacità varia significativamente? Possiamo trarne un qualche vantaggio? Lo schema è

Figura 4.13: Schema senza decisore

diventato quello in figura 4.13. Calcoliamo la capacità:

C = h (Y)− h (Y ∣X )

Il primo addendoh(Y) = E[− log2 p(Y)]

è abbastanza banale: l’unica è determinare p(Y), che è un po’ meno scontata. . .

p (y) =12

p(

y∣∣∣X =

√Ex

)︸︷︷︸

distribuzione gaussiana!

+12

p(

y∣∣∣X = −

√Ex

)︸︷︷︸distribuzione gaussiana!

=12

1√2πσ2

ne− (y−

√Ex)

2

2σ2n +

12

1√2πσ2

ne− (y+

√Ex)

2

2σ2n =

=12

1√2πσ2

n

⎛⎝e− (y−

√Ex)

2

2σ2n + e

− (y+√

Ex)2

2σ2n

⎞⎠61


Il secondo addendo è un pelo più elaborato ma neanche tanto:

h (Y ∣X ) = h(

Y∣∣∣X =

√Ex

)Pr(

X =√

Ex

)︸︷︷︸

bit equiprobabili =0,5

+h(

Y∣∣∣X = −

√Ex

)Pr(

X = −√

Ex

)︸︷︷︸bit equiprobabili =0,5

=

=12

(h(

Y∣∣∣X =

√Ex

)+ h

(Y∣∣∣X = −

√Ex

))=

=12

(h(

Y∣∣∣X =

√Ex

)+ h

(Y∣∣∣X = −

√Ex

)) h(Y∣X=√

Ex )=h(Y∣X=−√

Ex )=N (√

Ex ,σ2n)−−−−−−−−−−−−−−−−−−−−−−−−−−→

(Sommiamo costante a distribuzione gaussiana)

→ h(

Y∣∣∣X =

√Ex

)= log2

√2πeσ2

n

Ora abbiamo tutti gli elementi per calcolare la capacità di canale:

C = −∞∫−∞

p (y) log2 p (y)dy− log2

√2πeσ2

n =

= −∞∫−∞

p (y) log2 p (y)dy−∞∫−∞

p (y) log2

√2πeσ2

ndy =

= −∞∫−∞

p (y)(

log2 p (y) + log2

√2πeσ2

n

)dy = −

∞∫−∞

p (y) log2

(p (y)

√2πeσ2

n

)dy

L’ultimo integrale è ahimè calcolabile solo per via numerica; procedendo al calcolo otteniamo la figura4.14. Si noti che Ex è l’energia per uso del canale:

Ex

[energia

uso del canale

]= ESh

[energia

Shannon

]⋅ C[

Shannonuso del canale

]EShN0

=Ex

N0

1C

C≪1−−→ EShN0≫ Ex

N0

(4.20)

non bisogna dunque inquietarsi se il grafico pare andare più a sinistra del tanto blasonato limite diShannon. Se infatti facciamo il calcolo della capacità vera e propria (quella del grafico 4.8 con il limite di

Figura 4.14: Caso unquantized confrontato con il BSC

Shannon, tanto per intenderci) si ha:

EShN0︸︷︷︸

il limite di Shannon si applica qui!

=Ex

N0︸︷︷︸ad es. - 10 dB

1C

= −10 dB ⋅ 1

1−ℋ(

12

erfc√

Ex

N0

) = 0, 57 dB

Quindi siamo ben lontani dal limite invalicabile!

4.7 Low SNR region

Consideriamo ora il nostro canale BSC (vedi figura 4.12). La capacità del canale, ormai l’avremo capito,è

CBSC = 1−ℋ(p) (4.21)

62


mentre la probabilità p è:

p =12

erfc

√Ex

N0(4.22)

Concentriamoci però sulla zona cosiddetta Low SNR, ovvero quella tale per cui

z =

√Ex

N0→ 0 (4.23)

In tal caso possiamo sviluppare p(z) in serie di McLaurin:

p (z) McLaurin−−−−−→ p (0) +dpdz

∣∣∣∣z=0⋅ z︸︷︷︸→0

= p (0) +

d

{12

(1− 2√

π

z∫0

e−t2dt

)}dz

∣∣∣∣∣∣∣∣∣∣z=0

⋅ z︸︷︷︸→0

=

= p (0) +12

⎛⎝− 2√π

z︸︷︷︸→0

⎞⎠ ⋅ z︸︷︷︸→0

=12−

√Ex

N0π

La capacità del BSC è perciò:

CBSC = 1−ℋ (p) = 1 + plog2 p + (1− p) log2 (1− p)Sviluppo di Taylor−−−−−−−−−−→

intorno a p=0,5

→ CBSC

(12

)︸︷︷︸

=0

+dCBSC

dp

∣∣∣∣p0

(p− p0) +12

d2CBSCdp2

∣∣∣∣∣p0

(p− p0)2 =

=

(log2 p + p

1p

log2e− log2 (1− p)− log2e ⋅ (1− p) ⋅ 11− p

)p=0,5

(p− 1

2

)+

12

(d2CBSC

dp2

)p=0,5

(p− 1

2

)2=

= (log2 p− log2 (1− p))p=0,5︸︷︷︸=0

(p− 1

2

)+

12

(1p

log2e +1

1− plog2e

)p=0,5

(p− 1

2

)2=

=12(2log2e + 2log2e)p=0,5

(p− 1

2

)2= 2log2e ⋅

(p− 1

2

)2=

2ln 2

(p− 1

2

)2=

=2

ln 2

⎛⎜⎜⎜⎝ 12−

√Ex

N0π︸︷︷︸Trovato con McLaurin

−12

⎞⎟⎟⎟⎠2

=2

ln 2Ex

2σ2n︸︷︷︸

N0

π=

1ln 2

Ex

σ2nπ︸︷︷︸

BSC hard - decision LOW SNR

≈ 1ln 2

Ex

2σ2n︸︷︷︸

LOW SNR

Si noti che fra la penultima e l’ultima espressione (fra le quali intercorre il segno ≈) vi sono 2 dB didifferenza persi quantizzando.

4.8 Trattamento dei segnali passa-banda e water-filling

Nel caso di segnale passa-banda vale ancora la relazione:

C = B log2

(1 +

SN

)(4.24)

Ma che accade nel caso di canale distorcente caratterizzato da rumore gaussiano colorato (cioè non bianco)?Vincoliamo il segnale d’ingresso alla potenza S:

< x2(t) >= S (4.25)

E ora passiamo al calcolo della capacità e alla ricerca di un metodo per massimizzarla: effettueremo talecalcolo su piccoli intervallini ∆ f in cui possiamo considerare circa costante sia la ∣H( f )∣ che le densità

63


Figura 4.15: Caso passabanda

spettrali di potenza Gν( f ) e Gx( f ). Con questo piccolo trucco possiamo ancora fare i calcoli considerandoun canale non distorcente (∣H( f )∣ costante) on rumore AWGN (Gν( f ) costante) e scrivere, per ogni ∆ f :

Ci = Blog2

(1 +

SN

)= ∆ filog2

⎛⎜⎜⎝1 +

bilatera︷︸︸︷2∆ fi Gx ( fi) ∣H ( fi)∣2

2∆i f ⋅ Gν ( fi)

⎞⎟⎟⎠ = ∆i f log2

(1 +

Gx ( fi) ∣H ( fi)∣2

Gν ( fi)

)

Se ora mandiamo ∆ f → 0 e facciamo l’integrale su tutta la banda W otteniamo un’estensione della formuladi Hartley-Shannon:

C =∫W

log2

(1 +

Gx ( f ) ∣H ( f )∣2

Gν ( f )

)d f

Una volta fissata la potenza

S = 2︸︷︷︸bilatera

∫W

Gx ( f ) d f

è possibile scoprire quale fra tutte le possibili Gx( f ) massimizza C? Se la conoscessimo, potremmo sfrut-tarla! Per effettuare tale calcolo, ci serviamo del metodo dei moltiplicatori di Lagrange; cerchiamo quindi dimassimizzare la seguente espressione, dove µ è una variabile ausiliaria:

∫W

log2

(1 +

Gx ( f ) ∣H ( f )∣2

Gν ( f )

)− µGx ( f )d f

Deriviamo l’integrando rispetto a Gx e poniamo quindi uguale a zero il tutto:

1

1 +Gx ( f ) ∣H ( f )∣2

Gν ( f )

∣H ( f )∣2

Gν ( f )log2e− µ =

∣H ( f )∣2

Gν ( f ) + Gx ( f ) ∣H ( f )∣2log2e− µ = 0

64


Ma si ha anche:

∣H ( f )∣2

Gν ( f ) + Gx ( f ) ∣H ( f )∣2=

(Gν ( f )

∣H ( f )∣2+ Gx ( f )

)−1

=µ

log2e= costante

Dunque otteniamo:

Gx ( f ) =

⎧⎨⎩costante− Gν ( f )

∣H ( f )∣2se tale sottrazione dà come risultato un numero positivo

0 se la sottrazione di cui sopra dà come risultato un numero negativo

Perciò Gx( f ) sarà per forza sempre positiva; possiamo ora inoltre scriverne un’espressione generale:

Gx ( f ) =

⎧⎨⎩max

{costante− Gν ( f )

∣H ( f )∣2, 0

}nella banda W

0 altrove

Il risultato sembra non dire niente? E invece nasconde un’importantissima informazione! Si osservi lafigura 4.16: lo spettro Gx( f ), lo ricordiamo, è la differenza fra il valore costante e la curva in figura. Nellazona verde, dove il canale è buono, questa quantità è maggiore di zero (e quindi è un valore ammissibile inquanto positivo), mentre altrove risulta essere negativa e quindi, come indicato nelle formule precedenti,in tali luoghi non impiegheremo potenza (Gx( f ) = 0). In soldoni, la morale della favola è che convieneinvestire sui canali migliori e non sprecare potenza dove c’è molto rumore, perché il gioco non varrebbe lacandela. Tale tecnica viene chiamata water-filling (o water-pouring) in quanto è visivamente comprensibilese immaginiamo di avere una certa quantità d’acqua (cioè di potenza) e di versarla sulla curva in figura:essa andrà certamente a insinuarsi nelle zone a quota minore (= canale migliore) e le riempirà, ignorandocompletamente tutte le altre parti della banda W.

Figura 4.16: La tecnica del waterfilling

4.8.1 Caso tempo-discreto

Questo ragionamento può essere ripreso pari pari nel caso tempo-discreto. Immaginiamo di avere Ncanali in parallelo e sia quello in figura 4.17 il generico canale i-esimo, dove λi è il guadagno in potenzadato che

√λi è il guadagno in tensione.

65


Figura 4.17: Canale i-esimo

Figura 4.18: Guadagno in potenza e canali

La banda viene ora suddivisa in tanti canali e su ciascuno di essi inviamo un segnale (tecnica OFDM4).Quanta potenza viene trasmessa?

E[

X21

]+ E

[X2

2

]+ . . . + E

[X2

n

]= ∑

kE[

X2k

]= ∑

kSk = S

Ora il problema è come ripartirla, ma il discorso rispetto a prima non cambia:

Ci =12

log2

(1 +

E[x2

i]

λi

σ2

) [Shannon

uso del canale

]Massimizziamo quindi C tenendo conto del vincolo sulla potenza e usiamo nuovamente il metodo deimoltiplicatori di Lagrange: il risultato è il seguente:

Sk = max(

cost− σ2

λk, 0)

Si veda quindi la figura 4.19, in cui la somma delle frecce tratteggiate rosse rappresenta la potenza S delsegnale utile: il principio è esattamente identico a quello del caso continuo.

4Orthogonal Frequency Division Multiplexing.

66


Figura 4.19: Water-filling nel caso discreto

67


68

Capitolo 5

I codici di canale: codici a blocco

I codici possono essere raccolti in una precisa gerarchia:

∙ codici a blocco: vedi questo capitolo.

– lineari: vedi paragrafo 5.3.

∗ ciclici: vedi paragrafo 5.18.∗ sistematici (categoria ’trasversale’): vedi paragrafo 5.5.

– non lineari.

∙ codici a traliccio: vedi il capitolo 6.

– convoluzionali (lineari): vedi paragrafo 6.1.

– non lineari.

5.1 Codici a blocco

Figura 5.1: Schema della codifica a blocco lineare

Come si vede dalla figura 5.1, il codificatore di un codice a blocco emette blocchi di n bit1 per ogniblocco d’ingresso di k bit. Di seguito chiameremo:

∙ code-rate il rapporto Rc =kn . Tanto minore è la code-rate e tanto più ridondante sarà il codice;

∙ Eb l’energia per bit d’informazione (nel caso binario 1 bit = 1 Shannon);

∙ Ebc l’energia per bit codificato;

∙ Br la bit-rate, misurata in bit/s;

∙ Brc il numero di bit codificati al secondo. Chiaramente Brc > Br perché la code-rate è < 1 e dunquesono molti di più i bit che trasmettiamo di quelli che dobbiamo codificare dalla sorgente.

1Volendo rimanere nel caso generale dovremmo parlare di simboli, perché a rigore non è detto che l’alfabeto sia semplicementequello binario (altri possibili alfabeti sono tipicamente quelli di cardinalità 2q con q > 1). Tuttavia quest’ultima casistica è quella dimaggiore interesse e quindi daremo per scontato di lavorare con l’alfabeto {0, 1}.

69

70 CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

Supponendo di aver fissato la potenza media di trasmissione S possiamo scrivere:

S = Ebc ⋅ Brc = Eb ⋅ Br

Da quest’ultima relazione si ricava anche:EbEbc

=Brc

Br

Inoltre, se introduciamo anche il termine di rumore N0 (tipico del caso AWGN) otteniamo:

EbcEb

=Br

Brc⇒ Ebc

N0=

EbN0

Br

Brc=

EbN0

Rc

Consideriamo ora tutte le possibili codeword in uscita dal codificatore e immaginiamo di metterle tuttenell’insieme C: tale insieme è quello che in figura 5.2 è indicato in azzurrino. Come si nota, perché uncodice sia sensato deve sussistere un mapping iniettivo fra le parole di lunghezza 2k e quelle di codice(valide) di lunghezza 2n.

Figura 5.2: Insieme delle parole non codificate e mapping iniettivo verso quello delle parole codificate

ESEMPIO:Codice a ripetizione (3,1)

Abbiamo 21 possibili parole d'informazione di lunghezza 1, ovvero il bit '0' e il bit '1'. Esse

vengono mappate rispettivamente in '000' e '111', basandosi cioè sul semplice criterio di ripetizione

del bit d'informazione che si vuole trasmettere. Le parole codi�cate (2 su un totale di 23 possibili

stringhe lunghe 3) non sono però state prese a caso: esse sono infatti scelte a�nché abbiano distanza

massima (tutti i bit sono infatti di�erenti). Non è l'unica possibile opzione a nostra disposizione: si

poteva ad esempio propendere per '101' e '010', oppure per '001' e '110' etc. . .

5.1.1 Alcune definizioni e terminologia

Chiameremo:

∙ peso wi di una parola di codice: numero di ’1’ (uni) all’interno della parola di codice. Ovviamente siha che:

0 ≤ wi ≤ n

∙ distribuzione dei pesi {wi}: insieme dei pesi di tutte le parole di codice. La distribuzione dei pesicaratterizza le proprietà della distanza del codice;

70

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO 71

∙ distanza di Hamming dij = dH(ci, cj) fra due parole di codice ci, cj: numero di posizioni in cui le dueparole sono differenti;

∙ distanza minima del codice: è definita come

dmin = mini ∕=j

dij (5.1)

e coincide con il peso minimo (esclusa la parola di tutti zeri):

dmin = min∕=0

(wr) (5.2)

5.2 Concetti elementari di algebra lineare

Supponiamo di porci in un Galois field (campo di Galois) con cardinalità q e di dimensione n (si indicaGF(qn)). Possiamo definire la somma componente per componente (componentwise sum), che nel casobinario diventa la semplice somma ’modulo 2’:

(c1, c2, . . . , cn) + (d1, d2, . . . , dn) = (c1 + d1, c2 + d2, . . . , cn + dn) (5.3)

Possiamo poi definire la moltiplicazione scalare componente per componente (componentwise scalar molti-plication):

k(c1, c2, . . . , cn) = (kc1, kc2, . . . , kcn) (5.4)

Indicando con S il campo di Galois appena descritto una volta definite queste operazioni, possiamo defi-nire anche dei sottospazi vettoriali: possiamo ad esempio scegliere k vettori di lunghezza n linearmenteindipendenti

c1, c2, . . . , ck

e le possibili combinazioni lineari di questi ultimi genereranno il sottospazio SC di dimensione k. I vettoriortogonali ai vettori di SC genereranno invece un sottospazio ortogonale a SC (che chiameremo S⊥C ) cheavrà dimensione n− k. Ovviamente, qualunque codice C è un sottospazio di GF(q)n.

Nel caso di codici a blocco lineari binari, il nostro insieme S (quello che prima coincideva con il campodi Galois tutto intero) conterrà tutti i possibili vettori binari di lunghezza n. Se SC è un sottoinsieme di Savente cardinalità 2k, allora il sottoinsieme ortogonale S⊥C avrà cardinalità 2n−k e genererà il codice duale aquello generato da SC.

5.3 Codici a blocco lineari

In un codice lineare la combinazione lineare di due parole di codice restituisce un’altra parola di codice:

∀ci, cj ∈ C; ∀α, β ∈ {0, 1} ⇔ αci + βcj ∈ C (5.5)

Questo ha due principali conseguenze:

1. se il codice è lineare contiene la parola di codice di tutti zeri;

2. se il codice è lineare la distanza di Hamming fra ci e cj coincide con il peso di ci − cj:

dH(ci, cj) = w(ci − cj) = w(ci + cj) (5.6)

ESEMPIO:Il codice a ripetizione (3,1), già visto in un precedente esempio, è un codice lineare in quanto tutte

le possibili somme fra le parole di codice restituiscono un'altra parola di codice2. Supponiamo di

trasmettere tramite questo codice attraverso un BSC caratterizzato da probabilità di transizione

p < 1/2 e facciamo l'ipotesi che il decoder decida a maggioranza: le codeword 000, 100, 010 e 001

verranno quindi interpretate come 000 (bit '0') mentre 110, 101, 110 e 111 verranno interpretate

come 111 (bit '1'). Questo criterio è abbastanza ragionevole, anche se non è infallibile: può infatti

2D’altronde le parole di codice sono soltanto due e una ha tutti zeri, quindi. . .

71


capitare che vengano sbagliati due bit (o addirittura tre bit, se è il nostro giorno sfortunato) all'interno

della stessa parola di codice. Calcoliamo la probabilità che ciò accada, cioè calcoliamoci la seguente

quantità:

Pe = Pr

⎧⎨⎩ Bn︸︷︷︸Stimato

∕= Bn︸︷︷︸Trasmesso

⎫⎬⎭ = Pr {2 o 3 errori nella parola di codice} =

= p3︸︷︷︸3 errori

+ p ⋅ p ⋅ (1− p)︸︷︷︸2 errori e 1 bit corretto

(32

)= p3 + 3

[p2 (1− p)

]= 3p2 − 2p3

Ci abbiamo guadagnato o no? Se facciamo il confronto con il sistema uncoded scopriamo di sì (vedi

�gura 5.3, gra�co a sinistra), perché 3p2 − 2p3 < p se p < 0, 5. Tuttavia il prezzo da pagare è stato

molto alto: mentre prima trasmettevamo un unico bit ora ne dobbiamo infatti trasmettere tre, cosa

che comporta parecchi sacri�ci in termini di energia.

Figura 5.3: Confronto fra il caso non codificato e il codice a ripetizione (3,1)

Supponiamo infatti di e�ettuare la stessa trasmissione con codice a ripetizione attraverso un canale

AWGN, trasmissione antipodale e uso di hard decision. In questo caso si ha

p =12

erfc

√EbcN0

dove Ebc è l'energia della forma d'onda che rappresenta un bit codi�cato e che costituisce una frazione

di quella che possiamo pensare attribuita su un bit d'informazione:

Ebc = EbRc ⇒ p =12

erfc

√EbcN0

=12

erfc

√√√√⎷Eb

=1/3︷︸︸︷Rc

N0>

12

erfc

√EbN0

Dunque conviene non codi�care e utilizzare il triplo dell'energia per bit trasmesso, oppure codi�care

e accontentarsi del quantitativo energetico Ebc per ogni bit codi�cato? La �gura 5.3 (�gura a destra)

ci mostra che in realtà le cose vanno peggio nel caso codi�cato!

ESEMPIO:Codice a singolo bit di parità (single parity check code)

L'encoder per questo tipo di codici funziona nel seguente modo: prende in ingresso una parola

di k bit ed emette in uscita una parola di n = k + 1 bit che altro non è se non la parola in ingresso

concatenata con un bit di parità, il quale - come suggerisce il nome - ha il compito di rendere pari il

numero di '1' all'interno della parola codi�cata. Se al ricevitore perviene una parola con peso dispari

(cioè con un numero dispari di '1'), allora l'errore potrà essere rilevato (ma non corretto: chi ci dice

qual è il bit sbagliato?). Questo tipo di codice è in grado di correggere solo un numero dispari di

72


errori in quanto due errori su una parola di codice (che avrà sicuramente peso pari) renderanno la

parola nuovamente pari e non permetteranno la rilevazione. Possiamo però fare moooooolto meglio

di così: continuate a seguirci su questi schermi e scoprirete come!

5.4 La matrice generatrice

Consideriamo un certo codice lineare: sia

xm = (xm1, xm2, . . . , xmk)

una possibile parola d’informazione, mentre sia

cm = (cm1, cm2, . . . , cmn)

la relativa parola di codice. Il generico bit cmj della parola di codice può anche essere visto come una com-

Figura 5.4: Ogni bit della parola di codice è combinazione lineare dei bit della parola d’informazione

binazione lineare dei bit d’ingresso (cioè dei bit della parola d’informazione, vedi figura 5.4), perpetratatramite i coefficienti g:

cmj = xm1g1j + xm2g2j + . . . + xmngmj (5.7)

Dunque possiamo impostare il seguente sistema lineare per trovare tutti i bit cm j della parola codificatacm ⎧⎨⎩

cm1 = xm1g11 + xm2g21 + . . . + xmkgk1

cm2 = xm1g12 + xm2g22 + . . . + xmkgk2

. . .

cmn = xm1g1n + xm2g2n + . . . + xmkgkn

Questo sistema lineare ha ovviamente una forma matriciale

cm = xmG = xm

⎡⎢⎢⎢⎢⎣g11 g12 ⋅ ⋅ ⋅ g1n

g21. . .

......

. . ....

gk1 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ gkn

⎤⎥⎥⎥⎥⎦e G viene chiamata la matrice generatrice del codice. In matematichese, il codice C è lo spazio-riga dellamatrice G, ovvero l’insieme delle combinazioni lineari delle righe di tale matrice. Un’operazione di rigasulla matrice G non modifica il codice (si modifica la base del sottospazio, ma non il sottospazio stessoquindi le parole di codice rimangono invariate); nemmeno una permutazione di colonne della matriceG modifica il codice perché permutiamo i bit in tutte le parole di codice (dunque i pesi, le distanze,etc. . . rimangono invariati). Dunque un codice ottenuto da G tramite operazioni di riga e/o di colonna(permutazioni) è un codice equivalente a quello di partenza. In altre parole, due matrici G1 e G2 siriferiscono a due codici equivalenti se una si può ottenere dall’altra con operazioni di riga e permutazionidi colonna.

73


5.5 Codici sistematici

Ogni matrice generatrice G può essere ridotta, tramite operazioni di riga e/o permutazioni di colonnain una forma sistematica tale per cui:

Gk×n =[

Ik×k

∣∣∣Pk×(n−k)

](5.8)

In tale relazione I è la matrice identità e P viene detta matrice di parità. Questa strutturazione della matricegeneratrice ha il grosso vantaggio di conferire alla generica parola codificata la seguente struttura:

xm1, xm2, . . . , xmk︸︷︷︸parte sistematica = parola d’informazione

, cm(k+1), . . . , cmn︸︷︷︸parte di parità = comb. lin. dei primi k bit

Dunque nei primi k bit della parola codificata troviamo la parola d’informazione: per il ricevitore, senon vengono rilevati errori, sarà quindi sufficientemente tagliare via gli n− k bit della parte di parità perottenere la parola che volevamo trasmettere, senza dover effettuare alcuna operazione di combinazionelineare per rilevarla.

ESEMPIO:Il codice a ripetizione (3,1) ha matrice generatrice:

G =[

1 1 1]

La parte di parità (2× 1) è costituita dagli ultimi 2 uni, mentre la matrice identità (1× 1) è il primo

uno. Provando a moltiplicare le uniche due parole d'informazione disponibili (i bit '0' e '1') otteniamo:{0 ⋅ 111 = 000

1 ⋅ 111 = 111

Le due parole di codice sono quindi 000 e 111. Questo codice è evidentemente sistematico.

ESEMPIO:Il codice generato dalla seguente

G =

⎡⎣ 1 0 0 1 10 1 0 0 10 0 1 0 1

⎤⎦è sistematico. Tale codice è equivalente a quello generato dalla seguente matrice

Geq =

⎡⎣ 1 1 1 0 00 0 1 1 01 1 1 1 1

⎤⎦Infatti basta e�ettuare le seguenti operazioni di riga e colonna per ottenere G:

Geq =

⎡⎣ 1 1 1 0 00 0 1 1 01 1 1 1 1

⎤⎦⇒⎡⎣ 1 1 0 1 0

0 0 1 1 00 0 0 1 1

⎤⎦⎛⎝ ← I + II

invariato

← I + III

⎞⎠⇒⎡⎣ 1 0 0 1 1

0 1 0 0 10 0 1 0 1

⎤⎦︸︷︷︸

permuto colonne

5.6 Matrice di controllo parità

Se il codice C è stato ottenuto (generato) dalla matrice G, allora il codice C⊥ ortogonale a C, detto codiceduale, sarà ottenuto dalla matrice di controllo parità (parity check matrix) H.

Matrice generatrice⇒ Gk×n ⇒ Codice CMatrice di controllo parità ⇒ H(n−k)×n ⇒ Codice C⊥

74


Codice C Codice duale C⊥

Matrice generatrice Gk×n H(n−k)×n

Matrice di controllo parità H(n−k)×n Gk×n

Tabella 5.1: Matrici generatrici e di controllo parità di un codice e del suo duale

Codice e codice duale sono in rapporto fra loro come definito nella tabella 5.1: è però necessario specificareche, così come per un certo codice C la matrice G non è unica, anche la matrice di controllo parità non saràunica (purché lo spazio generato sia lo stesso). Un qualsiasi vettore c di C, per definizione, sarà ortogonalea qualunque vettore u di C⊥. Inoltre, si avrà che:

H ⋅ cT = 0, ∀c ∈ C (5.9)

Dunque un qualsiasi vettore del codice C, moltiplicato per la matrice di controllo parità trasposta HT ,deve dare come risultato zero: tale condizione è necessaria e sufficiente e ciò significa che una parola nonappartenente al codice C, giunta a destinatario e frutto di uno o più errori di trasmissione, se moltiplicataper HT restituirà un risultato diverso da zero. In queste semplici considerazioni è quindi nascosto ilprincipio di rilevazione degli errori per i codici di questo tipo.

Se G è in forma sistematica si ha che:

G =[

I ∣P]⇒ H =

[−PT ∣I

] in GF(2)−−−−→[

PT ∣I]

Sarà vero? L’Ingegnere Pazzo dice forse delle balle? Probabile, ma facciamo la controprova:

GHT =[

I ∣P] [ PTT

IT

]=[

I ∣P] [ P

I

]= P + P = 0

Fortunatamente tutto torna.

ESEMPIO:Troviamo la matrice di controllo parità del codice a ripetizione (3,1), avente la seguente

G =[

1 1 1]

Siccome abbiamo detto che

G =[

I ∣P]⇒ H =

[−PT ∣I

] in GF(2)−−−−−→[

PT ∣I]

allora la matrice di controllo parità sarà:

H =[

PT ∣I]=

[1 1 01 0 1

]Tale matrice è anche la matrice generatrice del single parity check code: se la permutiamo per colonne

otteniamo infatti: [1 1 01 0 1

]⇒[

1 0 10 1 1

]Di norma, il duale di un codice a ripetizione è un codice di tipo single parity check.

ESEMPIO:Codice di Hamming3 (7,4)

NOTA: per maggiori informazioni consulta il paragrafo 5.10.

3Richard Wesley Hamming (Chicago, 11 febbraio 1915 - Monterey, 7 gennaio 1998) è stato un matematico statunitense, famosoper l’ideazione del Codice di Hamming. Dopo il dottorato conseguito all’Università dell’Illinois nel 1942, Hamming fu professoreall’Università di Louisville fino all’inizio della Seconda guerra mondiale. Nel 1945 fece parte del Progetto Manhattan, programmandouno dei calcolatori digitali per calcolare le soluzioni delle equazioni fornite dai fisici del progetto. Nel 1968 ricevette il Premio Turing.

75


peso w n∘ di codeword

0 13 74 77 1

Tabella 5.2: Distribuzione dei pesi del codice di Hamming (7,4)

Consideriamo una matrice H fatta ad arte

H =

⎡⎣ 1 1 1 0 1 0 00 1 1 1 0 1 01 1 0 1 0 0 1

⎤⎦in cui le prime quattro colonne, costituenti la sottomatrice P, sono costituite da tutte le possibili

combinazioni di 3 bit aventi almeno due uni, mentre le ultime tre colonne formano una matrice

identità I: in questo modo, le 7 colonne della matrice di controllo parità costituiscono tutti i modi

possibili in cui si può formulare un vettore di lunghezza tre, se escludiamo la parola di tutti zeri. Tutte

le matrici costruite in questo modo generano codici equivalenti a quello di Hamming. Ricordando la

solita relazione, per cui

G =[

I ∣P]⇒ H =

[−PT ∣I

] in GF(2)−−−−−→[

PT ∣I]

allora la matrice G sarà:

G =[

I ∣P]=

⎡⎢⎢⎣1 0 0 0 1 0 10 1 0 0 1 1 10 0 1 0 1 1 00 0 0 1 0 1 1

⎤⎥⎥⎦Il codice generato da G è detto Codice di Hamming (7,4) e ha la distribuzione dei pesi indicata in

tabella 5.2: si noti che la distanza minima del codice, in questo caso, è 3.

5.7 Codici estesi

Supponiamo di voler allungare le parole di codice aggiungendo un ulteriore bit di parità che sia laparità dei bit precedenti. Un escamotage del genere potrebbe servire, ad esempio, per allungare la distanzaminima di un nostro codice C: chiaramente quest’intervento non è ’gratuito’ perché si ha una diminuzionedella rate di codifica e un conseguente aumento di ridondanza.

Per creare un codice esteso siffatto è sufficiente estendere la matrice H nel seguente modo:

Hext =

[H 01 1

]Nella formula precedente 0 è un vettore colonna di tutti zeri, 1 un vettore riga di tutti uni e H la matricedi controllo parità del codice di partenza. Con la precedente modifica effettuiamo il seguente passaggio:

Codice C ⇒ (n, k) estensione−−−−−→ (n + 1, k)⇒ Codice Cext

ESEMPIO:Consideriamo il codice di Hamming (7,4) e la sua versione estesa (8,4). Se ricaviamo gli spettri di

tali codici otteniamo la tabella 5.3. La distanza minima del codice, come si nota, è aumentata da 3

a 4.

Come accennato poco fa il rovescio della medaglia sta nel fatto che, mentre prima trasmettevamo 7 bitdi codice per 4 bit di informazione, ora dobbiamo inviarne uno in più (per un totale di 8), il che comportaun dispendio maggiore di energia. La code-rate si è infatti abbassata da 4/7 a 4/8 = 1/2.

76


peso w Hamming (8,4) (esteso) peso w Hamming (7,4) n∘ di codeword

0 0 14 3 75 4 78 7 1

Tabella 5.3: Distribuzione dei pesi del codice di Hamming (7,4) e della versione estesa

peso w Hamming (7,3) (purgato) peso w Hamming (7,4) n∘ di codeword

0 0 1purgato! 3 7

4 4 7purgato! 7 1

Tabella 5.4: Distribuzione dei pesi del codice di Hamming (7,4) e della versione purgata

5.8 Codici purgati

L’operazione duale a quella dell’estensione, ma avente la stessa capacità di aumentare la distanzaminima del codice, si chiama purga: se effettuata permette la seguente transizione

Codice C ⇒ (n, k)purga−−−→ (n, k− 1)⇒ Codice Cpurg

Per ottenere tale risultato è sufficiente prendere soltanto le parole di peso pari del nostro codice dipartenza, il che equivale modificare nel seguente modo la matrice H (che diventerà una n− k + 1× n):

Hpurg =

[H1

]Nella formula soprastante s’intende che H è la matrice di controllo parità del codice non purgato e 1 unvettore di tutti uni. La distanza minima del codice è aumentata (vedi tabella 5.4, in cui si fa un esempiocol solito codice di Hamming (7,4)), ma anche questa volta la code-rate è diminuita in quanto è passata da4/7 a 3/7.

5.9 Il Singleton Bound

Si dimostra che esiste un limite superiore alla distanza minima di un codice, dati i parametri k e n: talelimite è denominato Singleton Bound. Si ha infatti la seguente disequazione:

dmin ≤ n− k + 1 (5.10)

La dimostrazione è abbastanza intuitiva; prendiamo ad esempio un codice sistematico4: il meglio chepossiamo fare è quello di manipolare il codice affinché venga assegnata una parte di parità (lunga n− k)costituita interamente di uni ad una parola d’informazione con un solo 1. In questo modo otteniamo

000..010..000 | 111...11

parte sistematica (peso 1) | parte di parità (peso n-k)

Tale parola di codice avrebbe distanza di Hamming pari a n− k + 1 dalla parola di tutti zeri. A questopunto, per non peggiorare (diminuire) la distanza minima del nostro codice, dobbiamo cercare di aumen-tare (o al limite di non far calare) il peso di tutte le altre parole, cosa abbastanza plausibile visto che -certo, la parte di parità non potrà più avere tutti ’1’ - ma la parte sistematica possiamo ancora ’gonfiarla’di bit a uno. Meglio di così non possiamo fare: se affidassimo quella stessa parte di parità (tutti 1) ad unaparola di codice avente una parte sistematica con due ’1’

4Senza perdere in generalità, in quanto per ogni codice è possibile trovarne un equivalente sistematico.

77


n k code-rate Rc

3 1 1/37 4 4/7

15 11 11/15

Tabella 5.5: Parametri n e k per codici di Hamming

000..0110..000 | 111...11

parte sistematica (peso 2) | parte di parità (peso n-k)

potremmo pensare di aver fatto meglio in quanto distiamo dalla parola di tutti zeri n − k + 2. Tuttaviaquesta non sarebbe la distanza minima del codice, perché esisterebbe sicuramente una codeword con un ’1’in meno nella parte sistematica e una parte di parità diversa da quella di tutti uni (mettiamo, per esempio,con un ’1’ in meno):

000..010..000 | 111..101..11

parte sistematica (peso 1) | parte di parità (peso n-k-1)

Questa parola di codice avrebbe un numero di uni inferiore a quello della parola di peso n − k + 2 equindi si candiderebbe ad essere quella di peso minimo; se così fosse (e sarebbe un caso fortunato),avremmo ottenuto una distanza minima del codice addirittura inferiore rispetto a quella del Singletonbound (n− k− 1 + 1 = n− k < n− k + 1).

Se il codice ha distanza minima pari a n− k + 1 allora viene denominato maximum distance separablecode (MDSC). Ma è poi così importante disporre di un codice MDSC? Apparentemente sì, ma in realtà inGF(2) gli unici codici ad avere questa proprietà sono quelli a ripetizione, che sappiamo non essere propriobrillantissimi. . . Ma d’altronde chi ha mai detto che i MDSC sarebbero stati i migliori a prescindere?

5.10 Codici di Hamming

Abbiamo già accennato ai codici di Hamming in un esempio del paragrafo 5.6: in particolare si èaccennato al fatto che essi vengono costruiti a partire dalla matrice di controllo parità, imponendo che lecolonne di quest’ultima contengano tutte le possibili configurazioni (tranne quella di tutti zeri) di vettorilunghi n− k. Dunque, fissati n e k, i codici di Hamming validi sono quelli aventi un numero di colonne nin grado di soddisfare la seguente relazione

n = 2n−k − 1

dove 2n−k è il numero di configurazioni possibili per vettori lunghi n − k e il −1 serve ad escludere laparola di tutti zeri. In tabella 5.5 riportiamo alcuni valori di n e k ammissibili per i codici di Hamming(ma si potrebbe ovviamente continuare). I codici di Hamming vengono detti codici perfetti in quanto unqualunque vettore di lunghezza n o è una codeword oppure è distante⌊

dmin − 12

⌋da una parola di codice valida5.

5.11 La decodifica e la Teoria della Decisione

Facciamo tornare un po’ in auge quanto detto nei primi capitoli per la Teoria dell’Informazione eapplichiamo il ragionamento sui nostri codici (sia quello in figura 5.5 lo schema di riferimento). Se peripotesi cm è una parola di codice allora anche ciò che è stato stimato dal decisore ( ˆcm) lo dev’essere, se laparola è stata trasmessa correttamente. Ma qual è la probabilità di effettuare una scelta corretta? Su qualecriterio dobbiamo basarci per sbagliare il meno possibile? Definiamo:

5Inoltre, non vi sono interstizi fra le regioni di decisione (vedi paragrafo 5.14.

78


Figura 5.5: Lo schema di trasmissione: codifica, decodifica e decisione

∙ p(ci) la probabilità (a priori) che venga trasmesso ci;

∙ p(ci∣y) la probabilità (a posteriori) che sia stato trasmesso ci sapendo che è stato ricevuto y.

Qual è il criterio di scelta a minima probabilità d’errore per il nostro decisore? La Teoria della Decisioneci suggerisce di prendere la parola che massimizza la probabilità a posteriori (MAP, Maximum a-posterioridetection):

cm = argc∈C

max p(ci∣y) (5.11)

Possiamo poi applicare il criterio di Bayes:

p (c ∣y ) = p (y ∣c ) p (c)p (y)

(5.12)

La quantità p (y ∣c ) viene denominata funzione di verosimiglianza (likelyhood function). Al variare di c simodifica, della 5.12, solo il numeratore, dunque il decodificatore MAP massimizza quest’ultimo:

cm = argc∈C

max p (y ∣c ) p (c)

Nel caso i simboli siano equiprobabili le probabilità p(ci) saranno pari a 1/M (dove M è il numerototale di parole d’informazione): in questo caso si parla di maximum likelyhood detection (criterio ML) e ildecodificatore deve limitarsi a massimizzare

cm = argc∈C

max p(y∣c) (5.13)

5.12 Decodifica ottima per codici a blocco su canale BSC

Sia:

∙ cm la parola in ingresso al BSC;

∙ p la probabilità di transizione del canale;

∙ r l’osservabile, ovvero ciò che esce dal canale;

∙ ˆcm il simbolo per il quale decide il decoder.

Inoltre supponiamo che le parole siano tutte equiprobabili, cioè che si abbia:

ci =12k , ∀i

Il decoder ML si basa sulla seguente relazione:

cm = argc∈C

max p(r∣c) (5.14)

Dobbiamo però calcolare p(r∣c):

p(r∣c) =n

∏i=1

p ( ri∣ ci) ⇐ p ( ri∣ ci) =

{p se ri ∕= ci

1− p se ri = covvero

{p = p (1 ∣0 ) = p (0 ∣1 )1− p = p (0 ∣0 ) = p (1 ∣1 )

Quindi si ha:

p(r∣c) =n

∏i=1

p ( ri∣ ci) =n

∏i=1

pdH(ri ,ci) ⋅ (1− p)(1−dH(ri ,ci))

79


La produttoria possiamo portarla all’esponente (e farla quindi diventare una sommatoria):

p(r∣c) =n

∏i=1

pdH(ri ,ci) ⋅ (1− p)(1−dH(ri ,ci)) = p∑i

dH(ri ,ci)⋅ (1− p)

∑i(1−dH(ri ,ci))

Le quantità all’esponente (sommatorie della distanza di Hamming fra bit) possono essere viste comedistanze di Hamming calcolate sui vettori:

∑i

dH (ri, ci) = dH (r, c)

∑i(1− dH (ri, ci)) = n− dH (r, c)

Dunque:

p(r∣c) = pdH(r,c) ⋅ (1− p)n−dH(r,c) =

(p

1− p

)dH(r,c)⋅ (1− p)n

La quantità che il decoder deve massimizzare è il primo fattore, quello in cui compare c:(p

1− p

)dH(r,c)

Ma se la base è minore di 1 (ed è questo il caso, perché p1−p è minore di 1 quando p < 0, 5), l’esponenziale

è massimo quando è minimo l’esponente, ovvero quando è minimo dH(r, c). Ecco quindi trovata unaformulazione alternativa e molto significativa (anche se apparentemente ovvia) del criterio ML:

cm = arg minc∈C

dH (r, c) (5.15)

Tradotto in parole povere, il decodificatore ottimo è quello che decide in base alla minima distanza diHamming: ricevuto il vettore r, il decoder propenderà quindi per la parola di codice c con meno bitdifferenti rispetto a r stessa.

5.13 Rilevazione degli errori e standard array

Consideriamo ancora lo schema di figura 5.5: una volta definito e come il vettore errore, ovvero ilvettore che contiene degli ’1’ in corrispondenza dei bit che il canale BSC ha alterato per colpa del rumore,possiamo scrivere

r = cm + e

Come possiamo, lato decodifica, agire per scegliere la parola di codice più plausibile? Due opzioniequivalenti, e tuttavia non molto efficaci vista la mole di operazioni da effettuare, possono essere:

1. ricevere r, calcolare la distanza di Hamming con le 2k parole di codice e scegliere quella a distanzaminima;

2. calcolare r + cl per ogni l e scegliere la parola che minimizza il peso w(el).

Come accennato poco fa, tuttavia, questi metodi non sono molto performanti: k può infatti diventareconsistente e 2k ’esplodere’, cosa che non possiamo assolutamente permetterci. Fortunatamente esiste unterzo metodo: sappiamo infatti che

HcT = 0 = cHT

Supponiamo di poter prendere r e di moltiplicarla per HT :

r ⋅HT = (cm + e)HT = 0 + eHT = s

Il vettore s viene chiamato sindrome dell’errore; il numero di possibili sindromi è pari a 2n−k e ad ognunadi esse è associato un pattern d’errore ovvero il vettore e che, moltiplicato per HT , restituisce la s stessae che corrisponde quindi alla ’mappa’ dei bit invertiti nel passaggio attraverso il canale rumoroso. Latabella in cui vengono messi in corrispondenza le sindromi e i pattern d’errore (di peso minimo, visto che

80


sindrome pattern d’errore

s1 e1s2 e2. . . . . .

s2n−k e2n−k

Tabella 5.6: La tabella di decodifica

s1 = 0 c1 =0 c2 . . . c2k

s2 e2 c2 + e2 . . . c2k + e2...

...... . . .

...s2n−k e2n−k c2 + e2n−k . . . c2k + e2n−k

Tabella 5.7: Lo Standard Arrary

per ipotesi si vuole utilizzare il criterio ML) è chiamata tabella di decodifica (vedi tabella 5.6). Dunque dar calcoliamo s, poi dalla tabella determiniamo il pattern d’errore di peso minimo e infine lo sommiamo adr per ottenere cm. Si noti che, fatta l’ipotesi di aver sbagliato per la parola più vicina, se e non è il patterndi peso minimo, il decodificatore produce una parola di codice corretta ma diversa da quella trasmessa.

Siccome poi si ha che la generica sindrome sl è generata da el , ma anche da el + ck, ∀k in quanto si ha

(el + ck)HT = elH

T + ckHT︸︷︷︸=0

è possibile estendere la tabella di decodifica aggiungendo 2k − 1 colonne che considerino anche i casinon di peso minimo. Così facendo si crea lo Standard Array (o matrice canonica, vedi tabella 5.7), in cuivengono riportati le sindromi e tutti i modi in cui tali sindromi possono essere ottenute a partire dallevarie parole di codice valide. Ogni riga (coset) corrisponde a una determinata sindrome, ogni colonna aduna parola di codice (sommata di volta in volta con tutti i possibili pattern d’errore); la prima colonna(quella più a sinistra) è chiamata coset leader in quanto contiene gli errori di peso minimo.

ESEMPIO:Abbiamo la seguente matrice per un codice (5,2):

G =

[1 0 1 0 10 1 0 1 1

]Ad essa corrisponde la seguente matrice di controllo parità:

H =

⎡⎣ 1 0 1 0 00 1 0 1 01 1 0 0 1

⎤⎦Vogliamo riempire il relativo standard array ; per calcolare la sindrome e�ettuiamo la seguente opera-

zione:

s = rHT = (cm + e)HT = eHT = e ⋅

⎡⎢⎢⎢⎢⎣1 0 10 1 11 0 00 1 00 0 1

⎤⎥⎥⎥⎥⎦ =[

s1 s2 s3]⇒ 23 sindromi

Dopodiché ci serviamo di questa relazione per riempire la nostra matrice canonica (vedi tabella 5.8): in

neretto sono evidenziate le parole di codice valide. Le righe successive si possono costruire sommando

il pattern d'errore di peso minimo (seconda colonna) alle rispettive parole valide. Supponiamo, per

esempio, di ricevere 10011: moltiplicando tale vettore per la matrice HT otteniamo 110. A questo

punto consultiamo lo standard array e otteniamo la stringa 11000, la sommiamo a 10011 e otteniamo

in�ne la decisione del decoder (01011).

81


s e

000 00000 01011 10101 11110001 00001 01010 10100 11111010 00010 01001 10111 11100011 00100 01111 10001 11010100 01000 00011 11101 10110101 10000 11011 00101 01110110 11000 10011 01101 00110111 10010 11001 00111 01100

Tabella 5.8: Lo Standard Array dell’esempio

5.14 Capacità di correzione di un codice (canale BSC)

Come mostrato nei capitoli precedenti, il decodificatore ottimo cerca sempre la parola di codice piùvicina a quella ricevuta (nel senso della distanza di Hamming). Così facendo si creano delle partizioni(decision regions), ognuna della quale fa capo ad una parola di codice (vedi figura 5.6). Non è tuttavia

Figura 5.6: Regioni di decisione

questa l’unica scelta possibile: possiamo per esempio optare per un decoder a distanza limitata il chesignifica, se manteniamo la raffigurazione visiva introdotta con la figura 5.6, tracciare delle circonferenzeattorno a ciascuna parola di codice e rendere tali circonferenze le nostre regioni di decisione. Il raggiodelle circonferenze dev’essere chiaramente imparentato con la distanza minima fra le codewords: essodeve infatti valere al massimo ⌊

dmin − 12

⌋

pena l’insorgere di ambiguità (vedi figura 5.7). Un decoder ML può quindi correggere fino a⌊

dmin − 12

⌋errori oppure rivelarne dmin = 1 (se viene utilizzato solo come rilevatore).

La soluzione appena illustrata (bounded distance decoding) è chiaramente sub-ottima in quanto, se ilvettore ricevuto sta al di fuori di una circonferenza, il decoder non è in grado di decidere (vedi semprefigura 5.7). Chiaramente, un decoder ML non lascerebbe fuori alcun punto ma coprirebbe tutto lo schema;il rovescio della medaglia di questo aspetto sta tuttavia nel fatto che, se si verificano troppi errori, ildecoder deciderà per una parola sbagliata interpretandola come corretta (risultato catastrofico).

Fortunatamente è possibile propendere per una strategia mista, che comporta l’utilizzo di sfere piccole(che non coprano tutto lo schema) all’interno delle quali è possibile la correzione, mentre negli interstizinon coperti fra le sfere è possibile solo la rilevazione (alla quale si reagisce mettendo in funzione un

82


Figura 5.7: Criterio sub-ottimo di decisione

protocollo di ritrasmissione automatica come l’ARQ). In tal caso si ha

Pcd + Pmis + Pe = 1

dove Pcd è la probabilità che la parola ricevuta sia adeguatamente interpretata (sia perché è arrivata senzaerrori sia perché è stata corretta), Pmis la probabilità di ’cadere in un interstizio’ (e quindi di non saperdecidere) e Pe di interpretare male la parola a causa dei troppi errori. Se il raggio della sfera è t e il numerodi errori è > t usciamo da una regione di decisione e possiamo o finire in un interstizio oppure entrare inun’altra sfera; se il canale non è invece troppo cattivo, il decodificatore si ricondurrà alla parola a distanzaminima da quella corretta. La probabilità che vi siano più di t errori è pari a6:

Pe ⩽ Pr {più di t errori nella codeword} =n

∑m=t+1

(nm

)pm(1− p)n−m

Se p è piccola (auspicabile) il termine dominante sarà in realtà il primo della sommatoria e quindi potremoscrivere:

Pe ≈(

nt + 1

)pt+1

Molto probabilmente, se il decoder fallisce scegliendo una parola (corretta) ma diversa da quella che èstata trasmessa, deciderà per la parola a distanza dmin da quella ’vera’: in questo modo sbaglieremo ildmin

n % di bit della nostra codeword. La probabilità di errore per bit sarà quindi:

Peb ≈numero bit sbagliati

bit totali per codeword⋅ (Probabilità di sbagliare) =

=dmin

nPe ∼=

(n

t + 1

)pt+1 dmin

n=

(n

t + 1

)pt+1 2t + 1

n

La probabilità di rivelare l’errore (ma non di correggerlo) è invece:

Pmis ⩽ Pr {più di dmin − 1 errori} =n

∑m=dmin

(nm

)pm(1− p)n−m

Fra tutti i codici, gli unici ad avere la proprietà interessante di contenere tutti i possibili punti all’internodelle sfere (e di non avere quindi elementi negli interstizi) sono i cosiddetti codici perfetti (come adesempio i codici di Hamming, vedi paragrafo 5.10).

6Il leq indica che delle volte finiamo negli interstizi, quindi chiediamo la ritrasmissione e possiamo considerare questo caso comenon portatore d’errore.

83


5.15 Criterio ML per canali additivi gaussiani

Dopo aver esaminato il BSC, tuffiamoci alla ricerca della forma del criterio ML nel caso continuocostituito dalla presenza di un canale additivo gaussiano (vedi figura 5.8). Sia, per ipotesi:

Figura 5.8: Rumore additivo gaussiano e criterio ML: schema di riferimento

cm = (cm1, cm2, . . . cmn) ∈ (c1, c2, . . . cM)

ν = (ν1, ν2, . . . νn)

y = cm + ν⇒ yk = cmk + νk

Dunque, siccome y è il risultato della somma fra un valore costante (cmk) ed una variabile aleatoriagaussiana avente parametri (0, σ2), avremo che:

y = N (cmk, σ2) (5.16)

In questo caso la funzione di verosimiglianza (likelyhood function) assume la forma:

p (y∣cl) =n

∏k=1

p (yk∣clk)︸︷︷︸v.a. gaussiana︸︷︷︸

produttoria⇔ no memoria

=n

∏k=1

1√2πσ2

e−1

2σ2 (yk−clk)2=

(1√

2πσ2

)ne−

n∑

k=1

12σ2 (yk−clk)

2

(5.17)

Osservando chen

∑k=1

(yk − clk)2 = d2

E (y, cl)

(dove dE è la distanza euclidea, così chiamata in quanto continua), che l’esponente della 5.17 è negativo e,infine, che il decodificatore a massima verosimiglianza (ML) cerca di massimizzare la funzione 5.17, si hail seguente criterio:

arg maxcl

p (y∣cl) = arg mincl

dE (y, cl) (5.18)

Il decodificatore ML lavora perciò basandosi sul criterio della minima distanza euclidea. Volendo ulterior-mente sviscerare le nostre formule possiamo elaborare il seguente termine:

d2E (y, cl) =

n

∑k=1

(yk − clk)2 =

n

∑k=1

(y2

k + c2lk − 2ykclk

)= ∥y∥2︸︷︷︸

energia Ey

+ ∥cl∥2︸︷︷︸energia El

−2n

∑k=1

ykclk︸︷︷︸correlazione

Dunque, volendo minimizzare la distanza euclidea, è sufficiente massimizzare il termine di correlazione:

arg maxcl

n

∑k=1

ykclk

84


Figura 5.9: Schema di riferimento per la segnalazione antipodale su canale AWGN

ESEMPIO:

Come indicato in �gura 5.9, vogliamo trasmettere una certa forma d'onda (x(t) in corrispondenza

del bit d'informazione '0' e −x(t) per il bit d'informazione '1'), avente energia E = Ebc, attraverso

un canale AWGN con parametro N0 per la densità spettrale di potenza monolatera (forma d'onda del

rumore: ν(t)).Il generico campione yk della forma d'onda in uscita dal canale sarà quindi la somma di:

yk = cmk︸︷︷︸+√

E oppure −√

E

+ νk︸︷︷︸N(

0, N02

) (5.19)

Se ora dividiamo per√

E otteniamo la stessa somma ma diversamente normalizzata:

yk = cmk︸︷︷︸+1 oppure −1

+ νk︸︷︷︸N(

0, N02Ebc

)Come funziona il decoder a minore distanza euclidea? Supponiamo che il nostro codice contenga le

seguenti due parole

C = {(0, 0, 0) , (1, 1, 1)} trasmissione antipodale−−−−−−−−−−−−−→ Cant = {(1, 1, 1) , (−1,−1,−1)}

e che il ricevitore si ritrovi fra le mani i seguenti tre campionamenti:

y = (1, 2; −0, 4; 0, 2)

Allora la distanza euclidea rispetto alle due codeword sarà:

d2E1 = (1, 2− 1)2 + (−0, 4− 1)2 + (0, 2− 1)2 = 2, 64

d2E2 = (1, 2 + 1)2 + (−0, 4 + 1)2 + (0, 2 + 1)2 = 6, 64

Siccome d2E2 < d2

E1 il decoder propenderà per la parola (+1,+1,+1) = (0, 0, 0)bit.

5.16 Union Bound

Il criterio dello Union Bound afferma che, chiamato Ak il generico k-simo evento all’interno dello spaziodegli eventi, si ha

P

(M∪

k=1

Ak

)⩽

M

∑k=1

P (Ak) (5.20)

In soldoni, la somma delle probabilità dei vari eventi presi singolarmente non potrà mai essere inferioredella probabilità dell’unione di tali eventi. La cosa è molto intuitiva: alcuni eventi possono intersecarsi (si

85


pensi alle intersezioni nei Diagrammi di Venn) e, mentre somma delle probabilità conta due volte questeintersezioni (cioè una volta per ogni evento), l’unione le quantifica una volta soltanto. Applichiamo oraquesto union bound alla trattazione del decoder ML:

arg mincl∈C

dE = arg mincl∈C∥y− cl∥

Quando sbaglia il decoder?

Pr (errore ∣cm )︸︷︷︸errore nell’ipotesi di trasmiss. di cm

= Pr{

dE(cj, y

)< dE (cm, y) per almeno un j ∕= m ∣cm

}Per lo union bound, questa probabilità sarà inferiore alla seguente somma di probabilità (ognuna dellequali è denominata pairwise error probability Pep(cm, cl):

Pr (errore ∣cm )︸︷︷︸da unione di eventi...

⩽M

∑l ∕=m,l=1

Pr{

d2E (cl , y) < d2

E (cm, y) ∣cm

}︸︷︷︸

...a eventi singoli presi a coppie

=M

∑l ∕=m,l=1

Pep (cm, cl)(5.21)

Esaminiamo meglio l’espressione della pairwise error probability:

Pep (cm, cl) = Pr {dE (cl , y) < dE (cm, y) ∣cm } = Pr

{∑k(clk − yk)

2 < ∑k(cmk − yk)

2 ∣cm

}Sfruttando l’equazione 5.19 otteniamo:

Pep (cm, cl) = Pr

⎧⎨⎩∑k

⎛⎜⎝clk − (cmk + νk)︸︷︷︸yk

⎞⎟⎠2

< ∑k

⎛⎜⎝cmk − (cmk + νk)︸︷︷︸yk

⎞⎟⎠2⎫⎬⎭ =

= Pr

{∑k

((clk − cmk)

2 + ν2k − 2νk (clk − cmk)

)< ∑

k(νk)

2

}= Pr

{∑k(clk − cmk)

2 < 2 ∑k

νk (clk − cmk)

}(5.22)

Esaminando bene l’ultimo termine:

Pr

⎧⎨⎩∑k(clk − cmk)

2

︸︷︷︸distanza euclidea d2

E(cl,cm)

< 2 ∑k

νk (clk − cmk)︸︷︷︸combinazione lineare di gaussiane (un’altra gaussiana)

⎫⎬⎭La gaussiana a cui si fa riferimento sarà una variabile aleatoria, che chiameremo Z, avente i seguentiparametri:

Z ∼ N(

0, ∑k

4(clk − cmk)2σ2

)= N

⎛⎜⎜⎜⎜⎜⎜⎜⎝0, 4

⎛⎜⎜⎝ 1

2EbcN0

⎞⎟⎟⎠︸︷︷︸

σ2

∑k(clk − cmk)

2

︸︷︷︸d2

E(cl ,cm)

⎞⎟⎟⎟⎟⎟⎟⎟⎠Ora che sappiamo i parametri della gaussiana, possiamo - tramite la funzione erfc - determinare qual è laprobabilità indicata nella relazione 5.22:

Pr

{∑k(clk − cmk)

2 < 2 ∑k

νk (clk − cmk)

}=

12

erfc

⎛⎜⎜⎜⎜⎜⎜⎜⎜⎝d2

E (cl , cm)√√√√⎷2 ⋅ 2d2E (cl , cm)

N0

Ebc︸︷︷︸la varianza!

⎞⎟⎟⎟⎟⎟⎟⎟⎟⎠=

12

erfc

⎛⎝√d2E (cl , cm) Ebc

4N0

⎞⎠

86


Ora possiamo invece osservare che ciascun bit a differenziare le parole cl e cm dà un contributo pari a 4come indicato dalla seguente relazione:

[(+1)− (−1)]2 = 4

[(−1)− (+1)]2 = 4

}⇒ d2

E (cl , cm) = 4dH (cl , cm)

Sostituendo:

12

erfc

⎛⎝√d2E (cl , cm) Ebc

4N0

⎞⎠ =12

erfc

(√dH (cl , cm)

EbcN0

)

Quest’ultimo contributo, come abbiamo già accennato, rappresenta una formulazione alternativa dellapairwise error probability. Sommando ora i contributi di tutte le parole l ∕= n (nella relazione 5.21 c’erauna sommatoria che poi dopo abbiamo tralasciato per semplicità) otteniamo:

Pe∣cm ⩽2k(=M)

∑l=1,l ∕=m

12

erfc

(√dH (cl , cm)

EbcN0

)

La probabilità d’errore Pe sarà una media su tutte le parole di codice (supponendo queste equiprobabili):

Pe =M

∑m=1

1M︸︷︷︸

p(cm)

Pe∣cm =1M

M

∑m=1

Pe∣cm ⩽1

2M ∑m

∑l ∕=m

erfc

√EbcN0

dH (cl , cm)

Quest’ultima espressione è lo union bound sulla probabilità d’errore per la decodifica soft-decision dei codicia blocco: essa fornisce un limite superiore per la probabilità d’errore. Osserviamo ora che il set di distanze(cioè l’insieme delle distanze fra le varie parole di codice) è sempre lo stesso qualsiasi sia la parola cmdalla quale partiamo, in quanto stiamo in realtà calcolando dei pesi di Hamming e, per le proprietà deicodici a blocco, sommando due parole di codice si ottiene un’altra parola di codice: le distanze sarannoquindi sempre quelle, visto che le parole sono ’intercambiabili’ all’interno di tale set. Possiamo dunquescegliere una parola (ed esempio quella di tutti zeri c1, ma è indifferente) e rimuovere la sommatoria in me moltiplicare tutto per M:

Pe = Pe∣cm = Pe∣c1⩽

12

M

∑l=2

erfc

√√√⎷EbcN0

dH (c1, cl)︸︷︷︸=peso (c1 parola di zeri)

=12

M

∑l=2

erfc

√EbcN0

wl

Possiamo inoltre eliminare alcuni elementi dalla sommatoria, visto che il codice avrà una sua distanzaminima e sarà quindi sufficiente utilizzare, come estremo inferiore, dmin (ricordiamo inoltre che il peso wrappresenta la distanza dalla parola di tutti zeri, ovvero il numero di ’1’ contenuti nella codeword). Se Adè il numero di parole di peso d possiamo scrivere:

Pe ⩽12

M

∑l=2

erfc

√EbcN0

wl =12

M

∑d=dmin

Ad erfc

√EbcN0

d =12

M

∑d=dmin

Ad erfc

√d

EbRc

N0(5.23)

Se il rapporto EbN0

è grande, nella sommatoria i contributi maggiori verranno dalla parole con distanza piùvicina a dmin (se l’erfc aumenta troppo poi il suo contributo tende a calare). Quindi possiamo dare unaversione approssimata dello union bound e anche un termine in grado di maggiorarlo (facciamo finta chetutte le parole tranne quella di tutti zeri abbiano distanza dmin così viene massimizzato l’effetto dell’erfccon dmin al suo interno):

Pe ⩽12

M

∑d=dmin

Ad erfc

√d

EbRc

N0

⎧⎨⎩≈ Admin

2erfc

√dmin

EbRc

N0

⩽M− 1

2erfc

√dmin

EbRc

N0

87


Ad d

1 07 37 41 7

Tabella 5.9: Set di distanze

Volendo, possiamo trovare la probabilità d’errore sul singolo bit ipotizzando di sbagliare per una parolaa distanza dmin da quella corretta e scrivendo quindi:

Peb = Pedmin

n

ESEMPIO:Hamming (7,4) su AWGN, ML Soft-decision decoding

In tabella 5.9 è presente il set di distanze di Hamming. In base ad esso possiamo usare la formula

5.23 per trovare il limite superiore alla probabilità di errore:

Pe ⩽12

M

∑d=dmin

Ad erfc

√d

EbRc

N0=

12⋅ 7 ⋅ erfc

√3 ⋅ Eb

N0

47+

12⋅ 7 ⋅ erfc

√4 ⋅ Eb

N0

47+

12⋅ 1 ⋅ erfc

√7 ⋅ Eb

N0

47

Il decodi�catore soft fa quindi i suoi 1 + 7 + 7 + 1 = 16 confronti e poi decide con un bound alle

prestazioni che è quello appena scritto. Nel caso hard-decision, invece, la probabilità d'errore era la

seguente:

Pe ⩽n

∑m=t+1

(nm

)pm(1− p)n−m =

n

∑m=2

(nm

)pm(1− p)n−m = 1− ∑

m=0,1

(nm

)pm(1− p)n−m

︸︷︷︸proprietà delle distribuzioni statistiche

Provando a gra�care le due probabilità di errore si scopre che, volendo una probabilità d'errore pari a

10−6:

∙ possiamo risparmiare 0,6 dB di SNR rispetto al caso non codi�cato con Hamming (7,4) e

hard-decision;

∙ possiamo risparmiare ulteriori 2 dB (!) di SNR se usiamo la soft-decision.

5.17 Codici accorciati (shortened codes)

Il processo di accorciamento dei codici permette di ottenere un codice (n − l, k − l) a partire da uncodice (n, k). Come si può accorciare un codice? Forzando i primi l bit nella parte d’informazione adessere degli zeri! In virtù della sistematicità del codice, i primi l bit d’uscita (cioè i primi l bit della parolacodificata), saranno sempre pari a zero. Ignorando tali bit ne rimangono n− l ed il gioco è fatto: abbiamoquindi accorciato il codice selezionando il sottoinsieme di parole d’informazione che iniziano con l zeririspetto al codice originale. Utilizzando un sottoinsieme di parole di codice, queste non possono che esserepiù distanti (o - al limite - rimarranno a distanza invariata), dunque si ha:

dmin(accorciato) ≥ dmin(originale)

Uno dei grossi vantaggi sta nel fatto che possiamo mantenere il codificatore originale! Siccome l’imple-mentazione del codificatore è quella che dà più grane a un progettista, questo aspetto va particolarmente

88


considerato. Purtroppo tutto ciò viene ad un prezzo consistente nell’abbassamento della code-rate: infatti7

k− ln− l

<kn

5.18 Codici a blocco lineari ciclici

Si dice scorrimento ciclico della parola

(cn−1, cn−2, . . . , c1, c0)

la seguente parola ricorsivamente shiftata:

(cn−2, . . . , c1, c0, cn−1)

In un codice ciclico, tale parola è ancora una parola di codice, così come tutte le altre n− 2 parole che èpossibile calcolare a partire da queste tramite ulteriori scorrimenti ciclici.

Codici di questo tipo si studiano associando polinomi (di grado massimo n− 1) ai vettori (lunghi n):

c⇒ C (D) = cn−1Dn−1 + cn−2Dn−2 + . . . c1D + c0

La variabile D è una variabile ausiliaria, mentre i coefficienti sono da considerarsi modulo 2, visto chelavoriamo in GF(2). Shiftando di una posizione:

C(1) (D) = cn−2Dn−1 + cn−3Dn−2 + . . . c0D + cn−1

Ebbene, un teorema ci assicura che C(1)(D) è il resto della divisione:

DC (D)

Dn−1

In altre parole, si ha cheC(1) (D) ≡ D ⋅ C (D) mod (Dn − 1) (5.24)

dove tale simbologia sta ad indicare che tali quantità restituiscono lo stesso resto se divise per Dn − 1.Reiterando questo principio otteniamo:

C(i)D ≡ DiC(D)

Esiste una codeword di grado minimo? Indicandola con g(D) è facile mostrare che tale parola ha semprequesta forma8:

g (D) = Dn−k + ...qualcosa... + 1

Inoltre, essa è unica: se infatti ne esistessero due, e le sommassimo, il grado diminuirebbe (siamo inmodulo due quindi il coefficiente col termine D di grado maggiore diventerebbe pari a zero) ma ciòfarebbe per assurdo cadere l’ipotesi che quelle fossero le codeword di grado minimo. La nostra parola digrado minimo, per come l’abbiamo strutturata, avrà quindi tanti zeri in testa:

(000 . . . 01. . . qualcosa . . . 1)

Come sono fatti gli scorrimenti ciclici di questa parola di grado minimo? Iniziando con uno shift di unaposizione, dovremmo trovare il resto di

Dg (D)

Dn − 17Dimostrazione:

k− ln− l

<kn⇒ n (n− l)− k (n− l)

n (n− l)< 1

n− kn

< 1

− kn< 0

8La presenza dell’uno, lì in fondo, è necessaria: se non ci fosse potrei infatti shiftare il tutto per ottenere una parola di gradoinferiore.

89


ma il resto di tale frazione è direttamente Dg(D) in quanto tale termine ha grado inferiore ad n. Il vettoreassociato a questo primo scorrimento sarà:

(000 . . . 01. . . qualcosa . . . 10)

Reiterando questo stesso procedimento, anche D2g(D) sarà una parola di codice, dunque possiamo pro-seguire finché il primo ’1’ in testa non arriva nell’ultima posizione a sinistra, eventualità che si verifica alk− 1-esimo shift:

Dk−1g (D)

Dn − 1

In tal caso il nostro vettore associato avrà forma:

(1. . . qualcosa . . . 1000 . . . 0)

Con questi shift abbiamo ottenuto k parole di codice linearmente indipendenti (le quali possono quindicostituire una base k-dimensionale):

g (D) , Dg (D) , D2g (D) , . . . , Dk−1g (D)

Se Q(D) è un polinomio qualunque di grado ≤ k− 1, allora moltiplicando quest’ultimo per g(D) ottenia-mo una parola di codice:

Q (D)︸︷︷︸⩽k−1

g (D)︸︷︷︸n−k

= C (D)︸︷︷︸⩽n−1

∈ codice C

Questo semplice prodotto ci permette quindi di scrivere tutte le parole del codice: per questo motivo lapreziosissima g(D) viene denominata polinomio generatore del codice ciclico. Essa individua esattamenteil nostro codice e ne individua le proprietà.

Le condizioni perché un certo polinomio possa fregarsi dello status di generatore sono due:

∙ se C è l’insieme dei polinomi g(D) e Q(D), ovvero il nostro codice (n, k) ciclico, il polinomio gene-ratore è divisore di Dn − 1.Dimostrazione: abbiamo la seguente corrispondenza

g (D) = Dn−k + . . . qualcosa . . . + 1⇔ (0, . . . , 0, 1, . . . qualcosa . . . , 1)

Allora:Dg (D)⇔ (0, . . . , 0, 1, . . . qualcosa . . . , 1, 0)

Come abbiamo visto, questo giochetto funziona fino a Dk−1g(D), polinomio di grado esattamenten− 1 corrispondente ad un vettore con un ’1’ in testa. Se ora ostinatamente reiteriamo il processo emoltiplichiamo per Dk otteniamo:

Dkg(D) = g(k)(D) + (Dn − 1)

Ma g(k)(D) è ancora una parola di codice, la quale può essere scritta come

Q(D)g(D)

dunque:

Dkg(D) = Q(D)g(D)︸︷︷︸g(k)(D)

+(Dn − 1)⇒ g (D)(

Dk + Q(D))= Dn − 1

Abbiamo quindi fatto vedere che, fra i fattori di Dn − 1, vi è g(D), il che equivale a dire che talepolinomio è divisore di Dn − 1;

∙ se g(D) è divisore di Dn − 1, il codice definito da C(D) = g(D)Q(D) è ciclico.Dimostrazione: proviamo a calcolare lo shift ciclico di C(D) = g(D)Q(D). Otteniamo

C(1) (D) = DC (D) + cn−1 (Dn − 1)

90


Ma ora, visto che per ipotesi g(D) è un divisore di Dn − 1, possiamo effettuare le seguenti sostitu-zioni (p(D) è un polinomio generico):

C(1) (D) = D Q (D) g (D)︸︷︷︸C(D)

+Cn−1 g (D) P (D)︸︷︷︸Dn−1

= g (D) (DQ (D) + Cn−1P (D))︸︷︷︸polinomio Q(D)

Dunque C(1) è una parola di codice; ciò dimostra che quest’ultimo è effettivamente ciclico.

ESEMPIO:Quali sono i codici ciclici con n = 2?Il polinomio generatore g(D) dev'essere divisore di D2 + 1 che, in GF(2), può essere scritto come

(D + 1)(D + 1). Non abbiamo quindi altre possibilità all'infuori di:

g(d) = D + 1

Ricordiamo poi che si ha

C(D) = Q(D)g(D)

e che il grado di Q(D) è al massimo k− 1: in questo caso k− 1 = 1− 1 = 0 dunque Q(D) assume

i valori 0 e 1. Possiamo ora ricavare le parole di codice:

C (D) =

{0 ⋅ g (D) =′ 00′

1 ⋅ g (D) =′ 11′

Ecco quindi ricavato l'unico possibile codice ciclico di lunghezza 2.

ESEMPIO:Quali sono i codici ciclici con n = 3?Qui la cosa si fa più interessante, perché abbiamo due potenziali polinomi generatori:

D3 + 1 = (D + 1)(

D2 + D + 1)

∙ se scegliamo come polinomio generatore il polinomio di grado 1

g(D) = D + 1

otteniamo un codice con parametri (n− k) = (3, 3− 1) = (3, 2). Dalla relazione

C(D) = Q(D)g(D)

intuiamo che le parole di codice sono tutte quelle che si annullano in D = 1 (valore per il

quale g(D) è sicuramente zero), ovvero tutte le parole con un numero pari di '1' (sommando

un numero pari '1', in GF(2), otteniamo uno zero). Dunque questo codice ciclico è un codice di

parità in versione ciclica;

∙ se scegliamo come polinomio generatore il polinomio di grado 1

g(D) = D2 + D + 1

otteniamo un codice con parametri (n− k) = (3, 3− 2) = (3, 1). Ci troviamo in questo caso

in una situazione molto simile a quella dell'esempio precedente: si ha

C(D) = Q(D)g(D)

Tuttavia il grado di Q(D) è al massimo k− 1, ma k− 1 = 1− 1 = 0 dunque Q(D) assume i

valori 0 e 1.

C (D) =

{0 ⋅ g (D) =′ 000′

1 ⋅ g (D) =′ 111′

Anche questa volta spunta fuori un codice a ripetizione.

ESEMPIO:Quali sono i codici ciclici con n = 7?

Osservando le seguenti possibili scomposizioni

D7 + 1 = (D + 1)(

D5 + D4 + D3 + D2 + D + 1)= (D + 1)

(D3 + D2 + 1

) (D3 + D + 1

)si scopre le opzioni possibili sono molteplici (tabella 5.10).

91


(n, k) g(D)

(7, 7) 1 No parity code: vengon fuori tutte le n-ple(7, 6) D + 1 Parole di codice = parole di peso pari (overall parity check code)(7, 4) D3 + D2 + 1 Hamming (7,4)(7, 4) D3 + D + 1 Hamming (7,4)(7, 3) (D + 1)(D3 + D2 + 1) Hamming (7,4) + parità imposta da (D + 1)(7, 3) (D + 1)(D3 + D + 1) Hamming (7,4) + parità imposta da (D + 1)(7, 1) (D6 + D5 + . . . + 1) Codice a ripetizione (7,1)(7, 0) D7 + 1 Il codice più inutile del mondo

Tabella 5.10: Possibili codici ciclici con n = 7

5.19 Codificatore per codici ciclici (sistematici e non)

Il codificatore in questione (caso non sistematico) è un componente molto semplice che prende in pa-sto un polinomio x(D) (di grado al massimo k− 1) e lo moltiplica per g(D). Il risultato è un polinomioC(D), di grado n− 1, che rappresenta la parola di codice lunga n bit.

E se volessimo raggiungere lo stesso risultato aggiungendo la sistematicità del codice? Questo com-porterebbe moltiplicare per Dn−k il polinomio x(D) della parola di informazione, in modo da elevarne ilgrado a n− 1 e portarlo ’in cima’ al polinomio codificato. Dobbiamo quindi imporre che si abbia:

x (D) ⋅ Dn−k = Q (D) g (D) + R (D)︸︷︷︸resto

= C(D)

Si ha anche:x (D) ⋅ Dn−k + R (D) = Q (D) g (D) = C(D)

Dunque il resto R(D) è la parte di parità della parola/polinomio di codice e va a ’riempire’ i gradi0 → (k − 1) del polinomio C(D) (i gradi n → k sono invece ’occupati’ dalla parola d’informazioneprecedentemente shiftata). Dunque, riassumendo, ecco come si ottiene una parola di codice nel caso dicodice ciclico sistematico:

1. calcoliamo Dn−kx(D) il che significa, in soldoni, appendere alla parola di informazione n− k zeri incoda;

2. calcoliamo la divisione e prendiamo il resto:

Dn−kx(D) mod g(D) = R(D)

3. calcoliamo la parola di codice:C(D) = Dn−kx(D) + R(D)

Per la moltiplicazione fra polinomi esiste il circuito in figura 5.10, mentre per la divisione quello infigura 5.11 (i cui blocchi di ritardo - cioè di memorizzazione, dopo n colpi di clock, contengono R(D)).

Il circuito di figura 5.11 può essere specializzato al caso di codici sistematici (vedi figura 5.12): sinoti che lo switch A è chiuso durante l’elaborazione dei primi k bit (che sono necessari caricare nel ramodi retroazione la parte sistematica da elaborare) mentre lo switch B discrimina fra la scelta della partesistematica e quella del quoziente della divisione (ovvero dei n− k bit successivi ai primi k, corrispondentiala parte sistematica che B pescava dal filo inferiore).

5.20 Calcolo della sindrome

Siar(D) = C(D) + e(D)

92


Figura 5.10: Apparato per la moltiplicazione

Figura 5.11: Apparato per la divisione

Figura 5.12: Codificatore per codice sistematico ciclico

ciò che arriva al decodificatore per codici a blocco ciclici: C(D) è ovviamente la parola di codice, mentree(D) è l’eventuale pattern d’errore causato dal canale. Anche e(D) è un polinomio:

en−1Dn−1 + . . . + e1D + e0

Per capire se un polinomio fa parte del codice basta dividere ciò che si è ricevuto, cioè r(D), per ilpolinomio generatore g(D):{

no errore⇒ r (D) mod g (D) = 0

sì errore⇒ r (D) mod g (D) = 0 + e (D) mod g (D) = s (D)

Il polinomio s(D), di grado sicuramente minore di n− k − 1 (che è il grado di g(D)), è detto di sindro-me. Per la correzione dell’errore è necessario sommare a r(D) = C(D) + e(D) il pattern d’errore e(D)

93


S(D) e(D)

0 0 00000001 1 0000001D D 0000010D2 D2 0000100

D + 1 D3 0001000D2 + D D4 0010000

D2 + D + 1 D5 0100000D2 + 1 D6 1000000

Tabella 5.11: Associazione sindrome-pattern

appropriato, scelto cioè in corrispondenza della sindrome rilevata dal decoder:

r(D) + e(D) = C(D) + e(D) + e(D) = C(D)

Lavorando con i polinomi, l’hardware di codifica-decodifica risulta essere molto più semplice!

ESEMPIO:Abbiamo il codice ciclico descritto dal polinomio generatore

g(D) = D3 + D + 1

Ricordando che

r (D) mod g (D) = 0 + e (D) mod g (D) = s (D)

si può ricavare la tabella 5.11.

Si noti che risulta di fondamentale importanza che la sindrome s(D) sia diversa per ciascun caso dicorrezione. Con codici più lunghi di quello mostrato in tale esempio, le cose sono molto più complicate

5.21 Applicazioni notevoli dei codici ciclici

5.21.1 CRC: Cyclic Redundancy Check Codes

Il controllo tramite codici CRC è molto diffuso perché la sua implementazione binaria è semplice darealizzare, richiede conoscenze matematiche modeste per la stima degli errori e si presta bene a rilevareerrori di trasmissione su linee affette da elevato rumore di fondo. Le tecniche CRC furono inventate daW. Wesley Peterson che pubblicò il suo primo lavoro sull’argomento nel 1961. Utile per l’individuazionedegli errori casuali, il CRC non è invece affidabile per verificare la completa correttezza dei dati controtentativi intenzionali di manomissione. Tale famiglia di codici trova impiego, per esempio, nel protocolloHDLC9: in particolare per quest’ultimo si utilizza un codice ciclico con polinomio

g(D) = D16 + D12 + D5 + 1

il quale è divisore di

D215−1 + 1

Siccome abbiamo un numero pari di coefficienti, tutte le parole si annullano in D = 1 (e vengono quindiselezionate le sole codewords di peso pari). La distanza minima di questo codice, avente parametri (215 −1, 215 − 1− 16), è pari a 4, dunque:

∙ 1,2 o 3 errori li rileviamo sempre;

∙ ne sappiamo rilevare anche 5,7,9. . . visto che, per quanto detto poco fa, questo codice possiede ancheil meccanismo ereditato dai codici di parità.

9Incapsulato nell’IP.

94


5.21.2 Codici Hamming ciclici

I codici di Hamming ciclici hanno parametri (n, k) = (2m−1, 2m−1 −m), con m qualunque. Sono codicia distanza minima 3 e hanno la caratteristica di essere perfetti.

5.21.3 Codice di Golay

Ha parametri (23,12) ed è un codice perfetto con distanza minima 7. Nella sua versione ciclica ha ilseguente polinomio generatore:

g(D) = D11 + D9 + D7 + D6 + D5 + D + 1

5.21.4 Codici BCH

I codici BCH (acronimo di Bose-Ray-Chaudhuri, gli scopritori) possono essere costruiti in GF(q), con qqualunque. Per il caso binario si hanno parametri (n, k) = (2m−1, k) e le seguenti relazioni:⎧⎨⎩

n− k ⩽ mt

dmin = 2t + 1

m ⩾ 3

5.22 Codici di Reed-Solomon

Sono imparentati con i BCH, ma possono essere utilizzati anche in un campo non binario: ciascunsimbolo è infatti formato da m bit (con m > 1), cosicché possiamo dire di lavorare in un Campo di Galois(2m). Fissato m si ha automaticamente la lunghezza del codice:

n = 2m − 1 (5.25)

La distanza minima dei codici di Reed-Solomon, definita come il numero di simboli differenti fra i duevettori (si tenga però presente che due simboli sono diversi anche se differiscono di un solo bit), è invecepari al valore (sempre dispari)

n− k + 1 (5.26)

Come si nota, i codici di Reed-Solomon raggiungono il Singleton Bound; inoltre, con tale codifica possiamocorreggere

t =n− k

2

errori; come si noterà nel seguente esempio, spesso t è un parametro fissato in fase di scelta del codice edè utilizzato per ricavare k.

ESEMPIO:Scegliamo di utilizzare 4 bit per simbolo. Abbiamo quindi m = 4 e n = 2m − 1 = 15, lavoriamo

in GF(4) e - volendo correggere �no a t = 4 simboli - dobbiamo avere un parametro k pari a

k = n− 2t = 7. La rate di questo codice è di circa 1/2.

ESEMPIO:Scegliamo questa volta di utilizzare 8 bit per simbolo. La lunghezza naturale del codice sarà n =2m − 1 = 28− 1 = 255. Volendo correggere t = 2 errori, k dev'essere pari a n− 2t = 251; un codice

si�atto ha 4 bit di parità, ne corregge �no a 2 e ha una coderate molto vicina a 1.

I codici Reed-Solomon possono essere accorciati e anche estesi. Inoltre hanno l’importante caratteristicadi difendere bene l’informazione che attraversi un generico canale in grado di introdurre errori burst (=molti bit sbagliati consecutivi): infatti, errori consecutivi su un simbolo hanno grande probabilità direndere errato un solo simbolo, visto che è formato da più bit. Di seguito tratteremo altri casi di questogenere.

95


5.23 Codici per la rilevazione di errori burst

Per lo studio di tali codici è necessario rimuovere l’ipotesi di indipendenza statistica degli errori, vistoche essi hanno la tendenza a presentarsi ’in blocco’. Chiameremo inoltre burst di lunghezza b una sequenzadi errori confinati in b posizioni consecutive.

TeoremaOgni codice ciclico può rilevare tutti i burst di lunghezza b ≤ n − k. Questo significa che il polinomioerrore e(D) avrà in generale la seguente forma

e(D) = Di(Db−1 + . . . zeri ed uni . . . + 1)

dove il Di sta ad indicare la posizione assoluta della sequenza di bit errati. Supponiamo di voler solorilevare (e non correggere) e ricordiamo che si ha:

r (D) = c (D) + e (D)

r (D) mod g (D) = e (d) mod g (D)

Se abbiamo un polinomio e(D) di grado inferiore a n − k il resto della divisione dev’essere per forzadiverso da zero, dato che g(D) ha grado n− k; dunque e(D), in questo caso, fungerebbe (tutt’intero) daresto. Infatti:

∙ Di è divisibile per g(D)? No, perché il polinomio g(D) non ha radice in D = 0 dato che finiscesempre per 1;

∙ allo stesso modo, nemmeno il polinomio

Db−1 + . . . zeri ed uni . . . + 1

terminando anch’esso per 1, potrà essere divisibile per g(D).

Essendo il resto sempre diverso da zero, la rivelazione di errori burst può essere effettuata.Fra i più importanti codici ciclici per la correzione dei burst di errore citiamo i codici di Fire (usati nel

GSM).

5.24 Codici MLSR (Maximum Length Shift-Register Codes)

Trattasi dei codici (ciclici) duali a quelli di Hamming. Fissato m, i parametri di un codice MLSR sono(2m − 1, m); inoltre, tali codici hanno la proprietà di avere k = m e un numero di parole di codice pari a2m − 1: tutte queste parole sono uno shift ciclico di una stessa codeword. Infine, tutte le parole hanno unuguale peso, pari precisamente a 2m−1.

La codifica avviene con uno shift-register a m celle opportunamente configurato; tale processo è costi-tuito da due fasi: la prima consiste nel caricamento dello shift-register mentre la seconda nella generazionedella codeword. Le connessioni vengono scelte in modo che lo shift-register attraversi tutti i possibili 2m − 1stati diversi da zero prima di tornare a quello iniziale.

ESEMPIO:

In �gura 5.13 vediamo lo schema di codi�ca per un codice MLSR duale al codice di Hamming (7,3).

Risulta interessante notare che le sequenze in uscita hanno la caratteristica di essere pseudo-casuali,visto che sono grossomodo bilanciate fra bit a 0 e bit a 1. Inoltre, si hanno mediamente

∙ metà delle corse (sequenze di bit consecutivi a 0 o a 1) di lunghezza 1;

∙ 1/4 delle corse di lunghezza 2;

∙ 1/8 delle corse di lunghezza 4;

∙ etc. . .

96


Figura 5.13: Esempio di schema per codificatore MLSR

Se scriviamo la funzione di autocorrelazione temporale:

Rx (k) =1n

n−1

∑i=0

xixi+k

Questa vale 1 quando k = 0 + ln (l intero, zero compreso) e −1/n altrove10. Questa caratteristica faavvicinare le sequenze pseudo-casuali a quelle veramente casuali, per le quali vale:

RX(k) = E [xixi+k] =

{1 per k pari a 0

0 per k diverso da 0

Le due funzioni di autocorrelazione si somigliano, a meno del valore − 1n (che per n→ ∞ tende comunque

a zero) e per la periodicità.Queste sequenze vengono utilizzate per gli scopi più vari (ad esempio per ottenere sequenze ran-

dom, per lo scrambling11, per la crittografia o per evitare che lunghe sequenze di 0 e di 1 ostacolino lasincronizzazione fra sistemi di telecomunicazione).

10Proposta di dimostrazione: ricordando che xi può assumere il valore 1 o il valore -1 (segnalazione antipodale):

Rx (k) =1n

n−1

∑i=0

xixi+k =

⎧⎨⎩k = 0 + ln⇒ 1

n

n−1

∑i=0

x2i =

nx2i

n= x2

i = sempre 1

altrove⇒ 1n

n−1

∑i=0

xixi+k =1n(−1) = − 1

n

Si noti che nel penultimo passaggio abbiamo usato l’ipotesi che n sia dispari (non può essere altrimenti, visto che è pari a 2m − 1);essendo la sequenza grosso modo bilanciata, avremo un numero di bit a zero (valore +1) pari al numero di bit a uno (valore −1)meno uno (o più uno, dipende!). La sommatoria, dunque, coinvolgerà un numero dispari di termini: n

2 di questi varranno −1(moltiplicazione fra simboli di segno diverso), n

2 − 1 varranno +1 (prodotto di simboli d’uguale segno); il risultato della sommatoria,da dividere ancora per n, sarà dunque −1.

11A scrambler is a device that transposes or inverts signals or otherwise encodes a message at the transmitter to make the messageunintelligible at a receiver not equipped with an appropriately set descrambling device. Scrambling is accomplished by the additionof components to the original signal or the changing of some important component of the original signal in order to make extractionof the original signal difficult. A scrambler (also referred to as a randomizer) is a device that manipulates a data stream beforetransmitting. The manipulations are reversed by a descrambler at the receiving side. Scrambling is widely used in satellite, radiorelay communications and PSTN modems. A scrambler can be placed just before a FEC coder, or it can be placed after the FEC, justbefore the modulation or line code. A scrambler in this context, has nothing to do with encrypting, as the intent is not to render themessage unintelligeable, but to give the transmitted data useful engineering properties. A scrambler replaces sequences into othersequences without removing undesirable sequences, and as a result it changes the probability of occurrence of vexatious sequences.Clearly it is not foolproof as there are input sequences that yield all-zeros, all-ones, or other undesirable periodic output sequences.A scrambler is therefore not a good substitute for a line code, which, through a coding step, removes unwanted sequences.

97


98

Capitolo 6

Codici a traliccio

6.1 Codici convoluzionali

I codici convoluzionali guadagnano molto in termini energetici (permettono l’uso di un rapporto SNRmolto basso) e, asintoticamente, riescono a raggiungere una Peb molto bassa. Sono codici lineari creatimediante un codificatore a K stadi (pari alla lunghezza di vincolo del codice) ciascuno composto da k celledi memoria; all’interno del codificatore entrano k bit alla volta e gli n bit di uscita sono calcolati come unaqualche somma modulo 2 di quel che si trova all’interno degli shift-register (vedi figura 6.1).

Figura 6.1: Schema generico per codificatore di codici convoluzionali

Si noti che i bit di uscita dipendono non solo k bit d’ingresso dell’istante presente, ma anche dai bitprecedenti: il codificatore, dunque, ha memoria! In generale il codificatore ha memoria (K − 1)k bit: ciòsignifica che tiene conto di tutti bit precedenti nello shift-register oltre ai k bit d’ingresso.

ESEMPIO:Il codi�catore in �gura 6.2:

∙ ha un solo shift-register all'interno del quale entra un bit alla volta;

∙ ha rate di codi�ca 1/2 (per ogni bit che entra ne escono due);

∙ ha 2(K−1)k = 22 = 4 possibili stati (σl = {00, 01, 10, 11}, dove il primo bit è xl−1 e il secondo

xl−2);

∙ i bit d'uscita sono ottenuti tramite la combinazione lineare dei bit (xl , xl−2) ≡ g2 = (5)8(notazione in ottale per riferirsi a 101, cioè al primo e al terzo bit) e (xl , xl−1, xl−2) ≡ g2 = (7)8;

∙ è possibile de�nire un diagramma degli stati in cui si indicano i bit d'ingresso con delle frecce

e i bit d'uscita (sopra tali frecce, vedi �gura 6.3).

99

100 CAPITOLO 6. CODICI A TRALICCIO

Figura 6.2: Esempio di codificatore per codice convoluzionale

Figura 6.3: Diagramma degli stati

6.2 Diagramma a traliccio

Con il diagramma a traliccio si rappresentano le possibili evoluzioni nel tempo dello stato: con rife-rimento all’esempio del paragrafo precedente, un possibile schema a traliccio è quello riportato in figura6.4. La simbologia è simile a quella del diagramma degli stati, con la fattezza della freccia (in questo casoil colore) ad indicare quale bit d’ingresso produce la transizione di stato e la coppia di bit sopra le freccead indicare i bit d’uscita. Seguendo il traliccio è possibile ottenere la parola codificata (vedi figura 6.5):si noti che le tre rappresentazioni ivi indicate (bit d’informazione, bit d’uscita ed evoluzione dello stato)sono equivalenti.

Fissato il numero di transizioni nel traliccio (trellis) lo stato iniziale e lo stato finale (solitamenteentrambi S0) le possibili sequenze d’uscita sono le parole di codice.

ESEMPIO:Ad esempio, cinque transizioni sono necessarie per codi�care una parola di 3 bit (3 transizioni su 5)

e per riportare sicuramente lo stato a S0 (altre 2 transizioni su 5): solo 3 bit su 5 sono quindi liberi,

dunque abbiamo 23 possibili codewords.

Più in generale, se si vuole fare in modo che il trellis finisca nello stato ’zero’ (S0 nei precedenti esempi),si devono aggiungere in coda ai bit d’informazione (K − 1)k bit a zero (tail biting). Questi bit aggiuntiviinfluiscono sulla coderate che, per m transizioni (codewords di nm bit), diventa pari a:

Rc =k(m−K+ 1)

nm(6.1)

100

CAPITOLO 6. CODICI A TRALICCIO 101

Figura 6.4: Traliccio

Figura 6.5: Il traliccio percorso

6.3 Decodifica dei codici convoluzionali con hard decisions su BSC

Scegliamo di utilizzare il criterio ML (maximum likelyhood): applicare tale criterio in un traliccio, al finedi ricavare quale sia la parola di codice a minima distanza di Hamming da r (sequenza ricevuta), significadeterminare la sequenza che totalizza lo shortest route, ovvero quella che percorre il traliccio totalizzandola minore distanza di Hamming.

ESEMPIO:Consideriamo il traliccio in �gura 6.4. Partendo dallo stato iniziale S0, se riceviamo la sequenza 00,

possiamo dire percorrendo la freccia rossa (che rimane in S0) di aver accumulato una distanza di

Hamming pari a 0 (la sequenza ricevuta coincide con quella sopra la freccia); viceversa, percorrendo

101


la freccia blu (che porta in S1), accumuliamo distanza di Hamming pari a 2, visto che la sequenza

ricevuta 00 di�erisce per due bit rispetto a quella indicata sopra la freccia. Dopo cinque transizioni,

quando la parola codi�cata si sarà 'esaurita', saremo in grado di determinare tutti i possibili percorsi,

ognuno dei quali avrà un proprio peso: scegliere quello minore signi�cherà anche propendere per la

sequenza che più probabilmente, in base al criterio ML, è stata trasmessa.

Le possibili strategie per la rivelazione della shortest route sono il calcolo della distanza di Hammingper tutte le possibili 23 codewords oppure l’utilizzazione dell’algoritmo di Viterbi (vedi paragrafo 6.4).

6.4 Algoritmo di Viterbi

L’algoritmo di Viterbi determina la sequenza di lunghezza minima in un trellis tramite un procedimen-to ricorsivo-sequenziale. Il suo funzionamento si basa su un’osservazione fondamentale: se il percorso dipeso minimo passa per lo stato intermedio σl allora sarà composto dalla concatenazione

{σ0 → σl}peso minimo + {σl → σfinale}peso minimo

I passi dell’algoritmo sono i seguenti:

∙ si mantiene, per ciascun possibile stato intermedio l, solo il percorso di lunghezza minima σ0 → σl(percorso sopravvissuto, survivor per gli anglofoni). Ogni volta che siamo quindi indecisi fra duepercorsi andiamo a prendere solo quello più probabile;

∙ si determinano i survivors per σl+1 estendendo quelli per gli stati σl .

Più formalmente, indicando con l il passo dell’algoritmo al quale ci troviamo, vengono definite tre fasi:

∙ memorizzazione: va effettuata per ogni stato e consiste nella definizione dei survivors e della lunghezzadel relativo percorso;

∙ inizializzazione: va effettuata solo per l = 0. Si parte dallo stato S0 e si definisce per l’unico possibilesurvivor di lunghezza 0. Tutti gli altri percorsi si trovano invece a distanza +∞;

∙ ricorsione: si calcola, per ogni transizione, l’estensione dei cammini al passo l ed il relativo peso, chesarà pari al peso al passo precedente (l − 1) sommato al peso della transizione. Per ogni stato finalesi determina il survivor come quello a peso minimo. Dopodiché si ripete questo procedimento finoal termine.

L’algoritmo di Viterbi si può usare per decodificare codici convoluzionali sia nel caso di hard-decisionche di soft-decision: nel primo caso la metrica di ogni ramo va descritta in termini di distanza di Hamming,mentre nel secondo bisogna fare riferimento alla distanza euclidea fra i campioni del ricevitore e quelliassociati al ramo.

ESEMPIO:Mettiamoci nel caso di trasmissione antipodale su AWGN, nell'ipotesi di aver disposto tutto come nel

paragrafo 4.4. Facendo nuovamente riferimento alla �gura 6.4, supponendo di trovarci al primo passo

dell'algoritmo e di aver ricevuto i valori soft (−0, 3; 1, 1), la distanza (metrica) da scrivere sul ramo

'orizzontale' (che porta nuovamente in S0) sarà1:

(1− (−0, 3))2 + (1− 1, 1)2 = 1, 7

6.4.1 Complessità

Sia Nσ il numero di stati del trellis e NT il numero di transizioni dagli stati σl a σl+1. Il quantitativo dimemoria richiesto sarà pari a

1 survivor / stato + 1 lunghezza di percorso (survivor) / stato

1Ricordiamo che a 00 corrispondono i valori (+1,+1).

102

CAPITOLO 6. CODICI A TRALICCIO 103

La complessità computazionale sarà invece paragonabile a NT dato che dobbiamo effettuare:

NT somme Nσ comparazioni (6.2)

Dunque la complessità dell’algoritmo di Viterbi è sostanzialmente legata al numero di stati, ovvero a

Nσ = 2k(K−1)

6.4.2 Altri aspetti implementativi

Si può migliorare o perfezionare l’algoritmo di Viterbi troncando il trellis dopo (5 ∼ 6)K e decidendoin base al percorso minimo calcolato fino a quel punto (Truncated Viterbi Algorithm). Inoltre si può ricorrerealla normalizzazione delle metriche e alla quantizzazione.

Si definisce distanza libera (d f ree) del codice convoluzionale la distanza minima tra tutte le possibilidiverse sequenze di codice. Questo parametro è l’analogo della distanza minima dmin fra le parole dicodice già vista nel caso di codici a blocco lineari. In particolare, il guadagno di codifica asintotico è:

GC (dB) ⩽ 10log10

(d f reeRc

)6.5 Codici convoluzionali punturati

Servono per aumentare la coderate di codificatori/decodificatori già progettati. In figura 6.6 si puòvedere un esempio di traliccio di codice convoluzionale punturato.

Figura 6.6: Diagramma a traliccio di codice convoluzionale punturato

6.6 Codici convoluzionali sistematici

Hanno in genere una distanza d f ree peggiore dei non sistematici (vedi tabella 6.1, la quale si riferisce alcodificatore sistematico indicato in figura 6.7).

6.7 Codici convoluzionali catastrofici (paura eh!?)

Sono quelli tali per cui un numero finito di errori sul canale può provocare un numero infinito di bitdi informazione errati: questo avviene in quanto gli errori possono far prendere una strada sbagliata neltraliccio, impossibile da lasciare per determinate combinazioni di bit ricevuti (con conseguente accumu-larsi di errori). Si dimostra che il codice è catastrofico se g1(D) e g2(D), cioè le espressioni che indicanocome vengono combinati i bit in uscita, hanno fattori in comune.

103


Figura 6.7: Codificatore di codice convoluzionale sistematico

K d f ree codice sistematico d f ree codice NON sistematico

3 4 54 4 65 5 76 6 87 6 108 7 10

Tabella 6.1: Codice convoluzionale sistematico vs. non sistematico

104

Capitolo 7

Altri aspetti riguardanti i codici dicanale

7.1 Interleaving

Le ditate sui CD sono il male.

Il saggio

Consideriamo un’applicazione particolare, cioè quella della memorizzazione dei dati su CD. Quandoponiamo il nostro ditone sulla superficie del CD non stiamo compiendo un’azione indolore, bensì creandouna valanga di errori a burst. Magari il nostro codice è in grado di correggere un certo numero di erroriper codeword e tuttavia, fatta la ditata, ci troviamo con un sacco di parole senza errori assieme ad altrecompletamente sbagliate.

Facciamo ora un altro esempio: una stazione mobile (come un cellulare), non riceve un unico camminodalla stazione radio-base, bensì un insieme di cammini multipli dovuti a reiterate diffrazioni, riflessioni,etc. . . Questi cammini avranno potenze e fasi molto differenti e possono sommarsi sia costruttivamenteche distruttivamente; in quest’utlimo caso, la probabilità di occorrenza di errori a burst è molto elevata.

In entrambi i casi il canale (che sia il supporto di memorizzazione del CD o il canale radiomobile) èdotato di memoria: molti codici che solitamente funzionano bene potrebbero in tali casi fare male il lorolavoro e impedire una corretta comunicazione.

Come possiamo fare per tutelarci da questi spiacevoli inconvenienti? La cosa migliore è sparpagliarei bit secondo un certo criterio (interleaving), per poi ricomporli lato ricevitore in modo da diluire i bitsbagliati in mezzo a quelli giusti. Fra i vari modi in cui possiamo effettuare l’interleaving esamineremoquello nel seguente paragrafo (interleaving a blocco).

7.1.1 Interleaving a blocco

Immaginiamo di disporre di una certa matrice D×n: al trasmettitore, in base alla tecnica dell’interleavinga blocco, tale matrice (matrice di interleaving) viene riempita per righe di parole codificate e, in seguito, tra-smessa per colonne. Dopodiché, lato ricevitore, la scrittura su un’analoga matrice (matrice di de-interleaving)avviene per colonne e la lettura (a cui seguirà la decodifica) per righe. Con questo astuto escamotage ibit sono stati accuratamente sparpagliati: quelli che prima erano due bit adiacenti ora disteranno D po-sizioni; il grande vantaggio sta nel fatto che se il canale introduce un errore a burst di lunghezza b ≤ D,allora ciascuna parola di codice sarà inficiata al massimo da un solo errore o, più in generale, un burst dilunghezza lD provocherà al più l errori per codeword.

Non tutto questo ben di Dio ci piove però gratis dal cielo: l’interleaving introduce infatti il ritardoconsistente nel riempire la nostra matrice. Tale ritardo sarà pari a 2Dn

Br(metà imputato alla codifica e

metà alla decodifica), dove Br è la bit-rate con la quale il codificatore e il decodificatore processano i lorodati. Nel seguente esempio mostreremo come il ritardo necessario a un corretto funzionamento di questatecnica possa essere drammaticamente alto nel caso in cui il canale sia parecchio rumoroso.

105

106 CAPITOLO 7. ALTRI ASPETTI RIGUARDANTI I CODICI DI CANALE

ESEMPIO:Abbiamo un codice BCH di parametri (127,36) e una Brc di 19.200 bit/s. Supponiamo che la durata

dell'errore burst introdotto dal canale sia sempre inferiore o al limite uguale a 250 ms. Come proget-

tiamo l'interleaver? Quanto ritardo introduce?

A 19.200 bit/s, 250 ms di errore equivalgono a 4.800 bit sbagliati. Consultando le tabelle scopriamo

che la distanza minima del nostro BCH è pari a

dmin = 2t + 1 = 31

dunque il numero di errori correggibili t è

t =⌊

dmin − 12

⌋= 15

Potendo noi tollerare al massimo 15 errori per codeword, il parametro D della matrice di interleaving

dovrà essere almeno pari a:

D ≥ 480015

= 320

Il ritardo introdotto sarà quindi pari a:

2DnBrc

=8128019200

= 4, 2 secondi

Non so se mi spiego: 4,2 secondi. . . è un'eternità!

7.2 Codici concatenati

Sembra una gran roba, ma il termine codici concatenati sta semplicemente a significare che i codici pos-sono essere composti (applicati ’uno dietro l’altro’) per ottenere un risultato (si spera) più performanteper quanto riguarda la rilevazione/correzione degli errori. Supponendo che utilizzare due codici, chiame-remo outer (esterno) il codice che per primo viene applicato e che per ultimo viene decodificato, mentrediremo inner (interno) il codice che per ultimo viene codificato e per primo decodificato. La sequenza èdunque:

codifica (esterno) -> codifica (interno) ->

---> CANALE --->

-> decodifica (interno) -> decodifica (esterno)

Il buon senso vuole che vengano accoppiati codici in grado di completarsi l’un l’altro con le propriepeculiarità: la NASA, per esempio, utilizza per le applicazioni deep-space un Reed-Solomon (255,233) suGF(28) (ottimo per la correzione degli errori a burst) concatenato a un codice convoluzionale per sfruttarela decodifica soft. Il codice convoluzionale viene scelto come interno, visto che il Reed-Solomon non èfacile da decodificare in maniera soft.

7.3 Turbo-codici

I Codici Turbo sono una classe di recenti codici di correzione degli errori ad alte prestazioni, chetrovano impiego nelle comunicazioni satellitari nello spazio profondo ed in altre applicazioni in cui i pro-gettisti puntano ad avere il massimo trasferimento di informazione su una banda limitata in presenza diun segnale ricevuto molto affetto da rumore. I Codici Turbo sono stati teorizzati da Claude Berrou, AlainGlavieux e Punya Thitimajshima presentati nel 1993 ad una conferenza dell’IEEE. I codici turbo sono an-cora ad oggi oggetto di ricerche in numerose università del mondo, allo scopo di raffinarli e di ottenereimplementazioni più efficienti.

106

CAPITOLO 7. ALTRI ASPETTI RIGUARDANTI I CODICI DI CANALE 107

Cerchiamo ora di comprenderne, almeno qualitativamente, il principio di funzionamento. Supponia-mo di avere un unico bit: gli unici messaggi possibili sono quindi w1 =′ 0′ e w2 =′ 1′. Un decisore chepropendesse per la massima probabilità a posteriori (MAP) deciderebbe in base al seguente criterio:

w = arg maxwi

p (wi ∣y )

Se quindi, fatta l’ipotesi di utilizzare la solita segnalazione antipodale, si ha

P (X = +1 ∣Y ) > P (X = −1 ∣Y )

il decisore sceglierà per il bit 0 (valore +1). La stessa cosa può essere vista nel seguente modo:

P (X = +1 ∣Y )

P (X = −1 ∣Y )> 1?⇒

{se sì allora propendi per + 1

altrimenti scegli −1

In versione logaritmica:

lnP (X = +1 ∣Y )

P (X = −1 ∣Y )> 0?⇒

{se sì allora propendi per + 1

altrimenti scegli - 1

Così scrivendo, la decisione sarà il segno del nostro logaritmo. Volendo possiamo sfruttare il criterio diBayes:

P (X ∣Y ) =P (Y ∣X ) P (X)

P (Y)

Quindi abbiamo:

x = sign

⎧⎨⎩ln

P (Y ∣X = +1 ) P (X = +1)P (Y)

P (Y ∣X = −1 ) P (X = −1)P (Y)

⎫⎬⎭ = sign{

lnP (Y ∣X = +1 ) P (X = +1)P (Y ∣X = −1 ) P (X = −1)

}=

= sign

⎧⎨⎩lnP (Y ∣X = +1 )P (Y ∣X = −1 )︸︷︷︸

primo contributo

+ lnP (X = +1)P (X = −1)︸︷︷︸

secondo contributo

⎫⎬⎭Il primo contributo è imparentato con il rapporto di funzioni di verosimiglianza, mentre il secondo con laprobabilità a priori.

Supponiamo ora che i bit siano equiprobabili (cosicché il secondo contributo svanisce):

x = sign{

lnP (Y ∣X = +1 )P (Y ∣X = −1 )

}Osserviamo lo schema di codifica/decodifica in figura 7.1: in essa si nota che i due decodificatori, che lavo-rano con valori soft, sono retroazionati cosicché il risultato del primo decodificatore viene dato al secondocome probabilità a priori. Vista l’esistenza di questi contributi, che entrano nella catena di decodificacome informazioni aggiuntive apportate di volta in volta dai vari decoder, viene a cadere l’equiprobabilitàdei simboli. Anche il secondo decoder, comunque, ha qualcosa da dire e lo passa al terzo decoder (chestrutturalmente è uguale al primo) e così via. Se riusciamo ad evitare il feedback positivo (che, come sap-piamo da Controlli Automatici, nuoce gravemente alla salute del sistema) riusciamo, grazie questa catena,a raffinare sempre di più la stima e a convergere verso un risultato incredibilmente preciso. I turbo-codicihanno infatti una capacità di correzione d’errore veramente impressionante: la curva della BER va giù astrapiombo anche nelle regioni a basso rapporto segnale-rumore (regione ’waterfall’). Purtroppo, questoavviene solo fino a determinati valori di SNR: andando oltre, la BER smette di calare vigorosamente e,anzi, tende a non migliorare più di tanto (regione ’error floor’).

107


Figura 7.1: Schema di principio del funzionamento dei turbo-codici

7.4 LDPC: Low Density Parity Check

I codici LDPC (Low Density Parity Check) costituiscono una particolare tipologia di codici a blocco acorrezione d’errore inventata da Robert G. Gallager nel 1961. Inizialmente inimplementabili a causa del-la loro complessità computazionale, i codici LDPC sono stati dimenticati per più di trent’anni fino allaloro riscoperta, avvenuta a metà degli anni ’90, sotto l’impulso dell’introduzione dei Turbo codici e delprincipio della decodifica iterativa (ad opera dei francesi Berrou e Glavieux nel 1993). Tali codici costi-tuiscono tutt’ora una delle migliori soluzioni in termini di efficienza spettrale; inoltre, uno dei grandivantaggi riscontrabili nell’uso di questa codifica consiste nella possibilità di poter decodificare l’informa-zione tramite un algoritmo iterativo (Belief Propagation) avente complessità gestibile e ottime prestazioni.La matrice H creata descrive interamente il codice, ed è una matrice sparsa1 e quasi-ciclica le cui righecostituiscono delle equazioni di parità da applicare alle parole ricevute al fine di verificarne la correttezzaed eventualmente correggerle.

Figura 7.2: Schema qualitativo del principio degli LDPC

Giusto per capire qualitativamente il principio di questi codici (in realtà molto complessi), esaminiamola figura 7.2: supponiamo che y3 sia il bit di parità calcolato a partire da y1 e y2. Avremo allora che:

p (c3 = 1 ∣y ) = p (c1 = 1, c2 = 0) + p (c1 = 0, c2 = 1) =

= p (c1 = 1 ∣y ) p (c2 = 0 ∣y ) + p (c1 = 0 ∣y ) p (c2 = 1 ∣y ) == p (c1 = 1 ∣y1 ) p (c2 = 0 ∣y2 ) + p (c1 = 0 ∣y1 ) p (c2 = 1 ∣y2 )

Possiamo quindi avere un’idea di quanto valga un messaggio in base al valore degli altri. Tramite unmeccanismo di scambio di messaggi, la probabilità si aggiorna nei vari passi dell’algoritmo.

7.4.1 QC-LDPC

Fra i codici LDPC si trova la sottofamiglia del QC-LDPC (Quasi-Cyclic Low Density Parity Check): essivengono creati affiancando matrici circolanti al fine di creare la matrice di parità del codice H. Le matricicircolanti hanno la caratteristica di poter essere descritte tramite la loro sola prima riga (detta anche rigageneratrice), in quanto le righe successive sono ottenute dalla prima attraverso shift ciclici. Questo metododi costruzione ha due importanti vantaggi:

1Matrice che presenta un numero di ’1’ molto inferiore rispetto al numero di ’0’.

108

CAPITOLO 7. ALTRI ASPETTI RIGUARDANTI I CODICI DI CANALE 109

∙ viene sensibilmente ridotta la routing complexity delle interconnessioni nei circuiti che implementanoil decoder e l’encoder;

∙ la complessità di codifica è lineare rispetto alla lunghezza del codice (vengono usati degli shiftregisters).

109


110

Elenco delle figure

1.1 Lo schema del collegamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.2 Grafico probabilità/informazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.3 Entropia di una variabile aleatoria bernoulliana . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4 Esempio delle relazioni che intercorrono fra le probabilità congiunte e marginali . . . . . . . 13

2.1 Sorgente tempo-discreta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192.2 Schema di trasmissione col codificatore di sorgente . . . . . . . . . . . . . . . . . . . . . . . . 232.3 Albero di un codice a prefisso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.4 Schema della codifica a blocchi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.5 L’alberino post-natalizio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.1 Canale discreto senza memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2 Il grafo bipartito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.3 Esempio con grafo bipartito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.4 Canale binario simmetrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.5 Capacità in funzione di p per il BSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.6 Binary Erasure Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.7 Canale Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.8 Capacità del canale Z in funzione della probabilità p . . . . . . . . . . . . . . . . . . . . . . . 363.9 Canale binario non simmetrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.10 Canale ’strano’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.11 Canale discreto senza memoria: caso di gruppi di simboli . . . . . . . . . . . . . . . . . . . . 393.12 Y dipende da X, Z dipende da X solo per mezzo di Y . . . . . . . . . . . . . . . . . . . . . . 403.13 Apparato per illustrare la disuguaglianza di Fano . . . . . . . . . . . . . . . . . . . . . . . . . 403.14 Interpretazione grafica della disuguaglianza di Fano . . . . . . . . . . . . . . . . . . . . . . . 423.15 Limite superiore per l’entropia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.16 Schema di riferimento per la dimostrazione del secondo teorema di Shannon . . . . . . . . . 443.17 Probabilità di errore e code-rate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.18 Densità di probabilità di una variabile aleatoria continua . . . . . . . . . . . . . . . . . . . . . 46

4.1 Rumore additivo gaussiano bianco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514.2 Capacità in funzione del rapporto segnale rumore . . . . . . . . . . . . . . . . . . . . . . . . . 524.3 Schema del caso tempo-continuo a banda limitata . . . . . . . . . . . . . . . . . . . . . . . . . 534.4 Spettri dei segnali (raffiguriamo solo la parte tra −B e B tanto ci pensa il filtro ad eliminare

tutto il resto!) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534.5 Capacità su banda in funzione dell’SNR e capacità in funzione della banda . . . . . . . . . . 554.6 Sistema di trasmissione completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 564.7 Punti ammissibili e non ammissibili e limite di Shannon (1) . . . . . . . . . . . . . . . . . . . 574.8 Punti ammissibili e non ammissibili e limite di Shannon (2) . . . . . . . . . . . . . . . . . . . 584.9 Schema della trasmissione antipodale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584.10 Schema della trasmissione antipodale (una volta elaborato) . . . . . . . . . . . . . . . . . . . 604.11 La gaussiana e le erfc da considerare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.12 La similitudine con il canale BSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.13 Schema senza decisore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.14 Caso unquantized confrontato con il BSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

111

112 ELENCO DELLE FIGURE

4.15 Caso passabanda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.16 La tecnica del waterfilling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.17 Canale i-esimo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.18 Guadagno in potenza e canali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.19 Water-filling nel caso discreto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

5.1 Schema della codifica a blocco lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695.2 Insieme delle parole non codificate e mapping iniettivo verso quello delle parole codificate . 705.3 Confronto fra il caso non codificato e il codice a ripetizione (3,1) . . . . . . . . . . . . . . . . 725.4 Ogni bit della parola di codice è combinazione lineare dei bit della parola d’informazione . 735.5 Lo schema di trasmissione: codifica, decodifica e decisione . . . . . . . . . . . . . . . . . . . . 795.6 Regioni di decisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825.7 Criterio sub-ottimo di decisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 835.8 Rumore additivo gaussiano e criterio ML: schema di riferimento . . . . . . . . . . . . . . . . 845.9 Schema di riferimento per la segnalazione antipodale su canale AWGN . . . . . . . . . . . . 855.10 Apparato per la moltiplicazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935.11 Apparato per la divisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935.12 Codificatore per codice sistematico ciclico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935.13 Esempio di schema per codificatore MLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

6.1 Schema generico per codificatore di codici convoluzionali . . . . . . . . . . . . . . . . . . . . 996.2 Esempio di codificatore per codice convoluzionale . . . . . . . . . . . . . . . . . . . . . . . . . 1006.3 Diagramma degli stati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1006.4 Traliccio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1016.5 Il traliccio percorso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1016.6 Diagramma a traliccio di codice convoluzionale punturato . . . . . . . . . . . . . . . . . . . . 1036.7 Codificatore di codice convoluzionale sistematico . . . . . . . . . . . . . . . . . . . . . . . . . 104

7.1 Schema di principio del funzionamento dei turbo-codici . . . . . . . . . . . . . . . . . . . . . 1087.2 Schema qualitativo del principio degli LDPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

112

Elenco delle tabelle

1.1 Probabilità congiunte e marginali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1 Qualche esempio per la nomenclatura dei codici . . . . . . . . . . . . . . . . . . . . . . . . . . 232.2 Caso sfortunato di Shannon-Fano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.3 Distribuzione di probabilità del nostro esempio . . . . . . . . . . . . . . . . . . . . . . . . . . 292.4 Distribuzione di probabilità del nostro esempio, con supersimboli . . . . . . . . . . . . . . . 29

5.1 Matrici generatrici e di controllo parità di un codice e del suo duale . . . . . . . . . . . . . . 755.2 Distribuzione dei pesi del codice di Hamming (7,4) . . . . . . . . . . . . . . . . . . . . . . . . 765.3 Distribuzione dei pesi del codice di Hamming (7,4) e della versione estesa . . . . . . . . . . 775.4 Distribuzione dei pesi del codice di Hamming (7,4) e della versione purgata . . . . . . . . . 775.5 Parametri n e k per codici di Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785.6 La tabella di decodifica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815.7 Lo Standard Arrary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815.8 Lo Standard Array dell’esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 825.9 Set di distanze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885.10 Possibili codici ciclici con n = 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925.11 Associazione sindrome-pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

6.1 Codice convoluzionale sistematico vs. non sistematico . . . . . . . . . . . . . . . . . . . . . . 104

113

Teocod (revisionato)

Documents

Transcript of Teocod (revisionato)