-1.... Livello dei dispositivi ...-2.... (fisica dello stato solido) ...

(1)

Università degli Studi dell’Insubria Dipartimento di Scienze Teoriche e Applicate

Architettura degli elaboratori

Il Livello Logico-Digitale:

Le porte logiche

Marco Tarini - Dipartimento di Scienze Teoriche e Applicate marco.tarini@uninsubria.it

I livelli nei moderni calcolatori

6. … Livello delle applicazioni specifiche 5. Livello dei linguaggi applicativi

4. Livello del linguaggio assemblatore 3. Livello del sistema operativo

2. Livello dell’Instruction Set (ISA) 1. Livello della microarchitettura 0. Livello logico

-1. ... Livello dei dispositivi ...

-2. ... (fisica dello stato solido) ...

(2)

Porte logiche

Architettura degli elaboratori - 3 -

Segnali e informazioni

Per elaborare informazioni, occorre rappresentarle (o codificarle) Per rappresentare (o codificare) le informazioni si usano segnali I segnali devono essere elaborati, nei modi opportuni, tramite dispositivi di elaborazione

Porte logiche

Il segnale binario

Segnale binario: una grandezza che può assumere due valori distinti, convenzionalmente indicati con 0 e 1

s 0, 1

Come abbiamo visto, qualsiasi informazione è rappresentabile (o codificabile) tramite un insieme di segnali binari (per esempio i caratteri del codice ASCII)

(3)

Porte logiche

Il segnale binario

Il segnale binario è adottato per convenienza tecnica

in linea di principio si potrebbe usare un segnale ternario o a n valori

Rappresentazione fisica del segnale binario:

si usano svariate grandezze fisiche come corrente elettrica

luminosità

tensione elettricala più usata!

cioè potenziale elettrico;

si misura in Volt tipicamente:

tensione alta = segnale logico 1 tensione bassa = segnale logico 0 (nota: passa comunque una corrente!) altre grandezze fisiche ancora (suono, etc)

Circuiti digitali (o reti)

L’elaborazione di segnali (o informazioni) binarie è oggi svolta principalmente tramite tecnologie microelettroniche

(e in parte anche ottiche)

I circuiti microelettronici che elaborano segnali (o informazioni) binari si chiamano circuiti digitali (o circuiti numerici, o circuiti logici)

(4)

Porte logiche

Livelli

livello microarchitettura:

i circuiti digitali sono sono assemblati insieme (e pilotati una unità di controllo, che è solo un altro circuito), in una macchina in grado di eseguire istruzioni macchina di un dato instruction set livello logico:

Le porte logiche vengono assemblate in circuiti digitali,

che svolgono varie funzioni (di calcolo, di memoria, di controllo…) livello dei dispositivi:

il transistor è l’elemento funzionale fondamentale per la costruzione di porte logiche

Livello della microarchitettura Livello logico

Livello dei dispositivi

Porte logiche

Minuscoli dispositivi

dotati di alcuni cavi («wire») di ingresso, e cavo di uscita

Funzionamento:

1. dai cavi di ingresso viene immesso un certo segnale binario (di input)…

… e, dopo un certo tempo (brevissimo: frazioni di nanosec) … 2. dai cavi di uscita esce un certo altro segnale (elaborato, di output)

sia gli input e gli output sono codificati nello stesso modo fisico (esempio con una tensione)

Finchè il segnale di input resta invariato, neanche l’output cambia Quando il segnale di input cambia,

dopo un breve tempo il segnale di output cambia (oppure no) Esistono molti tipi di porta

Porta

(5)

Porte logiche

Tipi di porte logiche

Ogni porta logica implementa una funzione logica

Classificazione:

per numero di ingressi:

porte a 1 ingresso, (dette anche unarie, o monovariate) porte a 2 ingressi, (dette anche binarie, o bivariate) porte a 3 ingressi, (dette anche ternarie, o trivariate) e così via ...

Una porta logica a n ingressi implementa una funzione logica a n variabili!

Classificazione:

per funzione implementata:

