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. Questo perché (ovviamente!) non si vuole avere alcuna presunzione di esaustività, né di assoluta correttezza: nonostante le revisioni fin’ora effettuate, potrebbero infatti essere ancora presenti molti errori e imprecisioni.

2

Indice 1

2

3

Introduzione alla Teoria dell’Informazione 1.1 Schema del collegamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 La teoria dell’informazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Eventi, variabili aleatorie, bit d’informazione . . . . . . . . . . . . . . . . . . . . . 1.3.1 Informazione associata a due eventi indipendenti . . . . . . . . . . . . . . 1.3.2 Entropia di una variabile aleatoria . . . . . . . . . . . . . . . . . . . . . . . 1.3.3 Probabilità condizionata, probabilità marginale, distribuzione congiunta 1.3.4 Entropia congiunta, entropia condizionata . . . . . . . . . . . . . . . . . .

. . . . . . .

. . . . . . .

7 7 8 8 9 9 12 13

Codifica di sorgenti discrete 2.1 Osservazione simbolo per simbolo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Osservazione per gruppi di simboli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Entropia di una sorgente stazionaria: due definizioni . . . . . . . . . . . . . . . . . . . . . . 2.4 Ridondanza e confronto fra sorgenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5 Tecniche di compressione dei dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Codici a prefisso e disuguaglianza di Kraft . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Un’applicazione della disuguaglianza di Kraft: i codici a prefisso di Shannon-Fano 2.6 Teorema della codifica di sorgente (I teorema di Shannon) . . . . . . . . . . . . . . . . . . . 2.7 Codice di Huffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8 Codifica a blocchi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9 Codifica a corse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10 Codice di Lempel-Ziv . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.11 Considerazioni finali: lossy o lossless? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

19 19 20 20 21 22 24 26 26 27 28 29 29 30

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

La codifica di canale e la capacità 3.1 Canale discreto senza memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Capacità di canale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.1 Canale deterministico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.2 Canale binario simmetrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.3 Canale binario a cancellazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.4 Canale Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2.5 Canale binario non simmetrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Capacità di canale con blocchi di simboli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Disuguaglianza del data processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Disuguaglianza di Fano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Codifica di canale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.7 Teorema della codifica di canale (secondo teorema di Shannon) . . . . . . . . . . . . . . . . . 3.8 Variabili aleatorie continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Entropia differenziale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9.1 Teorema: la distribuzione uniforme ha entropia massima (caso intervallo limitato) . 3.9.2 Teorema: la distribuzione gaussiana ha entropia massima (caso intervallo illimitato) 3.9.3 Teorema: la distribuzione esponenziale negativa ha entropia massima (caso intervallo [0, +∞] ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

31 31 32 32 33 33 34 36 39 40 40 42 44 45 46 47 48 49

INDICE

4 4

5

6

Il limite di Shannon 4.1 Capacità del canale additivo gaussiano bianco . . . . . . . . . . . . . . 4.2 Caso tempo-continuo a banda limitata (formula di Hartley-Shannon) . 4.2.1 Incorrelazione del rumore . . . . . . . . . . . . . . . . . . . . . . 4.3 Il limite di Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.4 Antipodal Signalling AWGN . . . . . . . . . . . . . . . . . . . . . . . . . 4.5 Hard decision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 Unquantized output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.7 Low SNR region . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.8 Trattamento dei segnali passa-banda e water-filling . . . . . . . . . . . . 4.8.1 Caso tempo-discreto . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

51 51 53 55 56 57 60 61 62 63 65

I codici di canale: codici a blocco 5.1 Codici a blocco . . . . . . . . . . . . . . . . . . . . . 5.1.1 Alcune definizioni e terminologia . . . . . . 5.2 Concetti elementari di algebra lineare . . . . . . . . 5.3 Codici a blocco lineari . . . . . . . . . . . . . . . . . 5.4 La matrice generatrice . . . . . . . . . . . . . . . . . 5.5 Codici sistematici . . . . . . . . . . . . . . . . . . . . 5.6 Matrice di controllo parità . . . . . . . . . . . . . . . 5.7 Codici estesi . . . . . . . . . . . . . . . . . . . . . . . 5.8 Codici purgati . . . . . . . . . . . . . . . . . . . . . . 5.9 Il Singleton Bound . . . . . . . . . . . . . . . . . . . . 5.10 Codici di Hamming . . . . . . . . . . . . . . . . . . . 5.11 La decodifica e la Teoria della Decisione . . . . . . . 5.12 Decodifica ottima per codici a blocco su canale BSC 5.13 Rilevazione degli errori e standard array . . . . . . . 5.14 Capacità di correzione di un codice (canale BSC) . . 5.15 Criterio ML per canali additivi gaussiani . . . . . . 5.16 Union Bound . . . . . . . . . . . . . . . . . . . . . . . 5.17 Codici accorciati (shortened codes) . . . . . . . . . . . 5.18 Codici a blocco lineari ciclici . . . . . . . . . . . . . 5.19 Codificatore per codici ciclici (sistematici e non) . . 5.20 Calcolo della sindrome . . . . . . . . . . . . . . . . . 5.21 Applicazioni notevoli dei codici ciclici . . . . . . . . 5.21.1 CRC: Cyclic Redundancy Check Codes . . . . . 5.21.2 Codici Hamming ciclici . . . . . . . . . . . . 5.21.3 Codice di Golay . . . . . . . . . . . . . . . . . 5.21.4 Codici BCH . . . . . . . . . . . . . . . . . . . 5.22 Codici di Reed-Solomon . . . . . . . . . . . . . . . . 5.23 Codici per la rilevazione di errori burst . . . . . . . 5.24 Codici MLSR (Maximum Length Shift-Register Codes)

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69 69 70 71 71 73 74 74 76 77 77 78 78 79 80 82 84 85 88 89 92 92 94 94 95 95 95 95 96 96

Codici a traliccio 6.1 Codici convoluzionali . . . . . . . . . . . . . . . . . . . . . . . 6.2 Diagramma a traliccio . . . . . . . . . . . . . . . . . . . . . . . 6.3 Decodifica dei codici convoluzionali con hard decisions su BSC 6.4 Algoritmo di Viterbi . . . . . . . . . . . . . . . . . . . . . . . . 6.4.1 Complessità . . . . . . . . . . . . . . . . . . . . . . . . . 6.4.2 Altri aspetti implementativi . . . . . . . . . . . . . . . . 6.5 Codici convoluzionali punturati . . . . . . . . . . . . . . . . . 6.6 Codici convoluzionali sistematici . . . . . . . . . . . . . . . . . 6.7 Codici convoluzionali catastrofici (paura eh!?) . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

99 99 100 101 102 102 103 103 103 103

4

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

INDICE 7

Altri aspetti riguardanti i codici di canale 7.1 Interleaving . . . . . . . . . . . . . . . . 7.1.1 Interleaving a blocco . . . . . . 7.2 Codici concatenati . . . . . . . . . . . 7.3 Turbo-codici . . . . . . . . . . . . . . . 7.4 LDPC: Low Density Parity Check . . . . 7.4.1 QC-LDPC . . . . . . . . . . . .

5

. . . . . .

. . . . . .

. . . . . .

. . . . . .

5

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

105 105 105 106 106 108 108

INDICE

6

6

Capitolo 1

Introduzione alla Teoria dell’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 collegamento! Questo schemino essenziale mostra il percorso che l’informazione compie, dalla sorgente all’utilizzatore finale; gli step sono i seguenti: ∙ sorgente: trattasi della sorgente dell’informazione: può essere un’entità analogica1 (un suono), ma anche 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 che si possa spedire quanta più informazione possibile nel minor tempo possibile. Possono essere di due tipi, in base a se viene persa informazione (esempio: codifica JPEG) o meno (esempio: compressione ZIP); ∙ codificatore di canale: ha il compito di proteggere, con l’aggiunta di simboli di ridondanza, i dati dai 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. 1 In

tal caso sarà necessario un convertitore A/D.

7

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

8

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 incertezza che 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, in questo punto, non sono caduti degli aerei’, non diamo una grande informazione perché si presuppone che questo 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 teoriche su cui si fonda la scienza dell’informazione. La sua nascita è relativamente recente: essa viene solitamente fatta risalire al 1948, anno in cui Claude Shannon pubblicò sul Bell System Technical Journal Una teoria matematica della comunicazione in cui introduceva per la prima volta in modo sistematico lo studio dell’informazione e della comunicazione. Grazie alla sua affascinante teoria, Shannon è riuscito a definire e specificare in maniera quantitativa i meccanismi di compressione, codifica e trasmissione dei dati, 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 variabile aleatoria (v.a. o r.m.2 ). Indicheremo con X una generica variabile aleatoria e con 𝒳 l’insieme di tutti gli L valori che essa può assumere

𝒳 = x˜1 , x˜2 , . . . , x˜ L In questo contesto, L viene detta cardinalità di 𝒳 . A ciascun possibile risultato dell’esperimento ’incarnato’ dalla variabile aleatoria viene associato un valore e una probabilità: p ( X = x˜1 ) = p ( x˜1 ) = p1 p ( X = x˜2 ) = p ( x˜2 ) = p2 ... p ( X = x˜ L ) = p ( x˜ L ) = p L Chiaramente, per le basilari proprietà del calcolo aleatorio, si deve avere che

∑ pi = 1

(1.1)

i

L’informazione ’portata’ dall’esperimento x è pari a: I ( x ) = log2

1 = − log2 p( x ) p( x )

(1.2)

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

Variable.

8

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

Figura 1.2:

1.3.1

9

Grafico probabilità/informazione

Informazione associata a due eventi indipendenti

L’informazione associata a due eventi indipendenti è pari alla somma delle informazioni degli eventi presi singolarmente. Se si ha quindi xi , x j → Statisticamente indipendenti la probabilità congiunta sarà p ( xi , x j ) = p ( xi ) p ( x j ) e l’informazione pari a: I ( xi , x j ) = log2

1.3.2

1 1 1 = log2 + log2 = I ( xi ) + I ( x j ) p ( xi ) p ( x j ) p ( xi ) p( x j )

(1.3)

Entropia di una variabile aleatoria La mia più grande preoccupazione era come chiamarla. Pensavo di chiamarla informazione, ma la parola era fin troppo usata, così decisi di chiamarla incertezza. Quando discussi della cosa con John Von Neumann, lui ebbe un’idea migliore. Mi disse che avrei dovuto chiamarla entropia, per due motivi: ’Innanzitutto, la tua funzione d’incertezza è già nota nella meccanica statistica con quel nome. In secondo luogo, e più significativamente, nessuno sa cosa sia con certezza l’entropia, così in una discussione sarai sempre in vantaggio’. Claude Shannon

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

∑

x ∈𝒳

p( x ) I ( x ) =

∑

x ∈𝒳

p( x ) log2

9

1 = − ∑ p( x ) log2 p( x ) p( x ) x ∈𝒳

(1.4)

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

10 ESEMPIO:

Calcoliamo l'entropia di una distribuzione

Bernoulliana3: 𝒳 = x˜1 , x˜2

Associamo a x˜1 la probabilità p e a x˜2 la probabilità q = 1 − p. L'entropia sarà quindi: H ( x ) = p log2

1 1 1 1 + q log2 = p log + (1 − p) log p q p 1− p

Andando a gracare 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 ) è 1 una quantità sicuramente non negativa, così come è sempre positivo il termine log2 ; 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( x˜1 ) = p( x˜2 ) = . . . = p( x˜ L ) =

1 L

Si ha infatti: =1

1 1 H ( x ) − log2 L = ∑ p ( x ) log2 + log = p x L ( ) x | {z }

z }| { 1 1 ∑ p (x) log2 p (x) + ∑ p (x) ⋅ log L = x x

=− log2 L

[

] 1 1 p x log + log = ( ) ∑ 2 p (x) L x

∑ p (x)

[ log2

x

|

] 1 p (x) L {z }

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

10

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

11

Applicando una proprietà notevole dei logaritmi: 1 1 1 1 p (x) L ⇒ log2 = ln = log2 e ⋅ ln log2 e p (x) L p (x) L p (x) L {z }

log2 |

cambio di base

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

1 1 = log2 e ⋅ ln ⇒ log2 p (x) L p (x) L

1 p (x) L | {z }

(

⩽ log2 e ⋅

1 −1 p (x) L

) (1.6)

la χ dell’equaz. precedente

Sfruttando questa disuguaglianza nella nostra equazione arriviamo ad affermare che: [ ] [ ] ( ) 1 1 1 H ( x ) − log2 L = ∑ p ( x ) log2 ⩽ log2 e ⋅ ∑ p ( x ) − 1 = log2 e ∑ − ∑ p ( x ) = 0 p (x) L p (x) L x x x L x {z } | 1−1=0

Infine: H ( x ) − log2 L ⩽ 0 ⇒ H ( x ) ⩽ log2 L Questo risultato ci suggerisce una proprietà importante: la distribuzione uniforme (quella che rende possibile la sostituzione del segno ≤ con l’uguaglianza) è un’estremale per l’entropia e garantisce la massima incertezza. ESERCIZIO:

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

n

i =1

i =1

∑ a i = ∑ bi = 1

Vogliamo dimostrare che

n

n

i =1

i =1

∑ ai log2 ai ≥ ∑ ai log2 bi

cioè che:

n

b

∑ ai log2 aii

≤0

i =1

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

n b ∑ ai log2 aii ⩽ ∑ ai i =1 i =1

) bi − 1 log2 e a } | i {z

sicuramente minore di

4 Si

n

(

log2

= log2 e ⋅ ∑ (bi − ai ) = log2 e ⋅

(

i =1

|

bi ai

n

n

i =1

i =1

∑ bi − ∑ a i {z

=0

)

=0 }

osservi infatti che:

In χ = 1 le funzioni valgono entrambe 0 Derivata di χ − 1 ⇒ 1 ⎧ 1   per χ > 1 → < 1, la funzione ln χ cresce più lentamente di χ − 1 andando nella direzione positiva delle χ χ 1 ⎨ Derivata di ln χ ⇒ χ  1  ⎩ per 0 < χ < 1 → > 1, la funzione ln χ cala più velocemente di χ − 1 andando nella direzione negativa delle χ χ

11

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

12 ESERCIZIO:

Siano ai e bi due successioni e sia

i→∞

ai −−→ a

Si dimostri che si ha (regola di Cesaro 5 ): bn =

1 n

n

n→∞

∑ ai −−−→ a

(1.7)

i =1

Si deve insomma dimostrare che ∀ε > 0 ∃ N (ε) : ∣ an − a∣ < ε ∀ n > N (ε)

Soluzione6 : 1 n

bn − a = 1 ∣ bn − a ∣ = n

n

∑ ai − a

i =1

⎛ ⎞ ( ) N (ε) N (ε) n 1⎝ 1 ∑ ∣ a i − a ∣ = n ∑ ∣ a i − a ∣ + ∑ ∣ a i − a ∣ ⎠ ⩽ n ∑ ∣ a i − a ∣ + ε ( n − N ( ε ) − 1) i =1 i =1 i =1 i = N (ε)+1 ( ) N (ε) 1 ε n→∞ ∣ bn − a ∣ ⩽ ∣ ai − a∣ + (n − N (ε) − 1) −−−→ ε n i∑ n =1 n

n→∞

bn −−−→ 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 p X,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) (1.9) p Y ( y ) = p ( y ) = p (Y = y ) Infine, abbiamo la probabilità condizionata, ovvero quella che si verifichi un dato evento sapendo a priori che se n’è verificato un altro: di seguito riportiamo l’espressione della probabilità che X assuma valore x sapendo 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 ) =

∑

p( x, y)

(1.12)

y∈𝒴

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

∑ ∑

p( x, y) = 1

x ∈𝒳 y∈𝒴

12

(1.13)

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

Figura 1.4:

13

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 ) 1/2 = =1 p ( y2 ) 1/2

Guardando la tabella, d'altronde, sappiamo che la probabilità che X e Y assumano contemporaneamente valori x2 e y2 è nulla: quindi, se si palesa l'evento y2 , sicuramente si sarà vericato x1 .

1.3.4

Entropia congiunta, entropia condizionata

Definita la probabilità congiunta e la probabilità condizionata, possiamo ragionare sull’entropia: date le variabili aleatorie X e Y possiamo definire l’entropia di ciascuna H ( X ) = − ∑ p ( x ) log2 p ( x ) x

H (Y ) = − ∑ p (y) log2 p (y) y

ma possiamo anche definire: ∙ l’entropia congiunta:

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

(1.14)

y

∙ l’entropia condizionata: una volta che abbiamo calcolato H ( X ∣Y = y) = − ∑ p( x ∣y) log2 p( x ∣y)

(1.15)

x

possiamo definire entropia condizionata la seguente quantità: H ( X ∣Y = y )

z }| { H ( X ∣Y ) = Ey [ H ( X ∣Y = y)] = ∑ p (y) H ( X ∣Y = y ) = − ∑ ∑ p (y) p ( x ∣y ) log2 p ( x ∣y ) = y

x

y

= − ∑ ∑ p ( x, y) log2 p ( x ∣y ) | {z } x y = p(y) p( x ∣y )

5 Ernesto Cesàro (Napoli, 12 marzo 1859 - Torre Annunziata, 12 settembre 1906) è stato un matematico italiano, noto per i suoi contributi alla geometria differenziale e alla teoria delle serie infinite. 6 Si tratta della mia personalissima dimostrazione, quindi potrebbe non fare testo ed essere errata. Prendetela con le molle!

13

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

14

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 ) = − ∑ ∑ p( x, y) log2 p( x ∣y ) − ∑ p (y) log2 p (y) = x

y

y

{z

|

}

H ( X ∣Y )

|

{z

H (Y )

}

p( x, y) = − ∑ ∑ p( x, y) log2 p( x ∣y ) − ∑ ∑ p( x, y) log2 = p( x ∣y ) x y y x | {z } p(y)

[

]

[ ( )] p( x, y) p( x, y) = ∑ ∑ p( x, y) − log2 p( x ∣y ) − log2 = − ∑ ∑ p( x, y) log2 p( x ∣y ) = p( x ∣y ) p( x ∣y ) x y x y

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

y

∙ seconda proprietà: l’incertezza che abbiamo sulla variabile X data la variabile Y è non superiore all’incertezza che abbiamo sulla sola X. Si ha ovvero: H ( X ∣Y ) ⩽ H ( X ) ⇒ con = solo se X e Y sono indipendenti Dimostrazione: (

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

y

|

)

⩽0

x

{z

}

H ( X ∣Y )

|

{z

}

H (X)

1

1

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

x

y

y

|

{z

p( x )

}

(

) 1 p (y) ∑ ∑ p (x, y) log2 p (x, y) − log2 p (x) ⩽ 0 x y ) ( ) ( p (y) p ( x ) p (y) p ( x ) p x, y ⩽ log e p x, y − 1 = log ( ) ( ) ∑∑ 2 p ( x, y ) 2 ∑∑ p ( x, y) x y x y

= log2 e ∑ ∑ p (y) p ( x ) − p ( x, y) = 0 x

y

|

{z

=0

}

∙ terza proprietà (chain rule, regola della catena): consideriamo tre variabili aleatorie X1 , X2 , X3 . Allora si 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 la seconda delle nostre proprietà): H ( X1 , X2 , . . . , X k ) =

k

k

i =1

i =1

∑ H ( X i ∣ X i − 1 , X i − 2 , . . . , X1 ) ⩽ ∑ H ( X i )

k

(1.17)

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

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

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

15

∙ 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 separatamente gli elementi (nella coppia, infatti, possono esservi regole o legami che diminuiscono l’incertezza). Generalizzando: k

H ( X1 , X2 , X3 , . . . , X K ) ≤

∑ Xi

i =1

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

( ) 1 H (X) = ℋ 4 ∙ entropia congiunta: H ( X, Y ) =

1 1 3 1 log2 4 + log2 4 + log2 2 + 0 = 4 4 2 2

∙ entropia condizionata (y1 ): H ( X ∣Y = y1 ) = − ∑ p ( x ∣y1 ) log2 p ( x ∣y1 ) = − ∑ x

⎛

p( x1 ,y1 )

x

p ( x, y1 ) p ( x, y1 ) log2 = p ( y1 ) p ( y1 )

⎞

p( x2 ,y1 )

