Elementi di informatica Elementi di informatica

Elementi di informatica Elementi di informatica

Codifica dell’Informazione Codifica dell’Informazione

La

La CODIFICACODIFICA è è unauna tecnicatecnica con la con la qualequale un un datodato vieneviene rappresentatorappresentato mediante

medianteun un definitodefinitoinsiemeinsiemedidisimbolisimboli, o , o dididatidati, , piùpiùelementarielementarididiqualsiasiqualsiasi natura

natura((graficagrafica, , luminosaluminosa, , acusticaacustica, …), …) Con

Con talitali simbolisimboliè è possibilepossibile formareformare sequenzesequenze chechepossonopossono essereesseremessemesse in in relazione

relazionebiunivocabiunivocacon con gliglielementielementicostituenticostituentil’informazionel’informazione

Codifica

Codifica dell’Informazione dell’Informazione

problema della rappresentazione dei valori delle informazioni problema della rappresentazione dei valori delle informazioni

la rappresentazione deve essere effettuata attraverso un insieme

la rappresentazione deve essere effettuata attraverso un insiemefinito di finito di simboli disponibili

simboli disponibili

il numero di simboli disponibili è in generale minore del numero

il numero di simboli disponibili è in generale minore del numerodi valori di valori da rappresentare

da rappresentare

la rappresentazione avviene associando a ciascun valore una sequ

la rappresentazione avviene associando a ciascun valore una sequenza di enza di simboli

simboli

Esempi Esempi:: Alfabeto

Alfabeto MorseMorse ……sequenzesequenze didi puntipunti e e lineelinee rappresentantirappresentanti caratteri

caratteri numero

numero matricolamatricola ……sequenzasequenza didi cifrecifre rappresentantirappresentanti unouno studente

studente codice

codice articoloarticolo ……sequenzasequenza didi simbolisimboli rappresentantirappresentanti un un articolo

articolodidiun un negozionegozio codice

codicefiscalefiscale……sequenzasequenzadidicarattericaratteri rappresentantirappresentantiunauna persona

persona numeri

numeriNaturaliNaturali… … sequenzesequenzedidicifrecifre{0, 1, 2, …., 9} ….{0, 1, 2, …., 9} ….

parole

parole delladellalingua lingua italianaitaliana… … sequenzesequenzedidiletterelettere{a, b, c, …, {a, b, c, …, z}

z}

Codifica

Codifica dell’Informazione dell’Informazione

Codifica

Codifica dell’Informazione dell’Informazione

Formalizzando Formalizzando:: l’informazione

l’informazionedadarappresentarerappresentareappartieneappartienead un ad un tipotipoT a T a cardinalitàcardinalitàNN T=(x

T=(x₁₁, …, , …, xx_nn) x) x_ii genericogenericovalorevaloredadarappresentarerappresentare T

Tè è dettodettoAlfabetoAlfabetoSorgenteSorgente si

sivoglionovoglionorappresentarerappresentarei i valorivalorixx_iitramitetramitegliglielementielementididiun un altroaltrotipotipo E a

E a cardinalitàcardinalitàK < NK < N E=(a

E=(a₁₁, …, , …, aa_kk) ) aa_jj genericogenericosimbolosimbolo E

Eè è dettodettoAlfabetoAlfabetoin in CodiceCodice La

La CodificaCodificaè è un’applicazioneun’applicazioneC, C, dettadettatabellatabella--codicecodice, , cheche trasformatrasforma ciascun

ciascunelementoelemento xx_ii?TTin in unaunasequenzasequenzadidi elementielementiaa_jj? E, E, dettadettaparolaparola-- codice

codice((didilunghezzalunghezzall_ii))

Esempio:

Esempio:

Alfabeto Sorgente

Alfabeto Sorgente: (picche, fiori, quadri, cuori) : (picche, fiori, quadri, cuori) Alfabeto in codice

Alfabeto in codice: (*, /) : (*, /) Codice

Codice Altro Codice Altro Codice picche * **

picche * **

fiori / //

fiori / //

quadri ** */

quadri ** */

