02 - Scienza dell'Informazione [modalit compatibilit ]dipsf.fisica.unina.it/~mastro/02 - Scienza...

Lezione 2

Scienza dell’informazioneScuola di Specializzazione in Fisica Medica

Paolo Mastroserio 1

Lezione 2

Codifica dell’informazione

INDICE• L’algebra booleana

• I circuiti logici

• I circuiti di commutazione

Paolo Mastroserio 2

• I circuiti di commutazione

• Le prime macchine calcolatrici

• Il concetto di informazione

• La codifica binaria

1815-1864: George Boole

George Boole, nel 1854, pubblicò il libro:An Investigations of the Laws of Thought(Un esame sulle leggi logiche del pensiero)

Dimostrò che la maggior parte del pensiero logico

Paolo Mastroserio 3

pensiero logicoprivata di particolari irrilevanti e verbosità,

potesse essere concepita come una serie di scelte

Questa idea è divenuta la base dei computer

I diagrammi di flusso(flow chart)

• Qualsiasi processo logico può essere ricondotto ad una sequenza di eventi elementari, che nell'insieme prende il nome di algoritmo.

Paolo Mastroserio 4

nome di algoritmo.

• Una sequenza di passi logici può essere rappresentata con un diagramma di flusso(flow chart)

Problema �� flow chart

Per la visualizzazione di un problema con un diagramma di

Paolo Mastroserio 5

un diagramma di flusso, si utilizzano vari simboli graficistandard

I simboli grafici più usati

Ingresso/uscita dati �

Operazioni �

Paolo Mastroserio 6

Operazioni �

Controlli decisionali �

Problema �� flow chart

• Un flow chart è facilmente traducibile in un programma comprensibile dall'elaboratore

Paolo Mastroserio 7

• Immaginiamo di voler tradurre in un diagramma di flusso le seguenti affermazioni:

»"esco se è bel tempo e fa caldo“

»"esco se è bel tempo o fa caldo"

flow chart

Paolo Mastroserio 8

Questo diagramma comporta il verificarsi di due condizioni(evidenziate in verde)

• Un elaboratore non comprende il significato delle frasi "esco... resto in casa“• Un elaboratore può solo considerare il valore di certe costanti associate ad ogni

singolo evento.

Questo diagramma comporta il verificarsi di almeno unafra due condizioni

Manipolazione di simboli

Convertiamo i diagrammi di flusso in un linguaggio numerico, il solo comprensibile dall'elaboratore.

A = 1 corrisponde all'evento "bel tempo" B = 1 corrisponde all'evento "caldo"

Paolo Mastroserio 9

B = 1 corrisponde all'evento "caldo" C = 1 corrisponde all'azione "esco"

A = 0 corrisponde all'evento non "bel tempo" B = 0 corrisponde all'evento non "caldo" C = 0 corrisponde all'azione non "esco"

Istruzioni e operatori logiciCon le istruzioni riportate in tabella possiamo tradurre i due differenti diagrammi di flusso in

sequenze di istruzioni

Paolo Mastroserio 10

Ingresso dati: leggi A e B


IF A AND B THEN C IF A OR B THEN C

Le tavole della verità

A B C =

A AND B

0 0 0

A B C =

A OR B

0 0 0


0 1 0

1 0 0

1 1 1

0 1 1

1 0 1

1 1 1

Il circuito ANDA B C=A AND B

0 0 0

0 1 0

1 0 0

1 1 1


• La lampadina si accenderà solo se entrambi gli interruttoriA e B verranno abbassati in modo da chiudere il contatto elettrico.

• Questo circuito, corrisponde ad un operatore logico AND.

1 1 1

Il circuito ORA B C=A OR B

0 0 0

0 1 1

1 0 1


1 1 1

La lampadina si accenderà se uno solo degli interruttoriA e B verrà abbassato.

Questo circuito, corrisponde ad un operatore logico OR.

Il circuito NOT

A B = NOT A

0 1

1 0

• Il circuito, comprende due alimentatori con polarità opposta. • Quando il circuito inferiore è aperto (0), la batteria alimenta il


