Reti logiche- la parte teorica

1

• Corso che insegna a progettare o a comprendere il funzionamento di componenti elettronici di bassa o media complessità

• Non ha prerequisiti e consente di ‘imparare a pensare’ in modi più legati all’hardware

• Oltre a fornire strumenti e metodi per la progettazione il corso propone anche basi teoriche imprescindibili e casi di approfondimento su alcune tematiche per rafforzare i concetti appresi

2

Specifiche ( Per esempio: “Voglio progettare

una rete che riconosca il passaggio di un veicolo sulla base delle rilevazioni di due sensori”)

Realizzazione circuitale( Per esempio: “Servono determinaticomponenti interconnessi secondoun determinato schema”)

S I N T E S I

A N A L I S I

Come rappresento ingressi ed uscite dei blocchi e come elaboro I dati?• Codifica ed aritmetica binaria

Come connetto fra loro i componenti in modo ottimale allo scopo di ottenere le funzionalità volute?• Reti combinatorie

Come memorizzo informazioni sullo stato della rete in modo da avere un comportamento adeguato alla storia degli ingressi? A quale velocità può funzionare la rete?• Reti sequenziali

La parte teorica

Codifica e Aritmetica Binaria

4

Informazione• L’informazione è un attributo di un messaggio• L’informazione è una entità misurabile

– L’unità di misura dell’informazione è il bit (da Binary digIT)• Un messaggio porta un bit di informazione se rappresenta una

scelta (cioè una riduzione di incertezza) tra due alternative possibili

• Il bit è una variabile che può assumere solo due valori: 1 e 0• Qualunque informazione può essere rappresentata usando bit

– Testo– Video– Audio– …

5

Codifica binariaL’operazione di traduzione di una informazione in una sequenza di “0” e “1” si chiama

CODIFICA BINARIA delle INFORMAZIONI

6

Con n bit rappresento 2n informazioni quindi Ninf ≤ 2n ed n ≥ 𝒍𝒐𝒈𝟐(Ninf). Dove n ed Ninf

sono ovviamente degli interi positivi

Quando creo una codifica ho due gradi di libertà: il numero di bit usati e la codifica, cioè

il modo di associarli alle informazioni

In una codifica più configurazioni di bit possono corrispondere alla stessa informazione,

o possono esserci configurazioni che non corrispondono alcuna informazione, ma non è

mai possibile che a più informazioni distinte corrisponda la stessa configurazione di bit

Il numero di codifiche cresce molto rapidamente col numero di bit utilizzati ad esempio è

possibile codificare con 4 bit le 10 cifre decimali in oltre 29 miliardi di modi.

Codice binario

z

51

a

m?

Minformazioni

0 0 0 ……..0

1 0 0 ……..0

0 1 0 ……..0

1 1 0 ……..0

0 0 1 ……..0

0 1 1 ……..1

1 1 1 ……..1

2n config.

0 0 1 ……..1

n.u.

Codice binario - Funzione dall’insieme delle 2n configurazioni di n bit ad un insieme di M informazioni (simboli alfanumerici, colori, eventi, stati interni, ecc.).Condizione necessaria per la codifica: 2n M

7

Proprietà di un codice

Il codice è una rappresentazione convenzionale dell’informazione.

La scelta di un codice è condivisa da sorgente e destinazioneed ha due gradi di libertà:

• il numero di bit (qualsiasi, a patto che sia 2n M )• l’associazione tra configurazioni e informazioniA parità di n e di M le associazioni possibili sono

C = 2n! / (2n-M)!

n = 1, M = 2 C = 2n = 2, M = 4 C = 24n = 3, M = 8 C = 64.320n = 4, M = 10 C = 29.000.000.000

8

Codici ridondanti e non ridondanti

• Un codice è detto ‘non ridondante’ se viene utilizzato il minimo numero possibile di bit per la codifica

• Nel caso in cui si utilizzino più bit rispetto al minimo si parla invece di codice ridondante

• I codici ridondanti sono utili in molti casi e fra questi:

• Quando ci si interfaccia agli utenti (display, input da tastiera)

• Quando si ha a che fare con la sicurezza dei dati. Se un dato viene parzialmente corrotto i bit rimanenti sono in grado di darmi informazioni sul fatto che si sia verificato un errore o addirittura su quale bit è stato modificato dai disturbi

Altri29

miliardidi

codicia

4 bit

0000000100100011010001010110011110001001

BCD

1111110011000011011011111001011001110110110011111111000011111111110011

7 segmenti

1000000000010000000000100000000001000000000010000000000100000000001000000000010000000000100000000001