cuori // /*

cuori // /*

Codifica

Codifica dell’Informazione dell’Informazione

Codifica a lunghezza fissa Codifica a lunghezza fissa

la lunghezza l

la lunghezza liidelle parole codice associate ai valori dell'alfabeto delle parole codice associate ai valori dell'alfabeto sorgente è costante

sorgente è costante Codifica a lunghezza variabile Codifica a lunghezza variabile

la lunghezza l

la lunghezza liidelle parole codice associate ai valori dell'alfabeto delle parole codice associate ai valori dell'alfabeto sorgente è variabile

sorgente è variabile

•

• il codice può essere una associazione del tutto arbitraria il codice può essere una associazione del tutto arbitraria di parole codice a valori

di parole codice a valori

•

• oppure, può essere fondato su regole ben definiteoppure, può essere fondato su regole ben definite

•

• esempi: il codice fiscale, il codice esame, numero di esempi: il codice fiscale, il codice esame, numero di matricola

matricola

Codifica

Codifica dell’Informazione dell’Informazione

Codifica

Codifica dell’Informazione dell’Informazione

Codifica

Codifica a a lunghezza lunghezza fissa fissa T=(x

T=(x

, …, , …, x x

) ) Alfabeto Alfabeto Sorgente Sorgente, , cardinalità cardinalità N N E=(a

E=(a

, …, , …, a a

) ) Alfabeto Alfabeto in in Codice Codice, , cardinalità cardinalità K K

la

la parolaparola--codicecodiceha ha unaunalunghezzalunghezza llii= m = = m = costantecostanteper per tuttituttigliglielementielementididiTT ad

ad ognunoognunodeglideglielementielementixx_ii<<T T sisifafacorrisponderecorrispondereunaunadelledellekk^{m m} disposizionidisposizionicon con ripetizione

ripetizionedeideik k simbolisimbolididiE E suglisuglim m postipostidelladellasequenzasequenzae e dovràdovrànecessariamentenecessariamente aversi

aversi kk^{m m} <<N N (

(gligliN N elementielementidevonodevonotrovaretrovarealmenoalmenoaltrettantealtrettantedisposizionidisposizionichechelili rappresentino

rappresentino)) Per

Per codificarecodificare un un elementoelementodidiun un tipotipoa a cardinalitàcardinalitàN N mediantemedianteun un alfabetoalfabetoin in codice

codicedidiK K simbolisimboliè è necessarianecessariaunaunasequenzasequenzadidilunghezzalunghezzaminima m, conminima m, con

m =[

m =[ log log

N ] N ]

Codifica

Codifica dell’Informazione dell’Informazione

Esempio Esempio: :

T=(x

T=(x₁₁, x, x₂₂, x, x₃₃, x, x₄₄, x, x₅₅, x, x₆₆, x, x₇₇, x, x₈₈, x, x₉₉)) E=(a, b, c )

E=(a, b, c ) m =[ log

m =[ log₃₃ 9 ] = 29 ] = 2 x

x₁₁= a b = a b x x₂₂= b a = b a x x₃₃= a c = a c x x₄₄= c a = c a x x₅₅= b c = b c x x₆₆= c b = c b x x₇₇= a a= a a x x₈₈= b b= b b x x_{9 9} = c c = c c

Codice

Codice non non ridondante ridondante k

k

= = N N

Codifica

Codifica dell’Informazione dell’Informazione

Esempio Esempio:: T=(x

T=(x₁₁, x, x₂₂, x, x₃₃, x, x₄₄, x, x₅₅, x, x₆₆, x, x₇₇, x, x₈₈, x, x₉₉)) E=(0, 1)

E=(0, 1) m =[ log

m =[ log₂₂ 9 ] = 49 ] = 4 x

x₁₁= 0000 = 0000 x

x₂₂= 0001= 0001 x

x₃₃= 0010= 0010 x

x₄₄= 0011= 0011 x

x₅₅= 0100 = 0100 x

x₆₆= 0101= 0101 x

x₇₇= 0110= 0110 x

x₈₈= 0111= 0111 x

