1) Probabilità di errore di trasmissione 2) Capacità di ... · Capacità del canale BSC Si...

Argomenti della LezioneArgomenti della Lezione

1) Probabilità di errore di trasmissione

2) Capacità di canale

3) Esempi di calcolo della capacità

4) Disuguaglianza di Fano

Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata

1

4) Disuguaglianza di Fano

5) Teorema inverso della codifica di canale

Probabilità di errore nella trasmissione attraverso un canaleProbabilità di errore nella trasmissione attraverso un canale

� Si consideri un canale di comunicazione discreto e senza memoria

con ingresso la variabile aleatoria discreta X e con uscita la

variabile aleatoria Y e con NX=NY=N.

� In un canale di questo tipo si può mettere in relazione il simbolo in

ingresso xi con il simbolo in uscita yi.

� Definiamo la variabile aleatoria di errore E come la variabile


2

aleatoria binaria che assume valore se si verifica l'evento

congiunto {X=xi,Y=yj} con i ≠ j e assume valore se si

verifica l'evento congiunto {X=xi,Y=yj} con i=j

� Si può quindi definire la probabilità di errore come:

_

eE =

eE =

∑∑=

≠=

∆

===N

i

N

ijj

ji yxPePeEP1 1

),()()(

Probabilità di errore nella trasmissione attraverso un canaleProbabilità di errore nella trasmissione attraverso un canale

� Si noti che la probabilità di errore può essere definita solo per un

canale con NX=NY.

� La probabilità di errore dipende sia dalle probabilità di transisione

del canale (e quindi dalla matrice P) sia dalla massa di probabilità

della variabile aleatoria X di ingresso al canale.


3

La capacità C di un canale discreto senza memoria viene definita

come il massimo flusso di informazione al variare della

distribuzione di probabilità dell’alfabeto di ingresso, ovvero:

);(max)(

YXICxP

∆

=

Capacità di un canale discreto senza memoriaCapacità di un canale discreto senza memoria


4

Per come è definita la capacità di canale, essa non dipende dalla

massa di probabilità della variabile aleatoria X di ingresso, ma

dipende soltanto dalle probabilità di transizione sul canale (e quindi

dalla matrice P).

)( ixP

� L'unità di misura della capacità è bit/simbolo o bit/channel use.

� Si dimostrerà che non si può avere una trasmissione affidabile

attraverso il canale se il numero medio di bit per simbolo di

canale eccede la capacità del canale (Teorema inverso della



5

codifica di canale).

� La capacità di canale è limitata superiomente da:

� Il calcolo analitico della capacità C è difficoltoso nella maggior

parte dei casi.

{ }YXxP

NNCi

22)(

log,logmin≤

� Sia T il periodo di simbolo ed R=1/T la frequenza di trasmissione;

attraverso il canale viene trasmesso un simbolo ogni T secondi.

� Definiamo capacità per secondo di un canale discreto senza

memoria la quantità:



6

CRT

CCB ⋅==

∆

Un canale uniforme in genere non è simmetrico.

Ricordiamo il teorema: la H(Y|X) di un canale uniforme è indipendente

dalle probabilità di ingresso ed è data da:

Capacità di un canale uniformeCapacità di un canale uniforme

simbolobitqqqHq

qXYHYY

Y

NN

N

j j

j /),...,,(1

log)|( 21

1

=

=∑

=

∆


7

in cui ogni riga della matrice di canale è una permutazione dello

stesso insieme di probabilità qj, j=1,...,NY.

Di conseguenza la capacità di un canale uniforme è data da:

[ ] ),...,,()(max)|()(max 21)()( YY

ii

NNxPxP

qqqHYHXYHYHC −

=−=

Per un canale simmetrico si comunque applicare il precedente

teorema su H(Y|X) valido per un canale uniforme e scrivere:

Di conseguenza massimizzare:

I(X;Y) = H(Y) - H(Y|X)

Capacità di un canale simmetricoCapacità di un canale simmetrico

simbolobitqqqHq

qXYHYY

Y

NN

N

j j

j /),...,,(1

log)|( 21

1

=

=∑

=

∆


8

I(X;Y) = H(Y) - H(Y|X)

significa massimizzare H(Y).

Per canale simmetrico ricordiamo che dal Teorema enunciato in

precedenza, una distribuzione uniforme in ingresso produce una

distribuzione uniforme in uscita. Di conseguenza:

[ ]

),...,,(log

),...,,()(max)|()(max

21

21)()(

YY

YYii

NNY

NNxPxP

qqqHN

qqqHYHXYHYHC

−=

=−

=−=

� Canale simmetrico con matrice:

� la capacità è data in generale da:

( )∑−=YN

jjY qqNC 22 1loglog

=

3/13/16/16/1

6/16/13/13/1P

Esempio di calcolo di capacità per un canale simmetricoEsempio di calcolo di capacità per un canale simmetrico


9

� nell’esempio NY = 4 , e si ha:

( )∑=

−=j

jjY qqNC1

22 1loglog

simbolobitC /082.06

1log

6

1

3

1log

3

122 22 ≅

++=

� Per un canale simmetrico di ordine N e probabilità di errore p in cui:

NX = NY = N

le righe e le colonne di P sono in questo caso permutazioni

degli N numeri:

≠−

=−=

jiNp

jippij

),1/(

),1(

Capacità di un canale simmetrico di ordine Capacità di un canale simmetrico di ordine NN


10

degli N numeri:

Pertanto la capacità di questo canale è:

−−−

1,...,

1,1

N

p

N

pp

−+−−+=

1log)1(log)1(log 222

N

ppppNC

Capacità del canale non rumorosoCapacità del canale non rumoroso

� Ricordiamo che per un canale non rumoroso si ha NX=NY=N e:

1altrimenti,se0 ,, =≠= iiji pjip

H(X|Y) = 0

H(Y|X) = 0

H(X,Y) = H(X) = H(Y)


11

H(X,Y) = H(X) = H(Y)

[ ] NYHXYHYHCii xPxP

2)()(

log)(max)|()(max =

=−=

� La capacità si calcola facilmente come:

Capacità del canale inutileCapacità del canale inutile

� Si ricordi che per un canale inutile si ha NX = NY = N ed i simboli

d’uscita sono indipendenti da quelli d’ingresso, ovvero:

)()|( jij yPxyP =

H(X|Y) = H(X)

H(Y|X) = H(Y)


12

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

[ ] 0)|()(max)(

=−= XYHYHCixP

� La capacità risulta:

Capacità del canale BSCCapacità del canale BSC

� Si ricordi che un canale binario simmetrico è un canale con

NX=NY=2 e con la seguente matrice di probabilità di transizione:


13

)1(log)1(log1)(1),...,,(log 222212 rrrrrHqqqHNCYY NNY −−++=−=−=

� Utilizzando il risultato sulla capacità di un canale simmetrico,

capacità del canale BSC risulta:

Capacità del canale BSCCapacità del canale BSC

� La capacità del canale BSC si ottiene per ingresso con distribuzione

uniforme e quindi per P(x1)=P(x2)=1/2. La capacità del canale BSC è

una funzione della probabilità di inversione r.

� Per un canale BSC la probabilità di errore è indipendente dalla

distribuzione di probabilità dei simboli d'ingresso ed è:

N N

==∑∑∆


14

NOTA: per la simmetria del canale

si ha H2(r) = H2(1-r), e quindi: CBSC(r)

= CBSC(1-r)

La trattazione del canale BSC va

ristretta al caso in cui: 0 ≤ r ≤ 1/2,

P(e) ≤ 1/2. Capacità del BSC in funzione della probabilità di errore r

r

ryxPePN

i

N

ijj

ji ==∑∑=

≠=

∆

1 1

),()(

Capacità del canale BECCapacità del canale BEC

� Si ricordi che un canale binario a cancellazione ha due ingressi e tre

uscite ed è caratterizzato dalla seguente matrice delle probabilità di

transizione:

Ponendo P(x ) = q è stato calcolato in precedenza:


15

� Ponendo P(x1) = q è stato calcolato in precedenza:

H(Y) = – [ r log r + (1 – r) log(1 – r) + q (1 – r) log q + (1 – q )(1 – r) log(1 – q) ]

= H2(r) + (1 – r)H2(q)

H(Y|X) = H2(r)

Da cui:

[ ] rqHrXYHYHCqxP

−=

−=−= 1)()1(max)|()(max 2

)(

Capacità di un canale BECCapacità di un canale BEC

� La capacità del canale BEC si ottiene per ingresso con

distribuzione uniforme e quindi per P(x1)=q=1/2. La capacità del

canale BEC è una funzione della probabilità di cancellazione r.

1

C


16

r1

1

0

Capacità di canali in cascataCapacità di canali in cascata

� La capacità del canale equivalente costituito dalla cascata di

due canali discreti e senza memoria è limitata superiormente:

{ }21,min CCCequiv ≤


17

Canale 1 Canale 2X Y Z

� Sia H(X|Y) che P(e) possono essere usate come misura della qualità

del canale, e sono tra loro dipendenti.

� Definiamo la variabile aleatoria di errore E come la variabile aleatoria

binaria che assume valore se si verifica l'evento congiunto

{X=xi,Y=yj} con i ≠ j e assume valore se si verifica l'evento

congiunto {X=xi,Y=yj} con i=j

Disuguaglianza di FanoDisuguaglianza di Fano

_

eE =

eE =


18

congiunto {X=xi,Y=yj} con i=j

� L’entropia d'errore H(E) è definita come l'entropia della v.a. errore E:

� H(E) è la quantità di informazione necessaria per specificare se è

occorso un errore su un canale con probabilità d’errore P(e) data da:

[ ] [ ])(1log)(1)(log)()( 22 ePePePePEH −−−−=

∑∑=

≠=

∆

===N

i

N

ijj

ji yxPePeEP1 1

),()()(

Teorema (di Fano): dato un canale discreto senza memoria, con:

NX = NY = N e con probabilità d’errore P(e), vale la seguente

disuguaglianza di Fano:

)1(log)()()|( 2 −+≤ NePEHYXH



ovvero:

19

[ ] [ ])(1log)(1)(log)()1(log)()|( 222 ePePePePNePYXH −−−−−≤

1) Se si rivela che non c’è

