1

Espressioni generali e

MULTIPLEXER

2

Notazioni simboliche per le espressioni canoniche

r a b R S

0 0 0 0 00 0 1 0 10 1 0 0 10 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1

i

01234567

S (r,a,b) = 3 m (1,2,4,7) S (r,a,b) = 3 M (0,3,5,6)

R (r,a,b) = 3 m (3,5,6,7)R (r,a,b) = 3 M (0,1,2,4)

• m(i) : mintermine di n bit che assume il valore 1 solo per la n-pla di valori delle variabili corrispondente all’indice i.

• M(i) : maxtermine di n bit che assume il valore 0 solo per la n-pla di valori delle variabili corrispondente all’indice i.

• Abbiamo già visto che una funzione può essere espressa come somma di mintermini o come prodotto di maxtermini

• Questo esempio ne mostra la notazione applicata al caso del full adder

3

Espressioni generali

Espressione generale - Espressione in grado di descrivere qualsiasi funzione di n variabili:

F(x1,x2,...xi,..xn) = m(i) F(i) (SP).i=0

2n-1

m(i) : mintermine di n bitF(i): valore dalla funzione per la

n-pla di valori delle variabili per cui m(i)=1

Caso SP

M(i) : maxtermine di n bit F(i): valutazione dalla funzione

per la n-pla di valori delle variabili per cui M(i)=0

Caso PS

i=0

2n-1

F(x1,x2,...xi,..xn) = ( M(i) + F(i)) (PS)

La notazione del lucido precedente può essere generalizzata come segue: si consderano tutti i mintermini (caso SP) o i maxtermini(caso PS) e semplicemente si “mascherano” cioè si fanno sparire quelli che non interessano

4

La rete basata sull’espressione generale(caso SP)

F(0)

F(1)

F(2n-1)

x1 x2 xn

F

F(x1,x2,...xi,..xn) = m(i) F(i).i=0

2n-1 Espressione in grado di descrivere qualsiasi funzione di n variabili

Rete combinatoria programmabile in gradodi realizzare qualsiasi funzione di n variabile

F(i): costante detta anche “bit di programmazione”

Questa rete è un multiplexer a 2n vie e può anche essere realizzata con un decoder di n variabili, 2n and2 e un OR a 2n ingressi

5

SN74153

I Multiplexer

MUX a 4 vie, detto anche MUX di due variabili (espressione SP)U = A1’. A0’. I0 + A1’. A0 . I1 + A1 . A0’. I2 + A1 . A0 . I3

U

I0

I1

I2

I3

AB

Ricordando che il decoder è la rete che genera i mintermini,la realizzazione del MUX con decoder, and e or a partire dall’espressione di U è immediata (è sufficiente applicare la proprietà associativa ai 4 prodotti logici)

A e B si chiamano anche variabili di controllo o

bit di indirizzo del MUX

6

Circuiti integrati che realizzano MUX di 1, 2, 3, e 4 variabili (detti anche MUX a 2, 4, 8 e 16 vie)

SN74151I0

I1

I2

I3 ZI4

I5

I6

I7

CBA

SN74153I0

I1

I2 ZI3

B A

SN74157I0

I1 Z

A

SN74150I0

I1

I2

I3

I4

I5

I6

I7 ZI8

I9

I10

I11

I12

I13

I14

I15

DCBA

A,B,C,D ingressi ( xi )

Iibit di programmazione ( pi )

7

Sintesi con Multiplexer

1) Si sceglie, o si realizza, un MUX con un numero di vie pari alle righe della tabella della verità da realizzare.

2) Si collegano gli ingressi di selezione ai segnali che corrispondono alle variabili della funzione.

3) Si impone su ciascuna via o il valore “0” o il valore “1” seguendo le indicazioni fornite dalla tabella della verità.

Il Multiplexer con n bit di indirizzo è la realizzazione della espressione generale SP di n variabili.

Il procedimento di sintesi mediante multiplexer si articola nei seguenti passi:

N. B. - Nello schema elettrico l’imposizione di un valore logico (0 o 1)implica il collegamento con il corrispondente valore fisico (es. 0V o 5 V)

8

Sintesi di un full-adder con MUX

a b r S R

0 0 0 0 0 0 0 1 1 0 0 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1

1 0 a b r

I0I1I2I3I4I5I6I7 C B A

Z S

I0I1I2I3I4I5I6I7 C B A

Z R

SN74151

SN74151

Vcc 1GND 0

Ci vuole un MUX per ogni

variabile di uscita!