x_{9 9} = 1000= 1000

Codice

Codice ridondante ridondante k

k

> > N N

Lunedì Martedì Mercoledì

Giovedì Venerdì Sabato Domenica

000 001 010 011 100 101

111 110

Lunedì Martedì

Mercoledì Giovedì

Venerdì Sabato Domenica

00

01 10

11

Lunedì

Martedì Mercoledì

Giovedì

Venerdì Sabato Domenica

0

1

Lunedì Martedì Mercoledì

Giovedì Venerdì Sabato Domenica

I giorni della

I giorni della settimana settimana in binario (1) in binario (1)

1 bit

2 “gruppi” 2 bit

4 “gruppi” 3 bit

8 “gruppi”

CODIFICATORE

x

x

x

……… x

a

a

… a

CODIFICATORE

Lun Mar ……… Dom

1 0 1

Un Modello Un Modello

n

ninput, input, gliglielementielementidell’alfabetodell’alfabeto sorgente

sorgente, , didicui cui 1 solo 1 solo attivoattivo Un’applicazione

Un’applicazionechechetrasformatrasformaun un elementoelemento dell’alfabeto

dell’alfabetosorgentesorgentenellanella parolaparolacodicecodice k

koutput, i output, i simbolisimboli dell’alfabetodell’alfabeto codicecodice, , formanti

formanti la la parolaparola codicecodice

Esempio Esempio: :

bit 000 001 010 011 100 101 110 111

esad. 0 1 2 3 4 5 6 7

