CCODICI5 - UniNa STiDuE

1
FONDAMENTI
DI INFORMATICA
di
Matjaz Hmeljak
parte
INFORMAZIONE e CODICI
I N F O R M A Z I O N E - cenni
contenuto per la parte informazione:
* DEFINIZIONE
* MESSAGGI, DATI
* INFORMAZIONE E PROBABILITA'
* QUANTITA'
* ESEMPI
* DATI COMPOSTI
* SIMBOLI NON EQUIPROBABILI
* INFORMAZIONE MEDIA
* SIMBOLI DIPENDENTI
* INFORM. MEDIA DI UNA LETTERA DI
UN TESTO
2
contenuto per la parte codici:
contenuto della parte codici:
codici, rappresentazione, dati
codifiche binarie
codice ASCII
codice UNICODE
codici a controllo di errore
codici a correzione di errore
bibliografia
esercizi
3
parte informazione
segue la parte relativa
al concetto di informazione,
e
alla misura dell’informazione
4
informazione e codici
definizione
dell' informazione
?
5
6
I N F O R M A Z I O N E - cenni
canale di
trasmissione
?
hai vinto 1 miliardo
alla lotteria di carnevale
di Canicattini Bagni.
messaggio: contiene
informazione
sistema
sorgente
->
-> sistema
ricevente
I N F O R M A Z I O N E - definizione
“sistema di trasmissione” : due persone A e B,
la persona A (sorgente di informazione) dice
alla persona B (ricevente di informazione) :
hai vinto 1 miliardo alla lotteria di carnevale di
Canicattini (dato = informazione codificata )
A ------------------------------------>
B
sistema canale di trasmiss.
sistema
sorgente
informazione
ricevente
(messaggio M)
7
I N F O R M A Z I O N E - definizione
8
Con una dizione un po' approssimata diremo che :
l'informazione e' il contenuto
del messaggio M
trasmesso da un sistema sorgente A
al sistema ricevente B,
"contenuto" nel senso:
l’informazione contenuta nel messaggio M
e' capace di modificare lo stato di B !!
... un messaggio o un dato che non modifica lo stato
del sistema ricevente contiene zero informazione ...
9
I N F O R M A Z I O N E - messaggio / dato
esempio: abbiamo trovato un nuovo modo di far soldi
con un’ attivita’ in internet e lo scriviamo
sull’ ultima pagina della nostra rubrica telefonica:
A
------------------>
sistema
dispositivo di
sorgente
registrazione
informazione
B
= supporto
di memoria
--> dato
in un secondo tempo, eventualmente, avremo...
C
<----------------------B
sistema rice- dispositivo di
= supporto
vente
lettura
di memoria
<-- dato
I N F O R M A Z I O N E - messaggio / dato
10
notare: la stessa comunicazione verbale implica l’uso di
simboli per rappresentare oggetti (o altro):
la “parola” “gatto” e’ un simbolo che rappresenta un
gatto reale, la sequenza di suoni g-a-t-t-o non ha alcun
collegamento con l’oggetto rappresentato (idem per cat,
neko, mačka, kot, ecc)
la scrittura (circa 6000 anni fa) e’ un sistema di
rappresentazione di informazioni (codifica)
A
SCRIBA
------------------>
B
stilo
TAVOLETTA
in un secondo tempo (2 o 6000 anni dopo):
C <----------------------B
LETTORE
TAVOLETTA
11
I N F O R M A Z I O N E - messaggio / dato
L' informazione puo' essere trasmessa
( messaggio tra due sistemi [ A ==> B ] )
o registrata
(dato =info codificata su un supporto
di memoria per essere in seguito riutilizzata)
utilizzando un codice di rappresentazione
(vedremo)
A
abiesabies
------------------>
dispositivo
0011 0111 1010 0100 1111
(trasmette
e codifica)
B
37A4F =
dato bla-bla
codificato
I N F O R M A Z I O N E - cenni
dell' informazione interessa:
*
quantita' (unita' di misura)
*
rappresentazione (codici)
*
contenuto (significato, interpretazione)
12
I N F O R M A Z I O N E - cenni
*
13
quantita' (unita' di misura)
come si misura l’informazione ?
(2 pinte di informazione? - 2 claftre di informazione?)
vedremo tra breve
*
rappresentazione (codici)
( come si scrive "bisturi" in cinese? ... oppure
come si scrive “tassa di importazione” in wolof?
o “fondamenti di informatica” in guarani’ ?
o "domani" in azero? )
I N F O R M A Z I O N E - cenni
*
14
contenuto (significato, interpretazione)
lo studio del contenuto o del significato, interpretazione
(analisi pragmatica) di un messaggio non puo' prescindere dal
contesto:
1) es.: < l’inquinamento del mare sta aumentando >
2) es.: < mi devi 10 euro >
3) es.: < 1997 x 1997 = 3988009 >
4) es.: < #include <conio.h> void main() { cputs(“ciao”); }
5) es.: < la devolution, l'involution, il furbolution e
la pollution sono in fase di deflation... >
I N F O R M A Z I O N E - cenni
15
* contenuto (significato, interpretazione)
6) es.: < “ il recente lavoro di Zaffira Caterazzu abbraccia
il ritmo esistenziale, dilatandosi nella simbologia dalle precedenti porte che adombravano la necessita'dell'apertura
e dell'incontro oltre le differenze, e comprende questa significanza oltre i lacerti degli elementi visivi e formali nel non
effimero prototipo del nulla, che pochi comprendono” >
=> il contenuto del messaggio in generale implica due
contesti, del sistema sorgente e del sistema ricevente
il messaggio qui sopra (peraltro parte di un testo "reale" di un
critico d'arte) richiede un ambiente di nozioni del ricevente che
forse la maggior parte di noi non ha ... ;-)
lo studio del significato e l' interpretazione (analisi pragmatica)
di un messaggio sara’ oggetto del nostro corso solo per
programmi C++ ...
I N F O R M A Z I O N E - cenni
16
vediamo ora meglio questi attributi dell'informazione:
•quantita'
(unita' di misura)
•rappresentazione (codici)
* contenuto (significato, interpretazione)
 cominciamo con la quantita' ....
questa e' legata alla probabilita'
I N F O R M A Z I O N E - quantita’
La quantita' di informazione
associata ad un messaggio o ad un dato
dipende dall' incertezza del messaggio ovvero
dalla probabilita' di avere proprio
quel messaggio tra tutti i messaggi possibili
Ad es. il messaggio
"non hai vinto alla lotteria"
ha un contenuto di informazione
cioe’ l’effetto sullo stato del ricevente e’
ben diverso dal messaggio:
"hai vinto 1 miliardo alla lotteria"
17
18
I N F O R M A Z I O N E - probabilita’ di un dato
Esempi ... [quantita’ info del messaggio <--> probabilita’ del mess.]
vincita in lotteria rionale, con 200 numeri, un premio:
- probabilita' di vincita 1/200
vincita su lancio di moneta a testa/croce:
- probabilita' di vincita di 1/2
vincita al concorso per un posto di ricercatore presso l'
Universita' di Raute con unico candidato
(raccomandato):
- probabilita' di vincita 1/1 (certezza)
laurea in ingegneria gastronomica con 110 in 2 anni
- probabilita’ di riuscita 0 ( ..... impossibile ... non c’e’ )
I N F O R M A Z I O N E - I = f(probabilita’)
19
la quantita’ di informazione e’ legata all’ incertezza
con cui si aspetta il messaggio (o il dato), quindi alla
probabilita’ di quel dato (o messaggio) :
un dato relativo ad un evento poco probabile
contiene una grande quantita' di informazione;
e piu' conosco il contenuto del messaggio, cioe'
maggiore e' la probabilita' del messaggio ->
piu' piccola e' la quantita' di informazione contenuta;
fino al dato relativo ad un evento certo, che
ha probabilita' uno e a cui si associa un quantita'
di informazione zero.
I N F O R M A Z I O N E ...
20
I = f(p)
la quantita’ di informazione decresce
al crescere della probabilita’ del dato:
diagramma a
fianco, in
prima
approssimazione:
I
I grande
I piccola
p
p piccola
p grande
Ma il legame tra probabilita' e informazione non e' lineare;
inoltre- si tenga presente che la probabilita'viene misurata
in valori da 0 (evento impossibile) a 1 (evento certo)
INFORMAZIONE
- I = f(probabilita’)
21
il legame tra la probabilita’ e la quantita’ di
informazione e’ di tipo logaritmico; se dimezza la
probabilita’ -> l’ informazione aumenta di uno
Informazione
3
2
1
0
probabilita'
piccolainformazione
grande
Probabilita' grande,
P =1 significa Info=0
Informazione piccola,
1/8 1/4 1/2
1 probabilita'
Ad un evento certo si associa un'informazione nulla, ad un
evento poco probabile si associa un'informazione grande.
22
la funzione logaritmo
funzione logaritmo: log2(n) = x
...alcuni valori:
inversa di
log2(x)
2-4
log2(0,0625)=-4 0,0625=
log2(0,125)=-3 0,125= 2-3
log2(0,25)=-2 0,25= 2-2
log2(0,5)=-1 0,5= 2-1
log2(1)=0
1 = 20
log2(2)=1
2 = 21
log2(4)=2
4 = 22
log2(8)=3
8 = 23
log2(10)=3,3 10= 23,3
log2(16)=4
16= 24
log2(1024)=10 1024= 210
log2(1048576)=20 1048576=220
n = 2x
0
-1
-2 -
0,5
-
1
x
I N F O R M A Z I O N E - I = log2(1/probab)
23
il legame [ probabilita’ - quantita’ di informazione ]
e’ di tipo logaritmico: I = log2(1/p) = -log2(p)
Info
Per un dato relativo ad un evento su
N eventi possibili ed equiprobabili:
la probabilita’ del dato e’ p = 1/N
e quindi
I= log( 1/(1/N) )= log( N )
Prob
INFORMAZIONE
-
unita’ di ...
24
si definisce quantita’ di informazione unitaria
di
1 bit
l'informazione contenuta in un messaggio o in
un dato
di probabilita' 1/2
Es.: lancio di una moneta non truccata a testa o cifra
questo messaggio (relativo al risultato) ha un
contenuto di un bit di informazione :
I = log2( 1/probab ) = log2( 1/ ( 1/2 ) ) = log2 ( 2 ) = 1
25
I N F O R M A Z I O N E - 5 esempi
Relazione tra informazione e probabilita' :
I = log( 1/p ) = -log( p ) = log ( N )
2
2
2
esempi:
* informazione relativa ad un dato su sedici:
4 bit
* informazione relativa ad evento certo (p=1):
0 bit
* quantita' di inform. di un dato composto da un
simbolo dell' insieme delle 25 lettere dell'
alfabeto inglese :
I = log2 (25) =
4,6 bit
26
I N F O R M A Z I O N E - 5 esempi
altri esempi per il legame
quantita’ di informazione - probabilita’:
I = log2(1/p) = -log2(p) = log2(N)
quantita' di informazione di un dato composto
da un simbolo scelto tra 25 - qui, da una lettera
dell' insieme delle 25 lettere dell' alfabeto inglese:
I = log2 (25) =
4,6 bit
I N F O R M A Z I O N E - 5 esempi
altri esempi per il legame
quantita’ di informazione - probabilita’:
I = log2(1/p) = -log2(p) = log2(N)
informazione di una cifra decimale
I = log2(10) =
( 2 alla 3 = 8, 2 alla 3,3 = 10 )
3,3 bit
27
28
I N F O R M A Z I O N E - 5 esempi
altri esempi per il legame
quantita’ di informazione - probabilita’:
I = log2(1/p) = -log2(p) = log2(N)
* quantita' di inform. di una lettera dell' insieme delle
25 lettere dell' alfabeto inglese:
I = log2 (25) = 4,6 bit
* inf. di una cifra decimale I = log2(10) =
3,3 bit
* informazione di una cifra ottale (otto
simboli da 0 a 7)
I = log2( 8 ) =
3 bit
I N F O R M A Z I O N E - cont. 5 esempi
29
ancora un esempio per il legame
quantita’ di informazione - probabilita’:
I = log2(1/p) = -log2(p) = log2(N)
abbiamo visto che:
* info. relativa ad un dato su sedici:
4 bit
* info. di una lettera inglese:
I = log2 (25) = 4,6 bit
* info. di una cifra decimale:
I = log2(10) = 3,3 bit
* info. di una cifra ottale:
I = log2( 8 ) = 3 bit
quantita’ di informazione di una cifra binaria:
probabilita’ di scelta tra "0" e "1" : p = 1/2,
quantita'di inform(cifra bin) = I = log2(2) = 1 bit
30
Informazione - dato semplice
esercizi:
quanta informazione ha il simbolo +
scelto tra i dieci simboli + - * / . , ! ? ; :
quanta informazione ha il dato vocale E
scelto tra i cinque simboli A E I O U
quanta informazione ha una cifra esadecimale E scelta
tra i 16 simboli 0 1 2 3 4 5 6 7 8 9 A B C D E F
quanta informazione ha il dato
simboli dell’alfabeto russo
P scelto tra i 32
(soluzione segue)
31
Informazione - dato semplice
soluzioni:
quanta informazione ha il dato +
(scelto tra i dieci simboli + - * / .
n=10
,;:
!? )
log2(1/p) = log2(n) = log2(10 ) = 3,3 bit
quanta informazione ha il dato E
(scelto tra i cinque simboli A E I O U )
n=5
log2(1/p) = log2(n) = log2(5 ) = 2,3 bit
Informazione - dato semplice
soluzioni:
quanta informazione ha il dato E
scelto tra i 16 simboli 0 1 2 3 4 5 6 7 8 9 A B C D E F
n=16
log2(1/p) = log2(n) = log2(16 ) = 4 bit
quanta informazione ha il dato P
scelto tra i 32 simboli dell’alfabeto russo
n=32
log2(1/p) = log2(n) = log2( 32 ) = 5 bit
32
I N F O R M A Z I O N E - dati composti
quantita' di informazione
contenuta in un
dato composto:
quanta informazione contiene il dato seguente:
"operator overloading can be dangerous"
33
I N F O R M A Z I O N E - dati composti
34
dato composto: quanta informazione hanno i tre dati
seguenti (tutti di 8 simboli) :
“7 A 4 5 F F 0 0”
“ B F U W R Q E A”
“P a p e r i n a”
i 3 dati contengono la stessa quantita’di informazione?
L’ultimo simbolo 0 nel primo dato e l'ultimo simbolo A
nel secondo dato hanno una probabilita’ diversa
dall’ultimo simbolo a nel terzo dato?
Nei tre dati (composti da piu’ simboli) i singoli simboli
sono indipendenti tra loro?
I N F O R M A Z I O N E - dati composti
35
Per calcolare quanta informazione ha un dato composto
da piu’ simboli, come i tre dati visti:
1) “ 7 A 4 5 F F 0 0 ”
2) “ B F U W R Q E A ”
3) “ P a p e r i n o ”
distingueremo
il caso di dato composto
con i singoli simboli indipendenti tra loro (dati 1 e 2)
dal caso di dato composto da simboli legati tra loro,
cioe’ dipendenti uno dall’altro (dato 3)
I N F O R M A Z I O N E - dati composti
36
1) dati composti da piu' simboli indipendenti tra loro
(indipendenti la presenza dei primi k-1 simboli
non cambia la probabilita' del k-esimo simbolo)
probabilita' che si verifichi l’evento composto “ a , b” ,
con a e b indipendenti vale:
p( a,b) = p(a) * p(b)
da cui l’ informazione contenuta in un dato composto “a,b”
e' data dalla somma delle singole informazioni :
I(a,b) = log2( 1/ p(a,b) )
= log2( 1/( p(a) * p(b) ) )
= log2( 1/p(a) ) + log2( 1/p(b) ) ->
I(a,b) = I(a)+I(b)
(a,b simboli indipend.)
I N F O R M A Z I O N E - dati composti
37
Informazione contenuta nella parola di n lettere:
"ZHWITQ"
se le lettere sono indipendenti tra loro,
e’ la somma delle informazioni dei n singoli simboli
se le lettere sono equiprobabili allora l’informazione
per simbolo e’ costante e allora:
I(lettera)= 4,6 bit = log2(25) (alfab.di 25 lettere), quindi
6 * 4,6 bit = 27,6 bit
(scelta di un dato tra 2^28 = 256 milioni di dati
possibili)
I N F O R M A Z I O N E - dati composti
38
L'informazione contenuta nel dato (numero decimale):
"1863"
(una cifra decimale ha un contenuto di informazione
log2(10) = 3,3 bit )
per un dato di 4 cifre l’informazione
e' di 4 * 3,3 bit = 13,2 bit
ovvero scelta di un dato tra 10000 possibili (appunto
1863 scelto tra i dati 0000 ... 9999)
39
I N F O R M A Z I O N E - dati composti
esercizio:
quanta informazione hanno i dati:
5883460
(num.telefonico di 7 cifre)
さ よ な ら (sayonara(*)) (parola giapponese di 4 sillabe,
- vi sono 45 sillabe in giapponese)
corrompevole (parola di 12 lettere)
4 x 4 = 16 (un elemento della tavola Pitagorica)
segue soluzione
(*) in scrittura semplificata (hiragana)
;-)
I N F O R M A Z I O N E - dati composti - soluzione :
40
6763411 (num.telefonico di 7 cifre)
dato x x x x x x x (x sta per una cifra)
con I(x) = log2(10) = 3,3 -> I(dato)= 7*3,3= 23.1 bit
さ よ な ら (sayonara) (parola giapponese di 4 sillabe,
- vi sono 45 sillabe in giapponese)
dato x x x x (x sta per una sillaba)
con I(x) = log2(45) = 5,5 -> I(dato) = 4*5,5 = 22 bit
corr ompe vole (parola di 12 lettere, vi sono 21 lettere)
dato xxxx xxxx xxxx
con I(x) = 4,4 bit -> I(dato) = 12 * 4,4 = 53 bit
4 x 4 = 16 (elemento della tavola delle moltiplicazioni)
dato x * x = zz (con x cifra da 1 a 9, il resto e’ determinato)
con I(x) = 3,3 -> I(dato) = 2*3,3 = 6,6 bit
I N F O R M A Z I O N E - dati composti
41
Ripetiamo: l’ informazione contenuta in un dato composto da n
simboli indipendenti tra loro (cioe’ dove il verificarsi di k simboli
(k<n) non influisce sulla probabilita’ dell’ ennesimo simbolo) e’ la
somma delle informazioni dei singoli simboli,
se poi anche i singoli simboli sono equiprobabili (allora
l’informazione per simbolo e’ costante) l’informazione di un
dato di n simboli indipendenti ed equiprobabili = n *
info(simbolo)
MA: il calcolo dell’informazione contenuta in
un dato composto cambia ... se:
se i simboli non sono indipendenti tra loro e/o
se non sono equiprobabili
I N F O R M A Z I O N E - dati composti
42
Dato di n simboli non equiprobabili,
e/o non indipendenti tra loro un esempio per capire meglio:
calcolo della quantita' di informazione
contenuta nella parola "CAROTA"
1) se considero le lettere indipendenti tra loro:
6 * 4,6 bit = 27,6 bit
(scelta di uno tra 2^28 = 256 milioni di dati possibili
piu’ precisamente, 25 ^ 6 = 244.140.625 :
ovvero scelta di un dato tra i 244M di dati tipo:
AAAAAA, AAAAAB, .. AAAAAZ, AAAABA, ...
... ZZZZZW, ZZZZZX, ZZZZZY, ZZZZZZ)
I N F O R M A Z I O N E - dati composti
43
Dato di n simboli non equiprobabili,
e/o non indipendenti tra loro calcolo della quantita' di informazione
contenuta nella parola "CAROTA"
1) se le lettere sono indipendenti tra loro: I = 6 * 4,6 bit
= 27,6 bit (scelta di uno tra 256 = 244.140.625 dati possibili )
2) MA -osservo che CAROTA e'una parola della lingua
italiana (da un dizionario "medio" con 65000 parole)
allora l' informazione e' relativa ad un dato su 65000,
ovvero log2 ( 65000 ) = 16 bit
(... e non 27,6 !! )
(scelta di una parola tra "a", "abaco", "abate", "abbacchiare",
... "zuppa", "zuppiera", "zuppo", "zuzzurullone" (R.C.Melzi,
Bantam ed.1976)
I N F O R M A Z I O N E - dati composti
44
Ancora due esempi:
2) informazione data nella parola "PAPAVERO"
con lettere indipendenti tra loro: 8*4,6 bit =
36,8 bit
(scelta di uno tra 2^37 = 152 miliardi di dati possibili
piu’ precisamente, 25 ^ 8 = 152 587 890 625)
---> MA:
se diciamo che la parola PAPAVERO e' una parola
tratta da un dizionario della lingua italiana con 65000
parole - allora l' informazione e' relativa ad un dato su
65000, ovvero log2 ( 65000 ) =
16 bit
come nell'esempio precedente, e non 36,8 bit !!
I N F O R M A Z I O N E - dati composti
45
3) esempio:
quantita’ info. di una stringa di 8 caratteri (alfabeto
inglese di 25 lettere):
I("TOLMEZZO") = 8 * 4,6 bit = 36,8 bit
(ho 8 lettere equiprobabili e indipendenti)
invece se considero la quantita’ di informazione di
I(Tolmezzo) nel caso in cui so che Tolmezzo e’ nome di
una citta' dell'Italia scelta tra mille
(assumo il dato preso da una tabella di 1000 citta’)
I( un dato su 1000 ) = log2(1000) = 10 bit !!!
I N F O R M A Z I O N E - dati composti
46
ritorniamo sull' esempio per il caso di dato composto
con simboli NON indipendenti tra loro:
nel dato “CAROTA” , per ipotesi una parola della
lingua italiana, la probabilita’ delle singole lettere
cambia:
per la prima e’ 1/25:
“C”
per la seconda lettera - deve essere una vocale, oppure
una “h”,"r","l","s","n", quindi
la probabilita’ e’ 1/10...
“CA”
la terza lettera ...
“CAR”
la quarta lettera p(“O”)>1/5 “CARO”
la quinta p(“T”) > ...
“CAROT”
l’ultima lettera .. solo A o E “CAROTA”
I N F O R M A Z I O N E - dati composti
2) es. di dato composto da piu’ simboli - es.:
“fondamenti di informxxxxx”
L’ informazione di xxxxx e’ praticamente zero
[ ma qual’ e’ la quantita’ di informazione / ricevuta / da un
destinatario medio del corso di fondamenti di informatica ;-} ]
in generale il contenuto informativo di un testo
formato da parole, a loro volta formate da lettere,
NON e’ semplicemente :
(lungh. testo)*(informazione di una lettera alfabeto)
e quindi in un testo l' informazione di una lettera
non e’ semplicemente
I = log2( 1/ prob ) = log2 ( Num.lettere )
47
I N F O R M A Z I O N E - dati composti
48
il contenuto informativo di un testo formato da stringhe di
caratteri non e’ semplicemente
num.caratteri * info(carattere)
e l' informazione di una lettera non e’
I = log2( 1/ prob ) = log2 ( Num.lettere alfabeto)
devo considerare due aspetti:
a) i simboli non sono equiprobabili
(e questo era noto gia' ai tipografi da secoli)
b) simboli legati tra loro, ovvero non sono indipendenti
(in una stringa di k simboli
i primi k-1 simboli cambiano la probabilita' del
k-esimo simbolo ...
vediamo
I N F O R M A Z I O N E - cenni
49
DATO CON SIMBOLI NON EQUIPROBABILI
es: 32 lanci di una moneta (truccata) ottengo i valori:
CCCCC TCCCC CCCTC CCTCC
C T C C C C C C C C C C ( 28 croce e 4 testa )
assumo quindi
nc
nt
PC = ----------PT = ---------nc + nt
nc + nt
p(C)=28/32 e p(T)=4/32 -> inform.di un singolo dato:
( I = log2(1/p) ! )
I ( C )= log2(1/p(C)) = log2 ( 32/28 ) = log2 (1,14) = 0,19
I ( T )= log2(1/p(T)) = log2 ( 32/4 ) = log2(8) = 3
I(dato complessivo) = ?
I N F O R M A Z I O N E - dati composti
50
continua caso di simboli indipendenti ma non equiprobabili: se
su 32 lanci di una moneta truccata ottengo 28 valori croce e
4 valori testa:
CCCCC TCCCC CCCTC CCTCC
CTCCC CCCCC CC
allora p( C ) = 28/32 e p( T ) = 4/32
e quindi (ricorda: I = log2(1/p) ! ): il verificarsi di un singolo C
oppure T porta l’ informazione seguente:
I ( C ) = log2(1/p(C)) = log2 ( 32/28 ) = log2 (1,14) = 0,19
I ( T ) = log2(1/p(T)) = log2 ( 32/4 ) = log2(8) = 3
I(dato complessivo) =
I (dato) = num(c)*info(c) + num(t)*info(t) ... cioe' :
I(dato) = 28* 0,19 + 4 * 3 = 5,6 + 12 = 17,6
I N F O R M A Z I O N E - cenni
51
cont. es: 32 lanci: CCCCC TCCCC CCCTC CCTCC CTCCC
CCCCC CC (28 croce e 4 testa) quindi:
p(C) = 28/32, I (C) = log2(32/28) = 0,19
p(T)= 4/32; I (T) = log2(32/4)= 3
I(dato completo) = 28 * 0,19 + 4 * 3 = 5,6 + 12 = 17,6
Il contenuto informativo medio per simbolo
(dato composto da 2 simboli non equiprobabili):
I
I(tot.dato)
med = ----------------------num.simboli del dato
I N F O R M A Z I O N E - cenni
52
DUE simboli non equiprobabili, I media / simbolo:
il contenuto informativo medio per simbolo
(dato composto da 2 simboli non equiprobabili):
Imed
I(tot.dato)
= ----------------------num.simboli del dato
I(tot.dato)
nc*Ic + nt*It
= ----------- = --------------nc+nt
nc + nt
nc
nt
= ----* Ic + ----* It
nc+nt
nc+nt
=
=
= p(c)*Ic + p(t)*It
I N F O R M A Z I O N E - cenni
53
due simboli non equiprobabili, I media / simbolo:
Imed
=
p(c)*Ic + p(t)*It
e in generale per n simboli: Imed=  i p(i) * I (i)
Nel caso di due simboli e' certo che uno dei due
simboli si verifica, quindi deve essere:
p(a)+p(b)=1 --> p(b)=1- p(a), quindi:
Imed = p(a) * Ia + p(b) * Ib =
= p(a) *( log2(1/p(a)) + (1-p(a))* log2(1/(1-p(a)) )
con un massimo per p(a) = p(b), e’zero se p(a)=0 o se p(a) = 1:
Conten. inform. medio per simbolo, caso di 2 simboli
non equiprobabili: I med = p(a) * Ia + p(b) * Ib ,
dove nel caso di due simboli vale che:
54
p(a) + p(b) = 1 --> p(b) = 1 - p(a) --> quindi :
Inf
I media=p(a) * Ia + p(b) * Ib
1
1
0
1/2 Prob 1
= p(a) * (log2(1/p(a)) +
(1-p(a)) * log2(1/(1-p(a)) )
=f(p(a)) = figura a destra:
massimo per p(a) = p(b)
zero se p(a)=0, o se p(a) = 1
I N F O R M A Z I O N E - info media (carattere)
55
l’informazione media per simbolo per un dato
composto da n simboli con probabilita’ diversa:
Imed =  i p(i) * I (i)
Imed =
cioe’
 i { p(i) * (-log2 (p(i) ) ) }
In un testo di 10000 lettere casuali (alfabeto di 21
lettere) a distribuzione uniforme avremo 476 volte (in
media) ciascuna delle lettere - la quantita’ di
informazione per lettera e' I(l) = log2(21) = 4,4 bit
Ma in un testo in italiano (o in altra lingua) le
probabilita’ delle singole lettere sono diverse.
56
I N F O R M A Z I O N E - info media (carattere)
lettere non equiprobabili:
I med = -  i { p(i) * log2 (p(i) ) }
si puo' vedere che in un testo italiano di 10000 lettere
avremo circa:
1300 e
1100 i
1000 a
850 o
650 r
650 l
...
...
...
150 z
120 f
100 q
...
5 j
ed il contenuto di informazione medio per lettera e'
I(l) = p(a)*I(a)+p(b)*I(b)+..+p(z)*I(z) = 3,9 bit
mentre con lettere equiprobabili I(l) = log2(21) = 4,4 bit
I N F O R M A Z I O N E - info media (carattere)
57
ripetiamo:
... con simboli equiprobabili, l’informazione media di
I(lettera) = I ( 1/p ) = I ( N ) = log2(21) = 4,4 bit ,
con testo di lingua italiana, lettere NON equiprobabili,
il contenuto di informazione medio e' piu' piccolo :
Imed = -  i { p(i) * log2 (p(i) ) } = ... = 3,9 bit
---------------------------------------------------------------------ma il contenuto di informazione medio reale per una
lettera in un testo di italiano
e’ ancora molto piu’ piccolo, perche' le lettere NON
sono indipendenti tra loro vediamo ...
I N F O R M A Z I O N E - info media (carattere)
abbiamo visto che:
I(lettera/equipr.) = I(1/p) = I(N) = log2(21) = 4,4 bit
lettere/nonequipr.: Imed = - i {p(i)*log2 (p(i) )} = 3,9
ora, se immagino che le parole presenti nel testo
siano tutte contenute in un dizionario di 65000 parole
allora il contenuto info. medio per parola e’:
I(parola) = log2(N) = log2(65000) = 16 bit/parola
se supponiamo in media 6 lettere per parola, allora
Imed(lettera) = I(parola) / 6 = 2,67 bit / lettera
( beh, ... 2,3 bit/lettera se in media le parole hanno 7 lettere,
3,2 bit/lettera se in media le parole hanno 5 lettere ecc ;-)
58
I N F O R M A Z I O N E - info media (carattere)
59
I(lettera/equipr) = I(1/p) = I(N) = log2(21) = 4,4 bit
Imed(lettera/nonequip)= - i {p(i)*log2 (p(i) )}= 3,9 bit
Imed(lettere non equiprob = I(parola) / 6 = 2,67 bit
e dipendenti tra loro)
MA: tenendo conto del contesto
(anche le parole non sono indipendenti tra loro !)
si arriva ad un valore approssimativo di :
1 bit per lettera
I N F O R M A Z I O N E - info media (carattere)
In un generico testo la quantita’ di informazione
media per lettera e’ di circa un bit
60
I N F O R M A Z I O N E - info media (carattere)
61
Lettere, cifre, segni di interpunzione: la rappresentazione standard delle lettere in un calcolatore e’ data
dalla codifica ASCII che usa 8 bit per lettera
(Americ.Standard Code for Inform. Interchange)
allora un testo di 800 pagine (75 col * 40 righe) =
75*40*800 = 3000*800 = 2.400.000 lettere occupa due dischetti da 1,2 mega byte -
compattando (memorizzo il testo con codifiche piu'
economiche) arrivo a 2,4Mb/8 = 300Kb.
oggi sempre piu' in uso UNICODE a 16 bit (vedremo)
I N F O R M A Z I O N E - info media (carattere) 62
si noti che il problema della codifica "economica"
rimane attuale anche se la tecnologia offre
continuamente dispositivi e mezzi di memoria sempre
piu' capienti:
1980 i primi HD in commercio da 10Mbyte...
1999 in commercio dischi da 20 Giga Byte
(2.E+10= 8000 libri da 800 pag da 40 righe da 80 caratt)
2005 in commercio dischi da 200 G byte...
* un video da 100 minuti su HD, ma 100 video?
* esperimenti con misure che producono giga-byte
di dati in pochi minuti - quanto in un anno ?
* indici di archivi su rete con tera-byte di dati ...
tra 5 anni ? ... se si estrapola la situaz. di 5 anni fa?
codifica dati
63
se voglio salvare un filmato o un video da 90 minuti,
con 24 immagini al secondo, precisione 1200x900,
avro':
schermo a bassa risoluzione, dato da 640*480 (NTSCVGA) pixel (punti immagine) ciascun pixel richiede 3
byte, quindi
640*480*3 = 307.200*3 = 921.600 byte = 1M byte
24 immagini al secondo significa 24 * 1M = 24M,
90 minuti = 90*60 secondi = 5400 secondi quindi
in totale 5400 * 24 immagini, 129.600 immagini e
quindi 921.600 * 129.600 = 119.439.360.000 byte =
= 119 G byte per un video a bassa qualita' non
compresso...
codifica dati
64
con risoluzione maggiore, schermo da 1200 x 900 pixel
(punti immagine) con 3 byte per pixel, quindi 1200 x
900 x 3 = 3.240.000 byte, circa 3 Mega pixel,
24 immagini al secondo significa 24 * 3M = 72M,
90 minuti = 90*60 secondi = 5400 secondi quindi
in totale 5400 * 24 immagini, 129.600 immagini e
quindi 3.240.000 * 129.600 = 419.904.000.000
= 420 G byte (video non compresso)...
rimane sempre l' esigenza di salvare grandi quantita' di
dati in uno spazio (con un numero di byte) il piu'
piccolo possibile, esigenza di
codifica dati efficiente = compressione dei dati
breve cenno di questo aspetto nella parte seguente che riguarda i codici
65
I N F O R M A Z I O N E - cenni
fine " ... informazione (cenni) "
segue:
.
CODICI
codici
argomenti presentati:
codici, rappresentazione, dati
codifiche binarie
codice ASCII
codice UNICODE
codici a controllo di errore
codici a correzione di errore
bibliografia
esercizi
66
codici e dati
67
definizione:
Dati =
" fenomeni fisici scelti per convenzione
al fine di rappresentare
informazioni su fatti o idee "
La stessa informazione (fatto, idea) puo' essere
rappresentata da dati diversi;
diremo un valore l'insieme delle rappresentazioni
della stessa informazione (fatto,idea).
Codice = " un sistema convenzionale di regole
per rappresentare informazioni"
codici e dati
68
Ogni dispositivo (supporto fisico) capace di assumere
due o piu' stati distinti
puo' essere usato per rappresentare dei dati :
bastoncini intagliati, spaghi annodati,
pietre o ossa scolpite, tavolette d’argilla,
pergamena, carta stampata,
carta perforata, interruttore,
anello di ferrite, carica elettrostatica,
stato di un circuito bistabile,
nastro magnetico, disco ottico, ... ecc)
codici e dati
69
Ogni dispositivo (supporto fisico) capace di assumere
due o piu' stati distinti
puo' essere usato per rappresentare dei dati :
La rappresentazione di un dato con un codice
e' alla base dei sistemi di scrittura e di numerazione
la rappresentazione delle informazioni e' molto antica
e ha piu’ di 6000 anni ...
il passaggio dagli ideogrammi ad un sistema alfabetico
con un numero di simboli minore avviene circa 1000
anni prima di Cristo (ambiente egiziano-fenicio), poi
adottato dai greci e in seguito dai latini ...
codici e dati
70
esempio: il dato " 1.a lettera dell'alfabeto, "A" " :
noi siamo abituati a considerare
il simbolo (il carattere) “A” e la "vocale a"
(vocale del sistema fonetico della lingua italiana)
come equivalenti - ma non sono la stessa cosa:
"vocale a" (1.a lettera dell’alfabeto italiano) = dato
“A”
= un codice per il dato “a”
per lo stesso dato [vocale a]
abbiamo diversi codici:
codici e dati
per lo stesso dato "vocale a" abbiamo diversi codici:
.
codice del carcerato: un colpo per a,
due per b, tre per c ... supporto qualunqe,
equivale al numero uno in sistema unario
a  simbolo che rappresenta la lettera a,
codice grafico esterno [al calcolatore]
"aleph"origine egizia/fenicia/greca/latina..
sorgente-destinatario: persona-persona,
supporto: carta;
. - codice Morse, usa combinazioni di tre
simboli (punto,linea e spazio), supporto:
carta/ conduttore elettrico;
71
codici e dati
72
ripeto .. dato "1.a lettera dell'alfabeto, ‘a’ " , diversi codici:
.
a 
.-
codice del carcerato: un colpo per a;
codice grafico esterno, supporto carta;
cod. Morse, supporto carta/conduttore elettrico
ancora:
simbolo dell’alfabeto sillabico hiragana giapponese
ancora:
0100 0001 ASCII - codice interno al calcolatore, binario,
destinato ad una macchina (supporti vari),
73
codici e dati
es.di codifica:
dati 4 simboli - es.:
*
#
@
?
posso codificarli con un altro insieme di simboli
prestabilito, ad es. con lettere, o cifre, o altro:
codifica con lettere:
* con A, # con B, @ con C, ? con D,
codifica con cifre decimali:
*
1
oppure: *
113
#
2
#
224
@
3
@
557
?
4
?
668
74
codici e dati
ancora, dati 4 simboli - es.:
* # @ ?
posso codificarli utilizzando due simboli, x e y
ad esempio:
oppure:
oppure ancora:
*
xxx
xxyyy
xy
#
xxy
yxxyy
xyy
@ xyx
yyxxy
xyyy
?
xyy
yyyxx
x
le prime due colonne sono una codifica con codici a
lunghezza costante, la terza con codici a lunghezza
variabile
75
codici e dati
ancora, dati 4 simboli - es.:
* # @ ?
posso codificarli utilizzando un solo simbolo,
ad esempio:
*
x
#
xx
@
xxx
?
xxxx
(codifica con codici a lunghezza diversa!)
76
codici e dati
il calcolatore usa la codifica binaria, con DUE SOLI
SIMBOLI - perche’ i supporti fisici (memorie)
a 2 stati soli sono piu’ sicuri !!
acceso/spento;
c’e’corrente / non c’e’corrente;
magnetizzato N-S / magnetizzato S-N;
perforato / non perforato;
- da qui l’interesse per l’algebra della logica
a due valori falso/vero o zero/uno,
- da qui l’uso dei codici a due valori 0/1 = codici binari
dati 4 simboli
es.di codifica a 2 valori
ancora
*
00
000
#
01
011
@
10
101
?
11
110
77
codici e dati
nella codifica binaria, si usano due soli simboli,
di solito indicati con
0 zero o falso
1 uno o vero
usati anche per rappresentare numeri in base due,
detti bit, da binary digit o cifra binaria
il calcolatore usa al suo interno solo codici
a due valori 0/1 detti codici binari
ad esempio per tre simboli :
un es.di codifica binaria:
#
10
@
1
&
101
per cui il dato: # # # @ & & @@@ # @ #
si rappresenta: 10 10 10 1 101 101 1 1 1 10 1 10
78
codici e dati
per codificare 4 simboli in binario posso scegliere
moltissime soluzioni: ( A B C D sono i 4 simboli
da rappresentare) ... esempi di codici:
1) A
B
C
D
1
11
111
1111
2) A
B
C
D
101
1001
10001
100001
3) A
B
C
D
11000
01100
00110
00011
4) A
B
C
D
01
10
11
00
la codifica 4) (numero simboli binari fisso) e’ la piu’
economica, il numero di bit (due) e'uguale al
contenuto di informazione di un simbolo (su 4)
codici e dati
79
nota: per dati non equiprobabili esistono codici a
lunghezza variabile che consentono un risparmio nel
numero medio di bit usati, ovvero sono piu' efficienti;
i codici a lunghezza variabile tengono conto della
frequenza dei simboli nel dato: simboli piu' frequenti
avranno un codice piu' breve (circa come scelto da
Morse per il suo codice telegrafico);
es.: codice Hufmann, non trattato qui.
80
codici e dati
lo schema di codifica piu' usato e' a numero di bit fisso:
un bit per due simboli:
A
due bit per tre A 00
o per quattro
simboli
A 00
B 01
C 10
B 01
C 10
B 001
E 100
C 010
tre bit
per cinque,
sei, sette o
otto simboli,
A 000
D 011
0
B
1
D 11
quattro bit per nove..sedici simboli, cinque per 17..32
simboli, eccetera ...
81
codici e dati
devo usare almeno due bit per quattro simboli,
ma posso scegliere come associare simbolo-codice
in molti modi:
un modo:
A
oppure:
A
oppure:
A
oppure ancora: A
ecc
00
11
10
01
B
B
B
B
01
00
11
11
C
C
C
C
10
10
00
00
D
D
D
D
11
01
01
10
Quante codifiche con n bit (n fisso) per K simboli?
(deve essere n >= log2(K) ) - qui n=2, K=4
82
codici e dati
Quante codifiche con n bit (n fisso) per K simboli?
(deve essere n >= log2(K) ) se K=4, n=2,
posso associare i 4 simboli diversi A, B, C, D
ai 4 codici diversi 00, 11, 01, 10 in 4 ! modi diversi
(uno dei 4 codici per A, uno dei tre rimanenti per B, uno dei
due rimanenti per C, il codice per D rimane fissato), quindi vi
sono 4 * 3 * 2 * 1 modi per associare 4 codici a 4 simboli,
4 * 3 * 2 * 1 = 4 ! = 4 * 6 = 24
di seguito sono riportati 12 codici (dei 24 possibili):
A
B
C
D
00
01
10
11
1
00
01
11
10
2
00
10
01
11
3
00
10
11
01
4
00
11
01
10
5
00
11
10
01
6
01
00
10
11
7
01..01
00..11
11..10
10..00
8
12
10..10
01..11
00..00
11..01
13 18
11..11
01..00
10..10
11..01
19 24
codici e dati
83
Quante codifiche con n bit (n fisso) per N simboli?
(n >= log2(N) )
ad es. per codificare 25 simboli (alfabeto inglese) devo
usare 5 bit (4 bit arrivo fino 16, 5 bit arrivo fino 32),
( ho 32 * 31 * 30 * 29 * 28 .. * 8 * 7 possibili scelte per la codifica )
Normalmente si sceglie l’accoppiamento “per ordine”:
ordino i simboli (convenzione: ordine alfabetico),
ordino i codici binari (convenz.: numerazione binaria),
poi associo i simboli ordinati ai codici ordinati;
es. per quattro simboli: A B C D <--> 00 01 10 11
quindi A = 00, B = 01, C = 10, D = 11
codici e dati
numerazione binaria (vedremo di piu’ tra poco):
decimale binario(in base due, cifre 0,1)
0
0
1
1 (uno= due alla zero)
2
10 (due, = due alla uno)
3
11 (in base due, cioe’ due(=10) piu’ 1)
4
100 (quattro = due alla due)
5
101 (cinque=quattro+uno)
6
110 (sei = quattro + due)
7
111 (sette=quattro+due+uno)
8
1000 (otto = due alla tre)
9
1001 (nove=8+1)
10
1010 (dieci = 8+2) ecc
84
85
codici e dati
un bit per due simboli:
A 0
B 1
due bit per tre o quattro simboli:
A 00
B 01
C 10
A 00
B 01
C 10
D 11
tre bit per cinque, sei, sette o otto
simboli:
A
A
A
A
000
000
000
000
B
B
B
B
001
001
001
001
C
C
C
C
010
010
010
010
D
D
D
D
011
011
011
011
E 100
E 100 F 101
E 100 F 101 G 110
.. F 101 G 110 H 111
86
codici e dati
quattro bit per codificare da 9 a 16 simboli:
A 0000 B 0001 C 0010 D 0011
E 0100 F 0101 G 0110 H 0111
I 1000
(1..4)
(5..8)
(9)
...
...
A
E
I
M
0000
0100
1000
1100
B
F
J
N
0001
0101
1001
1101
C
G
K
O
0010
0110
1010
1110
D
H
L
P
0011
0111
1011
1111
(1..4)
(5..8)
(9..12)
(13..16)
codici e dati
87
con 5 bit posso rappresentare fino 32 simboli
(vecchio codice per telescrivente Baudot)
con 6 bit -> 64 simboli
(vecchio codice calcolatori BCD),
con 7 bit -> 128 simboli
(codice ASCII di 32 + 96 caratteri)
con 8 bit -> 256 simboli (codice ASCII esteso)
quanti bit per rappresentare i 10.000 simboli della
scrittura cinese?
(10 bit: 1024, 12 bit: 4096, 14 bit: 16384) => almeno 14
codici e dati
con 7 bit -> 128 simboli
(codice ASCII di 32 + 96 caratteri)
con 8 bit -> 256 simboli (codice ASCII esteso)
con 16 bit -> 32768 simboli (unicode)
(e per un po’ basta)
88
89
codici e dati
curiosita' storica ... due supporti dati ormai in disuso:
1) il nastro perforato (uno dei primi supporti dati usato nel
telaio automatico del 1801 di Joseph Jacquard, Lyon) per
"registrare" o memorizzare un dato = perforare dei codici
binari su nastro; in figura, * sta per perforazione)
es. codice di A: 01000 001 (41 esadecimale)
es. codice di C: 11000 011 (43 esadecimale)
0 1 2 3 4 5 6 7 8 9
*
*
* *
*
A B C D E F G H I ... Y Z
*
*
*
*
*
* *
* *
*
* * * *
* * *
. . . . . . . . . . . . . . . . . . .
* *
* * * * * * * *
* * * * * * * * *
* * * * * *
* *
*
*
*
* *
*
*
*
*
*
. . . . . . .
* *
* *
* * *
* *
* *
1
2
3
4
5
6
7
8
codici e dati
90
2) scheda perforata (inventata da Hollerith nel 1885, la
ditta di Hollerith nata agli inizi del secolo poi negli anni
20 divento’ una ditta di macchine "meccanografiche" o
elettrocontabili ... l' IBM)
La scheda perforata e' andata in disuso con l'avvento
dei sistemi in multiutenza (terminali alfanumerici, anni
70..) e dei personal (TRS, Commodore, Apple, anni
77..). a Trieste esistevano un lettore ed un perforatore
di schede ancora nel 1985, il lettore di schede e’
rimasto in uso fino al 90...
oggi e'possibile leggere schede perforate solo in una
macchina di un museo di informatica...
91
codici e dati
scheda perforata: codice a 12 bit, 80 caratteri (colonne)
il codice di A: 10 01000 00000, (qui sotto, * sta per
il codice di B: 10 00100 00000
posizione perforata)
0 1 2 3 4 5 6 7 1 9
A
B
*
1
2
3
4
5
6
7
8
9
A
B
0
*
2
3
4
5
6
7
8
9
A
B
0
1
*
3
4
5
6
7
8
9
A
B
0
1
2
*
4
5
6
7
8
9
A
B
0
1
2
3
*
5
6
7
8
9
A
B
0
1
2
3
4
*
6
7
8
9
A
B
0
1
2
3
4
5
*
7
8
9
A
B
0
1
2
3
4
5
6
*
8
9
A
B
0
1
2
3
4
5
6
7
*
9
A
B
0
1
2
3
4
5
6
7
8
*
A
B
0
1
2
3
4
5
6
7
8
9
A B C D E F G H I J K
W X Y Z
*
B
0
*
2
3
4
5
6
7
8
9
A
B
*
1
2
3
4
5
*
7
8
9
*
B
0
1
*
3
4
5
6
7
8
9
*
B
0
1
2
*
4
5
6
7
8
9
*
B
0
1
2
3
*
5
6
7
8
9
*
B
0
1
2
3
4
*
6
7
8
9
*
B
0
1
2
3
4
5
*
7
8
9
*
B
0
1
2
3
4
5
6
*
8
9
*
B
0
1
2
3
4
5
6
7
*
9
*
B
0
1
2
3
4
5
6
7
8
*
A
*
0
*
2
3
4
5
6
7
8
9
A
*
0
1
*
3
4
5
6
7
8
9
A
B
*
1
2
3
4
5
6
*
8
9
A
B
*
1
2
3
4
5
6
7
*
9
A
B
*
1
2
3
4
5
6
7
8
*
codici e dati
Ritorneremo in seguito
sui supporti dati
oggi piu' usati,
ovvero
i dischi (di vario genere ... )
i nastri magnetici
92
93
codici e dati
il codice
ASCII
(leggi: eski... ma anche asci)
American Standard Code for Information Interchange
codici e dati
94
il codice ASCII per rappresentare un testo semplice:
32 codici di controllo (corrisp.ai numeri da 0 a 31)
96 codici “stampabili”, sono i simboli (caratteri)
stampabili del codice ASCII, lettere (maiuscole,
minuscole, alfabeto inglese), cifre (da 0 a 9), simboli vari
(aritmetica, punteggiatura, parentesi, ecc)
i codici da 128 a 255 hanno significati diversi a seconda
della scelta dell'utente.
di seguito sono riportati tutti i codici ASCII , a scopo
informativo e di consultazione, (NON da memorizzare)
un anticipo sui codici numerici: il numero 10 ha diverse codifiche 95
decimale: ottale
0
0
1
1
2
2
...
6
6
7
7
8
10
9
11
10 12
11 13
..
14 16
15 17
esadecimale
0
1
2
binario
0
1
10
6
7
8
9
A
B
110
111
1000
1001
1010
1011
E
F
1110
1111
codici e dati - tabella ASCII - cont.
96
American Standard Code for Information Interchange =
codice ASCII: codice a 7 bit per rappresentare un dato, es.:
“riganuova” (NON stampabile) codice num. 10, esadecim. A
vediamo alcuni codici:
“ “ = codice numero 32, esadecimale: 20 binario: 010 0000
“6” = codice numero 54, esadecimale: 36 binario: 011 0110
“A”= codice numero 65, esadecimale: 41 binario: 100 0001
“a”= codice numero 97, esadecimale: 61 binario: 110 0001
“}”= codice numero 125, esadecimale: 7D binario: 111 1101
97
codici e dati - tabella ASCII - cont.
i primi 32 codici ASCII (da 0 a 31)
sono codici NON stampabili, usati per controllo es.: 8 = back space, 10 = line feed, 13 = carriage return ecc
parte codici controllo, da 0 a 31, in decimale / esadec:
0
4
0
4
NUL
EOT
1
5
1
5
SOH
ENQ
2
6
2
6
STX
ACK
3
7
3
7
ETX
BEL
8
8
BS
9
9
HT
10
A
LF
11
B
VT
12
C
FF
13
D
CR
14
E
SO
15
F
SI
16
20
10
14
DLE
DC4
17 11
21 15
DC1
NAK
18 12
22 16
DC2
SYN
19
23
13
17
DC3
ETB
24
28
18
1C
CAN
FS
25 19
29 1D
EM
GS
26 1A
30 1E
SUB
RS
27
31
1B
1F
ESC
US
codici e dati - tabella ASCII - cont.
98
nota: per ottenere uno di questi caratteri speciali con
codice 0..31 su una tastiera [di solito] si deve premere
assieme il tasto CTRL piu' un altro carattere, es:
3 (EndOfText=CTRL-C);
8 (BackSpace=CTRL-H);
9 (TABula);
10 (LineFeed=caporiga);
12 (FormFeed=capopagina); 13 (Carriage Return=
RitornoCarr);
26 (EndOfText in MSDOS); 27 (escape)..
alcuni caratteri speciali corrispondono ad un tasto
singolo:
BackSpace [ 8 ],
Esc [ 27 esad. 1B ],
Return [ 13 esad. D ],
...
codici e dati - tabella ASCII - cont.
di seguito e’ riportata
la tabella dei codici ASCII
completa
(da 32 a 127, i codici da 0 a 31 riportati prima)
...
99
100
codici e dati - cont. codici ASCII - codici da 32 a 79 :
32
36
40
44
20
24
28
2C
spaz.
$
(
,
33
37
41
45
21
25
29
2D
!
%
)
-
34
38
42
46
22
26
2A
2E
"
&
*
.
35
39
43
47
23
27
2B
2F
#
'
+
/
48
52
56
60
30
34
38
3C
0
4
8
<
49
53
57
61
31
35
39
3D
1
5
9
=
50
54
58
62
32
36
3A
3E
2
6
:
>
51
55
59
63
33
37
3B
3F
3
7
;
?
64
68
72
76
40
44
48
4C
@
D
H
L
65
69
73
77
41
45
49
4D
A
E
I
M
66
70
74
78
42
46
4A
4E
B
F
J
N
67
71
75
79
43
47
4B
4F
C
G
K
O
(cont.pag.seg.)
es. lettura tabella:
! = codice n.ro 33, esadec. 21, binario 010 0001
C = codice n.ro 67, esadec, 43, binario 100 0011
101
codici e dati - cont. codici ASCII - codici da 80 a 127 :
80
84
88
92
50
54
58
5C
P
T
X
\
81
85
89
93
51
55
59
5D
Q
U
Y
]
82
86
90
94
52
56
5A
5E
R
V
Z
^
83
87
91
95
53
57
5B
5F
S
W
[
_
96
100
104
108
60
64
68
6C
`
d
h
l
97
101
105
109
61
65
69
6D
a
e
i
m
98
102
106
110
62
66
6A
6E
b
f
j
n
99
103
107
111
63
67
6B
6F
c
g
k
o
112
116
120
124
70
74
78
7C
p
t
x
|
113
117
121
125
71
75
79
7D
q
u
y
}
114
118
122
126
72
76
7A
7E
r
v
z
~
115
119
123
127
73 s
77 w
7B {
7F DEL
es. lettura tabella:
u = codice n.ro 117, esadec. 75, binario 111 0101
~ = codice n.ro 126, esadec. 7E, binario 111 1110
=> ancora codice ASCII, ... tabella completa :
102
!
+
5
32
33 "
43 ,
53 6
34 #
44 54 7
35 $
45 .
55 8
36 %
46 /
56 9
37 &
47 0
57 :
38 '
48 1
58 ;
39 (
49 2
59 <
40 )
50 3
60 =
41 *
51 4
61 >
42
52
62
?
I
S
63 @
73 J
83 T
64 A
74 K
84 U
65 B
75 L
85 V
66 C
76 M
86 W
67 D
77 N
87 X
68 E
78 O
88 Y
69 F
79 P
89 Z
70 G
80 Q
90 [
71 H
81 R
91 \
72
82
92
] 93 ^ 94
g 103 h 104
q 113 r 114
{ 123 | 124
_ 95 ` 96 a 97 b 98 c 99 d 100 e 101 f 102
i 105 j 106 k 107 l 108 m 109 n 110 o 111 p 112
s 115 t 116 u 117 v 118 w 119 x 120 y 121 z 122
} 125 ~ 126
ricorda: il codice ASCII originale prevede 7 bit di
codifica, quindi 128 possibili simboli diversi: i codici da 0
a 31 sono caratteri di controllo, non stampabili, i 96
codici da 32 a 127 corrispondono a caratteri stampabili.
codici e dati
103
il codice ASCII prevede 8 bit;
inizialmente l’ottavo bit assumeva sempre un significato
di controllo parita’ (vedremo cosa significa)
oggi piu’ spesso il codice a 8 bit e’ un ASCII esteso,
dove si riservano dei codici per caratteri / simboli
speciali,
ad es alcune lettere greche, simboli matematici ecc,
e codici per caratteri nazionali, che pero’ cambiano
significato a seconda della nazione (e quindi cambia
tastiera...)
ad es: ò oppure ç oppure ž ...
104
seguono cenni sul
CODICE UNICODE
vedi su rete
http://www.unicode.org/
UNICODE - un codice “per tutti” a 16 bit
105
il codice UNICODE (ISBN 0-201-56788-1, 1990)
usa 16 bit per rappresentare un simbolo, e quindi puo’
rappresentare 65000 simboli diversi...
i primi 256 codici sono il set ASCII a 8 bit Latin-1,
che quasi coincide per i primi 128 codici con il ASCII a 7 bit;
vi sono vari codici Latin-extended esistono centinaia di lingue che usano le lettere latine, ciascuna
con varie modifiche o segni modificatori come ¨ ˆ ° · ´ _
gli altri codici sono usati per rappresentare una gran quantita’
di simboli usati in varie lingue del mondo, raggruppando dove
possibile (ad es. i set latini, i set cirillici, i set arabi) o definendo
codici e regole per parti di caratteri piu’ complicati ( i set che si
basano sui simboli cinesi )
UNICODE - un codice “per tutti” a 16 bit
106
ad es.:
alfabeti arabo, armeno, bengali, cirillico, copto, devanagari,
ebraico, greco, hiragana, katakana, koreano, ecc
(vi sono piu' di 2000 lingue "riconosciute" ... )
anche i simboli per le cifre decimali delle varie lingue sono
talvolta diversi
....
infine sono definiti dei set di simboli piu’ usati (valute, frecce,
simboli matematici, “dingsbat” ecc) cioe’ molti set di
ideogrammi standardizzati
(da http://www.unicode.org/ , e
libri ad es. “The Java Programming Language” di K.Arnold e
J.Gosling, 1996):
107
..
CODICI A CONTROLLO DI ERRORE
. . .
codici ed
errori
contenuto:
codici e trattamento dell'errore
legame tra ridondanza/efficienza e
il controllo di errore
* codici a controllo di errore o
a segnalazione automatica di errori:
raddoppio, parita', ASCII a 8 bit,
controllo su blocchi piu' grandi
distanza tra due valori di un codice
* recupero automatico di errori
codici triplicati, controllo incrociato
108
109
codici e dati
definizione:
dato un codice di rappresentazione di k simboli diversi,
(event. non equiprobabili, con codifiche di lunghezza
eventualmente diversa),
si definiscono:
efficienza
e
I med
= -------N med
r
=
e
ridondanza
1 - e
110
esempio: codifica dei 4 simboli: A, B, C, D
1) codice: A 00
B 11
C 01
D 10
<<====
I med = 2 bit (simboli equiprobabili)
N bit medio per simbolo: 2
efficienza: I med / N med = 2/2 = 1,0 <-2) codice: A 111
B 11
C1
D 1111 <<====
I med = 2 bit (simboli equiprobabili)
N bit medio per simbolo: (1+2+3+4)/4 = 10/4 = 2,5
efficienza: I med / N med = 2/2,5 = 0,8 <--
111
continua esempio codifica di 4 simboli: A, B, C, D
3) codice:
A 0001
B 0010
C 0100
D 1000
<<====
I med = 2 bit (simboli equiprobabili)
N bit medio per simbolo: 4
efficienza: I med / N med = 2/4 = 0,5 <--
codici ed
errori
112
Problema dell' errore:
un dispositivo (un supporto fisico) puo' dar luogo a
errori di trasmissione/di registrazione, e' inevitabile,
anche se la tecnologia fornisce sistemi sempre piu'
affidabili.
e' essenziale che il calcolatore stesso
- in modo del tutto automatico controlli e quindi segnali la presenza di un errore e, se possibile, lo corregga
Esistono codici che consentono * la rilevazione
e anche * la correzione automatica di errori.
codici ed
errori
113
rilevazione di un errore: dato di partenza (37 caratteri):
IL PRESIDENTE E' UN GRANDE FILANTROPO
trasmesso con codice ASCII, 7 bit/carattere,
in tutto 7 * 37 = 259 bit
contenuto d'informazione (circa, ipotizzo un
dizionario di 16000 parole, quindi 14 bit per
parola)
14(bit) * 6(parole) = 84 bit
efficienza I / N = 84/259 = 0,33
(prescindiamo dal contenuto di informazione "vero" di un
messaggio di questo tipo ;-)
codici ed
errori
114
rilevazione di un errore: dato di partenza (37 caratteri):
IL PRESIDENTE E' UN GRANDE FILANTROPO
codice ASCII, numero bit usati 7 * 37 = 259 bit, contenuto
d'informazione 14*6 = 84 bit, efficienza I / N = 84/259 = 0,33
se c'e' un errore in registrazione (o di trasmissione)
allora uno dei caratteri trasmessi viene ricevuto errato,
es:
IL PRESIDENTE E' UN GRANDE FILANTRZPO
L'errore viene rilevato e anche corretto: la lettera Z
viene facilmente individuata come errore.
[ qui siamo noi a fare da “correttori automatici” ]
codici ed
errori
115
2) codifica piu' efficiente: utilizzo un dizionario
(a disposizione sia del sistema sorgente sia del ricevente)
di 16.000 parole; per spedire una parola bastano 14 bit
(2^14 = 16384), in tutto sei parole 6*14 = 84 bit (invece
dei 37 * 8 = 296 nella codifica di prima)
il dato
IL PRESIDENTE E' UN GRANDE FILANTROPO
codificato [ parola -> numero ] diventa:
6173 11410 4003 15501 5026 4897
-> Suppongo ora che si verifichi un errore,
ad es. invece di 4897 ricevo 9897 ..... decodifico ....
codici ed
errori
116
2) codifica efficiente con dizionario di 16.000 parole,
messaggio codificato (6*14= 84 bit invece di 296)
6173 11410 4003 15501 5026 4897
se si verifica un errore, ad es. invece di 4897 ricevo
9897, ottengo:
6173 11410 4003 15501 5026 9897
che interpretato con lo stesso dizionario da':
IL PRESIDENTE E' UN GRANDE MACACO
L'errore NON si rileva (tantomeno si corregge)
=> un codice molto efficente
NON permette la rilevazione degli errori !!
117
ancora un esempio:
l’infochimica vi insegnera’come iniziare una nuova vita
[testo di 9 parole in tutto 55 caratteri]
codifica: solito dizionario di 15000 parole “numerate”
della lingua italiana, da dove trovo i numeri
progressivi delle parole. Per ogni parola trovo un
numero (codice) :
come
infochimica
iniziare
insegnera’
vita
3021
7953
7977
8042
14903
l’
nuova
una
vi
8411
10766
13311
14850
118
l’infochimica vi insegnera’come iniziare una nuova vita
[9 parole in tutto 55 caratteri, quindi in codice ASCII 55x8 = 440 bit ]
codifica: con dizionario di 15000 parole “numerate”
come
3021
infochimica 7953
iniziare
7977
insegnera’ 8042
l’
nuova
una
vi
8411
10766
13311
14850
vita 14903
quindi il messaggio codificato diventa:
8411 7953 14850 8042 3021 7977 13311 10766 14903
invece di 55 caratteri a 8 bit = 440 bit testo ASCII,
ho ora 9 numeri da 14 bit = 126 bit !
risparmio per un fattore di 3,5 !
... ma ...
codici ed errori (cont. es.)
119
messaggio originale (ASCII: 55 caratteri x 8 bit = 440 bit)
“l’infochimica vi insegnera’come iniziare una nuova vita”
codifica: sost. alle parole i numeri progressivi del dizionario:
come 3021
... iniziare 7977 una
13311
insegnera’ 8042 vi
14850
vita 14903
il messaggio codificato (9 numeri da 14 bit = 126 bit)
8411 7953 14850 8042 3021 7977 13311 10766 14903
con un errore (es. canale disturbato, o memoria con errori)
ricevo/leggo rispettivamente nelle due codifiche:
“l’infochimica vi insegnera’come inwziare una nuova vita”
“8411 7953 14850 8042 3021 7677 13311 10766 14903”
caso di un errore:
120
a) messaggio spedito in ASCII ( 440 bit), ricevo:
“l’infochimica vi insegnera’come inwziare una nuova
vita”
-->> mi accorgo dell’errore,
inwziare NON e’ una parola legale!
qui anche riesco a correggere !!
121
b) mess. codificato in numeri, (9 num. da 14 bit = 126 bit)
ricevo: ( 7677 invece di 7977)
“8411 7953 14850 8042 3021 7677 13311 10766 14903”
decodifico con l’aiuto del dizionario (parole numerate):
come
finire
infochimica
iniziare
insegnera’
3021
7677
7953
7977
8042
l’
nuova
una
vi
vita
8411
10766
13311
14850
14903
MESSAGGIO (con errore) DECODIFICATO diventa:
l’infochimica vi insegnera’come finire una nuova vita
-->> non mi accorgo dell’errore!
codici ed
errori
dall'esempio visto segue che
* per consentire
la rilevazione ("controllo") di un errore
di trasmissione o di registrazione
* devo usare un codice ridondante cioe' tale che
NON TUTTE le combinazioni di bit sono lecite
ovvero non tutti i codici rappresentano un dato.
122
codici ed
errori
ricordiamo la definizione dell’ efficienza; il codice
A 00
B 01
efficienza: e = Imed / Nmed = 2/2 = 1
C 10
..
D 11
ridondanza r = 1 - e = 0
A
B
C
D
000
001
010
101
efficienza: e = Imed / Nmed = 2/3 = 0,66
..
ridondanza r = 1 - e = 0,33
123
codici ed
errori
124
Es: 4 simboli, A B C D - codifica:
1) non ridondante: uso il minimo di bit
A 00 tutti i codici di 2 bit sono legali ->
B 01 nessuna ridondanza, massima efficienza, MA
C 10 non c' e' possibilita' di rilevare gli errori
D 11 ad es: il dato: DABAC
codificato e’ 11 00 01 00 10
se c'e' un errore allora ricevo: 11 00 11 00 10
da cui
decodifico: DADAC
(... non mi accorgo dell'errore !! )
125
Es: 4 simboli, A B C D
2) codifica ridondante:
uso piu’ bit del minimo necessario
A 000 non tutti i codici di 2 bit sono legali, c'e'
B 001 ridondanza, --> posso rilevare errori
C 010 qui uso 3 bit per 4 simboli...
D 101 ad es. il dato: DABAC codifica:
101 000 001 000 010
se ho un err. al 10.o bit ricevo: 101 000 001 100 010 ->
decodifica:
DAB?C
ma 100 e'illegale ->
mi accorgo dell'errore
codici ed
errori
126
attenzione: non tutti i codici ridondanti vanno bene
A
B
C
D
000
001
010
101
questo codice a 3 bit e’scelto un po' a caso...
come vedremo subito,
non e' un buon codice perche'
... in alcuni casi non mi accorgo
dell’errore ... vediamo due esempi:
come visto, il codice permette di individuare questo
errore: dato DABAC:
101 000 001 000 010
errore al 10.o bit leggo:
101 000 001 100 010
--> in decodifica ho il codice 100 illegale -> rilevo
l’errore, ottengo DAB?C
MA in altri casi questo stesso codice non va bene:
codici ed
errori
continua... non tutti i codici ridondanti vanno bene A 000
come visto, con questo codice
B 001
talvolta posso accorgermi
C 010
di un errore, ma ...
D 101
... secondo esempio:
2) caso: stesso dato DABAC
se ho un err. al 12.o bit (prima era al 10.o):
DABAC codifica: 101 000 001 000 010
ricevo:
101 000 001 001 010 -->
nella decodifica non rilevo l’errore ! leggo ...
DABBC - il codice 001 e' legale->
127
codici ed
errori
128
3) invece del codice senza ridondanza 4 simboli, 2 bit:
A 00 B 01 C 10 D 11
uso il codice:
A
B
C
D
0000
0011
1100
1111
qui raddoppio i bit della codifica iniziale
-> il codice e' meno efficiente (vedi sotto)
ma posso rilevare piu' errori rispetto il
codice precedente - questo codice rileva
un singolo errore in posizione qualunque!
efficienza del codice: e= Imed / Nmed = 2/4 = 0,5
..
ridondanza r = 1 - e = 0,5
codici ed
errori
129
ricordiamo: un raddoppio di bit permette il controllo
di errore; invece del codice a efficienza 1,
A 00 B 01 C 10 D 11 uso un codice:
A 0000 questo codice (con num. bit doppio) ha
B 0011 efficienza: e = Imed / Nmed = 2/4 = 0,5
C 1100 ..
D 1111 ridondanza r = 1 - e = 0,5
rilevo un singolo errore in qualunque posizione ...
ma ... e’ un codice troppo ridondante!
come deve essere costruito il codice per poter
rilevare sempre un singolo errore, senza essere
troppo ridondante?
codici ed
130
errori
definiamo la distanza tra due valori di un codice
come il numero di bit da cambiare per passare da un
valore all’altro, ad es. per il codice
A011
B010
C 111
D 001
abbiamo:
dist(A,B) = 1, dist(A,C) = 1, dist(A,D) = 1
dist(B,C) = 2, dist(B,D) = 2, dist(C,D) = 2
se c’e’ un errore nel dato A, e cioe’
scrivo (trasmetto) il dato 011 -> ma poi
leggo (ricevo)
il dato 010 ->
ottengo il codice di B, che e' un codice legale [qui vi
sono coppie di valori (legali) X,Y con dist(X,Y)=1 ]
quindi non mi accorgo dell’errore!
codici ed
errori
131
distanza tra due valori di un codice = il numero di bit
da cambiare per passare da un valore all’altro:
se ho: A 0 1 1 B 0 1 0 C 1 1 1 D 0 0 1
allora :
dist(A,B)=1, dist(B,C)=2, dist(B,D)=2, dist(C,D)=2
puo’ verificarsi: trasmetto il dato A=011, ricevo il
codice 010 (legale!) = B -> ottengo il dato B
[qui vi sono coppie di valori (legali) X,Y con dist(X,Y)=1]
un codice con distanza minima tra due codici legali
uguale a 1 non permette la segnalazione di errore,
perche’ un errore puo’ portare una stringa di bit legale
in un’altra stringa di bit legale - perche’ vi sono dati
diversi con codifiche distanti di 1 solo bit.
codici ed
errori
132
ricorda: la distanza tra due valori di un codice e' il numero
di bit da cambiare per passare da un valore all’altro; es:
A011
B010
C 111
D 001
dist(A,B) = 1, dist(A,C) = 1, dist(A,D) = 1
dist(B,C) = 2, dist(B,D) = 2, dist(C,D) = 2
NON deve essere possibile che un errore possa portare
una stringa di bit legale X in un’altra stringa di bit
legale (diversa) Y:
per avere la segnalazione di errore un codice deve
avere il valore della distanza maggiore o uguale a 2
per tutte le coppie X e Y di valori legali del codice
distmin(X,Y)>=2
codici ed
errori
133
nota:
il codice con i bit raddoppiati NON si usa, perche’ la
probabilita’ di un errore in un dato manipolato
(trasmesso, memorizzato...) da un calcolatore e’ piccola,
e quindi si usano codici con meno ridondanza!
Se la probabilita’ di errore e’ ad es. 10E-6 non usero’ un
codice con 50% di ridondanza, ma con molto meno.
Nei sistemi vecchi di trasmissione e registrazione dati
l’affidabilita’ era minore, la probab. di errore piu’
grande, si usava il codice ASCII a 7 bit + 1 bit di
controllo di errore (ridondanza di 1/8)...
codici ed
134
errori
un sistema semplice per avere un codice a controllo di
errore e' l' aggiunta di 1 bit al dato, tale che la
somma dei bit del dato piu' il bit aggiunto sia pari:
codici a controllo di parita'.
per 4 simboli (il punto evidenzia il bit di controllo) :
A 00.0
B 01.1
C 10.1
D 11.0
con tale codifica il dato B B A D
diventa: 011 011 000 110
se ho un errore (ad es. nel 6.o bit): 011 010 000 110
rilevo l'errore nel secondo carattere,
perche’ la terna 010 e’ illegale;
codici ed
errori
135
nota: il codice senza ridondanza era:
A
B
C
D
00
01 efficienza: e = Imed / Nmed = 2/2 = 1
10 ..
11 ridondanza r = 1 - e = 0
il codice con aggiunto un bit di parita' ha:
A 000
B 011
C 101
D 110
efficienza: e = Imed / Nmed = 2/3 = 0,66
..
ridondanza r = 1 - e = 0,33
un po' meglio del raddoppio ... ma non tanto (non si
usa: il controllo e' fatto su "pacchi" di dati piu' grandi)
codici ed errori
136
nota: ricordiamo il codice ASCII con controllo parita’:
se due codici (legali) differiscono di 1 bit, ad es.:
a = 110 0001, A = 100 0001,
aggiungo un bit di parita’, i due codici differiscono di due bit:
a = 110 0001 1,
A = 100 0001 0
se differiscono di due bit, il bit di parita’ e’lo stesso, e la
distanza e’ sempre di due bit:
a = 110 0001, A = 000 0001,
aggiungendo un bit di parita’ la distanza rimane due:
a = 110 0001 1,
A = 000 0001 1
con questa codifica posso sempre rilevare la presenza di un
singolo errore !
==>> CODICE A CONTROLLO DI ERRORE
codici ed
137
errori
codice ASCII a 7 bit piu' un bit di parita':
a
110 0001 1
k
110 1011 1
A
100 0001 0
l'ottavo bit aggiunto e' tale che la somma di tutti i bit e' pari.
spedisco questo dato e poi ricevo il dato con un errore:
110 0001 1
110 1111 1
100 0001 0
in ricezione ricalcolo il bit di controllo per ogni
carattere e lo confronto con quello letto (ricevuto);
... trovo che il secondo carattere e' errato:
infatti 110 1111 => bit di controllo calcolato = 0
=> bit controllo ricevuto
= 1
sono diversi => c’e’ un err !
codici ed errori
138
due osservazioni sul codice a controllo parita':
1) si noti che non posso ricostruire il dato originale,
perche’ con un errore posso
passare da 000 a 010
oppure da 011 a 010
cioe' un dato errato si puo' ottenere da piu' di un dato
originale corretto ...
(non e’ un codice a correzione automatica di errore)
2) se si verificano piu' errori in un dato ?
allora puo' darsi che da un codice legale si passi
ad un altro codice legale ->
non si rilevano errori multipli
codici ed
errori
139
efficienza e ridondanza per il codice ASCII con
controllo di parita’ ?
(cioe' dove ai 7 bit del dato si aggiunge un bit calcolato
in modo che la somma dei bit 0 e 1 risulti pari) es:
a
k
A
110 0001 1
110 1011 1
100
0001 0
efficienza: e = Imed / Nmed = 7 / 8 = 0,875
e la
ridondanza r = 1 - e = 0,125
n.b.: sono usati i codici ASCII a controllo di parita',
controllo di disparita' e i codici senza controllo
codici ed
errori
140
MA: in un calcolatore la probabilita' di errore e'
molto piccola - per rilevare un errore bastano codici
con poca ridondanza
Normalmente la probabilita' di errore e'
(vedere caratteristiche su internet)
molto piccola nel caso di trasmissione dati
(linee telefoniche, linee dati)
ancora piu' piccola nella registrazione su
supporti magnetici (dischi)
ancora piu' piccola nella memoria
centrale del calcolatore:
codici ed
errori
141
probabilita' di errore e' piccola -> per rilevare un
errore bastano codici con poca ridondanza
la probabilita' di errore e' (in ordine decrescente da
“piccola” a “molto piccola”):
caso di trasmissione dati
scrittura/lettura su supporti magnetici (dischetti)
scrittura/lettura in memoria centrale del calcolatore:
si usa una codifica con ridondanza molto piu' piccola
del caso ASCII con controllo parita’:
si aggiungono uno o piu' bit di controllo
su blocchi di bit piu' grandi.
codici ed
errori
142
Es: aggiungo un carattere (8 bit) di controllo ad ogni
blocco di 511 caratteri (511*8 bit), e ho la dimensione
complessiva del blocco di 512 caratteri.
Il carattere e' calcolato ("in qualche modo", ad es.
come somma dei caratteri precedenti, modulo 256) e
poi aggiunto (“Cyclic Redundancy Check” / CRC)
nella lettura (o in ricezione) ricalcolo il carattere di
controllo (dai dati letti/ricevuti) e lo confronto con
quello trovato ->
se sono diversi c'e' un errore nel blocco.
143
Molto usato e' il codice CIRC
o Cross-interleaved Reed-Solomon Code
che usa una codifica con l'algoritmo di Reed e Solomon
(anni 60)
I sistemi di rilevazione e correzione di errore sono
stati definiti gia' negli anni 40
(telecomunicazioni)
alcuni nomi:
Claude Shannon,
Richard Hamming
e altri ... (altro corso ;-)
144
aggiungo un carattere (8 bit) di controllo ad ogni blocco di 511
caratteri (511*8 bit) (in totale il blocco avra’ 512 caratteri); il
carattere e' calcolato dai caratteri presenti nel blocco dato, e
poi aggiunto;
nella lettura (o in ricezione) ricalcolo il carattere di controllo
(dai dati letti/ricevuti) e lo confronto con quello trovato -> se
sono diversi c'e' un errore nel blocco.
efficienza: e = Imed / Nmed = 511*8 / 512*8 = 0,998
e la
ridondanza r = 1 - e = 0,002
ricorda ASCII con parita’:
e = Imed / Nmed = 7 / 8 = 0,875
ridondanza r = 1 - e = 0,125
145
CODICI A CORREZIONE DI ERRORE
(cenni)
codici ed
146
errori
senza controllo errore:
A 00 B 01 C 10
D 11 e= Imed/Nmed = 2/2= 1, r=0
con controllo errore - controllo parita' :
A 000 B 011 C 101 D 110 e= Imed/Nmed = 2/3 , r=1/3
oppure raddoppio
A 0000
B 0011
C 1100
D 1111
e= Imed / Nmed = 2 / 4 = 0,5; r = 1 - e = 0,5
se triplico i bit del codice senza controllo:
A 000000 B 000111 C 111000
D 111111
e= Imed / Nmed = 2 / 6 = 0,33; r = 1 - e = 4 / 6 = 0,66
e’ un codice che consente la correzione di errore:
codici ed
147
errori
se triplico i bit del codice senza controllo (2 bit per 4
simboli) ottengo
A 000000 B 000111 C 111000
D 111111
... un codice che consente la correzione di errore!
es.: dato originale B B A D
spedisco i bit: 000111 000111 000000 111111
con un errore
ricevo ad es.:
000111
000111
001000
111111
dove si riconosce il carattere errato e si ricostruisce anche
quale era il dato originale ! Si noti che qui la distanza tra
due codici legali e' almeno 3 bit.
vale: e = Imed / Nmed = 2 / 6 = 0,33;
r = 1 - e = 4 / 6 = 0,66
codici ed errori
148
come nel caso di codice a rilevazione di errore
[versione rudimentale : rraaddooppiioo i bit]
se la probabilita’di errore e’ piccola - anche
nel caso di codice a correzione automatica dell'errore
-> si puo’ fare di meglio
vediamo uno schema di codifica un po' meno
rudimentale;
in ogni caso :
aggiungo bit per 1) rilevare se c'e' un errore e
aggiungo bit per 2) trovare quale bit del dato e' errato,
e quindi correggerlo
codici ed
errori
149
es.: 16 simboli, codice senza controllo err. (con r=0)
uso 4 bit:
A 1000
B 1001
C 1010
... F 0000
codice a controllo di errore: aggiungo un bit di parita'
(totale 5 bit):
A 10001 B 10010 C 10100 ... F 00000
codice a correzione automatica di errore: dispongo i bit
del dato in due righe da due bit ciscuna, e aggiungo per
ogni riga e ogni colonna un bit di parita',
in tutto altri 4 bit :
A 10 1 B 10 1
quindi: A = 101 000 10
00 0
01 1
quindi: B = 101 011 11
10
11
codici ed
errori
150
ripetiamo: codice a correzione automatica di errore: dispongo i
bit del dato in due righe da due bit ciascuna, e aggiungo un bit
di parita' per ogni riga e ogni colonna:
A 10 1 B 10 1
quindi: A = 101 000 10
00 0
01 1
quindi: B = 101 011 11
10
11
se trasmetto A ovvero
101 000 10
e ricevo (un errore) ad es.
101 010 10
rieseguo il controllo righe/colonne e ho:
10 1
.
01 0
.errore nella seconda riga
10
.errore nella seonda colonna ->
err. nel bit marcato 101 010 10 -> correz.ne: 101 000 10
codici ed
errori
151
e se c’e’ un errore nei bit di controllo parita?
Dato di 16 bit: 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0
aggiungo dei bit secondo lo schema:
1101
0011
0101
1000
0011
1
0
0
1
0
(aggiungo anche un
bit di controllo sui bit
dell’ ultima riga
(riga di controllo), in tutto
aggiungo 9 bit su 16,
in totale 25 bit
Se si verifica un singolo errore ricalcolando i codici di
controllo parita’ per le “righe” e per le “colonne” e il bit
finale, trovo in quale riga e in quale colonna si trova ->
posso correggere.
codici ed
errori
152
es: dato: 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 0
aggiungo dei bit secondo lo schema:
1101 1
(aggiungo anche
0011 0
un bit di controllo
0101 0
sui bit della riga
1000 1
di controllo, in tutto
0011 0
aggiungo 9 bit su 16)
immagino che ci sia un errore in trasmissione, ricevo:
1101 1 0011 1 0101 1 1000 1 0011 0
ricalcolo le parita’ sulle righe: errore nella terza riga;
ricalcolo la parita’ sulle colonne, trovo che le prime
quattro colonne sono a posto -> l’errore e’ nell’ultima
colonna -> ho individuato il bit errato, lo correggo.
codici ed
153
errori
Si osservi che un codice a correzione di errore deve
indicare (in qualche modo) la posizione del bit errato ne ricaviamo l'esigenza minima di questo codice:
dato di k simboli: per indicare una posizione su k devo
usare al minimo n = log2(k) bit, quindi un codice a
correzione automatica dell' errore richiede almeno
k bit (dato) + log2(k) bit (controllo)
e quindi per un dato di k bit, con
k = 4 6 8 32 60 100 128
devo aggiungere almeno
n= 2 3 3 5
6
7
7
256
8
...
... bit
( vedi codice Hamming, 1950 )
codici ed
errori
154
oggi la maggior parte dei dispositivi di trasmissione e/o
di memorizzazione dati usa codici a controllo di errore:
trasmissione dati:
a caratteri: controllo parita’ sul carattere
a blocchi: blocco con carattere di
controllo (cyclic redundancy check,
o il codice CIRC)
registrazione: a blocchi con controllo crc,
sistemi piu’ complessi
155
memoria centrale del calcolatore (RAM):
memoria a celle (gruppi di bit) con controllo errore,
memoria a celle con correz. automatica di err. singolo
memoria senza controllo (in tal caso il sistema esegue
periodicamente delle procedure di controllo
scrivi/rileggi su tutta la memoria centrale)
---ogni dispositivo ha un tasso di errore ammesso proprio
grazie ai sistemi a rilevazione e correzione di errore
(es.dischi magn.: 1 err ogni Gbit -> ogni secondo!)
codici ed
errori ...
BIBLIOGRAFIA:
J.R.Pierce,
"La Teoria dell'Informazione"
Ed.Sc.e Tec. Mondadori, 1963
P.O.Longo, "Teoria dell'informazione",
Boringhieri 1980,
A.Sgarro, "Crittografia, tecniche di protezione
dei dati riservati", Muzzio, 1986,
A.Sgarro, "Codici segreti", Mondadori 1988.
ecc
156
ESERCIZI
157
1) Dati 7 simboli @ # $ % ^ & ”
definire un codice a controllo di errore
2) Definire un codice a correzione di errore per + - /
3) Il codice seguente consente il controllo di errore?
A 101 B 110 C 011 D 111
4) Calcolare l’efficienza e la ridondanza
del codice dell’esercizio 3
5) Il governo cinese ha deciso di utilizzare un codice
a 32 bit per codificare i 20000 ideogrammi cinesi;
calcolare l’efficienza di tale codice.
6) Quanto spazio risparmia la codifica con numero di
matricola [8 cifre decim.] al posto del nome e cognome
[20 lettere] immaginando che tale informaz.e appaia 20
volte per studente nell’ archivio [16000 studenti]
esercizi
158
1) codice a controllo di errore per @ # $ % ^ & ”
7 simboli - 3 bit per codifica almeno, + bit parita’:
0000 @
0011 #
0101 $
0110 %
1001 ^
1010 &
1100 ”
2) Definire un codice a correzione di errore per + - /
due bit per codifica di 3 simboli, poi triplico i bit:
000 000 + 000111 111000 /
3) Il codice seguente consente il controllo di errore?
A 101 B 110 C 011 D 111
no: le codifiche di A e D (BD e CD) hanno distanza uno
-> un errore in A puo’ dare il codice di D
esercizi
4) Calcolare l’efficienza e la ridondanza
del codice dell’esercizio 3 cioe’
A 101 B 110 C 011 D 111
4 simboli - richiesti 2 bit, il codice usa 3 bit ->
efficienza: e = Imed / Nmed = 2/3 => 0,66
ridondanza r = 1-e =0,33
5) Il governo cinese ha deciso di utilizzare un codice
a 32 bit per codificare i 20000 ideogrammi cinesi;
calcolare l’efficienza di tale codice.
e = I / N = log2(20000)/32 = 14,3 / 32 = 0,45
159
esercizi
160
6) Quanto spazio risparmia la codifica con numero di
matricola [8 cifre decim.] al posto del nome e cognome
[20 lettere] immaginando che tale informaz.e appaia 20
volte per studente nell’ archivio [16000 studenti]
per ogni occorrenza risparmio (uso codice ASCII) 12
caratteri, in totale
12 x 20 x 16000 = 12 x 320 000 = 3 840 000 caratteri
se codifico il numero di matricola in binario, uso
log2(100 000 000) = 27 bit (circa)
al posto di 20 x 8 = 160 bit, risparmio 133 bit = 17 car
quindi per 20 occorrenze per 16000 studenti ho
320 000 x 17 = 5 440 000 caratteri
161
FINE
PARTE
INFORMAZIONE
E
CODICI
segue parte numeri