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. 17ELEMENTI 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’INFORMAZIONE1. 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 2A 0 0 0 I 0 2 2B 0 0 1 J 1 0 0C 0 0 2 K 1 0 1D 0 1 0 L 1 0 2E 0 1 1 M 1 1 0F 0 1 2 N 1 1 1G 0 2 0 O 1 1 2H 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’INFORMAZIONE4. 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 /117062102423
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,18128104128
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,3912877128
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)102411(
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,18326
322632
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 1B 0 0 0 0 1 1 O 0 1 1 1 0 1C 0 0 0 1 0 1 P 0 1 1 1 1 0D 0 0 0 1 1 0 Q 1 0 0 0 0 1E 0 0 1 0 0 1 R 1 0 0 0 1 0F 0 0 1 0 1 0 S 1 0 0 1 0 0G 0 0 1 1 0 0 T 1 0 0 1 1 1H 0 0 1 1 1 1 U 1 0 1 0 0 0I 0 1 0 0 0 1 V 1 0 1 0 1 1J 0 1 0 0 1 0 W 1 0 1 1 0 1K 0 1 0 1 0 0 X 1 0 1 1 1 0L 0 1 0 1 1 1 Y 1 1 0 0 0 0M 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 CODICIVALIDI 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 0H 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,80512100512
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.
pqn
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