circuito superiore e la lampadina è accesa• Quando il circuito inferiore è chiuso, la seconda batteria fornisce

una corrente uguale e opposta che impedisce il passaggio di corrente per cui la lampadina si spegne

• La tavola di verità corrispondente a questo circuito, comprende un solo ingresso. Quando l'interruttore è alzato (A=0), la lampadina è accesa (B=1) e viceversa.

I simboli delle porte


Utilizzando le porte logiche …"se è bel tempo ed è caldo esco; tuttavia, se ho un impegno esco in ogni caso"

AND


Si richiede una porta AND ed una porta OR unite tra loro

OR

Combinazione di più porte logiche

• Quello che abbiamo esaminato finora, può definirsi un semplice elaboratore dedicato, capace cioè di eseguire un compito particolare: verificare la presenza di due eventi (bel tempo, caldo) o di un evento alternativo (impegno)

• Si può facilmente intuire che gli elementi discussi costituiscono la base per combinare tra loro più porte


costituiscono la base per combinare tra loro più porte logiche in modo da ottenere rapidamente, e senza confusione, decisioni immediate.

• Inoltre, si possono costruire circuiti in grado di effettuare operazioni matematiche.

Operazioni di somma

Due numeri in notazione binaria vengono sommati allo stesso modo dei numeri in notazione decimale:

1 111


1 0 0 1 0 1

1 0 1 1 1

3 7

2 3

6 0 001 1 1 1

1 111

Sommiamo (in binario) due numeri a una cifra

A B ssomma

r resto

0 0 0 0

0 1 1 0


0 1 1 0

1 0 1 0

1 1 0 1

Analizziamo prima il resto

A B s r

0 0 0 0

0 1 1 0

A Br =

A AND B

0 0 0

0 1 0

1 0 0


0 1 1 0

1 0 1 0

1 1 0 1

r = resto

1 0 0

1 1 1

Si può osservare che il risultato coincide

esattamente a quello fornito dall’operatore

AND

Analizziamo la somma (senzail resto)

A B s r

0 0 0 0

0 1 1 0

A Bs =

A XOR B

0 0 0

0 1 1

1 0 1


0 1 1 0

1 0 1 0

1 1 0 1

s = somma

1 0 1

1 1 0

Si può osservare che il risultato coincide

esattamente a quello fornito daell’operatore

XOR

Cos’è lo XOR ?(o l’uno, o l’altro, ma non tutti e due)

Lo XOR è un operatore, detto anche OR esclusivo,

che restituisce uno (vero) se e sole se uno solo dei due elementi è uguale a uno


A Bs =

A XOR B

0 0 0

0 1 1

1 0 1

1 1 0

Usiamo questi simboli

AND


OR

NOT

Costruiamo il circuito per la somma:XOR

A1

11

1

01


B

s = A + B

00

01

1 1

Costruiamo il circuito per il resto:AND

A

r


B

s = A + B

Combinando i due circuiti …

A1

11

1

10 r = 11


B

s = A + B

11

10

0 0

… otteniamo il semi-addizionatore

Perchè semi-addizionatore?

Perché fa la somma di soli due bit e non tiene conto dell’eventuale resto di una


tiene conto dell’eventuale resto di una somma precedente

L’addizionatore completo

A

B

r=1

1

0

1

0


R

r=1

s=0Resto di una somma precedente

1

1

0

1

1947 - Invenzione del transistor

La caratteristica che distingue gli interruttori elettronicidai più comuni interruttori elettrici


interruttori elettriciè che essi sono comandati da un segnale elettronico binario e non dall'intervento umano.

Primo transistor

John Bardeen, Walter Brattain, William Shockley

(1956 premio Nobel per la Fisica)

Scoprirono gli effetti del transistor nel 1947; erano


transistor nel 1947; erano membri dello staff tecnico dei Bell Laboratories aMurray Hill, NJ

Joachim Bouvet

Un gesuita missionario, padre Joachim Bouvet,

portò a Leibniz dei curiosi diagrammi riportati in un testo


