INFORMATICA

MATTEO CRISTANI

INDICE CICLO DELLE LEZIONI

LEZ. 1INTRODUZIONE AL CORSO

LEZ. 2I CALCOLATORI ELETTRONICI

LEZ. 3ELEMENTI DI TEORIA DELL’INFORMAZIONE

LEZ. 4MISURE DELLA INFORMAZIONE

LEZ. 5CALCOLO BINARIO: CONVERSIONI DI BASE

LEZ. 6CALCOLO BINARIO: OPERAZIONI IN BASE 2

LEZ. 7ESERCITAZIONE DI CALCOLO BINARIO

LEZ. 8ESERCITAZIONE DI CALCOLO BINARIO

LEZ. 9PORTE LOGICHE

LEZ. 10PROGETTO DI CIRCUITI DIGITALI

LEZ. 11INTRODUZIONE AGLI ALGORITMI

LEZ. 12PRODUTTIVITA’ INDIVIDUALE

LEZ. 13IL WEB

LEZ. 14RICERCA DI DOCUMENTI

LEZ. 15USO DEI MOTORI DI RICERCA

LEZ. 16SICUREZZA INFORMATICA

LEZ. 17

ELEMENTI DI CRITTOGRAFIA

LEZ. 18ESERCITAZIONE DI CRITTOGRAFIA

LEZ. 19ESERCITAZIONE GENERALE

LEZ. 20SOMMARIO DEL CORSO

AGENDA ESERCIZI BASE SULLE MISURE DELLA

INFORMAZIONE ESERCIZI SUI CODICI ESERCIZI AVANZATI SULLE MISURE DELLA

INFORMAZIONE

ESERCIZI BASE DI TEORIA DELL’INFORMAZIONE

1. Dato un sistema di Shannon con un alfabeto di canale di 23 simboli equiprobabili, calcolare la quantità di informazione portata da tre messaggi.

2. Dato un sistema di Shannon con un alfabeto di canale con 16 simboli calcolare la ridondanza di una codifica ternaria.

3. Dato un sistema di Shannon in cui la quantità di informazione portata da due messaggi è pari a circa 7 bit, sapendo che la distribuzione di probabilità dei messaggi è uniforme trovare l’ampiezza dell’alfabeto di canale.

SOLUZIONE ESERCIZIO 1 L’informazione portata da un singolo simbolo

è

L’informazione portata da tre messaggi è quindi

