STII Probabilità e proprietà dei logaritmi - Luca Costante STII.pdf · Probabilità e proprietà...

Giardino Daniele – Costante Luca

1

STII

Durante una trasmissione, il segnale naviga alcuni minuti prima di arrivare a destinazione. Durante il

percorso, il segnale è soggetto a rumore, quindi può capitare che il messaggio che è stato inviato (espresso

in bit) sia diverso da quello ricevuto. Ci chiediamo come mai riusciamo a ricevere i dati così come sono stati

trasmessi? La risposta è semplice, non si trattano i dati direttamente, ma solo dopo averli trasformati:

bisogna eliminare la ridondanza (efficienza) ed aggiungere ridondanza utile (per la protezione dal rumore).

Probabilità e proprietà dei logaritmi

Valore medio di una variabile casuale:

Consideriamo 2 V.C. X,Y, abbiamo

o Prob. congiunta :

o

o

o

Disuguaglianza di Markov:

Chernoff Bound: sia v.c. iid (indipendenti ed identicamente distribuite) con valore medio ,

allora

Legge debole dei grandi numeri: sia v.c. iid (indipendenti ed identicamente distribuite) con

valore medio ,

Informazione associata al valore x:

Logaritmo

Derivata:


2

Funzione concava/convessa

f è strettamente concava se la disuguaglianza è stretta

per . Il log è una funzione strettamente concava

di x.

Disuguaglianza di Jensen:

Dim. La dimostrazione avviene per induzione sulla .

Base: =2. Si consideri

, per la definizione di funzione concava si ha che

Passo induttivo. Supponiamo che la disuguaglianza sia verificata per =k-1, dimostriamo

che è verificata per =k.


3

Entropia (è il numero di bit per rappresentare l’informazione)

Misura l’incertezza di una variabile casuale X. Può essere vista anche come l’informazione che otteniamo in

media conoscendo il valore di X. Poiché l’unità di misura sono i bits, usiamo il log in base 2.

(informazione emessa alla sorgente)

Indichiamo con H(X) l’Entropia e si calcola:

Come si può facilmente vedere, eventi poco probabili danno maggiore informazione. L’entropia non

dipende dall’alfabeto ma solo dalla sua distribuzione di probabilità. Il massimo dell’entropia si ha quando

gli M simboli dell’alfabeto sono equiprobabili ossia . L’unità di misura dell’entropia sono i

bits. Se si cambia la base del logaritmo, il valore dell’entropia cambia solo di un fattore costante. Quindi

Dim:

Con l’entropia, è possibile anche calcolare il numero di domande necessarie per poter “indovinare” un

numero a partire da un insieme di numeri.

Sia , in media il numero di domande è

.

In generale il minimo numero medio di domande del tipo è compreso tra e .

Il termine nullo non incide nel valore dell’entropia. Logicamente un simbolo con probabilità 0 è sicuro non

verificarsi mai. Quindi l’entropia che misura l’incertezza del verificarsi di tale simbolo non ha significato.

Entropia binaria di Bernulli: Nel caso di soli due valori della V.C. si parla di entropia binaria o di Bernulli:

Entropia Congiunta: date due v.c. X ed Y con distribuzione di probabilità congiunta p(x,y), si definisce


4

Entropia Condizionata: rappresenta l’informazione addizionale media di Y nota X. Date due v.c. X ed Y

con distribuzione di probabilità condizionata p(y/x), si definisce

Dim:

Regola della catena:

Dim:

Proprietà

1.

Dim. Sappiamo che

. Inoltre

e tutte le altre )

2. . Dimostriamo questa proprietà tramite la disuguaglianza di Jensen.

3.


5

4.

a.

b.

c.

d.

5.

La disuguaglianza di Jensen vale con il segno di “ ” s se

.

Sommando su y abbiamo , quindi

s.se X,Y sono indipendenti.

6.

Dim.

7.

Estensione regola della catena

La dimostrazione avviene per induzione su n:

(BASE n=2), applicando la regola della catena abbiamo

(INDUZIONE assumendo vero per n-1, si prova per n)


6

Mutua Informazione

La mutua informazione rappresenta i bit di informazione che una delle variabili fornisce circa l’altra. Ci dice

di quanto decresce l’incertezza su X una volta vista Y.

Mutua Informazione Condizionata: Il condizionamento di Z si applica sia ad X che ad Y

