Rappresentazione Rappresentazione eeMemorizzazione dei DatiMemorizzazione dei Dati

CdL in Matematica (Laurea Triennale)Facoltà di Scienze MM.FF.NN.

Università di Catania

Giuseppe NicosiaGiuseppe Nicosia

Bit e Bit e loro Memorizzazioneloro Memorizzazione

Definizioni•• AlgoritmoAlgoritmo: una sequenza finita ordinata di passi non

ambigui ed eseguibili che definiscono un'attività dilunghezza finita.

•• ProgrammiProgrammi: la rappresentazione di un algoritmocompatibile con la macchina.

•• SoftwareSoftware: i programmi, e gli algoritmi cherappresentano (es. sistemi operativi).

•• HardwareHardware: dispositivi fisici.

Lo sviluppo di algoritmi è quindi un obiettivofondamentale dell’informatica.

Individuare un algoritmo per risolvere ilIndividuare un algoritmo per risolvere ilproblema equivale a risolvere il problema stessoproblema equivale a risolvere il problema stesso.

Operazioni BooleaneGeorge Boole (1815-1864)

• I computer rappresentano le informazionicome sequenze di bit (bbinary digitit o cifrabinaria o unità binaria).

• Operazioni Booleane:– AND;– OR;– XOR (eXclusive OR, OR esclusivo);– NOT.

• Un dispositivo che, dati i valori di ingresso,produce l’uscita di un’operazione booleana èchiamato porta logica.

Operazioni Booleane1.1. P AND QP AND Q => è vera solo quando P e Q sono

vere (dove P e Q rappresentano asserzioni, adesempio “Questa è una frase.”);

2.2. P OR QP OR Q => è vera quando almeno una delle dueè vera;

3.3. P XOR QP XOR Q => è vera quando uno dei due è vera el’altro è falsa (“o P oppure Q ma nonentrambi”);

4.4. NOT PNOT P => assume il valore di verità opposto a P.

Operazioni Booleane (2/2)

Rappresentazioni delle Porte LogicheAND e OR

Rappresentazioni delle Porte LogicheXOR e NOT

Un semplice Circuito flip-flop

L ' i m p u l s ot e m p o r a n e os u l l ' i n g r e s s osuperiore ha portatoil flip-flop a 1, equesto valore resteràtale anche dopo chel'ingresso superioresarà riportato a 0.

Esempio (1/3)

Esempio (2/3)

Esempio (3/3)

–Analogamente, se siporta temporaneamentea 1 l'ingresso inferiore,si forza l'uscita del flip-flop a diventare 0 e arimanere tale anchedopo che il valoredell'ingresso inferioresarà riportato a 0.–Memorizzazione di bit.

Un altro modo di costruire un flip-flop

Rappresentazione delleRappresentazione delleInformazioni su di Informazioni su di unun

calcolatorecalcolatore

Rappresentazione delle Informazioni

• L’informazione viene rappresentatamediante sequenze di bit.

• Ogni parola, o testo, o dato numerico,o immagine, o suono viene codificatocome configurazioni di bit.

Rappresentazione dei Valori Numerici (1/2)• La notazione binarianotazione binaria è un modo di

rappresentare i valori numerici usando solo lecifre 0 e 1, anziché tutte le cifre del sistemadecimale.

• Attraverso 1 bit è possibile rappresentare dueinformazioni (una con 0 ed una con 1).

• Utilizzando una sequenza di 2 bit possiamoavere quattro codifiche distinte.

• Analogamente, utilizzando 3 bit possiamorappresentare otto informazioni differenti.

Rappresentazione dei ValoriNumerici (2/2)

• Riassumendo:– 1 bit => 2=21 informazioni;– 2 bit => 4=22 informazioni;– 3 bit => 8=23 informazioni;In generale:– N bit =>2N informazioni.

•• EsempioEsempio:Per rappresentare 5757 informazioni è

necessario utilizzare una sequenza di 6 bit.

Rappresentazione Binaria (1/2)

Nel sistema di numerazionebinario i numeri vengonocodificati usando le duecifre ““11”” e ““00”” ed unoschema posizionale in cuisi usa la base 2base 2 al postodella base 10base 10.

Utilizzando questa codificaUtilizzando questa codificaè è possibile rappresentarepossibile rappresentarequalunque numero interoqualunque numero interopositivopositivo..

Decoding the binaryrepresentation 100101

0

Rappresentazione Binaria (2/2)

Considerato il numerale:ccnn ccn-1n-1 …… c c11 c c00

in cui ogni ““ccii”” è la cifra “0” o “1”,rappresenterà il numero:

cc00*2*200 + c + c11*2*211 + + …… + c + cn-1n-1*2*2n-1n-1 + + ccnn*2*2nn

Decodifica di rappresentazioni Binarie

