Comunicazioni Elettriche II

Laurea Magistrale in Ingegneria Elettronica

Università di Roma La Sapienza

A.A. 2017-2018

Capacità del canale discreto

Teoria dell’informazione

Sorgente Codificatore di sorgente

Codificatore di canale DestinazioneCanale

Obiettivo del codificatore di sorgente: minimizzare il bit rate nel rappresentare la sorgente (compressione dati)

Obiettivo del codificatore di canale: massimizzare il bit rate all’ingresso del canale (velocità di trasmissione) affinché la trasmissione avvenga rispettando prestazioni specifiche

Teoria dell’informazione

La teoria dell’informazione consente di dare risposta a due problemi fondamentali

Sorgente Codificatore di sorgente

Codificatore di canale DestinazioneCanale

Qual’ è la minima velocità di trasmissione ottenibile nella compressione dei dati: l’entropia H

Qual’ è la massima velocità di trasmissione ottenibile nella trasmissione: la capacità di canale C

Limiti

Se l’entropia della sorgente è inferiore alla capacità di canale, è possibile ottenere, asintoticamente, comunicazioni prive di errore

La teoria dell’informazione studia tali limiti e suggerisce anche come raggiungerli, benché computazionalmentepossano rivelarsi impraticabili

ComunicazioniLimite sulla

compressione dati

Limite sulla velocità di

trasmissione

entropia capacità di canale!! min I X ,X!( ) !!max I X ,Y( )

Capacità di canale

L’analisi svolta finora ha considerato la sorgente

I dati generati e codificati sono tuttavia tipicamente trasmessi su un canale che può introdurre errori

Ci si chiede quindi: quanta informazione è possibile trasferire sul canale pur preservando una probabilità di errore piccola a piacere?

Questa quantità prende il nome di Capacità di canale

Il canale discreto

Codificatore DecodificatoreCanalep(y/x)

W

Messaggio

Xn Yn ŴStima del Messaggio

Si definisce “canale discreto” un sistema che consiste in un alfabeto di ingresso X , un alfabeto di uscita Y e una matrice di probabilità di transizione che esprime la probabilità di osservare un simbolo y in uscita dato un simbolo in ingresso x, p(y/x).

Il canale è senza memoria se la distribuzione delle uscite dipende solo dall’ingresso allo stesso momento ed è condizionatamente indipendente sia da ingressi che da uscite precedenti

Capacità del canale discreto senza memoria

La capacità del canale discreto senza memoria è

!!C =max

p(x )I(X ;Y )

dove il massimo è rispetto a tutte le possibili distribuzioni dell’ingresso p(x)

Codificatore DecodificatoreCanalep(y/x)

W

Messaggio

Xn Yn ŴStima del Messaggio

Esempio: il canale binario non rumoroso

Canale binario non rumoroso

In questo caso l’uscita Y è una riproduzione dell’ingresso X e in ogni trasmissione possiamo mandare 1 bit senza errori al ricevitore. La capacità di canale è quindi 1 bit, e la si ottiene con p(x)= (½, ½)

C =max I X ;Y( ) =1bit

1

0

1

0

Esempio: il canale rumoroso con uscite distinte

In questo caso l’uscita Y non è una riproduzione dell’ingresso X ma in effetti per ogni trasmissione possiamo mandare 1 bit senza commettere errori. La capacità di canale è quindi 1 bit, e la si ottiene con p(x)= (½, ½)

C =max I X ;Y( ) =1bit

0

1

1

2

3

4

X Y

1/2

1/2

1/3

2/3

Esempio: noisy typewriter

Canale rumoroso con 26 simboli

Ogni simbolo è ricevuto correttamente con probabilità ½ oppure come il simbolo successivo con probabilità ½

!!

C =max I X ;Y( ) =max(H(Y )−H(Y / X ))==maxH(Y )−1= log26−1= log13

A

B

Z

Se si usano tutti i simboli la trasmissione avviene con errore ma se si usano solo simboli alternati, per esempio A, C etc. la trasmissione è corretta e il canale si comporta come il canale privo di rumore sul quale si possono mandare 13 simboli per trasmissione senza commettere errore. La capacità è raggiunta usando una p(x) distribuita uniformemente su tutti gli ingressi:

A

B

Z

C C

Il canale binario simmetrico BSC

Canale binario simmetrico

Questo è il modello più semplice di canale rumoroso

1

0

1

01-p

1-p

pp

Tuttavia rappresenta molto bene anche aspetti complessi del problema più generale

Nota: tutti i bit ricevuti sono inaffidabili!

Il canale binario simmetrico BSC

!!

I(X ;Y )=H(Y )−H(Y / X )==H(Y )− p(x)H(Y / X = x)=∑=H(Y )− p(x)H(p)=∑=H(Y )−H(p)=≤1−H(p)

dove l’uguaglianza vale se p(x) è uniforme

Quindi la capacità del canale binario simmetrico con parametro p è

!!C =1−H(p) bit

1

0

1

01-p

1-p

pp

Il canale binario con cancellazione

Il canale con cancellazione è un canale binario nel quale una frazione α di bit è cancellata anziché corrotta. Il ricevitore sa quali bit sono stati cancellati.

1

0

1

01-α

1-α

αα e

C =maxp(X )

I(X ;Y )=maxp(X )

(H(Y )−H(Y / X ))=maxp(X )

H(Y )−H(α )

Intuitivamente il massimo di H(Y) sarebbe log3 ma in effetti dipende da p(x)

Sia Pr{X=1}=π