Dato che

Regola della catena per la Mutua Informazione:

PROPRIETA’

Se X ed Y sono indipendenti,


7

Dim:

Divergenza informazionale

Misura la somiglianza tra le distribuzioni di probabilità p(x) e q(x). Quindi date due distribuzioni di

probabilità p(x) e q(x), la divergenza informazionale o entropia relativa è definita come

. Inoltre la divergenza informazionale non è simmetrica,

Abbiamo che

Date due v.c. X e Y con probabilità congiunta p(x,y), la mutua informazione corrisponde all’entropia relativa

tra e :

Questa divergenza misura la differenza tra la distribuzione di probabilità congiunta p(x,y) e la distribuzione

quando le variabili casuali sono .


8


9

Teorema del data processing

Catene di Markov:

Dati X,Y,Z con formano una catena di Markov

1. Se

2. Se

Teorema:

1)

2)

Dim:

Poiché ,

Da cui

Quindi abbiamo dimostrato che

Disuguaglianza di Fano

Siano X e Y variabili casuali. Vogliamo stimare X dall’osservazione di Y. Definiamo

Teorema:

Dim.

Con

1)= lg( 1) poiché l’entropia è sempre minore uguale del numero di valori.


10

Compressione dati

Abbiamo una sorgente X che emette simboli vogliamo rappresentarli con simboli.

Vogliamo rappresentare sequenze sorgente di lunghezza n in sequenze codice di lunghezza N. Lo scopo

della compressione è quello di minimizzare la quantità di dati da trasmettere, eliminando la ridondanza.

L’entropia fornisce un limite sia inferiore che superiore al numero di bit per rappresentare dati.

Notazione:

Codifica univoca: se vogliamo una codifica univoca, ogni simbolo della sequenza sorgente deve essere

codificata da un simbolo codice.

Un codice è detto non singolare se ad ogni viene assegnata una diversa stringa in , cioè

L’estensione k-esima Ck di un codice C è una funzione che associa ad ogni

Un codice si dice univocamente decodificabile UD se la sua estensione è non singolare (interessano tali

codici perché come si comprime così si vuole decomprimere). Associare a parole sorgente diverse, parole

codice diverse non garantisce la decodifica univoca di sequenze di parole di codice. Quindi, per vedere se

un codice è univocamente decodificabile, devo leggere tutta la sequenza e controllare se alla fine riesco a

determinare l’univocità della decodifica. In questo caso, si parla di ritardo di decodifica. Un codice si dice

prefisso se nessuna parola codice è prefissa di un’altra. Un codice prefisso è univocamente decodificabile

con ritardo finito (il ritardo è dato dalla lunghezza della parola codice più lunga).

A un codice D-ario C prefisso corrisponde un albero D-ario dove i rami dell’albero sono etichettati con le

lettere dell’alfabeto e ogni parola di C è ottenuta leggendo le etichette dei rami lungo il percorso dalla

radice ad una foglia.


11

Disuguaglianza di KRAFT

La disuguaglianza di KRAFT lega la lunghezza delle parole codice alla cardinalità dell’alfabeto.

(PARTE DIRETTA): Per ogni codice prefisso D-ario, le lunghezze delle parole codice soddisfano:

Sia C il codice prefisso D-ario con lunghezza delle parole codice . Sia la lunghezza massima

delle parole di C (corrisponde all’altezza dell’albero T D-ario associato al codice C, dove il numero di foglie di

T è ).

Per ogni lunghezza dobbiamo eliminare

un sottoalbero di altezza . Quindi per ogni i,

eliminiamo dall’albero foglie. In totale

eliminiamo foglie. Poiché il numero di

foglie eliminate non può superare il numero totale di

foglie, abbiamo che

(PARTE INVERSA): Se soddisfano la disuguaglianza di Kraft, allora esiste un codice prefisso D-ario

le cui parole hanno lunghezza .

Supponiamo che soddisfano la disuguaglianza di Kraft e che . Consideriamo l’albero

D-ario completo di altezza . Lo trasformeremo in un albero che rappresenta un codice D-ario prefisso con

parole lunghe :

1. Prima di tutto etichettiamo i rami uscenti da ciascun nodo interno con gli interi .

2. Per ogni i=1,…,m,