z}|{ z}|{ ( ) ⎜ 0, 25 0, 25 0, 25 0, 25 ⎟ 1 1 ⎜ ⎟ = −⎜ log2 + log2 (−1) + (−1) = 1 ⎟=− 0, 5 0, 5 0, 5 ⎠ 2 2 ⎝ 0, 5 ∙ entropia condizionata (y2 ): H ( X ∣Y = y2 ) = − ∑ p ( x ∣y2 ) log2 p ( x ∣y2 ) = − ∑ x

⎛

x

p ( x, y2 ) p ( x, y2 ) log2 = p ( y2 ) p ( y2 )

⎞

p( x1 ,y2 )

z}|{ ⎜ 0, 5 ⎟ 0, 5 ⎜ ⎟ = −⎜ log2 + 0⎟ = 0 ⇒ non c'è incertezza! 0, 5 ⎝ 0, 5 ⎠

A prima vista i seguenti risultati H (X) = ℋ

( ) 1 = 0, 8113 < 1 4

H ( X ∣Y = y 1 ) = 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 : ( ) 1 H ( X ∣Y ) = H ( X ∣Y = y1 ) p (y1 ) + H ( X ∣Y = y2 ) p (y2 ) = 0, 5 < ℋ 4

Ecco quindi che tutto torna! 7 Ricordiamo

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

15

(1.19)

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

16 ESERCIZIO:

NOTA: non ho le soluzioni 'uciali' 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 𝒳 = 𝒴 = {−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 ∑ ∑ e βxy = 1 x

y

Allora: k∑ x

2.

(

∑e y

) βxy

( ) ( ) ( ) = k ∑ e− βx + e βx = k e− β + e β + e− β + e β = 2k e− β + e β = 1 ⇒ k = x

2e− β

1 + 2e β

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

y=1

ke β

ke− β

y = −1

ke− β

ke β

prob. marginale

k (e β + e− β ) =

Tabella 1.1:

3.

1 2

k (e β + e− β ) =

prob. marginale 1 2 1 k (e β + e− β ) = 2 k (e β + e− β ) =

1 2

Probabilità congiunte e marginali

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 ) = − ∑ ∑ p ( x, y) log2 p ( x, y) = − ∑ ( p ( x, −1) log2 p ( x, −1) + p ( x, 1) log2 p ( x, 1)) = x

y

x

= − ( 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)) = ( −β ) ( ) e log2 e− β + e β log2 e β −β −β β β β β −β −β = −k e log2 e + e log2 e + e log2 e + e log2 e =− e− β + e β 16

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

17

ESERCIZIO:

NOTA: non ho le soluzioni 'uciali' 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 𝒳1 = {1, . . . , m} 𝒳2 = {m + 1, . . . , n}

A partire da queste due si denisce 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 ) ≜ − ∑ p ( x ) log2 p ( x ) = x

m

= −α

∑

x =1 m

= −α log2 α − α

n

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

∑

x = m +1

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

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

x =1

p2 ( x ) [ p2 ( x )] =

x = m +1

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

3.

Determinare le entropie H(X1 ) e H(X2 ). Vedi punto precedente.

17

18

CAPITOLO 1. INTRODUZIONE ALLA TEORIA DELL’INFORMAZIONE

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 variabili aleatorie (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ì che possiamo scrivere: ( ) p X n1 = x (1) , X n2 = x (2) , . . . , X n M = x ( M ) =

M

∏p

(

) Xni = x (i ) =

i =1

{

M

∏p

(

i =1

ni → istante d’osservazione

x (i )

) (2.1)

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

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 ) = − ∑ p ( x ) log2 p ( x ) 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

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

20

2.2

Osservazione per gruppi di simboli

Immaginiamo ora di osservare gruppi di K simboli alla volta. Ogni gruppo sarà interpretabile come (K )

una variabile aleatoria multidimensionale: chiameremo a tal proposito Xi il vettore di K simboli di posizione i (diremo anche che è l’i-esimo supersimbolo). Supponendo che i nostri supersimboli siano stazionari (dato che la DMS lo è) potremo calcolarne l’entropia: ( ) H X ( K ) = H ( X1 , X2 , . . . , X K ) =

K

∑

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

i =1

Shannon supersimbolo

]

Con un semplicissimo passaggio algebrico possiamo anche scrivere: H ( X (K ) ) = H (X) K

(2.2)

Rimuovendo l’ipotesi di mancanza di memoria1 , ma mantenendo quella di stazionarietà, abbiamo invece: ( ) ( ) !! K H X ( K ) = H ( X1 , X2 , . . . , X K ) < ∑ H ( X i ) = K ⋅ H ( X ) ⇒ H X ( K ) < K ⋅ H ( X ) i =1

H |

(

X (K ) K {z

)

< }

H (X) | {z }

Entropia/simbolo (caso NO memoria)

Entropia/simbolo (caso con 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 passare al limite la relazione 2.2: ( ) H X (k) H∞ ( X ) = lim (2.3) k k→∞ Questo procedimento equivale a effettuare una media sull’entropia dei simboli appartenenti ad un supersimbolo X (k) enorme (ovvero grande a tal punto da inglobare tutta sequenza con il passaggio al limite); ∙ la seconda definizione si ricava col calcolo dell’entropia di un simbolo molto ’lontano’ una volta noti tutti i precedenti: ′ (2.4) H∞ ( X ) = lim H ( Xk ∣ Xk−1 Xk−2 . . . X1 ) k→∞

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’ipotesi di stazionarietà. Sicuramente possiamo scrivere 0 ⩽ H ( X k ∣ X k − 1 X k − 2 . . . X1 ) ⩽ H ( X k ∣ X k − 1 X k − 2 . . . X2 ) | {z } Un simbolo in meno ( X1 )!

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

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 modifichi il risultato: H ( X k ∣ X k − 1 X k − 2 . . . X2 ) = H ( X k − 1 ∣ X k − 2 X k − 3 . . . X1 ) | {z } Traslazione di una posizione

Ora possiamo immaginare di iterare questi passaggi, rimuovendo di volta in volta un simbolo e successivamente traslando2 ; l’entropia, ad ogni rimozione, sarà sempre ≤ rispetto al passo precedente: abbiamo quindi 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) 1 k Cesa ro ′ = ∑ H ( Xi ∣ Xi−1 . . . X1 ) −−−−→ H∞ (X) k k i =1 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)

′ ( X ) e H ( X ) diventa un = nel caso senza Come abbiamo già più volte sottolineato, il segno ≤ fra H∞ memoria; il segno ≤ fra H ( X ) e log2 L, invece, diventa un = nel caso di distribuzione uniforme (simboli tutti equiprobabili): tale tipologia di p.d.f.4 è infatti quella che massimizza l’entropia e la porta al suo valore 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 simboli equiprobabili.

2.4

Ridondanza e confronto fra sorgenti

Si definisce ridondanza di sorgente la quantità:

ℛ=

Hmax − H∞ ( X ) H∞ ( X ) ⩽1 = 1− Hmax log2 L

(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 due effetti provocano la ridondanza!

Hmax − H∞ ( X ) =

z

Hmax − H ( X ) | {z }

}| +

dovuto alla non equiprobabilità

H ( X ) − H∞ ( X ) | {z }

{

(2.9)

legato alla memoria della sorgente

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 ) {z } |

equiprobabili ( Hmax = H ( X ))

+

H ( X ) − H∞ ( X ) {z } |

sorgente senza memoria ( H ( X )= H∞ ( X ))

2 FFffatto? 3 Il

termine H ( Xi ∣ Xi−1 . . . X1 ) è l’ak dell’enunciato della regola di Cesaro. Density Funciton.

4 Probability

21

=0⇒ℛ=0

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

22

Tramite il parametro ridondanza possiamo fare interessanti paragoni fra due sorgenti; consideriamo, a titolo d’esempio, due sorgenti tempo-discrete: la prima sia una sorgente avente symbol-rate Bs1 e entropia H∞ ( 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 ⇒

log2 L Bs1 Hmax = = Bs2 H∞ ( X ) H∞ ( X )

Osservando questa relazione possiamo fare due interessanti osservazioni: ∙ la sorgente 1 diventa equivalente alla sorgente ’ideale’, ed emette quindi massimo contenuto informativo, solo se H∞ ( X ) = Hmax ; ∙ se la sorgente è un po’ ridondante (entropia non massima) sarà necessario emettere più simboli, e quindi 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, 46

Sh simbolo

Questo signica 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’ideale sarebbe avere simboli indipendenti, equiprobabili e assenza di memoria. Possiamo tuttavia migliorare l’efficienza di una sorgente (ovvero aumentarne l’entropia) tramite un dispositivo, denominato codificatore di sorgente (vedi figura 2.2), da posporre alla sorgente stessa per cercare, a parità di informazione, di diminuire il più possibile il numero di bit da trasmettere. In questo consiste l’operazione di compressione dei dati. 22

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

Figura 2.2:

23

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 di codifica (codifica di sorgente) dev’essere chiaramente invertibile dal ricevente per poter fruire dell’informazione. 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): ( ) (2.10) C ( xi ) ∕ = C x j , ∀i ∕ = j Un codice non singolare potrebbe non essere decodificabile in maniera univoca (e quindi non invertibile, vedi esempio di seguito); si parla invece di codice univocamente decodificabile (invertibile) se, data una sequenza qualunque, si ha: C ( x1 ) , C ( x2 ) , . . . , C ( x M )

⇔ univocamente

x1 , x2 , . . . , x M

(2.11)

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

ℒ(C ) = E[l ( x )] =

∑

l ( x ) p( x )

(2.12)

x ∈𝒳

Inoltre, un codice si dice a prefisso (o codice istantaneo)5 se nessuna parola di codice C ( x ) è prefisso di un’altra. Tali codici sono sempre univocamente decodificabile. Questo aspetto verrà approfondito nel paragrafo 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⋅ 5 In

1 1 1 1 3 +2⋅ +2⋅ +2⋅ = 2 4 8 8 2

quanto la codifica è istantanea.

23

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

24

Il codice 1 non è tuttavia invertibile perché non è univocamente decodicabile : per esempio 1001

potrebbe contemporaneamente essere x1 x2 x1 oppure x4 x3 , ma non possiamo saperlo. Come si può facilmente vericare, i codici 2 e 3 sono invece univocamente decodicabili in quanto non vi è ambiguità. In particolare: ∙ il codice 2 è a presso in quanto nessuna codeword è presso di altre. Inoltre esso ha lunghezza

media

2⋅

1 1 3 7 +2⋅ +2⋅ = 2 4 8 4

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 è decodicabile, ma dobbiamo per forza attendere che nisca la sequenza per poter

comprendere quale sia stata la parola codicata (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 essere associate alle foglie di un albero. Consideriamo il codice 2 (tabella 2.1): una possibile rappresentazione ad albero è 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 6 Da Wikipedia: In coding theory, Kraft’s inequality gives a condition for the existence of a uniquely decodable code for a given set of codeword lengths. Its applications to prefix codes and trees often find use in computer science and information theory. More specifically, Kraft’s inequality limits the lengths of codewords in a prefix code: if one takes an exponential function of each length, the resulting values must look like a probability mass function. Kraft’s inequality can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive.

∙ 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

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

25

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

∑ 2− li ≤ 1

(2.13)

i =1

Inoltre, esiste sempre un codice a prefisso con lunghezza l1 ≤ l2 ≤ l3 ≤ . . . ≤ l L in grado di soddisfare la disuguaglianza di cui sopra. Dimostrazione: iniziamo col dimostrare la necessarietà. Il codice a prefisso con parole di lunghezza l1 ≤ l2 ≤ l3 ≤ . . . ≤ l L può essere generato da un albero che si estende al massimo fino all’ordine l L , con 2l L potenziali nodi. Se però posizioniamo una parola di codice all’ordine li andiamo in realtà ad eliminare tutti i potenziali rami ’figli’ di quella parola, i quali sono 2l L −li . Abbastanza ovvio è il fatto che il numero di nodi che andremo in tutto a eliminare non potrà essere maggiore del numero totale di nodi 2l L : L

∑ 2l L − li ⩽ 2l L

i =1

Se ora dividiamo per 2l L quel che otteniamo è la disuguaglianza di Kraft. Ora passiamo a dimostrare la sufficienza: supponiamo che le nostre lunghezze abbiano soddisfatto la disuguaglianza. . . riusciamo ora a costruire un codice a prefisso? Immaginiamo di avere l’albero completo e di posizionare presso un suo nodo una certa parola di codice C1 di lunghezza l1 . Così facendo avremo seccato 2l L −l1 nodi, ovvero il 2 l L − l1 = 2 − l1 % 2l L dei nodi di ordine massimo (cioè i più ’figli di tutti’7 ). Questo implica che sarà rimasta una percentuale pari 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 quelli di 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 di Kraft, quindi esisteranno ancora dei nodi di ordine l L (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à seccare 2l L −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 massimo sono ancora vivi, etc. . . Al passo k la disuguaglianza di Kraft sarà ancora soddisfatta e varrà k

∑ 2− li

i =1

⩽ |{z} 1

totale

| {z }

% nodi (ordine max) morti

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 McMillan ha dimostrato che qualunque codice univocamente decodificabile ha lunghezze che soddisfano tale disuguaglianza. 7 Detto

così è ambiguo eh. . . ?

25

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

26

2.5.2

Un’applicazione della disuguaglianza di Kraft: i codici a prefisso di ShannonFano

I codici di Shannon-Fano8 sono un particolare tipo di codici a prefisso con lunghezze lk intere scelte secondo la relazione: ⌈ ⌉ 1 1 1 log2 ⩽ l ( x ) < log2 + 1 ⇔ l ( x ) = log2 = ⌈ I ( x )⌉ l ( x ) intero (2.14) p (x) p (x) p (x) Mostriamo che tali codici soddisfano la disuguaglianza di Kraft verificando la prima parte della disuguaglianza soprastante: l ( x ) ⩾ log2

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

1 p( x )

⇒ 2l ( x ) ⩾

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

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

∑ 2− l ( x ) ⩽ ∑ p ( x ) = 1 x

x

ESEMPIO:

Se proviamo a costruire il relativo codice a presso 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), stabilisce dei limiti alla massima compressione possibile di un insieme di dati e definisce il significato operativo dell’entropia. Il teorema stabilisce che, per una serie di variabili aleatorie indipendenti ed identicamente distribuite (i.i.d.) di lunghezza che tende ad infinito, non è possibile comprimere i dati in un messaggio più corto dell’entropia totale senza rischiare di perdere informazione. Al contrario, compressioni arbitrariamente vicine al valore di entropia sono possibili, con probabilità di perdita di informazione piccola a piacere (a patto di inventarsi un codice molto buono!). Un’altra possibile formulazione di questo teorema può essere: qualunque codice univocamente decodificabile applicato ai simboli Xn di una sorgente stazionaria ha lunghezza media non inferiore all’entropia della 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 disuguaglianza di Kraft deve quindi per forza essere rispettata). Possiamo scrivere, usando le definizioni: H ( X ) − E [l ( x )] =

1

1

∑ p (x) log p (x) − ∑ p (x) l (x) = ∑ p (x) log p (x) − ∑ p (x) x

x

x

x

2− l ( x )

[

1 = ∑ p ( x ) log = ∑ p ( x ) log ⩽ log2 e ∑ p ( x ) p (x) p ( x ) 2l ( x ) x x x

log2 2l ( x) | {z }

=

=l ( x ) Che trucco!

2− l ( x ) p (x)

]

−1

Dove nell’ultimo passaggio abbiamo usato la disequazione log2 x ⩽ ( x − 1) log2 e

(2.17)

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

26

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

27

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

z ⎛

}|

] ⎜ ( ) 2− l ( x ) ⎜ log2 e ∑ p ( x ) − 1 = log2 e ∑ 2−l (x) − p ( x ) = log2 e ⎜ p x ⎝ ( ) {z } | x x [

⩾0

∑ 2− l ( x ) x

⎞{ ⎟ ⎟ −1⎟ ⩽ 0 ⎠

| {z }

⩽1 PER KRAFT!

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

1 1 1 ⩽ l ( x ) < log2 + 1 ⇒ p ( x ) l ( x ) < p ( x ) log2 + p (x) p (x) p (x) p (x)

Ora applichiamo l’operatore sommatoria: 1

∑ p (x) l (x) < ∑ p (x) log2 p (x) + ∑ p (x) x

|

x

{z

E[l ( x )]

}

|

x

{z

}

H (X)

| {z } 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 il seguente ESEMPIO:

Abbiamo una sorgente binaria che emette i due simboli in tabella 2.2. Secondo Shannon-Fano dovremmo 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 codicare sia x˜1 che x˜2 . p( x )

I (x)

l ( x ) (Shannon-Fano)

x˜1

0,1

3,32

4 (!!!)

x˜2

0,9

0,15

1

Tabella 2.2:

2.7

Caso sfortunato di Shannon-Fano

Codice di Huffman

Nel 1951 a David Huffman e ad un suo collega al corso del MIT di Teoria dell’Informazione venne data la scelta tra una tesi scritta o un esame. Il docente, Robert M. Fano, assegnò una tesi sul problema di trovare il codice binario più efficiente. Huffman, incapace di dimostrare un qualsiasi codice che fosse il più efficiente, si stava rassegnando all’idea di dover studiare per l’esame, quando gli venne l’idea di usare un albero binario ordinato in base alla frequenza, e così dimostrò velocemente che questo metodo era il più efficiente. Un’idea simile era stata usata in precedenza nella codifica di Shannon-Fano, ma Huffman sistemò la sua 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 (Un Metodo per la Costruzione di Codici a Ridondanza Minima), usa un metodo specifico per scegliere la 9 Bricconcello!

27

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

28

rappresentazione di ciascun simbolo ed è stato dimostrato che è il più efficiente sistema di compressione di questo tipo: nessun’altra mappatura di simboli in stringhe binarie può produrre un risultato più breve nel caso in cui le frequenze di simboli effettive corrispondono a quelle usate per creare il codice. Oggi la codifica di Huffman è spesso usata come complemento di altri metodi di compressione: sono esempi il Deflate (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 delle probabilità; 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 la lunghezza 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 {z

[ ( )] E l X (k)

⩽ }

Per k →∞ diventa H∞ ( X )

|

k {z

( ) H X (k)

( ) H X (k) + 1

<

k

=

k

+

1 k

(2.19)

}

Per k →∞ diventa H∞ ( X )

Il primo (entropia della sorgente) e il secondo termine (numero medio di bit per simbolo) vengono a coincidere; codificando i blocchi possiamo perciò avvantaggiarci della memoria del codice e avvicinarci sempre 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 )] E l X (k)

<

kH ( X ) 1 + k k

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

< H (X) +

H (X) ⩽

28

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

29

ESEMPIO:

Sorgente binaria senza memoria con la distribuzione di probabilità mostrata in tabella 2.3. L'entropia p( x ) x1 x2

Tabella 2.3:

0,1 0,9

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 codica simbolo-per-simbolo. . . La cosa è abbastanza deludente perché siamo ben lontani dall'entropia H ( X ), ma che succede se codichiamo supersimboli costituiti da due simboli 'elementari' (tabella 2.4)? p ( X (2) ) x1 x1 x1 x2 x2 x1 x2 x2

Tabella 2.4:

0,01 0,09 0,09 0,81

Distribuzione di probabilità del nostro esempio, con supersimboli

Ora possiamo costruire il nostro alberino post-natalizio con il metodo di Human (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 codica 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 pixel bianchi e neri, può convenire una codifica delle lunghezze di tali corse (magari secondo Huffman) e dell’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 vengono per questo chiamati codici entropici, visto che l’entropia è matematicamente calcolabile a partire dalla distribuzione di probabilità). Un codice universale che non richiede tale conoscenza statistica, dando 29

CAPITOLO 2. CODIFICA DI SORGENTI DISCRETE

30

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 è infatti utilizzato nella codifica delle immagini in formato GIF (e, facoltativamente, nei file TIFF) ed è il risultato delle modifiche apportate nel 1984 da Terry Welch ai due algoritmi sviluppati nel 1977 e nel 1978 da Jacob Ziv e Abraham Lempel, e chiamati rispettivamente LZ77 e LZ78. Funziona costruendo un dizionario nel quale 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 una cifra binaria (1 oppure 0). Successivamente si codificano le frasi con parole di lunghezza fissa, che indicano la posizione in binario della frase precedente seguita dal nuovo bit della sorgente. Si può dimostrare che 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 codicabile 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 signicativo, 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 0000 0001 0010 0011 0100

| | | | | |

Frase nel dizionario 1 0 10 11

| | | | | |

Codeword 0000 1 0000 0 0001 0 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’informazione: vengono quindi chiamati codici lossless, ovvero senza perdita. Esistono tuttavia anche tecniche di codifica lossy (JPEG, MP3) le quali comprimono moltissimo e - in sostanza - si basano sulla legge dei grandi numeri10 . Per esempio, consideriamo una sorgente binaria con probabilità p{ x = 1} = 90% e p{ x = 0} = 10%: guardando lunghissime sequenze potremo molto probabilmente constatare la presenza di (circa) un 90% di ’1’ e un 10% di ’0’. Ipotizziamo inoltre di considerare n-ple di 1000 bit: le parole possibili 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 di tutte le 21000 parole possibili e codificare soltanto quelle. Così facendo risparmieremmo tantissimi bit in quanto dovremmo codificare un numero molto piccolo di sequenze se confrontato con tutte quelle possibili; l’altra faccia della medaglia è l’incapacità di codificare tutte le sequenze, con la conseguente perdita di informazione. Tale perdita d’informazione è assolutamente inevitabile se abbiamo delle sorgenti continue: prima di poterle codificare dovrò campionarle e questo genererà un errore di quantizzazione impossibile da recuperare. 10 La legge dei grandi numeri, detta anche legge empirica del caso oppure teorema di Bernoulli (in quanto la sua prima formulazione è dovuta a Jakob Bernoulli), descrive il comportamento della media di una sequenza di n variabili casuali indipendenti e caratterizzate dalla stessa distribuzione di probabilità (n misure della stessa grandezza, n lanci della stessa moneta ecc.) al tendere ad infinito della numerosità della sequenza stessa (n). In altre parole, grazie alla legge dei grandi numeri, possiamo fidarci che la media 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 al Lidl) non vi sarà più molta ridondanza all’uscita. Non abbiamo però finito il lavoro: dobbiamo trasportare questi bit a destinazione! Purtroppo il canale che tali bit dovranno attraversare è tutt’altro che ideale e favorisce 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 sappiamo cosa 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 solo un simbolo alla volta, senza dover specificare l’indice temporale nelle varie formule in cui compare l’operatore di probabilità: per questo, considerando lo schema in figura 3.1, possiamo ad esempio dire che Yk dipenderà soltanto da Xk e da nessun’altro simbolo. Volendo, possiamo graficare la probabilità che un certo simbolo X generi il relativo Y in uscita dal canale facendo uso di un grafo bipartito, dove ad ogni freccia sono associate delle probabilità (vedi figura 3.2). Tutte le probabilità di transizione dal nodo generico i al nodo generico j possono perciò essere poste in una matrice P, detta matrice di transizione, i cui elementi saranno molto semplicemente { } pij = p Y = y j ∣ X = xi (3.1) Supponiamo di conoscere solamente la P di una certa sorgente: trasmettiamo i nostri simboli X attraverso il canale e vediamo che accade alle Y. Ebbene, si può dimostrare che si ha una riduzione di incertezza legata all’osservazione del canale: H ( X ∣Y ) ≤ H ( X )