Ci vuole un MUX per ogni

variabile di uscita!

9

Impiego dei MUX per semplificare la sintesi di funzioni di molte variabili

• Dividiamo in due una t.d.v. di n variabili in modo che ognuna delle due “sottotabelle” ottenute abbia una variabile di ingresso costante (es.: xn-1)

• Si ottengono così 2 tdv di n-1 variabili ciascuna associata a un valore costante di xn-1

• La rete che realizza la tdv di n var. assegnata può essere realizzata inviando a un MUX a due vie controllato da xn-1 le uscite delle 2 reti di n-1 variabili che realizzano le due sottotabelle

a b r S

0 0 0 00 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1

a

MUX0 U1 A

Sa=0

a=1

RC

0 11 0

b r

RC

1 00 1

b r

Una RC per a =0 e una RC per a =1

Una RC per a =0 e una RC per a =1

10

Iterazione del procedimento illustrato nel lucido precedente

• Il procedimento illustrato nel lucido precedente è semplicemente l’applicazione del teorema di espansione

• Il procedimento può essere iterato suddividendo ulteriormente le tdv di n-1 variabili in due tdv di n-2 variabili

• La realizzazione della tdv assegnata, dopo due iterazioni, si riduce a:– la realizzazione di 4 funzioni di n-2 variabili

– un albero di multiplexer a due vie

• l’albero di MUX realizza a sua volta la funzione di mux a 4 vie, come illustrato dal prossimo lucido

• Il teorema di espansione può essere applicato in tutto n volte (TANTE QUANTE SONO LE VAR. DI INGRESSO)

• Alla fine si arriva alla realizzazione delll’espressione generale SP tramite albero di MUX a n livelli

11

Albero di MUXEspressione SP di un MUX a 4 vieU = A1’. A0’. I0 + A1’. A0 . I1 + A1 . A0’. I2 + A1 . A0 . I3 Manipolazione algebrica:U = A1’. (A0’. I0 + A0 . I1) + A1 . (A0’. I2 + A0 . I3)

Disponendo opportunamente in serie/parallelo dei MUX si ottiene un MUX con un numero maggiore di vie.

MUX0 U1 A

A1

U

I0

I1

I2

I3

MUX0 U1 A

MUX0 U1 A

A0

12

Ripetizione dei teoremi di espansione (o di Shannon)

F(x1,x2,..xn-1,0), F(x1,x2,..xn-1,1) sono rispettivamente la parte

della tabella della verità di F in cui xn=0 e quella in cui xn=1. Se F è descritta da una espressione E(x1,x2,..xn-1,xn), sono le

espressioni che si ottengono da E sostituendo a xn i valori 0 e 1.

Esempio: E= x1+x2 x3’

= x1’.(0+x2 x3’)+x1.(1+x2 x3’)

= (x1+(0+x2 x3’)).(x1’+(1+x2 x3’))

Esempio: b F(0,b)a b F(a,b) 0 00 0 0 1 10 1 11 0 1 b F(1,b)1 1 1 0 1

1 1

T19) F(x1,x2,..xn-1,xn) = xn’.F(x1,x2,..xn-1,0) + xn .F(x1,x2,..xn-1,1)

T20) F(x1,x2,..xn-1,xn) = (xn+ F(x1,x2,..xn-1,0)).(xn’+ F(x1,x2,..xn-1,1))

13

Mapping di reti logiche su gate array programmabili

• Il simulatore logico che utilizziamo nel corso di reti logiche deve sapere quale dispositivo elettronico verrà impiegato per realizzare le reti che vogliamo simulare

• I dispositivi utilizzabili sono gate array programmabili in campo (FPGA o Field Programmable Gate Arrays) costruiti da Altera

• Questi dispositivi sono costituiti da matrici di celle logiche, la cui struttura di riferimento sarà illustrata nel prossimo lucido

• Solitamente le celle sono tutte uguali• Le loro principali caratteristiche sono la configurabilità e la interconnettibilità:

esiste un programma detto “fitter” che automaticamente converte la rete data in una rete equivalente composta di celle configurate e interconnesse

• Alcuni FPGA mantengono la configurazione anche in assenza di alimentazione• Altri FPGA mantengono la configurazione su una memoria volatile che perde il

contenuto in assenza di alimentazione

14

FPGA: struttura di una cella tipo• Interconnettendo tra loro più celle di un FPGA è possibile realizzare

reti combinatorie e sequenziali di notevole complessità

• Ogni cella ha le seguenti caratteristiche:– 5 o 6 ingressi “combinatori”