o Consideriamo il primo nodo disponibile di profondità (primo secondo l’ordine

lessicografico delle parole che si leggono andando dalla radice ai nodi)

o Eliminiamo il sottoalbero di questo nodo dall’albero ed associamo alla foglia che abbiamo

appena creato la parola codice i

Eliminiamo foglie

Al passo i-esimo in totale abbiamo eliminato foglie


12

Es: sia D={0,1,2}; gli interi 1,2,2,2,2,2,3,3,3 soddisfano la disuguaglianza di Kraft. In questo caso =3

i=1, eliminiamo foglie, ossia

i=2, eliminiamo foglie, ossia

e così via

Quindi il numero di foglie eliminate nei primi i passi (con i<m) è:

Ora possiamo eseguire il passo (i+1)-esimo. Infatti il numero di foglie rimaste dopo il passo i

Disuguaglianza di Mc Millan

Le lunghezze delle parole di un codice Univocamente Decodificabile soddisfano la disuguaglianza di Kraft.

DIM. Sia C codice UD (vuol dire che la sua estensione è non singolare)

Sia

Se avessimo , allora

, per k grande (contraddizione). Quindi

, e C soddisfa la disuguaglianza di Kraft.

Conseguenze: abbiamo dimostrato che la disuguaglianza di Kraft vale anche per i codici UD e quindi per un

qualsiasi codice UD esisterà un codice prefisso avente parole della stessa lunghezza, quindi possiamo

limitarci a considerare solo codici prefissi che non hanno ritardo di decodifica.


13

Lunghezza media di un codice

La lunghezza media L (C) di un codice C per una v.c. X con d.d.p. P(x) è data da

La lunghezza media L di un codice D-ario UD per una vc X soddisfa

DIM :

Si ha l’uguaglianza s.se

Ora ci chiediamo se

non sono tutti interi? A tal proposito quindi, vediamo quanto la lunghezza

media può discostarsi dall’Entropia.

Codice di Shannon

Consideriamo X con d.d.p. . Il codice di Shannon D-ario è un codice prefisso che assegna al

simbolo di probabilità una parola codice di lunghezza

. Il codice di

Shannon esiste in quanto le lunghezze soddisfano la disuguaglianza di Kraft:

La lunghezza media è < :

Quando si effettuano i calcoli, basta un solo caso in cui il calcolo del logaritmo non da risultato intero che

vale la disuguaglianza ossia che

Codifica ottimale

Siano

le lunghezze delle parole di un codice UD ottimo D-ario per una v.c X con d.d.p. .

La lunghezza media


14

Dim: ogni codice UD soddisfa la prima disuguaglianza. Per quanto riguarda invece la seconda

disuguaglianza, sia C il codice di Shannon D-ario per X tale che . La lunghezza media

del codice ottimale soddisfa

Costruzione codici prefissi ottimali (binari)

Per ogni d.d.p. p esiste un codice prefisso ottimo tale che:

1. Se > allora

2. Le due parole più lunghe hanno la stessa lunghezza

3. Le due parole più lunghe differiscono solo nell’ultimo bit

Dim: siano . Sia C codice ottimo con lunghezze

1. Supponiamo per assurdo che > allora . Consideriamo il codice C’ ottenuto da C

scambiando la parola j-esima con quella k-esima, ossia

La lunghezza media di C’ è . La differenza tra L’ e la lunghezza media L

di C è:

Ricordando che > ma , allora L’<L che è impossibile, quindi

2. Supponiamo per assurdo che C contenga un’unica parola di lunghezza massima . Possiamo

quindi eliminare l’ultimo bit dalla parola codice di ottenendone una di lunghezza .

Otteniamo così un codice prefisso con lunghezza media inferiore ad L. Questo è impossibile in

quanto C è ottimo

3. Se valgono la 1 e la 2, allora

In generale non è vero che un codice ottimale soddisfa la 3.

Supponiamo che e non differiscono solo nell’ultimo bit, allora i nodi associati a

e non sono fratelli, quindi ha fratello con , allora

.

Possiamo quindi scambiare e ottenendo un codice con lunghezza uguale a quella di C.


15

Algoritmo di Huffman

Viene utilizzato per la costruzione di codici ottimali. L’algoritmo viene definito ricorsivamente

1) Si prendano le due (oppure d in caso di codice D-ario) probabilità più piccole e si assegni a ciascuna