riportati in un antico molto diffuso in

Cina, quanto la Bibbia in Europa.

Gottfried Wilhelm Leibniz(Lipsia, 1646 - Hannover, 1716)

• Studiò filosofia e diritto e conseguì la laurea in giurisprudenza nel 1666.

• Nel 1676 divenne bibliotecario del duca di Hannover.

• Gli ultimi anni della sua vita furono amareggiati dalla disputa sorta tra lui e


• Gli ultimi anni della sua vita furono amareggiati dalla disputa sorta tra lui e Newtona proposito della paternità del calcolo infinitesimale

• Leibniz intuì che, affidandosi ad alcune sequenze numeriche (in binario), ci si poteva costruire convenzionalmente alcune lettere di un immaginario "alfabeto", di conseguenzaparole, frasi, concetti.

• ComeLeibniz arrivò a questa conclusione non è dato di sapere

• La corrente, i relè e le valvole termoioniche non esistevano e l’on-off neppure si poteva immaginare cos'era

L’intuizione di Leibniz (2)


• Nulla si poteva sapere del polo positivo e del polo negativo

• Le porte logicheo gli indirizzi di memoria non erano stati ancora inventati

• Il grande matematico descrisse un sistema già usato dagli antichi cinesi, lui cercò solo di capirci qualcosa creando un sistema numerico e nel farlo fu poi quasi deriso

Charles Babbagela macchina delle differenze

• Il problema originario che portò Charles Babbage al concetto di calcolatore programmabileè quello della realizzazione di tavole matematicheprecise e prive di errori

• Quelle disponibili all’epoca erano affette da numerosi


• Quelle disponibili all’epoca erano affette da numerosi errori di calcolo e di stampa.

• Il calcolatore meccanico differenziale doveva essere capace di eseguire calcoli fino all’ottava cifra decimale, ma non fu mai realizzato

• Nonostante i numerosi tentativi, Babbage non riuscì mai a completare la realizzazionedella macchina a causa delle difficoltà tecniche per il montaggio dei componenti meccanici richiesti e per la notevole precisione meccanica necessaria nella preparazione di ogni singolo componente e, soprattutto, per la mancanza di fondi sufficienti

Modello della macchina delle differenzericostruito presso il Museo della Scienza di Londra seguendo il progetto del 1849, di cui si hanno tutti i disegni

Herman Hollerithla macchina di Hollerith

• Verso la fine del 1800, con la rivoluzione industriale le campagnesi spopolavanoa favore delle città

• I governi dovevano essere in grado di conoscere, attraverso censimenti, la composizione delle società per poter prendere decisioni adeguate al momento giusto.

• Fu la prima volta che ci si rese conto


• Fu la prima volta che ci si rese conto che sole capacità mentali non sarebbero bastate ma era necessario un aiuto meccanico.

• HERMAN HOLLERITH (1860-1929) ingegnere meccanico, nel 1884 propose l’utilizzo di un macchinario elettrico da lui elaborato, basato sull’utilizzo di schede di cartoneperforate, sull’esempio di Jacquard.

Sistema di numerazione NON posizionale

• Il sistema di numerazione romano non e’ posizionale

• Il valore associato a ciascun simbolo non dipende dalla sua posizione.


dalla sua posizione.• Nei due numeri XII e XIX la seconda cifra, pur

avendo la stessa posizione, assume due pesi diversi:

XII = 10 + 1 + 1

XIX = 10 + 10 - 1

Il sistema di numerazione posizionale

La notazione posizionale consente di scrivere un numero N di una certa base generica come una sequenza di cifre; a destra abbiamo le cifre meno


sequenza di cifre; a destra abbiamo le cifre meno significative e a sinistra le più significative

504.31 = 5 • 102 + 0 • 101 + 4 • 100 + 3 • 10-1 + 1 • 10-2

Sistemi di numerazione posizionale

Sistema Base Cifre

Unario 1 1, 11, 111, …

Binario 2 0, 1


Ottale 8 0, 1, 2, 3, 4, 5, 6, 7

