• Non ci sono risultati.

Codifica Huffmann

N/A
N/A
Protected

Academic year: 2021

Condividi "Codifica Huffmann"

Copied!
35
0
0

Testo completo

(1)

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

(2)

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.

(3)

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 i

x

A

=

=1 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”.

(4)

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.

(5)

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.

(6)

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.



(7)

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 i

n

p

n

E

n

1

n

7

n

i è la lunghezza della codeword che rappresenta il simbolo i-esimo

p

i è la probabilità di emissione del simbolo xi , e quindi è la

probabilità di avere una codeword di lunghezza

n

i

n

è la variabile aleatoria che rappresenta la lunghezza della

(8)

Codici 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

(9)

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.

(10)

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: . _

(11)

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.

(12)

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à.

(13)

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).

(14)

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

(15)

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 ni

(16)

Disuguaglianza 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 1

verificata

Kraft

di

dis

i ni

=

+

+

+

+

+

=

= −

)

.

(

06

.

1

32

1

32

1

8

1

8

1

4

1

2

1

2

6 1

verificata

non

Kraft

di

dis

i ni

=

+

+

+

+

+

=

= −

(17)

Disuguaglianza di Kraft

Disuguaglianza di Kraft –

– Esempio e discussione

Esempio 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.

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.

(18)

Disuguaglianza di Kraft

Disuguaglianza di Kraft –

– Esempio e discussione

Esempio 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 i i X

n

p

1

2

:

to

subject

1 1

= − = M i n i i i i

(19)

Primo 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

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

)

(

)

(

X

n

<

H

X

+

H

(20)

 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

(

)

=

(21)

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

(22)

Codici Completi

Codici Completi

 In casi particolari esiste una relazione tra

p

i e

n

i nei codici completi

 Dato che:

n

X

H

n

=

(

)

se

e

solo

se

:

log

1

=

= =

=





=

M i i i M i i i

n

p

n

p

p

X

H

1 1

1

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

2

1

M

i

p

ni i

=

2

,

=

1

,...,

(23)

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 ottenere

n =

H(X)

i

n

i n i

p

= 2

23

quindi, date le

p

i, 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 =

(24)

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

=

=

=

n

p

1

simbolo

simbolo

code word

code word

2 2

2

2

4

1

2

=

=

=

n

p

3 3

2

2

8

1

3

=

=

=

n

p

4 5 4

2

2

2

16

1

45

=

=

=

=

=

p

n n

p

n =

4

n

5

(25)

Esempio (continua)

Esempio (continua)

=

=





=

M i i i

p

p

X

H

1

1

log

)

(

(

)

8

15

4

4

16

1

3

8

1

2

4

1

1

2

1

=

+

+

+

+

M

1

1

1

1

(

)

15

25

=

=

=

M i i i

n

p

n

1

(

)

8

15

4

4

16

1

3

8

1

2

4

1

1

2

1

=

+

+

+

+

8

15

)

(

=

=

H

X

n

(26)

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:

(27)

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

i

2. Si raggruppano gli ultimi due simboli

x

M e

x

M-1 in un

“simbolo equivalente” di probabilità

(

p

M-1

+ p

M

)

. Ad ognuno

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

(28)

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÷4

Albero generato da una codifica di Huffman per una sorgente di sei simboli

(29)

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

(30)

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

(31)

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

4

x

1

x

3

x

2

x

4

 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

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)

(32)

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

(33)

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 i

n

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 =

= i

98

.

0

)

(

=

=

n

X

H

ε

r

=

1

ε

=

0

.

02

(34)

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 0

5

x 0.2 1 0 0.6

(35)

Esercizio

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.

Riferimenti

Documenti correlati

sua divisione in due cellule, tempo caratteristico della specie e delle condizioni colturali..

Si aggiunga alla classe ArrayStack (implementa l’interfaccia Stack usando un array) il metodo Stack clone() che restituisce un nuovo stack avente lo stesso contenuto dello stack...

Scuola secondaria di primo grado – classe prima Competizione 22 marzo 2011.. • Usate un solo foglio risposta per ogni esercizio; per ognuno deve essere riportata una sola

Funzioni membro operator* e inversa sintatticamente corrette ma non seguono le richieste del testo Dopo il ciclo di lettura dal file devi salvare il valore di i ad esempio in

tale indirizzo deve corrispondere a quello utilizzato dal segnalante per l’invio del modulo di adesione, ad eccezione dei casi in cui il segnalante stesso non sia tenuto al possesso

Se  la  Pa  si  è  scostata  dai  valori  normali  (valore  di  riferimento  VR)  i  meccanismi  di  compenso 

Tale studio deve essere presentato tramite un’opportuna modellazione via diagrammi UML (www.uml.org), che descriva l’architettura del simulatore e dei suoi componenti..

Definito (non--ambiguo) ambiguo), , ogni istruzione deve essere elementare e deve consentire un’interpretazione.. elementare e deve consentire un’interpretazione