un ultimo bit differente. Si faccia il merge dei simboli corrispondenti alle due probabilità più piccole

in un unico simbolo

2) Ripetere il passo 1 fino ad avere 1 simbolo. Non è sempre possibile raggruppare le probabilità in

gruppi di D, in tal caso aggiungiamo tanti

simboli fino a quando non si forma un gruppo

e ogni simbolo ha probabilità zero.

Formalmente: Codice per

è definito a partire da , il codice per

( simbolo di concatenazione, l’alfabeto è D-ario)

Ottimalità dei codici di Huffman. Tale dimostrazione avviene per induzione sul numero m di simboli da

codificare.

BASE: per m=2, si ha che è ovviamente ottimo.

PASSO INDUTTIVO:

indipendente da lunghezze del codice per cui (sapendo che in codice ottimale

) abbiamo che se è ottimo, allora anche è ottimo.

poiché i codici di Huffman sono prefissi e ottimali, allora la lunghezza di un codice di Huffman C*

soddisfa


16

Ricordiamo che un albero D-ario pieno ha nodi. Se non è nella forma ,

aggiungiamo simboli fino ad arrivare all’intero più vicino ad di questa forma.

Ritornando al gioco delle domande citato sopra, le domande equivalgono al codice ossia le domande

equivalgono ad una sequenza di risposte cioè ad una codifica binaria di oggetti. Il codice invece rappresenta

l’i-ma domanda: “è il bit i-mo=1?”. Quindi


17

Compressione dati

Compressione dati con distribuzione di probabilità non esatta

Sia p(x) la probabilità reale (non nota), q(x) la stima di p(x) ottenuta da rilievi statistici. Ci chiediamo: se la

codifica si basa su q(x), di quanto aumenta la lunghezza media per simbolo rispetto a quella che avremmo

ottenuto utilizzando la distribuzione reale p(x)?

Teorema:

: lunghezza media del codice di Shannon con lunghezze

. Risulta

Dim:

Analogamente possiamo dimostrare il limite inferiore

Migliore è la stima q(x), minore è la divergenza e migliore è la lunghezza media.

Compressione di sequenze Abbiamo visto che la lunghezza media L* di un codice ottimo soddisfa , quindi se

codifichiamo un simbolo sorgente alla volta, il limite superiore al numero medio di bit per simbolo sorgente

differisce di al più un bit dall’entropia. Cosa succede se invece di codificare ciascun simbolo separatamente,

codifichiamo sequenze di simboli sorgente?

Sia la sequenza composta da n simboli emessi dalla sorgente, con n v.c. e d.p. congiunta

. Indichiamo con

: la lunghezza della parola codice associata a .

numero medio di simboli codice per simbolo sorgente, ovvero

.

Poiché la sommatoria è il numero di bit che usiamo per codificare n simboli, ho diviso per n in

modo da ottenere il numero medio di simboli codice per simbolo sorgente.

: minimo numero medio di simboli codice per simbolo sorgente.

Teorema di codifica di sequenze sorgente

Il minimo numero medio di simboli codice per simboli sorgente soddisfa


18

DIM: ciascuna sequenza può essere vista come un “supersimbolo” dell’alfabeto . Possiamo

quindi considerare la codifica ottimale di :

poichè

, ossia dividendo per n otteniamo il risultato voluto

OSSERVAZIONE: se la sorgente è senza memoria, cioè sono indipendenti ed identicamente

distribuiti come X, allora

In generale, se

, allora

. Quindi codificando sequenze

sorgente con codici prefissi possiamo ottenere un numero medio di simboli codice per simbolo sorgente

arbitrariamente prossimo all’entropia.

Compressione dati

Il nostro obiettivo è quello di riuscire a codificare sequenze sorgente lunghe n in sequenze codice lunghe N

con un rapporto di compressione migliore di quello ottenuto, cercando di mantenere basso l’errore.

La sorgente emette sequenze di simboli in alfabeto che vengono codificati come sequenze di simboli di

un alfabeto D-ario. Consideriamo il caso più semplice in cui la sorgente è senza memoria, ossia la sequenza

di v.c. indipendenti ed identicamente distribuite come v.c. X.

Per la legge debole dei grandi numeri:

se sono n v.c. i.i.d., allora

Proprietà di equipartizione asintotica (PEA- AEP)

Se sono v.c. i.i.d., con d.d.p. , allora

