Post on 16-Feb-2019
Argomenti della LezioneArgomenti della Lezione
1) Codici di sorgente
2) Codici univocamente decifrabili e codici a prefisso.
3) Disuguaglianza di Kraft
4) Primo Teorema di Shannon
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
1
4) Primo Teorema di Shannon
5) Codifica di Huffman
Codifica di sorgenteCodifica di sorgente
� Il processo di codifica di sorgente ha lo scopo di aumentare
l’efficienza nell’utilizzo della risorsa “tempo” di un canale di
comunicazione.
� La codifica di sorgente regola la costruzione dei codici di sorgente
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
2
� La codifica di sorgente regola la costruzione dei codici di sorgente
e la legge di associazione di un codice di sorgente con i simboli
dell’alfabeto di sorgente.
Codici di sorgenteCodici di sorgente
� Supponiamo che la sorgente sia discreta e senza memoria e che
emetta simboli appartenenti all’alfabeto . Sorgenti non
discrete come ad esempio un microfono possono essere rese
discrete utilizzando l’operazione di conversione A/D.
� Prima di essere inviato al codificatore di canale, ogni simbolo
dell’alfabeto di sorgente deve essere rappresentato da una stringa
{ } XN
iixA1=
=
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
3
dell’alfabeto di sorgente deve essere rappresentato da una stringa
finita di simboli appartenenti all’alfabeto del codice, detta parola di
codice (codeword).
� Un codice è un insieme di parole di codice.
� Verrà considerato soltanto il caso in cui l’alfabeto del codice sia un
alfabeto binario costituito dai due binary digit “0” e “1”.
� Es. C={001, 100, 101, 110, 111}.
Codici di sorgenteCodici di sorgente
� In generale le codeword di uno stesso codice hanno una lunghezza
variabile.
� La codifica di sorgente mette in corrispondenza i simboli di una
sorgente con le codeword di un codice di sorgente sulla base della
probabilità di emissione dei simboli di sorgente.
� La codifica di sorgente che andremo a studiare è di tipo senza
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
4
� La codifica di sorgente che andremo a studiare è di tipo senza
perdite. Infatti se si assume una trasmissione senza errori, il
messaggio inviato dalla sorgente e successivamente codificato
viene riprodotto esattamente dal decodificatore di sorgente e
consegnato al destinatario.
Codici di sorgenteCodici di sorgente
� Il codice ASCII (esteso) è un codice di sorgente le cui codeword sono
costituite da stringhe di 8 bit. Con il codice ASCII è possibile rappresentare
tutte le lettere (maiuscole e minuscole) dell’alfabeto inglese, i numeri da 0 a
9, alcuni simboli speciali ed alcuni simboli di controllo.
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
5
Codici di sorgenteCodici di sorgente
� Comunicazione efficiente: la trasmissione di ogni simbolo di
sorgente avviene in poco tempo (e quindi con pochi bit – binary
digit).
� Per avere mediamente un comportamento come quello richiesto, un
codice di sorgente assegna le codeword di lunghezza minore ai
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
6
codice di sorgente assegna le codeword di lunghezza minore ai
simboli di sorgente che hanno una più alta probabilità di emissione,
mentre assegna le codeword di lunghezza maggiore ai simboli di
sorgente che hanno una più bassa probabilità di emissione.
�� E’ necessario quindi minimizzare la lunghezza media della E’ necessario quindi minimizzare la lunghezza media della
codeword.codeword.
Codifica dell’alfabeto di sorgenteCodifica dell’alfabeto di sorgente
L’obiettivo è minimizzare la lunghezza media delle codeword calcolabile come:
dove:
n è la lunghezza della codeword che rappresenta il simbolo i-esimo
{ } ∑=
∆
==XN
i
ii npnEn1
n
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
7
ni è la lunghezza della codeword che rappresenta il simbolo i-esimo
pi è la probabilità di emissione del simbolo xi , e quindi è la
probabilità di avere una codeword di lunghezza ni
n è la variabile aleatoria che rappresenta la lunghezza della
codeword (cioè che assume il valore ni con probabilità pi)
Codici Univocamente DecifrabiliCodici Univocamente Decifrabili
C’è un importante vincolo nella minimizzazione della lunghezza
media della codeword . Il codice deve essere univocamente
decifrabile, cioè ogni sequenza finita di bit emessa dalla sorgente
deve corrispondere ad uno ed un solo messaggio senza ambiguità.
n
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
8
Esempio:
Dato il codice riportato qui a destra, la
sequenza 010010 corrisponde ad uno qualsiasi
dei cinque messaggi:
Il codice dell’esempio è ambiguo, cioè non decifrabile in modo univoco.
x1x3x2x1 x1x3x1x3 x1x4x3 x2x1x1x3 x2x1x2x1
Simbolo Codeword
x1 0
x2 01
x3 10
x4 100
Codici Univocamente DecifrabiliCodici Univocamente Decifrabili� Un codice è detto non singolare se ha tutte le codeword diverse.
� Chiaramente un codice univocamente decifrabile deve essere non singolare.
� Viene definita n-esima estensione del codice C, un codice C' costituito
dall'insieme di tutte le possibili concatenazioni di n codeword del codice C.
� Un codice è univocamente decifrabile se la sua n-esima estensione è non
singolare, per ogni n.
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
9
� Affinchè un codice sia univocamente decifrabile è sufficiente che esista un
algoritmo che porti a suddividere in blocchi corrispondenti a codeword ogni
sequenza finita all’uscita del codificatore di sorgente. Tale suddivisione deve
avvenire senza ambiguità.
� All’uscita del codificatore di sorgente non si avranno necessariamente tutte
le possibili sequenze che possono essere costruite con i bit “0” e “1”, ma si
avranno tutte le possibili sequenze di codeword del codice.
Codici Univocamente DecifrabiliCodici Univocamente Decifrabili
� Il codice Morse è un codice di sorgente a lunghezza variabile che permette
di codificare l’alfabeto inglese. L’alfabeto di codice è costituito da quattro
simboli: punto, linea, spazio tra lettere (attesa equivalente alla durata di tre
punti), spazio tra parole (attesa equivalente alla durata di cinque punti).
� Con i due soli simboli “punto” e “linea” il codice non sarebbe
univocamente decodificabile.
Esempio di ambiguità nella decodifica: . _A
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
10
Esempio di ambiguità nella decodifica: . _
ET
Codici a PrefissoCodici a Prefisso
� Una condizione che assicura l’univoca decifrabilità è che nessuna parola
di codice sia prefisso di una parola di codice più lunga (Regola del
prefisso – PREFIX CODE). Un codice che soddisfa questa condizione
viene detto codice a prefisso.
� Rappresentazione tramite albero binario dei codici a prefisso:
SYMBOL CODE WORDinin
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
11
SYMBOL CODE WORD
X1 0
X2 10
X3 110
X4 111Primo digitPrimo digit
� Poiché le codeword corrispondono alle sequenze di bit che si incontrano
nei percorsi che portano ai nodi foglia dell’albero, e ad ogni arco uscente
da uno stesso nodo viene assegnato un diverso digit, nessuna codeword
può essere il prefisso di un’altra codeword più lunga.
Relazione tra Codici a Prefisso e Codici Relazione tra Codici a Prefisso e Codici Univocamente DecifrabiliUnivocamente Decifrabili
� Codice a prefisso Codice univocamente decifrabile.
� La condizione che il codice sia a prefisso è soltanto una
condizione sufficiente affinché il codice sia univocamente
decifrabile, ma non è una condizione necessaria.
⇒
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
12
decifrabile, ma non è una condizione necessaria.
� I codici a prefisso sono la categoria di codici più studiata perché
permettono di minimizzare la lunghezza media delle codeword
per qualsiasi funzione di massa di probabilità.
Ulteriori Ulteriori classiclassi di di codicicodici di di sorgentesorgente
� Esistono altre classi di codici che non sono a prefisso, ma sono
univocamente decifrabili e le più note sono i codici a lunghezza
fissa ed i codici a virgola.
� I codici a lunghezza fissa sono costituiti da un insieme di
codeword di uguale lunghezza L. Un codice a lunghezza fissa per
essere univocamente decifrabile deve avere una lunghezza pari a:
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
13
essere univocamente decifrabile deve avere una lunghezza pari a:
in cui è la cardinalità dell’alfabeto di sorgente e indica il più
grande intero non maggiore di .
� I codici a virgola sono un particolare tipo di codici in cui l'inizio (o
la fine) di una codeword è segnalata da un simbolo non utilizzato
altrimenti (detto virgola).
Esempi di Codici di SorgenteEsempi di Codici di Sorgente
Si consideri una sorgente avente 4 simboli a,b,c,d ed i tre codici C1,
C2 e C3 la cui corrispondenza tra codeword e simboli di sorgente è mostrata in Tabella.
C1 C2 C3
a 0 00 1
b 1 01 10
c 01 10 100
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
14
C1 non è univocamente decifrabile poiché alla emissione dal codificatore di
sorgente della sequenza 01 vi è una incertezza sulla decodifica (ab oppure c).
C2 è univ. decifrabile poiché è un codice a lunghezza fissa con lunghezza pari a 2 e
con codeword tutte diverse. I codici a lunghezza fissa rispettano anche rispettano
implicitamente la regola del prefisso.
C3 è univ. decifrabile poiché “1” indica l’emissione di un nuovo simbolo. Tale classe
di codici viene indicata come codici a virgola.
c 01 10 100
d 11 11 1000
Disuguaglianza di KraftDisuguaglianza di Kraft
Una condizione necessaria e sufficiente per un dato codice affinché
sia soddisfatta la condizione sul prefisso è data dal seguente
teorema.
Teorema (DISUGUAGLIANZA DI KRAFT):
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
15
Un codice binario che soddisfi la regola del prefisso con codeword di
lunghezza n1 , n2 ,…, nM esiste se e solo se:
La dimostrazione viene omessa
121
≤∑=
−M
i
ni
Disuguaglianza di Kraft Disuguaglianza di Kraft -- EsempioEsempio
Verificare la disuguaglianza di Kraft per i seguenti codici:
C1 = {0, 01, 011, 0111, 01111, 11111}
C2 = {0, 01, 011, 001, 01111, 11111}
Soluzione:Per C1 si ha:
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
16
Per C1 si ha:
Per C2 si ha:
).(132
1
32
1
16
1
8
1
4
1
2
12
6
1
verificataKraftdidisi
ni =+++++=∑=
−
).(06.132
1
32
1
8
1
8
1
4
1
2
12
6
1
verificatanonKraftdidisi
ni =+++++=∑=
−
Disuguaglianza di Kraft Disuguaglianza di Kraft –– Esempio e discussioneEsempio e discussione
� Controllando per ispezione i due codici precedenti si può vedere come
nessuno dei due codici soddisfa la regola del prefisso.
� Da questo esempio si può vedere che se la disuguaglianza di Kraft è verificata
per un certo codice C, ciò non assicura che il codice C sia a prefisso.
� Infatti la disuguaglianza di Kraft, nel caso in cui sia verificata per un certo
codice C, garantisce soltanto l’esistenza di un codice a prefisso con le stesse
lunghezze delle codeword di C.
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
17
lunghezze delle codeword di C.
� La disuguaglianza di Kraft non può garantire che un codice sia a prefisso
perché nella disuguaglianza vengono prese in considerazione soltanto le
lunghezze delle codeword, ma non la disposizione dei binary digit di ogni
codeword.
� Se la disuguaglianza di Kraft è verificata per un codice C, è possibile ottenere
un codice C’ a prefisso permutando i simboli binari delle codeword di C e
mantenendo inalterata la loro lunghezza. Se la disuguaglianza di Kraft non è
verificata, tale procedimento non può portare ad un codice a prefisso.
Disuguaglianza di Kraft Disuguaglianza di Kraft –– Esempio e discussioneEsempio e discussione
� Volendo utilizzare codici a prefisso che sono una categoria di codici
ottimizzabile per qualsiasi tipo di massa di probabilità dei simboli di sorgente
e utilizzando il teorema di Kraft, si può impostare il problema di ottimizzazione
vincolata nel seguente modo:
min ∑=
N
ii
X
np
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
18
12:tosubject1
1
≤∑
∑
=
−
=
M
i
n
i
ii
i
Primo Teorema di Primo Teorema di ShannonShannon
� Teorema: si può trovare un codice di sorgente binario di lunghezza
media che soddisfi la regola del prefisso, per ogni alfabeto di
sorgente di entropia H(X), per cui risulti soddisfatta la seguente:
1)()( +<≤ XHnXH
n
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
19
� Tale teorema è noto come “primo Teorema di Shannon” o come
“Teorema Fondamentale della Codifica di Sorgente”.
� Questo Teorema rappresenta il primo limite fondamentale nella
teoria dell’informazione per la codifica di corgente senza perdite.
1)()( +<≤ XHnXH
� Un codice che ha una lunghezza media non è un buon
codice, ossia esiste un codice a prefisso con una lunghezza media inferiore.
� Un codice di sorgente è tanto migliore quanto più è piccola la sua
lunghezza media. Dal primo Teorema di Shannon si può vedere che esiste
un limite inferiore alla lunghezza media del codice che è sempre maggiore o
al più uguale all'entropia di sorgente.
� Ricordando che in genere l’efficienza è una metrica di prestazioni che al più
Efficienza Efficienza didi un un codicecodice di di sorgentesorgente
( ) 1_
+≥ XHn
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
20
� Ricordando che in genere l’efficienza è una metrica di prestazioni che al più
vale 1, possiamo definire l’efficienza e la ridondanza di un codice di
sorgente come segue.
� Efficienza del codice di sorgente:
� Ridondanza del codice di sorgente:
n
XH )(=ε
εεεε−−−−1
Codici CompletiCodici Completi
� Si definisce codice completo un codice a prefisso che soddisfa
la disuguaglianza di Kraft con il segno di uguaglianza.
� Per un codice completo non si fa però nessuna ipotesi sulle
probabilità di emissione dei simboli dell'alfabeto di sorgente e
neanche sull’associazione tra codeword e simboli di sorgente.
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
21
neanche sull’associazione tra codeword e simboli di sorgente.
� Di conseguenza un codice completo non minimizza
necessariamente la lunghezza media delle codeword.
Codici CompletiCodici Completi
� In casi particolari esiste una relazione tra pi e ni nei codici completi
� Dato che:
nXHn =
=1
log:sesoloese)(
∑∑==
=
=
M
i
ii
M
i i
i npnp
pXH11
1log)( e
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
22
Si ha:
ovvero:
e in questo caso la disuguaglianza di Kraft è verificata con il segno
di uguaglianza (codice completo) ed inoltre la sua efficienza è
unitaria.
i
i
np
XHn =
=
1log:sesoloese)( 2
Mip in
i ,...,1,2 ==−
Codici CompletiCodici Completi
� Un codice di sorgente ad efficienza unitaria è un codice
completo, ma non è vero il viceversa.
� In generale la non è soddisfatta con intero e
quindi, date le pi , non è sempre possibile ottenere H(X)n =
inin
ip−
= 2
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
23
quindi, date le pi , non è sempre possibile ottenere
� Dato M, esiste sempre un codice completo con M codeword,
ma tale codice non ha necessariamente
H(X)n =
H(X)n =
EsempioEsempio
)(xHn ≥In tabella viene riportato un codice che soddisfa la:
con il segno di uguaglianza, essendo:
1
1 222
11 −−
===n
p
1 −
simbolosimbolo code wordcode word
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
24
2
2 224
12 −−
===n
p
3
3 228
13 −−
===n
p
4
54 22216
154 −−−
=====nn
pp54 nn =
Esempio (continua)Esempio (continua)
∑=
=
=
M
i i
ip
pXH1
1log)( ( )
8
1544
16
13
8
12
4
11
2
1=++⋅+⋅+⋅
∑M
( )151111
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
25
∑=
==M
i
iinpn1
( )8
1544
16
13
8
12
4
11
2
1=++⋅+⋅+⋅
8
15)( == XHn
Codici di Codici di HuffmanHuffman
� I codici di Huffman sono dei codici di sorgente a prefisso che
vengono costruiti mediante l’algoritmo di Huffman che fa uso di
un albero binario.
� Sono codici ottimi, cioè tra tutti i codici a prefisso sono quelli che
minimizzano la lunghezza media delle codeword per un dato
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
26
alfabeto di sorgente e massa di probabilità.
� Sono codici completi, non necessariamente ad efficienza unitaria.
� Sono in generale codici a lunghezza variabile. Nel caso in cui NX è
una potenza di 2 e i simboli di sorgente sono equiprobabili allora il
codice di Huffman coincide con un codice a lunghezza fissa con:
XNL 2log=
Costruzione di codici ottimali di Costruzione di codici ottimali di HuffmanHuffman
1. Gli M simboli dell’alfabeto di sorgente vengono ordinati in
accordo a valori non crescenti delle loro probabilità pi
2. Si raggruppano gli ultimi due simboli xM e xM-1 in un
“simbolo equivalente” di probabilità (pM-1+ pM). Ad ognuno
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
27
dei due rami corrispondenti ai due simboli uniti viene
associato un simbolo "0" ed un simbolo "1".
3. Si ripetono i passi 1 e 2 finché non rimane un solo simbolo
4. Per ogni simbolo, la parola di codice corrispondente si trova
esplorando a ritroso l’albero generato con i passi 1 ÷÷÷÷ 3, dalla
radice verso quel simbolo
Costruzione di codici ottimali di Costruzione di codici ottimali di HuffmanHuffman -- EsempioEsempio
p.e.p.e.
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
28
p.e.p.e.
Albero realizzato applicando i passi
1÷4
Albero generato da una codifica di Huffman
per una sorgente di sei simboli
Costruzione di codici ottimali di Costruzione di codici ottimali di HuffmanHuffman -- EsempioEsempio
Per l’esempio precedente si
ottiene:
simbolosimbolo code wordcode word
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
29
2.1 digit/simbolo
2.086 bit/simbolo
=⋅+⋅+⋅+
+⋅+⋅+⋅=
405040503100
31503150150
...
...n
=⋅+⋅+⋅+
+⋅+⋅+⋅=
20log05020log05010log10
15.0
1log150
15.0
1log1502log50)(
...
...XH
Costruzione di codici ottimali di Costruzione di codici ottimali di HuffmanHuffman -- EsempioEsempio
Per decodificare la sequenza ricevuta: 11001011001101100101100110
si usa l’albero generato dalla procedura di Huffman.
Per l’esempio precedente si ottiene:
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
30
Muovendosi dalla radice dell’albero,
si seguono i rami ad ogni nodo
intermedio in accordo ai digit binari
della sequenza finché si raggiunge un
nodo terminale (cioè un simbolo).
Poi si ricomincia la procedura
Costruzione di codici ottimali di Costruzione di codici ottimali di HuffmanHuffman -- EsempioEsempio
Nel caso in esame si ha: 110| 0 |101|100|110110| 0 |101|100|110x4 x1 x3 x2 x4
� Assumendo la presenza di un errore introdotto dal canale in prima
posizione, la procedura di decodifica genera catastrofici effetti di
propagazione in questi codici a lunghezza variabile
� Tuttavia l’obiettivo della codifica di sorgente è la riduzione della
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
31
� Tuttavia l’obiettivo della codifica di sorgente è la riduzione della
ridondanza dell’alfabeto di sorgente (compressione)
E NON
la protezione dagli errori del canale (che è l’obiettivo della codifica
di canale)
EsercizioEsercizio
Generare l’albero di codifica di Huffman per un alfabeto di sorgente di cardinalità M=5 e probabilità pari a: p1=p4=0.3; p2=0.1; p3=0.2; p5=0.1. Calcolare la lunghezza media delle codeword, l’efficienza del codice e la sua ridondanza.
Soluzione:Disponendo i simboli in ordine decrescente di probabilità si costruisce l’albero:
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
32
x4
x1
x3
x2
x5
0.3
0.3
0.2
0.1
0.10.2
0.6
0.4
1
01
0
1
0
1
0
Esercizio Esercizio –– contcont..
olodigit/simb2.2
31.023.022.031.023.05
1
=
=⋅+⋅+⋅+⋅+⋅==∑=i
iinpn
C
x1 (p=0.3) 01
x2 (p=0.1) 110
x3 (p=0.2) 10
x4 (p=0.3) 00 33.033.046.052.052.0log)(5
=++++=−= ∑=
ii ppXH
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
33
x4 (p=0.3) 00
x5 (p=0.1) 111 obit/simbol16.2
1
=
∑=i
98.0)(
==n
XHε 02.01 =−= εr
EsercizioEsercizio
Generare un codice di Huffman ed un altro codice a lunghezza costante per un alfabeto di sorgente di cardinalità M=5 e densità di probabilità uniforme.
Soluzione:Ne risulta che: 5,...,2,1,
5
1== ipi
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
34
x1
x2
x3
x4
0.2
0.2
0.2
0.2
0.4
0.4
1
01
0
1
0
5
x5 0.2
1
00.6
Esercizio Esercizio –– contcont..
C1 (Huffman) C2 (lunghezza fissa)
x1 (p=0.2) 00 000
x2 (p=0.2) 010 001
x3 (p=0.2) 011 010
x4 (p=0.2) 10 011
x5 (p=0.2) 11 100
Mauro De Sanctis – corso di Informazione e Codifica – Università di Roma Tor Vergata
35
x5 (p=0.2) 11 100
Anche se i simboli sono equiprobabili, il codice di Huffman ha codeword con
lunghezze diverse. Il codice di Huffman equivale al codice a lunghezza fissa nel
caso in cui il numero di simboli sia una potenza di 2 ed i simboli siano equiprobabili.
Infatti in questo caso un codice a lunghezza fissa è un codice ottimo.
N.B.: Il codice di Huffman associato ad un alfabeto di sorgente non è unico.