porta NOT, porta AND, porta OR, ...

Circuiti digitali (o reti digitali)

Collegando gli output di una porta logica agli input di un’altra, e così via, costruiremo dei circuiti logici (circuiti digitali, o reti)

che implementano funzioni a molti input e molti output ottenendo così elaborazioni via via più complesse

Porta 1

Porta 2

Porta 3

Porta 4

i n g r e s s i u s c i t e

(6)

Circuiti digitali (o reti digitali)

Un circuito digitale:

è dotato di n  1 ingressi e di un’uscita

è formato da porte logiche interconnesse da cavi

l’uscita di una porta è connessa con entrata in una porta o con l’output del circuito

Porte logiche

Porta 1

Porta 2

Porta 3

Porta 4

i n g r e s s i u s c i t e

Funzioni e circuiti combinatori

Circuiti digitali:

combinatori VS sequenziali

Due tipi di circuiti:

combinatori

sono privi di retroazioni

il segnale viaggia dall’input all’output «a senso unico»

c’è una gerarchia (un ordinamento parziale) fra le porte niente cicli (aciclico)!

sequenziali hanno retroazioni

retroazione: quando il segnale che esce da una porta torna

indietro alla stessa porta (anche dopo essere passato da altre porte) esempio:

Porta 1

Porta 2

per ora,

ci concentriamo solo su questi

(7)

Porte logiche

Quali tipi di porte logiche usare?

Porte logiche fondamentali

Vogliamo usare un insieme di tipi di porte logiche che ci consenta di realizzare qualunque funzione.

Sarebbe anche opportuno che l’insieme fosse piccolo!

per ridurre i costi

La teoria ci dice che esistono diversi insiemi siffatti Noi useremo (soprattutto) l’insieme:

{ NOT , AND , OR }

Implementano funzioni logiche molto intuitive

che hanno una lunghissima storia di uso nella logica (da Aristotele in poi!)

L’insieme consente di realizzare qualsiasi funzione

Non è un insieme più piccolo possibile, ma è comodo da usare

Pro-memoria: esistono insiemi più piccoli ma ancora sufficienti, come: { NOT, OR}, {NOT, AND}, {NAND}, {NOR}

usatissimo in pratica

Descriviamo alcuni tipi di porta logicha

Ogni porta logica (a n ingressi binari)

implementa un operatore logico (a n variabili booleane)

Di ogni porta logica che usiamo siamo per vedere:

con quale simbolo grafico rappresentarla nei nostri schemi (seguendo delle tradizioni consolidate)

con quale nome, e quali sinonimi, chiamarla (idem)

e quale simbolo usare per l’operatore implementato (idem)

e soprattutto …

quale operatore logico implementa,

cioè quale sia la funzione logica corrispondente

(8)

Come descrivo una funzione logica

Problema: come faccio a descrivere una data funzione logica f ? y = f( x )

o più in generale y = f( x₁, x₂, x₃, …)

Risposta: possotabellarla!

cioè riportare esaustivamente cosa faccia f( x₁, x₂, x₃, …) per ogni combinazione possibile di x₁, x₂, x₃, …

nota:

lo posso fare perché esiste solo un un numero finito di valori possibili:

x₁vale 0 oppure 1

se ho n valori, ho solo 2ⁿcombinazioni da specificare questa tabella è detta tabella delle verità

Porte logiche

Porta NOT (invertitore, negatore)

A X

Simbolo funzionale Tabella delle verità

A X 0 1 1 0

A X

simbolo semplificato

L’uscita vale 1 se e solo se l’ingresso vale 0

L’uscita vale 0 se e solo se l’ingresso vale 1

(9)

Porte logiche

Porta AND

Tabella delle verità

A B X 0 0 0 0 1 0 1 0 0 1 1 1

A

X B

(a 2 ingressi) Simbolo funzionale

L’uscita vale 1 se e solo se entrambi gli ingressi valgono 1

Porta OR

Tabella delle verità

A B X 0 0 0 0 1 1 1 0 1 1 1 1