Esempi:Esempi:Il numerale ““10111011”” denota il numero:

1*21*200 + 1*2 + 1*211 + 0*2 + 0*222 + 1*2 + 1*233 = 1110

il numerale ““100101100101”” denota il numero:1*21*200 + 0*2 + 0*211 + 1*2 + 1*222 + 0*2 + 0*233 + 0*2 + 0*244 + 1*2 + 1*255 = 3710

il numerale ““10100011010001”” denota il numero:1*21*200 + 0*2 + 0*211 + 0*2 + 0*222 + 0*2 + 0*233 + 1*2 + 1*244 + 0*2 + 0*255 + 1*2 + 1*266 = 8110

Conversione dalla base 10 alla base 2Bisogna dividere la base 10 per 2 fino a quando ilquoziente intero della divisione è zero.

1resto0=1/20resto1=2/21resto2=5/20resto5=10/21resto10=21/21resto21=43/20resto43=86/20resto86=172/21resto172=345/2Esempio: Esempio: consideriamo il

numerale 34510 ecerchiamo larappresentazione binariacorrispondente:

Leggendo i resti dal bassoLeggendo i resti dal bassoverso lverso l’’alto si ha laalto si ha larappresentazione binariarappresentazione binariadel numero del numero 34534510 10 ..

Un Algoritmo per trovare larappresentazione binaria di un

intero positivo

Operazioni sui numeri binari• Lo stesso procedimento che utilizziamo per

i numeri decimale può essere utilizzato perle operazioni di somma in base due.

• L’unica differenza è che si devonoeffettuare i riporti quando la somma superail valore “1”.

• Regole di base:

Esempi di Somma Binaria

011001 +010101 =101110

25 +21 =46

01110101 +01101101 =11100010

117 +109 =226

0101 +0011 =1000

5 +3 =8

Esercizi sul Sistema Binario

• Convertire le seguenti rappresentazioni binarienel formato in base 10 equivalente:

a.101010, b. 100001, c. 10111, d. 0110, e. 11111• Convertire le seguenti rappresentazioni in base

dieci nel formato binario equivalente:a. 32, b. 64, c. 96, d. 15, e. 27

• Eseguire le seguenti somme in binario:a.32 + 27, b. 96 +15, c. 64 + 11

Complemento Complemento a duea due

Complemento a due+3 = 00000011+2 = 00000010+1 = 00000001+0 = 00000000 -1 = 11111111 -2 = 11111110 -3 = 11111101

Notazione in Complemento a Due•• Complemento Complemento a duea due viene utilizzato per rappresentare

ogni intero positivo e negativo.•• RegoleRegole:

– Il bit più significativo (più a sinistra) rappresenta il segno delnumero: “0” positivo, “1” negativo;

– La rappresentazione di un numero negativo si ottiene in trepassi:

• Si rappresenta in complemento a due il numero positivo con lo stessovalore assoluto del numero negativo da codificare;

• Si invertono tutti i bit in tale rappresentazione, cioè si mette “1” dovec’e’ “0” e viceversa;

• Si somma 1 al LSB del risultato ottenuto al passo precedente.

Esempio di Notazione in Complemento a Due:da +5 a -5

Supponiamo di voler codificare in formabinaria il numero “-5”:

1) La rappresentazione in complemento adue del numero “+5” è 0101;

2) Invertendo tutti i bit si ottiene: 1010;3) Sommando “1” si ottiene 1011,

rappresentazione in complemento adue di “-5”.

Notazione in Complemento a Due

• Per effettuare la conversione inversa, si procedecome segue:– Se il primo bit è “0” il numero è positivo;– Altrimenti:

• Si ignora il primo bit;• Si invertono i restanti bit;• Si somma “1” al numero ottenuto al passo precedente per

ottenere il valore assoluto del numero negativo.

Esempio di Notazione inComplemento a Due: da -5 a +5

Consideriamo il numero binario incomplemento a due 1011= -5.

1. Si esclude il primo bit (011);2. Invertendo si ottiene: 100;3. 1002 = 410;4. 4 + 1 = 5.Risultato finale “5”.

Sistema di Notazione inComplemento a Due

Caso speciale 1 0 = 00000000Bitwise not 11111111Add 1 to LSB +1Result 1 00000000Overflow is ignored, so:- 0 = 0

Caso speciale 2-128 = 10000000bitwise not 01111111Add 1 to LSB +1Result 10000000So:-(-128) = -128 !Monitor MSB (sign bit)It should change during negation

Somma Binaria con Notazione inComplemento a Due (1/2)

0111 +1011 =0010

+7-5 =+2

0010 +1011 =1101

+2-5 =-3

Il problema della sottrazione è uguale al problema dell’addizione.

Il problema Il problema ““7 - 57 - 5”” equivale al problema equivale al problema ““7 + (-5)7 + (-5)””..