52,4)23(log2 I

57,13)23(log3 2 I

SOLUZIONE ESERCIZIO 2 Le codifiche ternarie portano i simboli

dell’alfabeto su blocchi di simboli 0, 1, 2. Con tre simboli, il numero minimo di codici necessari per 16 elementi dell’alfabeto di canale è 2, perché

2,1)16(log3

SOLUZIONE ESERCIZIO 2 Quindi, ad esempio, supponendo che i glifi dei

sedici elementi dell’alfabeto di canale siano le prime sedici lettere dell’alfabeto latino esteso, si avrebbe la codifica della tabella del prossimo lucido

SOLUZIONE ESERCIZIO 2

A 0 0 0 I 0 2 2

B 0 0 1 J 1 0 0

C 0 0 2 K 1 0 1

D 0 1 0 L 1 0 2

E 0 1 1 M 1 1 0

F 0 1 2 N 1 1 1

G 0 2 0 O 1 1 2

H 0 2 1 P 1 2 0

SOLUZIONE ESERCIZIO 2 Naturalmente sono invalide le seguenti

codifiche

- 1 2 1 - 2 1 1

- 1 2 2 - 2 1 2

- 2 0 0 - 2 2 0

- 2 0 1 - 2 2 1

- 2 0 2 - 2 2 2

- 2 1 0 -------------------------------

SOLUZIONE ESERCIZIO 3 Se due messaggi portano circa sette bit,

nell’ipotesi di codici semplici (un simbolo, un messaggio), allora un messaggio porta circa 3,5 bit.

Quindi,

Da cui le due ipotesi possibili, ovvero che il codice sia di 11 simboli oppure che sia di 12 simboli.

31,112

log5,35,3

2

n

n

SOLUZIONE ESERCIZIO 3 Con 11 simboli avremmo

Se scegliessimo una codifica a blocchi servirebbero 4 simboli binari.

Con 12 simboli avremmo

Se scegliessimo una codifica a blocchi servirebbero sempre 4 simboli binari.

45,311log2 n

58,312log2 n

ESERCIZI BASE DI TEORIA DELL’INFORMAZIONE

4. Dato un canale con alfabeto di 21 simboli a codifica semplice, che invia 5 segnali al secondo, misurare la velocità di trasmissione.

5. Se un canale ha velocità di trasmissione pari a 23 Kbps e l’alfabeto di canale è formato da 4 simboli, e la codifica è semplice, quanti segnali invia la sorgente sul canale ogni secondo?

SOLUZIONE ESERCIZIO 4 Su un canale a codifica semplice di 21 simboli

d’alfabeto, un messaggio porta

Quindi, cinque segnali portano circa

La velocità di trasmissione è di circa 22 bps

39,421log2 I

96,2139,45 I

SOLUZIONE ESERCIZIO 5 Se un canale trasmette 4 simboli a codifica

semplice un messaggio porta due bit. Poiché la velocità di trasmissione è di 23 Kbps, passeranno

smn /117062

102423

ESERCIZI SUI CODICI6. Una codifica diretta a blocchi di tredici

simboli binari è utilizzata per mappare un alfabeto di canale di 104 simboli. Calcolare la ridondanza del codice.

7. Si vuole costruire un codice a codifica d’errore basato sul metodo dell’alternanza di simboli validi ed invalidi. Se l’alfabeto di canale è costituito da 77 simboli, e la codifica scelta è a blocchi di 7 simboli binari, quanti bit servono per garantire la costruzione corretta del codice?

SOLUZIONE ESERCIZIO 6 Un codice a blocchi di tredici simboli binari

codifica 213=8192 simboli. Il codice è quindi sovrabbondante. Se il codice fosse abbondante occorrerebbero sette simboli binari, perché 27=128.

Il codice scelto avrebbe ridondanza

Per il codice abbondande a sette bit

%7,988192

1048192

r

%75,18128

104128

r

SOLUZIONE ESERCIZIO 7 Con sette simboli binari la codifica ha una

ridondanza pari a

Per un codice con alternanza occorre che la ridondanza della codifica sia almeno del cinquanta per cento, cosa che si ottiene aggiungendo un singolo bit al codice.

%84,39128

77128

r

ESERCIZI SULL’ERRORE8. Un canale ha un tasso d’errore di 1/1024. Si

misuri l’affidabilità, sapendo che trasmette a 22 Kbps.

9. Un canale ha un tasso d’errore di 1/2048 e trasmette a 12 Kbps. Se si osservano i messaggi giunti alla destinazione, che cosa si può dire di una sequenza di sei messaggi?

10. Quanti messaggi errati ci sono in una sequenza di venti su un canale a tasso d’errore 1/16?

SOLUZIONE ESERCIZIO 8 L’affidabilità di canale si ottiene riducendo alla

percentuale di messaggi corretti determinata dal tasso d’errore la velocità del canale

bpsa 22506102322102422)1024

11(

PROPOSTE SOLUZIONE ESERCIZIO 9a) Almeno uno dei messaggi è erratob) Nessuno dei messaggi è erratoc) Tutti i messaggi sono erratid) Se il primo messaggio è errato allora anche

gli altri lo sonoe) Se il primo messaggio è errato allora gli altri

non lo sonof) Non possono esserci più di due messaggi

errati

SOLUZIONE ESERCIZIO 10 Non esiste una soluzione corretta, perché il

tasso d’errore misura la probabilità che un messaggio sia corretto, non prevede il numero di messaggi errati in una sequenza.

ESERCIZI AVANZATI DI TEORIA DELL’INFORMAZIONE

11. Si determini un codice lineare con un bit di controllo di parità per correggere errori su un canale con alfabeto di 26 simboli codificato in base 2.