= probabilità di osservare la sequenza

Ciò significa che se facciamo crescere di molto la lunghezza della sequenza, l’informazione media di una

sequenza sorgente si discosta molto dall’entropia con probabilità bassa.


19

DIM:

Sequenze tipiche

Sia:

S: sorgente modellata con una sequenza di n v.c. , i.i.d. con alfabeto

: insieme delle sequenze di lunghezza n emesse da S. Tale insieme può essere partizionato in:

o : insieme delle sequenze tipiche di lunghezza n costituito da tutte le sequenze

t.c

o complemento di

in

Dimostreremo che l’insieme ha probabilità . Tale insieme non contiene tutte le sequenze: per

codificare sequenze sorgente, non servono bits, sono sufficienti

Proprietà delle sequenze tipiche

1.

DIM:

è ovvia per la definizione di sequenze tipiche e dalla PEA

2.

DIM:

Per la proprietà di equipartizione asintotica (PEA), allora

3.

DIM:

4.

DIM:

Per n sufficientemente grande abbiamo


20

TEOREMA DI CODIFICA SORGENTE Th: Sia sequenza di v.c. i.i.d. con d.d.p. . Sia . Esiste un codice che mappa sequenze sorgente

di lunghezza n in stringhe binarie in modo che la codifica sia 1-1 e

DIM SE :

se vogliamo ottenere un rapporto di compressione migliore sfruttando le proprietà delle sequenze tipiche

possiamo fare in questo modo:

Partizioniamo l’insieme di tutte le sequenze negli insiemi

.

Ordiniamo ciascuno dei due insiemi

(ad esempio in modo lessicografico)

Rappresentiamo ciascuna sequenza con il suo rango (posizione) nell’ordinamento

o Il numero di bit necessari per codificare le sequenze tipiche è

o Il numero di bit necessari per codificare le sequenze non tipiche è al più

Il codice viene così definito:

codifica sequenza tipica: alla sequenza binaria corrispondente aggiungiamo 0 come prefisso

codifica sequenza non tipica: alla sequenza binaria corrispondente aggiungiamo 1 come prefisso

a ciascuna sequenza sorgente è associata una parola codice distinta (codifica lossless)

la lunghezza della parola codice è :

A quanto corrisponde la lunghezza media del codice?

Sia di lunghezza n.

Con

Allora

DIM SOLO SE :

il teorema di codifica sorgente ci dice che possiamo codificare le sequenze usando bit. Ci si

chiede se si può fare di meglio, ossia se esiste un insieme più piccolo dell’insieme tipico che concentra la

massa probabilistica? La risposta è no ed ora mostriamo il perché.

Dato

. Dimostreremo che deve avere un’intersezione

significativa (molte sequenze in comune) con

TH: Siano i.i.d con d.d.p. P(x). Per ogni

si ha


21

Dim:

Inoltre risulta

Quindi

NELLA PRATICA, ESISTE LA CODIFICA LEMPEL ZIV (LZ)

Per la codifica di sequenze, si legge la sequenza di sinistra a destra, si divide in parti in modo che ogni parte

è una parte precedente più un bit

Es: 1011010100010, diventa 1011010100010

Per sequenze di n bit, sia c(n) il numero di parti . La codifica di : puntatore

e bit addizionale b in modo che

Es:

1011010100010=1,0,11,01,010,00,10

, dove i primi 3 bit del carattere separatore “,”

stanno ad indicare l’indirizzo della parte . Il puntatore usa , nel nostro caso avendo 7 parti,

bits.

La lunghezza della sequenza compressa è circa

Questa codifica è molto usata in varie versioni: compress, gzip, ecc. nella pratica, la compressione ha un

ruolo fondamentale in quanti molti files contengono sequenze ripetute.

Sia n la lunghezza della sequenza, v.c. modella il simbolo i-esimo. LZ è asintoticamente ottimo per

sorgenti stazionarie ergodiche

. Si mostra che con n sufficientemente grande:

Una sequenza compressa di lunghezza circa


22

CODIFICA CANALE

La codifica sorgente codifica i dati per rimuovere ridondanza, mentre la codifica canale aggiunge

ridondanza per proteggere da errori di trasmissione sul canale. Si ha successo di trasmissione se i dati

inviati giungono correttamente alla destinazione. Un obiettivo fondamentale della codifica canale è quello