Problema di overflowProblema di overflow11

Somma Binaria con Notazione inComplemento a Due (2/2)

Esercizi sul Sistema Binario conNotazione in Complemento a Due

• Convertire le seguenti rappresentazioni incomplemento a due:

a.00011, b.01111, c.11100, d.11010, e.00000, f.10000a.00011, b.01111, c.11100, d.11010, e.00000, f.10000

• Convertire le seguenti rappresentazioni in basedieci:

a. 6, b.-6, c.-17, d.13, e.-1• Eseguire le seguenti somme:

a.0101 + 0010, b. 1110 + 0011, c. 1010 + 1110

Rappresentazione Rappresentazione in in NotazioneNotazioneEsadecimale di numeri positiviEsadecimale di numeri positivi

Notazione Esadecimale (1/3)

• Le sequenze di lunghe stringhe di bit(flussi di bit) sono facilmente soggette aderrori.

• La notazione esadecimale si basa sul fattoche le configurazioni di bit hannolunghezza multipla di quattro.

• La notazione esadecimale impiega ununico simbolo per esprimere quattro bit.

Notazione Esadecimale (2/3)

Notazione Esadecimale (3/3)EsempiEsempi::• 10110101 => B5

A4C81010010011001000 =>

Esercizi:Esercizi:Utilizzare la notazione esadecimale per rappresentare le

seguenti configurazioni di bit: 0110101011110010 –111010000101010100010111 – 01001000

Quali configurazioni di bit sono rappresentate dalleseguenti configurazioni esadecimali: 5FD97 – 610A –

ABCD – 0100

Problema dell’Overflow• Il problema dell’overflow si presenta

quando il valore da rappresentare è esternoall’intervallo di valori che possono essererappresentati.

• Es. 5 + 4 = 9 utilizzando 4 bit.• Con la notazione in complemento a due, si

ottiene sommando due valori positivi o duenegativi.

• Oggi si utilizzano configurazioni di 3232 bit bit(2.147.483.647)(2.147.483.647) per memorizzare i valori.

Rappresentazione del Testo (1/4)• In un calcolatore, un testo viene presentato come una lunga

stringa (sequenza) di bit.• Il metodo di codifica più utilizzato è il codice codice ASCIIASCII

(AAmerican merican SStandard tandard CCode for ode for IInformation nformation IInterchangenterchange).• L’insieme dei simboli comunemente usati può essere

codificato usando 7 7 bitbit, che permettono la rappresentazionedi 2277=128=128 configurazioni differenti (76 conf. nel codiceoriginario)

• Oggi si usa il formato esteso a 8 bit:– Vantaggi: un codice che si adatta perfettamente alle celle

di memoria, altre 128 configurazioni da usare perincludere altre informazioni non usate nel codice ASCIIiniziale

– Svantaggi: queste 128 configurazioni vengono interpretatein modo diverso dai diversi produttori SW/HW, ovveroproblemi di compatibilità.

Rappresentazione del Testo (2/4)

• Sebbene 77 bit bit siano sufficienti per codificarel’insieme dei caratteri, oggi il codice ASCIIstandard usa 88 bit bit.

Rappresentazione del Testo (3/4)

EsempioEsempio: : sia data la seguente sequenza:011010010110110000000000011100000110111100101110011010010110110000000000011100000110111100101110

Il testo che essa codifica può essere ottenuto, dividendo lasequenza in gruppi di 88 bit bit e assegnare ad ogni gruppo ilcorrispondente carattere nella tabella tabella ASCIIASCII.

01101001 01101100 00000000 01110000 01101111 0010111001101001 01101100 00000000 01110000 01101111 00101110 i l p o . i l p o .

Rappresentazione del Testo (4/4)

EsempioEsempio:: siano dati i numeri 2 e 5, lacodifica nella tabella ASCII è:

2 = 00110010, 5 = 001101012 = 00110010, 5 = 00110101il risultato che si ottiene dalla somma è:

001100100011001000110101001101010110011101100111 ““gg””

Rappresentazione del testo:Unicode e ISO

• Codice Unicode: usa una codifica univoca di16 bit (65536 configurazioni), quanto basta arappresentare i simboli più comuni cinesi egiapponesi.

• Codice ISO: 32 bit, in potenza miliardi disimboli.

Rappresentazione delle Immagini (1/3)• Le tecniche più diffuse per rappresentare le

immagini vengono classificate in due categorie:tecniche bitmap e tecniche vettoriali.

• L’immagine viene considerata come una matrice dipunti. Ogni punto è detto pixelpixel (picture elementpicture element) edassume il valore di “0” o “1” per un’immagineB/W.

Si usa Si usa la la convenzione che convenzione che i pixel i pixel siano ordinati dal siano ordinati dal bassobassoverso verso ll’’alto alto e e da sinistra da sinistra verso verso destradestra.