12. Si determini la velocità effettiva di canale quando un alfabeto di 100 simboli codificati in base due viene esteso con due bit di controllo di parità, in presenza di un tasso d’errore di 1/2048 bit su un canale a 215 Kbps.

SOLUZIONE ESERCIZIO 11 Un alfabeto di 26 simboli richiede 5 bit per la

codifica binaria. Questa codifica ha ridondanza inferiore al

50%, in particolare la ridondanza risultante è

Occorre quindi codificare a sei bit.

%75,1832

6

32

2632

r

SOLUZIONE ESERCIZIO 11: CODICI VALIDIGLIFO B1 B2 B3 B4 B5 C.P. GLIFO B1 B2 B3 B4 B5 C.P.

A 0 0 0 0 0 0 N 0 1 1 0 1 1

B 0 0 0 0 1 1 O 0 1 1 1 0 1

C 0 0 0 1 0 1 P 0 1 1 1 1 0

D 0 0 0 1 1 0 Q 1 0 0 0 0 1

E 0 0 1 0 0 1 R 1 0 0 0 1 0

F 0 0 1 0 1 0 S 1 0 0 1 0 0

G 0 0 1 1 0 0 T 1 0 0 1 1 1

H 0 0 1 1 1 1 U 1 0 1 0 0 0

I 0 1 0 0 0 1 V 1 0 1 0 1 1

J 0 1 0 0 1 0 W 1 0 1 1 0 1

K 0 1 0 1 0 0 X 1 0 1 1 1 0

L 0 1 0 1 1 1 Y 1 1 0 0 0 0

M 0 1 1 0 0 0 Z 1 1 0 0 1 1

SOLUZIONE ESERCIZIO 11: CODICI INVALIDIGLIFO B1 B2 B3 B4 B5 C.P. GLIFO B1 B2 B3 B4 B5 C.P.

- 0 0 0 0 0 1 - 0 1 1 0 1 0

- 0 0 0 0 1 0 - 0 1 1 1 0 0

- 0 0 0 1 0 0 - 0 1 1 1 1 1

- 0 0 0 1 1 1 - 1 0 0 0 0 0

- 0 0 1 0 0 0 - 1 0 0 0 1 1

- 0 0 1 0 1 1 - 1 0 0 1 0 1

- 0 0 1 1 0 1 - 1 0 0 1 1 0

- 0 0 1 1 1 0 - 1 0 1 0 0 1

- 0 1 0 0 0 0 - 1 0 1 0 1 0

- 0 1 0 0 1 1 - 1 0 1 1 0 0

- 0 1 0 1 0 1 - 1 0 1 1 1 1

- 0 1 0 1 1 0 - 1 1 0 0 0 1

- 0 1 1 0 0 1 - 1 1 0 0 1 0

SOLUZIONE ESERCIZIO 11: NON CODICI

VALIDI INVALIDI

GLIFO B1 B2 B3 B4 B5 C.P. GLIFO B1 B2 B3 B4 B5 C.P.

- 1 1 0 1 0 1 - 1 1 0 1 0 0

- 1 1 0 1 1 0 - 1 1 0 1 1 1

- 1 1 1 0 0 1 - 1 1 1 0 0 0

- 1 1 1 0 1 0 - 1 1 1 0 1 1

- 1 1 1 1 0 0 - 1 1 1 1 0 1

- 1 1 1 1 1 1 - 1 1 1 1 1 0

ESEMPI DI TRASMISSIONE CASO 1: SPEDIAMO UN GLIFO E NE GIUNGE

UNALTRO

CASO 2: SPEDIAMO UN GLIFO E GIUNGE UNNON CODICE VALIDO

CASO 3: SPEDIAMO UN GLIFO E GIUNGE UNCODICE INVALIDO

CASO 4: SPEDIAMO UN GLIFO E GIUNGE UNNON CODICE INVALIDO

CASO I Se, ad esempio, parte il glifo X e giunge il glifo H

allora lo schema di trasmissione è.

Come si vede il numero di errori commessi è 2. L’errore non viene corretto. In generale, se il codice a correzione d’errore è

lineare il numero di errori commessi se parte un glifo e ne giunge un altro è pari.

