Facoltà di Ingegneria Appunti dalle lezioni del corso di · Facoltà di Ingegneria Appunti dalle...

Facoltà di Ingegneria

Appunti dalle lezioni del corso di

Teoria dell’informazione e codici

Prof. Alessandro NERI

Anno accademico 2008-2009

TEORIA DELL'INFORMAZIONE

� Problema fondamentale della comunicazione:

Riprodurre in un punto, in modo esatto o approssimato, un messaggio selezionato

in un altro punto

� Obiettivo

Provare, per mezzo della teoria dei processi ergodici, teoremi fondamentali sulla

codificazione dell'informazione trasmessa (in cui l'entropia gioca un ruolo

essenziale)

� La misura dell'informazione è

1. Un'indicazione della libertà di scelta che una sorgente è in grado di esercitare

nel selezionare un messaggio

2. Un'indicazione del grado di incertezza di un osservatore nei riguardi del

messaggio che sarà emesso

Codifica a blocchi

� Data una sorgente discreta S0, siano:

� x[n]: una realizzazione costituita da una successione indefinita di caratteri

appartenenti all'alfabeto di sorgente A ad L determinazioni

A=(a1, a2, …, aj, …aL)

� xk: sequenza di k caratteri successivi

Codificatore a blocchi (k;M)

Codifica a blocchi

� A(k) : l'alfabeto estensione di ordine k di A

A(k) =(b1, b2, …, bj, …bLk)

i cui elementi sono le Lk differenti sequenze di k caratteri ciascuno appartenente ad

A, cioè