• Nelle immagini a colori ogni pixel può essererappresentato da una combinazione di bit, cheindicano il colore corrispondente.

Rappresentazione delle Immagini (2/3)• Il colore di ogni pixel viene registrato secondo tre

componenti: rossorosso, verdeverde e blue blue (ogni componente unbyte)

•• RisoluzioneRisoluzione: indica la precisione con cui vieneeffettuata la suddivisione di un’immagine in pixel (es.una griglia di 640x480 pixel).DomandaDomanda: quanti bit servono per rappresentare 256colori, per ciascun pixel? 8 bit => 28 bit => 288 = 256 = 256

La rappresentazione di un’immagine mediante lacodifica dei pixel richiede una quantità notevole dispazio di memoria (es. 8 bit per pixel con risoluzione(es. 8 bit per pixel con risoluzione640x480 => 307200 x 8 bit => 2457600)640x480 => 307200 x 8 bit => 2457600).

Rappresentazione delle Immagini (3/3)• Svantaggio tecniche bitmap: difficilmente una immagine può essere

convertita in una dimensione qualsiasi.• Le tecniche vettoriali consentono di risolvere il problema della

scalatura:– l'immagine è rappresentata da un insieme di linee e curve.– Tale rappresentazione mantiene i dettagli relativi al modo in cui

le linee e le curve sono tracciate dal dispositivo.– Font scalabili: i vari font (tipi di caratteri) disponibili sulle

stampanti e sui monitor sono codificati con tecniche vettoriali.– Esempi: True type (Microsoft e Apple) simboli mediante

formule matematiche; Postscript (Adobe Systems) caratteri edati grafici più generali; CAD (computer aid design).

• Le tecniche vettoriali non sono in grado di produrre immagini diqualità fotografica, ecco perchè nelle videocamere digitali di oggisono utilizzate tecniche bitmap.

3

Rappresentazione dei suoni• Metodo generico: campionare l'ampiezza dell'onda sonora a

intervalli regolari e nel registrare le serie di valori numerici ottenuti.• Frequenza di campionamento di 8000 campioni al secondo.

Rappresentazione dei suoni• Gli attuali CD musicali sono realizzati con una frequenza di

campionamento di 44.100 campioni al secondo. Ogni campione èrappresentato con 16 bit (32 bit per le registrazioni stereo).

• Segue, che ogni secondo di musica registrata in stereo richiede piùdi un milione di bit.

• Sistema di codifica alternativo, più economico, MIDI (MusicalInstrument Digital Interface)

– MIDI codifica lo strumento che deve eseguire una determinatanota per un certo periodo.

– Questo implica che una registrazione MIDI possa risultaremolto diversa se eseguita su sintetizzatori differenti.

– Codifica meno costosa in termini di bit.

Memorizzazione dei DatiMemorizzazione dei Dati

La La Memoria PrincipaleMemoria Principale

Organizzazione della Memoria (1/4)• Un qualunque calcolatore è costituito da un

numero elevato di circuiti flip-flop, in gradodi memorizzare un bit.

• Sono organizzati in unità dette cellecelle, o, oparole, parole, con una dimensione tipica di 8 bit.

•• 8 bit = 1 byte, 8 bit = 1 byte, ovvero ovvero una cella una cella un byteun byte• Data una sequenza di bit:

bit piùbit piùsignificativosignificativo

bit menobit menosignificativosignificativo

Organizzazione della Memoria (2/4)• La memoria principale è una sequenza di sequenza di bytebyte,

ciascuna caratterizzata da un indirizzoindirizzo.• L’indirizzoindirizzo, o locazionelocazione, di un byte nel

dispositivo è il suo numero d’ordine nellasequenza, a partire da 0.

• Un tale sistema di indirizzo consentel’identificazione univoca di ciascuna cella.

• La memoria è divisa in celle di 1 byte => perarchiviare una stringa di 16 bit si utilizzano 22celle di memoria celle di memoria consecutiveconsecutive.

Organizzazione della Memoria (3/4)

Gli indirizzi sono espressi mediante numeri interinumeri interi oin notazione binarianotazione binaria.

Organizzazione della Memoria (4/4)•• Memoria Memoria RAMRAM (RRandom AAccess MMemory): indica che

è possibile accedere individualmente ad ogni cella ininordine casualeordine casuale e con accesso direttoaccesso diretto.

• Il tempo necessario per accedere ad una cella dimemoria è lo stesso indipendentemente dalla posizionedella cella nella sequenza.

• Operazioni sulle celle di memoria: lettura e scrittura.

Il numero totale di celle progettate è una potenza di 2.

N.B.:N.B.:

1K= kilobyte = 210=1024 ~ 103, 1M = 220=1KK, 1G= 230=1KM

Es.Es. 4 KB = 4x1024 = 4096 byte (4096 celle di memoria)