Evoluzione della tecnologia informatica: dal bit ad internet, Marengo, Scalera - Definizioni

CODIFICA BINARIA DEI DATI:

• Sistema di codifica grandezza e segno: permette di rappresentare i numeri interi

positivi e negativi. La parola di memoria è infatti divisa in due parti:

il primo bit rappresenta il segno (0 per i numeri positivi, 1 per quelli negativi);

o tutti gli altri bit sono utilizzati per la rappresentazione del valore assoluto del

o numero.

Esempio: si vuole rappresentare i numeri +23 e -23 utilizzando 8 bit.

Conversione del numero decimale |23| in binario 10111

Codifica del numero +23 in 8 bit 00010111

Codifica del numero -23 in 8 bit 10010111

• Sistema di codifica complemento a uno: anche questo sistema permette di rappre-

sentare i numeri interi positivi e negativi.

Esempio: si vuole effettuare in binario, con il numero minimo di bit, la seguente ope-

razione aritmetica -10-11=-21 utilizzando il sistema di codifica complemento a uno.

Innanzitutto, per individuare il numero minimo di bit, bisogna convertire nel sistema

di numerazione binario il numero più grande tra quelli che compaiono

nell’operazione: il numero di bit necessari per rappresentarlo, aumentato di 1, costi-

tuirà il numero minimo di bit necessari per la realizzazione dell’operazione.

Calcolo del numero 21 in binario 10101

Numero di bit per rappresentare 21 5

Numero di bit minimo per realizzare l’operazione 5+1=6

infatti, con 5 bit, l’intervallo dei valori rappresentabili è:

5 5

[-(2 )+1;2 -1] = [-31;+31]

Realizziamo quindi l’operazione con 6 bit

Conversione del numero 10 in binario 1010

Calcolo del numero +10 in complemento a uno 001010

Calcolo del numero -10 in complemento a uno 110101

Conversione del numero 11 in binario 1011

Calcolo del numero +11 in complemento a uno 001011

Calcolo del numero -11 in complemento a uno 110100

Effettuare l’operazione -10-11 utilizzando 6 bit

-31 16 8 4 2 1 Pesi

1 0 1 0 0 Riporti

1 1 0 1 0 1 + -10

1 1 0 1 0 0 = -11

1 1 0 1 0 0 1 + Risultato

1 = Il riporto si somma

1 0 1 0 1 0

Verifica:

1•(-31) + 0•16 + 1•8 + 0•4 + 1•2 + 0•1 = -31 +8 +2 = -31 +10 = -21

• Sistema di codifica complemento a due: anche questo sistema permette di rappre-

sentare i numeri interi positivi e negativi.

Esempio: si vuole effettuare in binario, con il numero minimo di bit, la seguente ope-

razione aritmetica -10-11=-21 utilizzando il sistema di codifica complemento a due.

Calcolo del numero 21 in binario 10101

Numero di bit per rappresentare 21 5

Numero di bit minimo per realizzare l’operazione 5+1=6

infatti, con 5 bit, l’intervallo dei valori rappresentabili è:

  8  

5 5

[-(2 );2 -1] = [-32;+31]

Realizziamo quindi l’operazione con 6 bit

Conversione del numero 10 in binario 1010

Calcolo del numero +10 in complemento a uno 001010

Calcolo del numero -10 in complemento a uno 110101+1 = 110110

Conversione del numero 11 in binario 1011

Calcolo del numero +11 in complemento a uno 001011

Calcolo del numero -11 in complemento a uno 110100+1 = 110101

Effettuare l’operazione -10-11 utilizzando 6 bit

-32 16 8 4 2 1 Pesi

1 0 1 0 0 Riporti

1 1 0 1 1 0 + -10

1 1 0 1 0 1 = -11

1 0 0 1 0 1 1 + Risultato

Il riporto si trascura

Verifica:

1•(-32) + 0•16 + 1•8 + 0•4 + 1•2 + 1•1 = -32 +8 +2 +1 = -32 +11 = -21