A

X B

(a 2 ingressi) Simbolo funzionale

NB: è un “or”

inclusivo

L’uscita vale 1 se e solo se almeno un

ingresso vale 1

(10)

Porte logiche

Generalizzazioni

Alcuni tipi di porte a 2 ingressi si possono generalizzare a 3, 4, ecc.

ingressi

Le due porte a più ingressi maggiormente usate sono la porta AND e la porta OR

Tipicamente si usano AND (o OR) a 2, 4 o 8 ingressi (raramente più di 8)

Porte logiche

Porta AND a 3 ingressi

Tabella delle verità

A B C X 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1

Simbolo funzionale

L’uscita vale 1 se e solo se tutti gli ingressi valgono 1 A

B C

X

(11)

Porte logiche

Realizzazione ad albero

La porta AND a 3 ingressi si può realizzare come albero di porte AND a 2 ingressi

ma non è l’unico modo, es (circuito funzionalmente

equivalente)

(= esegue la stessa funzione degli input)

A



B C

X

A B C

X

A B C

X

Porta OR a 3 ingressi

Simbolo funzionale Tabella delle verità

A B C X 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1

L’uscita vale 1 se e solo se almeno uno

degli ingressi vale 1 A

B C

X

(12)

Porte logiche

Porte AND e OR a più ingressi

L’uscita X della porta AND a 3 ingressi vale 1 se e soltanto se tutti e tre gli ingressi A, B e C valgono 1

L’uscita X della porta OR a 3 ingressi vale 1 se e soltanto se almeno uno tra gli ingressi A, B e C vale 1

Si generalizza a più ingressi nel modo ovvio ...

Porte logiche

Costo di una porta logica

Una porta logica è sono realizzata con un certo numero di transistor Il numero necessario determina il costo della porta

Dipende da: la tecnologia usata, l’operatore realizzato, il num di ingressi porta NOT : 1 oppure 2 transistor

porte AND e OR (a 2 ingressi): 3 oppure 4 transistor altre porte:  4 transistor

« In quale modo 3-4 transistor compongono una porta AND? » Questo tipo di domanda pertiene al livello dei dispositivi

esula da questo corso (noi partiamo dal livello logico) ci limitiamo ad alcune considerazioni di massima, come quelle riportate qui sopra…

Livello logico

Livello dei dispositivi

(13)

Porte logiche

Velocità di una porta logica

Tempo di commutazione: il tempo che impiega un dispositivo a generare l’uscita dopo che sono cambiati gli ingressi

Tempo di commutazione di un circuito=

max tempo di commutazione di tutti i percorsi da input a output Tempo di commutazionedi un percorso=

somma tempi di commutazione di tutte le porte attraversate Tempo di commutazione di una porta=

dipende dalla tecnologia,

dalla funzione e dal numero di ingressi

Le porte più veloci (oltre che più piccole) sono tipicamente le porte NAND e NOR a 2 ingressi: possono commutare in meno di 1 nanosecondo (10^9sec, un miliardesimo di sec)

NAND = AND negato NOR = OR negato

Costo di un circuito digitale

Il costo di un circuito digitale si valuta in vari modi (criteri di costo):

Numero totale di porte utilizzate Numero di tipi diversi di porte utilizzate Altri ...

Numero di porte universali (NAND o NOR)

Numero tutale di transistor (per comporre tutte le porte necessarie) ES:

ogni AND oppure OR : 4 transistor ogni NOT : 2 transistor

Complessità delle interconnessioni ecc ...

(14)

Velocità di

un circuito digitale combinatorio

( o latenza , o ritardo di propagazione )

La velocità di una rete combinatoria è misurata dal tempo che una variazione di ingresso impiega per modificare l’uscita della rete Per calcolare la velocità di una rete combinatoria, occorre conoscere i ritardi di propagazione delle porte logiche componenti la rete, e poi analizzare i percorsi ingressi-uscita

Frequenza di commutazione = 1 / (latenza)

(quante volte al secondo può calcolare la funzione logica associata)

