Argomenti della Lezione
Argomenti della Lezione
1) Codici di sorgente
2) Codici univocamente decifrabili e codici a prefisso.
3) Disuguaglianza di Kraft
4) Primo Teorema di Shannon
1
4) Primo Teorema di Shannon
Codifica di sorgente
Codifica 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 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 sorgente
Codici 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
{ }
NX i ix
A
=
=1 3dell’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”.
Codici di sorgente
Codici 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 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 sorgente
Codici 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.
Codici di sorgente
Codici 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 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.
Codifica dell’alfabeto di sorgente
Codifica 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{ }
∑
= ∆=
=
X N i i in
p
n
E
n
1n
7n
i è la lunghezza della codeword che rappresenta il simbolo i-esimop
i è la probabilità di emissione del simbolo xi , e quindi è laprobabilità di avere una codeword di lunghezza
n
in
è la variabile aleatoria che rappresenta la lunghezza dellaCodici Univocamente Decifrabili
Codici 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
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 Decifrabili
Codici 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.
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 Decifrabili
Codici 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 Esempio di ambiguità nella decodifica: . _
Codici a Prefisso
Codici 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 WORD
in
in
11
SYMBOL CODE WORD
X1 0 X2 10 X3 110 X4 111 Primo digit Primo 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 Decifrabili
Univocamente 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.
⇒
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 classi
classi di
di codici
codici di
di sorgente
sorgente
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:
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 Sorgente
Esempi 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
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.
c 01 10 100
Disuguaglianza di Kraft
Disuguaglianza 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):
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
1
2
1≤
∑
= − M i niDisuguaglianza di Kraft
Disuguaglianza di Kraft -- Esempio
Esempio
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: Per C1 si ha: Per C2 si ha:
)
.
(
1
32
1
32
1
16
1
8
1
4
1
2
1
2
6 1verificata
Kraft
di
dis
i ni=
+
+
+
+
+
=
∑
= −)
.
(
06
.
1
32
1
32
1
8
1
8
1
4
1
2
1
2
6 1verificata
non
Kraft
di
dis
i ni=
+
+
+
+
+
=
∑
= −Disuguaglianza di Kraft
Disuguaglianza di Kraft –
– Esempio e discussione
Esempio e discussione
Controllando per ispezione i due codici precedenti si può vedere comenessuno 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.
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 discussione
Esempio e discussione
Volendo utilizzare codici a prefisso che sono una categoria di codiciottimizzabile 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 i i Xn
p
1
2
:
to
subject
1 1≤
∑
∑
= − = M i n i i i iPrimo Teorema di
Primo Teorema di Shannon
Shannon
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
)
(
)
(
X
≤
n
<
H
X
+
H
n
19Tale 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
)
(
)
(
X
≤
n
<
H
X
+
H
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 di
di un
un codice
codice di
di sorgente
sorgente
( )
1
_
+
≥
H
X
n
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:
n
X
H
(
)
=
Codici Completi
Codici 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.
21
neanche sull’associazione tra codeword e simboli di sorgente.
Di conseguenza un codice completo non minimizza
Codici Completi
Codici Completi
In casi particolari esiste una relazione tra
p
i en
i nei codici completiDato che:
n
X
H
n
=
(
)
se
e
solo
se
:
log
1
=
∑
∑
= ==
=
M i i i M i i in
p
n
p
p
X
H
1 11
log
)
(
e
Si ha: ovvero:e in questo caso la disuguaglianza di Kraft è verificata con il segno di uguaglianza (codice completo) ed inoltre la sua efficienza è
i i
n
p
X
H
n
=
=
(
)
se
e
solo
se
:
log
21
M
i
p
ni i=
2
,
=
1
,...,
−Codici Completi
Codici 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
p
i, non è sempre possibile otteneren =
H(X)
i
n
i n ip
= 2
− 23quindi, date le
p
i, non è sempre possibile ottenereDato M, esiste sempre un codice completo con M codeword,
ma tale codice non ha necessariamente
H(X)
n =
H(X)
n =
Esempio
Esempio
)
(x
H
n ≥
In tabella viene riportato un codice che soddisfa la: con il segno di uguaglianza, essendo:
1 1
2
2
2
1
− 1 −=
=
=
np
1
−simbolo
simbolo
code word
code word
2 2
2
2
4
1
− 2 −=
=
=
np
3 32
2
8
1
− 3 −=
=
=
np
4 5 42
2
2
16
1
− 4 − 5 −=
=
=
=
=
p
n np
n =
4n
5Esempio (continua)
Esempio (continua)
∑
==
=
M i i ip
p
X
H
11
log
)
(
(
)
8
15
4
4
16
1
3
8
1
2
4
1
1
2
1
=
+
+
⋅
+
⋅
+
⋅
∑
M1
1
1
1
(
)
15
25∑
==
=
M i i in
p
n
1(
)
8
15
4
4
16
1
3
8
1
2
4
1
1
2
1
=
+
+
⋅
+
⋅
+
⋅
8
15
)
(
=
=
H
X
n
Codici di
Codici di Huffman
Huffman
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
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:
Costruzione di codici ottimali di
Costruzione di codici ottimali di Huffman
Huffman
1. Gli M simboli dell’alfabeto di sorgente vengono ordinati in
accordo a valori non crescenti delle loro probabilità
p
i2. Si raggruppano gli ultimi due simboli
x
M ex
M-1 in un“simbolo equivalente” di probabilità
(
p
M-1+ p
M)
. Ad ognuno27
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
Costruzione di codici ottimali di
Costruzione di codici ottimali di Huffman
Huffman -- Esempio
Esempio
p.e.
p.e.
p.e.
p.e.
Albero realizzato applicando i passi 1÷4Albero generato da una codifica di Huffman per una sorgente di sei simboli
Costruzione di codici ottimali di
Costruzione di codici ottimali di Huffman
Huffman -- Esempio
Esempio
Per l’esempio precedente si ottiene:
simbolo
simbolo
code word
code word
29 2.1 digit/simbolo 2.086 bit/simbolo
=
⋅
+
⋅
+
⋅
+
+
⋅
+
⋅
+
⋅
=
4
05
0
4
05
0
3
10
0
3
15
0
3
15
0
1
5
0
.
.
.
.
.
.
n
=
⋅
+
⋅
+
⋅
+
+
⋅
+
⋅
+
⋅
=
20
log
05
0
20
log
05
0
10
log
1
0
15
.
0
1
log
15
0
15
.
0
1
log
15
0
2
log
5
0
)
(
.
.
.
.
.
.
X
H
Costruzione di codici ottimali di
Costruzione di codici ottimali di Huffman
Huffman -- Esempio
Esempio
Per decodificare la sequenza ricevuta:
1100101100110
1100101100110
si usa l’albero generato dalla procedura di Huffman.Per l’esempio precedente si ottiene:
Muovendosi dalla radice dell’albero, si seguono i rami ad ogni nodo
intermedio in accordo ai digit binari
della sequenza finché si raggiunge un
Costruzione di codici ottimali di
Costruzione di codici ottimali di Huffman
Huffman -- Esempio
Esempio
Nel caso in esame si ha:
110| 0 |101|100|110
110| 0 |101|100|110
x
4x
1x
3x
2x
4Assumendo 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
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)
Esercizio
Esercizio
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:
x4 x1 x3 x2 x 0.3 0.3 0.2 0.1 0.1 0.2 0.6 0.4 1 0 1 0 1 0 1 0
Esercizio
Esercizio –
– cont
cont..
olo
digit/simb
2
.
2
3
1
.
0
2
3
.
0
2
2
.
0
3
1
.
0
2
3
.
0
5 1=
=
⋅
+
⋅
+
⋅
+
⋅
+
⋅
=
=
∑
= i i in
p
n
C x1 (p=0.3) 01 x2 (p=0.1) 110 x3 (p=0.2) 10 x4 (p=0.3) 00 ( ) log 0.52 0.52 0.46 0.33 0.33 5 = + + + + = − =∑
= i i p p X H 33 x4 (p=0.3) 00 x5 (p=0.1) 111 2.16 bit/simbolo 1 =∑
= i98
.
0
)
(
=
=
n
X
H
ε
r
=
1
−
ε
=
0
.
02
Esercizio
Esercizio
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:
,
1
,
2
,...,
5
5
1
=
=
i
p
i x1 x2 x3 x4 0.2 0.2 0.2 0.2 0.4 0.4 1 0 1 0 1 05
x 0.2 1 0 0.6Esercizio
Esercizio –
– cont
cont..
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 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.