0000 0 NUL DLE spz 0 @ P ` p

0001 1 SOH DC1 ! 1 A Q a q

0010 2 STX DC2 " 2 B R b r

0011 3 ETX DC3 # 3 C S c s

0100 4 EOT DC4 $ 4 D T d t

0101 5 ENQ NAK % 5 E U e u

0110 6 ACK SYN & 6 F V f v

0111 7 BEL ETB ' 7 G W g w

1000 8 BS CAN ( 8 H X h x

1001 9 HT EM ) 9 I Y i y

1010 A LF SS * : J Z j z

1011 B VT ESC + ; K [ k {

1100 C FF FS , < L \ l |

1101 D CR GS - = M ] m }

1110 E SO RS . > N ^ n ~

1111 F SI US / ? O _ o DEL

Codice

Codice ASCII ASCII

Codice ASCII (American Standard Code for Information Interchange): usato per uniformare la codifica dei caratteri

Esempio: Lettera ‘A’ => 100 0001

Codici ridondanti e controllo dell’errore

Codici binari ridondanti sono utilizzati per la individuazione di malfunzionamenti (guasto dei circuiti, difetti di trasmissione) che conducano a parole errate

In un codice ridondante, solo n delle parole disponibili sono lecite (dove n ? ) per cui

? se S non è una parola lecita, allora è certamente errata

? se S è una parola lecita, allora è probabilmente corretta K m

… maggiore è la ridondanza maggiore è la probabilità di scoprire un errore … nessuna certezza che una parola codice lecita non sia errata ...

Km-1

Codifica

Codifica dell’Informazione dell’Informazione

Un esempio:

Un esempio: Il controllo di paritàIl controllo di parità

Utilizzato per il controllo dell’errore nella trasmissione di pa

Utilizzato per il controllo dell’errore nella trasmissione di parole di codici role di codici binari completi (

binari completi (KK= 2, = 2, nn= 2= 2^{m m} ) )

Dal codice completo si ottiene un codice ridondante aggiungendo Dal codice completo si ottiene un codice ridondante aggiungendo un bit un bit con la seguente regola:

con la seguente regola:

?

? 1 se gli 1 se gli mmbit hanno un numero dispari di 1bit hanno un numero dispari di 1

?

? 0 se gli 0 se gli mmbit hanno un numero pari di 1bit hanno un numero pari di 1

…

…le parole lecite del nuovo codice avranno un numero pari di le parole lecite del nuovo codice avranno un numero pari di 1 ...

1 ...

aggiunta bit di parità parola

(m bit)

trasmissione parola

(m+1 bit)

Parola ricevuta (m+1 bit)

controllo di parità

Parola lecita (m bit) segnalazione esito

trasmissione

Codifica

Codifica dell’Informazione dell’Informazione

Codifica in Bit

Codifica in Bit DirettaDirettaed ed IndirettaIndiretta

Un codice binario associa ad ogni valore una parola codice in bi Un codice binario associa ad ogni valore una parola codice in bitt Una codifica in bit può anche essere ottenuta attraverso un codi

Una codifica in bit può anche essere ottenuta attraverso un codice intermedioce intermedio T=(x1,x2,...,

T=(x1,x2,...,xnxn) J=(s1,s2,....,) J=(s1,s2,....,sksk) E=(0,1)) E=(0,1)

?

? un codice intermedio associa ad ogni un codice intermedio associa ad ogni xixiuna stringa di una stringa di sjsj

?

? un codice binario associa ad un codice binario associa ad sjsjuna stringa di bit una stringa di bit

?

? sostituendo i simboli sj di ciascuna parola codice sostituendo i simboli sj di ciascuna parola codice xixicon la corrispondente con la corrispondente parola in bit...

parola in bit...

… diremo Indiretta un tale tipo di codifica ...

… diremo Indiretta un tale tipo di codifica ...

Codifica

Codifica dell’Informazione dell’Informazione

Esempio:

T= (x1,x2,...x10) J= (a,b,c) codice:

x1 aaa x6 abc x2 aab x7 aca x3 aac x8 acb x4 aba x9 acc x5 abb x10 baa codice binario per J:

a 00 b 01 c 11

X1 000000 X2 000001 X3 000011 X4 000100 X5 000101 X6 000111 X7 001100 X8 001101 X9 001111

Codifica Binaria Indiretta

Codifica

Codifica dell’Informazione dell’Informazione

Codifica

Codifica dell’Informazione dell’Informazione

Una codifica indiretta produce parole codice di lunghezza Una codifica indiretta produce parole codice di lunghezza maggiore od uguale di quella delle parole codice prodotte da maggiore od uguale di quella delle parole codice prodotte da una codifica diretta

una codifica diretta

[

[log log

n n]*[log ]*[log

k]>=[log k]>=[log

n] n]

(… log : parte intera, maggiorata di uno se ...) (… log : parte intera, maggiorata di uno se ...)

… nell'esempio precedente:

… nell'esempio precedente:

[log

[log

10]*[log 10]*[log

3]=6 3]=6 [log

[log

10]=4 10]=4

Informazione

Informazione e Registri e Registri

Le

Le informazioniinformazioni((datidatie/o e/o istruzioniistruzioni) ) trattatetrattatedadaunaunamacchinamacchinasonosono memorizzate

memorizzatein in elementielementidettidettiregistriregistri Il

Il registroregistropuòpuòessereesserevistovistocome un come un contenitorecontenitoredidiinformazioneinformazione individuato

individuatodadaun un nomenome

Il

Il valorevaloreè è rappresentatorappresentato((codificatocodificato) ) mediantemedianteapposite apposite sequenzesequenzedidi simboli

simbolididiun un alfabetoalfabetocodicecodice

nome valore registro

cliente Rossi registro Un

Un registroregistrocontienecontieneililvalorevaloredidiun’informazioneun’informazionedidiun un determinatodeterminato tipo

tipo, , mentrementreililnomenomeequivaleequivaleall’attributoall’attributodell’informazionedell’informazione Esempio

Esempio::

Informazione

Informazione e Registri e Registri - - 2 2

Se

Se ilildatodato è è codificatocodificatoin un in un alfabetoalfabetocodicecodicea a cardinalitàcardinalitàk ed ha k ed ha unauna lunghezza

lunghezzal,l,ililregistroregistrochechelo lo memorizzamemorizzapuòpuòessereesserecompostocompostodadaunauna sequenza

sequenzadidillelementielementi kk--stabilistabili Per la

Per la rappresentazionerappresentazionedidiun’informazioneun’informazionedidiun un tipotipoa a cardinalitàcardinalitàN N occorrono

occorronoregistriregistriad ad almenoalmenoN N statistatistabilistabili, , ciascunociascunodeideiqualiqualiindividuaindividua uno

unodeideipossibilipossibilivalorivaloridell’informazionedell’informazione Un

Un registroregistroè è compostocompostodadaelementielementipiùpiùsemplicisemplici((cellecelle) ) ognunoognunodeidei quali

qualipuòpuòassumereassumereun un numeronumerofinitofinitodidistatistati

Registro con 4 celle Elemento atomico del registro

Informazione

Informazione e Registri e Registri - - 3 3

…

…supponiamo supponiamo che che

…

… ogni ogni cella cella può può assumere assumere 10 10 stati stati distinti distinti ( (deca deca- -stabile) stabile)

… ad

… ad esempio esempio le le cifre cifre da da 0 a 9 0 a 9

…

… il il registro registro in in totale totale può può assumere assumere 10000 10000 stati stati distinti distinti

Registro: : elementoelementofisicofisicoattoattoad ad assumereassumere K K statistatifinitifiniti(K(K-- stabile)

stabile) associabiliassociabilia K a K valorivalori distintidistintididiun’informazioneun’informazione Esempio

Esempio::

Registro con 4 celle

0 0 0 0 ... 5 1 0 7 ... 9 9 9 9

Informazione

Informazione e Registri e Registri - - 4 4

Esempio:

T=(x

, x

, x

, x

, x

, x

, x

, x

, x

) E=(a, b, c )

m =[ log

9 ] = 2

…un registro di 2 celle, ciascuna tri-stabile

• ciascuna delle celle del registro può assumere 1 dei tre valori (a, b, c )

• celle tri-stabili, registro a 9 stati totali

x₁= a b x₂= b c x₃= a c x₄= c a x₅= b c x₆= c b x₇= a a x₈= b b x₉ = c c

? ? ? x

Informazione

Informazione e Registri e Registri - - 5 5

Esempio:

T=(x₁, x₂, x₃, x₄, x₅, x₆, x₇, x₈, x₉)

E=( ?????????????)

m =[ log₂ 9 ] = 4

…un registro di 4 celle, ciascuna bi-stabile

• ciascuna delle 4 celle del registro può assumere 1 dei 2 valori (???)

• celle bi-stabili, registro a 16 stati totali

0

0 1 1

x

x₁= 0000 x₂= 0001 x₃= 0010 x₄= 0011 x₅= 0100 x₆= 0101 x₇= 0110 x₈= 0111 x₉ = 1000

Informazione

Informazione e Registri e Registri - - 6 6

Nella

Nellamacchinamacchinarealerealetuttetuttele le informazioniinformazionisonosonocodificatecodificatein in BITBIT e la e la cella

cellaelementareelementaredeidei registriregistriè un è un elementoelementobistabilebistabiledettodettoflipflip--flopflop l’alfabeto

l’alfabetocodicecodiceutilizzatoutilizzatoper per codificarecodificare le le informazioniinformazioni e e renderlerenderle comprensibili

comprensibiliad ad unaunamacchinamacchinaè è quindiquindiun un alfabetoalfabeto binariobinario((cardinalitàcardinalità 2): {0, 1}, {

2): {0, 1}, {spentospento, , accesoacceso}, {}, {verovero, , falsofalso}, …}, …

….

…. esistenzaesistenzadidielementielementifisicifisici economicieconomici bistabilibistabili

….

…. semplicitàsemplicitàdeideicircuiticircuitielettronicielettronicididielaborazioneelaborazione

….

…. sicurezzasicurezzadel del funzionamentofunzionamento, , ovveroovveronecessitànecessitàdidiridurreridurre la la possibilità

possibilitàdidicommetterecommettereun un erroreerroreduranteduranteunaunasceltascelta (

(discriminazionediscriminazionetratra livellilivelli))

…. la

…. la dimensionedimensione((lunghezzalunghezza) ) deideiregistriregistriè ‘è ‘finitafinita’’