La latenza si misura in secondi (s)

o, più comodamente, nano-sec (10^-9sec)…

La frequenza si misura in Hertz (Hz) 1Hz = 1 / sec = una volta al sec o, più comodamente, Mega Hertz (MHz,), Giga Hertz (GH) …

Velocità

A

F=AB+/C B

C

Ritardo totale = 5 ns = 5 10

^9

sec

Freq. di commutazione = 1 / 5 ns = 200 MHz

2 ns

1 ns

+3 = 5 ns 2 ns

1 ns

3 ns 2 max

(15)

Velocità

Calcolo “all’indietro”

1 ns

T

₀

A

F B

C

3 ns

1 ns 2 ns

T

₀

- 3 ns T

₀

- 3 ns T

₀

-(3+2) ns

T

₀

-(3+2) ns

T

₀

-(3+1) ns

Il ritardo è il massimo tra quelli “riportati” all’ingresso max( 3+2, 3+2 , 3+1)

Esempio di circuito combinatorio

B A

X

realizza la funzione espressa da questa tabella di verità:

(verificare!)

A B X

0 0 1

0 1 0

1 0 1

1 1 1

(16)

Esempio di circuito combinatorio

Porte logiche

B A

X

Domande:

quali altri circuiti eseguono la stessa funzione?

ce ne sono di migliori?

(costo complessivo, o tempo di commutazione) vediamo strumenti per rispondere a questo tipo di domande

A B X 0 0 1 0 1 0 1 0 1 1 1 1

Porte logiche

Algebra di Boole (o Booleana)

Algebra = un insieme di valori (oppure alcuni) + operazioni definite su questi valori Algebra di Boole

Insieme = { 0, 1 } (cioè {Falso , Vero} ) Operatori = AND, OR, NOT

L’algebra di Boole ci sarà utile a descrivere matematicamente i circuiti combinatori

Ogni espressione dell’algebra di boole corrisponde ad un circuito

Lavoreremo con:

Espressioni che compongono operatori booleani

Regole di trasformazione (equivalenza) tra queste espressioni

(17)

Porte logiche

Operatori booleani

A, B e X sono variabili booleane A, B, X 0, 1

Il prodotto ha precedenza sulla somma

L’inversione ha precedenza su somma e prodotto

(tipicamente: tutti gli op UNARI hanno precedenza su op BINARI)

Nome Operazione Porta associata Inversione X = /A Porta NOT

Somma logica X = A + B Porta OR Prodotto logico X = A B Porta AND

su 2 param

Operatori booleani

Ciascuno corrisponde a una porta logica

Il funzionamento di qualsiasi operatore booleano si può rappresentare tramite la tabella delle verità della porta associata

Gli operatori NOT, AND e OR sono quelli fondamentali della logica classica

Si possono comporre per ottenere tutti gli altri possibili operatori boolenani

(questo sarebbe vero anche scegliendo insiemi differenti, anche più piccoli, di «operatori fondamentali»: per es… ? )

(18)

Operatori booleani binari

(cioè a 2 ingressi) Curiosità: quanti possibili operatori booleani binari diversi?

Risposta: tanti quante sono le tabelle di verità possibili cioè…

Elenchiamole tutte (molte hanno un nome):

Porte logiche

A B 0 0 0 1 1 0 1 1

X 0 0 0 0

X 0 0 0 1

X 0 0 1 0

X 0 0 1 1

X 0 1 0 0

X 0 1 0 1

X 0 1 1 0

X 0 1 1 1

X 1 0 0 0

X 1 0 0 1

X 1 0 1 0

X 1 0 1 1

X 1 1 0 0

X 1 1 0 1

X 1 1 1 0

X 1 1 1 1

AND XOR NAND

NOR

OR

==

sempre0 A

(ignora B)

\A

(ignora B)

B

(ignora A)

\B

(ignora A)

sempre1

Porte logiche

Operatori booleani

Somma Prodotto Inversione

(op.binario) (op.binario) (op.unario)