uno su dieci

zerounoduetre

quattrocinque

sei setteottonove

Cifre decimali

10

Supponendo di voler codificare le cifre decimali ho infiniti modi in quanto posso scegliere un qualsiasi numero di bit ≥ 4 per farlo. A sinistra delle informazioni sono rappresentate la codifica BCD e riassunte tutte le altre codifiche non ridondanti. Fra le infinite codifiche ridondanti mettiamo in evidenza la codifica 7 segmenti (display) e la codifica 1 su 10, usata per alcune pulsantiere (v. calcolatrice)

Codice BCD

• Codice che rappresenta ciascuna cifra decimale con 4 bit

• k cifre decimali -> 4k bit

• Es.: nel caso di due cifre decimali: ventuno -> 0010 0001

0000000100100011010001010110011110001001

zerounoduetre

quattrocinque

sei setteottonove

11

Codice a 7 segmenti

• Codice ridondante utilizzato per visualizzare a display numeri decimali

• M=10, n=7>4

g

a

f b

e c

d

a b c d e f g

zero 1 1 1 1 1 1 0uno 0 1 1 0 0 0 0ecc.

12

La calcolatrice tascabile

Codiceridondante

per la visualizzazione

dei dati es 7 segmenti

Codiceridondante

per laintroduzione

dei dati edei comandi

Es: 1 su n

CodiceBinarioper la

rappresentazioneinterna

dei numeri

13

Anche per una semplice calcolatrice vengono impiegate

diverse codifiche. Una per l’immissione dei dati, una per la

lettura, ed una per il processamento

14

Distanza minima di un codice

Esempi: D(100,101) = 1; D(011,000) = 2; D(010,101) = 3

• I codici non ridondanti hanno DMIN=1. • I codici ridondanti possono avere DMIN > 1.

Distanza fra due configurazioni binarie di n bit:Numero di bit omologhi che hanno valore diverso.

Distanza minima di un Codice C: DMIN (C) - Valore minimodella distanza tra due qualsiasi delle configurazioni utilizzate.

15

Rappresentazione dei numeri

• Esterna: BCD, ASCII, 1 su 10, …

• Interna: Sistema di numerazione in base 2

16

Numeri in base B

(N)B = (an-1 .Bn-1 + …+ a0 .B

0 + a-1 .B-1 + a-2 .B

-2 + … a-m .B-m)

an-1 …… a0 , a-1 …… a-mai {0, 1, …., (B-1)}

𝒊=−𝒎

𝒏−𝟏

𝒂𝒊𝑩𝒊

• Quanto vale 11 in base 7? Ed in base 2?• E’ più grande :

• 100 in base 10 o in base 2?• 0.1 in base 10 o in base 2?

Definizione simbolica della rappresentazione posizionale dei numeri ad esempio un

numero con n=4 cifre a sinistra della virgola ed m=2 cifre a destra potrebbe essere 1224,82.

Attenzione, data una base B (ad esempio 10), ci sono solo B (ad esempio 10) cifre distinte

Il valore di un numero in notazione posizionale dipende dalle cifre (chiamate coefficienti),

dalla loro posizione,e dalla base. Ciascun coefficiente viene moltiplicato per la base elevata

ad un esponente pari alla posizione. La stessa formula è riscritta in breve sotto

17

Il sistema di numerazione in base 2(il caso dei numeri naturali < 2n)

bn-1bn-2 b1 b0

n bit

(N)2 = bn-1 .2n-1 + bn-2 .2

n-2 + …+ b0 .20

N10 N2 N10 N2

0 0000 8 10001 0001 9 10012 0010 10 10103 0011 11 10114 0100 12 11005 0101 13 11016 0110 14 11107 0111 15 1111

In base due ci sono solo due cifre distinte (dette bit)

per rappresentare tutti I numeri secondo la notazione

posizionale.

I numeri in base due sono rappresentati con

configurazioni più lunghe di bit rispetto alle

equivalenti in base 10, il rapporto massimo fra le

lunghezze è fra 3 e 4 (es: 999 lo rappresento con 3

cifre decimali, ma ho bisogno di 10 bit in

numerazione binaria)

Nel nostro corso il numero di bit utilizzato è

solitamente fissato, quindi esisteranno degli intervalli

di rappresentabilità dei numeri oltre ai quali i numeri

sono non rappresentabili

Conversione da base 2 a base 10(N)10 = (bn-1 .2

n-1 + bn-2 .2n-2 + … + b1 .2

1 + b0 .20)10

Conversioni da base 2 a base 10 e viceversadi numeri naturali