di avere input non confondibili e la capacità di poter correggere errori di trasmissione. Per questo motivo

vengono aggiunti bit ridondanti.

Canali discreti senza memoria

Un canale discreto è una tripla dove:

alfabeto di input al canale

: alfabeto di output al canale

: matrice delle probabilità di transizione

In un canale discreto senza memoria (DCM), la probabilità di output dipende solo da input corrispondente

NON da precedenti input o output.

Dato un canale discreto senza memoria, la capacità per n usi del canale è

Dove

Quindi . Ci concentreremo su ossia un singolo

uso canale. Dimostreremo che la capacità equivale al massimo numero di bit che possono essere trasmessi

per ogni uso del canale. La regola generale per il calcolo della capacità è .

Canale binario simmetrico:

quindi

, quindi la capacità

Canale binario con cancellazione:


23

Sia allora

, quindi

Canali simmetrici: ogni riga (rispettivamente colonna) è permutazione di ogni altra riga e

(rispettivamente colonna). Canali debolmente simmetrici: ogni riga è permutazione di ogni altra

riga; la somma su ogni colonna è costante. un canale simmetrico è anche un canale debolmente

simmetrico.

Sia

Ponendo

Quindi

Canale asimmetrico:

Sia

per trovare C massimizziamo

. sostituisco questo valore in f(p) ed ottengo

Codifica canale DCM (senza memoria)

Un codice canale (M,n) per è dato da:

1. Insieme di indici {1,…,M} (equivale a possibili sequenze input)

2. Funzione codifica

3. Funzione decodifica

Inoltre definiamo:

la probabilità di errore quando si codifica l’indice i con

Probabilità massima di errore:


24

Probabilità media di errore:

Tasso codice (M,n):

Il tasso R è ottenibile se esiste sequenza di codice

Attraverso il Teorema di Codifica Canale si dimostra che

o Ogni tasso è ottenibile

o Nessun tasso è ottenibile

La capacità C rappresenta il limite superiore di tutti i tassi ottenibili.

L’obiettivo è quello di avere codici che abbiano probabilità di errore prossima a 0 e tasso del canale alto.

Coppie tipiche

L’insieme

delle coppie tipiche rispetto alla distribuzione è definita da:

TEOREMA JOINT PEA

Siano sequenze di v.c. i.i.d. secondo . Allora

1.

2.

3. Se ed sono indipendenti e scelte secondo e , quindi ,

allora per

TEOREMA DI CODIFICA CANALE

Per ogni tasso , esiste una sequenza di codici con probabilità massima di errore .

La dimostrazione si basa sulle seguenti idee: analisi di sequenze lunghe, in modo da sfruttare la legge dei

grandi numeri e, specificamente, le proprietà delle coppie tipiche; calcolo della probabilità di errore

mediata su una scelta random del codice.

Dimostrazione parte diretta

Generiamo parole codice i.i.d. scegliendone i simboli da indipendentemente in accordo ad una

fissata d.p. .

Una sequenza è scelta con probabilità

Un codice

Con probabilità

Come descritto sopra il codice viene generato in maniera random. Il messaggio W da trasmettere viene

scelto uniformemente a caso:


25

La parola codice , corrispondente alla w-esima riga di C viene spedita sul canale. L’output del canale

è una sequenza (versione ottenuta dopo la trasmissione sul canale rumoroso) determinata in accordo

alla distribuzione

La sequenza viene decodificato come se formano una coppia tipica e quindi non esiste

un altro messaggio k t.c. formano una coppia tipica (ciò sta a significare che è l’unico

che forma una coppia tipica con ). Se non esiste un tale W o ce ne è più di uno, si emette un segnale di

errore. Dichiariamo la codifica errata se , e denotiamo con tale evento.

La probabilità di errore la si calcola mediata su tutte le parole del codice, e mediata su tutti i codici possibili,

quindi:

Poiché mediamo su tutti i codice non dipende da w. Infatti, guardando a tutti i codici, la

stessa parola appare lo stesso numero di volte con ogni indice. Quindi possiamo assumere, senza perdita di

generalità che l’indice del messaggio inviato sia W=1, poiché

Sia la sequenza output quando viene trasmesso (stiamo codificando W=1). Definiamo

“l’evento l’i-esima parola codice e formano una coppia tipica”:

Quando viene trasmessa, si ha errore se si verifica una delle seguenti condizioni:

(c’è più di una che forma una coppia tipica)

(caso in cui e non formano una coppia tipica)

Quindi

Consideriamo le 2 quantità separatamente. Si ha che:

, per (proprietà 1 di joint AEP)

e sono indipendenti, allora sono indipendenti . Allora

(proprietà 3 di joint AEP)

Otteniamo quindi

se scegliamo n sufficientemente grande e .

Se possiamo scegliere e n in modo da rendere la media (su tutti i codici) di

Cosa possiamo dire della probabilità massima di errore?

Scegliamo , cioè quella che ottiene la capacità.

quindi possiamo sostituire ad .


26

Se la media su tutti i codici di , allora esiste un codice tale che

.

Eliminiamo da ogni parola i con (sono meno della metà altrimenti

Allora

Creiamo un nuovo codice che contiene solo tali parole di con probabilità di errore piccola:

Tale codice contiene ovviamente parole, quindi il suo tasso è

che per n grande non differisce

significativamente da R.

Concludendo: per ogni , possiamo scegliere un codice di tasso

, con probabilità massima

di errore .

Dimostrazione parte inversa

Ci resta da dimostrare che per ogni sequenza di codici con .

Cominceremo con il dimostrare due lemmi che ci serviranno per la dimostrazione.

1.

LEMMA: sia l’output di un DMC per input . Allora per ogni distribuzione vale

DIM:

COROLLARIO: Sia l’output di un DMC per input . Allora ogni distribuzione

2.

Consideriamo un Canale discreto senza memoria (DMC). Sia il messaggio in input W scelto in

accordo alla distribuzione uniforme tra messaggi. Sia C il codice, la parola ricevuta in output

al canale, la funzione di decodifica e

. Allora

Definiamo

Espandiamo

Notiamo che


27

Ne consegue che

da cui segue la tesi in quanto ,

poiché è funzione di W.

DIM. PARTE INVERSA

Abbiamo che se , allora

Consideriamo il messaggio W scelto uniformemente in

Allora

Riscriviamo la disuguaglianza

Questo mostra che per la probabilità di errore si mantiene per . Questo deve valere per

ogni n, infatti se avessimo codice con

per n piccoli potremmo estenderli a codici di lunghezza

maggiore per concatenazione. In conclusione, non si può ridurre arbitrariamente la probabilità di errore

con tassi superiori alla capacità.

TEOREMA CODIFICA SORGENTE-CANALE

Se soddisfano la PEA allora esiste un codice sorgente-canale con

. Se

la probabilità di errore non può essere resa arbitrariamente piccola.

DIM. PARTE DIRETTA

Se vale la PEA, allora

e

Se codifichiamo solo sequenze tipiche allora abbiamo indici. Se possiamo

trasmettere sul canale con probabilità di errore . Quindi

DIM. PARTE INVERSA

Dalla disuguaglianza di Fano

Quindi


28

Per

si ha


29

CODICI A CORRETTORI D’ERRORE

In ogni trasmissione digitale possono avvenire degli errori. Senza metodi efficaci e veloci di correzione degli

errori non sarebbe possibile ricevere informazioni provenienti dallo spazio, usare un lettore cd con qualche

graffio ecc. Tendenzialmente, codifica e decodifica sono realizzate mediante hardware per essere più

performanti.

L'algoritmo più semplice è il controllo di parità. Ovvero data un'informazione da inviare, ad esempio “10”,

l'emittente aggiunge un bit così che il numero di uno sia pari: nel nostro esempio l’informazione inviata sarà

“101”. Il ricevente verifica se l'informazione ricevuta rispetta il controllo di parità, scarta l’ultimo bit e

processa il contenuto informativo, che è “10”. Nella realtà il ricevente, accantona l’ultimo bit, ricalcola il

valore di parità e lo compara con il ricevuto. Se sono diversi intercetta l'errore, e quindi richiede una

ritrasmissione. Notate che se ricevesse “000”, non si accorgerebbe dell'errore !! Questo significa che il

controllo di parità con ridondanza singola non si accorge di doppi errori, e comunque in caso di singolo

errore non sa correggerlo, sa solo identificarlo.

Cominciamo a porre le basi per capire come funzioni i codici di identificazione e correzione di errore con

controllo di parità: essi si chiamano Codici di Hamming.

Definiamo con l’alfabeto e con .

Si definisce Distanza di Hamming (d), dati due codici, il numero di bit differenti posizione per posizione. Ad

esempio d(101,010)=3. Tecnicamente la distanza di Hamming si ottiene facendo un XOR tra i due codici e

contando quanti uno ha il risultato.

Inoltre valgono le seguenti proprietà:

DEFINIZIONI

Un codice a correzione di errore è un sottoinsieme C di . La distanza minima di C è (minimo su

tutte le coppie di parole diverse in C)

C è e error detecting se può rilevare e errori

C è t error correcting se può correggere t errori

Se , C è 2t error detecting e t error correcting

DIM:

sequenza a distanza da parola codice non è in C

sequenza r a distanza da parola codice ha distanza almeno

da ogni altra parola codice (vale la disuguaglianza triangolare). Prendendo la parola codice più

vicino ad r correggiamo t errori, quindi è

è pairwise-indipendent t se per ogni e si ha


30

Codici lineari Un codice è lineare s.se esiste una matrice di controllo parità sull’alfabeto A tale che C è lo

spazio nullo di H, cioè

Codici di Hamming

Per garantire il rilevamento di un numero di errori minore o uguale a s, occorre un codice con distanza di

Hamming minima dmin s+1. Immaginiamo un codice con distanza di Hamming minima dmin = 2. Questo

codice garantisce il rilevamento di un solo errore. Per esempio, se la parola codice spedita è 101 e si verifica

un solo errore di trasmissione, la parola codice ricevuta non corrisponderà a nessuna parola codice valida.

Se si verificano invece due errori, la parola codice ricevuta potrebbe essere uguale a una delle parole codice

valide e quindi il ricevitore potrebbe non accorgersi degli errori. Per garantire la correzione fino a t errori, la

distanza di Hamming minima del codice che si utilizza deve essere dmin 2t+1. Per esempio, se uno

schema di codifica ha una distanza di Hamming dmin = 4 possiamo rilevare al massimo 3 errori ma ne

possiamo correggere 1 solo.

Sia . H è composta da vettori di bits, tranne quello di tutti 0,….0.

Il numero totale di parole codice è dove k viene così definito:

Es.

Definiamo con w(x)=peso di Hamming di x= numero di componenti di x non nulle;

LEMMA: dato un codice lineare C, w(C)= minimo numero di colonne linearmente dipendenti di H

DIM: H ha r colonne linearmente dipendenti in posizioni s.se esistono tali che

e s.se esiste una parola codice di peso r:

LEMMA: dato un codice lineare C, w(C)=d(C)

DIM:

COROLLARIO: un codice lineare C corregge t errori se

CODIFICA E DECODIFICA DEI CODICI DI HAMMING

Sia . H è composta da vettori di bits, tranne quello di tutti 0,….0.

Siano

Se vi sono 0 errori, allora

In pratica

G = matrice generatrice del codice

H = matrice di controllo di parità


31

Mostriamo ora un esempio di codifica/decodifica. Si fornisce la procedura di codifica per un codice lungo

15. Per prima cosa ricordiamo che e . Poiché la parola codice è lunga 15 caratteri,

sappiamo che e . Inoltre sappiamo che H è composta da tutti i

vettori tranne quello composto da tutti 0. Quindi gli ultimi n-k ossia 4 vettori sono la matrice identità, gli

altri 11 vettori i restanti ordinati in base al loro valore. Quindi

Mentre ,quindi

CODIFICA

Sia data una parola da spedire ad esempio . La codifica si effettua moltiplicando

, ossia prendo solo le righe in G corrispondenti alla posizione degli 1 in u, sommo per colonne modulo 2 e

ottengo x.

La parola codice da spedire è .

DECODIFICA: . La parte di dati interessati sono . Si procede quindi

al controllo dei dati sui bit di controllo. Verifico se . Se ottengo un 1 mi dice in quale posizione di H

si è verificato l’errore.

Immaginiamo di ricevere . Per verificare dobbiamo moltiplicare


32

Abbiamo un errore nella colonna 10 quindi l’errore è in posizione 10.

STII Probabilità e proprietà dei logaritmi - Luca Costante STII.pdf · Probabilità e proprietà...

Documents

Transcript of STII Probabilità e proprietà dei logaritmi - Luca Costante STII.pdf · Probabilità e proprietà...