0 + 0 = 0 0 0 = 0 /0 = 1 0 + 1 = 1 0 1 = 0 /1 = 0 1 + 0 = 1 1 0 = 0

1 + 1 = 1 1 1 = 1

Sono le tabelle delle verità della porta logica OR, AND e NOT, rispettivamente

(19)

Porte logiche

Operatori booleani

Alcune sintassi alternative:

Somma Prodotto Inversione

A + B A × B / A

A | | B A && B ! A A | B A & B ~A

A or B A and B not A

A ˅ B A ˄ B ¬A

A ∙ B A

A * B AB

^^nota!

Altri operatori booleani binari (e porte corrispondenti)

Noi useremo circuiti che usano porte AND, OR e NOT comodità, + uso diretto della logica classica Altre porte popolari:

A B X 0 0 0 0 1 1 1 0 1

1 1 0

XOR («or esclusivo»)

uno o l’altro, ma

NON entrambi

Significati intuitivi di A XOR B:

A oppure B, ma non entrambi (in latino: Aaut B)

vero se A e B diversi falso se A e B uguali vale /A se B = 1 vale A se B = 0 (e viceversa)

il contrario di A, se B vale;

A immutato, altrimenti (e viceversa)

(20)

Altri operatori booleani binari (e porte corrispondenti)

Porte logiche

A B X 0 0 1 0 1 0 1 0 0 1 1 1 NXOR

(«fa il contrario di XOR»)

Significati intuitivi di A NXOR B:

uno XOR seguito da un NOT A NXOR B = \( A XOR B) cioè…

entrambi veri oppure entrambi falsi cioè…

AB + \A\B cioè…

operatore di uguaglianza fra A e B:

vero se A e B sono uguali.

falso se sono diversi

Altri operatori booleani binari (e porte corrispondenti)

Porte logiche

A B X 0 0 1 0 1 1 1 0 1 1 1 0 NAND

(«fa il contrario di AND»)

A B X 0 0 1 0 1 0 1 0 0 1 1 0

NOR

(«fa il contrario di OR»)

(21)

Espressioni booleane

Una espressione booleanacontiene una o più variabili booleane,

operatori booleani prodotto (AND), somma (OR) e negaz (NOT):

es: \A B + C

Dando dei valori alle variabili booleane dell’espressione, e calcolando, si ottiene un valore risultante

Una data espressione booleana (con N variabili) esprime una funzione booleana(o funzione logica)

una funzione che va da: N booleani (parametri) a: un booleano Una funzione booleana si può definire tabellandola esaustivamente

cioè specificando il valore della funzione

per ciascuna combinazione dei valori 0,1 dei suoi parametri (la sua tavola di verità) (o tabella delle verità)

ogni tabella diversa rappresenta una funzione diversa Diverse espressioni booleane esprimono la stessa funzione.

Tabella (o tavola) delle verità

La tabella delle verità è un modo per rappresentare una funzione booleana(data o da determinare) La tabella delle verità ha due colonne:

colonna degli ingressi,

le righe contengono tutte le possibili combinazioni di valori delle variabili della funzione

colonna dell’uscita,

riporta i corrispondenti valori assunti dalla funzione

Nota: se due funzioni hanno la stessa tabella di verità, allora sono la stessa funzione!

Ogni tabella di verità corrisponde ad una funzione booleana, e viceversa

Tabella di verità è in pratica sinonimo di funzione booleana

(22)

Tabella verità Rete combinatoria

Ricapitolando

Porte logiche

Espressione booleana

A + /A /B

A B X 0 0 1 0 1 0 1 0 1 1 1 1 1:1

∞:1

cioè funzione booleana

Rete combinatoria Rete combinatoria Rete combinatoriaRete combinatoriaRete combinatoria

Ricapitolando

(ciascuna freccia rappresenta un procedimento, che vedremo)

Porte logiche

Espressione booleana

A + /A /B

Tabella verità (funzione booleana)

A B X 0 0 1 0 1 0 1 0 1 1 1 1 Analisi

Implementazione

Transfor- mazione