• Sistema di codifica BCD (Binary Coded Decimal): è il sistema decimale codificato in

binario, secondo il quale ogni cifra decimale e il segno del numero occupano cia-

scuno 4 bit.

• Sistema di codifica floating point: sistema con cui è possibile rappresentare i numeri

reali; in tale sistema infatti i numeri vengono trasformati in forma normalizzata, ven-

gono cioè espressi come prodotti di due fattori:

il primo fattore (mantissa) è un numero, in valore assoluto, maggiore di 0 e

o minore di 1;

il secondo fattore (caratteristica) è una potenza di 2.

o

Inoltre, normalmente una rappresentazione di questo tipo occupa 4 byte, ovvero 32

bit.

Esempio: si vuole rappresentare il numero -123,4 in floating point.

3

Il numero normalizzato è -0,1234*10

Per cui i 4 byte assumeranno i seguenti valori:

1° byte:

o bit 1 1 segno negativo della mantissa

bit 2 0 segno positivo dell’esponente

bit 3-8 000011 valore dell’esponente, 3.

2°-4° byte:

o 00000000 00000100 11010010 valore della mantissa,1234.

I quattro byte avranno quindi la seguente configurazione:

10000011 00000000 00000100 11010010

• Codifica dei caratteri:

codice EBCDIC, acronimo di Extended Binary Coded Decimal Interchange

o Code (codice esteso di scambio decimale codificato in binario), utilizzato dai

calcolatori di grandi dimensioni;

codice ASCII, acronimo di American Standard Code for Information Inter-

o change (codice americano standard per lo scambio di informazioni), utilizzato

sui mini e personal computer.

  9  

C 3 – L’ B

APITOLO ALGEBRA DI OOLE

PROPOSIZIONI: frasi affermative che si differenziano dalle altre perché possono essere

vere o false. Una proposizione non ulteriormente scomponibile è detta proposizione ele-

mentare; ma se a questa si aggiungono i cosiddetti connettori logici, rappresentati dai

∧, ∨

simboli ~, (rispettivamente not, e, o), si possono ottenere nuove proposizioni compo-

ste.

VARIABILE BOOLEANA: entità che può assumere solo due valori (1 o 0; Vero o Falso; On

o Off).

OPERAZIONI SULL’INSIEME DELLE VARIABILI BOOLEANE: le variabili booleane indi-

pendenti sono “legate” tra loro mediante operatori booleani, questi ultimi regolati da una

tabella chiamata “tabella di verità”, divisa in due sezioni: la sezione input (costituita da un

numero di colonne pari al numero di variabili indipendenti presenti nella funzione boolea-

na), e la sezione output (costituita sempre da una colonna); inoltre le righe della tabella di

n

verità dovranno essere pari a 2 dove n è il numero di variabili indipendenti.

Esempio: sia F = (A,B) una funzione booleana in cui sono presenti due variabili indipen-

denti legate tra loro da operatori booleani (qui non specificati).

Input Output

A B F

0 0

0 1

1 0

1 1

Sulle variabili booleane si possono eseguire sei operazioni elementari:

• operazione NOT: si applica a una sola variabile booleana; quindi se C=NOT(A) = A,

la variabile booleana C assumerà valore opposto ad A;

A C

0 1

1 0

• operazione OR: si può indicare anche con il termine “somma logica” e si applica a

∨

due variabili booleane; quindi se C = OR(A,B) = A + B = A B, il valore di C risulte-

rà vero nel momento in cui almeno una delle due variabili indipendenti A e B assu-

me valore vero, mentre sarà falso solo quando le due variabili booleane A e B sono

contemporaneamente false;

A B C

0 0 0

0 1 1

1 0 1

1 1 1

• operazione AND: si può indicare anche con il termine “prodotto logico” e si applica

• ∧

a due variabili booleane; quindi se C = AND(A,B) = A B = A B, il valore di C ri-

