Espressione booleana

(1)

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

Architettura degli elaboratori

Il Livello Logico-Digitale:

Sintesi

di reti combinatorie

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

Da espressione booleana

a tabella di veritá corrispondente

Task:

passare da una espressione booleana alla tabella di veritá corrispndente Nota:

se due espressioni diverse producono la stessa tabella di verità, allora computano la stessa funzione.

Si dicono allora espressioni equivalenti.

(una può essere migliore dell’altra)

Espressione booleana

A + /A /B

Tabella verità (funzione booleana)

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

(2)

Funzioni e circuiti combinatori

Architettura degli elaboratori - 3 -

Da espressione booleana

a tabella di veritá corrispondente

Task:

passare da una espressione booleana alla tabella di veritá 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 F(1, 1, 1) = 1 1 + /1 = 1 + 0 = 1

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

a tre parametri

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

ⁿ

= 2

³

= 8 righe

(come scriverle tutte?)

(3)

Implementare una espressione booleana con una rete combinatoria

A ogni espressione booleana, è associata

una rete combinatoria Gli ingressi della rete

combinatoria sono le variabili della funzione

L’uscita della rete combinatoria è il valore assunto dall’espressione La rete è costituita da porte logiche corrispondenti agli operatori della espressione Rete combinatoria

Espressione booleana

A + /A /B

Implementazione dell’espressione (basta mettere porte al posto degli operatori)

Esempio:

espressione AB+/C

A B

C

A B

/C ingressi

uscita segnale

interno

segnale interno

A×B + /C

A B +/ C

(4)

Implementare una espressione booleana con una rete combinatoria

Nota:

espressioni differenti producono circuiti differenti

anche se le espressioni sono equivalenti (stessa tabella delle verità)

Quindi:

in pratica, prima di passare all’implementazione spesso è opportuno ottimizzare l’espressione

creare una espressione equivalente più corta

Espressioni più corte (con meno operatori) sono in genere implementate

da circuti meno costosi

(ma non necessariamente più veloci!)

Dal circuito 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 possibile combinazioni di 0 e 1 in ingresso in ciascun caso, si computa l’uscita

Tabella verità della funzione Rete

combinatoria

Simulazione (circuitale)

(5)

Simulazione circuitale

A

F B

C

(corrisponde alla riga 0 della tabella)

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

0

1

1 Simulazione circuitale

A

F B

C

(corrisponde alla riga 001 della tabella)

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

0

1

0

(6)

Simulazione circuitale

A

F B

C

(corrisponde alla riga 010 della tabella)

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

1

0

1

1 Simulazione circuitale

A

F B

C

(corrisponde alla riga 111 della tabella)

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

1

0

1

(7)

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

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 è combinatorio (no retroazioni)

Espressione booleana Rete

combinatoria

(8)

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

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

(9)

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

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

(10)

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)

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 delle variabili) Data una funzione booleana (come tabella di verità)

esistono molte reti combinatorie che la realizzano

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

Esse computano tutte la stessa funzione, ma hanno Diverso costo

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

(o, almeno, una sufficientemente buona)

(11)

…

Rete

combinatoria 1

★★★☆☆

Sintesi di reti combinatorie

Problema della sintesi:

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

costruire (sintetizzare): lo schema logico di uncircuitoche la calcola tipicamente: passaggio intermedio: una espressione booleana

Funzione booleana (tav. verita)

Espressione booleana 1

Espressione booleana 2

Rete

combinatoria 2

★☆☆☆☆

Rete

combinatoria 3

★★★★☆

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, velocità, dissipazione di calore…)

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

Funzione booleana (tabella verita qualsiasi)

Espressione booleana (ora: una somma di prodotti) sintesi per SdP

Circuito digitale finale

implementazione

(12)

Sintesi come somma di prodotti (SdP) (o sintesi in 1a forma canonica)

Input: la tabella delle verità della funzione da sintetizzare,

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 un certo numero di fattori).

Procedimento:

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

costruire un addendo della somma come prodotto di tutti i parametro:

Se il parametro xi ha valore 1

mettere nell’addendo il parametro naturale (es: A ) Se il parametro xi ha valore 0

mettere nell’addendo il parametro negato (es: /A ) costruire la somma di tutti gli addendi così ottenuti

Funzioni e circuiti combinatori Architettura degli elaboratori

- 23 -

Esempio: funzione maggioranza

Si chiede di sintetizzare (in 1^aforma canonica) una funzione combinatoria dotata di 3 ingressi A, B e C, e di un’uscita F, definita (a parole) come segue:

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

(13)

Esempio: funzione maggioranza Tabella delle vertià

Primo passo,

scriviamo la tabella delle verità

E’ quella 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

Esempio: funzione maggioranza

Sintesi espressione (in 1ma forma canonica)

F(A, B, C) =

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

E’ una somma di prodotti Il passaggio successivo

è quello di implementare questa espressione in un circuito

Vediamo un modo semplice di farlo (per le Somme 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

(14)

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

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

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

(15)

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

X

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 F(A, B, C) =