– un mux a due vie: una via è un ingresso, la variabile di controllo è un altro ingresso e l’altra via è una qualunque funzione degli altri 3 o 4 ingressi (scelta dal fitter)

– un FFD con ingressi di clock, enable, e clear+preset sincroni

– 2 uscite: l’uscita del mux e l’uscita del FFD

– l’ingresso del FFD è l’uscita del MUX

• In questo modo ogni cella può essere impiegata per realizzare la funzione G, la funzione F o il registro con lo stato presente

15

Rappresentazione concettuale di una cella logica di FPGA

cd00 01 11 10

00ab

X 1 1 X

X 1 1 X

0 1 1 X

X 1 1 X0111

10

MUX0 U1 A

YF

RC di 4 variabiliconfigurabile

a,b,c,d

fe

• Preset e clear del FFD non sono indicati

• Il clock è un segnale globale, esteso cioè a tutto il dispositivo

D Q y

z

16

Esercizi di mapping su FPGA

• Si mappi su due celle una funzione di 5 variabili

• Si mappi su tre celle il generatore di forme d’onda assegnato nella prima prova intermedia

• Si scelgano a piacere tre reti e le si mappi su FPGA

• Questi esercizi si possono risolvere applicando alle funzioni da mappare il teorema di espansione come indicato nel lucido n.9 (semplificazione di reti complesse)

17

Sintesi a MUX di funzioni complesse (1)

Caso di studio: sintesi di una funzione incompleta di 4 variabiliusando MUX con 3 ingressi di selezione.

.= F(Q0 ,Q1 ,Q2 ,0) Q3’Z = F(Q0 ,Q1 ,Q2 , Q3) a)

1000 0 1 0

- - - 1

000 001 010 01101

Q3

Q2Q1 Q0

1 0 1 0

1 0 - -

101 110 111

.

+ F(Q0 ,Q1 ,Q2 ,1) Q3

18

Sintesi a MUX di funzioni complesse (2)

Q2Q1Q0 1 0

I0I1I2I3I4I5I6I7 C B A

Z

SN74151

I0I1I2I3I4I5I6I7 C B A

Z

SN74151

SN74157I0

I1A

ZF (Q0 ,Q1 ,Q2 , Q3)

Q3

F(Q0 ,Q1 ,Q2 ,0)

F(Q0 ,Q1 ,Q2 ,1)

19

Sintesi di funzioni con molte variabili (3)

Z = F(Q0 ,Q1 ,Q2 ,Q3)

= F(0,0,0, Q3) Q2’Q1’Q0’ + F(0,0,1, Q3) Q2’Q1’Q0 + F(0,1,0, Q3) Q2’Q1 Q0’ + F(0,1,1, Q3) Q2’Q1 Q0 + F(1,0,0, Q3) Q2 Q1’Q0’ + F(1,0,1, Q3) Q2 Q1’Q0 + F(1,1,0, Q3) Q2 Q1 Q0’ + F(1,1,1, Q3) Q2 Q1 Q0

b) Applicando 3 volte il teorema di espansione per “estrarre” una dopo l’altra le variabili Q0, Q1 e Q2 :

F(0,0,0,Q3)

F(0,0,1,Q3)

F(0,1,0,Q3)

F(0,1,1,Q3)

F(1,0,0,Q3)

F(1,0,1,Q3)

F(1,1,0,Q3)

F(1,1,1,Q3)Q3 Q2Q1Q0

I0I1I2I3I4I5I6I7 C B A

Z F

SN74151

20

Sintesi a MUX di funzioni complesse (4)

La soluzione b) presenta minor numero di componenti e minor ritardo rispetto alla a) .

1000 0 1 0

- - - 1

000 001 010 01101

Q3

Q2Q1 Q0

1 0 1 0

1 0 - -

101 110 111

1 0Q3

I0I1I2I3I4I5I6I7 C B A

Z

Q2Q1Q0

F

SN74151

Q3’

genera le 4 funzioni di una variabile !

F(0,0,0,Q3) = 1F(0,0,1,Q3) = 0F(0,1,0,Q3) = 1F(0,1,1,Q3) = 0F(1,0,0,Q3) = 0F(1,0,1,Q3) = 0F(1,1,0,Q3) = 1F(1,1,1,Q3) = Q3

21

Esercizio 4.9

Si consideri la precedente funzione Z e si esegua la sintesi con MUX a 3 ingressi di selezione estraendo dapprima solo Q0 e poi Q1, Q2 ,Q3 .