Lezione 13 Codifica e crittografia

X

. Da questo esempio si capisce che se si scelgono le parole codice

( ) (

L C ≥ H X)

di lunghezza diversa allora si può avere la compressione, mentre se scelgo

lunghezza del codice sempre pari a 2 non si ha compressione. Si deve

( )

C ' x

avere un codice che sia univocamente decifrabile, cioè da ogni sequenza di

parole codice si può risalire ad una sola sequenza di simboli di sorgente. Ad

esempio col codice :

( )

C x

010111110010111

Trovo subito uno 0 che è la prima parola codice; poi c’è 1 e non posso dire

subito qual è la parola codice, noto che subito dopo c’è 0 quindi la parola

codice è 2; successivamente ci sono tre 1 consecutivi quindi la parola codice è

la 4, ecc.

Mentre col codice :

( )

C ' ' x

100

Si può interpretare come il simbolo 3, oppure come combinazione dei simboli

2 e 1. Dunque, il codice non è univocamente decifrabile.

C ' '( x)

Codice non singolare

Def. significa che ogni elemento di ha una

∈

x X

differente parola codice , che è una stringa *

( )

C x D

⟹ (x )≠C (x )

x ≠ x C

i j i j

La non singolarità del codice consente una descrizione non ambigua del

singolo ma non necessariamente di una sequenza di simboli di .

∈

x X x

Indichiamo con * l’estensione del codice e corrisponde alla

C C

mappatura di stringhe di lunghezza finita di *(simboli dell’alfabeto

X

sorgente) in stringhe di lunghezza finita di * (alfabeto codice) ottenute

D

mediante la concatenazione delle parole codice dei singoli simboli. (La

codifica di una stringa di simboli di sorgente avviene concatenando le parole

codice dei singoli simboli)

( ) ( ) ( )

=C )

C x ,… , x x C x … C( x

1 n 1 2 n

Nasce il problema della punteggiatura, bisogna capire quando finisce una

parola codice e ne inizia un’altra. Inserire un segno di punteggiatura tra le

parole codice non è efficiente ai fini della compressione, perché allungo il

messaggio da codificare. Si nota che il codice dell’esempio ha una

( )

C x

sorta di punteggiatura automatica che deriva da come sono state costruite le

parole codice per i diversi simboli.

La separazione tra le parole codice di simboli diversi deve “avvenire

⟹

automaticamente”.

Codice univocamente decifrabile

Def. se l’estensione del codice * è non

C

singolare, ogni stringa di * può essere generata da una sola stringa di

D

*.

X

Prefisso di una parola codice *

( )=d ∈

x → C x d … d d … d D

( )

1 2 p p+1 l x

prende il nome di prefisso, corrisponde cioè ai primi p simboli.

d d … d

1 2 p

codice si dice a prefisso o istantaneo

Un quando nessuna parola codice è

prefisso di un’altra parola codice. In un codice istantaneo (a prefisso) ogni

parola codice può essere decodificata senza attendere le parole codice

successive.

Il primo insieme corrisponde a tutti i codici, quello successivo corrisponde ai

codici singolari, un codice però non deve essere solo singolare ma anche

decifrabile; nell’ambito dei codici univocamente decifrabili c’è la categoria dei

codici istantanei o a prefisso (caso particolare dei codici univocamente

decifrabili)

Prendendo in considerazione il codice univocamente decifrabile ma non

istantaneo dell’esempio, la seguente stringa:

110000000011

Dal primo 1 non riusciamo a capire qual è la parola codice, stessa cosa

succede se osservo anche l’1 successivo, neanche per 110 posso dire qual è la

parola codice perché si deve vedere se i numeri 0 successivi siano pari o

dispari, se è pari allora si ha 11 seguito da un certo numero di coppie 00;

mentre se sono dispari allora i codici saranno 110 seguito da un certo numero

di coppie 00. Il codice è quindi univocamente decifrabile in quanto ad ogni

stringa corrisponde un’unica stringa di simboli di sorgente, ma la decodifica

non è istantanea, cioè devo individuare prima le parole codice successive per

poter capire la stringa di simboli di sorgente ed effettuare la decodifica.

Per un codice non istantaneo devo utilizzare un buffer per memorizzare le

parole codice prima di poter effettuare la decodifica, devo prevedere un

lunghezza massima e quindi può succedere che il buffer vada in overflow.

Per questo motivo si utilizzano solo i codici istantanei, perché dal punto di

vista implementativo la decodifica del codice istantaneo è più semplice dato

che avviene istantaneamente.

4.2. P ( )

ROBLEMA DELLA COMPRESSIONE O CODIFICA DI SORGENTE

Per una data sorgente trovare un codice istantaneo che minimizzi la

lunghezza media delle parole codice.

∑ ( ) ( )

L= p x l x

X

x∈ X

Per effettuare la minimizzazione di una funzione reale di variabile reale si

deve effettuare la ricerca in un intervallo che è il più ampio possibile in

maniera tale da ottenere la più piccola possibile. Tale discorso vale

( )

f x

anche in ambito più generale se la funzione che sto considerando è una

lunghezza media delle parole codice e la variabile indipendente è il codice

utilizzato per conseguire la lunghezza media.

4.3. D K

ISUGUAGLIANZA DI RAFT

Per ogni codice a prefisso (istantaneo) su un alfabeto codice con

D

cardinalità , le lunghezze dove delle parole

| |

l , … , l =

D=¿ D∨¿ M X

1 M

codice devono soddisfare la disuguaglianza:

( ) ( )

C x , … ,C x

1 M

M

∑ −l

D ≤ 1

i

i=1

Viceversa, dato un insieme di lunghezze che soddisfa la

l , … , l

1 M

disuguaglianza allora esiste un codice istantaneo le cui parole codice hanno

queste lunghezze.

Dimostrazione

Per dimostrare la disuguaglianza di Kraft si considera l’albero D-ario (da

ogni nodo partono D rami):

Albero binario D=2