stato errore, l’incertezza

residua H(X|Y) riguardo il

Interpretazione intuitiva: rilevare l’occorrenza di un errore alla

ricezione del simbolo y ∈ Y rimuove un’incertezza H(E)

H(E) + P(e) log2(N-1)



20

simbolo trasmesso è zero

2) Se si rivela che c’è stato un

errore, occorre decidere quale

dei rimanenti (N-1) simboli sia

stato trasmesso; l’incertezza

residua non eccede log2(N-1)H(X|Y) ≤ H(E) + P(e) log2(N-1)

Regione permessa per

le coppie P(e), H(X|Y)

� Dal teorema sulla disuguaglianza di Fano possiamo derivare

anche un altro risultato.

� Poiché H(X|Y) = H(X) - I(X;Y), la disuguaglianza di Fano

fornisce un limite inferiore alla probabilità di errore in termini

di eccesso d’entropia dell’alfabeto X d’ingresso rispetto al

Teorema inverso della codifica di canaleTeorema inverso della codifica di canale


21

di eccesso d’entropia dell’alfabeto X d’ingresso rispetto al

flusso informativo attraverso il canale:

H(X) - I(X;Y) ≤ f (P(e), N) = H(E) + P(e)log2(N-1)∆

Considerando che: I(X;Y)=H(X)-H(X|Y) e che I(X;Y)≤ C,