X 1 0 1 1 1 0

H 0 0 1 1 1 1

- + + + + -

CASO 2 Se parte il glifo X e giunge un non codice, allora si

potrebbe avere, ad esempio

Il numero di errori è 2. L’errore viene riconosciuto perché i non codici non

sono ammissibili In generale, se il codice a correzione d’errore è

lineare il numero di errori commessi se parte un glifo e giunge un non codice valido è pari.

X 1 0 1 1 1 0

- 1 1 1 1 1 1

+ - + + + -

CASO 3 Se parte il glifo X e giunge un codice invalido,

allora si potrebbe avere, ad esempio

Il numero di errori è 1. L’errore viene riconosciuto. In generale, se il codice a correzione d’errore è

lineare il numero di errori commessi se parte un glifo e giunge un codice invalido è dispari.

X 1 0 1 1 1 0

- 1 0 1 1 1 1

+ + + + + -

CASO 4 Se parte il glifo X e giunge un non codice invalido,

allora si potrebbe avere, ad esempio

Il numero di errori è 3. L’errore viene riconosciuto. In generale, se il codice a correzione d’errore è

lineare il numero di errori commessi se parte un glifo e giunge un non codice invalido è dispari.

X 1 0 1 1 1 0

- 1 1 1 0 1 1

+ - + - + -

SOLUZIONE ESERCIZIO 12 Per codificare 100 simboli occorrono 7 bit. Se si aggiungono 2 bit di controllo di parità il

codice risulta di 9 bit. La ridondanza è quindi

La velocità di trasmissione viene ridotta quindi in misura pari ai bit effettivamente trasmessi mediante il processo di correzione del codice lineare.

Adotteremo il metodo dello stream standard.

%4,80512

100512

r

METODO DELLO STREAM STANDARD Lo stream standard è uno stream di bit lungo

n, tale per cui il tasso d’errore risulti di 1/n. Se il tasso d’errore è espresso in frazione

egizia 1/n, ovviamente n è la lunghezza dello stream standard.

Se il tasso d’errore è espresso in percentuale equivalente alla frazione p/q, allora per calcolare n, lunghezza dello stream standard, dove [x] è il più piccolo intero più grande di x.

Se un codice è a blocchi, ovviamente, il numero n è approssimato.

p

qn

ESEMPIO Supponiamo che un codice a blocchi di 12 bit

sia utilizzato su un canale a tasso d’errore 1/1024.

Lo stream standard è costituito da un numero di blocchi che formi uno stream il più corto possibile rispetto a 1024 bit.

Il numero minimo di blocchi è 86, e la lunghezza corrispondente è 1032 bit.

PROCESSO DI CORREZIONE1. Trasmissione di uno stream standard di bit;2. Ripetizione dei blocchi riconosciuti errati;

[SI CONSIDERA UNA SOLA RIPETIZIONE]

Lo stream così ottenuto viene posto al denominatore di una frazione al cui numeratore si mette il numero di blocchi effettivamente inviati.

Si moltiplica poi la frazione così ottenuta per la velocità di canale.

CALCOLO Poiché il tasso d’errore è 1/2048 lo stream

standard è 2048 bit. Poiché la codifica base è a sette bit lo stream trasferisce 293 blocchi base.

L’estensione a nove bit comporta che per inviare 293 blocchi base occorre inviare 293 blocchi a nove bit, che portano lo stream standard a 2637 bit.

Il tasso d’errore di 1/2048 comporta che l’errore commesso sullo stream standard possa portare alla ripetizione di un blocco di nove bit per correggere il primo errore sui 2048 bit dello stream base.

Come approssimazione per eccesso si stima la ripetizione ulteriore di un ulteriore blocco.

LUNGHEZZA EFFETTIVA DELLO STREAM Lo stream effettivo è quindi 2637+18=2655. Poiché uno stream di 2655 bit porta 293

blocchi, ognuno dei quali esprime, in effetti, l’informazione pari a log2(100).

Quindi la velocità effettiva di canale è

Kbpsbps

bpsKbpsv

157160717

102421573,02152655

)100(log293 2