1
La codifica è una tecnica con la quale un dato viene rappresentato mediante un definito insieme di simboli, o di dati, più elementari di qualsiasi natura (grafica, luminosa, acustica, …)
Con tali simboli è possibile formare sequenze che possono essere messe in relazione biunivoca con gli elementi costituenti l’informazione
Esempi:
Alfabeto Morse …sequenze di punti e linee rappresentanti caratteri numero matricola …sequenza di cifre rappresentanti uno studente codice articolo …sequenza di simboli rappresentanti un articolo di un negozio
codice fiscale …sequenza di caratteri rappresentanti una persona numeri Naturali … sequenze di cifre {0, 1, 2, …., 9} ….
parole della lingua italiana … sequenze di lettere {a, b, c, …, z}
Codifica dell’Informazione - 1
2
Codifica dell’Informazione - 2
Formalizzando:
l’informazione da rappresentare appartiene ad un tipo T a cardinalità N T=(x1, …, xn) xi generico valore da rappresentare
T è detto Alfabeto Sorgente
si vuole rappresentare i valori xitramite gli elementi di un tipo E a cardinalità K ≤N
E=(a1, …, ak) aj generico simbolo E è detto Alfabeto in Codice
La Codifica è un’applicazione C, detta tabella-codice, che trasforma ciascun elemento xi∈T in una sequenza di elementi aj∈E, detta parola- codice (di lunghezza li)
3
Codifica dell’Informazione - 3
Codifica a lunghezza fissa
T=(x1, …, xn) Alfabeto Sorgente, cardinalità N E=(a1, …, ak) Alfabeto in Codice, cardinalità K
si dice che la codifica è a lunghezza fissa se la parola-codice ha una lunghezza li = m = costante per tutti gli elementi di T
ad ognuno degli elementi xi∈T si fa corrispondere una delle km disposizioni con ripetizione dei k simboli di E sugli m posti della sequenza e dovrà necessariamente aversi km ≥N
(gli N elementi devono trovare almeno altrettante disposizioni che li rappresentino)
Per codificare un elemento di un tipo a cardinalità N mediante un alfabeto in codice di K simboli è necessaria una sequenza di lunghezza minima m, con
m =[ logk N ]
Codifica dell’Informazione - 4
Esempio:
T=(x1, x2, x3, x4, x5, x6, x7, x8, x9) E=(αα, ββ, γγ)
m =[ log3 9 ] = 2 x1 = αα ββ x2 = β β αα x3 = α γα γ x4 = γ αγ α x5 = ββ γγ x6 = γγ ββ x7 = α αα α x8 = ββ ββ x = γγ γγ
Codice non ridondante km =N
5
Codifica dell’Informazione - 5
Esempio:
T=(x1, x2, x3, x4, x5, x6, x7, x8, x9) E=(0, 10, 1)
m =[ log2 9 ] = 4 x1 = 00000000 x2 = 00010001 x3 = 00100010 x4 = 00110011 x5 = 01000100 x6 = 01010101 x7 = 01100110 x8 = 01110111 x9 = 10001000
Codice ridondante km >N
6
Informazione e Registri
Le informazioni (dati e/o istruzioni) trattate da una macchina sono memorizzate in elementi detti registri o in memoria
Il registro può essere visto come un contenitore di informazione individuato da un nome
Il valore è rappresentato (codificato) mediante apposite sequenze di simboli di un alfabeto codice
nome valore registro
cliente Rossi registro
Esso contiene il valore di un’informazione di un determinato tipo, mentre il nome equivale all’attributo dell’informazione
Esempio:
7
Informazione e Registri - 2
Se il dato è codificato in un alfabeto codice a cardinalità k ed ha una lunghezza l il registro che lo memorizza può essere composto da una sequenza di l elementi k-stabili
Per la rappresentazione di un’informazione di un tipo a cardinalità N occorrono registri ad almeno N stati stabili, ciascuno dei quali
individua uno dei possibili valori
Un registro è composto da elementi più semplici (celle) ognuno dei quali può assumere un numero finito di stati
Registro con 4 celle
Elemento atomico del registro
Informazione e Registri - 3
… ogni cella può assumere 10 stati distinti
… ad esempio le cifre da 0 a 9
… il registro in totale può assumere 10000 stati distinti
Registro: elemento fisico atto ad assumere K stati finiti (K-stabile) associabili a K valori distinti di un’informazione
Esempio:
Registro con 4 celle
0 0 0 0
...
5 1 0 7...
9 9 9 99
Informazione e Registri - 4
Esempio:
T=(x1, x2, x3, x4, x5, x6, x7, x8, x9) E=(αα, ββ, γγ)
m =[ log3 9 ] = 2
x1 αα ββ
ciascuna delle due celle del registro può assumere 1 dei tre valori (αα, ββ, γγ) - cella tri-stabile, registro a 9 stati totali
10
Informazione e Registri - 5
Esempio:
T=(x1, x2, x3, x4, x5, x6, x7, x8, x9) E=(0, 10, 1)
m =[ log2 9 ] = 4
x4
0 0 1 1
ciascuna delle 4 celle del registro può assumere 1 dei 2 valori (0,10,1) - cella bi-stabile, registro a 16 stati totali
11
Informazione e Registri - 6
Nella macchina reale tutte le informazioni sono codificate in BIT e la cella elementare dei registri è un elemento bistabile detto flip-flop l’alfabeto codice utilizzato per codificare le informazioni e renderle
comprensibili ad una macchina è quindi un alfabeto binario (cardinalità 2):
{0, 1}, {spento, acceso}
…. esistenza di elementi fisici economici bistabili
…. semplicità dei circuiti elettronici di elaborazione
…. sicurezza del funzionamento, ovvero necessità di ridurre la possibilità di commettere un errore durante una scelta
(discriminazione tra livelli)