sulterà vero nel momento in cui le variabili indipendenti A e B sono contempora-

neamente vere, mentre sarà falso quando almeno una delle due variabili indipen-

denti assume valore falso;

A B C

0 0 0

0 1 0

1 0 0

1 1 1

• operazione NOR: si ottiene combinando le operazioni NOT ed OR; quindi se

  10  

C = NOR(A,B) = NOT(OR(A,B)) = A + B, il valore di C risulterà vero nel momento in

cui le variabili indipendenti A e B sono contemporaneamente false; mentre assume-

rà valore falso negli altri tre casi;

A B A + B C

0 0 0 1

0 1 1 0

1 0 1 0

1 1 1 0

• operazione NAND: si ottiene combinando le operazioni NOT e AND; quindi se

•

C = NAND(A,B) = NOT(AND(A,B)) = A B, il valore di C risulterà falso nel momento

in cui le variabili indipendenti A e B sono contemporaneamente vere; mentre assu-

merà valore vero negli altri tre casi; •

A B C

A B

0 0 0 1

0 1 0 1

1 0 0 1

1 1 1 0

• operazione OR ESCLUSIVO: si applica a due variabili booleane; quindi se

⊕

C = XOR(A,B) = A B, il valore di C sarà vero nel momento in cui i valori delle due

variabili indipendenti A e B sono diversi e falso quando assumono valore uguale.

A B C

0 0 0

0 1 1

1 0 1

1 1 0

PROPRIETÀ DELL’ALGEBRA BOOLEANA: sono dimostrabili con il metodo delle tabelle

di verità; la proprietà infatti risulta verificata quando la colonna dell’output del primo mem-

bro è uguale a quella del secondo membro.

• Proprietà commutativa:

A + B = B + A

• •

A B = B A

⊕ ⊕

A B = B A

• Proprietà associativa:

A + (B + C) = (A + B) + C

• • • •

A (B C) = (A B) C

⊕ ⊕ ⊕ ⊕

A (B C) = (A B) C

• Proprietà distributiva:

• •

A + (B C) = (A + B) (A + C)

• • •

A (B + C) = (A B) + (A C)

TEOREMI DELL’ALGEBRA BOOLEANA:

• A + 0 = A

• •

A 1 = A

• A + 1 = 1

• •

A 0 = 0

• A + A = A

• •

A A = A

• ⊕

A A = A

• A + A = 1

• •

A A = 1

  11  

• A = A

• •

A + B = A B (1° Teorema di De Morgan)

• •

A B = A + B (2° Teorema di De Morgan)

FUNZIONI BOOLEANE: espressioni algebriche che legano una variabile (dipendente) ad

altre (indipendenti) connesse tra loro tramite operatori booleani. La funzione booleana è

governata da cinque regole di priorità delle operazioni:

• parentesi ();

• NOT, NAND, NOR;

• AND;

• XOR;

• OR. • ⊕ •

Esempio: risolvere la funzione booleana F = A B + C B A.

COLONNE INPUT COLONNE INTERMEDIE COLONNA

OUTPUT

1 2 3 4 5

• • • ⊕ •

A B C B F

A B A B B A C B A

0 0 0 0 1 1 0 0 1

0 0 1 0 1 1 0 1 1

0 1 0 0 1 0 0 0 1

0 1 1 0 1 0 0 1 1

1 0 0 0 1 1 1 1 1

1 0 1 0 1 1 1 0 1

1 1 0 1 0 0 0 0 0

1 1 1 1 0 0 0 1 1

In una funzione booleana si chiama:

• termine prodotto, ogni prodotto di due o più variabili booleane;

• termine somma, ogni somma di due o più variabili booleane;

• termine canonico, un termine prodotto o un termine somma che contiene tutte le va-

riabili da cui essa dipende.

Inoltre, la rappresentazione algebrica di una funzione booleana si dice:

• in forma normale, se è espressa come somma di termini