Decimale 10 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Esadecimale 16 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

La codifica binaria

• L’alfabeto più semplice è quello costituito da soli due simboli.

• È facilmente implementabile su un supporto fisico– Sostanze magnetiche con due opposte polarizzazioni


– Passaggio o meno di corrente– Passaggio o meno di luce– …

• Un sistema automatico basato su un alfabeto binario e’– Più economico– Piu’ affidabile

Big Endian e Little Endian

• BIG-ENDIAN e LITTLE ENDIAN sono i termini che descrivono l'ordine con cui una macchina immagazzina i byte di una parola in memoria.

• BIG-ENDIAN è l'ordine per cui (l'indiano più grande) la


• BIG-ENDIAN è l'ordine per cui (l'indiano più grande) la parte più significativa va memorizzata per prima(all'indirizzo più basso di memoria).

• LITTLE-ENDIAN è l'ordine per cui (l'indiano più piccolo) la parte meno significativa va memorizzata per prima (all'indirizzo più basso di memoria)

Chi adopera big/little endian ?

Little EndianCompaq

Intel

Big EndianCray

IBM

MAC


Intel

Vax MAC

SGI

Sun

Formati di fileLittle Endian

BMP (Windows and OS/2 Bitmaps)GIFFLI (Autodesk Animator)PCX (PC Paintbrush)QTM (Quicktime Movies)Microsoft RTF (Rich Text Format)TGA (Targa)

Big Endian

Sistemi misti

DXF (AutoCad) -- VariablePostScript -- Not Applicable (text!)POV (Persistence of Vision ray-tracer) -- Not Applicable (text!)Microsoft RIFF (.WAV & .AVI) -- Both


Big Endian

Adobe PhotoshopIMG (GEM Raster)JPEGMacPaintSGI (Silicon Graphics)Sun RasterWPG (WordPerfect Graphics Metafile)

Microsoft RIFF (.WAV & .AVI) -- BothTIFF -- Both, Endian identifier encoded into fileXWD (X Window Dump) -- Both, Endian identifier encoded into file

Problemi di compatibilità

• Il problema di compatibilitàtra le due modalità sorge quando i dati vengono stampati, oppure trasmessi da un computer ad un altro.


• Attenzione al linguaggio C: spesso un programma scritto per un tipo di macchina, non funziona correttamente su un'altra macchina a causa della diversità delle due modalità operative appena descritte.

Il concetto di informazione

Osserviamo questi due fogli

Foglio pieno di

informazioni

SPZB CSFADV

ASV


• Fisicamente sono simili: inchiostro su supporto cartaceo• L’informazione che se ne può ottenere è completamente

diversa• I due fogli non costituiscono informazione, la portano

ASV

Caratteristiche dei supportiAlcuni supporti sono adatti alla

trasmissione ma non alla memorizzazione:

• L’aria trasporta l’informazione sonora, ma non la memorizza

• Analogamente un cavo elettrico, trasporta byte ma non li


• Analogamente un cavo elettrico, trasporta byte ma non li memorizza

Altri supporti, al contrario, sono adatti alla memorizzazione ma non alla trasmissione:

• Un CD memorizza l’informazione digitale ma non è leggibile direttamente dall’uomo

Stessa informazione su supporti diversi

10

131211109


10 87654321

Stesso supporto informazioni diverse

fare


• Se la legge un italiano pensa al verbo fare• Se la legge un inglese pensa a un pedaggio

Informazione e pattern recognition

Per riconoscere informazione da un supporto fisico occorre applicare un

QQ QQQQ


fisico occorre applicare un processo operativo di astrazione

attraverso il quale un sistema fisico

viene considerato dal punto di vista della sua forma

I sistemi OCRI programmi di riconoscimento dei caratteri

OCR = Optical Character Recognition

in dotazione agli scanner svolgono funzioni di pattern recognition e riconducono uno stato fisico a un grafema.


grafema.

L’informazione a lato viene riconosciuta come una qse risponde alla descrizione:

“ovale con breve segmento intersecante in basso”

QQQQ

Algoritmo di edge-preserving smoothingNagao e Matsujama


Immagine originale Immagine dopo 5 iterazioni

Codifica binaria dei numeri

• Binario naturale

• Numeri interi– Codifica con modulo e segno


– Codifica con modulo e segno

– Complemento alla base

• Numeri razionali

Codifica con modulo e segno (MS)

Il modo più semplice di codificare i numeri interi, positivi e negativi, è quello di associare:


• Il primo bit : al segno (0=positivo, 1=negativo)

• I bit restanti : al valore assoluto del numero da rappresentare

Rappresentazione con modulo e segno (con 4 bit)Base duenaturale

Base dieci

0000 0

0001 1

0010 2

0011 3

0100 4

0101 5

0110 6

0111 7

Base dueMS (modulo e segno)

Base dieci

0000 +0

0001 +1

0010 +2

0011 +3

0100 +4

0101 +5

0110 +6

0111 +7


0111 7

1000 8

1001 9

1010 10

1011 11

1100 12

1101 13

1110 14

1111 15

0111 +7

1000 -0

1001 -1

1010 -2

1011 -3

1100 -4

1101 -5

1110 -6

1111 -7

Modulo e segno: osservazioniSemplice da codificare ma:

• Ha il difetto di duplicare lo zero(+0 e -0)

• La realizzazione in termini circuitali dei sommatori è particolarmente complessa

Ne consegue che:

Base dueMS (modulo e segno)

Base dieci

0000 +0

0001 +1

0010 +2

0011 +3

0100 +4

0101 +5

0110 +6

0111 +7


Ne consegue che:

• È stato poco utilizzato nel progettare i calcolatori

• Si è preferito adottare la rappresentazione in complemento alla base (complemento a 2)

0111 +7

1000 -0

1001 -1

1010 -2

1011 -3

1100 -4

1101 -5

1110 -6

1111 -7

Complemento a due con 4 bit - NoteBase due

Compl. a 2Base dieci

0000 +0

0001 +1

0010 +2

0011 +3

0100 +4

0101 +5

0110 +6

0111 +7

Si può notare che:

• la cifra più significativa rappresenta il segno, anche se nella definizione formale la cosa non è espressa esplicitamente come nella rappresentazione per modulo e segno

Base duenaturale

Base dieci

0000 0

0001 1

0010 2

0011 3

0100 4

0101 5

0110 6

0111 7


0111 +7

1000 -8

1001 -7

1010 -6

1011 -5

1100 -4

1101 -3

1110 -2

1111 -1

e segno• lo zero è rappresentato una

sola volta• c’è uno sbilanciamentotra la

quantità di numeri positivirappresentati (sono sette nell’esempio a 4 bit) e numeri negativi (sono 8)

0111 7

1000 8

1001 9

1010 10

1011 11

1100 12

1101 13

1110 14

1111 15

Confronto tra i sistemi di numerazione trattatiBase duenaturale

Base dieci

0000 0

0001 1

0010 2

0011 3

0100 4

0101 5

0110 6

0111 7

Base dueCompl. a 2

Base dieci

0000 +0

0001 +1

0010 +2

0011 +3

0100 +4

0101 +5

0110 +6

0111 +7

Base dueMS

Base dieci

0000 +0

0001 +1

0010 +2

0011 +3

0100 +4

0101 +5

0110 +6

0111 +7


0111 7

1000 8

1001 9

1010 10

1011 11

1100 12

1101 13

1110 14

1111 15

0111 +7

1000 -8

1001 -7

1010 -6

1011 -5

1100 -4

1101 -3

1110 -2

1111 -1

0111 +7

1000 -0

1001 -1

1010 -2

1011 -3

1100 -4

1101 -5

1110 -6

1111 -7

Costo ed efficienza di una codifica

• L’uso di una codifica rispetto ad un’altra può cambiare l’efficienza nella trattazione dei dati


• Il costo, ovvero il numero di bit necessari per la rappresentazione dei dati, è un parametro che viene utilizzato al momento della scelta della codifica da adottare

Algoritmi di compressione dati

• Tecniche di compressione dati vengono utilizzate per avere dei vantaggi dal punto di vista dei costi di memorizzazione e di


vista dei costi di memorizzazione e di trasmissione dati

Esempio di compressione dati

• Si supponga di avere un milione di caratteri da trasmettere avendo a disposizione, come alfabeto, il seguente insieme di simboli:

{A,C,G,T}• si supponga di associare a ciascun simbolo la successione

di due bit:


di due bit:A=00

C=01

G=10

T=11

• In questo caso i bit da trasmettere sono due milioni

Ricerca di un algoritmo di compressione

Si supponga che la frequenza dei quattro caratteri all’interno della successione abbia la seguente distribuzione:


A �� 50.0%

C �� 25.0%

G �� 12.5%

T �� 12.5%

Cambiando la codifica …

A=0

C=10

G=110

T=111


T=111… la lunghezza della successione risulta ora

inferiore ovvero pari a 1.750.000 bit

(resta da verificare l’univocità della decodifica)

Algoritmi fedeli e infedeli

Gli algoritmi di compressione dati possono essere di due tipi:


– Lossless (senza perdita di dati)

– Lossy (con perdita di dati)

Algoritmi lossless: rapporto di compressione

• Ci sono alcuni file per i quali non è accettabile che si perdano informazioni (file .doc, programmi, archivi, ecc.)


.doc, programmi, archivi, ecc.)