H(Y )=H((1−π )(1−α ),α ,π(1−α ))=H(α )+(1−α )H(π )

Il canale con cancellazione

Si ha quindi

raggiunta se π=1/2

C =maxp(x )

H(Y )−H(α )=maxπ(1−α )H(π )+H(α )−H(α )=

=maxπ(1−α )H(π )=1−α

Se il canale è dotato di feedback è chiaro cosa si debba fare: se un bit è perso bisogna ritrasmetterlo fino a corretta ricezione. Siccome i bit arrivano correttamente con probabilità 1-α, il rate effettivo di trasmissione è 1-α. In questo modo si raggiunge la capacità di 1-α con feedback

Il feedback quindi non consente di aumentare la capacità?..Risultato generale: il feedback non aumenta la capacità dei canali discreti senza memoria

1

0

1

01-α

1-α

αα e

In generale, se i campioni sono indipendenti sappiamo chel’informazione media associata a ciascun campione è H(X)Per n campioni è quindi pari a nH(X)

Ma quanta di questa informazione passa attraverso il canale, cioèquanto vale l’informazione (o incertezza) su X una volta osservato y?Si ha che l’incertezza residua su X é:

H X | y( ) = E − log p X | y( )( )⎡⎣ ⎤⎦ = − p x | y( )x∑ log p x | y( )( )

Capacità del canale discreto

che mediata su tutti possibili valori di Y vale:

H X /Y( ) = H X / y( )y∑ = − p x / y( )log p x / y( ) p y( )

x∑

y∑ =

= − p x, y( )log p x / y( )x∑

y∑

ENTROPIA CONDIZIONATA o EQUIVOCAZIONE

In media, l’informazione che passa sul canale è quindi:

I X;Y( ) = H X( )− H X /Y( ) == H (Y )− H (Y / X)INFORMAZIONE MUTUA

Capacità del canale discreto

I X;Y( ) = H X( )− H X /Y( ) == − p x( )log p x( )

x∑ + p x, y( )log p x / y( )

x∑

y∑ =

= − p x( )log p x( )x∑ + p y / x( ) p x( )log p x / y( )

x∑

y∑ =

= p x( ) p y / x( )log p x / y( )p x( )y

∑x∑ =

= p x( ) p y / x( )log p y / x( ) p x( )p x( ) p y / x( ) p x( )

x∑y

∑x∑ =

P A / B( )P B( ) = P B / A( )P A( )

Capacità del canale discreto

I X;Y( ) = p x( ) p y / x( )log p y / x( )p y / x( ) p x( )

x∑y

∑x∑

Si ha quindi

Espressione di I(X,Y) in funzione di:➤ Probabilità di transizione del canale➤ Probabilità dei simboli di sorgente, dipendenti dal codificatore

di trasmissione

Capacità del canale discreto

Capacità di canale

CS = maxp x( )I X;Y( )

Si definisce la capacità per simbolo

Se il canale è utilizzato s volte in un secondo, si ottiene la capacità dicanale in bit/s:

C = sCS

Capacità di canale sul simbolo espressa in bit/simbolo, dove ogni simbolo è una

realizzazione di X

Capacità di canale in bit/s

Proprietà della capacità di canale

C ≤ log X datoche C = max I(X;Y ) ≤maxH (X) = log X

C ≥ 0 datoche I(X;Y ) ≥ 0

C ≤ log Y idem

I(X;Y ) èuna funzionecontinuadi p(x)

I(X;Y ) èuna funzioneconcavadi p(x)

Definizioni

CodiceUn codice (M,n) per un canale (X, p(x/y, Y) consiste in:1. Un insieme di indici {1,2,…,M}2. Una funzione di codifica Xn: {1,2,…,M}à Xn, che

produce le parole di codice xn(1), xn(2),…,xn(M). L’insieme delle parole di codice è detto codebook

3. Una funzione di decodifica g: Ynà{1,2,…,M}, deterministica, che a ogni vettore ricevuto un’ipotesi su quanto trasmesso

Massima probabilità di errore per un codice

!!λ(n) = max

i∈ 1,2,...,M{ }λi = max

i∈ 1,2,...,M{ }Pr g(Y n)≠ i / Xn = xn(i){ }

Teorema sulla capacità di canale

Il teorema fornisce un limite : anche se R<C, non è detto che si riesca aindividuare il codice che consente di arrivare prossimi a C:

➤ Complessità computazionale➤ Tempo di elaborazione

Per un canale discreto senza memoria tutti i rate inferiorialla capacità sono raggiungibili, ovvero per ogni rate R<Cesiste una sequenza di codici (2nR,n) con massimaprobabilità di errore che tende a zero !!λ(n)→0

Interpretazione

Xn Yn

Per ogni sequenza tipica di ingresso vi sono 2nH(Y/X) possibili sequenze in Y tutte con stessa probabilitàVorremmo che due sequenze di ingresso non producano la stessa sequenza in uscita

Interpretazione

Xn Yn

Questi insiemi devono essere disgiunti

Dato il numero totale di possibili sequenze Y !!≈2nH(Y )

Possiamo dividere questo insieme in tante parti di dimensione !!2nH(Y/X )

Corrispondenti alle diverse sequenze di ingresso X

Il numero totale di insiemi disgiunti è inferiore o uguale a !!2nH(Y )2nH(Y/X ) =2

n(H(X )−H(Y/X )) =2nI(X ;Y )

!!2n(H(X )−H(Y/X ))!!2n(H(X )−H(Y/X ))

Quindi è possibile trasferire un numero di sequenze distinguibili pari al più a !!≈2nI(X ;Y )