• Non ci sono risultati.

tavola di verità

N/A
N/A
Protected

Academic year: 2021

Condividi "tavola di verità"

Copied!
24
0
0

Testo completo

(1)

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

Architettura degli elaboratori

Il Livello Logico-Digitale Funzioni e Reti Combinatorie

Marco Tarini

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

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

(2)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 3 -

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 cui righe contengono tutte le combinazioni di valori delle variabili della funzione

colonna dell’uscita, che riporta i corrispondenti valori assunti dalla funzione

Da espressione booleana

a tabella di veritá corrispondente

Task:

passare da una espressione booleana alla sua tabella di veritá della funzione corrispndente

Esempio:

F(A, B, C) = AB + /C F(0, 0, 0) = 0 0 + /0 = 0 + 1 = 1

F(0, 0, 1) = 0 0 + /1 = 0 + 0 = 0 F(0, 1, 0) = 0 1 + /0 = 0 + 1 = 1 F(0, 1, 0) = 0 1 + /1 = 0 + 0 = 1 F(1, 0, 0) = 1 0 + /0 = 0 + 1 = 1 F(1, 0, 1) = 1 0 + /1 = 0 + 0 = 0 F(1, 1, 0) = 1 1 + /0 = 1 + 1 = 1

espressione booleana con 3 variabili A, B e C funzione booleana

a tre parametri

(3)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 5 -

Esempio 2/2

# riga A B C A B + /C F 0 0 0 0 0 0 + /0 1 1 0 0 1 0 0 + /1 0 2 0 1 0 0 1 + / 0 1 3 0 1 1 0 1 + /1 0 4 1 0 0 1 0 + /0 1 5 1 0 1 1 0 + /1 0 6 1 1 0 1 1 + /0 1 7 1 1 1 1 1 + /1 1 (qui, per comodità nella colonna centrale

è riportato anche il calcolo e in quella iniziale il numero di riga)

colonna uscita colonna

ingressi

n = 3 ingressi

2

n

= 2

3

= 8 righe

Rete combinatoria

A ogni espressione booleana, è associare una rete combinatoria Gli ingressi della rete combinatoria sono le variabili della funzione L’uscita della rete combinatoria è il valore assunto dalla funzione La rete è costituita da porte logiche corrispondenti agli operatori presenti nella funzione

Espressione

booleana Rete

combinatoria Basta mettere

porte al posto

(4)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 7 -

Esempio

A B C

A B

/C ingressi

uscita segnale

interno

segnale interno

A B + /C

espressione booleana

combinatoria rete

A B +/ C

Rete combinatoria

Una rete combinatoria è un circuito digitale:

dotato di n  1 ingressi e di un’uscita

formato da porte logiche interconnesse da cavi

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

privo di retroazioni

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

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

Noi usiamo porte logiche AND, OR e NOT

ma una rete combinatoria può anche essere formata da porte logiche di altro tipo

(5)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 9 -

Dalla rete alla tabella delle verità

Data una rete combinatoria, qual’è la funzione calcolata?

La tabella delle verità della funzione implementata da

una rete combinatoria può essere ricavata per simulazione del funzionamento circuitale della rete combinatoria stessa

Per simulare il funzionamento di una rete combinatoria, si applicano dei valori agli ingressi, e li si propaga lungo la rete fino all’uscita

si applica ogni possibili combinazioni di 0 e 1 in ingresso si osserva ogni rispettiva uscita

Tabella verità della funzione Rete

combinatoria

Simulazione (circuitale)

Simulazione circuitale

A

F B

C

(corrisponde alla riga 0 della tabella)

Risultato della simulazione: F(0, 0, 0) = 1 0

0

0

0

1 1

(6)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 11 -

Simulazione circuitale

A

F B

C

(corrisponde alla riga 001 della tabella)

Risultato della simulazione: F(0, 0, 1) = 0 0

0

1

0

0 0

Simulazione circuitale

A

F B

C

(corrisponde alla riga 010 della tabella)

Risultato della simulazione: F(0, 1, 0) = 1 0

1

0

0

1 1

(7)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 13 -

Simulazione circuitale

A

F B

C

(corrisponde alla riga 111 della tabella)

Risultato della simulazione: F(1, 1, 1) = 1 1

1

1

1

0 1

Simulazione circuitale: risultato (dopo tutte le simulazioni)

A B C F 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1

(8)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 15 -

Dalla rete combinatoria ad espressione booleana

Data una rete combinatoria si può analizzarla per determinare la espressione booleana corrispondente