(3.2)

Tale riduzione di incertezza1 può essere quantificata con un parametro che chiameremo informazione mutua: I ( X; Y ) = H ( X ) − H ( X ∣Y ) (3.3) Com’è facile accorgersi, questo parametro viene quantificato in Shannon per simbolo. Inoltre, soggiace alle seguenti proprietà: 1 Come

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

31

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

32

Figura 3.2:

Figura 3.3:

Il grafo bipartito

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. Ma come facciamo a quantificare tale capacità per i nostri canali? Semplice: con la capacità di canale2 ! Tale parametro è pari a: C = max I ( X; Y ) (3.4) p( x )

Provando a dare in pasto al canale più informazione rispetto alla sua capacità inevitabilmente perderemo qualcosa: la capacità è infatti un metro di misura per la massima quantità di informazione che possiamo 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à: ogni nodo j (d’ingresso) del grafo bipartito finisce in un nodo i con probabilità 1, quindi non sono possibili 2 Gioco

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 = max I ( X; Y ) = max H ( X ) = log2 N (Ottenuta con distribuzione uniforme) p( x )

p( x )

(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: ⎡ ⎤ ℋ( p) ℋ( p) z }| { z }| { ⎢ ⎥ I ( X; Y ) = H ( X ) − ( X ∣Y ) = H ( X ) − ⎣ p (y1 ) p ( X ∣Y = y1 ) + p (y2 ) p ( X ∣Y = y2 )⎦ = H ( X ) − ℋ( p) |

{z

Caso della variabile bernoulliana!

} (3.7)

Ora siamo pronti a ricavare anche la capacità: C = max I ( X; Y ) = max [ H ( X ) − ℋ ( p)] = 1 − ℋ ( p) (Ottenuta con bit d’ingresso equiprobabili) (3.8) p( x )

p( x )

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 valori si cancellino (erasure). Il caso tipico in cui questa schematizzazione è valida è quello della trasmissione dei pacchetti agli alti livelli della pila OSI; in generale si avrà un campo che serve a controllare l’integrità di tali 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 = y 1 ) | {z }

=0 (il risultato è certo: x1 )

+ p ( y2 )

H ( X ∣Y = y 2 ) | {z }

=0 (il risultato è certo: x2 )

+ p (e)

stessa prob. per x1 e x2

⎤

z }| { H ( X ∣Y = e ) {z } |

⎥ ⎦

=1: caso di massima incertezza

(3.9) 33

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

34

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 ) + p ( e ∣ x2 ) p ( x2 ) = q ⎝ p ( e ∣ x1 ) + p ( e ∣ x1 ) ⎠ = q | {z } | {z } | {z } =q

=q

=1

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 = max[ H ( X ) − q] = 1 − q Ottenuta con ingressi equiprobabili p( x )

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

(3.11)

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

Figura 3.7:

35

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 = x 1 ) p ( x 1 ) + H (Y ∣ X = x 2 ) p ( x 2 ) = H (Y ∣ X = x 2 ) p ( x 2 ) = π ℋ ( p ) | {z } {z } | {z } | =0, no incertezza!

=ℋ( 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 ) p ( x1 ) + p ( y2 ∣ X = x2 ) p ( x2 ) = (1 − p ) π {z } | {z } | {z } | =1− p

=0 (impossibile)

=π

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 funzione tramite 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: 1−x d ℋ ( x ) = log2 dx x Otteniamo: ∂ 1 − π (1 − p ) − ℋ ( p) = 0 (ℋ [(1 − p)π ]) − ℋ( p) = (1 − p) log2 ∂π π (1 − p ) 35

(3.12)

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

36

Portando di là dall’uguale il termine ℋ( p) ed elaborando ancora: 1 − π (1 − p ) ℋ ( p) (1 − p) log2 π (1 − p ) ( ) 1 − π (1 − p ) − (1 − p) log2 (1 − p) = − p log2 p − (1 − p) log2 (1 − p) (1 − p) log2 π {z } | ℋ( p)

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

)

Uguagliando gli argomenti dei logaritmi: p 1 − π (1 − p ) − = p 1− p π

−

p

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

Figura 3.8:

3.2.5

Capacità del canale Z in funzione della probabilità p

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 = x 1 ) p ( x 1 ) + H (Y ∣ X = x 2 ) p ( x 2 ) = π ℋ ( p ) + ( 1 − π ) ℋ ( q ) | {z } | {z } | {z } | {z } ℋ( p)

π

ℋ(q)

36

1− π

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

Figura 3.9:

37

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 ) p ( x1 ) + ( y1 ∣ X = x2 ) p ( x2 ) = (1 − p ) π + (1 − π ) ε {z } | {z } | {z } | {z } | 1− p

π

1− π

ε

Di conseguenza: H (Y ) = ℋ[(1 − p)π + (1 − π )ε] Quindi, rimettendo insieme i cocci, si ha: I ( X; Y ) = ℋ [π (1 − p) + (1 − π ) ε] − (π ℋ ( p) + (1 − π ) ℋ (ε)) | {z } | {z } H (Y ∣ X )

H (Y )

Ora vogliamo trovare il massimo di questa funzione, visto che ci servirà per trovare il massimo dell’informazione mutua e quindi la capacità: per trovare il massimo sfruttiamo le ben note derivate e scriviamo ∂ f (π, p, ε) = 0 ∂π 1 − π (1 − p ) − ε (1 − π ) −ℋ ( p) + ℋ (ε) = 0 [(1 − p) − ε] log2 π (1 − p ) + ε (1 − π ) {z } | d 1− x d x ℋ( x )=log2 x

1 − π (1 − p ) − ε (1 − π ) ℋ ( p) − ℋ (ε) = π (1 − p ) + ε (1 − π ) (1 − p ) − ε ℋ( p)−ℋ(ε) 1 − π (1 − p ) − ε (1 − π ) = 2 (1− p)−ε ≜ γ ( p, ε) π (1 − p ) + ε (1 − π ) log2

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à del canale 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 il risultato va a coincidere con il BSC. 37

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

38

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 x3 Q = 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 = max I ( X; Y ) = max{ H (Y ) − H (Y ∣ X )} Q

Q

Il secondo addendo può essere sviluppato nel seguente modo: H (Y ∣ X ) = H (Y ∣ X = x1 ) p ( x1 ) + H (Y ∣ X = x2 ) p ( x2 ) + H (Y ∣ X = x3 ) p ( x3 ) = 2Qℋ ( p) {z } | {z } {z } | | =0

no incertezza

=ℋ( p)

=ℋ( p)

Ora passiamo al primo addendo, che è risaputamente più complicato: H (Y ) = − p (y1 ) log2 p (y1 ) − p2 log2 p (y2 ) − p (y3 ) log2 p (y3 ) = − p (y1 ) log2 p (y1 ) − 2Qlog2 Q | {z } | {z } =Q

=Q

La probabilità p(y1 ) sarà: p (y1 ) = p (y1 ∣ X = x1 ) p ( x1 ) + p (y1 ∣ X = x2 ) p ( x2 ) + p (y1 ∣ X = x3 ) p ( x3 ) = p ( x1 ) = 1 − 2Q | {z } {z } {z } | | evento certo ( = 1)

impossibile! ( = 0)

impossibile! ( = 0)

Sostituendo: H (Y ) = − p (y1 ) log2 p (y1 ) − 2Qlog2 Q = − (1 − 2Q) log2 (1 − 2Q) − 2Qlog2 Q

Ora possiamo ricavare l'espressione generale dell'informazione mutua: I ( X; Y ) = H (Y ) − H (Y ∣ X ) = − (1 − 2Q) log2 (1 − 2Q) − 2Qlog2 Q − 2Qℋ ( p)

Ricordando ora la relazione notevole

1 d log x = dx 2 x ln 2 possiamo calcolare la derivata dell'informazione mutua al ne di ricavare il massimo di quest'ultima: d d I ( X; Y ) = {− (1 − 2Q) log2 (1 − 2Q) − 2Qlog2 Q − 2Qℋ ( p)} = dQ dQ

= (1 − 2Q)

2 1 + 2log2 (1 − 2Q) − 2Q − 2log2 Q − 2ℋ ( p) = Q ln 2 (1 − 2Q) ln 2

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

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

39

Semplicando e riordinando:

log2 (1 − 2Q) − log2 Q − ℋ ( p) = 0 1 − 2Q = ℋ ( p) log2 Q 1 − 2Q 1 = 2ℋ( p) ≜ β ( p) ⇒ Q = Q 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) − 2Qlog2 Q − 2Qℋ ( p) = ) ( ) 1 1 1 1 1 = − 1−2 log2 1 − 2 −2 log2 −2 ℋ ( p) = 2+β 2+β 2+β 2+β 2 + β | {z } (

≜log2 β

( ) β 2 1 2 β log2 − log2 − log2 β = =− 2+β 2+β 2+β 2+β 2+β ( ( )β )2 β 1 1 1 1 log2 log2 log2 β2 = =− − − 2+β 2+β 2+β 2+β 2+β [ ] ( )β ( )2 1 β 1 2 =− log2 + log2 + log2 β = 2+β 2+β 2+β [ ( ( )β )2 ] ( ) 2+ β β 1 2+β 1 β β + log2 =− = log2 =− log2 log2 2+β 2+β 2+β 2+β 2+β β

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 blocchi di 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 (Y1 Y2 Y3 . . . Yn ∣ X1 X2 X3 . . . Xn ) −−−−−−−−−−−−−−−−−−−−−−→ usiamo la regola della catena (chain rule)

→ H (Y1 ∣Y2 . . . Yn X1 . . . Xn ) + H (Y2 ∣Y3 . . . Yn X1 . . . Xn ) + . . . + H (Yn ∣ X1 . . . Xn ) = ⎛ ⎞ n = ∑ H ⎝Yi Yi−1 Yi−2 . . . Y1 X1 . . . Xn ⎠ | {z } i =1 tocca tenercele!

Siccome tuttavia il canale è senza memoria, la generica variabile aleatoria Yi dipende solo dalla Xi quindi possiamo riscrivere l’ultima sommatoria in questa maniera: ⎛ ⎞ n n ∑ H ⎝Yi Yi−1 Yi−2 . . . Y1 |X1 .{z. . Xn} ⎠ = ∑ H (Yi ∣Xi ) i =1 i =1 tocca tenercele!

39

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

40

Ora invece soffermiamoci sull’altro addendo: anche in questo caso possiamo sfruttare l’ipotesi di assenza di memoria e i calcoli si rivelano abbastanza semplici. ( ) H Y (n) = H (Y1 Y2 Y3 . . . Yn ) ⩽ ∑ H (Yi ) i

Mettendo insieme gli ingredienti: ( ) I X (n) ; Y (n) ⩽ ∑ H (Yi ) − H (Yi ∣ Xi ) = i

3.4

n

∑

i =1

I ( Xi ; Yi ) } | {z

⩽ nC

ciascun termine ⩽C

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 in realtà non la stiamo aumentando: anzi, al massimo possiamo perderne! Si ha infatti: I ( X; Z ) ≤ I (Y; Z ) I ( X; Z ) ≤ I ( X; Y ) Dimostrazione:

(3.14)

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 e guardando 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, infiliamo un blocchetto decisore nella catena. Tale elemento funziona secondo alcuni criteri che per semplicità 40

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

41

considereremo alla stregua di una certa funzione g(). Chiameremo xˆ il simbolo che il decisore ha stimato per X in un certo istante: chiaramente il DMC può aver indotto degli errori e quindi non sempre accadrà ˆ Sia quindi che x = x. 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 𝒳 che si riferisce ai simboli che trasmettiamo. Dimostrazione: chiamiamo E la variabile aleatoria ’errore’, la quale si rivela essere una variabile bernoulliana con probabilità Pe { 1 se xˆ ∕= x (Errore) ⇒ P ( E = 1) = Pe 0 se xˆ = x (No errore) 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 Y 3 equivale a conoscere Xˆ (grazie al decisore): se conosciamo sia X che Xˆ sappiamo con certezza 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 regole di 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 senza nessuna informazione. Inoltre possiamo sviluppare H ( X ∣ E, Y ), cioè l’altro addendo: H ( X ∣ E , Y ) = H ( X ∣ E = 1 , Y ) p ( E = 1) + H ( X ∣ E = 0 , Y ) p ( E = 0) | {z } | {z } 1− Pe

Pe

Possiamo tuttavia eliminare il termine H ( X ∣ E = 0 , Y ) p ( E = 0) in quanto se qualcuno ci dice che non vi è 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 siamo al corrente della presenza di un errore, ma non sappiamo quale scegliere fra gli Nx − 1 altri elementi dell’alfabeto 𝒳 . 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 ) = H ( X ∣ E , Y ) + H ( E ∣Y ) ⩾ ℋ ( Pe ) + Pe log2 ( Nx − 1) {z } | {z } | {z } | =0

⩾ Pe log2 ( Nx −1)

⩾ℋ( Pe )

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

41

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

42

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 = max [ I ( X; Y )] = max [ H ( X ) − H ( X ∣Y )] ⇒ C ⩾ H ( X ) − H ( X ∣Y ) p( x )

p( x )

(3.17)

H ( X ) ⩽ C + H ( X ∣Y ) ⩽ C + ℋ ( Pe ) + Pe log2 ( Nx − 1) Ecco trovato, in funzione di C, un bound superiore per l’entropia H ( X ). Anche qui possiamo dare un’interpretazione grafica di quanto trovato (vedi figura 3.15): notiamo che non possiamo immettere troppa informazione nel canale se vogliamo lavorare nella zona cerchiata di rosso, dove si sbaglia poco (Pe piccola o - meglio ancora - nulla). Possiamo certo provare a spedire più informazione (aumentare H ( X )), ma a patto 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 è in telecomunicazioni il processo volto a garantire la trasmissione ottimale di un messaggio, trasmesso attraverso 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 che ogni supersimbolo sia un vettore di k bit (cardinalità dell’alfabeto d’ingresso: L = 2k ), che w sia uno degli 4 Di

seguito riporto un mio tentativo di calcolo del massimo, tutto da verificare: { } 1 1 ∂ pe log2 + (1 − pe ) log2 + pe log2 ( N − 1) = ∂pe pe (1 − p e )

= log2

1 pe 1 1 (1 − p e ) + pe − log2 + (1 − p e ) + log2 ( N − 1) + pe = pe ln 2 ln 2 (1 − p e ) ( N − 1) ln 2

= log2

1 − pe p2 1 (1 − p e )2 + e + + log2 ( N − 1) + pe = pe ln 2 ln 2 ( N − 1) ln 2

pe (1 − pe ) ( N − 1) 2p2e − 2pe + 1 + + = pe ln 2 ( N − 1) ln 2 ( 2 ) 2pe − 2pe + 1 ( N − 1) + pe (1 − p e ) ( N − 1) = log2 + pe ( N − 1) ln 2

= log2

5 Se

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

42

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

Figura 3.15:

43

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: log2 L H (W ) = = Rc n n

(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-ple e, se è ben fatto, farà in modo di rendere il più possibile distanti6 (cioè differenti) in modo da minimizzare ˆ stimata al ricevitore, sia errata. Tale probabilità verrà di seguito indicata con la probabilità che la W, ˆ ∕= W ) p e = p (W

(3.19)

Mentre quella di seguito è la probabilità d’errore condizionata dal fatto che sappiamo quale vettore è stato inviato: ˆ ∕ = W ∣W = w i ) p e ∣ i = p (W (3.20) Definiamo inoltre la massima probabilità di errore: λ = max pe∣i i

(3.21)

Il criterio con il quale il codificatore effettua il mapping dei vettori dipende dal codice 𝒞 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). 6 Nel

senso di Hamming.

43

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

44

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 canale di comunicazione sia affetto da rumore, è possibile trasmettere dati (informazioni) con probabilità di errore piccola a piacere fino ad una frequenza massima7 attraverso il canale stesso. Questo sorprendente risultato fu presentato per la prima volta da Claude Shannon nel 19488 e, sostanzialmente, descrive la massima possibile efficienza di un qualunque metodo di correzione degli errori in funzione del livello di rumore. La teoria non spiega come costruire un codice ottimo, ma stabilisce solo quali siano le prestazioni di tale codice ottimo9 . Formalizzando matematicamente, il teorema sostiene che

∀ε > 0, Rc =

log2 L < C ∃ Codice 𝒞 : Pe < ε per n sufficientemente elevato n

(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: ) ( ℋ ( Pe ) log2 L ⩽ H W Y (n) + nC ⩽ | {z }

+

incertezza: è avvenuto un errore?

Pe log2 ( L − 1) | {z }

+nC

c’è errore: incertezza sui rimanenti L−1 simboli

Proseguendo con la catena di disuguaglianze:

ℋ ( Pe ) + Pe log2 ( L − 1) + nC ⩽ 1 + P2 log2 ( L − 1) + nC < 1 + Pe log2 L + nC | {z } ⩽1

Rimettiamo insieme i pezzi: ( ) log2 L ⩽ H W Y (n) + nC < 1 + Pe log2 L + nC Se ora dividiamo per n otteniamo: log2 L 1 + Pe log2 L + nC 1 = Rc < = + Pe Rc + C n n n 7 La capacità di Shannon, nota anche come limite di Shannon, di un canale di comunicazione è il massimo tasso di trasferimento di dati che può fornire il canale per un dato livello di rapporto segnale/rumore, con un tasso di errore piccolo a piacere. 8 Shannon diede solo una traccia della dimostrazione. La prima dimostrazione rigorosa è dovuta a Amiel Feinstein nel 1954. 9 Utilizzando 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. 10 Si ricorda che C si riferisce al singolo simbolo!

44

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

45

Mandando Pe a 0 e imponendo n ≫ 1 Rc <

1 + Pe Rc + C ⇒ Rc < C n

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 che Pe → 0, ma manteniamo l’ipotesi n ≫ 1: otteniamo Rc > Pe Rc + C da cui Pe > 1 −

Figura 3.17:

C Rc

(3.23)

(3.24)

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 codice), 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 che in 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 a causa di fenomeni fisici come il rumore gaussiano. Per una variabile continua la densità di probabilità è una funzione continua tale per cui (vedi figura 3.18):

p ( a ⩽ x ⩽ b) =

∫b

p X ( x ) dx

(3.25)

a

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

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

46

Figura 3.18:

Densità di probabilità di una variabile aleatoria continua

valor medio: si assegna in pratica al generico campione xˆ n la seguente probabilità P ( xˆ n ) = ∆ ⋅ p X ( xi ) =

∫

p X ( x ) dx ⇒

∑ p (xˆi ) = 1

(3.26)

i

∆

cosicché, come indicato, la sommatoria delle probabilità associate a ciascun campione restituisca esattamente 1. Il teorema del punto medio ci garantisce che il rettangolino di larghezza ∆ su cui integriamo avrà la stessa area della funzione calcolata nell’intervallo (P ( xˆ n ) = ∆ ⋅ p X ( xi )). Calcoliamo ora l’entropia ˆ della nostra variabile aleatoria ’discretizzata’ X: ( ) ∆ ⋅ p (x ) H Xˆ = − ∑ P ( xˆi ) log2 P ( xˆi ) = − ∑ log2 (∆ ⋅ p ( xi )) = | {z i } i i teorema valor medio

= −∆ ∑ px ( xˆi ) log2 p ( xi ) − ∆ ∑ p ( xi ) log2 ∆ = i

i

|

{z

=1

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

i

} ∫∞

p ( xi ) log2 p ( xi )

−∞

|

+ |{z} ∞ !??!!

{z

}

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 anche perché 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) ≜