allora: H(X) - H(X|Y) ≤ C e cioè H(X) - C ≤ H(X|Y), e applicando

la disuguaglianza di Fano al secondo membro si ha:

H(X) - C ≤ H(E) + P(e)log2(N-1)



22

Curva: C + H(E) + P(e)log2(N-1)

H(X) ≤ C + H(E) + P(e)log2(N-1)

Regione permessa per

le coppie P(e), H(X)

Grafico della funzione C+H(E)+P(e)log2(N-1) in funzione di P(e)

� NOTA: la regione di coppie consentite ( P(e), H(X) ) contiene punti

con ascissa P(e) = 0 solo se H(X) ≤ C

� Teorema inverso della codifica: se l’entropia dell’alfabeto d’ingresso



23

� Teorema inverso della codifica: se l’entropia dell’alfabeto d’ingresso

H(X) eccede la capacità di canale C è impossibile trasmettere

informazione attraverso il canale con probabilità d’errore P(e)

arbitrariamente piccola

� Se si identifica l’alfabeto di ingresso del canale con l’alfabeto di

uscita del codificatore di sorgente, la situazione descritta

corrisponde ad un sistema di comunicazione dove i simboli

all’uscita del codificatore di sorgente sono inviati direttamente

attraverso il canale, senza effettuare la codifica di canale.



24

� Verrà in seguito incluso il codificatore di canale nel sistema e

verranno estesi i risultati precedenti.

1) Probabilità di errore di trasmissione 2) Capacità di ... · Capacità del canale BSC Si...

Documents

Transcript of 1) Probabilità di errore di trasmissione 2) Capacità di ... · Capacità del canale BSC Si...