Esiste sempre una funzione corrispondente, se il circuito non contiene collegamenti illegali, retroazioni, ecc.

Espressione booleana Rete

combinatoria

Analisi di reti combinatorie

1. Si applicano nomi ai segnali interni: p, q e r

2. Si esprimono p, q, r in funzione di A, B, C, e F in funzione di p, q, r A

F B

C

p q r

(9)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 17 -

Analisi di reti combinatorie:

un metodo lento ma sicuro

Espressioni booleane corrispondenti ai segnali interni:

p = /A B q = /C r = /A C

A

F B

C

p q r

Analisi di reti combinatorie:

un metodo lento ma sicuro

Uscita come espressione booleana in funzione dei segnali interni:

F = p + q + r

A

F B

C

p q r

(10)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 19 -

Analisi di reti combinatorie

p = /A B q = /C r = /A C F = p + q + r

Per sostituzione, si ricava l’uscita come espressione booleana in funzione degli ingressi principali:

F(A, B, C) = /A B + /C + /A C

L’espressione booleana così trovata esprime la stessa funzione booleana calcolata dal circuito combinatorio di partenza

OPPURE: procedere in avanti, dagli input verso l’output (s

Sintesi di reti combinatorie

Problema della sintesi:

data: una funzione booleana (espressa come tabella delle verità):

costruire (sintetizzare): lo schema logico di un circuito che la calcola Usiamo due passi:

1: trovare una espressione booleana che esprime la funzione booleana data

2: costruiriamo la rete corrispondente all’espressione booleana In generale, per una data tabella delle verità possono esistere più espressioni booleane

la soluzione al problema di sintesi non è dunque unica!

problema: trovare la rete ottima (o almeno buona)

(11)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 21 -

Reminder: reti combinatorie (funzionalmente) equivalenti

Ogni rete combinatoria realizza una espressione booleana Ogni espressione booleana rappresenta una rete combinatoria Ma: tante espressioni booleane diverse possono esprimere la stessa funzione booleana (data come una tabella di veritá)!

(cioè dare lo stesso valore per gli stessi assegnamenti della vars) Data una funzione booleana (come tabella di verità)

esistono molte reti combinatorie che la realizzano

Reti combinatorie che realizzano la medesima funzione combinatoria si dicono (funzionalmente) equivalenti

Esse hanno tutte la stessa funzione, ma struttura differente Diverso costo

Diverse prestazioni (es: velocità, consumo … ) Ci dobbiamo porre il problema di scegliere la migliore

(o almeno una sufficientemente buona)

Rete combinatoria

★★★☆☆

Sintesi di reti combinatorie

Problema della sintesi:

data: una funzione booleana (espressa come tabella delle verità):

costruire (sintetizzare): lo schema logico di un circuito che la calcola

Funzione booleana (tav. verita)

Espressione booleana Espressione booleana

Rete combinatoria

★☆☆☆☆

Rete combinatoria

★★★★☆

(12)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 23 -

Sintesi di reti combinatorie

Esistono svariate tecniche di sintesi di reti combinatorie, che differiscono per:

Complessità della procedura

Qualità della rete combinatoria risultante

(per dimensioni, costo, e velocità, dissipazione di calore…)

Una tecnica semplice e universale, benché generalmente non ottimale, è la sintesi attraverso somma di prodotti (detta 1aforma canonica)

Funzione booleana (tav. verita)

espressione booleana (una somma di prodotti) Passo 1

rete

combinatoria finale Passo 2

Sintesi come somma di prodotto (SP) (o sintesi in 1

a

forma canonica)

Input: la tabella delle verità della funzione da sintetizzare, funz con n parametri,

Output: una somma di prodotti, cioè un’espressione booleana del tipo XXXX + YYYY + ZZZZ + ….

dove ciascuno degli addendi della somma XXXX, YYYY … è un prodotto (di n fattori).

Per ogni 1 nella colonna dell’uscita della tabella delle verità:

costruire una somma con un termine per ogni parametro:

Se il parametro xiha valore 1

mettere nella somma il parametro naturale (es: A ) Se il parametro xiha valore 0

mettere nella somma il parametro negato (es: /A )

(13)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 25 -

Esempio: funzione maggioranza

Si chiede di sintetizzare (in 1aforma canonica) una funzione

combinatoria dotata di 3 ingressi A, B e C, e di un’uscita F, funzionante come segue:

Se la maggioranza degli ingressi vale 0, l’uscita vale 0 Se la maggioranza degli ingressi vale 1, l’uscita vale 1

Tabella delle verità

La tabella delle verità della funzione maggioranza è mostrata a lato

L’uscita vale 1 se e solo se 2 o tutti e 3 gli ingressi valgono 1 (cioè se e solo se il valore 1 è in maggioranza)

A B C F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1

(14)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 27 -

Espressione booleana

F(A, B, C) =

/A B C + A /B C + A B /C + A B C

E’ una somma di prodotti!

# riga A B C F 0 0 0 0 0 1 0 0 1 0 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 1 6 1 1 0 1 7 1 1 1 1

Si può ridurre?

Modo pratico di disegnare un circuito per una somma di prodotti (step 1)

A

/A

A

B

/B

B

C

/C

C

X =

/A B C +

A /B C +

A B /C +

A B C

(15)

Modo pratico di disegnare un circuito per una somma di prodotti (step 2)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 29 -

A

/A

A

B

/B

B

C

/C

C

X =

/A B C + A /B C + A B /C + A B C

/A B C A /B C A B /C A B C

Modo pratico di disegnare un circuito per una somma di prodotti (step 3)

A

/A

A

B

/B

B

C

/C

C

X =

/A B C +

A /B C +

A B /C +

A B C

(16)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 31 -

Modo pratico di disegnare un circuito per una somma di prodotti: una variante

A B C

F /ABC, vero quando input 011

A/BC, vero quando input 101

AB/C, vero quando input 110 ABC, vero quando

input 111 F(A, B, C) =

/A B C + A /B C + A B /C + A B C

Metodo alternativo:

usare un prodotto di somme

“Seconda forma canonica”

Funzione booleana (tav. verita)

espressione booleana che un prodotto di somme Passo 1

rete

combinatoria finale Passo 2

(17)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 33 -

Sintesi come prodotto di somme

F(A, B, C) =

(A+B+C) (A+B+/C) (A+/B+C) (/A+B+C)

Nota bene: è un prodotto di somme

# riga A B C F 0 0 0 0 0 1 0 0 1 0 2 0 1 0 0 3 0 1 1 1 4 1 0 0 0 5 1 0 1 1 6 1 1 0 1 7 1 1 1 1

Sintesi come prodotto di somme

F(A, B, C) =

(A+B) (A+/B) (/A+B)

F=0 sse uno dei fattori è 0.

Essendo un prodotto di somme ciascun fattore annulla la funzione solo in un caso

A+B = 0 sse A=0, B=0 A+/B = sse A=0, B=1 /A+B = sse A=1, B=0 Nel caso A=1, B=1 nessun

A B F

0 0 0

0 1 0

1 0 0

1 1 1

(18)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 35 -

Quale metodo conviene?

PoS o SoP?

Se ci sono pochi 1 conviene SoP Se ci sono pochi 0 conviene PoS

Due reti equivalenti

F1 = AB + AC F2 = A(B + C)

F1 = AB + AC =

= A (B + C) =

= F2

A

F1 B

C

AB

AC

AB+AC

A

F2 B

C B+C

A(B+C)

Proprietà distributiva

(19)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 37 -

Costo di reti combinatorie

Il costo di una rete combinatoria si valuta in vari modi (criteri di costo):

Numero di porte,

Numero di tipi diversi di porte utilizzate Altri ...

Numero di porte universali (NAND o NOR)

Numero di transistor (per fare tutte le porte necessarie) ES: ogni AND oppure OR : 4 transistor

ogni NOT : 2 transistor

Complessità delle interconnessioni ecc ...

Velocità di una rete

( 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, milli-sec (ms), nano-sec (ns)…

La frequenza si misura in Hertz (Hz) 1Hz = 1 / sec = una volta al sec

(20)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 39 -

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

Velocità

Calcolo “all’indietro”

1 ns

T

0

A

F B

C

3 ns

1 ns 2 ns

T

0

- 3 ns T

0

- 3 ns T

0

-(3+2) ns

T

0

-(3+2) ns

T

0

-(3+1) ns

(21)

Idea: ottimizzare l’espressione prima di convertirla in un circuito

Funzioni e circuiti combinatori

Architettura degli elaboratori - 41 -

Funzione booleana (tav. verita)

espressione booleana:

prodotto di somme OPPURE somma di prodotti costruzione

di 1ma oppure 2da forma canonica

rete combinatoria ottimizzata

Ottimizzazione usando le regole di riscrittura delle espr. booleane

espressione più semplice

da espressione booleana a circuito combinatorio

Ottimizzazione: esempio

/A B C + A /B C + A B /C + A B C =

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

BC + AC + AB

Meno costosa e più veloce! (provare)

oppure, andando avanti con le riscritture BC + AC + AB = C (A+B) + AB

Ancora meno costosa (solo 4 porte a due ingressi, anziché 5) Velocità?

Velocità alta VS costo ridotto :

(22)

Esempio dell’intero processo 1/5

Numeri a led (cosiddetti “Seven-segment display”) : costruiamo un piccolo circuito combinatorio che calcola lo stato (acceso, spento) di uno dei 7 led del display dobbiamo accendere sul display una cifra in base 8 espresso da tre bit dati in igresso in base 2

la cifra da esprimere è espressa con tre bit A,B,C

Funzioni e circuiti combinatori

Architettura degli elaboratori - 43 -

000ABC 001 ABC 010

ABC 011 ABC 100

ABC 101 ABC 110

ABC 111 ABC

Esempio dell’intero processo 2/5

Numeri a led (“Seven-segment display”) in base 8:

risolviamo per il led in alto

000ABC 001 ABC 010

ABC 011 ABC 100

ABC 101 ABC 110

ABC 111 ABC

acceso spento acceso acceso spento acceso acceso acceso A B C X 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1

tabella

di veritá

(23)

Esempio dell’intero processo 3/5

Come SOMMA DI PRODOTTI (1ma forma canonica)

\A \B \C + \A B \C + \A B C + A \B C + A B \C + A B C

Come PRODOTTO DI SOMME (2da forma canonica)

( A + B + \C ) ( \A + B + C) (usiamo questa! meno 0 che 1)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 45 -

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

Esempio dell’intero processo 4/5

Ottimizzazione:

// start: 5 operatori binari, 2 not ( A + B + \C ) ( \A + B + C)

= // distributiva: ( X + Y ) ( X + Z ) = X + YZ B + ( A + \C ) ( \A + C)

= // distr (2 volte): X( Z + K ) = XZ+XK B + A \A + AC + \C \A + C \C

= // inverso (2 volte): X \X = 0 B + 0 + AC + \C \A + 0

= // elem neutro B + AC + \A \C

// end: 4 opeatori binari, 2 not

(24)

Esempio dell’intero processo 5/5

Rete combinatoria per: B + AC + \A\C

Funzioni e circuiti combinatori

Architettura degli elaboratori - 47 -

A B C

or a tre ingressi (costa due or)

Esercizi proposti

Simulare la rete che abbiamo costruito e verificare se soddisfa la tabella di verita’

Stimare la velocita’ del circuito

Costruire la tabella di verita’ per l’espressione boolana ottimizzata e verificare sia la stessa tabella di verita’

Scrivere l’espressione booleana associata al circuito e verificare che sia la stessa espressione booleana ottimizzata

Costruire la tabella di verita’ per l’espressione booleana non ottimizzata e verificare che sia la tabella dalla quale siamo partiti Ottimizzare l’espressione in 1ma forma normale

Scrivere il circuito per l’espressione booleana non ottimizzata.

Scrivere il circuito (ottimizzato) per qualche altro led!

Ripetere gli esercizi sopra per qualche altro led

Riferimenti

Documenti correlati

 Un mintermine rappresenta una della combinazioni delle variabili binarie elencate nella tabella di verità, e assume il valore 1 solo per quella specifica. combinazione, e 0

• Oltre che mediante tavola di verità, ogni funzione booleana può essere rappresentata tramite la sua espressione booleana (forma canonica).. • Per passare dalla rappresentazione

“coordinate, si constata che le coppie di valori di A e B (di C e D) associate alle colonne (alle righe) sono ordinate in modo che tra due caselle adiacenti (della medesima riga

“coordinate, si constata che le coppie di valori di A e B (di C e D) associate alle colonne (alle righe) sono ordinate in modo che tra due caselle adiacenti (della medesima riga

A turno ogni giocatore può fare una delle seguenti mosse: o sceglie una colonna con 2k monete e la suddivide in due colonne di k monete oppure toglie tutte le colonne con un

Sapendo che la combinazione `e composta da 6 cifre, ognuna tra 1 e 5, e che nessuna cifra compare una sola volta, quanti tentativi dovrà effettuare al massimo per riottenere il

Sono tante quante le sequenze lunghe 2n con somma totale 2 (si prende il pi` u piccolo k tale che la somma parziale fino a k sia −1, e si cambia il segno a tutti i termini fino a

• Oltre che mediante tavola di verità, ogni funzione booleana può essere rappresentata tramite la sua espressione booleana (forma canonica).. • Per passare dalla