∫∞ −∞

1 p ( x ) log2 dx = p (x)

∫∞

p ( x ) log2 p ( x ) dx

(3.27)

−∞

Tale parametro ci dà un’indicazione di quanto sia random la nostra variabile aleatoria. Chiaramente esistono anche. . . 1. l’entropia differenziale congiunta: h ( x, y) = −

∫∫

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

R2

46

(3.28)

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

47

2. l’entropia differenziale condizionata: h ( x ∣y ) = −

∫∫

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

(3.29)

R2

L’entropia differenziale condizionata è sicuramente minore o uguale dell’entropia condizionata semplice11 . ESEMPIO:

Calcoliamo l'entropia dierenziale per la variabile X uniformemente distribuita su [ a, b]: h (X) = −

∫

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

x

∫b a

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

ESERCIZIO:

Dimostrare che si ha la seguente relazione per la distanza di Kullback-Leiber 12 : −

∫

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

∫

p ( x ) log2 q ( x ) dx ∫∞

cioè che (distanza di Kullback-Leiber) →

p ( x ) log2

−∞

q (x) dx ⩽ 0 p (x)

(3.30)

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

p ( x ) log2

q (x) dx ⩽ log2 e p (x)

∫∞

[ p (x)

−∞

−∞

] q (x) − 1 dx = 0 p (x)

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

3.9.1

Teorema: la distribuzione uniforme ha entropia massima (caso intervallo limitato)

Vogliamo dimostrare che h( 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. ∫ ∫ 1 1 p ( x ) log2 dx ⩽ p ( x ) log2 dx p (x) q (x) Se p( x ) è una distribuzione generica e q( x ) quella uniforme si ha: hgenerica ( X ) = 11 Dimostrazione

∫

p ( x ) log2

1 dx ⩽ p (x)

∫

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

∫

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

di mio pugno e senza pretese di correttezza:

−

∫ ∫

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

x y

∫

p ( x ) log2 p ( x ) dx

x

p (y) dxdy ⩽ p ( x, y) log2 p ( x ) dxdy p ( x, y) x y x y ( ) ( ) ∫ ∫ ∫ ∫ p (y) p ( x ) p (y) p ( x ) dxdy ⩽ − log2 e p ( x, y) − 1 dxdy = 0 − p ( x, y) log2 p ( x, y) p ( x, y)

−

∫ ∫

∫ ∫

p ( x, y) log2

x y

x y

12 Questa

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

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

48

3.9.2

Teorema: la distribuzione gaussiana ha entropia massima (caso intervallo illimitato)

Rimuoviamo ora l’ipotesi di intervallo finito [ a,√ b] e estendiamoci da −∞ a +∞. Allora in tal caso la distribuzione avente entropia massima (pari a log2 2πσ2 e) è quella gaussiana e si ha:

√ h( X ) < log2

2πσ2 e

(3.32)

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

hgaussiana ( X ) = −

∫∞

−∞

√

log2 pgaussiana ( x ) dx =

pgaussiana ( x ) | {z } {

1

2πσ2

∫∞

exp −

(

( x − µ )2 2σ2

}

{

}) ( x − µ )2 pgaussiana ( x ) log2 √ =− exp − dx = 2σ2 2πσ2 −∞ ( { }) ] [ ∫∞ 1 ( x − µ )2 + ln exp − ⋅ log2 e dx = =− pgaussiana ( x ) ⋅ log2 √ 2 2σ2 2πσ −∞ [ ] ∫∞ √ ( x − µ )2 2 = pgaussiana ( x ) ⋅ log2 2πσ + ⋅ log2 e dx = 2σ2 1

−∞

√ = log2

∫∞

2πσ2

pgaussiana ( x ) dx +

−∞

{z

|

√ = log2

=1

2πσ2 +

log2 e 2σ2

}

∫∞

pgaussiana ( x ) ⋅ ( x − µ)2 dx =

−∞

{z

|

}

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

√ √ √ log2 e = log2 2πσ2 + log2 e = log2 2πσ2 e 2

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

h (X) =

∫

p ( x ) log2

1 dx ⩽ p (x)

∫

p ( x ) log2

1 dx q (x)

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

p ( x ) log2

1 dx ⩽ p (x)

∫

p ( x ) log2

1 dx pgaussiana ( x )

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

pgaussiana ( x ) log2

1 pgaussiana ( x )

√ dx = log2

2πσ2 e

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

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

3.9.3

49

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

Anzitutto calcoliamo l’entropia differenziale della distribuzione esponenziale negativa (s’intende che gli 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 +λ log2 e xp ( x ) dx = {z } | {z } | =1

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 ) generiche si ha: ∫ ∫ 1 1 h ( X ) = p ( x ) log2 dx p ( x ) log2 dx p (x) q (x) Quindi se scegliamo al posto di q( x ) la distribuzione esponenziale negativa, l’uguaglianza vale solo se p( x ) = q( x ) e si ha: ∫ 1 h ( X ) pesp - neg ( x ) log2 dx = hesp - neg ( X ) pesp - neg ( x )

49

50

CAPITOLO 3. LA CODIFICA DI CANALE E LA CAPACITÀ

50

Capitolo 4

Il limite di Shannon In questo capitolo tratteremo la parte più avanzata della Teoria dell’Informazione, soffermandoci sull’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 si possono 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 valor medio nullo e varianza σ2 così che possiamo scrivere Z ∼ 𝒩 (0, σ2 )

(4.1)

Visto che Y = X + Z, anche Y sarà (come Z) una variabile aleatoria caratterizzata da una distribuzione continua. All’interno di questo schema un vincolo è costituito dalla potenza del rumore e da quella del segnale che trasmettiamo, le quali dipendono dai seguenti momenti del second’ordine: [ ] E X 2 = 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 ) | {z }

√ −log2 2πeσ2

Dipende dalla v.a. Y

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

CAPITOLO 4. IL LIMITE DI SHANNON

52

√ 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 distribuzione gaussiana1 e si ha: ( ) {Y ∣ X = x (costante)} ∼ 𝒩 x, σ2