ESEMPIO: 1001100 +2 +4 +0 +0 +

32 =38

Applico la definizione di notazione posizionale dei numeri

18

19

Conversione di un numero naturale N da base 10 a base 2

i = 0A = N

fineSI

B = (A / 2) 10 = (Qi + Ri2-1) 10

A = Qi

bi = Ri

A = 0i = i+1NO

ESEMPIO: 131131/2 = 65 + 1.0,565/2 = 32 + 1.0,532/2 = 16 + 016/2 = 8 + 08/2 = 4 + 04/2 = 2 + 02/2 = 1 + 01/2 = 0 + 1.0,510000011

Attenzione il metodo funziona in generale (anche per altre coppie di basi) e solo per la parte intera, per la parte decimale c’è un algoritmo separato!!

20

Altre rappresentazioni di numeri binari

• Sistema esadecimale: B =16 cifre: 0,1,..,9,a,b,c,d,e,fcodice binario: 0 = 0000, 1 = 0001, …, f = 1111n° di bit per cifra: 4 perché 16 = 24

Non si possono separare i bit per basi che non siano esponenti di 2 come ad esempio la base 10

ESEMPIO: 11000100 1100-0100 c4 =

Nei calcolatori gli indirizzi in memoria sono composti da 32 bit, ma possono essere rappresentati semplicemente con 8 cifre esadecimali

0xc4 c4h

Le operazioni aritmetiche usando i bit

21

Partiamo da operazioni fra interi positivi.

Con n bit rappresento i numeri fra 0 e 2n -1

Si procede come per quelle in base 10, che abbiamo imparato da piccoli, ma occorre

ovviamente ricordarsi che possono essere usati solo ‘0’ ed ‘1’ e che la base di riferimento è 2

Nelle somme in colonna si ha riporto se si sommano almeno due 1 fra loro, nelle sottrazioni

in colonna vale il meccanismo del prestito, ma esso vale 2 e non più 10 come nella base che

conosciamoEsempi a 5 bit

10010 +

00111 =

11001

10010 +

10111 =

01001Risultato non rappresentabile,

occorre un bit aggiuntivo

10010 -

00111 =

01011

18 + 7 = 25 18 - 7 = 11

18 + 23 = ? In quanto 41 > 31

Insieme:

20 + 11;

4 + 1;

29 - 10;

15 - 3

Numeri relativi: rappresentazione segno-valore assoluto

N [-(2n-1 - 1), +(2n-1 - 1)]

bn-1 bn-2 b1 b0

n bit

segno (0: positivo, 1: negativo)

valore assoluto|N| = (bn-2 .2n-2 + …+ b0 .2

0)

• Semplici da leggere (per l’uomo)• Due rappresentazioni di 0• Operazioni difficili

22

Il bit più a sinistra, detto anche bit più significativo, viene adibito alla rappresentazione del segno, quindi per la rappresentazione del valore assoluto del numero restano n – 1 bit. Questo tipo di rappresentazione non è ottimale per l’esecuzione di operazioni all’interno di una CPU e quindi, nei calcolatori si preferisce usare la codifica in complemento a 2 per rappresentare i numeri interi negativi

Con modulo e segno rappresento i numeri che vanno da (-2n -1 -1) a (2n-1 -1) estremi inclusi

n-1

23

In complemento a due il bit più significativo va considerato con il suo valore posizionale, ma negato.

Posso rappresentare 1 numero in più perché non ho due rappresentazioni per lo 0.

A sinistra le rappresentazioni in complemento a due dei numeri da -8 a 7

Proprietà della rappresentazione in complemento a 2

• eseguendo complement and increment su A si ottiene -A

• A+B con rappresentazione in complemento a due restituisce la somma algebrica:

Siano A e B due numeri nella rappresentazione in complemento a 2:

• eseguendo A + 2(B) si ottiene A - B

1 0 0 1

1 1 0 1 +

1 1 0 0 =

A = -3

B = -4

-7 1 1 1 1

1 1 0 0 +

0 0 1 1 =

A = -4

B = +3

-1 0 0 0 1

1 1 0 0 +

0 1 0 1 =

A = -4

B = +5

+1

N.B. - per sommare o sottrarre due numeri relativi espressi in complemento a 2 è sufficiente eseguire una somma quindi ho bisogno solo di componenti che sommano e non di componenti che sottraggono.

A: 0 0 0 1 (+1)1 1 1 0 +

1 2A: 1 1 1 1 (-1)

1 0 0 1 (-7)0 1 1 0 +

10 1 1 1 (+7)

24

complement

increment