• I rapporti di compressione variano a seconda del contenuto del file:– 3:1 o piùper i file di testo

– 2:1 o menoper file diprogramma di tipobinario

Algoritmi lossy

• A volte si è disposti ad avere elevati rapporti di compressione purché venga garantita l’intelligibilità dell’informazione


garantita l’intelligibilità dell’informazione

• La percentuale di dati che si perde può essere controllata in base a un rapporto di compressione prescelto dall’utente

Codifica di un’immagine binaria


Immagini compresse

• Sfruttando il fatto che per l’occhio umano lievi cambiamenti di colore in punti contigui sono poco visibili e quindi possono essere eliminati, sono nati alcuni standard che effettuano la compressione delle immagini in maniera parametrizzata:


parametrizzata:

– Tiff (Tagget Image File Format)– Gif (Graphics Image Format – per immagini semplici)– Jpeg(Joint Photographers Expert Group) molto usato per

immagini fotografiche– BMP: basso livello di compressione, immagini ingombranti

Immagini vettoriali• Sono usate nel campo della progettazione meccanica, architettonica,

elettronica etc. • L’immagine è scomposta in forme geometriche astratte come poligoni,

cerchi etc.• Per descrivere una circonferenza bastano le coordinate del centro e il

raggio. Vantaggi:

• indipendenza dalla risoluzione del dispositivo di visualizzazione e stampa


• indipendenza dalla risoluzione del dispositivo di visualizzazione e stampa

• dimensioni ridotte delle immaginiSvantaggi

• non applicabile in modo semplice a fotografie e immagini complesse

Tipici formati vettoriali: • PostScript• PDF (Portable Data Format)

Animazioni e video compressi

• Si sfrutta il fatto che immagini successive hanno spesso molte parti uguali e quindi di ogni immagine possono essere memorizzate


ogni immagine possono essere memorizzate solo le differenze tra la precedente e la successiva

– Mpeg

File audio compressi

• Si sfrutta il fatto che per l’orecchio umano suoni a basso volume sovrapposti ad altri di volume maggiore sono poco udibili e quindi


volume maggiore sono poco udibili e quindi possono essere eliminati

–MPEG 1 Layer 3 (mp3)

Un’altra definizione dell’informatica

La scienza della rappresentazione e dell’elaborazione dell’informazione


dell’elaborazione dell’informazione

02 - Scienza dell'Informazione [modalit compatibilit ]dipsf.fisica.unina.it/~mastro/02 - Scienza...

Documents

Transcript of 02 - Scienza dell'Informazione [modalit compatibilit ]dipsf.fisica.unina.it/~mastro/02 - Scienza...