Ma l’entropia differenziale dipende solo dalla varianza: se √ effettuiamo una media sui valori di tutte le x otteniamo quindi un valor medio esattamente pari a log2 2πeσ2 . Calcoliamo ora la capacità, ovvero il massimo dell’informazione mutua; dovendo noi massimizzare la h(Y ), faremo l’ipotesi che anche la Y sia una variabile gaussiana imponendo che anche X lo sia, cosicché possiamo scrivere: √ √ √ 2πeσy2 σy2 √ σy2 1 C = max I ( X; Y ) = log2 2πeσy2 − log2 2πeσ2 = log2 √ = log2 √ = log2 2 2 σ p( x ) 2πeσ2 σ2 Se facciamo l’ipotesi (ragionevole) che rumore e segnale utile facciano capo a due variabili indipendenti ed entrambe gaussiane, allora la varianza di Y = X + Z è uguale alla somma delle varianze di X e Y: ) ( σy2 1 1 1 σx2 + σ2 σx2 C = max I ( X; Y ) = log2 2 = log2 = log2 1 + 2 2 2 2 σ σ2 σ p( x ) Possiamo ora esprimere la varianza σx2 in funzione dei nostri vincoli, dato che si ha [ ] σx2 = E X 2 − E2 [ X ] Volendo noi massimizzare σx2 , cioè la potenza del segnale utile, l’unica è annullare E2 [ X ]. Così facendo otteniamo: (4.2) σx2 = E[ X 2 ] = S Sostituendo nella formula della capacità di canale otteniamo: ( ) 1 S C = log2 1 + 2 N

(4.3)

S Provando a graficare la capacità in funzione del rapporto segnale-rumore N 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

( ) S/N (dB) grande S/N (dB) S/N (dB) S/N (dB) S S S 1 1 = 10 10 ⇒ C = log2 1 + 10 10 −−−−−−−−−→ C = log2 10 10 (dB) = 10log10 ⇒ N N N 2 2 1 Attenzione: Y di per sé non è gaussiana. Lo è soltanto se consideriamo un valore costante di X che chiamiamo x, in quanto sommando una costante ad una qualsiasi variabile aleatoria gaussiana otteniamo un’altra variabile aleatoria gaussiana, ma con un valor 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=

S/ (dB) S/N (dB) 1 log2 10 10 = N log2 10 2 20

1 log2 10; la cattiva notizia è invece che 20 la capacità cresce logaritmicamente con il rapporto S/N. Peccato: è una crescita piuttosto lenta. . .

Dunque la retta tratteggiata in figura 4.2 ha coefficiente angolare

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 additivo gaussiano bianco e quindi riceve un contributo di rumore n(t). Per ipotesi supporremo la banda limitata tra − 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

〈 〉 Ergodicità [ ] = E X 2 (t) Gx ( f ) d f = S = x 2 ( t )

−B

Considerazioni analoghe possiamo farle per il rumore: ∫B

] 〈 〉 [ Ergodicità = Gn ( f ) d f = N = n2 (t) = N0 B = σ2 E n2 ( t )

−B

Ora serviamoci della nostra arma segreta: il teorema del campionamento! Esso, ci ricordiamo, afferma che si ha reversibilità nella conversione A/D se la frequenza di campionamento f s è almeno il doppio della banda del segnale B: (4.4) f s ≥ 2B 53

CAPITOLO 4. IL LIMITE DI SHANNON

54

Scegliamo esattamente la frequenza f s = 2B e campioniamo il nostro segnale all’interno di una finestra ˜ Otteniamo perciò, con un periodo pari a 1/ f s , dei campioni che andremo a raccogliere nei temporale T. vettori x, y, n: ognuno di questi vettori conterrà 2B T˜ campioni x− = x1 , x2 , . . . , x2BT˜ y = y1 , y2 , . . . , y2BT˜ −

n ˜ − = n1 , n2 , . . . , n2B T Sul singolo istante di campionamento si ha: yi = xi + ni Sia xi che ni sono campioni di processi ergodici: [ ] [ ] 〈 〉 E xi2 = E x2 (ti ) = x2 (t) = S ( ) [ ] ni = 𝒩 0, σ2 ⇔ N = σ2 = E n2i Si noti che, come indicato, ni è il campione una variabile aleatoria gaussiana. Nonostante vengano trasmessi dei vettori, ha comunque senso calcolare la capacità simbolo per simbolo in quanto si dimostra che gli 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 ragionare campione per campione. Ricordando dal paragrafo 4.1 che la capacità (in Shannon per campione) è ( ) S 1 C = log2 1 + 2 N allora avremo, in Shannon per vettore (cioè in Shannon per T˜ secondi) ( ) ( ) S S 1 = B T˜ log2 1 + C = 2B T˜ log2 1 + 2 N N e, nell’unità di tempo (Shannon/secondo), ( ) S C = B log2 1 + N

(4.5)

Quest’ultima relazione (4.5) viene chiamata formula di Hartley-Shannon: portando la B a denominatore della C otteniamo una relazione ( ) ( ) C S S = log2 1 + = log2 1 + B N N0 B che può essere facilmente graficata come mostrato in figura 4.5. Purtroppo, come si nota, anche qui emerge che la capacità aumenta logaritmicamente con il rapporto segnale-rumore (SNR). Se fissiamo ora S e N0 2 possiamo provare a mandare al limite B → ∞: la capacità C in tal caso tende a ( C = lim Blog2 B→∞

S 1+ N0 B

)

(

= lim log2 B→∞

S 1+ N0 B

)B

S S LIMITE NOTEVOLE −−−−−−−−−−− → lim log2 e N0 = log2 e x α N B→∞ 0 lim (1+ x ) =eα x →∞

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 limite invalicabile! 2 Si

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

54

CAPITOLO 4. IL LIMITE DI SHANNON

Figura 4.5:

4.2.1

55

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

Incorrelazione del rumore

Il generico ni è stato ottenuto campionando n(t), rumore bianco avente banda tra − B e B, su T˜ e con frequenza f s = 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 i campioni sono incorrelati calcolando il seguente valor medio ] ( ) [ [ ] E ni n j i ∕= j = E ni ( ti ) n j ( ti ) i ∕= j ≜ R n ti − t j

funzione di autocorrelazione del processo di rumore

La nostra funzione Rn , come sappiamo da Comunicazioni Elettriche LB, è una sinc avente forma: Rn (τ ) = BN0 sinc(2Bτ ) La distanza temporale fra un campione e l’altro sarà di tale distanza. Possiamo quindi scrivere:

1 2B

dunque ti − t j sarà sicuramente un multiplo intero

ti = i ⋅ TS =

) ( R n ti − t j = R n

(

i−j 2B

)

(4.6)

i 2B

( ) i−j = N sinc 2B =N 2B

sinc (i − j) | {z }

=0

sinc di un numero intero→0

Dunque fra campioni non c’è correlazione: questo implica che siano indipendenti! Si noti che ciò è legato a due ipotesi: 1. il rumore è bianco (sennò addio antitrasformata!); 2. il campionamento è esattamente a frequenza f s = 2B. Come sappiamo l’informazione trasmessa dipende dall’entropia ed essa è tanto maggiore quanto i campioni sono imprevedibili: il massimo risultato si ha quindi nel caso di campioni xi indipendenti. Se dunque prendiamo un segnale utile molto simile al rumore (cioè gaussiano, visto che la distribuzione gaussiana massimizza l’entropia), e dunque abbiamo indipendenza statistica fra i campioni, massimizziamo l’informazione per il canale AWGN (Additive White Gaussian Noise). Lo strumento con il quale rendere i campioni meno ridondanti possibili, lo sappiamo, è il codificatore di sorgente mentre, per proteggere l’informazione dai disturbi del canale, c’è il codificatore di canale. Ora possiamo quindi parlare di un sistema di trasmissione completo, come mostrato in figura 4.6; se lo osserviamo ai morsetti della nuvoletta tratteggiata vediamo dei simboli in ingresso bn e dei simboli in uscita bn′ : se la rate dei bn è inferiore alla capacità di canale allora Shannon ci garantisce che esisteranno dei codici coi i quali è possibile rendere arbitrariamente 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 la capacità di un sistema? Riusciamo ad avere un limite di riferimento per capire quanto più in là possiamo spingerci in questa sistematica riduzione di Pe ? 55

CAPITOLO 4. IL LIMITE DI SHANNON

56

Figura 4.6:

4.3

Sistema di trasmissione completo

Il limite di Shannon

Sappiamo che la capacità vale: ) ( ) ( S S C = Blog2 1 + = Blog2 1 + N N0 B Se l’energia per bit di sorgente spedito è Eb abbiamo che la potenza del segnale è pari a S = Eb ⋅ Br =

Eb Tb

(4.7)

dove Tb è il tempo di bit. ( C = Blog2 Il termine

Eb N0

E Br 1+ b N0 B

)

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

per bit trasmesso; il termine BBr = η, 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 di sotto della capacità (non vorremo mica perdere informazione nel canale, vero?) otteniamo: ( ) ( ) E Br Br E Br < C = Blog2 1 + b ⇒η= < log2 1 + b η N0 B B N0 E 2η < 1 + b η N0 2η − 1 Eb > N0 η 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: 2η − 1 Limite notevole = ln 2 ≃ 0, 69 ≃ −1, 6 dB η η →0 lim

56

(4.8)

CAPITOLO 4. IL LIMITE DI SHANNON

57

Fissata la potenza per bit trasmesso, non è possibile andare oltre una certa efficienza spettrale (vedi figura 4.7) ma, cosa ancor più importante, fissata l’efficienza spettrale non è possibile trasmettere a meno di una certa potenza (vedi figura 4.8). Non sarà inoltre mai possibile, neanche con il codificatore di canale più furbo del mondo, trasmettere in maniera corretta un’informazione con un rapporto segnale rumore inferiore a −1, 6 dB. . . e già ci va grassa perché significa che, comunque, possiamo correttamente comunicare 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 buona quantità di potenza ma non si ha molta banda, quindi bisogna fare in modo di aumentare al massimo l’efficienza spettrale (parte in alto a destra del grafico); ∙ quella dei sistemi limitati in potenza (esempio: le sonde dello spazio profondo) → abbiamo un’autonomia limitata (non possiamo assolutamente sprecare energia) tuttavia non abbiamo problemi di banda (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 simboli antipodali: 0′′ → +1 → x (t) (4.9) 1′′ → −1 → − x (t) Immaginiamo inoltre che la forma d’onda x (t) sia ∈ R e consista in una semplice rect: ( ) t x (t) = rect cos 2π f 0 t T

(4.10)

Il nostro schema diventa quello in figura 4.9, dove il filtro in uscita dal canale rumoroso (il rumore sia gaussiano, 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 sul rumore N: l’SNR, dunque, non dipende da K. 3 In

questo modo abbiamo l’SNR ottimo.

57

CAPITOLO 4. IL LIMITE DI SHANNON

58

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 − τ ) dτ = | {z } Kx ∗ (t0 −t+τ )

x (t) ∗ ν (t) =

∫∞

∫∞ −∞

Kx (τ ) x (t0 − t + τ ) dτ | {z } x = x ∗ perchè ∈R

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

−∞

58

CAPITOLO 4. IL LIMITE DI SHANNON

59

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τ = ±K

x2 (τ ) dτ +n (t0 ) = ±KEx + n (t0 )

−∞

−∞

−∞

∫∞

|

{z

|

}

n(t0 )≡n0

{z

Energia Ex

}

Per via del fatto che il rumore è gaussiano e bianco, allora anche di n(t0 ) possiamo dire la stessa cosa ed esaminare valor medio e varianza: ⎡ ⎤ E [n (t0 )] = E ⎣

∫∞

⎡ ]

var [n (t0 )] = E n2 (t0 ) − E2 [n (t0 )] = E ⎣ | {z }

=

−∞ −∞

∫∞ ∫∞

⎤ ν (τ ) ν (ξ ) h (t0 − τ ) h (t0 − ξ ) dτdξ ⎦ =

−∞ −∞

=0

∫∞ ∫∞

E [ν (τ )] h (t0 − τ ) dτ = 0 | {z }

−∞ =0 per ipotesi

−∞

[

∫∞

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

E [ν (τ ) ν (ξ )] h (t0 − τ ) h (t0 − ξ ) dτdξ | {z } Rν (τ −ξ )

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: N0 (4.13) Rν ( x ) = ℱ −1 { G0 ( f )} = δ (x) 2 Sostituendo nuovamente nell’espressione della varianza: ∫∞ ∫∞

var [n (t0 )] =

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

∫∞ ∫∞ −∞ −∞

−∞ −∞

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

La delta di Dirac ha la ben gradita proprietà di ’ammazzare’ un integrale (in quanto impone z = τ), quindi si ha: var [n (t0 )] =

∫∞ −∞

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

∫∞ −∞

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

∫∞ −∞

K2 x2 (t0 − t0 + τ ) dτ =

N0 2 K Ex 2

Dunque ora possiamo scrivere che n(t0 ) è una variabile aleatoria gaussiana avente i seguenti parametri: ( ) N0 2 ∼ n(t0 ) = 𝒩 0, K Ex (4.14) 2 Per semplificarci i calcoli supponiamo che 1 K= √ Ex Dunque ora si ha, più semplicemente: n ( t0 ) ∼ =𝒩

(

N0 0, 2

) (4.15)

Inoltre possiamo riscrivere nel seguente modo la risposta impulsiva

e la generica espressione di y(t0 ):

1 h ( t ) = √ x ( t0 − t ) Ex

(4.16)

√ y ( t0 ) = ± Ex + n0

(4.17)

Dunque ora lo schema è quello in figura 4.10. 59

CAPITOLO 4. IL LIMITE DI SHANNON

60

Figura 4.10:

4.5

Schema della trasmissione antipodale (una volta elaborato)

Hard decision

Strutturiamo il sistema affinché prenda delle hard-decision e aggiungiamo quindi un comparatore a soglia in cascata al morsetto trasportante y0 : tale comparatore propenderà per { +1 (bit ’0’) se y0 > 0 d= −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′ = } { }) 1( { = Pr d = +1 trasmesso un ′ 1′ + Pr d = −1 trasmesso uno ′ 0′ = 2 ⎛ ⎞

=

{ √ } {√ }⎟ } { √ }) 1 ( {√ 1⎜ ⎜Pr − Ex + n0 > 0 + Pr Ex + n0 < 0 ⎟ = Pr Ex < n0 + Pr − Ex > n0 = ⎝ ⎠ 2 | 2 {z } | {z } soprasoglia

1 = erfc 2

sottosoglia

{

√ √ } √ 1 Ex 1 1 Ex Ex √ + √ = erfc √ 2 2σn2 2 2σn2 2 2σn2

σn2 =

N0 2

=

√ 1 Ex erfc √ 2 N0

In figura 4.11 possiamo vedere la gaussiana e localizzare le erfc citate nelle formule precedenti. In particolare si ricorda che la funzione erfc ha la seguente forma analitica: 1 erfc ( x ) ≜ √ π

∫∞

2

e−t dt

x

Dunque possiamo verificare la correttezza dei nostri calcoli ricavando:

Figura 4.11:

La gaussiana e le erfc da considerare

60

(4.18)

CAPITOLO 4. IL LIMITE DI SHANNON

{

p e n0 >

√

Ex

}

=

∫∞ √

1 √

Ex

2πσn2

e

−

t2 2σn2

61

√ dt= 2σn ds

dt −−−−−−→ s= √ t

2σn

∫∞

√

1 √

Ex 2σn2

2πσn2

e

− s2

√

2σn ds =

∫∞ √

2 1 1 √ e−s ds = erfc 2 π

(√

Ex 2σn2

Quanto fatto fin’ora, a pensarci bene, ricorda il canale BSC con p pari alla pe così faticosamente calcolata poco fa (vedi figura 4.12). Sappiamo quindi bene qual è la sua capacità: C = 1 − ℋ( p) = 1 + p log2 p + (1 − p) log2 (1 − p)

Figura 4.12:

4.6

(4.19)

La similitudine con il canale BSC

Unquantized output

Nel paragrafo precedente abbiamo utilizzato un decisore: l’abbiamo fatto molto a cuor leggero, senza sottolineare il fatto che, ahimè, la scelta a soglia è molto drastica e - ponendosi come una vera e propria quantizzazione - ci fa perdere una parte della nostra informazione. Che accade allora se eliminiamo il decisore? 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 addendo h(Y ) = E[− log2 p(Y )] è abbastanza banale: l’unica è determinare p(Y ), che è un po’ meno scontata. . . √

√

( y − Ex )2 ( y + Ex )2 ( √ ) √ ) − − 1 1 ( 1 1 1 1 2 2σ 2σn2 n p (y) = p y X = Ex + p y X = − Ex = √ e + √ e = 2 | 2| 2 2πσn2 2 2πσn2 {z } {z } distribuzione gaussiana!

distribuzione gaussiana!

⎛ ⎞ √ √ ( y − Ex )2 ( y + Ex )2 − − 1 1 2 2 2σn 2σn ⎝e ⎠ = √ +e 2 2πσn2 61

Ex 2σn2

)

CAPITOLO 4. IL LIMITE DI SHANNON

62

Il secondo addendo è un pelo più elaborato ma neanche tanto: ( ( ( √ ) √ ) ( √ ) √ ) h (Y ∣ X ) = h Y X = Ex Pr X = Ex +h Y X = − Ex Pr X = − Ex = | {z } | {z } bit equiprobabili =0,5

bit equiprobabili =0,5

( √ )) √ ) 1 ( ( = = h Y X = Ex + h Y X = − Ex 2 √ √ √ ( √ ) √ )) h(Y ∣ X = Ex )=h(Y ∣ X =− Ex )=𝒩 ( Ex ,σn2 ) 1 ( ( = h Y X = Ex + h Y X = − Ex −−−−−−−−−−−−−−−−−−−−−−−−−−→ 2 (Sommiamo costante a distribuzione gaussiana) √ ( √ ) → h Y X = Ex = log2 2πeσn2 Ora abbiamo tutti gli elementi per calcolare la capacità di canale: C=−

∫∞

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

√

2πeσn2 =

−∞

=−

∫∞

−∞

=−

∫∞

∫∞

p (y) log2 p (y) dy −

p (y) log2

√

2πeσn2 dy =

−∞

( p (y) log2 p (y) + log2

√

2πeσn2

) dy = −

∫∞

( p (y) log2

p (y)

√

2πeσn2

) dy

−∞

−∞

L’ultimo integrale è ahimè calcolabile solo per via numerica; procedendo al calcolo otteniamo la figura 4.14. Si noti che Ex è l’energia per uso del canale: [ ] [ ] [ ] energia energia Shannon Ex = ESh ⋅C uso del canale Shannon uso del canale (4.20) ESh Ex 1 C≪1 ESh Ex −−→ = ≫ N0 N0 C N0 N0 non bisogna dunque inquietarsi se il grafico pare andare più a sinistra del tanto blasonato limite di Shannon. 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: ESh N0 |{z}

il limite di Shannon si applica qui!

=

Ex N0 |{z}

1 = −10 dB ⋅ C

ad es. - 10 dB

1 ( 1−ℋ

1 erfc 2

√

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) 62

(4.21)

CAPITOLO 4. IL LIMITE DI SHANNON

63

mentre la probabilità p è: 1 p = erfc 2

√

Ex N0

(4.22)

Concentriamoci però sulla zona cosiddetta Low SNR, ovvero quella tale per cui √ Ex z= →0 N0

(4.23)

In tal caso possiamo sviluppare p(z) in serie di McLaurin: { ( )} 1 2 ∫z −t2 d e dt 1− √ 2 π dp 0 McLaurin ⋅ |{z} z = p (z) −−−−−→ p (0) + ⋅ |{z} z = p (0) + dz z=0 dz →0 →0 z =0 ⎛ ⎞ √ 1 2 Ex 1 = p (0) + ⎝− √ |{z} z ⎠ ⋅ |{z} z = − 2 2 N0 π π →0

→0

La capacità del BSC è perciò: Sviluppo di Taylor

CBSC = 1 − ℋ ( p) = 1 + plog2 p + (1 − p) log2 (1 − p) −−−−−−−−−−→ intorno a p=0,5 ( ) 2 dC 1 1 d CBSC 2 + BSC ( p − p0 ) + → CBSC ( p − p0 ) = 2 dp p0 2 dp2 p0 | {z } =0 ( ) ) ( ) ( ) ( 1 1 1 d2 CBSC 1 2 1 = p− + p − = log2 p + p log2 e − log2 (1 − p) − log2 e ⋅ (1 − p) ⋅ p 1 − p p=0,5 2 2 2 dp2 p=0,5 ( ) ( ) ( ) 1 1 1 1 1 2 = = (log2 p − log2 (1 − p)) p=0,5 p − + log2 e + log2 e p− 2 2 p 1− p 2 | {z } p=0,5 =0

( 1 = (2log2 e + 2log2 e) p=0,5 p − 2 ⎛ ⎞2 √ 2 ⎜ Ex 1⎟ ⎜ 1 ⎟ = − − ⎟ = ⎜ ln 2 ⎝ 2 N0 π 2⎠ | {z } Trovato con McLaurin

1 2

)2

( ) ( ) 1 2 2 1 2 = 2log2 e ⋅ p − = = p− 2 ln 2 2

2 Ex = ln 2 2σn2 π |{z} N0

1 Ex ln 2 σn2 π | {z }

BSC hard - decision LOW SNR

≈

1 Ex ln 2 2σn2 | {z }

LOW SNR

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

4.8

Trattamento dei segnali passa-banda e water-filling

Nel caso di segnale passa-banda vale ancora la relazione: ( ) S C = B log2 1 + N

(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 tale calcolo su piccoli intervallini ∆ f in cui possiamo considerare circa costante sia la ∣ H ( f )∣ che le densità 63

CAPITOLO 4. IL LIMITE DI SHANNON

64

Figura 4.15:

Caso passabanda

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

⎛

( Ci = Blog2 1 +

S N

)

⎞ ( ) z}|{ 2⎟ 2 ⎜ H f H f 2∆ f G f G f )∣ )∣ ) ( ) ( ( ( ∣ ∣ x x i i i i i ⎟ = ∆i f log 1 + = ∆ f i log2 ⎜ 2 ⎝1 + ⎠ 2∆i f ⋅ Gν ( f i ) Gν ( f i )

Se ora mandiamo ∆ f → 0 e facciamo l’integrale su tutta la banda W otteniamo un’estensione della formula di Hartley-Shannon: ( ) ∫ Gx ( f ) ∣ H ( f )∣2 C = log2 1 + df Gν ( f ) W

Una volta fissata la potenza S = |{z} 2

∫

Gx ( f ) d f

bilatera W

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

( log2

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

)

− µGx ( f ) d f

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

∣ H ( f )∣2 ∣ H ( f )∣2 log e − µ = log2 e − µ = 0 2 Gx ( f ) ∣ H ( f )∣2 Gν ( f ) Gν ( f ) + Gx ( f ) ∣ H ( f )∣2 1+ Gν ( f ) 1

64

CAPITOLO 4. IL LIMITE DI SHANNON

65

Ma si ha anche:

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

(

Gν ( f )

∣ H ( f )∣

2

) −1

+ Gx ( f )

=

µ = costante log2 e

Dunque otteniamo: ⎧  ⎨ costante − Gν ( f ) se tale sottrazione dà come risultato un numero positivo ∣ H ( f )∣2 Gx ( f ) =  ⎩ 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: } { ⎧ G f ( )  ν ⎨ max costante − ,0 Gx ( f ) = ∣ H ( f )∣2  ⎩ 0 altrove

nella banda W

Il risultato sembra non dire niente? E invece nasconde un’importantissima informazione! Si osservi la figura 4.16: lo spettro Gx ( f ), lo ricordiamo, è la differenza fra il valore costante e la curva in figura. Nella zona verde, dove il canale è buono, questa quantità è maggiore di zero (e quindi è un valore ammissibile in quanto 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 conviene investire sui canali migliori e non sprecare potenza dove c’è molto rumore, perché il gioco non varrebbe la candela. Tale tecnica viene chiamata water-filling (o water-pouring) in quanto è visivamente comprensibile se 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à, ignorando completamente tutte le altre parti della banda W.

Figura 4.16:

4.8.1

La tecnica del waterfilling

Caso tempo-discreto

Questo ragionamento può essere ripreso pari pari nel caso tempo-discreto. Immaginiamo di avere N canali in √ parallelo e sia quello in figura 4.17 il generico canale i-esimo, dove λi è il guadagno in potenza dato che λi è il guadagno in tensione. 65

CAPITOLO 4. IL LIMITE DI SHANNON

66

Figura 4.17:

Figura 4.18:

Canale i-esimo

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 X12 + E X22 + . . . + E Xn2 = ∑ E Xk2 = ∑ Sk = S k

k

Ora il problema è come ripartirla, ma il discorso rispetto a prima non cambia: ( [ ] ) [ ] E xi2 λi 1 Shannon Ci = log2 1 + 2 uso del canale σ2 Massimizziamo quindi C tenendo conto del vincolo sulla potenza e usiamo nuovamente il metodo dei moltiplicatori di Lagrange: il risultato è il seguente: σ2 Sk = max cost − , 0 λk (

)

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

4 Orthogonal

Frequency Division Multiplexing.

66

CAPITOLO 4. IL LIMITE DI SHANNON

Figura 4.19:

67

Water-filling nel caso discreto

67

CAPITOLO 4. IL LIMITE DI SHANNON

68

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 ogni blocco d’ingresso di k bit. Di seguito chiameremo: ∙ code-rate il rapporto Rc = nk . 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 dunque sono molti di più i bit che trasmettiamo di quelli che dobbiamo codificare dalla sorgente. 1 Volendo rimanere nel caso generale dovremmo parlare di simboli, perché a rigore non è detto che l’alfabeto sia semplicemente quello binario (altri possibili alfabeti sono tipicamente quelli di cardinalità 2q con q > 1). Tuttavia quest’ultima casistica è quella di maggiore interesse e quindi daremo per scontato di lavorare con l’alfabeto {0, 1}.

69

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

70

Supponendo di aver fissato la potenza media di trasmissione S possiamo scrivere: S = Ebc ⋅ Brc = Eb ⋅ Br Da quest’ultima relazione si ricava anche: Eb Brc = Ebc Br Inoltre, se introduciamo anche il termine di rumore N0 (tipico del caso AWGN) otteniamo: Ebc Br E E Br E = ⇒ bc = b = b Rc Eb Brc N0 N0 Brc N0 Consideriamo ora tutte le possibili codeword in uscita dal codificatore e immaginiamo di metterle tutte nell’insieme 𝒞 : tale insieme è quello che in figura 5.2 è indicato in azzurrino. Come si nota, perché un codice 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 codicate (2 su un totale di 23 possibili stringhe lunghe 3) non sono però state prese a caso: esse sono infatti scelte anché abbiano distanza massima (tutti i bit sono infatti dierenti). 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 si ha che: 0 ≤ wi ≤ n ∙ distribuzione dei pesi {wi }: insieme dei pesi di tutte le parole di codice. La distribuzione dei pesi caratterizza le proprietà della distanza del codice; 70

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

71

∙ distanza di Hamming dij = d H (ci , c j ) fra due parole di codice ci , c j : numero di posizioni in cui le due parole sono differenti; ∙ distanza minima del codice: è definita come dmin = min dij i∕= j

(5.1)

e coincide con il peso minimo (esclusa la parola di tutti zeri): dmin = min(wr ) ∕ =0

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 indica GF (qn )). Possiamo definire la somma componente per componente (componentwise sum), che nel caso binario diventa la semplice somma ’modulo 2’:

( c1 , c2 , . . . , c n ) + ( d1 , d2 , . . . , d n ) = ( c1 + d1 , c2 + d2 , . . . , c n + d n )

(5.3)

Possiamo poi definire la moltiplicazione scalare componente per componente (componentwise scalar moltiplication): (5.4) k(c1 , c2 , . . . , cn ) = (kc1 , kc2 , . . . , kcn ) Indicando con S il campo di Galois appena descritto una volta definite queste operazioni, possiamo definire anche dei sottospazi vettoriali: possiamo ad esempio scegliere k vettori di lunghezza n linearmente indipendenti c˜1 , c˜2 , . . . , c˜k e le possibili combinazioni lineari di questi ultimi genereranno il sottospazio SC di dimensione k. I vettori ortogonali ai vettori di SC genereranno invece un sottospazio ortogonale a SC (che chiameremo SC⊥ ) che avrà dimensione n − k. Ovviamente, qualunque codice 𝒞 è un sottospazio di GF (q)n . Nel caso di codici a blocco lineari binari, il nostro insieme S (quello che prima coincideva con il campo di Galois tutto intero) conterrà tutti i possibili vettori binari di lunghezza n. Se SC è un sottoinsieme di S avente cardinalità 2k , allora il sottoinsieme ortogonale SC⊥ avrà cardinalità 2n−k e genererà il codice duale a quello 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 , c j ∈ 𝒞 ; ∀α, β ∈ {0, 1} ⇔ αci + βc j ∈ 𝒞

(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 c j coincide con il peso di ci − c j : d H ( ci , c j ) = w ( ci − c j ) = w ( ci + c j ) 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 2 D’altronde

le parole di codice sono soltanto due e una ha tutti zeri, quindi. . .

71

(5.6)

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

72

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à: ⎧ ⎨

⎫ ⎬

Bn = Pr {2 o 3 errori nella parola di codice} = |{z} ⎭ Stimato Trasmesso ( ) [ ] 3 = p3 + p ⋅ p ⋅ (1 − p ) = p3 + 3 p2 (1 − p) = 3p2 − 2p3 2 |{z} {z } |

Pe = Pr

3

Bˆ n ∕= ⎩ |{z}

errori

2 errori e 1 bit corretto

Ci abbiamo guadagnato o no? Se facciamo il confronto con il sistema uncoded scopriamo di sì (vedi gura 5.3, graco 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 sacrici in termini di energia.

Figura 5.3:

Confronto fra il caso non codificato e il codice a ripetizione (3,1)

Supponiamo infatti di eettuare la stessa trasmissione con codice a ripetizione attraverso un canale AWGN, trasmissione antipodale e uso di hard decision. In questo caso si ha 1 p = erfc 2

√

Ebc N0

dove Ebc è l'energia della forma d'onda che rappresenta un bit codicato e che costituisce una frazione di quella che possiamo pensare attribuita su un bit d'informazione:

Ebc = Eb Rc ⇒ p =

1 erfc 2

√

v u =1/3 u z}|{ √ u ⎷ Eb Rc Ebc 1 1 Eb = erfc > erfc N0 2 N0 2 N0

Dunque conviene non codicare e utilizzare il triplo dell'energia per bit trasmesso, oppure codicare e accontentarsi del quantitativo energetico Ebc per ogni bit codicato? La gura 5.3 (gura a destra) ci mostra che in realtà le cose vanno peggio nel caso codicato! 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 codicata. 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

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

73

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), perpetrata tramite i coefficienti g: cmj = xm1 g1j + xm2 g2j + . . . + xmn gmj (5.7) Dunque possiamo impostare il seguente sistema lineare per trovare tutti i bit cm j della parola codificata cm ⎧  cm1 = xm1 g11 + xm2 g21 + . . . + xmk gk1    ⎨c = x g +x g +...+x g m2 m2 22 m1 12 mk k2  . . .    ⎩c = x g +x g +...+x g mn

m2 2n

m1 1n

mk kn

Questo sistema lineare ha ovviamente una forma matriciale ⎡

g11

⎢ ⎢ g21 cm = xm G = xm ⎢ ⎢ . ⎣ .. gk1

g12 .. .

⋅⋅⋅ ..

⋅⋅⋅

. ⋅⋅⋅

g1n .. . .. . gkn

⎤ ⎥ ⎥ ⎥ ⎥ ⎦

e G viene chiamata la matrice generatrice del codice. In matematichese, il codice 𝒞 è lo spazio-riga della matrice G, ovvero l’insieme delle combinazioni lineari delle righe di tale matrice. Un’operazione di riga sulla matrice G non modifica il codice (si modifica la base del sottospazio, ma non il sottospazio stesso quindi le parole di codice rimangono invariate); nemmeno una permutazione di colonne della matrice G 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 si riferiscono a due codici equivalenti se una si può ottenere dall’altra con operazioni di riga e permutazioni di colonna. 73

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

74

5.5

Codici sistematici

Ogni matrice generatrice G può essere ridotta, tramite operazioni di riga e/o permutazioni di colonna in una forma sistematica tale per cui: ] [ (5.8) Gk×n = Ik×k Pk×(n−k) In tale relazione I è la matrice identità e P viene detta matrice di parità. Questa strutturazione della matrice generatrice ha il grosso vantaggio di conferire alla generica parola codificata la seguente struttura: x , x , . . . , xmk | m1 m2{z }

cm(k+1) , . . . , cmn | {z }

,

parte sistematica = parola d’informazione 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, se non vengono rilevati errori, sarà quindi sufficientemente tagliare via gli n − k bit della parte di parità per ottenere la parola che volevamo trasmettere, senza dover effettuare alcuna operazione di combinazione lineare 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 ⎡

1 G=⎣ 0 0

0 1 0

0 0 1

1 0 0

⎤ 1 1 ⎦ 1

è sistematico. Tale codice è equivalente a quello generato dalla seguente matrice ⎡

Geq

1 =⎣ 0 1

1 0 1

1 1 1

0 1 1

⎤ 0 0 ⎦ 1

Infatti basta eettuare le seguenti operazioni di riga e colonna per ottenere G: ⎡

Geq

1 =⎣ 0 1

1 0 1

1 1 1

0 1 1

⎤ ⎡ 0 1 0 ⎦⇒⎣ 0 1 0

1 0 0

0 1 0

1 1 1

⎤⎛ ⎞ ⎡ ← I + II 1 0 0 ⎦ ⎝ invariato ⎠ ⇒ ⎣ 0 ← I + III 0 1 |

0 1 0

0 1 0 0 1 0 {z

⎤ 1 1 ⎦ 1 }

permuto colonne

5.6

Matrice di controllo parità

Se il codice 𝒞 è stato ottenuto (generato) dalla matrice G, allora il codice 𝒞 ⊥ ortogonale a 𝒞 , detto codice duale, sarà ottenuto dalla matrice di controllo parità (parity check matrix) H. Matrice generatrice ⇒ Gk×n ⇒ Codice 𝒞 Matrice di controllo parità ⇒ H(n−k)×n ⇒ Codice 𝒞 ⊥ 74

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO Codice 𝒞

Codice duale 𝒞 ⊥

Gk×n

H(n−k)×n

H(n−k)×n

Gk×n

Matrice generatrice Matrice di controllo parità Tabella 5.1:

75

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 specificare che, così come per un certo codice 𝒞 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 𝒞 , per definizione, sarà ortogonale a qualunque vettore u di 𝒞 ⊥ . Inoltre, si avrà che: H ⋅ c T = 0, ∀c ∈ 𝒞

(5.9)

Dunque un qualsiasi vettore del codice 𝒞 , moltiplicato per la matrice di controllo parità trasposta H T , deve dare come risultato zero: tale condizione è necessaria e sufficiente e ciò significa che una parola non appartenente al codice 𝒞 , giunta a destinatario e frutto di uno o più errori di trasmissione, se moltiplicata per H T restituirà un risultato diverso da zero. In queste semplici considerazioni è quindi nascosto il principio 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: ] [ ] [ [ ] P [ ] P TT T = I ∣P GH = I ∣P = P+P = 0 I IT 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=

[

−P T

]

∣I

in GF(2)

−−−−−→

[

PT

∣I

]

allora la matrice di controllo parità sarà: H=

[

PT

∣I

]

[

=

1 1

1 0

0 1

]

Tale matrice è anche la matrice generatrice del single parity check code: se la permutiamo per colonne otteniamo infatti: [ ] [ ] 1 1

1 0

0 1

⇒

1 0

0 1

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. 3 Richard Wesley Hamming (Chicago, 11 febbraio 1915 - Monterey, 7 gennaio 1998) è stato un matematico statunitense, famoso per l’ideazione del Codice di Hamming. Dopo il dottorato conseguito all’Università dell’Illinois nel 1942, Hamming fu professore all’Università di Louisville fino all’inizio della Seconda guerra mondiale. Nel 1945 fece parte del Progetto Manhattan, programmando uno dei calcolatori digitali per calcolare le soluzioni delle equazioni fornite dai fisici del progetto. Nel 1968 ricevette il Premio Turing.

75

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

76

peso w

n∘ di codeword

0 3 4 7

1 7 7 1

Distribuzione dei pesi del codice di Hamming (7,4)

Tabella 5.2:

Consideriamo una matrice H fatta ad arte ⎡

1 H=⎣ 0 1

1 1 1

1 1 0

0 1 1

1 0 0

0 1 0

⎤ 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

1 ] ⎢ 0 ∣P = ⎢ ⎣ 0 0

0 1 0 0

0 0 1 0

0 0 0 1

1 1 1 0

0 1 1 1

⎤ 1 1 ⎥ ⎥ 0 ⎦ 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 la parità dei bit precedenti. Un escamotage del genere potrebbe servire, ad esempio, per allungare la distanza minima di un nostro codice 𝒞 : chiaramente quest’intervento non è ’gratuito’ perché si ha una diminuzione della rate di codifica e un conseguente aumento di ridondanza. Per creare un codice esteso siffatto è sufficiente estendere la matrice H nel seguente modo: [ ] H 0 Hext = 1 1 Nella formula precedente 0 è un vettore colonna di tutti zeri, 1 un vettore riga di tutti uni e H la matrice di controllo parità del codice di partenza. Con la precedente modifica effettuiamo il seguente passaggio: estensione

Codice 𝒞 ⇒ (n, k) −−−−−→ (n + 1, k) ⇒ Codice 𝒞ext 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 bit di codice per 4 bit di informazione, ora dobbiamo inviarne uno in più (per un totale di 8), il che comporta un dispendio maggiore di energia. La code-rate si è infatti abbassata da 4/7 a 4/8 = 1/2. 76

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO peso w Hamming (8,4) (esteso)

peso w Hamming (7,4)

n∘ di codeword

0 4 5 8

0 3 4 7

1 7 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 purgato! 4 purgato!

0 3 4 7

1 7 7 1

Tabella 5.4:

5.8

77

Distribuzione dei pesi del codice di Hamming (7,4) e della versione purgata

Codici purgati

L’operazione duale a quella dell’estensione, ma avente la stessa capacità di aumentare la distanza minima del codice, si chiama purga: se effettuata permette la seguente transizione purga

Codice 𝒞 ⇒ (n, k) −−−→ (n, k − 1) ⇒ Codice 𝒞purg Per ottenere tale risultato è sufficiente prendere soltanto le parole di peso pari del nostro codice di partenza, il che equivale modificare nel seguente modo la matrice H (che diventerà una n − k + 1 × n): [ ] H Hpurg = 1 Nella formula soprastante s’intende che H è la matrice di controllo parità del codice non purgato e 1 un vettore di tutti uni. La distanza minima del codice è aumentata (vedi tabella 5.4, in cui si fa un esempio col solito codice di Hamming (7,4)), ma anche questa volta la code-rate è diminuita in quanto è passata da 4/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: tale limite è 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 che possiamo 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 parte sistematica (peso 1)

| 111...11 | 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 questo punto, per non peggiorare (diminuire) la distanza minima del nostro codice, dobbiamo cercare di aumentare (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 una parola di codice avente una parte sistematica con due ’1’ 4 Senza

perdere in generalità, in quanto per ogni codice è possibile trovarne un equivalente sistematico.

77

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

78

Tabella 5.5:

n

k

code-rate Rc

3 7 15

1 4 11

1/3 4/7 11/15

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. Tuttavia questa 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 parte sistematica (peso 1)

| 111..101..11 | 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 e quindi 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 Singleton bound (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 separable code (MDSC). Ma è poi così importante disporre di un codice MDSC? Apparentemente sì, ma in realtà in GF(2) gli unici codici ad avere questa proprietà sono quelli a ripetizione, che sappiamo non essere proprio brillantissimi. . . 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 le colonne di quest’ultima contengano tutte le possibili configurazioni (tranne quella di tutti zeri) di vettori lunghi n − k. Dunque, fissati n e k, i codici di Hamming validi sono quelli aventi un numero di colonne n in 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 la parola 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 un qualunque vettore di lunghezza n o è una codeword oppure è distante ⌊ ⌋ dmin − 1 2 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 e applichiamo il ragionamento sui nostri codici (sia quello in figura 5.5 lo schema di riferimento). Se per ipotesi cm è una parola di codice allora anche ciò che è stato stimato dal decisore (cˆm ) lo dev’essere, se la parola è stata trasmessa correttamente. Ma qual è la probabilità di effettuare una scelta corretta? Su quale criterio dobbiamo basarci per sbagliare il meno possibile? Definiamo: 5 Inoltre,

non vi sono interstizi fra le regioni di decisione (vedi paragrafo 5.14.

78

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

Figura 5.5:

79

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 Decisione ci suggerisce di prendere la parola che massimizza la probabilità a posteriori (MAP, Maximum a-posteriori detection): cˆm = arg max p(ci ∣y) (5.11) c∈𝒞

Possiamo poi applicare il criterio di Bayes: p (y ∣c ) p (c) p (y)

p (c ∣y ) =

(5.12)

La quantità p (y ∣c ) viene denominata funzione di verosimiglianza (likelyhood function). Al variare di c si modifica, della 5.12, solo il numeratore, dunque il decodificatore MAP massimizza quest’ultimo: cˆm = arg max p (y ∣c ) p (c) c∈𝒞

Nel caso i simboli siano equiprobabili le probabilità p(ci ) saranno pari a 1/M (dove M è il numero totale di parole d’informazione): in questo caso si parla di maximum likelyhood detection (criterio ML) e il decodificatore deve limitarsi a massimizzare cˆm = arg max p(y∣c)

(5.13)

c∈𝒞

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; ∙ cˆm il simbolo per il quale decide il decoder. Inoltre supponiamo che le parole siano tutte equiprobabili, cioè che si abbia: 1 , ∀i 2k

ci = Il decoder ML si basa sulla seguente relazione:

cˆm = arg max p(r∣c)

(5.14)

c∈𝒞

Dobbiamo però calcolare p(r∣c): {

n

p(r∣c) =

∏ p ( ri ∣ ci )

⇐ p ( ri ∣ ci ) =

i =1

Quindi si ha: p(r∣c) =

p se ri ∕= ci 1 − p se ri = c

n

n

i =1

i =1

{ ovvero

p = p (1 ∣0 ) = p (0 ∣1 ) 1 − p = p (0 ∣0 ) = p (1 ∣1 )

∏ p ( ri ∣ ci ) = ∏ pdH (ri ,ci ) ⋅ (1 − p)(1−dH (ri ,ci )) 79

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

80

La produttoria possiamo portarla all’esponente (e farla quindi diventare una sommatoria): n

p(r∣c) =

∑ d H (ri ,ci )

∏ pdH (ri ,ci ) ⋅ (1 − p)(1−dH (ri ,ci )) = p i

∑ (1−d H (ri ,ci ))

⋅ (1 − p ) i

i =1

Le quantità all’esponente (sommatorie della distanza di Hamming fra bit) possono essere viste come distanze di Hamming calcolate sui vettori:

∑ d H (ri , ci ) = d H (r, c) i

∑ (1 − d H (ri , ci )) = n − d H (r, c) i

Dunque: p(r∣c) = p

d H (r,c)

⋅ (1 − p )

n−d H (r,c)

(

=

p 1− p

)d H (r,c)

⋅ (1 − p ) n

La quantità che il decoder deve massimizzare è il primo fattore, quello in cui compare c: (

p 1− p

)d H (r,c)

p

Ma se la base è minore di 1 (ed è questo il caso, perché 1− p è minore di 1 quando p < 0, 5), l’esponenziale è massimo quando è minimo l’esponente, ovvero quando è minimo d H (r, c). Ecco quindi trovata una formulazione alternativa e molto significativa (anche se apparentemente ovvia) del criterio ML: cˆ m = arg min d H (r, c) c∈𝒞

(5.15)

Tradotto in parole povere, il decodificatore ottimo è quello che decide in base alla minima distanza di Hamming: ricevuto il vettore r, il decoder propenderà quindi per la parola di codice c con meno bit differenti 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 il vettore 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 opzioni equivalenti, 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 distanza minima; 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 diventare consistente e 2k ’esplodere’, cosa che non possiamo assolutamente permetterci. Fortunatamente esiste un terzo metodo: sappiamo infatti che Hc T = 0 = cH T Supponiamo di poter prendere r e di moltiplicarla per H T : r ⋅ H T = (cm + e) H T = 0 + eH T = s Il vettore s viene chiamato sindrome dell’errore; il numero di possibili sindromi è pari a 2n−k e ad ognuna di esse è associato un pattern d’errore ovvero il vettore e che, moltiplicato per H T , restituisce la s stessa e che corrisponde quindi alla ’mappa’ dei bit invertiti nel passaggio attraverso il canale rumoroso. La tabella in cui vengono messi in corrispondenza le sindromi e i pattern d’errore (di peso minimo, visto che 80

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

81

sindrome

pattern d’errore

s1 s2 ... s 2n − k

e1 e2 ... e 2n − k

Tabella 5.6:

La tabella di decodifica

s1 = 0

c1 =0

c2

...

c 2k

s2 .. .

e2 .. .

c2 + e2 .. .

...

c 2k + e 2 .. .

s 2n − k

e 2n − k

c 2 + e 2n − k

Tabella 5.7:

... ...

c 2k + e 2n − k

Lo Standard Arrary

per ipotesi si vuole utilizzare il criterio ML) è chiamata tabella di decodifica (vedi tabella 5.6). Dunque da r calcoliamo s, poi dalla tabella determiniamo il pattern d’errore di peso minimo e infine lo sommiamo ad r per ottenere cˆ m . Si noti che, fatta l’ipotesi di aver sbagliato per la parola più vicina, se e non è il pattern di 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 )H T = el H T + ck H T | {z } =0

è possibile estendere la tabella di decodifica aggiungendo 2k − 1 colonne che considerino anche i casi non di peso minimo. Così facendo si crea lo Standard Array (o matrice canonica, vedi tabella 5.7), in cui vengono riportati le sindromi e tutti i modi in cui tali sindromi possono essere ottenute a partire dalle varie parole di codice valide. Ogni riga (coset) corrisponde a una determinata sindrome, ogni colonna ad una 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

0 1

1 0

0 1

1 1

]

Ad essa corrisponde la seguente matrice di controllo parità: ⎡

1 H=⎣ 0 1

0 1 1

1 0 0

0 1 0

⎤ 0 0 ⎦ 1

Vogliamo riempire il relativo standard array ; per calcolare la sindrome eettuiamo la seguente operazione: ⎡ ⎢ ⎢ s = rH = (cm + e) H = eH = e ⋅ ⎢ ⎢ ⎣ T

T

T

1 0 1 0 0

0 1 0 1 0

1 1 0 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 inne la decisione del decoder (01011). 81

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

82 s

e

000 001 010 011 100 101 110 111

00000 00001 00010 00100 01000 10000 11000 10010

Tabella 5.8:

5.14

01011 01010 01001 01111 00011 11011 10011 11001

10101 10100 10111 10001 11101 00101 01101 00111

11110 11111 11100 11010 10110 01110 00110 01100

Lo Standard Array dell’esempio

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 che significa, se manteniamo la raffigurazione visiva introdotta con la figura 5.6, tracciare delle circonferenze attorno a ciascuna parola di codice e rendere tali circonferenze le nostre regioni di decisione. Il raggio delle circonferenze dev’essere chiaramente imparentato con la distanza minima fra le codewords: esso deve infatti valere al massimo ⌋ ⌊ dmin − 1 2 ⌊ ⌋ dmin − 1 pena l’insorgere di ambiguità (vedi figura 5.7). Un decoder ML può quindi correggere fino a 2 errori oppure rivelarne dmin = 1 (se viene utilizzato solo come rilevatore). La soluzione appena illustrata (bounded distance decoding) è chiaramente sub-ottima in quanto, se il vettore ricevuto sta al di fuori di una circonferenza, il decoder non è in grado di decidere (vedi sempre figura 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, il decoder 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 interstizi non coperti fra le sfere è possibile solo la rilevazione (alla quale si reagisce mettendo in funzione un 82

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

Figura 5.7:

83

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 senza errori sia perché è stata corretta), Pmis la probabilità di ’cadere in un interstizio’ (e quindi di non saper decidere) e Pe di interpretare male la parola a causa dei troppi errori. Se il raggio della sfera è t e il numero di errori è > t usciamo da una regione di decisione e possiamo o finire in un interstizio oppure entrare in un’altra sfera; se il canale non è invece troppo cattivo, il decodificatore si ricondurrà alla parola a distanza minima da quella corretta. La probabilità che vi siano più di t errori è pari a6 : ( ) n n Pe ⩽ Pr {più di t errori nella codeword} = ∑ p m (1 − p ) n − m m m = t +1 Se p è piccola (auspicabile) il termine dominante sarà in realtà il primo della sommatoria e quindi potremo scrivere: ( ) n Pe ≈ p t +1 t+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 il dmin n % di bit della nostra codeword. La probabilità di errore per bit sarà quindi: numero bit sbagliati ⋅ (Probabilità di sbagliare) = bit totali per codeword ( ) ( ) d dmin 2t + 1 n n = min Pe ∼ p t +1 = p t +1 = t+1 t+1 n n n

Peb ≈

La probabilità di rivelare l’errore (ma non di correggerlo) è invece: ( ) n n Pmis ⩽ Pr {più di dmin − 1 errori} = ∑ p m (1 − p ) n − m m m=d min

Fra tutti i codici, gli unici ad avere la proprietà interessante di contenere tutti i possibili punti all’interno delle sfere (e di non avere quindi elementi negli interstizi) sono i cosiddetti codici perfetti (come ad esempio i codici di Hamming, vedi paragrafo 5.10). 6 Il leq indica che delle volte finiamo negli interstizi, quindi chiediamo la ritrasmissione e possiamo considerare questo caso come non portatore d’errore.

83

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

84

5.15

Criterio ML per canali additivi gaussiani

Dopo aver esaminato il BSC, tuffiamoci alla ricerca della forma del criterio ML nel caso continuo costituito 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 , . . . c M ) ν = (ν1 , ν2 , . . . νn ) y = cm + ν ⇒ yk = cmk + νk Dunque, siccome y è il risultato della somma fra un valore costante (cmk ) ed una variabile aleatoria gaussiana avente parametri (0, σ2 ), avremo che: y = 𝒩 (cmk , σ2 )

(5.16)

In questo caso la funzione di verosimiglianza (likelyhood function) assume la forma: n

p (y∣cl ) =

n

∏

k =1

p (yk ∣clk ) | {z }

=

v.a. gaussiana

|

{z

1

∏ √2πσ2 e

−

1 y −c 2 ( k lk ) 2σ2

(

=

k =1

√

)n

1 2πσ2

e

n 1 y −c 2 lk ) 2( k k=1 2σ

− ∑

(5.17)

}

produttoria ⇔ no memoria

Osservando che

n

∑ (yk − clk )2 = d2E (y, cl )

k =1

(dove d E è 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 ha il seguente criterio: arg max p (y∣cl ) = arg min d E (y, cl ) (5.18) cl

cl

Il decodificatore ML lavora perciò basandosi sul criterio della minima distanza euclidea. Volendo ulteriormente sviscerare le nostre formule possiamo elaborare il seguente termine: d2E (y, cl ) =

n

∑

k =1

(yk − clk )2 =

n

∑

(

) y2k + c2lk − 2yk clk =

k =1

∥ y ∥2 + ∥ c l ∥2 −2 | {z } | {z }

energia Ey

energia El

n

∑ yk clk

k =1

| {z }

correlazione

Dunque, volendo minimizzare la distanza euclidea, è sufficiente massimizzare il termine di correlazione: n

arg max cl

∑ yk clk

k =1

84

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

Figura 5.9:

85

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 = √

+ E

Se ora dividiamo per

√

cmk |{z}

+

oppure

νk |{z} ( )

√

− E

𝒩 0,

N0 2

(5.19)

E otteniamo la stessa somma ma diversamente normalizzata: yk = +1

cmk |{z}

oppure

+ −1

νk |{z}

(

N

𝒩 0, 2E0

)

bc

Come funziona il decoder a minore distanza euclidea? Supponiamo che il nostro codice contenga le seguenti due parole trasmissione antipodale

𝒞 = {(0, 0, 0) , (1, 1, 1)} −−−−−−−−−−−−−→ 𝒞 ant = {(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 < d2E1 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 𝒜k il generico k-simo evento all’interno dello spazio degli eventi, si ha ( ) P

M ∪

M

𝒜k

⩽

∑ P (𝒜k )

(5.20)

k =1

k =1

In soldoni, la somma delle probabilità dei vari eventi presi singolarmente non potrà mai essere inferiore della probabilità dell’unione di tali eventi. La cosa è molto intuitiva: alcuni eventi possono intersecarsi (si 85

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

86

pensi alle intersezioni nei Diagrammi di Venn) e, mentre somma delle probabilità conta due volte queste intersezioni (cioè una volta per ogni evento), l’unione le quantifica una volta soltanto. Applichiamo ora questo union bound alla trattazione del decoder ML: arg min d E = arg min ∥y − cl ∥ cl ∈𝒞

cl ∈𝒞

Quando sbaglia il decoder? Pr (errore ∣cm ) | {z }

{ ( ) } = Pr d E c j , y < d E (cm , y) per almeno un j ∕= m ∣cm

errore nell’ipotesi di trasmiss. di cm

Per lo union bound, questa probabilità sarà inferiore alla seguente somma di probabilità (ognuna delle quali è denominata pairwise error probability Pep (cm , cl ): { } M M Pr (errore ∣cm ) ⩽ ∑ Pr d2E (cl , y) < d2E (cm , y) ∣cm = ∑ Pep (cm , cl ) {z } | l ∕=m,l =1 l ∕=m,l =1 da unione di eventi... {z } |

(5.21)

...a eventi singoli presi a coppie

Esaminiamo meglio l’espressione della pairwise error probability: { Pep (cm , cl ) = Pr {d E (cl , y) < d E (cm , y) ∣cm } = Pr

∑ (clk − yk ) k

2

< ∑ (cmk − yk ) ∣cm

}

2

k

Sfruttando l’equazione 5.19 otteniamo: ⎧ ⎛ ⎞2 ⎛ ⎞2 ⎫   ⎨ ⎬ ⎜ ⎟ ⎜ ⎟ Pep (cm , cl ) = Pr ∑ ⎝clk − (cmk + νk )⎠ < ∑ ⎝cmk − (cmk + νk )⎠ =  | {z } | {z }  ⎩k ⎭ k yk yk { } { } ( ) 2 2 2 = Pr ∑ (clk − cmk ) + νk2 − 2νk (clk − cmk ) < ∑ (νk ) = Pr ∑ (clk − cmk ) < 2 ∑ νk (clk − cmk ) k

k

k

k

(5.22) Esaminando bene l’ultimo termine: ⎫ ⎧           ⎬ ⎨ 2 c − c < 2 ν c − c Pr ( ) ) ( ∑ lk mk ∑ k lk mk     k k     | {z } | {z }   ⎭ ⎩ 2 combinazione lineare di gaussiane (un’altra gaussiana) distanza euclidea d E (cl, cm ) La gaussiana a cui si fa riferimento sarà una variabile aleatoria, che chiameremo Z, avente i seguenti parametri: ⎞ ⎛ ⎞ ⎛ ⎜ ⎟ ⎜ ⎟ ( ) ⎜ ⎟ ⎜ ⎟ 1 ⎜ 2 2 2 ⎟ ∑ (clk − cmk ) ⎟ Z ∼ 𝒩 0, ∑ 4(clk − cmk ) σ = 𝒩 ⎜0, 4 ⎜ ⎟ ⎝ ⎠ E ⎜ ⎟ k ⎜ 2 bc |k {z }⎟ ⎝ ⎠ N0 | {z } d2E (cl ,cm ) σ2

Ora che sappiamo i parametri della gaussiana, possiamo - tramite la funzione erfc - determinare qual è la probabilità indicata nella relazione 5.22: ⎛ ⎞ { Pr

∑ (clk − cmk )2 < 2 ∑ νk (clk − cmk ) k

k

}

⎜ ⎟ ⎜ ⎟ ⎛√ ⎞ ⎜ ⎟ 2 (c , c ) 2 (c , c ) E ⎜ ⎟ d d 1 bc ⎠ E l m E l m ⎟ = 1 erfc ⎝ = erfc ⎜ ⎜v ⎟ u 2 2 4N 0 N ⎜u ⎟ ⎜ u2 ⋅ 2d2E (cl , cm ) 0 ⎟ ⎝⎷ Ebc ⎠ | {z } la varianza!

86

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

87

Ora possiamo invece osservare che ciascun bit a differenziare le parole cl e cm dà un contributo pari a 4 come indicato dalla seguente relazione:

[(+1) − (−1)]2 = 4

}

⇒ d2E (cl , cm ) = 4d H (cl , cm )

[(−1) − (+1)]2 = 4 Sostituendo:

⎛√ ⎞ (√ ) d2E (cl , cm ) Ebc 1 Ebc 1 ⎝ ⎠ = erfc d H (cl , cm ) erfc 2 4N0 2 N0

Quest’ultimo contributo, come abbiamo già accennato, rappresenta una formulazione alternativa della pairwise error probability. Sommando ora i contributi di tutte le parole l ∕= n (nella relazione 5.21 c’era una sommatoria che poi dopo abbiamo tralasciato per semplicità) otteniamo: 2k (= M )

Pe∣cm

1 ⩽ ∑ erfc 2 l =1,l ∕=m

(√

E d H (cl , cm ) bc N0

)

La probabilità d’errore Pe sarà una media su tutte le parole di codice (supponendo queste equiprobabili): M

1 1 Pe = ∑ Pe∣cm = M M m=1 |{z}

M

∑

Pe∣cm

m =1

1 ⩽ 2M

√

∑ ∑ erfc m l ∕=m

Ebc d H (cl , cm ) N0

p(cm )

Quest’ultima espressione è lo union bound sulla probabilità d’errore per la decodifica soft-decision dei codici a 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 cm dalla quale partiamo, in quanto stiamo in realtà calcolando dei pesi di Hamming e, per le proprietà dei codici a blocco, sommando due parole di codice si ottiene un’altra parola di codice: le distanze saranno quindi sempre quelle, visto che le parole sono ’intercambiabili’ all’interno di tale set. Possiamo dunque scegliere una parola (ed esempio quella di tutti zeri c1 , ma è indifferente) e rimuovere la sommatoria in m e moltiplicare tutto per M: Pe = Pe∣cm = Pe∣c1

v uE 1 M bc ⩽ ∑ erfc u ⎷N 2 l =2 0

d H ( c1 , c ) | {z l }

=peso (c1 parola di zeri)

1 M = ∑ erfc 2 l =2

√

Ebc w N0 l

Possiamo inoltre eliminare alcuni elementi dalla sommatoria, visto che il codice avrà una sua distanza minima e sarà quindi sufficiente utilizzare, come estremo inferiore, dmin (ricordiamo inoltre che il peso w rappresenta 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: 1 M Pe ⩽ ∑ erfc 2 l =2

√

Ebc 1 M wl = Ad erfc N0 2 d=∑ d min

√

Ebc 1 M d= Ad erfc N0 2 d=∑ d min

√ d

Eb Rc N0

(5.23)

Eb Se il rapporto N è grande, nella sommatoria i contributi maggiori verranno dalla parole con distanza più 0 vicina a dmin (se l’erfc aumenta troppo poi il suo contributo tende a calare). Quindi possiamo dare una versione approssimata dello union bound e anche un termine in grado di maggiorarlo (facciamo finta che tutte le parole tranne quella di tutti zeri abbiano distanza dmin così viene massimizzato l’effetto dell’erfc con dmin al suo interno): √ ⎧  A E Rc dmin  √ ≈ erfc dmin b  ⎨ M 2 N0 1 E Rc Pe ⩽ Ad erfc d b √ ∑ 2 d=d N0   M−1 E Rc min   erfc dmin b ⎩⩽ 2 N0

87

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

88

Ad

d

1 7 7 1

0 3 4 7

Tabella 5.9:

Set di distanze

Volendo, possiamo trovare la probabilità d’errore sul singolo bit ipotizzando di sbagliare per una parola a distanza dmin da quella corretta e scrivendo quindi: Peb = Pe

dmin 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: 1 M Pe ⩽ Ad erfc 2 d=∑ d min

√

E Rc 1 d b = ⋅ 7 ⋅ erfc N0 2

√

E 4 1 3 ⋅ b + ⋅ 7 ⋅ erfc N0 7 2

√

E 4 1 4 ⋅ b + ⋅ 1 ⋅ erfc N0 7 2

√ 7⋅

Eb 4 N0 7

Il decodicatore 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: n

Pe ⩽

∑

m = t +1

(

n m

)

p m (1 − p ) n − m =

n

∑

m =2

(

n m

)

p m (1 − p ) n − m = 1 −

∑

(

m=0,1

|

n m

)

p m (1 − p ) n − m

{z

}

proprietà delle distribuzioni statistiche

Provando a gracare 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 codicato 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 un codice (n, k). Come si può accorciare un codice? Forzando i primi l bit nella parte d’informazione ad essere degli zeri! In virtù della sistematicità del codice, i primi l bit d’uscita (cioè i primi l bit della parola codificata), saranno sempre pari a zero. Ignorando tali bit ne rimangono n − l ed il gioco è fatto: abbiamo quindi accorciato il codice selezionando il sottoinsieme di parole d’informazione che iniziano con l zeri rispetto al codice originale. Utilizzando un sottoinsieme di parole di codice, queste non possono che essere più 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’implementazione del codificatore è quella che dà più grane a un progettista, questo aspetto va particolarmente 88

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

89

considerato. Purtroppo tutto ciò viene ad un prezzo consistente nell’abbassamento della code-rate: infatti7 k k−l < n−l n

5.18

Codici a blocco lineari ciclici

Si dice scorrimento ciclico della parola

( c n −1 , c n −2 , . . . , c 1 , c 0 ) la seguente parola ricorsivamente shiftata:

( c n −2 , . . . , c 1 , c 0 , c n −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 ) = c n −1 D n −1 + c n −2 D n −2 + . . . c 1 D + c 0 La variabile D è una variabile ausiliaria, mentre i coefficienti sono da considerarsi modulo 2, visto che lavoriamo in GF(2). Shiftando di una posizione: C (1) ( D ) = c n −2 D n −1 + c n −3 D n −2 + . . . c 0 D + c n −1 Ebbene, un teorema ci assicura che C (1) ( D ) è il resto della divisione: D

C (D) D n −1

In altre parole, si ha che C (1) ( D ) ≡ D ⋅ C ( D )

mod ( D n − 1)

dove tale simbologia sta ad indicare che tali quantità restituiscono lo stesso resto se divise per Reiterando questo principio otteniamo: C (i ) D ≡ D i C ( D )

(5.24) Dn

− 1.

Esiste una codeword di grado minimo? Indicandola con g( D ) è facile mostrare che tale parola ha sempre questa forma8 : g ( D ) = D n−k + ...qualcosa... + 1 Inoltre, essa è unica: se infatti ne esistessero due, e le sommassimo, il grado diminuirebbe (siamo in modulo 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 di grado 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 una posizione, dovremmo trovare il resto di Dg ( D ) Dn − 1 7 Dimostrazione:

k−l k n (n − l ) − k (n − l ) < ⇒ <1 n−l n n (n − l ) n−k <1 n k − <0 n

8 La presenza dell’uno, lì in fondo, è necessaria: se non ci fosse potrei infatti shiftare il tutto per ottenere una parola di grado inferiore.

89

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

90

ma il resto di tale frazione è direttamente Dg( D ) in quanto tale termine ha grado inferiore ad n. Il vettore associato a questo primo scorrimento sarà:

(000 . . . 01. . . qualcosa . . . 10) Reiterando questo stesso procedimento, anche D2 g( D ) sarà una parola di codice, dunque possiamo proseguire finché il primo ’1’ in testa non arriva nell’ultima posizione a sinistra, eventualità che si verifica al k − 1-esimo shift: D k −1 g ( 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 quindi costituire una base k-dimensionale): g ( D ) , Dg ( D ) , D2 g ( D ) , . . . , D k−1 g ( D ) Se Q( D ) è un polinomio qualunque di grado ≤ k − 1, allora moltiplicando quest’ultimo per g( D ) otteniamo una parola di codice: Q ( D ) g ( D ) = C ( D ) ∈ codice 𝒞 | {z } | {z } | {z } ⩽k −1

n−k

⩽n −1

Questo semplice prodotto ci permette quindi di scrivere tutte le parole del codice: per questo motivo la preziosissima g( D ) viene denominata polinomio generatore del codice ciclico. Essa individua esattamente il nostro codice e ne individua le proprietà. Le condizioni perché un certo polinomio possa fregarsi dello status di generatore sono due: ∙ se 𝒞 è l’insieme dei polinomi g( D ) e Q( D ), ovvero il nostro codice (n, k) ciclico, il polinomio generatore è divisore di D n − 1. Dimostrazione: abbiamo la seguente corrispondenza g ( D ) = D n−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 D k−1 g( D ), polinomio di grado esattamente n − 1 corrispondente ad un vettore con un ’1’ in testa. Se ora ostinatamente reiteriamo il processo e moltiplichiamo per D k otteniamo: D k g ( D ) = g ( k ) ( D ) + ( D n − 1) Ma g(k) ( D ) è ancora una parola di codice, la quale può essere scritta come Q˜ ( D ) g( D ) dunque: ( ) D k g( D ) = Q˜ ( D ) g( D ) +( D n − 1) ⇒ g ( D ) D k + Q˜ ( D ) = D n − 1 | {z } g(k) ( D )

Abbiamo quindi fatto vedere che, fra i fattori di D n − 1, vi è g( D ), il che equivale a dire che tale polinomio è divisore di D n − 1; ∙ se g( D ) è divisore di D n − 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 ( D n − 1) 90

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

91

Ma ora, visto che per ipotesi g( D ) è un divisore di D n − 1, possiamo effettuare le seguenti sostituzioni (p( D ) è un polinomio generico): C (1) ( D ) = D Q ( D ) g ( D ) +Cn−1 g ( D ) P ( D ) = g ( D ) ( DQ ( D ) + Cn−1 P ( D )) | {z } | {z } | {z } D n −1

C(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: ( ) D 3 + 1 = ( D + 1) D 2 + 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. { ′ ′ 0 ⋅ g ( D ) = 000

C (D) =

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 ( ) ( )( ) D 7 + 1 = ( D + 1) D 5 + D 4 + D 3 + D 2 + D + 1 = ( D + 1) D 3 + D 2 + 1 D 3 + D + 1

si scopre le opzioni possibili sono molteplici (tabella 5.10). 91

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

92

(n, k)

g( D )

(7, 7) (7, 6) (7, 4) (7, 4) (7, 3) (7, 3) (7, 1) (7, 0)

1 D+1 D3 + D2 + 1 D3 + D + 1 ( D + 1)( D3 + D2 + 1) ( D + 1)( D3 + D + 1) ( D 6 + D 5 + . . . + 1) D7 + 1

No parity code: vengon fuori tutte le n-ple Parole di codice = parole di peso pari (overall parity check code) Hamming (7,4) Hamming (7,4) Hamming (7,4) + parità imposta da ( D + 1) Hamming (7,4) + parità imposta da ( D + 1) Codice a ripetizione (7,1) Il codice più inutile del mondo

Tabella 5.10:

5.19

Possibili codici ciclici con n = 7

Codificatore per codici ciclici (sistematici e non)

Il codificatore in questione (caso non sistematico) è un componente molto semplice che prende in pasto un polinomio x ( D ) (di grado al massimo k − 1) e lo moltiplica per g( D ). Il risultato è un polinomio C ( 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 comporterebbe moltiplicare per D n−k il polinomio x ( D ) della parola di informazione, in modo da elevarne il grado a n − 1 e portarlo ’in cima’ al polinomio codificato. Dobbiamo quindi imporre che si abbia: x ( D ) ⋅ D n−k = Q ( D ) g ( D ) + R ( D ) = C ( D ) | {z } resto

Si ha anche: x ( D ) ⋅ D n−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 gradi 0 → (k − 1) del polinomio C ( D ) (i gradi n → k sono invece ’occupati’ dalla parola d’informazione precedentemente shiftata). Dunque, riassumendo, ecco come si ottiene una parola di codice nel caso di codice ciclico sistematico: 1. calcoliamo D n−k x ( D ) il che significa, in soldoni, appendere alla parola di informazione n − k zeri in coda; 2. calcoliamo la divisione e prendiamo il resto: D n−k x ( D ) mod g( D ) = R( D ) 3. calcoliamo la parola di codice: C ( D ) = D n−k x ( D ) + R ( D ) Per la moltiplicazione fra polinomi esiste il circuito in figura 5.10, mentre per la divisione quello in figura 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): si noti che lo switch A è chiuso durante l’elaborazione dei primi k bit (che sono necessari caricare nel ramo di retroazione la parte sistematica da elaborare) mentre lo switch B discrimina fra la scelta della parte sistematica e quella del quoziente della divisione (ovvero dei n − k bit successivi ai primi k, corrispondenti ala parte sistematica che B pescava dal filo inferiore).

5.20

Calcolo della sindrome

Sia r ( D ) = C ( D ) + e( D ) 92

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

Figura 5.10:

Apparato per la moltiplicazione

Figura 5.11:

Figura 5.12:

93

Apparato per la divisione

Codificatore per codice sistematico ciclico

ciò che arriva al decodificatore per codici a blocco ciclici: C ( D ) è ovviamente la parola di codice, mentre e( D ) è l’eventuale pattern d’errore causato dal canale. Anche e( D ) è un polinomio: e n −1 D n −1 + . . . + e1 D + e0 Per capire se un polinomio fa parte del codice basta dividere ciò che si è ricevuto, cioè r ( D ), per il polinomio 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 sindrome. Per la correzione dell’errore è necessario sommare a r ( D ) = C ( D ) + e( D ) il pattern d’errore e( D ) 93

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

94 S( D )

e( D )

0 1 D D2 D+1 D2 + D D2 + D + 1 D2 + 1

0 1 D D2 D3 D4 D5 D6

Tabella 5.11:

0000000 0000001 0000010 0000100 0001000 0010000 0100000 1000000

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 di correzione. 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 da realizzare, richiede conoscenze matematiche modeste per la stima degli errori e si presta bene a rilevare errori di trasmissione su linee affette da elevato rumore di fondo. Le tecniche CRC furono inventate da W. Wesley Peterson che pubblicò il suo primo lavoro sull’argomento nel 1961. Utile per l’individuazione degli errori casuali, il CRC non è invece affidabile per verificare la completa correttezza dei dati contro tentativi intenzionali di manomissione. Tale famiglia di codici trova impiego, per esempio, nel protocollo HDLC9 : in particolare per quest’ultimo si utilizza un codice ciclico con polinomio g( D ) = D16 + D12 + D5 + 1 il quale è divisore di D2

15 −1

+1

Siccome abbiamo un numero pari di coefficienti, tutte le parole si annullano in D = 1 (e vengono quindi selezionate 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 anche il meccanismo ereditato dai codici di parità. 9 Incapsulato

nell’IP.

94

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

5.21.2

95

Codici Hamming ciclici

I codici di Hamming ciclici hanno parametri (n, k ) = (2m−1 , 2m−1 − m), con m qualunque. Sono codici a 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 il seguente 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 q qualunque. 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: ciascun simbolo è 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 due vettori (si tenga però presente che due simboli sono diversi anche se differiscono di un solo bit), è invece pari al valore (sempre dispari) (5.26) n−k+1 Come si nota, i codici di Reed-Solomon raggiungono il Singleton Bound; inoltre, con tale codifica possiamo correggere n−k t= 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 siatto 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 caratteristica di 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à di rendere errato un solo simbolo, visto che è formato da più bit. Di seguito tratteremo altri casi di questo genere. 95

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

96

5.23

Codici per la rilevazione di errori burst

Per lo studio di tali codici è necessario rimuovere l’ipotesi di indipendenza statistica degli errori, visto che essi hanno la tendenza a presentarsi ’in blocco’. Chiameremo inoltre burst di lunghezza b una sequenza di errori confinati in b posizioni consecutive. Teorema Ogni codice ciclico può rilevare tutti i burst di lunghezza b ≤ n − k. Questo significa che il polinomio errore e( D ) avrà in generale la seguente forma e( D ) = Di ( D b−1 + . . . zeri ed uni . . . + 1) dove il Di sta ad indicare la posizione assoluta della sequenza di bit errati. Supponiamo di voler solo rilevare (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 forza diverso da zero, dato che g( D ) ha grado n − k; dunque e( D ), in questo caso, fungerebbe (tutt’intero) da resto. Infatti: ∙ Di è divisibile per g( D )? No, perché il polinomio g( D ) non ha radice in D = 0 dato che finisce sempre per 1; ∙ allo stesso modo, nemmeno il polinomio D b−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 a 2m − 1: tutte queste parole sono uno shift ciclico di una stessa codeword. Infine, tutte le parole hanno un uguale peso, pari precisamente a 2m−1 . La codifica avviene con uno shift-register a m celle opportunamente configurato; tale processo è costituito da due fasi: la prima consiste nel caricamento dello shift-register mentre la seconda nella generazione della codeword. Le connessioni vengono scelte in modo che lo shift-register attraversi tutti i possibili 2m − 1 stati diversi da zero prima di tornare a quello iniziale. ESEMPIO:

In gura 5.13 vediamo lo schema di codica 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

CAPITOLO 5. I CODICI DI CANALE: CODICI A BLOCCO

Figura 5.13:

97

Esempio di schema per codificatore MLSR

Se scriviamo la funzione di autocorrelazione temporale: R x (k) =

1 n

n −1

∑ xi xi +k

i =0

Questa vale 1 quando k = 0 + ln (l intero, zero compreso) e −1/n altrove10 . Questa caratteristica fa avvicinare le sequenze pseudo-casuali a quelle veramente casuali, per le quali vale: { 1 per k pari a 0 R X ( k ) = E [ xi xi +k ] = 0 per k diverso da 0 Le due funzioni di autocorrelazione si somigliano, a meno del valore − n1 (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 random, per lo scrambling11 , per la crittografia o per evitare che lunghe sequenze di 0 e di 1 ostacolino la sincronizzazione fra sistemi di telecomunicazione).

10 Proposta

di dimostrazione: ricordando che xi può assumere il valore 1 o il valore -1 (segnalazione antipodale): ⎧ nxi2 1 n −1 2    k = 0 + ln ⇒ xi = = xi2 = sempre 1 ∑  ⎨ n i =0 n 1 n −1 R x (k) = xi xi +k =  n i∑  1 n −1 1 1 =0   xi xi+k = (−1) = − ⎩ altrove ⇒ n i∑ n n =0

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: n2 di questi varranno −1 (moltiplicazione fra simboli di segno diverso), n2 − 1 varranno +1 (prodotto di simboli d’uguale segno); il risultato della sommatoria, da dividere ancora per n, sarà dunque −1. 11 A scrambler is a device that transposes or inverts signals or otherwise encodes a message at the transmitter to make the message unintelligible at a receiver not equipped with an appropriately set descrambling device. Scrambling is accomplished by the addition of components to the original signal or the changing of some important component of the original signal in order to make extraction of the original signal difficult. A scrambler (also referred to as a randomizer) is a device that manipulates a data stream before transmitting. The manipulations are reversed by a descrambler at the receiving side. Scrambling is widely used in satellite, radio relay communications and PSTN modems. A scrambler can be placed just before a FEC coder, or it can be placed after the FEC, just before the modulation or line code. A scrambler in this context, has nothing to do with encrypting, as the intent is not to render the message unintelligeable, but to give the transmitted data useful engineering properties. A scrambler replaces sequences into other sequences 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 5. I CODICI DI CANALE: CODICI A BLOCCO

98

Capitolo 6

Codici a traliccio 6.1

Codici convoluzionali

I codici convoluzionali guadagnano molto in termini energetici (permettono l’uso di un rapporto SNR molto basso) e, asintoticamente, riescono a raggiungere una Peb molto bassa. Sono codici lineari creati mediante un codificatore a 𝒦 stadi (pari alla lunghezza di vincolo del codice) ciascuno composto da k celle di memoria; all’interno del codificatore entrano k bit alla volta e gli n bit di uscita sono calcolati come una qualche 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 bit precedenti: il codificatore, dunque, ha memoria! In generale il codificatore ha memoria (𝒦 − 1)k bit: ciò significa che tiene conto di tutti bit precedenti nello shift-register oltre ai k bit d’ingresso. ESEMPIO:

Il codicatore in gura 6.2: ∙ ha un solo shift-register all'interno del quale entra un bit alla volta; ∙ ha rate di codica 1/2 (per ogni bit che entra ne escono due); ∙ ha 2(𝒦−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 denire 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

CAPITOLO 6. CODICI A TRALICCIO

100

Figura 6.2:

Esempio di codificatore per codice convoluzionale

Figura 6.3:

6.2

Diagramma degli stati

Diagramma a traliccio

Con il diagramma a traliccio si rappresentano le possibili evoluzioni nel tempo dello stato: con riferimento all’esempio del paragrafo precedente, un possibile schema a traliccio è quello riportato in figura 6.4. La simbologia è simile a quella del diagramma degli stati, con la fattezza della freccia (in questo caso il colore) ad indicare quale bit d’ingresso produce la transizione di stato e la coppia di bit sopra le frecce ad 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 (solitamente entrambi S0 ) le possibili sequenze d’uscita sono le parole di codice. ESEMPIO:

Ad esempio, cinque transizioni sono necessarie per codicare 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 (𝒦 − 1)k bit a zero (tail biting). Questi bit aggiuntivi influiscono sulla coderate che, per m transizioni (codewords di nm bit), diventa pari a: Rc =

k ( m − 𝒦 + 1) nm 100

(6.1)

CAPITOLO 6. CODICI A TRALICCIO

101

Figura 6.4:

Figura 6.5:

6.3

Traliccio

Il traliccio percorso

Decodifica dei codici convoluzionali con hard decisions su BSC

Scegliamo di utilizzare il criterio ML (maximum likelyhood): applicare tale criterio in un traliccio, al fine di ricavare quale sia la parola di codice a minima distanza di Hamming da r (sequenza ricevuta), significa determinare la sequenza che totalizza lo shortest route, ovvero quella che percorre il traliccio totalizzando la 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

CAPITOLO 6. CODICI A TRALICCIO

102

la freccia blu (che porta in S1 ), accumuliamo distanza di Hamming pari a 2, visto che la sequenza ricevuta 00 dierisce per due bit rispetto a quella indicata sopra la freccia. Dopo cinque transizioni, quando la parola codicata si sarà 'esaurita', saremo in grado di determinare tutti i possibili percorsi, ognuno dei quali avrà un proprio peso: scegliere quello minore signicherà 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 Hamming per 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 procedimento ricorsivo-sequenziale. Il suo funzionamento si basa su un’osservazione fondamentale: se il percorso di peso 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 due percorsi 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 lunghezza del relativo percorso; ∙ inizializzazione: va effettuata solo per l = 0. Si parte dallo stato S0 e si definisce per l’unico possibile survivor 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, che sarà pari al peso al passo precedente (l − 1) sommato al peso della transizione. Per ogni stato finale si determina il survivor come quello a peso minimo. Dopodiché si ripete questo procedimento fino al termine. L’algoritmo di Viterbi si può usare per decodificare codici convoluzionali sia nel caso di hard-decision che 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 quelli associati 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 di memoria richiesto sarà pari a 1 survivor / stato + 1 lunghezza di percorso (survivor) / stato 1 Ricordiamo

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(𝒦−1)

6.4.2

Altri aspetti implementativi

Si può migliorare o perfezionare l’algoritmo di Viterbi troncando il trellis dopo (5 ∼ 6)𝒦 e decidendo in base al percorso minimo calcolato fino a quel punto (Truncated Viterbi Algorithm). Inoltre si può ricorrere alla normalizzazione delle metriche e alla quantizzazione. Si definisce distanza libera (d f ree ) del codice convoluzionale la distanza minima tra tutte le possibili diverse sequenze di codice. Questo parametro è l’analogo della distanza minima dmin fra le parole di codice già vista nel caso di codici a blocco lineari. In particolare, il guadagno di codifica asintotico è: ( ) GC (dB) ⩽ 10log10 d f ree Rc

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:

6.6

Diagramma a traliccio di codice convoluzionale punturato

Codici convoluzionali sistematici

Hanno in genere una distanza d f ree peggiore dei non sistematici (vedi tabella 6.1, la quale si riferisce al codificatore 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 bit di informazione errati: questo avviene in quanto gli errori possono far prendere una strada sbagliata nel traliccio, impossibile da lasciare per determinate combinazioni di bit ricevuti (con conseguente accumularsi di errori). Si dimostra che il codice è catastrofico se g1 ( D ) e g2 ( D ), cioè le espressioni che indicano come vengono combinati i bit in uscita, hanno fattori in comune.

103

CAPITOLO 6. CODICI A TRALICCIO

104

Figura 6.7:

Codificatore di codice convoluzionale sistematico

𝒦

d f ree codice sistematico

d f ree codice NON sistematico

3 4 5 6 7 8

4 4 5 6 6 7

5 6 7 8 10 10

Tabella 6.1:

Codice convoluzionale sistematico vs. non sistematico

104

Capitolo 7

Altri aspetti riguardanti i codici di canale 7.1

Interleaving Le ditate sui CD sono il male. Il saggio

Consideriamo un’applicazione particolare, cioè quella della memorizzazione dei dati su CD. Quando poniamo il nostro ditone sulla superficie del CD non stiamo compiendo un’azione indolore, bensì creando una valanga di errori a burst. Magari il nostro codice è in grado di correggere un certo numero di errori per codeword e tuttavia, fatta la ditata, ci troviamo con un sacco di parole senza errori assieme ad altre completamente sbagliate. Facciamo ora un altro esempio: una stazione mobile (come un cellulare), non riceve un unico cammino dalla 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 costruttivamente che 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 loro lavoro e impedire una corretta comunicazione. Come possiamo fare per tutelarci da questi spiacevoli inconvenienti? La cosa migliore è sparpagliare i bit secondo un certo criterio (interleaving), per poi ricomporli lato ricevitore in modo da diluire i bit sbagliati in mezzo a quelli giusti. Fra i vari modi in cui possiamo effettuare l’interleaving esamineremo quello 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’interleaving a blocco, tale matrice (matrice di interleaving) viene riempita per righe di parole codificate e, in seguito, trasmessa 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 i bit sono stati accuratamente sparpagliati: quelli che prima erano due bit adiacenti ora disteranno D posizioni; 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 di lunghezza 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 ritardo consistente 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 loro dati. Nel seguente esempio mostreremo come il ritardo necessario a un corretto funzionamento di questa tecnica possa essere drammaticamente alto nel caso in cui il canale sia parecchio rumoroso. 105

CAPITOLO 7. ALTRI ASPETTI RIGUARDANTI I CODICI DI CANALE

106 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 progettiamo 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 − 1 2

⌋

= 15

Potendo noi tollerare al massimo 15 errori per codeword, il parametro D della matrice di interleaving dovrà essere almeno pari a: D≥

4800 = 320 15

Il ritardo introdotto sarà quindi pari a: 2Dn 81280 = = 4, 2 secondi Brc 19200

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 possono essere composti (applicati ’uno dietro l’altro’) per ottenere un risultato (si spera) più performante per quanto riguarda la rilevazione/correzione degli errori. Supponendo che utilizzare due codici, chiameremo outer (esterno) il codice che per primo viene applicato e che per ultimo viene decodificato, mentre diremo 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 proprie peculiarità: la NASA, per esempio, utilizza per le applicazioni deep-space un Reed-Solomon (255,233) su GF(28 ) (ottimo per la correzione degli errori a burst) concatenato a un codice convoluzionale per sfruttare la 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, che trovano impiego nelle comunicazioni satellitari nello spazio profondo ed in altre applicazioni in cui i progettisti puntano ad avere il massimo trasferimento di informazione su una banda limitata in presenza di un segnale ricevuto molto affetto da rumore. I Codici Turbo sono stati teorizzati da Claude Berrou, Alain Glavieux e Punya Thitimajshima presentati nel 1993 ad una conferenza dell’IEEE. I codici turbo sono ancora ad oggi oggetto di ricerche in numerose università del mondo, allo scopo di raffinarli e di ottenere implementazioni più efficienti.

106

CAPITOLO 7. ALTRI ASPETTI RIGUARDANTI I CODICI DI CANALE

107

Cerchiamo ora di comprenderne, almeno qualitativamente, il principio di funzionamento. Supponiamo di avere un unico bit: gli unici messaggi possibili sono quindi w1 =′ 0′ e w2 =′ 1′ . Un decisore che propendesse per la massima probabilità a posteriori (MAP) deciderebbe in base al seguente criterio: wˆ = arg max p (wi ∣y ) wi

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 ) > 1? ⇒ P ( X = − 1 ∣Y )

{

se sì allora propendi per + 1 altrimenti scegli −1

In versione logaritmica: P ( X = + 1 ∣Y ) ln > 0? ⇒ P ( X = − 1 ∣Y )

{

se sì allora propendi per + 1 altrimenti scegli - 1

Così scrivendo, la decisione sarà il segno del nostro logaritmo. Volendo possiamo sfruttare il criterio di Bayes: P (Y ∣ X ) P ( X ) P ( X ∣Y ) = P (Y ) Quindi abbiamo: ⎫ P (Y ∣ X = + 1 ) P ( X = + 1 )   { } ⎬ P (Y ∣ X = + 1 ) P ( X = + 1 ) P (Y ) ˆx = sign ln = sign ln =  P (Y ∣ X = − 1 ) P ( X = − 1 )  P (Y ∣ X = − 1 ) P ( X = − 1 )   ⎩ ⎭ P (Y ) ⎫ ⎧       ⎨ P (Y ∣ X = + 1 ) P ( X = +1) ⎬ + ln = sign ln  P (Y ∣ X = − 1 ) P ( X = −1)     {z } | {z } ⎭ ⎩| ⎧   ⎨

primo contributo

secondo contributo

Il primo contributo è imparentato con il rapporto di funzioni di verosimiglianza, mentre il secondo con la probabilità a priori. Supponiamo ora che i bit siano equiprobabili (cosicché il secondo contributo svanisce): { } P (Y ∣ X = + 1 ) xˆ = sign ln P (Y ∣ X = − 1 ) Osserviamo lo schema di codifica/decodifica in figura 7.1: in essa si nota che i due decodificatori, che lavorano con valori soft, sono retroazionati cosicché il risultato del primo decodificatore viene dato al secondo come probabilità a priori. Vista l’esistenza di questi contributi, che entrano nella catena di decodifica come 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 (che strutturalmente è uguale al primo) e così via. Se riusciamo ad evitare il feedback positivo (che, come sappiamo 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-codici hanno infatti una capacità di correzione d’errore veramente impressionante: la curva della BER va giù a strapiombo anche nelle regioni a basso rapporto segnale-rumore (regione ’waterfall’). Purtroppo, questo avviene 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

CAPITOLO 7. ALTRI ASPETTI RIGUARDANTI I CODICI DI CANALE

108

Figura 7.1:

7.4

Schema di principio del funzionamento dei turbo-codici

LDPC: Low Density Parity Check

I codici LDPC (Low Density Parity Check) costituiscono una particolare tipologia di codici a blocco a correzione d’errore inventata da Robert G. Gallager nel 1961. Inizialmente inimplementabili a causa della loro complessità computazionale, i codici LDPC sono stati dimenticati per più di trent’anni fino alla loro riscoperta, avvenuta a metà degli anni ’90, sotto l’impulso dell’introduzione dei Turbo codici e del principio della decodifica iterativa (ad opera dei francesi Berrou e Glavieux nel 1993). Tali codici costituiscono tutt’ora una delle migliori soluzioni in termini di efficienza spettrale; inoltre, uno dei grandi vantaggi riscontrabili nell’uso di questa codifica consiste nella possibilità di poter decodificare l’informazione 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 righe costituiscono delle equazioni di parità da applicare alle parole ricevute al fine di verificarne la correttezza ed eventualmente correggerle.

Figura 7.2:

Schema qualitativo del principio degli LDPC

Giusto per capire qualitativamente il principio di questi codici (in realtà molto complessi), esaminiamo la 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 un meccanismo 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): essi vengono creati affiancando matrici circolanti al fine di creare la matrice di parità del codice H. Le matrici circolanti hanno la caratteristica di poter essere descritte tramite la loro sola prima riga (detta anche riga generatrice), in quanto le righe successive sono ottenute dalla prima attraverso shift ciclici. Questo metodo di costruzione ha due importanti vantaggi: 1 Matrice

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 implementano il decoder e l’encoder; ∙ la complessità di codifica è lineare rispetto alla lunghezza del codice (vengono usati degli shift registers).

109

110

CAPITOLO 7. ALTRI ASPETTI RIGUARDANTI I CODICI DI CANALE

110

Elenco delle figure 1.1 1.2 1.3 1.4

Lo schema del collegamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Grafico probabilità/informazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . Entropia di una variabile aleatoria bernoulliana . . . . . . . . . . . . . . . . . . . Esempio delle relazioni che intercorrono fra le probabilità congiunte e marginali

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

7 9 10 13

2.1 2.2 2.3 2.4 2.5

Sorgente tempo-discreta . . . . . . . . . . . . . . . . Schema di trasmissione col codificatore di sorgente Albero di un codice a prefisso . . . . . . . . . . . . . Schema della codifica a blocchi . . . . . . . . . . . . L’alberino post-natalizio . . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

19 23 24 28 29

3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 3.16 3.17 3.18

Canale discreto senza memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . Il grafo bipartito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Esempio con grafo bipartito . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Canale binario simmetrico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Capacità in funzione di p per il BSC . . . . . . . . . . . . . . . . . . . . . . . . Binary Erasure Channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Canale Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Capacità del canale Z in funzione della probabilità p . . . . . . . . . . . . . . Canale binario non simmetrico . . . . . . . . . . . . . . . . . . . . . . . . . . . Canale ’strano’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Canale discreto senza memoria: caso di gruppi di simboli . . . . . . . . . . . Y dipende da X, Z dipende da X solo per mezzo di Y . . . . . . . . . . . . . Apparato per illustrare la disuguaglianza di Fano . . . . . . . . . . . . . . . . Interpretazione grafica della disuguaglianza di Fano . . . . . . . . . . . . . . Limite superiore per l’entropia . . . . . . . . . . . . . . . . . . . . . . . . . . . Schema di riferimento per la dimostrazione del secondo teorema di Shannon Probabilità di errore e code-rate . . . . . . . . . . . . . . . . . . . . . . . . . . . Densità di probabilità di una variabile aleatoria continua . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

31 32 32 33 34 34 35 36 37 38 39 40 40 42 43 44 45 46

4.1 4.2 4.3 4.4

Rumore additivo gaussiano bianco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Capacità in funzione del rapporto segnale rumore . . . . . . . . . . . . . . . . . . . . . . . . . Schema del caso tempo-continuo a banda limitata . . . . . . . . . . . . . . . . . . . . . . . . . Spettri dei segnali (raffiguriamo solo la parte tra − B e B tanto ci pensa il filtro ad eliminare tutto il resto!) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Capacità su banda in funzione dell’SNR e capacità in funzione della banda . . . . . . . . . . Sistema di trasmissione completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Punti ammissibili e non ammissibili e limite di Shannon (1) . . . . . . . . . . . . . . . . . . . Punti ammissibili e non ammissibili e limite di Shannon (2) . . . . . . . . . . . . . . . . . . . Schema della trasmissione antipodale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Schema della trasmissione antipodale (una volta elaborato) . . . . . . . . . . . . . . . . . . . La gaussiana e le erfc da considerare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . La similitudine con il canale BSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Schema senza decisore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Caso unquantized confrontato con il BSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51 52 53

4.5 4.6 4.7 4.8 4.9 4.10 4.11 4.12 4.13 4.14

111

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

53 55 56 57 58 58 60 60 61 61 62

ELENCO DELLE FIGURE

112 4.15 4.16 4.17 4.18 4.19

Caso passabanda . . . . . . . La tecnica del waterfilling . . . Canale i-esimo . . . . . . . . . Guadagno in potenza e canali Water-filling nel caso discreto

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

64 65 66 66 67

5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11 5.12 5.13

Schema della codifica a blocco lineare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Insieme delle parole non codificate e mapping iniettivo verso quello delle parole codificate Confronto fra il caso non codificato e il codice a ripetizione (3,1) . . . . . . . . . . . . . . . Ogni bit della parola di codice è combinazione lineare dei bit della parola d’informazione Lo schema di trasmissione: codifica, decodifica e decisione . . . . . . . . . . . . . . . . . . . Regioni di decisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Criterio sub-ottimo di decisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Rumore additivo gaussiano e criterio ML: schema di riferimento . . . . . . . . . . . . . . . Schema di riferimento per la segnalazione antipodale su canale AWGN . . . . . . . . . . . Apparato per la moltiplicazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Apparato per la divisione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Codificatore per codice sistematico ciclico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Esempio di schema per codificatore MLSR . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .

69 70 72 73 79 82 83 84 85 93 93 93 97

6.1 6.2 6.3 6.4 6.5 6.6 6.7

Schema generico per codificatore di codici convoluzionali Esempio di codificatore per codice convoluzionale . . . . . Diagramma degli stati . . . . . . . . . . . . . . . . . . . . . Traliccio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Il traliccio percorso . . . . . . . . . . . . . . . . . . . . . . . Diagramma a traliccio di codice convoluzionale punturato Codificatore di codice convoluzionale sistematico . . . . .

. . . . . . .

99 100 100 101 101 103 104

7.1 7.2

Schema di principio del funzionamento dei turbo-codici . . . . . . . . . . . . . . . . . . . . . 108 Schema qualitativo del principio degli LDPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

112

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . .

. . . . . . .

. . . . . . .

Elenco delle tabelle 1.1

Probabilità congiunte e marginali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.1 2.2 2.3 2.4

Qualche esempio per la nomenclatura dei codici . . . . . . . . . . . Caso sfortunato di Shannon-Fano . . . . . . . . . . . . . . . . . . . Distribuzione di probabilità del nostro esempio . . . . . . . . . . . Distribuzione di probabilità del nostro esempio, con supersimboli

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

23 27 29 29

5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 5.10 5.11

Matrici generatrici e di controllo parità di un codice e del suo duale . . . . . Distribuzione dei pesi del codice di Hamming (7,4) . . . . . . . . . . . . . . . Distribuzione dei pesi del codice di Hamming (7,4) e della versione estesa . Distribuzione dei pesi del codice di Hamming (7,4) e della versione purgata Parametri n e k per codici di Hamming . . . . . . . . . . . . . . . . . . . . . . La tabella di decodifica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lo Standard Arrary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Lo Standard Array dell’esempio . . . . . . . . . . . . . . . . . . . . . . . . . . . Set di distanze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Possibili codici ciclici con n = 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . Associazione sindrome-pattern . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

75 76 77 77 78 81 81 82 88 92 94

6.1

Codice convoluzionale sistematico vs. non sistematico . . . . . . . . . . . . . . . . . . . . . . 104

113

. . . .

. . . .

. . . .

. . . .

. . . .