bj =(aj1, aj2

, …, ajn , … ajk

� Si applichi ad x[n] una codificazione a blocchi (k; M) a lunghezza di parola non

necessariamente costante tale che a ciascun carattere bj di A(k) faccia corrispondere

una stringa di nj caratteri del nuovo alfabeto ad M simboli

C =(c1, c2, …, cj, …cM)

Codifica a blocchi

carattere PA(a) Codice I Codice II Codice III a1 1/2 1 0 0 a2 1/4 00 10 01 a3 1/8 01 110 011 a4 1/8 10 111 111

Codici:

univocamente decodificabili Trasformazione invertibile

istantaneamente decodificabili l'inversione può essere effettuata in tempo reale

senza dover attendere gli altri caratteri della

sequenza.

� Regola del prefisso: Un codice risulta univocamente istantaneamente

decodificabile se non esiste nessuna parola di codice che coincida interamente

con l'inizio di parole di codice di lunghezza maggiore.

ENTROPIA

� Obiettivo

cercare di assegnare le parole di codice di lunghezza più brevi alle

sequenze di caratteri d'ingresso più frequenti

� esempio: codice MORSE

� Definizione

� Indicata con PB(bj) la probabilità associata al carattere bj, il valore atteso

del numero di caratteri di C che corrispondono a xk vale:

jjBjB bPnnE

ENTROPIA

Ciò posto, si definisce Entropia H della sorgente la quantità

nEInfH B

al variare in tutti i modi possibili del sistema di codificazione a blocchi,

purché biunivocamente decodificabile.

ENTROPIA (cont.)

� Teorema

=∞→ )(

BMBk (1)

� Dal teorema discende che una serie di approssimazioni per H può essere

ottenuta a partire dalla conoscenza delle proprietà statistiche di sequenze

di 1, 2, …, k simboli

� La base del logaritmo che compare nella (1) determina l'unità di misura

per l'entropia.

� Per M=2 l'entropia si misura in [bit/simbolo]

� Per M=e l'entropia si misura in [nat/simbolo]

Sorgente ergodica senza memoria

Poiché per tale sorgente:

PB(bj)=PA(aj1, aj2

, …, ajn , … ajk

l ljA aP1

si ha:

( ) ( )2 21

1 1 1 1lim log lim log

( )( )k k

kk kA jj

H E Ek k P aP a

→∞ →∞ =

∑∏

=∞→ )(

1lim 2 aP

Sorgente ergodica senza memoria � quindi una sorgente senza memoria presenta una entropia pari a:

1log2 aP

� Sorgente binaria posto

PA(a1)=P; PA(a2)=1-P

per l'entropia di tale sorgente si ha:

−−+=

log)1(1

log 22

� Teorema: L'entropia di una sorgente senza memoria soddisfa la

diseguaglianza:

LH 2log≤

con uguaglianza quando i simboli sono equiprobabili.

Dim.: poiché

)1(2ln

1log2 −≤ yy

si ha:

∑∑==

−≤=−

n nAnA

nnA aLP

aPLH11

22 1)(

log)(log .

D’altro canto,

∑∑∑===

=−=−=

n nAnA aP

LaLPaP

111011)(1

pertanto si ha:

0log2 ≤− LH

c.d.d.

Diseguaglianza di KRAFT � Teorema (diseguaglianza di Kraft): Dato un codice istantaneamente

decodificabile definito sull’alfabeto C ad M simboli, le lunghezze delle

parole di codice deve soddisfare la condizione

=≤∑

Di converso, per ogni insieme di lunghezze ni che soddisfano la precedente

condizione esiste almeno un codice istantaneamente decodificabile con le

predette lunghezze di codice.

Diseguaglianza di KRAFT

Si osservi che un

codice a blocco

istantaneamente

decodificabile può

essere rappresentato da

un un albero M-ario in

cui ogni nodo ha M

figli.

Ogni ramo dell’albero rappresenta un carattere di C mentre ogni foglia

rappresenta una parola di codice. Il cammino dalla radice alla foglia definisce

la parola di codice. La regola del prefisso è automaticamente verificata poiché

ogni nodo che corrisponde ad una parola di codice è una foglia da cui, pertanto,

non si sviluppano altri sottoalberi.

• Sia nmax la lunghezza maggiore.

• Considerati i nodi al livello nmax, alcuni di essi rappresenteranno parole di

codice, altri corrisponderanno a discendenti di parole di codice.

• Una parola di lunghezza ni ha max in nM − discendenti a livello nmax.

Poiché i sottoinsiemi costituiti dai discendenti delle parole di codice sono

disgiunti si ha

max max

Ln n n

M M−

=≤∑

Ovvero

=≤∑

q.e.d.

OTTIMIZZAZIONE DELLE LUNGHEZZE La minimizzazione di EB{ n} deve tenere in conto la diseguaglianza di Kraft. A

tale scopo si può ricorrere alla tecnica dei moltiplicatori di Lagrange.

Pertanto, indicando con λ il moltiplicatore di Lagrange, possiamo imporre la

minimizzazione del funzionale

( ) 1k k

i ii i

J n P b Mλ −

= + −

∑ ∑

e risolvere parametricamente il problema secondo le tecniche consuete.

Pertanto, imponiamo

( ) log 0ini e

JP b M M

nλ −∂ = − =

Da cui si ottiene

loglog

Il valore del moltiplicatore può essere determinato imponendo il rispetto del

vincolo, ovvero della diseguaglianza di Kraft:

( ) 11

log log

L Ln i

e ei i

M Mλ λ−

= == = ≤∑ ∑

Da cui segue che

1 loge Mλ≤

e quindi, poiché le lunghezze devono essere numeri interi

( )i Mi

Ovvero, indicando con x il più piccolo intero x≥

( )i Mi

Poiché

1 1log log 1

( ) ( )M i Mi i

nP b P b

≤ < +

1 1log ( ) log 1

( ) ( )B M i i B Mi i

E n P b EP b P b

≤ < +

Per una sorgente senza memoria pertanto

{ } 1BkH E n kH≤ < +

Codificatore di Huffman (1952) Procedura per M=2

Passo 1 Si ordinino gli Lk simboli bj

secondo valori non crescenti delle

loro probabilità e si indichi con

{ d(n)} la sequenza così riordinata di

D simboli

Passo 2 Si raggruppino gli ultimi due

simboli d(D) e d(D-1) in un simbolo

equivalente con probabilità

P[d(D)]+P[d(D-1)]

Passo 3 Posto D=D-1 si ripetano i passi 1 e

2 finché non rimanga un unico

simbolo

Codificatore di Huffman

All’albero binario di figura costruito secondo l’algoritmo di Huffman corrisponde il codice seguente

carattere Codifica P(bj) log2 [P(bj)]-1 nj

a1 00 0.36 1,47 2 a2 010 0.14 2,84 3 a3 011 0.13 2,94 3 a4 100 0.12 3,06 3 a5 101 0.10 3,32 3 a6 110 0.09 3,47 3 a7 1110 0.04 4,64 4 a8 1111 0.02 5,64 4

L’entropia della sorgente vale H=2,62 bit/simbolo

La lunghezza media del codice vale pertanto EB[n]=2x0.36+3x0.14+3x0.13+3x0.12+3x0.10+3x0.09+4x0.04+4x0.02= =2.7 bit/simbolo

Codificatore di Huffman

• Per alfabeti di sorgente di dimensione ridotta una codifica efficiente

richiede valori di k relativamente elevati.

• Uno degli svantaggi del codificatore di Huffman è che la soluzione relativa

a blocchi di dimensione k non può essere dedotta a partire da quella

relativa a blocchi di dimensione k-1.

o Il codificatore di Huffman richiede infatti il calcolo completo delle

probabilità di tutte le possibili sequenze di lunghezza k e la costruzione

dell’albero relativo.

• Più adatti appaiono gli schemi di codifica che consentono l’estensione a

lunghezze di blocco via via crescenti di soluzioni relative a lunghezze di

blocco inferiori.

Codifica di Shannon-Fano-Elias

L’insieme delle lunghezze 1

log( )i M

soddisfa la diseguaglianza di

Kraft e può essere impiegato per costruire un codice univocamente

decodificabile.

A questo scopo si può fare ricorso al metodo di Shannon-Fano-Elias basato

sulla funzione di distribuzione di probabilità.

Consideriamo, inizialmente, per semplicità una sorgente discreta senza

memoria, tale che per ogni possibile carattere ( ) 0A kP a > .

Come è noto, nel caso di sorgente discreta la funzione di distribuzione è una

funzione costante a tratti.

Inoltre

( ) ( )k

A ka x

F x P a≤

Oltre alla funzione di distribuzione nel seguito è conveniente fare riferimento

alla funzione di distribuzione modificata definita come segue:

1( ) ( ) ( )

A k Aa x

F x P a P x<

= +∑

• Poiché le probabilità sono tutte positive, se a b≠ si ha che ( ) ( )F a F b≠ e

quindi se conosciamo ( )F x possiamo determinare x.

• Quindi ( )F x può essere impiegato per codificare x.

• In generale è un numero reale e la sua rappresentazione richiede un numero

infinito di bit.

a1 a2 aL aj

1 ( )F x

• Indichiamo con ( )( )

l xF x l’approssimazione di ( )F x basata su l(x) bit

per cui si ha

• ( )( )

1( ) ( )

2l xl xF x F x − <

• Se

( ) log 1( )

l xP x

Si ha che

• ( )

1 ( )( ) ( 1)

P xF x F x< = − −

E quindi ( )( )

l xF x cade all’interno del salto corrispondente ad x e consente

di identificarlo correttamente.

( )F x

( )( )

l xF x

( )F x−

Poiché per rappresentare x viene impiegato un numero di bit pari a

( ) log 1( )

l xP x

La lunghezza attesa del codice vale:

( ) ( ) ( ) log 1 ( ) 2( )

L P x l x P x H XP x

= = + < +

∑ ∑

Codifica aritmetica

• Elemento essenziale della codifica aritmetica è il calcolo efficiente della

funzione di probabilità e della funzione di distribuzione

• In particolare indicando con 1ma la sottosequenza

1 1 2 1( , ,..., , )nn na a a a−=a

• Per codificare il carattere successivo emesso dalla sorgente occorre

calcolare

1 1( )nnP a +a e 1 1( )n

nF a +a

A partire dai valori 1( )nP a e 1( )nF a calcolati al passo precedente.

1 1 1 1 1( ) ( | ) ( )n n nn nP a P a P+ +=a a a

• Riferendoci per semplicità di notazione al caso binario, si ha che per il

calcolo della funzione di distribuzione in x, in linea di principio

occorrerebbe sommare le probabilità relative a tutte le foglie dell’albero

che cadono a sinistra di x.

• In alternativa è però possibile sommare le probabilità dei sottoalberi

disgiunti a sinistra di x calcolati direttamente, passo dopo passo.

� L’algoritmo base può schematizzato come segue:

1. Si inizializza l’intervallo corrente a [0..1].

2. Per ogni carattere della sequenza:

2.1. Si suddivide l’intervallo corrente in sottointervalli, uno per ciascun

simbolo dell’alfabeto. L’ampiezza di ciascun sottointervallo è

proporzionale alla probabilità (stimata) che il carattere corrente sia

uguale al simbolo corrispondente all’intervallo.

2.2. Si seleziona come intervallo corrente il sottointervallo

corrispondente al carattere corrente.

La lunghezza finale dell’intervallo corrente è uguale al prodotto P delle

probabilità dei singoli caratteri che compongono la sequenza.

Esempio. Codifica della sequenza bbb a partire dalla conoscenza delle

probabilità

Pa=0.4

Pb=0.5

Peof=0.1

Intervallo

corrente

Azione a b EOF Ingresso

[0.000,1.000] dividi [0.000,0.400] [0.400,0.900] [0.900,1.000] b

[0.400,0.900] dividi [0.400,0.600] [0.600,0.850] [0.850,0.900] b

[0.600,0.850] dividi [0.600,0.700] [0.700,0.825] [0.825,0.850] b

[0.700,0.825] dividi [0.700,0.750] [0.750,0.812] [0.812,0.825] eof

[0.812,0.825]

0.0 0.4 0.9 1.0 a b eof

1101000

L’intervallo finale, senza approssimazioni, è [0.812,0.825], che è approssimato

dalla seguente rappresentazione binaria:

[0.11010000, 0.11010011]

L’intervallo può quindi essere identificato trasmettendo 1101000.

Si osservi che la probabilità della sequenza considerata vale

P=(0.5)3(0.1)=0.0125. Pertanto –logP=6.322, mentre la versione approssimata

del codificatore aritmetico impiega 7 cifre binarie.

Decodifica aritmetica Il decodificatore opera a partire dal valore x che rappresenta un punto

dell’intervallo [0,1].

• Supponiamo, per semplicità, che il decodificatore conosca la lunghezza N

della sequenza da decodificare, codificata e trasmessa separatamente. In

alternativa può essere impiegato un ulteriore carattere di fine sequenza

• Si inizializza l’intervallo corrente a [0..1].

• Per ciascuno degli N caratteri da decodificare:

o Si suddivide l’intervallo corrente in sottointervalli, uno per ciascun

simbolo dell’alfabeto. L’ampiezza di ciascun sottointervallo è

proporzionale alla probabilità (stimata) che il carattere corrente sia

uguale al simbolo corrispondente all’intervallo.

o Si selezione il carattere corrispondente al sottointervallo in cui cade il

valore x e si tale sottointervallo come intervallo corrente

0.0 1.0

Codifica universale

• Consideriamo, senza perdita di generalità, una sorgente senza memoria.

L’algoritmo di Huffmann consente di costruire un codice la cui efficienza

raggiunge, al crescere della dimensione k del blocco, il valore teorico

corrispondente all’entropia H della sorgente.

• La procedura presuppone la conoscenza della funzione di probabilità

PB(bj)=PA(aj1, aj2

, …, ajn , … ajk

che caratterizza la sorgente.

• Se in fase di progetto del codice, si commette un errore nella valutazione

della funzione di probabilità della sorgente, esso si ripercuote sul codice e

quindi sulle prestazioni.

• In particolare sia

o PA(a): la funzione di probabilità corretta

o QA(a): la funzione di probabilità assunta nel progetto del codice

Per un’assegnata lunghezza k del blocco, il codice costruito a partire da

QB(bj)=QA(aj1, aj2

, …, ajn , … ajk

avrà parole di lunghezza pari a

1 1log log 1

( ) ( )M i MB i B i

nQ b Q b

≤ < +

Poiché la probabilità corretta PB(bj) il valore atteso del numero di simboli

impiegato per codificare un simbolo emesso dalla sorgente varrà

1 1 1 1 1( ) log ( ) ( ) log

( ) ( )

k K kL L Li

B i M i B i MB i B ii i i

nP b P b P b

k Q b k k Q b k= = =≤ < +∑ ∑ ∑

Quindi

1 1lim ( ) log

B i Mkk B ii

E nInf P b

k k Q b→∞ == ∑

Ovvero un errore nella valutazione iniziale del modello probabilistico della

sorgente si traduce in un aumento ∆H del numero medio di caratteri necessari

per codificare un simbolo emesso dalla sorgente pari a:

1 ( )lim log

( )B i

B Mk B i

P bH E

k Q b→∞

Algoritmo di Lempel-Ziv

� Appartiene alla classe dei codificatori di sorgente universali (É progettato in

modo da essere indipendente dalla statistica dell'ingresso)

1. La sequenza d'ingresso é scomposta in blocchi di lunghezza variabile, chiamati

frasi.

2. Ogni volta che un blocco di lettere differisce da uno dei blocchi precedenti per

l'ultima lettera esso viene inserito nel dizionario.

3. Tutte le frasi sono riportate nel dizionario unitamente all'informazione sulle

locazioni in cui ciascuna frase compare.

4. nel codificare quindi una nuova frase, l'algoritmo registra nel dizionario la

locazione da cui essa inizia e la nuova lettera.

10101101001001110101000011001110101100011011

scomposizione in frasi

1,0,10,11,01,00,100,111,010,1000,011,001,110,101,10001,1011

Algoritmo di Lempel-Ziv 10101101001001110101000011001110101100011011

Dizionario

Locazione del dizionario

Contenuto del dizionario

Parola di codice

1 0001 1 00001 2 0010 0 00000 3 0011 10 00010 4 0100 11 00011 5 0101 01 00101 6 0110 00 00100 7 0111 100 00110 8 1000 111 01001 9 1001 010 01010 10 1010 1000 01110 11 1011 011 01011 12 1100 001 01101 13 1101 110 01000 14 1110 101 00111 15 1111 10001 10101 16 1011 11101

� Le parole di codice sono determinate concatenando la locazione (in binario)

del dizionario che contiene la frase precedente che coincide sino al

penultimo carattere con quella da codificare, ed il nuovo carattere.

� La locazione 0000 é impiegata per fare riferimento alla frase nulla.

Canale di comunicazione

Canale:

� É da considerarsi come una trasformazione (dallo spazio dei messaggi in ingresso allo spazio

dei messaggi in uscita) con corrispondenze non rigide ma probabilistiche fra ogni messaggio

possibile in ingresso ed ogni messaggio possibile in uscita (operatore stocastico)

� L'operatore é descritto dalla funzione di probabilità della variabile del messaggio d'uscita

condizionata a quella del messaggio d'ingresso

CANALE ai bj

Canale stazionario (o permanente) senza memoria

Caratteristiche: � Invariante nel tempo � L'azione sul messaggio in transito si esplica simbolo per simbolo (trasformazione passo-

passo) � É descritto dalla Matrice di Canale

b1 b2 … bj … bM a1 PB/A(b1/a1) PB/A(b2/a1) … PB/A(bj/a1) … PB/A(bM/a1) a2 PB/A(b1/a2) PB/A(b2/a2) … PB/A(bj/a2) … PB/A(bM/a2) … … … … … … … ai PB/A(b1/ai) PB/A(b2/ai) … PB/A(bj/ai) … PB/A(bM/ai) … … … … … … … aL PB/A(b1/aL) PB/A(b2/aL) … PB/A(bj/aL) … PB/A(bM/aL)

CANALE ai bj

PB/A(bj/ai)

Tasso di informazione mutua

� Prima di osservare il simbolo in uscita dal canale lo stato di conoscenza di un osservatore

circa i risultati possibili é rappresentabile con

{ PA(ai), i=1,…,L}

� Dopo la ricezione del simbolo bj lo stato di conoscenza di un osservatore é rappresentabile da

{ PA/B(ai/bj), i=1,…,L}

� L'osservatore esterno é in grado di osservare sia ciò che é emesso dalla sorgente, sia ciò che é

emesso dal canale (con errori dovuti al rumore).

S Canale

Osservatore esterno

Correttore Db j

� L'osservatore nota gli errori e trasmette le eventuali correzioni sul canale ideale

� Avendo osservato bj l'osservatore esterno può ricorrere ad una codifica per gli ai che richiede

un numero medio di binit per simbolo pari a:

1( / ) log

j A BA B j

A B i jA B i j

H A b EP a b

P a bP a b

� Il modo più efficiente di operare per l'osservatore consiste nel:

1. predisporre M codici, uno per ogni possibile valore ricevuto bj in base alle PA/B(ai/bj)

2. usare il codice corrispondente al simbolo ricevuto per inviare s

3. ul canale di correzione la codifica del simbolo ai emesso dalla sorgente.

� I codici utilizzati dall'osservatore devono essere necessariamente istantanei.

Equivocazione H(A/B) del canale

Def. numero medio di binit necessari all'osservatore esterno per

rappresentare il simbolo di ingresso, ovvero per inviare la correzione

{ } , 2/

1( / ) ( / ) log

1( , ) log

B A BA B

A B i jA B i j

H A B E H A b EP a b

P a bP a b

=∑∑ (1)

� Nel caso di canale ideale l'osservazione all'uscita del canale é perfetta e

quindi

� PA/B(ai/bj= aj) =δij,

Equivocazione H(A/B) del canale

in tal caso, coerentemente con il fatto che in tal caso l'osservatore non ha

necessità di inviare alcuna correzione, l'eq. (1) fornisce un valore nullo per

l'equivocazione.

� Poiché l'insieme (canale+osservatore esterno) si comporta come un canale

ideale, é naturale dire che

� il complesso fornisce una quantità di informazione media per simbolo

pari alla entropia della sorgente H(A)

� l'osservatore deve fornire, per inviare le correzioni, una quantità di

informazione media pari alla equivocazione H(A/B)

� e quindi l'osservazione di un simbolo all'uscita del canale fornisce una

quantità di informazione media per simbolo pari a

I(A;B)= H(A)- H(A/B)

� La quantità I(A;B) prende il nome di TASSO DI INFORMAZIONE (MUTUA) del

canale e può essere calcolata come segue

),(log

)/(log)/()();(

baPEBAHAHBAI

Ricordando che )1(2ln

1log2 −≤ yy si può verificare che

0);( ≥BAI

con il segno di eguaglianza se e solo se

PA,B(ai,bj)= PA(ai) PB(bj)

ovvero

� l'informazione media ricevuta attraverso un canale é sempre non negativa

� la sola situazione in cui l'informazione é nulla é rappresentata dal caso in

cui i simboli di ingesso e di uscita sono indipendenti.

Entropia congiunta � Def.: Si definisce Entropia congiunta H(A,B) la quantità

log),(

baPbaP

baPEBAH

∑∑= =

♦ Il tasso di informazione si può quindi esprimere come segue:

I(A;B) = H(A)- H(A/B) =

= H(B)- H(B/A) =

= H(A) + H(B) - H(A,B)

Capacità di canale ♦ Obiettivo:

caratterizzare le potenzialità del canale prescindendo dalla distribuzione di

probabilità della sorgente a cui il canale é connesso.

♦ Definizioni:

• CAPACITÀ DI CANALE PER SIMBOLO Cs : tasso di informazione massimo

consentito da un dato canale, rispetto a tutte le possibili distribuzioni di

probabilità della sorgente

)];([)(

BAIMaxCaP

= [bit/coppia di simboli]

Capacità di canale

• CAPACITÀ DI CANALE C:

cs fCC = [bit/s] con

fc: frequenza di simbolo all'uscita del canale

� C é funzione solo delle probabilità condizionate che caratterizzano il canale.

Capacità di un canale ideale

• Poiché per un canale ideale l'equivocazione é nulla sia ha

AHMaxfBAHAHMaxfC

aAPcaAPc

)]([)]/()([

==−=

INTENSITÀ DI EROGAZIONE DI UNA SORGENTE

• Indicata con

fS: la frequenza con la quale la sorgente eroga i messaggi

si definisce intensità di erogazione della sorgente la quantità

RS=fS H(A)

Capacità di un canale binario simmetrico

Per il canale binario simmetrico si ha pPbaP =),( 00 qQbaP =),( 01

qPbaP =),( 10 pQbaP =),( 11

+=)/( 00

+=)/( 01

+=)/( 10

+=)/( 11

Q=1-P 1 1

q =1-p

Capacità di un canale binario simmetrico

e quindi

== ∑ ∑= = )(

)/(log),();( /

i jjiBA aP

baPbaPBAI

loglog

log)()(

1log)(

loglog

pQqPpQqP

qQpPqQpP

Capacità di un canale binario simmetrico ovvero

)()();( 00 pHqQpPHBAI −+=

1 1( ) log (1 )log

1H x x x

x x= + −

Poiché H(x) é massima per x=1/2, il massimo del tasso di informazione

rispetto a P si ha per

1 =⇒=−+⇒=+ PPqpPqQpP

Capacità per simbolo del canale binario simmetrico

• La capacità per simbolo di un canale binario simmetrico vale

Cs = 1- H0(p)

Capacità del Canale Gaussiano limitato in banda

� TEOREMA. Una sorgente analogica, stazionaria ergodica, senza memoria,

con valore atteso e momento del secondo ordine o varianza assegnati e di

valore finito, ha la massima entropia se é gaussiana.

Il problema può essere formulato come segue: determinare la funzione di

densità di probabilità p(x) tale che

1( )log

( )p xMax p x dx

−∞∫

Con i vincoli

( ) 1p x dx+∞

−∞=∫

( )x p x dx m+∞

−∞=∫

2 (2)( )x p x dx m+∞

−∞=∫

Pertanto, applicando il metodo dei moltiplicatori di Lagrange possiamo

massimizzare il funzionale seguente:

(2) 22 1 2 3

1( ) log 1 ( ) ( ) ( )

( )F p x dx p x dx m xp x dx m x p x dx

p xλ λ λ

+∞ +∞ +∞ +∞

−∞ −∞ −∞ −∞ = + − + − + − ∫ ∫ ∫ ∫

determinando la funzione p che annulla la derivata parziale di F rispetto a p,

ovvero tale che

22 1 2 3log ( )ln ( ) ( ) ( ) ( ) 0e p x p x p x xp x x p x dx

pλ λ λ

−∞

∂ − − − − = ∂ ∫

Da cui si ha:

22 1 2 3

1log ( ) ln ( ) 0

( )e p x p x x x dx

p xλ λ λ

−∞

− − − − − =

Che ammette come soluzione

21 2 3ln ( ) ( 1) 0p x x xλ λ λ− − + − − =

Ovvero 2

1 2 3( 1)( ) x xp x e λ λ λ− + − −=

I valori dei moltiplicatori di Lagrange si ottengono imponendo il rispetto dei

vincoli, per cui si ha 2

p x e σπσ

−−=

2 (2) 2m mσ = −

q.e.d.

� I(X;Y) = H(Y)- H(Y/X)

σ−+πσ=

log)/(N

+πσ ee N ln21

log 22 =

= 22 2log

1Neσπ

n[k]~ ),0( 2NσN

� Poichè in virtù del risultato precedente, affinché H (Y) sia massima si ha:

� Y~ ),0( 22NX σ+σN

� Ovvero, poiché X e N sono statisticamente, la varianza di y è pari alla

somma delle varianze di X e N, si ha:

Y~ ),0( 22NX σ+σN

� quindi

σ+σ= ed essendo fC=2w si ha

)1(log2 SNRwC +=

Teorema della codifica di canale - Canale Ideale

• Teorema: Data una sorgente con entropia H (bit/simbolo) ed un canale

ideale binario di capacità C (bit/s), é possibile codificare i messaggi in modo

da trasmettere attraverso il canale, nell'unità di tempo, un numero di simboli

di sorgente pari a

ε−H

con ε piccolo a piacere. Non é possibile trasmettere nell'unità di tempo un

numero di simboli della sorgente superiore a (C/H).

Teorema della codifica di canale - Canale Ideale

� condizione di codifica in tempo reale

� fS: frequenza dei messaggi della sorgente

� E{ n}: valore atteso del numero di simboli all'ingresso del canale

corrispondenti a k simboli emessi dalla sorgente

Teorema della codifica di canale - Canale Ideale � Per il Io teorema di Shannon, ⇒∃>ε∀ codiceun,0

ε+<≤ Hk

ovvero tale che

ε+<≤ Hf

Poiché per un canale binario ideale CC fLfC == 2log (L=2)

si ottiene

ε+<≤ Hf

ovvero

CS ≤<ε−

c.d.d.

Teorema della codifica di canale - Caso generale (Shannon 1948)

� Teorema: Siano dati una sorgente con entropia H (bit/simbolo) ed un canale

binario di capacità C (bit/s).

• Se fSH<C esiste almeno un codice tale che l'uscita della sorgente possa

essere trasmessa attraverso il canale con un tasso di errore arbitrariamente

piccolo (o equivocazione arbitrariamente piccola).

• Se fSH>C é possibile codificare la sorgente in modo tale che

l'equivocazione sia minore di (fSH - C+ε) con ε piccolo a piacere. Non

esiste nessun codice tale che l'equivocazione sia minore di (fSH - C) .

Diseguaglianza di Fano

• Dalla precedente trattazione appare che la qualità di un canale può essere

descritta sia facendo riferimento alla probabilità d’errore che

all’equivocazione. Tali grandezze non sono tra loro indipendenti, come

mostrato dalla seguente disuguaglianza di Fano che lega tra loro la

probabilità d’errore e l’equivocazione di un canale discreto senza

memoria.

• Teorema: dato un canale discreto senza memoria i cui alfabeti di ingresso e

d'uscita A e B hanno lo stesso numero di simboli L e la cui probabilità

d'errore é Pe, vale la diseguaglianza

)1(log)()/( 20 −+≤ LPPHBAH ee .

In base alla definizione di equivocazione si ha:

{ } , 2 , 2/ /

1 1( / ) ( / ) log ( , ) log

( / ) ( / )

B A B A B i jA B A B i j

H A B E H A b E P a bP a b P a b

∑∑

, 2 , 2/ /

1 1( , ) log ( , ) log

( / ) ( / )

A B i j A B j jA B i j A B j j

j i ji j

P a b P a bP a b P a b

= = =≠

= +∑∑ ∑

Pertanto

0 2( / ) ( ) log ( 1)e eH A B H P P L− − − =

, 2 , 2/ /

1 1( , ) log ( , ) log

( / ) ( / )

A B i j A B j jA B i j A B j j

j i ji j

P a b P a bP a b P a b

= = =≠

= +∑∑ ∑

( ), 2 , 2

( , ) log ( , ) log 1

A B i j e A B j j e

j i ji j

P a b P P a b P

= = =≠

+ + −∑∑ ∑

( ), 2

( , ) log 1

A B i j

j ii j

P a b L

= =≠

− −∑∑

( ), 2 , 2/ /

1( , ) log ( , ) log

1 ( / ) ( / )

e eA B i j A B j j

A B i j A B j jj i j

P PP a b P a b

L P a b P a b= = =

−= +−∑∑ ∑

Ricordando che

)1(2ln

1log2 −≤ yy

si ha:

( )0 2 ,/

1( / ) ( ) log ( 1) ( , ) 1

ln 2 1 ( / )

1( , ) 1

ee e A B i j

A B i jj i

eA B j j

A B j jj

PH A B H P P L P a b

L P a b

PP a b

= =≠

− − − ≤ − −

−+ −

∑∑

1 1 1 1

1( / ) ( ) log ( 1) ( ) ( , )

ln 2 1

1 ( ) ( , )

L L L L

ee e B j A B i j

j i j ii j i j

e B j A B j j

PH A B H P P L P b P a b

P P b P a b

= = = =≠ ≠

− − − ≤ − −

+ − −

∑∑ ∑∑

∑ ∑

( ) ( ) ( )0 2

1( / ) ( ) log ( 1) 1 ( ) 1 ( ) 1

ln 2 1

ee e B j e B j

PH A B H P P L L P b P P b

− − − ≤ − + − − −

∑ ∑

Quindi

0 2( / ) ( ) log ( 1) 0e eH A B H P P L− − − ≤ .

c.d.d.

0 0 , 2 0 , 4 0 , 6 0 , 8 1

L = 1 6

L = 3 2

RATE DISTORTION THEORY

QUANTIZZAZIONE Una sorgente analogica presenta, per definizione, una cardinalità dello spazio

di messaggio almeno pari a quella del continuo. Pertanto il ricorso ad una sua

rappresentazione in forma numerica, ad esempio per mezzo di un numero finito

di cifre binarie, richiede l’analisi della bontà dell’approssimazione.

Il primo passo concettuale consiste nell’introduzione di una misura di

distorsione ˆ( , )d x x (non negativa) che definisce il costo pagato nel

rappresentare il dato originale x con una sua rappresentazione x discreta.

ˆ:d R+× →X X

Una volta specificata la funzione di distorsione, il problema di base può essere

formulato in una delle due forme seguenti:

• Data una sorgente caratterizzata da una propria distribuzione ed una classe

di rappresentazioni ˆ ( ; )Rx x che utilizzano un numero preassegnato R di bit

con associata distorsione media D(R)

[ ]{ }ˆ( ) , ( ; )D R E d R= X x x x

determinare quanto vale il minimo valore di distorsione media D(R)

ottenibile e la rappresentazione che consente di ottenere tale valore.

• Data una sorgente caratterizzata da una propria distribuzione ed una

funzione di distorsione, determinare quanto vale il minimo numero di bit R

necessario per garantire che la distorsione media non superi un livello

preassegnato.

ξ1 ξ2

ξi-1 ξi ξN-1

Quantizzazione scalare Consideriamo inizialmente il caso della quantizzazione scalare.

L’asse reale è partizionato in

N=2R intervalli

( ]{ }1, , 1, ,i i iV i Nξ ξ−= = K

consecutivi, con 0ξ = −∞ e

Nξ = ∞ .

Il quantizzatore scalare associa il

valore ix ad ogni punto

dell’intervallo Vi.

La distorsione media vale pertanto

ˆ( ) , ( )i

D R d x x p x dx=

=∑∫

• L’ottimizzazione della regola di quantizzazione richiede sia la

determinazione dei valori quantizzati, sia l’individuazione della partizione.

• Consideriamo inizialmente, per semplicità, l’ottimizzazione dei valori

quantizzati nel caso in cui la partizione sia fissata ed esaminiamo in

particolare il caso di distorsione quadratica.

Quantizzazione scalare e distorsione quadratica

Nel caso di funzione di distorsione di tipo quadratico si ha:

ˆ( ) ( )i

D R x x p x dx=

= −∑∫

Pertanto, per una partizione assegnata il livello di quantizzazione ottimo si

ottiene imponendo l’annullamento di

( )( )ˆ2 ( )

ˆ ii XV

D Rx x p x dx

∂ = − −∂ ∫

Da cui si ha

( ') 'i

xp x dxx

p x dx

p xx dx

p x dx= =∫

∫∫∫

• Il valore ottimo per un dato intervallo Vi è quindi dato dal valore atteso

condizionato all’evento che il valore osservato cada in tale intervallo.

• Esso si riduce, ad esempio, al punto medio dell’intervallo nel caso in cui la

funzione di densità di probabilità sia costante nell’intervallo Vi.

Quantizzazione scalare Max-Lloyd

L’algoritmo di Max-Lloyd fornisce un procedimento iterativo per la

determinazione del quantizzatore ottimo per un’assegnata funzione di densità

di probabilità nel caso di funzione di distorsione di tipo quadratico.

Si assume che sia disponibile un’approssimazione iniziale

({ }(0) (0) (0)1 , , 1, ,i iiV i Nξ ξ− = = K

della partizione ottima.

• Tale approssimazione può essere ottenuta ad esempio, suddividendo

l’intervallo di variabilità della grandezza fisica d’interesse in parti uguali.

Algoritmo Max-Lloyd

1. Inizializza k=0

2. Ripeti

( )1( )

( 1)( )

xp x dxx

p x dx

+ =∫

b. ( 1) ( 1)

( 1) 1ˆ ˆ

k kk i i

ix xξ

+ ++ ++=

c. k=k+1

Sino a quando { }( 1) ( )k ki i

iMax ξ ξ ξ+ − > ∆

QUANTIZZAZIONE: Sorgente con distribuzione uniforme

Si consideri il caso in cui i valori emessi dalla sorgente siano distribuiti

uniformemente nell’intervallo [-A, A], cosicchè

( ) ( ) 22

A x Ap x rect x A

Aaltrimenti

− ≤ ≤= =

In tal caso, indicato con Qi l’ampiezza dell’i-esimo intervallo, si ha

Qx ξ−= +

2 2i i

N Q ii

QD R x dx

ξξ−

= − +

∑∫

x dxA −=

= ∑∫

A == ∑

Con il vincolo

Pertanto, applicando il metodo dei moltiplicatori di Lagrange, posto

QJ A Q

= + −

∑ ∑

Q Aλ∂ = − =

8iQ Aλ=

Il valore del moltiplicatore può essere ottenuto imponendo il vincolo

A Aλ=

Da cui segue che

Ovvero la partizione ottima corrisponde a intervalli tutti uguali con ampiezza

E la distorsione complessiva vale

3 3 2 22

1 1 8( ) 2

2 12 2 312 3

Q A A AD R N

A A N N−

== = = =∑

Ovvero, esprimendo la distorsione in dB si ha

[ ] ( )2 2

10 10 10( ) 10log 20log 2 10log 63 3dB

A AD R R R= − × ≅ −

Si osserva quindi che in questo caso la distorsione decresce di circa 6 dB per

ogni bit impiegato nel convertitore.

CODIFICA PCM DELLA FONIA (ITU G.711)

La raccomandazione ITU G.711 specifica le modalità secondo le quali deve

essere rappresentato il segnale vocale per servizi di fonia offerti dalle reti

telefoniche pubbliche internazionali.

• Il valore nominale raccomandato per il ritmo di campionamento è di 8000

campioni al secondo con una tolleranza di ± 50 parti per milione (ppm).

• Ogni campione è rappresentato con 8 bit.

• La quantizzazione è non uniforme ed è realizzata come cascata di un

quantizzatore uniforme e di una non linearità per la

compressione/espansione della dinamica.

• La raccomandazione specifica due non linearità indicate rispettivamente

come legge A e legge µ.

• La legge µ si applica negli USA e in Giappone ed è caratterizzata dalla

seguente espressione analitica

( )( )

ln 1( ) ( ) , 1

xF x sign x xµ

Il quantizzatore uniforme impiega 14 bit.

s(t) Campionatore

Fc=8000

Quantizzatore uniforme

a 14 bit

Legge µ ( )( )

ln 1( ) ( ) , 1

xF x sign x xµ

sPCM[k]

• La legge A si applica in Europa e nel resto del mondo (ad esclusione di

USA e Giappone) ed è caratterizzata dalla seguente espressione analitica

( ) 01 ln( )

1 ln( ) 1

A xsign x x A

AF xA x

sign x A xA

≤ < +=

+ ≤ ≤ +

Il quantizzatore uniforme impiega 13 bit.

s(t) Campionatore

Fc=8000

Quantizzatore uniforme

a 13 bit

Legge A 1

( ) 01 ln( )

1 ln( ) 1

A xsign x x A

AF xA x

sign x A xA

≤ < +=

+ ≤ ≤ +

sPCM[k]

QUANTIZZAZIONE VETTORIALE

Un quantizzatore vettoriale associa ad ogni vettore dello spazio a k dimensioni

uno fra N possibili vettori C={c1,c2,…,cN} che costituiscono il dizionario

(codebook).

Ad ogni parola di codice ci, è associata la regione di Voronoi i cui punti

soddisfano la condizione { }: ,ki i jV R j i= ∈ − ≤ − ∀ ≠x x c x c

L’insieme delle regioni di Voronoi costituisce una partizione di Rk .

ALGORITMO LBG

Nel 1980, Linde, Buzo, and Gray (LBG) hanno proposto un algoritmo per la

progettazione di un quantizzatore vettoriale a partire da una sequenza di

addestramento (training sequence) il cui impiego consente di evitare le

operazioni di integrazione multidimensionale richieste dall’uso diretto della

funzione di densità di probabilità.

Nel caso ad esempio dei segnali vocali la sequenza di addestramento potrebbe

essere estratta a partire da registrazioni di conversazioni telefoniche tipiche.

Si assume che il numero di casi che costituiscono la sequenza di

addestramento sia sufficientemente grande da poter applicare le leggi dei

grandi numeri e sostituire le medie d’insieme con le medie calcolate sul

numero finito di realizzazioni disponibili.

ALGORITMO LBG

Il problema affrontato da Linde, Buzo, and Gray può essere schematizzato

come segue:

Dato un insieme di M vettori di addestramento T=(x1x2,xM), trovare il dizionario C={c1,c2,…,cN} e la partizione V={V1,V2,…,VN} = tale che la sia minima distorsione media

D QMk =

= −∑ x x

essendo ( )mQ x il vettore del dizionario associato a xm:

( ) ,m n m nQ if V= ∈x c x

IV. Criteri di ottimalità

Indicato con Sn l’insieme dei vettori di addestramento che cadono in Vn:

{ }, 1, ,n m m nS V m M= ∈ =x x K

se C e V sono soluzioni del problema devono essere soddisfatte le due

condizioni seguenti

Nearest Neighbor Condition:

22: ,m n m n m jS j n∀ ∈ − ≤ − ∀ ≠x x c x c

Centroid Condition:

, 1, ,1

n N∈

= =∑∑

IV. Algoritmo

L’algoritmo si compone di tre parti

• Inizializzazione

• Raddoppio degli elementi della partizione tramite suddivisione

• Raffinamento iterativo della partizione

Inizializzazione

• La partizione iniziale è costituita da un unico elemento coincidente con

• Il dizionario ha un solo elemento costituito dal centroide dei vettori della

sequenza di addestramento

= ∑c x

= −∑ x c

• Raddoppio degli elementi della partizione tramite suddivisione

1. Suddivisione

1. Per i=1,2,…,N

i. (0) * (1 )i i= +∈c c

ii. (0) * (1 )ii N+ = −∈c c

2. Poni N=2N

• Raffinamento iterativo della partizione

(0) *av avD D=

Ripeti

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

{ }( )

( ) ( )( )i

i im m nQ Arg Min= −

cx x c

ii. Aggiornamento partizione

{ }( ) ( ) ( )( ) , 1, ,i i in m m nS Q n N= = =x x c K

iii. Aggiornamento del dizionario

( 1) , 1, ,1

n N∈+

= =∑∑

iv. Aggiornamento distorsione

2( ) ( )

av m mm

D QMk =

= −∑ x x

v. i=i+1

sino a quando

( ) ( 1)

i iav av

−− >∈

* ( )in n=c c

VI. Two-Dimensional Animation

VIII. References

1. A. Gersho and R. M. Gray, Vector Quantization and Signal Compression. 2. H. Abut, Vector Quantization. 3. R. M. Gray, ``Vector Quantization,'' IEEE ASSP Magazine, pp. 4--29, April 1984. 4. Y. Linde, A. Buzo, and R. M. Gray, ``An Algorithm for Vector Quantizer Design,'' IEEE Transactions on Communications, pp. 702--710, January 1980.

CODIFICA DI CANALE

Codificatore lineare a blocchi - In un codice lineare a blocchi la sequenza in ingresso viene suddivisa in

blocchi di lunghezza costante k,

- per ogni blocco in ingresso di lunghezza k, il codificatore genera un

blocco di n cifre in uscita combinando linearmente le k cifre del blocco

sorgente

xm1 xm2 … xmk

cm1 cm2 … cmn

registro d'ingresso

registro d'uscita

Codificatore lineare a blocchi Un codice lineare a blocchi (n,k) e' definito quindi dalla relazione

in cui - Ingresso: [ ]mkmmm xxx K21=X

- Uscita: [ ]mnmmm ccc K21=C

- G : Matrice di generazione del codice

→←

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

GXC mm = Xm Cm

Codificatore lineare a blocchi Esempio: Il codice di Hamming (7,4)

1101000

0110100

1110010

1010001

ingresso Codice Peso Ingresso Codice Peso 0000 0000 000 0 1000 1000 101 3 0001 0001 011 3 1001 1001 110 4 0010 0010 110 3 1010 1010 011 4 0011 0011 101 4 1011 1011 000 3 0100 0100 111 4 1100 1100 010 3 0101 0101 100 3 1101 1101 001 4 0110 0110 001 3 1110 1110 100 4 0111 0111 010 4 1111 1111 111 7

x xm1 xm2 xm4 xm3

cm1 cm2 cm6 c

cm3 cm4 cm5 cm7

Codificatore lineare a blocchi Poiché

Cm=XmG

per ottenere l'uscita del codificatore è sufficiente sommare le righe

corrispondenti agli 1 contenuti nella sequenza d'ingresso

Esempio: Dato il codice di Hamming (7,4) calcolare l'uscita per Xm=[1100]

1101000

0110100

1110010

1010001

0011mC 0100011

1110010

1010001

Codificatore lineare a blocchi

Def.: Peso di Hamming: numero di 1 contenuti in una parola di codice

Def.: distanza di Hamming fra due parole di codice: numero di

posizioni in cui le parole sono diverse.

Def.: distanza minima del codice: minimo delle distanze di Hamming

tra le parole che compongono il codice

Codici sistematici

Def.: Un codice lineare (n,k) e' detto sistematico se le prime k cifre della

parola di codice sono una replica delle cifre d'ingresso e le rimanenti (n-k)

sono dei controlli di parità sulle k cifre d'informazione, ovvero se la sua

matrice di generazione ha la forma seguente:

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

1...00

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

0...10

0...01

Codici sistematici

Proprietà 1. Ogni parola di codice è una somma di righe della matrice generatrice

Proprietà 2. Il codice a blocco è formato da tutte le possibili somme delle righe della matrice generatrice

Proprietà 3. La somma di due parole di codice è ancora una parola di codice

Proprietà 4. La sequenza di tutti zeri è sempre una parola di codice di un codice a controllo di parità

Proprietà 5. La distanza minima di un codice a blocco lineare è il peso minimo delle sue parole di codice non nulle.

Codici sistematici

Proprietà 6. Da un punto di vista algebrico le k righe della matrice

generatrice costituisco una base del sottospazio costituito

dalle 2k parole di codice

Proprietà 7. La matrice di un codice lineare a blocco può essere ridotta,

tramite operazioni sulle righe e permutazioni sulle

colonne, alla forma sistematica

Rivelazione e correzione d'errore per i codici a bl occo � Siano

Cm: parola di codice trasmessa

Y: parola di codice ricevuta

In generale Y può essere posto nella forma seguente

Y= Cm+ e

e: vettore di errore binario arbitrario

� Il decodificatore confronta le (n-k) cifre di controllo di parità con il

risultato dei controlli effettuati sulle prime k cifre ricevute.

� Viene rivelato un errore quando almeno uno degli (n-k) controlli fallisce.

Rivelazione e correzione d'errore per i codici a bl occo

Def.: Si definisce sindrome il vettore S a (n-k) componenti la cui

componente i-esima vale 1 se il controllo di parità i-esimo è fallito e 0

altrimenti.

Codice duale di un codice sistematico � Dato un codice lineare a blocchi (n, k), ad esso e' associato un codice duale

a blocco (n, n-k) il cui sottospazio costituito dalle 2n-k parole di codice è

ortogonale al sottospazio costituito dalle 2k parole del codice (n,k).

� Sia H la matrice di generazione del codice duale. Poiché ogni parola di

codice Cm e' ortogonale ad ogni parola del codice duale, vale la condizione

XmG(ZmH)T =0

ovvero

XmGHT(Zm)T =0

Poiché tale condizione deve valere per ogni Xm e per ogni Zm, si ha

GHT =0

Matrice di controllo di parità

� Per un codice sistematico posto

]|[ BAH =

si ha:

[ | ] ,T

T T T Tk k n kT −

= + = ⇒ = − =

AI P I A PB 0 A P B I

ovvero (poiché il segno negativo può essere omesso per codici binari):

]|[ knT

−= IPH

� H prende il nome di matrice di controllo di parità

Matrice di controllo di parità � Dato il codice di Hamming (7,4)

1101000

0110100

1110010

1010001

� la matrice di controllo di parità vale

=1001011

0101110

0010111

Matrice di controllo di parità � Data la matrice di controllo di parità vale la proprietà:

TYHS =

essendo S la sindrome del vettore d'errore. Infatti

[ ]1 1... ...Tk k n

y y y y+−

e quindi YHT è un vettore la cui componente i-esima vale 0 solo se il risultato del controllo di parità i-esimo coincide con la (k+i)-esima cifra ricevuta

� Inoltre

S=YHT= CmHT+ eHT=eHT

Rivelazione e correzione dell'errore

�� La sindrome associata ad una sequenza Y è un vettore nullo se e solo se Y è

una parola di codice

�� Il decodificatore può rivelare tutti gli errori del canale che non siano parole

di codice

�� Data una parola di codice esistono 2k diverse sequenze che danno la stessa

sindrome

�� La sola sindrome non consente di determinare quindi quale sequenza

di errore si sia verificata

Rivelazione e correzione dell'errore per canali bin ari simmetrici � Per un canale binario simmetrico si ha

ii ddni ppP )1()/( )( −= −CY

in cui di è la distanza di Hamming tra Y e la i-esima parola di codice C(i).

Quindi, date due parole di codice C(i) e C(h) , per il logaritmo del rapporto

di verosimiglianza si ha

)1ln(ln)()1ln(ln)()/(

pdpdnpdpdnP

Phhiih

−+−−−+−=CY

pdd ih −

Rivelazione e correzione dell'errore per canali bin ari simmetrici � Pertanto, poiché per funzione di costo uniforme e simboli equiprobabili si

ln)()(

−−

se p>1/2 la verifica del rapporto di verosimiglianza porta a scegliere, tra le

due ipotesi, quella a cui corrisponde la minima distanza di Hamming (se

p<1/2 viene selezionata l'ipotesi a cui corrisponde la massima distanza di

Hamming)

Rivelazione e correzione dell'errore per canali bin ari simmetrici

� Posto

Y= C(i)+ e(i)

la distanza di hamming di tra Ye C(i) è pari al peso dell'errore e(i)

�� pertanto se p>1/2 la regola di decisione ottima associa selezionata

la parola di codice corrispondente all'errore di peso minimo.

Rivelazione e correzione d'errore per i codici a bl occo � TEOREMA

Un codice a blocco lineare (n,k) con distanza minima dmin può correggere

tutti i vettori d'errore che non contengano più di

2/)1( min −= dt

errori. Tale codice è detto a correzione di t errori.

Dim.: la regola di decisione ottima fa corrispondere una data parola di codice a tutte le sequenze ricevibili che sono più vicine ad essa piuttosto che ad una delle altre parole di codice. Un vettore d'errore con non più di

2/)1( min −= dt errori genera una sequenza ricevuta che cade all'interno della regione corretta.pertanto la correzione dell'errore è possibile

Rivelazione e correzione d'errore per i codici a bl occo � Poiché dato un codice ed una parola ricevibile è possibile calcolare la

parola di codice più vicina, l'uso diretto dell'algoritmo di decodifica a

distanza minima richiede la memorizzazione di una tavola con 2n ingressi

dmin errori corretti

errori rilevati

2 0 1 3 1 2 4 1 3 5 2 4 6 2 5 7 3 6

Rivelazione e correzione d'errore per i codici a bl occo � Un approccio più efficiente consiste nell'associare ad ogni sindrome il

vettore d'errore di peso minimo che possa produrre la sindrome osservata.

�� Aggiungendo ad una parola di codice una parola non di codice la

somma ha la stessa sindrome della parola non di codice

S= CmHT+ eHT=eHT

�� Per ogni sindrome S esistono 2k parole di codice che la generano, che

prendono il nome di coinsieme

�� L'elemento del coinsieme di peso minimo prende il nome di

rappresentante del coinsieme

Schieramento standard dato il codice (6,3) associato alla matrice

=101100

011010

111001

G a cui corrisponde

=100101

010011

001111

ad esso è associato lo schieramento standard

sindrome Codice 000 000000 100111 010110 001101 110001 101010 011011 111100 111 100000 000111 110110 101101 010001 001010 111011 011100 110 010000 110111 000110 011101 100001 111010 001011 101100 101 001000 101111 011110 000101 111001 100010 010011 110100 100 000100 100011 010010 001001 110101 101110 011111 111000 010 000010 100101 010100 001111 110011 101000 011001 111110 001 000001 100110 010111 001100 110000 101011 011010 111101 011 000011 100111 010101 001110 110010 101001 011000 111111

Schieramento standard � la prima riga dello schieramento standard è costituita dalle 2k parole di

codice riordinate per peso crescente da sinistra verso destra

� le successive righe sono costituite dagli altri coinsiemi

� per ciascuna riga, a sinistra si scrive il rappresentante di coinsieme

� le altre parole si ottengono sommando a ciascuna parola di codice della

prima riga, il rappresentante di coinsieme

� a margine di ciascuna riga si annota inoltre la sindrome corrispondente

Algoritmo per la correzione degli errori � FUORI LINEA

costruzione della tabella di decodifica a 2n-k ingressi corrispondenti alle diverse

sindromi contenente

(sindrome, rappresentante di coinsieme)

ovvero

(Si,ei), i=1,…,2 n-k

Algoritmo per la correzione degli errori � IN LINEA

1. calcolo della sindrome S della sequenza ricevuta

2. ricerca nella teballa di decodifica della riga corrispondente

associatocoinsiemediantirappresentm →e

3. stima della sequenza trasmessa come

mm eYC ˆˆ +=

Algoritmo per la correzione degli errori � Dato il codice di Hamming (7,4) si ha

Sindrome Rappresentante di coinsieme

cifra errata

000 0000000 Nessuna 001 0000001 7 010 0000010 6 011 0001000 4 100 0000100 5 101 1000000 1 110 0010000 3 111 0100000 2

Algoritmo per la correzione degli errori pertanto se Y=(1101010) si ha

[ ] [ ]110

0101011 =

== TYHS

il rappresentante di coinsieme è [0 0 0 1 0 0 0] e quindi

[ ] [ ][ ]0100011

00010000101011ˆ

==+=mC

Codici Convoluzionali

� Un codificatore binario convoluzionale (n, k) con lunghezza di vincolo N è un sistema a memoria finita che genera n cifre binarie per ogni k cifre di messaggio presentate al suo ingresso.

� Può essere pensato come una macchina sequenziale costituita da un registro a scorrimento a Nk posizioni, suddivise in N stadi di k elementi, un circuito combinatorio di uscita e un convertitore parallelo serie.

1 2 … k 1 2 … k 1 2 … k

1 2 … … … … … n

Nk elementi

� Il diagramma di connessione tra le celle del registro a scorrimento ed i

sommatori modulo-2 è specificato dall'insieme dei coefficienti

{ }njkNigij ,...,1,,...,1, ==

� Tali coefficienti possono essere riorganizzati in N sottomatrici G1, G2, …,

GN, che descrivono le connessioni del i-esimo stadio del registro a

scorrimento con le n celle del registro di uscita.

010101

(10) (01)

Diagramma a traliccio Diagramma degli stati di un codice (3,1)

Decodifica a massima verosimiglianza Si indichino con St lo stato del codificatore convoluzionale, con St∈{0,1,…,M-1}, con M=2Nk, e con Xt l’uscita del sistema nell’istante t. Si indichi inoltre con

'1 ' 1 '( , ,..., , )t

t t t t tS S S S+ −=S

la successione degli stati dall’istante t, all’istante t’, e con '

1 ' 1 '( , ,..., , )tt t t t tX X X X+ −=X

la successione delle uscite dall’istante t, all’istante t’.

Nel seguito, per semplicità e compattezza, si assume che l’ingresso del codificatore

convoluzionale sia costituito dall’uscita di un codificatore (di sorgente) entropico, cosicché i

simboli binari in ingresso possano essere considerati statisticamente indipendenti, identicamente

distribuiti ed equiprobabili.

La sorgente parte dallo stato iniziale S0=0 e ritorna nello stesso stato all’istante finale τ.

Si assume infine che il canale di comunicazione sia un canale senza memoria per cui la

probabilità condizionata della successione ricevuta dal ricevitore

1 1 2 1( , ,..., , )Y Y Y Yττ τ−=Y

{ } { }1 1 1 11 1

Pr Pr , , ( , )j j j j jj j

Y S S R Y X S Sτ τ

τ τ− −

= = ∏ ∏Y S .

L’obiettivo è quello di calcolare la successione degli stati tale che

{ } { }{ } { }

1 1 1 1 1

Pr ,ˆ Pr | Pr ,

PrArg Max Arg Max Arg Max

τ τ τ

τ ττ τ τ τ τ

= = = S S S

S YS S Y S Y

A tal fine si osservi che

{ } { } { }1 11 1 1 1 1 1Pr , Pr | , Pr ,Yτ τ τ τ τ τ

τ− −=S Y S Y S Y

{ } { } { }1 1 1 1 11 1 1 1 1 1Pr | , Pr | , Pr ,Y Sτ τ τ τ τ τ

τ τ− − − − −= S Y S Y S Y

Poichè il sistema è markoviano, se lo stato Sτ−1 è noto gli eventi che si producono dopo l’istante

τ-1 non dipendono dalle uscite del sistema sino all’istante τ-1. Pertanto

{ } { } ( )11 1 1 1Pr | , Pr | , , ,Y Y S S R Y X S Sτ τ

τ τ τ τ τ τ τ−

− − = = S Y

{ } { }1 11 1 1Pr | , Pr |S S Sτ τ

τ τ τ− −

−=S Y

e quindi

{ } { } { } { }1 11 1 1 1 1 1Pr , Pr | , Pr | Pr ,Y S S S Sτ τ τ τ

τ τ τ τ τ− −

− −=S Y S Y

Ovvero riapplicando iterativamente la procedura si ha

{ } { } { }1 1 1 11

Pr , Pr | , Pr |t t t t tt

Y S S S Sτ

τ τ− −

= ∏S Y

{ } ( ) { }1 1 1 11

Pr , , , Pr |t t t t tt

R Y X S S S Sτ

τ τ− −

= ∏S Y

� Data una sequenza ricevuta 1τY di lunghezza τ, a cui corrisponde un cammino

di lunghezza τ sul traliccio, il decodificatore ottimo a massima

verosimiglianza deve scegliere il cammino del traliccio per il quale risulti

massima la probabilità condizionata { }1 1Pr ,τ τS Y , ovvero il suo logaritmo.

Decodifica a massima verosimiglianza

� Considerato che ciascuno dei 2kN stati in cui si può trovare il sistema

ammette solo 2k possibili successori. Pertanto, indicato con T(m) l’insieme

dei successori dello stato m-esimo, nel caso in cui la sequenza in ingresso al

codificatore convoluzionale sia una sequenza i.i.d. binaria con simboli

equiprobabili, la probabilità di transizione vale:

2 ( ')Pr | '

m T mS m S m

altrimenti

∈= = =

� Conseguentemente, all’istante t sono possibili solo 2(k+1)N transizioni. Nel

seguito indicheremo con r l’indice che identifica le transizioni ammissibili

e con ( )rtX l’uscita corrispondente ovvero la sequenza di n cifre binarie

relativa al cammino r-esimo del traliccio che congiunge gli stati St e St-1 .

� Pertanto il decodificatore ottimo deve trovare il cammino per il quale

{ } ( ) { }( )

( )1 1 1 1

Pr , , , Pr | 2 ,r

k rt t t t t t t

Max Max R Y X S S S S Max Rτ τ

τ ττ τ −

− −= =

= = ∏ ∏S S X

S Y Y X

� Ovvero per cui

{ }( )

, 1,..., 1

Max Rτ

� O equivalentemente

{ }( )

, 1,..., 1

Min Rτ

− ∑X

Decodifica a massima verosimiglianza: canale binari o simmetrico

• Indicando con ( )rtd la distanza di Hamming tra le due sequenze tY e ( )r

tX , per

un canale binario simmetrico con probabilità di rivelazione corretta p si ha:

( ) ( ) ( )( ), (1 )

r rl ln d dr

t tP p p−= −Y X

e quindi

( ) ( ) ( )

( ) ( )

ln , ln ln(1 )

ln ln(1 )1

r r rt t t t

r rt t

R n d p d p

pd n p d

pα β

= − + − =

= − + − = − −−

• Pertanto se p>1/2, α>0 e il problema si riduce a

{ }( )

, 1,..., 1r

Min dτ

= =∑

Decodifica a massima verosimiglianza: canale gaussi ano additivo

• Nel caso in cui il canale sia caratterizzato da un rumore gaussiano additivo

bianco, con varianza 2Nσ si ha:

( )( )

1, exp

t t nN

pσπσ

− = −

X YY X

e quindi 2( )

( ) 22

ln , ln 22 2

t t NN

nR πσ

− = + X Y

• Pertanto il problema si riduce a

{ }( )

, 1,..., 1r

−∑X

Decodifica a massima verosimiglianza

� quindi, tralasciando le costanti non essenziali il problema si riduce alla

ricerca del cammino che rende minimo

Canale binario simmetrico ( ) ( )r rt tV d=

Canale gaussiano 2( ) ( )r rt t tV = −X Y

� Come era intuitivo, la decodifica a massa verosimiglianza, richiede nel caso

del canale discreto binario simmetrico la minimizzazione della distanza di

Hamming fra la sequenza ricevuta e quella che sarebbe stata ricevuta in

assenza di errore in corrispondenza al singolo cammino del traliccio del

codice.

� Nel caso del canale gaussiano additivo richiede la minimizzazione della

distanza euclidea (norma L2) fra la sequenza ricevuta e quella che sarebbe

stata ricevuta in assenza di rumore in corrispondenza al singolo cammino del

traliccio del codice.

� Per la ricerca del minimo di tale funzionale può essere impiegato l'algoritmo

di Viterbi (1969), essendo la metrica di ogni ramo la distanza di Hamming tra

le sequenze binarie.

Algoritmo di Viterbi (1969) per stato iniziale noto � Denotiamo ciascuno degli M=2k stati con il numero d'ordine corrispondente

1. Passo:

1.1. Il decodificatore considera tutti gli MN cammini relativi ai primi N rami

del traliccio che si dipartono dal nodo iniziale, supposto in questo caso

noto, e computa le funzioni ( )1( , )r

t t tV S S− , relative a ciascun ramo ovvero

• nel caso di decisione soft: ( )( )ln rt tp− Y X , ed in particolare nel caso di

canale gaussiano additivo 2( )r

t t−X Y

• nel caso di decisione hard: le distanze di Hamming )( rld

• Esempio per k=1, N=2

110 111 011 001 000 000 000

l=0 l=1 l=2 l=3 l=4 l=5 l=6 l=7

Algoritmo di Viterbi (1969) per stato iniziale noto 1.2. Per analogia con quanto accade nei passi successivi dell’algoritmo

ciascuna delle MN sottosequenze di stati corrispondente ad un cammino

che si diparte dal nodo iniziale viene indicata con il termine di

superstite. Per ciascun superstite viene calcolata la metrica relativa al

cammino associato sommando le metriche dei singoli rami

Stato finale Superstite Metrica S1 S1S1 5 S2 S1 S1 2 S3 S1 S2 2 S4 S1 S2 3

Algoritmo di Viterbi (1969) per stato iniziale noto 2. passo

2.1. Per ciascun superstite del passo 1 vengono calcolate le M metriche relative ai rami del traliccio divergenti dal nodo 1Ns − e vengono sommate alla metrica corrispondente al superstite. Ciò produce MN funzioni relative agli MN cammini di lunghezza N+1.

110 111 011 001 000 000 000

l=0 l=1 l=2 l=3 l=4 l=5 l=6 l=7

2.2. Il decodificatore compara le funzioni in gruppi di M, eseguendo i confronti sui sottinsiemi di cammini che terminano in uno stesso stato conservando solo il cammino con la metrica più piccola che diviene il nuovo superstite associato a tale stato

110 111 011 001 000 000 000

l=0 l=1 l=2 l=3 l=4 l=5 l=6 l=7

Stato finale Superstite Metrica

Algoritmo di Viterbi (1969) per stato iniziale noto j. passo

j.1 Per ciascun superstite del passo j-1 vengono calcolate le M metriche

relative ai rami del traliccio divergenti dal nodo terminale

corrispondente e vengono sommate alla metrica corrispondente al

superstite. Ciò produce MN funzioni relative agli MN cammini di

lunghezza j.

Superstiti al passo j-1

110 111 011 001 000 000 000

l=0 l=1 l=2 l=3 l=4 l=5 l=6 l=7

Stato finale Superstite Metrica S

Calcolo delle metriche dei singoli cammini divergenti dai superstiti

110 111 011 001 000 000 000

l=0 l=1 l=2 l=3 l=4 l=5 l=6 l=7

j.2 Il decodificatore compara le funzioni in gruppi di M, eseguendo i confronti sui sottinsiemi di cammini che terminano in uno stesso stato conservando solo il cammino con la metrica più piccola che diviene il nuovo superstite associato a tale stato.

110 111 011 001 000 000 000

l=0 l=1 l=2 l=3 l=4 l=5 l=6 l=7

Stato finale Superstite Metrica

Algoritmo di Viterbi (1969) per stato iniziale noto Passo finale:

� Nel caso in cui anche lo stato finale sia noto (ad es. nel caso della

codifica di canale per servidi di fonia in GSM) si seleziona tra i superstiti

quello che termina in tale stato.

� Nel caso in cui lo stato finale non sia noto si seleziona il superstite

corrispondente al cammino più corto.

Turbocodici

Turbocodici • Lo schema base è costituito da due codificatori convoluzionali di tipo ricorsivo

sistematico (RSC: Recursive Systematic Convolutional), chiamati codificatori costituenti, concatenati in parallelo e separati tra loro tramite un interleaver (permutatore o interlacciatore).

• Ogni RSC costituente produce in uscita, in base al tasso di codifica r, per ciascun bit d’ingresso, una replica dello stesso bit (systematic output o codificatore sistematico) sommata ad un numero di bit di parità.

• Se un RSC encoder è caratterizzato da r=1/2, viene usato uno soltanto dei due systematic output provenienti dai precedenti encoder;

• questo avviene perché l’altro è la versione permutata di quello scelto e per ogni bit di sorgente ottengo in uscita il bit stesso più un bit di parità.

• i codificatori usati nel turbo encoder sono ricorsivi cioè con controreazione (feedback). mentre i codificatori convoluzionali standard sono del tipo in avanti (feedforward) senza controreazione.

Recursive Systematic Convolutional (RSC) Encoder

Gli encoder RSC sono ottenuti a partire dai codificatori convoluzionali non ricorsivi e non

sistematici (convenzionali) riportando in ingresso come input uno dei loro output codificati.

Stato finale del codificatore Per il codificatore convoluzionario convenzionale, si forza lo stato finale accodando in ingresso al blocco di bite prodotto dalla soregente, kN bit pari a zero. A causa del feedback, per l’RSC questa strategia non è possibile. I bits terminali accodati dipendono, in questo caso, dallo stato dell’encoder e sono molto difficili da precalcolare. La presenza dell’interliver tra i codificatori costituenti fa sì che, anche se per uno dei codificatori è nota la sequenza che lo riporta nello stato “all-zero”, la sequenza complessiva rimescolata dall'interleaver non riporta n generale il secondo codificatore nello stato “all-zero”. Per superare questo problema è stato proposto uno schema semplice ma molto funzionale che viene riportato di seguito.

Per codificare la sequenza di input lo swich è posizionato in A, per la terminazione in B.

BLOCK INTERLEAVER • É il più usato nei sistemi di comunicazione. • Scrive per colonne dall’alto verso il basso e da sinistra a destra. • Legge per righe da sinistra a destra e dall’alto verso il basso.

Random (Pseudo-Random) Interleaver • Selezione puramente aleatoria di una tra tutte le possibili permutazioni

della sequenza d’ingresso. • Tutte le permutazioni sono equiprobabili.

0 1 1 0 1 0 0 1

0 2 5 7 1 6 3 4

0 0 0 1 1 1 1 0

0 1 2 3 4 5 6 7

Ingresso

Indice i

Permutazione

Uscita

Circular-Shifting Iterleaver • La permutazione p di questo interlacciatore è definita come

p(i)=(ai+s)mod L • Deve soddisfare a<L e s<L con a primo rispetto ad L, dove i è l’indice,

a è il passo e s è l’offset.

• Esempio per L=8, a=3 e s=0. L

Si vede come bit adiacenti nella sequenza d’ingresso si trovano a distanza 3 o 5

0 1 1 0 1 0 0 1

0 3 6 1 4 7 2 5

0 0 0 1 1 1 1 0

0 1 2 3 4 5 6 7

Ingresso

Indice i

Permutazione

Uscita

in quella d’uscita.

Semirandom Interleaver • E’ un compromesso tra un random interleaver ed uno tra il “block” ed il

“circular- shifting” interleaver. • In essenza, in un interleaver semi-random di lunghezza L, caratterizzato da

una distanza minima uguale a / 2S L< , l’n-esimo indice della permutazione

è calcolato generando a caso un intero in.

• Se |in - in-k |>S, per k=1,2,…,S, in è considerato valido, altrimenti esso viene

scartato e la procedura viene reiterata generando un nuovo valore per

l’indice.

• L’insieme degli interleaver completamente aleatori è il sottoinsieme degli

interleaver semialeatori corrispondente a S=1.

Turbocodici - Calcolo della Probabilità A Posterior i (APP) Si consideri una sorgente di Markov a tempo discreto con un numero finito di stati. Si indichino con St lo stato della sorgente, con St∈{0,1,…,M-1}, e con Xt l’uscita del sistema nell’istante t. Si indichi inoltre con

'1 ' 1 '( , ,..., , )t

t t t t tS S S S+ −=S

la successione degli stati dall’istante t, all’istante t’, e con '

1 ' 1 '( , ,..., , )tt t t t tX X X X+ −=X

la successione delle uscite dall’istante t, all’istante t’.

La sorgente di Markov sia caratterizzata dalle seguenti probabilità di transizione

{ }1( | ') Pr 't t tp m m S m S m−= = =

E dalle seguenti probabilità condizionate delle uscite:

{ }1( | ', ) Pr ';t t t tq X m m X X S m S m−= = = =

Infine la sorgente parte dallo stato iniziale S0=0 e ritorna nello stesso stato all’istante

finale τ.

Si assume infine che il canale di comunicazione sia un canale senza memoria per cui la

probabilità condizionata della successione ricevuta dal ricevitore

1 1 2 1( , ,..., , )Y Y Y Yττ τ−=Y

{ } { }1 11 1

Pr Pr ( )j j j jj j

Y X R Y Xτ τ

= =∏ ∏Y X .

L’obiettivo è quello di calcolare le probabilità congiunte

• { }1( ) Pr ;t tm S m τλ = = Y

• { }1 1( ', ) Pr ; ';t t tm m S m S m τσ −= = = Y

Infatti, una volta note tali probabilità è possibile calcolare le probabilità condizionate:

{ } { }{ }

Pr ; ( )Pr

Pr ; ( )

t tt M M

t tn n

S m mS m

λ− −

== = =

=∑ ∑

{ } { }{ }

1 1 1 1 1 1

1 10 ' 0 0 ' 0

Pr ; '; ( ', )Pr ';

Pr ; '; ( ', )

t t tt t M M M M

t t tn n n n

S m S m m mS m S m

S n S n n n

−− − − − −

−= = = =

= == = = =

= =∑∑ ∑∑

A tal fine, posto

{ }1( ) Pr ; tt tm S mα = = Y

{ }1( ) Prt t tm S mτβ += =Y

{ }1( ', ) Pr ; 't t t tm m S m S mγ −= = =Y

Si osservi che per λt(m) si ha

{ }1( ) Pr ;t tm S m τλ = = Y

{ } { }1 1 1Pr ; Pr ;t tt t tS m S mτ+= = =Y Y Y

Poichè il sistema è markoviano, se lo stato St è noto gli eventi che si producono dopo

l’istante t non dipendono dalle uscite del sistema sino all’istante t. Pertanto

{ } { }1 1( ) Pr Pr ; tt t t tm S m S mτλ += = =Y Y

( ) ( )t tm mα β=

Similmente:

{ }1 1( ', ) Pr ; ';t t tm m S m S m τσ −= = = Y

{ } { }1 1 1 1 1Pr '; ; Pr '; ;t tt t t t tS m S m S m S mτ+ − −= = = = =Y Y Y

e sempre per la markovianità si ha:

{ } { }1 1 1 1Pr '; ; Prtt t t t tS m S m S mτ τ+ − += = = =Y Y Y

Conseguentemente

{ } { }1 1 1( ', ) Pr Pr '; ; tt t t t tm m S m S m S mτσ + −= = = =Y Y

{ } { } { }1 11 1 1 1 1Pr Pr ; '; Pr ';t t

t t t t t tS m S m Y S m S mτ − −+ − −= = = = =Y Y Y

1( ) ( ) ( ', )t t tm m m mα β γ−=

Inoltre, sempre per la markovianità si ha:

( ) ( ', ) ( ')M

t t tm

m m m mα γ α−

1 1' 0

( ) ( , ') ( ')M

t t tm

m m m mβ γ β−

con condizioni al contorno

1 0( )

per mm

altrimentiα

1 0( )

per mm

altrimentiτβ=

Inoltre

{ }1( ', ) Pr ; ; 't t t t tX

m m S m Y X X S mγ −= = = =∑

{ } { }1 1Pr '; ; Pr ; 't t t t t t tX

Y S m S m X X S m X X S m− −= = = = = = =∑

{ } { }1Pr Pr ; 't t t t tX

Y X X S m X X S m−= = = = =∑

{ } { } { }1 1Pr Pr '; Pr 't t t t t t tX

Y X X X X S m S m S m S m− −= = = = = = =∑

( , ) ( | ', ) ( | ')t t tX

R Y X q X m m p m m=∑

Algoritmo AAP 1. Inizializzazione

1 0( )

per mm

altrimentiα

b. 1 0

per mm

altrimentiτβ==

2. Per ogni t=1,…,τ, ricevuto Yt, si calcola

a. ( ', ) ( , ) ( , ', ) ( , ')t t t tX

m m R Y X q X m m p m mγ ==∑

( ) ( ', ) ( ')M

t t tm

m m m mα γ α−

3. Per ogni t=τ−1…,1, ricevuto Yt, si calcola

1 1' 0

( ) ( , ') ( ')M

t t tm

m m m mβ γ β−

4. Per ogni t=1,…,τ si calcola

a. Si calcolano i valori

( ) ( ) ( )t t tm m mλ α β=

b. Si normalizzano le probabilità per ottenere le probabilità condizionate

{ }1 1

= =∑

c. Si calcolano i valori

1( ', ) ( ) ( ) ( ', )t t t tm m m m m mσ α β γ−=

d. Si normalizzano le probabilità per ottenere le probabilità condizionate

{ }1 1 1 1

( ', )Pr ';

( ', )

tt t M M

m mS m S m

σ− − −

= = =∑∑

Turbocodice + canale gaussiano additivo

Interleaver Π

RSC C1

RSC C2

dt X t

Codificatore turbo

Interleaver Π

DECODE

R DEC1

Decodificatore turbo

[ ]1τ

[ ]1 1

[ ]2 1

[ ]1τ

DECODE

R DEC1

Deinterleaver Π−1

τ Λ ( )2

• Il ricevitore ottimo si basa sul criterio di decisione bayesiano

Λ(dk)

essendo

{ }{ }

Pr 1 , ,( ) log

Pr 0 , ,k

=X Y Y

{ }{ }

{ }1 2 1 2

1 2 1 2

Pr 1, , , Pr , ,log

Pr , , Pr 0, , ,k

=X Y Y X Y Y

X Y Y X Y Y

{ }{ }

Pr , , / 1 Pr 1log log

Pr , , / 0 Pr 0k k

= == +

= =X Y Y

{ }{ }

Pr 1 Pr , / 1 Pr / 1, ,log log log

Pr 0 Pr , / 0 Pr / 0, ,k k k

= = == + +

= = =X Y Y X Y

X Y Y X Y

{ }{ }

Pr 1 Pr / 1 Pr / 1, Pr / 1, ,log log log log

Pr 0 Pr / 0 Pr / 0, Pr / 0, ,k k k k

k k k k

d d d d

= = = == + + +

= = = =X Y X Y X Y

X Y X Y X Y

Si osserva che il logaritmo del rapporto di verosimiglianza si compone di 4 termini:

{ }{ }

Pr 1( ) log

Pr 0kapriori

= rappresenta il contributo relativo

all'informazione a priori { }{ }

( ) Pr / 1( ) log

Pr / 0k

X rappresenta il contributo relativo

all'osservazione della parte sistematica del codice

{ }{ }

1 1( )

Pr / 1,( ) log

Pr / 0,k

=Y Y X

Y X rappresenta il contributo relativo

all'osservazione dei bit di parità del primo codificatore

{ }{ }

2 2 1( )

Pr / 1, ,( ) log

Pr / 0, ,k

=Y Y X Y

Y X Y rappresenta il contributo relativo

all'osservazione dei bit di parità del secondo codificatore

Algoritmo di decodifica L'algoritmo di decodifica approssima il codificatore ottimo attraverso un procedimento

iterativo.

Al primo passo il primo decodificatore calcola

{ }{ }

Pr 1 ,( ) log

Pr 0 ,k

A questo scopo è utile osservare

{ }{ }

1 1 11

Pr 1 , Pr 1 , Pr ,( ) log log

Pr ,Pr 0 , Pr 0 ,k k

= =Λ = = =

= =X Y X Y X Y

X YX Y X Y

[ ] [ ]{ }[ ] [ ]{ }

111 1 1 1 11 1

Pr 1, , , , , ,log

Pr 0, , , , , ,

k Nk Nk k k k

−−+ +

X Y X Y

[ ] [ ]{ } [ ] [ ]{ }[ ] [ ]{ } [ ] [ ]{ }

1 11 11 1 1 1 1 1 1 1 1 11 1 1 1

Pr / 1, , , , , Pr 1, , , , ,log

Pr / 0, , , , , Pr 0, , , , ,

k N k Nk N k Nk k k k kk k

x d y d y

− −− −+ ++ +

= == =

X Y X Y X Y X Y

[ ] [ ]{ }[ ] [ ]{ }

111 1 1 1 11 1

Pr / 1, , , , ,log

Pr / 0, , , , ,

k Nk Nk k k k

−−+ +

X Y X Y

[ ] [ ]{ }[ ] [ ]{ }

111 1 1 1 11 1

Pr 1, , , , ,log

Pr 0, , , , ,

k Nk Nk k k

−−+ +

X Y X Y

Poiché il codice è sistematico, nel caso di modulazione BPSK si ha

k− 1+ n

cosicché

[ ] [ ]{ }[ ] [ ]{ }

111 1 1 1 1 11 1

Pr 1, , , , , , ,log

Pr 0, , , , , , ,

k Nk Nk k k k k k

x d S m S m y

−−− + +

′= = ==

′= = =

X Y X Y

{ }{ }

Pr 1log

Pr 0k k

( 1) ( 1) 2

σ σ− − += − =

Inoltre

[ ] [ ]{ }[ ] [ ]{ }

111 1 1 1 11 1

Pr 1, , , , ,log

Pr 0, , , , ,

k Nk Nk k k

−−+ +

X Y X Y

[ ] [ ]{ }[ ] [ ]{ }

111 1 1 1 1 11 1

Pr 1, , , , , , , ,log

Pr 0, , , , , , , ,

k Nk Nk k k k k k

d S m S m x y

−−− + +

′= = == =

′= = =

∑∑

X Y X Y

Pertanto

{ }{ }

Pr 1 ,( ) log

Pr 0 ,k

=Λ = =

[ ] [ ]{ }[ ] [ ]{ }

111 1 1 1 1 11 1

1 1 1 1 1 11 1

Pr 1, , , , , , ,2

logPr 0, , , , , , ,

k Nk Nk k k k k

k Nk Nnk k k k k

d S m S m yx

d S m S m yσ

−−− + +

′= = == +

′= = =

∑∑

X Y X Y

ovvero

d x Wσ

Λ = +

avendo posto

[ ] [ ]{ }[ ] [ ]{ }

111 1 1 1 1 11 1

1 1 1 1 1 11 1

Pr 1, , , , , , ,log

Pr 0, , , , , , ,

k Nk Nk k k k k

d S m S m yW

d S m S m y

−−− + +

′= = ==

′= = =

∑∑

X Y X Y

si noti che

1k= Λ

k) xk =0

Inoltre

[ ] [ ]{ }111 1 1 1 1 11 1

Pr 1, , , , , , ,k

k Nk Nk k k k k

d S m S m y−−

− + +′

′= = = =∑∑ X Y X Y

[ ] [ ]{ }[ ]{ }

[ ]{ } [ ]{ }

111 1 1 1 1 11 1

111 1 1 1 1

1 11 11 1 1 1 11 1

Pr , / , 1, , , ,

Pr , 1, , / , ,

Pr / , Pr ,

N kN kk k k kk

kkk k k

k kk kk

y d S m S m

−−+ −+

−−−

− −− −−

′= = = = ×

′× = = = ×

′× =

∑∑ X Y X Y

X Y X Y

e per le ipotesi di markovianità

[ ] [ ]{ } [ ]{ }111 1 1 1 1 1 1 11 1 1

Pr , / , 1, , , , Pr , /k

N k NN k Nk k k k k kk k

y d S m S m S m−−

+ − ++ +′= = = = =X Y X Y X Y

[ ]{ } { }11

1 1 1 1 1 11Pr , 1, , / , , Pr , 1, , /

kkk k k k k ky d S m S m y d S m S m

−−− −′ ′= = = = = = =X Y

quindi, posto

[ ]{ }1 1 1( ) Pr / ,

kkk km S mα = = X Y

[ ]{ }[ ] [ ]{ }

1 1 1 11 1

Pr , /( )

Pr , / ,

NNk kk

k N kN kk k

S mmβ

X Y X Y

[ ]{ }1 1 1 11( , , ) Pr , , , /

kki k k ky m m d i S m S mγ −′ ′= = = =X Y

La componente estrinseca del funzionale di verosimiglianza vale

= logγ

1k, ′m ,m)α

k( ′m )β

′m∑

γ0( y

1k, ′m ,m)α

k( ′m )β

′m∑

• W1k è una funzione dell'informazione relativa alla ridondanza (controlli di

parità) introdotta dal codificatore. In generale esso ha lo stesso segno di dk: quindi

W1k può migliorare l'attendibilità del logaritmo del rapporto di verosimiglianza.

Esso rappresenta l'informazione estrinseca fornita dai bit di parità introdotti dal

primo codificatore

• Per il calcolo di W1k si può impiegare l'algoritmo di Bahl.

• Il secondo decodificatore effettua la decodifica di { dk} a partire da {Λ1(dk)} e da

• quindi

[ ]2 1 2( ) ( )kk kd f d WΛ = Λ +

• Si può verificare che W2k è una funzione della sequenza

{ }1( )n n kd

• Poiché { Λ1(dn)} dipende dalle osservazioni X e Y1 l’informazione estrinseca

W2k è correlata con le osservzaioni xk e y1k, cionondimeno maggiore è il valore di

|n-k| minore è la correlazione tra Λ1(dn) e xk e y1k. A causa dell’interleaver

interposto tra il primo ed l secondo decodificatore, in genere la correlazione tra

W2k e xk e y1k è modesta. Pertanto l’informazione estrinseca W2k ed i dati ricevuti

xk e y1k possono essere rielaborati insieme al fine di fornire una valutazione più

affidabile di dk

• Per le successive iterazioni si procede come segue:

Al secondo passo, posto

{ }2 2 ( ) 01( )k kk dk

z W dΛ =

= = Λ

Per il primo codificatore si calcola

1 12 2

2 2( )

kk k kn z

d x z Wσ σ

Λ = + +

[ ]1 1 0, 0( )

kx zW d

=== Λ

Poichè Λ1(dk) è calcolato utilizzando i valori zk forniti dal secondo decoder DEC2, il

decoder DEC2 in ingresso, oltre a Y2, ha

[ ]1 1 0

( ) ( )k

k k zd d

=Λ = Λ%

• quindi

2 1 2( ) ( )kk kd f d W Λ = Λ +

Inoltre l’informazione estrinseca fornita da DEC2 che alimenta il primo

decodificatore, dal terzo passo in poi si calcola come segue

{ }2 2 ( ) 01( )k kk dk

z W dΛ =

= = Λ%

Infine, la decisione finale è calcolata come segue

[ ]2ˆ ( )k kd sign d= Λ

Codici punturati

� L’operazione di punturazione consiste nell’eliminazione selettiva di alcuni

caratteri della sequenza prodotta in uscita da un codificatore convoluzionale

ordinario, secondo una legge (periodica) nota sia al codificatore che al

decodificatore.

� L’obiettivo è quello di generare un codice caratterizzato da un tasso elevato a

partire da un codice a tasso basso e di ridotta complessità computazionale.

Generazione di un codice punturato con tasso ¾ a partire da un codice con tasso 1/3

0 0 00

Punturazione

SERIE DISCRETE

• Presa una serie aleatoria X(t; ω) essa si dice discreta se le variabili aleatorie X(t1), X(t2), … , X(tn) estratte negli n istanti t1, t2, … , tn sono variabili aleatorie discrete che possono assumere una fra L possibili determinazioni appartenenti all’insieme A:

A= x1,x2, ...,xL{ }

con L eventualmente infinito. • L’insieme A prende il nome di Alfabeto di sorgente. • Analogamente la serie aleatoria si dice continua se le predette variabili

aleatorie risultano essere v. a. continue.

SERIE DI MARKOV • Definizione. Una serie aleatoria discreta (e la sorgente che la emette) si

dice di Markov di ordine M se detti

tk1,tk2

, ...,tkN

N istanti di tempo in ordine crescente con N > M+1, e indicate con

1 21 2[ ] ( ), [ ] ( ),..., [ ] ( )nk k n kx k x t x k x t x k x t= = =

le generiche determinazioni delle v. a. estratte in detti istanti, le probabilità delle determinazioni della v. a. X [ kn ] condizionate alle determinazioni x[k1], x[k2],…, x[kn-1] dipendono dalle determinazioni delle M variabili aleatorie che precedono X[kn]. In formule

[ ] [ ] [ ]{ }[ ] [ ] [ ]{ }

Pr ,...,

k k kn n

k k kn n n M

n i n i i

n i n i n M i

X k x X k x X k x

− −

= = = =

= = = = (1)

• Per M = 1 la serie viene detta di Markov semplice.

• Si osservi che per le serie di Markov (e per i processi di Markov che ne rappresentano l’estensione al caso continuo), la gerarchia di qualsiasi ordine è ottenibile a partire dalla conoscenza della gerarchia di probabilità di ordine M+1.

• Infatti in base alla (1) per n > M+1 si ha:

{ }1 2 1

Pr [ ] , [ 1] , [ 2] ,..., [1]n n ni i i iX n x X n x X n x X x

− −= − = − = = =

{ }1 2 1

Pr [ ] / [ 1] , [ 2] ,..., [1]n n ni i i iX n x X n x X n x X x

− −= = − = − = = ×

{ }1 2 1

Pr [ 1] , [ 2] ,..., [1]n ni i iX n x X n x X x

− −× − = − = = =

{ }1 2

Pr [ ] / [ 1] , [ 2] ,..., [ ]n n n n Mi i i iX n x X n x X n x X n M x

− − −= = − = − = − = ×

{ }1 2 1

Pr [ 1] , [ 2] ,..., [1]n ni i iX n x X n x X x

− −× − = − = = =

{ }1 2

− − −= = − = − = − = ×

{ }1 2 1

Pr [ 1] / [ 2] ,..., [1]n ni i iX n x X n x X x

− −× − = − = = ×

{ }2 1

Pr [ 2] ,..., [1]ni iX n x X x

−× − = = =

{ }1 2

− − −= = − = − = − = ×

{ }1 2 1

Pr [ 1] / [ 2] ,..., [ 1 ]n n n Mi i iX n x X n x X n M x

− − − −× − = − = − − = ×

{ }2 1

Pr [ 2] ,..., [1]ni iX n x X x

−× − = = =

{ }1 2

− − −= = − = − = − = ×

{ }1 2 1

Pr [ 1] / [ 2] ,..., [ 1 ] ...n n n Mi i iX n x X n x X n M x

− − − −× − = − = − − = × ×

{ }1 1

Pr [ 1] / [ ] ,..., [1]M Mi i iX M x X M x X x

+× + = = = ×

Pr [ ] ,..., [1] .Mi iX M x X x× = =

Ovvero

{ }1 2 1

Pr [ ] , [ 1] , [ 2] ,..., [1]n n ni i i iX n x X n x X n x X x

− −= − = − = = =

{ }1 2

Pr [ ] / [ 1] , [ 2] ,..., [ ]m m m m M

i i i im M

X m x X m x X n x X m M x− − −

= += = − = − = − = ×∏

Pr [ ] ,..., [1] .Mi iX M x X x× = = (2)

ed inoltre:

[ ] [ ] [ ]{ }[ ] [ ] [ ]{ }

[ ] [ ]{ }

Pr 1 ,...,

Pr , 1 ,...,

Pr 1 ,...,

n n n M

X n x X n x X n M x

X n x X n M x

− −

= − = − = =

= − = − ==

− = − =

• Ovviamente le gerarchie di ordine inferiore a M+1 possono essere ottenute per saturazione della gerarchia di ordine M+1.

RELAZIONE DI CHAPMAN – KOLMOGOROFF

• Anche nel caso delle serie di Markov, la gerarchia di probabilità di ordine

M+1 dovrà soddisfare la relazione di consistenza rappresentata dalla relazione di CHAPMAN – KOLMOGOROFF.

• Per derivare le implicazioni di tale relazione, si cominci con il considerare una serie di Markov semplice.

• A tale scopo si osservi che nel caso di serie discreta, la gerarchia di probabilità del 1° ordine può essere riscritta in forma più compatta introducendo il vettore P[kn] i cui elementi sono costituiti dalle probabilità che la v. a. X[kn] assuma le singole determinazioni x1, …, xL . In formule:

Pr{ [ ] }

Pr{ [ ] }[ ]

Pr{ [ ] }

X k xk

= = = =

D’altronde, considerando due istanti di tempo tkn e tkl

, per l’elemento i–

esimo di tale vettore si ha

{ } { }1

Pr [ ] Pr [ ] , [ ] 1,...,L

n i n i l jj

X k x X k x X k x i L=

= = = = =∑ (5)

ovvero, esprimendo la probabilità congiunta tramite le probabilità condizionate si ha:

[ ]{ } [ ] [ ]{ } [ ]{ }1

Pr Pr Pr , 1,...,L

n i n i l j l jj

X k x X k x X k x X k x i L=

= = = = ⋅ = =∑ (6)

Tale Relazione che vale per il singolo elemento del vettore può essere riscritta in modo più compatto, in forma matriciale, come segue:

[ ] [ , ] [ ]n n l lk k k k=ΠP P (7)

in cui Π[ kn ,kl ] è la matrice LxL il cui generico elemento (i, j) è costituito dalla

probabilità condizionata { }Pr [ ] [ ]n i l jX k x X k x= = :

Pr{ [ ] / [ ] } ... Pr{ [ ] / [ ] }

Pr{ [ ] / [ ] } ... Pr{ [ ] / [ ][ , ]

... ... ...

Pr{ [ ] / [ ] } ... Pr{ [ ] / [ ]

n l n l L

n l n l Ln l

n L l n L l L

X k x X k x X k x X k x

X k x X k x X k x X k xk k

X k x X k x X k x X k x

= = = = = = = = Π = = = = =

Si noti che la somma degli elementi di ciascuna colonna della matrice Π[ kn ,kl ] è pari a 1, in quanto la funzione di normalizzazione

[ ] [ ]{ }1

n i l ji

X k x X k x=

= = =∑ (9)

Si noti che la reazione (7) vale per qualsiasi serie discreta.

• Nel caso in cui la serie discreta sia di Markov semplice, la relazione di

CHAPMAN – KOLMOGOROFF può essere scritta in forma matriciale

come fattorizzazione della matrice Π[ kn ,kl ] . Ovvero presi 3 istanti

tkl< tkm

< tkn si ha:

Π[kn,kl ] = Π[kn,km]Π[km,kl ] (10)

Per la dimostrazione della (10) si osservi che per ciascun elemento della matrice Π[ kn ,kl ] si ha:

[ ] [ ]{ } [ ] [ ] [ ]{ }

[ ] [ ] [ ]{ } [ ] [ ]{ }1

Pr Pr ,

Pr , Pr

n i l j n i m h l jj

n i m h l j m h l jj

X k x X k x X k x X k x X k x

= = = = = = =

= = = = ⋅ = =

∑ (11)

ed essendo la serie di Markov semplice ne consegue che:

[ ] [ ]{ } [ ] [ ]{ } [ ] [ ]{ }1

Pr Pr PrL

n i l j n i m h m h l jj

X k x X k x X k x X k x X k x X k x=

= = = = = ⋅ = =∑ (10’)

Come è facile verificare la (10’), altro non è che la (10) riscritta elemento per elemento. Ciò posto, applicando iterativamente la (10) nella (7) e ponendo per semplicità di notazione

[ ] [ ]1

1,k k k∆= +∏ ∏ (12)

si ha:

[ ] [ ] [ ] [ ] [ ]1 1 1 2 1...n n n l lk k k k k− −= ⋅ ⋅∏ ∏ ∏P P (13)

che fornisce la funzione di probabilità all’istante tkn a partire dalla conoscenza

della funzione di probabilità all’istante tkl e delle matrici delle probabilità

condizionate.

• Di conseguenza si può affermare che una serie di Markov semplice è

completamente descritta sul piano statistico non appena si conoscono le

matrici delle probabilità condizionate a passo 1, e la funzione di probabilità

relativa all’istante iniziale P[0]=P0 che rappresenta la condizione iniziale

dell’equazione alle differenze:

[ 1] [ ] [ ]k k k+ = ΠP P (14)

soddisfatta dalla gerarchia di ordine 1.

• Nel caso in cui la serie di Markov semplice sia omogenea le matrici delle

probabilità condizionate non dipenderanno più dai 2 indici relativi agli

istanti di tempo, ma solo dalla loro differenza. Ciò implica che la matrice

Π1[k] diviene costante rispetto al tempo e le relazioni (14) e (13) si

semplificano come segue:

1[ 1] [ ]k k+ = ΠP P (15)

[ ]1[ ] [ ]n

k n k+ = ΠP P (16)

• Nel caso in cui la serie sia stazionaria oltre alle (15) e (16) si ha:

[ ] [ ]1 cos .k K t+ = = =P P P (17)

Dalle (15) e (17) ne consegue che la gerarchia di ordine 1 deve soddisfare

la relazione:

(I - Π1) P = 0 (18)

• Si osservi che poiché la somma della matrice degli elementi di ciascuna

colonna della matrice Π1 è pari a 1, e che quindi la somma degli elementi di

ciascuna colonna della matrice (I - Π1) è zero, il determinante della matrice

I - Π1 è nullo.

• Quindi il sistema omogeneo (18) ammette almeno ∞1 soluzioni. Affinché

però il vettore P rappresenti una funzione di probabilità deve essere

soddisfatta la condizione di normalizzazione:

Pii =1

∑ =1 (19)

• In effetti, si potrebbe dimostrare che qualora la serie sia anche ergodica, il

rango della matrice (I - Π1) è proprio pari a L-1 e quindi il sistema

omogeneo (18) ammette ∞1 soluzioni, ovvero la funzione di probabilità

individuata dalle (18) e (19) è unica.

• In definitiva, se la serie è ergodica, la matrice delle probabilità,

condizionate a passo 1, descrive completamente il comportamento

statistico della serie, in quando da essa può essere calcolata la gerarchia di

qualsiasi ordine.

STATO DI UNA SERIE DI MARKOV

• Quanto precede può essere esteso agevolmente al caso di sorgente di

Markov di ordine M attraverso l’introduzione del concetto di stato.

• Per definizione lo stato della sorgente S[k] all’istante tk è rappresentato

dalle determinazioni degli M termini precedenti:

S k[ ] =∆

x k−1[ ],x k− 2[ ],...,x k− M[ ]( )

• Pertanto il numero di stati possibili è pari a LM, ovvero pari al numero di

combinazioni di M termini consecutivi delle L possibili determinazioni. Lo

stato della serie di Markov potrà assumere valori sull’insieme

{ }1 2, , ... ,

MLS s s s=

i cui elementi sono i punti di uno spazio prodotto LxLxLx…xL (M volte).

• Da ciò ne consegue che una volta noto lo stato all’istante tk+1, risulta nota

anche la determinazione assunta dalla serie nell’istante tk.

• Inoltre, per come è definito una volta note le proprietà statistiche dello

stato S[k+1] da esse possono essere dedotte (tramite operazioni di somma)

le proprietà statistiche delle v. a. X[k], …, X[k-M+1].

• L’impiego dello stato, nello studio di una sorgente di Markov è motivato

dal seguente teorema:

Teorema. Data una serie di Markov discreta di ordine M, la serie (discreta)

degli stati è una serie di Markov semplice

Dim. Dalla definizione di stato della serie di Markov ne consegue che:

[ ] [ ] [ ]{ }[ ] [ ] [ ] [ ] [ ]{ }[ ] [ ] [ ]{ }

[ ] [ ] [ ] [ ]{ }[ ] [ ] [ ]{ }

1 2 2 1

Pr 1 ,..., 1

Pr 1 , 2 ,..., 2 ,..., 1

Pr 1 2 ,..., 1

Pr 2 ,..., 2 ,..., 1

Pr 1 2 ,..., 1

k k k M k

k k M k

k k k M

S k s S k s S s

X k x X k x X k M x X k x X x

X k x X k x X x

X k x X k M x X k x X x

X k x X k x X k M x

− − − −

− −

− − −

− − − −

= − = = =

= − = − = − = − = = =

= − = − = = ⋅

⋅ − = − = − = = =

= − = − = − − =

[ ] [ ]{ }1 1Pr 1 1k kX k x S k s− −

= − = − =

in quanto la probabilità condizionata di una v. a. rispetto a sé stessa e altre v. a.

è pari a 1 e la serie è di Markov di ordine M.

Analogamente si ha:

[ ] [ ]{ }1Pr 1

k kS k s S k s−= − = =

[ ] [ ] [ ] [ ] [ ]{ }1 2 2 1Pr 1 , 2 ,..., 2 ,..., 1

k k k M k k MX k x X k x X k M x X k x X k M x− − − − − −= − = − = − = − = − − = =

[ ] [ ] [ ]{ }[ ] [ ] [ ] [ ]{ }

Pr 1 2 ,..., 1

Pr 2 ,..., 2 ,..., 1

k k k M

k k M k k M

X k x X k x X k M x

X k x X k M x X k x X k M x

− − − −

− − − − −

= − = − = − − = ×

× − = − = − = − − = =

[ ] [ ] [ ]{ }1 2 1Pr 1 2 ,..., 1

k k k MX k x X k x X k M x− − − −= − = − = − − = =

[ ] [ ]{ }1 1Pr 1 1

k kX k x S k s− −= − = − =

• dall’eguaglianza tra la (20) e la (21) ne discende che la serie degli stati è di

Markov semplice. C. d. d.

• In virtù del precedente teorema per l’analisi del comportamento statistico

della serie degli stati sono immediatamente applicabili i risultati derivanti

in precedenza per le serie di Markov semplici.

• A tale scopo giova osservare che una serie di Markov stazionaria di ordine

M con il cosiddetto diagramma di stato.

• Il diagramma di stato è un grafo orientato i cui nodi rappresentano i

possibili stati della serie e gli archi le emissioni dei successivi termini della

serie che si verificano nelle transizioni da uno stato all’altro. Gli archi

sono etichettati con i valori delle probabilità condizionate di uno stato

rispetto al suo predecessore, ovvero del termine della serie emesso in

funzione dello stato di partenza. Ad esempio, con riferimento alla fig.1

S4= (0,1)

S1= (1,0)

S3= (1,1)

S0= (0,0) P(1/S0)

P(0/S0)

P(1/S1)

P(0/S1)

P(1/S4)

P(0/S4)

P(0/S3)

P(1/S3)

Si consideri una serie di Markov di ordine M=2 che possa assumere determinazioni su un alfabeto binario {0, 1}. In tal caso gli stati possibili saranno:

(0, 0)

(0, 1)

(1, 0)

(1, 1)

≡≡≡≡

• Nella costruzione del diagramma di stato, occorrerà considerare che, per

come è definito lo stato, solo alcune transizioni sono possibili. In

particolare, supponendo S[k]=s0, lo stato S[k+1] all’istante k+1 varrà

ancora s0 se la sorgente avrà emesso il simbolo 0 e varrà s2 se la sorgente

avrà emesso il simbolo 1. Si noti che la relazione (19) di normalizzazione

delle probabilità condizionate si traduce nella probabilità che la somma dei

pesi dei rami uscenti da un nodo sia pari a 1.

Facoltà di Ingegneria Appunti dalle lezioni del corso di · Facoltà di Ingegneria Appunti dalle...

Documents

Transcript of Facoltà di Ingegneria Appunti dalle lezioni del corso di · Facoltà di Ingegneria Appunti dalle...

APPUNTI DELLE LEZIONI DI FISICA PER …...1 APPUNTI DELLE LEZIONI DI FISICA PER INGEGNERIA TERMODINAMICA GAS, LIQUIDI E SOLIDI LUIGI PALUMBO Dipartimento di Scienze di Base e Applicate

Corso di Diploma Universitario in Ingegneria Elettronica ... · Questi appunti sono un breve riassunto delle lezioni di FOTONICA per il corso di Diploma Uni-versitario in Ingegneria

Quaderni di “Complementi di Scienza delle Costruzioni” · Scienza delle Costruzioni” - Ingegneria Meccanica - Appunti dalle lezioni a cura di Stella Brach ... La teoria delle

+ gli appunti delle lezioni

Appunti delle lezioni di Meccanica Razionale

Appunti Lezioni Di Diritto Della Navigazione

CORSO DI LAUREA IN INGEGNERIA CIVILE TECNICA … 2004-2005/Lezioni/Lezione Ale I... · • dinamica storica di sviluppo ... CLASSIFICAZIONE DELLE STRADE . APPUNTI DI TECNICA URBANISTICA

Appunti dalle lezioni di Calcolo Numerico

APPUNTI DELLE LEZIONI DI FISICA PER INGEGNERIA ......di Fisica Generale agli studenti del corso di laurea in Ingegneria Edile Architettura. Il corso tratta una parte della Fisica Classica,

APPUNTI DELLE LEZIONI ANNO ACCADEMICO 2008/2009INTRODUZIONE.

Appunti - Lezioni Di Diritto Dei Mercati Finanziari

Corso di Matematica Generale - Appunti dalle lezioni -

APPUNTI DELLE LEZIONI ANNO ACCADEMICO 2009/2010INTRODUZIONE.

APPUNTI DELLE LEZIONI DI FISICA PER … APPUNTI DELLE LEZIONI DI FISICA PER INGEGNERIA TERMODINAMICA GAS, LIQUIDI E SOLIDI LUIGI PALUMBO Dipartimento di Scienze di Base e Applicate

Appunti dalle Lezioni di MECCANICA RAZIONALE

APPUNTI DELLE LEZIONI - Centro di Ricerca …´a degli Studi di Pisa Facolt´a di Ingegneria Centro Interdipartimentale “Enrico Piaggio” APPUNTI DELLE LEZIONI Studio di sistemi

Appunti delle lezioni del corso di Aritmeticapeople.dm.unipi.it/.../Didattica/2016-17MDAL/dispenseAritmetica201… · Appunti delle lezioni del corso di Aritmetica Giovanni Gai 9

Appunti integrativi delle lezioni di Materiali Metallici ...dicma.ing.uniroma1.it/sites/default/files/didattica/2MUB.pdf · Appunti integrativi delle lezioni di ... Vengono impiegati

APPUNTI DELLE LEZIONI DI FISICA PER INGEGNERIA EDILE ... LEZIONI DI... · I.5.5 Accelerazione, derivata seconda della legge oraria.....21 I.5.6 Esempi di funzioni del tempo e loro

Facoltà di Ingegneria Appunti dalle lezioni del corso di · Provare, per mezzo della teoria dei processi ergodici, teoremi fondamentali sulla codificazione dell'informazione trasmessa