Reti Combinatorie: sintesi

Sintesi di reti combinatorie

Una rete combinatoria realizza una funzione dicommutazione

Data una tabella di verità è possibile ricavare piùespressioni equivalenti che la rappresentano.

Obiettivi:• massimizzare le prestazioni: realizzare una rete logica il più

veloce possibile (minimizzare il numero di livelli della rete)• minimizzare il costo: realizzare rete con minimo numero di

porte oppure con minimo numero di ingressi

Forme canoniche come retiOgni funzione Y può essere espressa in forma canonica:

•Somma di prodotti•Prodotti di somme.

X0

ÿ

X1X2

ÿ

X0X1

X2

X0

ÿX1

ÿ

X2

Y

Rete OR di AND: Somma di prodotti

1

5

6

Y = (1,5,6)

001 101 110

COMPORTAMENTO della Rete

STRUTTURA della Rete

Analisi e Sintesi di reti logiche

ANALISI SINTESI

Costo e velocità di un circuitoRealizziamo una funzione come somma di prodottiSono possibili diverse realizzazioni equivalentiVelocità: numero di livelli logiciCosto: Somma del numero di letterali e degli implicanti

Velocità: 2 livelliCosto: 3+3+3+3=12

X0

ÿX1

X2

ÿX0

X1

X2

X0

ÿX1

ÿX2

Y

Rete AND in OR

3

3

3

DefinizioniUna funzione di commutazione di n variabili può essereespressa come somme di prodotti (OR di AND), ex n=4

Y= P1 + P2 + … + PK = X3X1 + X4X2X1 + X4X3X2X1

• letterale: var. positiva o negativa

• Pi implicante della funzione, PiÆy

Infatti Pi =1 implica y=1, ex: X4X3X2X1 Æy

• Implicante primo: implicante per il quale non è possibileeliminare un letterale dalla sua espressione ed ottenere ancoraun implicante, esempio X4X2X1

• Espressione minima: espressione nella quale non possonoessere eliminati né un letterale né un termine senza alterare lafunzione rappresentata dall’espressione stessa.

Y= X3X1 + X4X2X1

sum-of-products

sum-of-products

product-of-sums

product-of-sums

F1

F2

F3

B

A

C

F4

Realizzazioni di F = AB + C

Mappe di Karnaugh (MK)

• Le mappe di Karnaugh sono tabelle che permettonola rappresentazione e la semplificazione dellefunzioni di commutazione fino a quattro variabili.E' possibile usarle, con qualche difficoltà, ancheper funzioni di cinque e sei variabili

• Le mappe di Karnaugh per le funzioni di 2, 3, 4, 5variabili sono divise in tante caselle (o "celle")quanti sono i corrispondenti mintermini (4, 8, 16,32).

MK per 2 variabili

0 12 3

Y

00 1X0

1X1

11011000

X0 X1 YTabella di verità

MK per 2,3,4 variabili

0 12 3

Y

00 1X0

1X1

0 14 5

Y

000 01

X1 X0

1X2

3 27 6

11 10

0 14 5

Y

0000 01

01X3 X2

3 27 6

11 10

12 138 9

1110

15 1411 10

X1 X0

Le caselle adiacenti corrispondono a configurazioni delle variabili diingresso che differiscono di un solo bitNOTA: le caselle sulle due colonne estreme sono adiacenti,(immagina che la mappa fosse originariamente su una sfera

Esempio

0 14 5

Y

0000 01

01X3 X2

3 27 6

11 10

12 138 9

1110

15 1411 10

X1 X0

Y = S (1,5,6) = ÿX3 ÿX2 ÿX1X0 + ÿX3 X2 ÿX1X0 + X3X2 X1ÿX0

0 10 1

Y

0000 01

01X3 X2

0 00 0

11 10

0 00 0

1110

0 10 0

X1 X0

0001->m1 0101->m5 1110->m12

Se la funzione è data come somma di mintermini, bastascrivere 1 in tutte le celle corrispondenti ai minterminidella somma

Semplificazione

• m1 + m5 = X3X2X1X0+X3X2X1X0

=j X2 + j X2 j =X3X1X0

= j (X2+X2) = j

m1 ed m5 non sono implicanti primi, mentre j è un implicante primoIn una mappa K un implicante primo corrisponde ad un

raggruppamento di 2i celle adiacenti (cubi), sia orizzontalmenteo verticalmente, non incluso in altri raggruppamenti

0 10 1

Y

0000 01

01X3 X2

0 00 0

11 10

0 00 0

1110

0 00 0

X1 X0

0 14 5

0001

3 27 6

12 138 9

11 15 1411 10

00 01 11 10

10

Esempi

0 10 1

Y

0000 01

01X3 X2

1 01 0

11 10

0 00 0

1110

0 00 0

X1 X0

(ÿX3X0)1 01 0

Y

0000 01

01

0 10 1

11 10

0 00 0

1110

0 00 0

(ÿX3 ÿX0)X3 X2

X1 X0

0 10 1

Y

0000 01

01X3 X2

1 01 0

11 10

0 10 1

1110

1 01 0

X1 X0

(X0) 1 01 0

Y

0000 01

01

0 10 1

11 10

1 01 0

1110

0 10 1

(ÿX0)X3 X2

X1 X0

Altre definizioni

• Implicante primo essenziale: implicante primorappresentato da un cubo che copre almeno un 1non coperto da altri implicanti primi

• Un insieme di implicanti primi essenziali permettedi rappresentare la funzione

Esempi

1

Y

0000 01

01

1 11

11 10

11

1110

11

X1 X0

1 11

Y

0000 01

01

1 11 1

11 10

1 11

1110

1 1X3 X2

X1 X0

11 1

Y

0000 01

01

11

11 10

1 11

1110

11

X1 X0

11

Y

0000 01

01

11

11 10

1 11 1

1110

1 11 1

X3 X2

X1 X0

Algoritmo per la minimizzazione

1. Si segnano con 1 le caselle relative ai minterminidella funzione

2. Si identificano gli implicanti primi essenziali e sidisegnano i relativi cubi. Se sono coperti tutti imintermini si va al passo 4, altrimenti al 3.

3. Si coprono i restanti mintermini con il minornumero possibile di implicanti

4. Fine della procedura

NOTA: non univocità del passo 3

Esempio

0 10 1

Y

0000 01

01X3 X2

1 01 1

11 10

0 11 1

1110

0 00 0

X1 X0

Funzioni parzialmente specificate

Funzioni in cui non sono possibili alcune configurazionidelle variabili di ingresso o non interessa il valoredi uscita per alcune configurazioni di ingresso

Esempio: date quattro variabili di commutazionecodificanti i numeri 0..9 la funzione è vera quandoil numero è divisibile per 3

Tabella di verità e MK di una funzione parz. spec.

1001001001

d.c.c.d.c.c.d.c.c.d.c.c.d.c.c.d.c.c.

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

fx3 x2 x1 x0 Realizzare un circuito che riconosca se un numero compreso tra 0 e 9sia divisibile per 3

1 00 0

Y

0000 01

01X3 X2

1 00 1

11 10

- -0 1

1110

- -- -

X1 X0

Algoritmo per la minimizzazione1. Si segnano con 1 le caselle relative ai mintermini

e con – le d.c.c. (don’t care condition) dellafunzione.

2. Si identificano gli implicanti primi essenzialirappresentati da cubi costituiti da 1 e – ed aventialmeno un 1. Se sono coperti tutti i mintermini siva al passo 4, altrimenti al 3.

3. Si coprono i restanti mintermini con il minornumero possibile di cubi aventi le dimensionimassime e costituiti da 1 e -.

NOTA: non esiste un modo veloce per realizzare il passo 3 inmto ottimale

Codificatore• Realizza la funzione di codifica binaria: associa ad

ogni elemento di un insieme G composto da msimboli, una sequenza distinta di n bit 2n≥m

• m linee di ingresso x0,..,xm-1, n linea di uscitay0,..,yn-1– La linea xi è associata al simbolo i-esimo– Quando xi=1, e xj=0 (j≠i), in uscita è presente il

codice corrispondente al simbolo i-esimo

X0X1

Xm-1

y0

yn-1

Esempio• Codifica cifre decimali in BCD

1001

1000

0111

0110

0101

0100

0011

0010

0001

0000

9

8

7

6

5

4

3

2

1

0

y3y2y1y013579

2367

4567

8

9

y0

y1

y2

y3

Decodificatore

• Realizza la funzione inversa del codificatore: datauna parola di un codice genera il simbolocorrispondente

• Per ogni configurazione di ingresso, una sola uscitavale 1, le altre hanno valore 0

y0

y1

yn-1

x0

xm-1

EsempioDecoder BCD-Cifre decimali (prima realizzazione)

1001100001110110010101000011001000010000

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

x3x2x1x0y9y8y7y6y6y5y4y3y2y1y0

ÿx3ÿx2ÿx1ÿx0

ÿx3ÿx2ÿx1

x0

x3ÿx2ÿx1

x0

.

.

.

y0

y1

y9

EsempioDecoder BCD-Cifre decimali (seconda realizzazione)

1001100001110110010101000011001000010000

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

x3x2x1x0y9y8y7y6y6y5y4y3y2y1y0

ÿx3ÿx2

x3ÿx2

x3 x2ÿx1ÿx0ÿx1 x0 x1ÿx0

x1 x0

ÿx3 x2

y0 y1

….

Decodificatore con enable

• E’ dotato di un ulteriore ingresso di abilitazione E(detto anche strobe)

• Il decodificatore è abilitato (ossia il processo didecodifica ha luogo) solo quando E=1

EE

Realizzazione di funzioni con decoder

0101

1110

111

100

011

010

001

000

1

1

0

0

0

1x2x1x0

f

E

E

fusibile

ROM (Read Only Memory)

Insieme di locazioni di memoria che possonoessere lette specificandone l’indirizzo

• Una ROM è un circuito combinatorio

Ingresso

(indirizzo)

Uscita

(word)

Schema logico di una ROMFunzioni realizzate come OR di mintermini

fusibile

0 0 0

input: m bit- indirizzodi memoria

output: parola memorizzata

Implementazione ROM con C-MOS

ROM 4x4 (numero parole x dimens. parola)

Uscita

R R R R

Vdd

Indirizzo

DE

C

Assenzacollegamento =1

“Interruttore”

Implementazione ROM (2)

• Esempio, indirizzo 01, uscita=0001

Uscita

R R R R

Vdd

Indirizzo01

DE

CO

DE

R

0 0 0 1

ROM temporizzazioni

Xindirizzi

dati Zcsoe

t a

t cs

t oe

alta impedenza alta impedenza

indirizzo valido

cs

oe

Zdato valido

t

t

v

d

• ta : tempo di propagazione dall'ingresso X all'uscita Z• tcs: tempo di propagazione dall'ingresso cs all'uscita Z• toe: tempo di propagazione dall'ingresso oe all'uscita Z• t v: tempo di mantenimento dell'uscita da quando commuta Xo cs o oe

• td: tempo di disabilitazione dell'uscita da quando commutacs o oe

Multiplexer (MUX 2n:1)

• Ingressi– m=2n ingressi dati– n ingressi di selezione (controllo)

• Uscita– Una fra le m, a seconda del controllo

x0x1

xm-1

sn-1 s0

01

m-1

y X0

X1

..X2

n-1

01..

2n-1

yS

MUX 4-2

Y

X 0

X 1

X 2

X 3

s 0 s 1

MUX - Generatore di funzioni

0

1

2

3

4

5

6

7

0 1

y=f(x0x1x2)=m0+m2+m3+m6=S(0,2,3,6)

y=M1M4M5M7=P(1,4,5,7)

x0x1x2

DEMUX 2-4

d d d

0 d 1 2 3

Y

s0s1

Half Hadder - Semisommatore

Ingresso 2 bit, uscita 2 bit

HA

A B

SC

A+B=

---C S

A

B

S

C

HA

C=ABS=(not A)B + A(not B)=A⊕B

0 01 01 00 1

0 00 11 01 1

S CA B

OutIn

Full Hadder:Addizionatore completo

+

A B

S Cout

Cin+A+B=

------Cout S

S vale 1 solo quando un numero dispari di bit di ingresso vale 1. Quindi, S=A⊕B ⊕C

Cin

0 01 01 00 11 00 10 11 1

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

S CoutA BCin

OutIn

1110

0100

ABCin

Cout=CB+AB+CA

Full Adder: circuito minimo

Si vale 1 solo quando il numero di bit è dispari:Si = Ci ⊕ Ai ⊕ Bi

Inoltre, ci+1 = AiBi + ciBi + ciAi = AiBi + ci(Ai+Bi) = AiBi +ci (Ai⊕Bi)

ci

ci+1

Ai Bi

Ai ⊕ Bi

ci (Ai ⊕ Bi)

Si

Ripple Carry Adder (RCA)

Full Adder

a0 b0

c0

s0

Full Adder

a1 b1

c1c2

s1

Full Adder

an-1 bn-1

cn-1

cn

sn-1

n-bit Ripple Carry

Adder

sn-1 s0

an-1 bn-1 a0 b0

c0cn

Il tempo per ottenere ilrisultato è pari ad nTc, dove Tcè il tempo dipropagazione del riporto

Circuito per la somma/sottrazionea1 b1 a0b0 an-1bn-1

c0FAFAFA

OVF

S/D

sn-1 s1 s0

…

Decodificatore

Ogni uscita vale 1 in corrispondenza di una eduna sola configurazione d’ingresso

DECZ0I0

I1

Z1

Z2

Z3En

Z0

0

1

I1I0

XX

00

En

0

1

Z1

0

0

Z2

0

0

Z3

0

0

0011 1 0 0

0101 0 1 0

0111 0 0 1Z0 = En I1 I0

Z1 = En I1 I0

Z2 = En I1 I0

Z3 = En I1 I0

Nota: Zi è il mintermine mi

Zi=1 Û (Input)2 = iUn decoder con n segnali di ingresso possiede 2n segnali di uscita

DEC n 2n

ALU (ad un solo bit)

Op: ingresso deldecodificatore, seleziona iltipo di operazione

+

a

b

opcin

cout

0

1

2

y

0 0 0 11 011

op

a AND ba OR b

(a+b+cin) mod 2??

y

ALU a 32 bit

cin

cout

ALU0

cin

cout

ALU1

cin

cout

ALU31

a0

b0

a1

b1

a31

b31

y0

y1

y31

… ……

op

ALU (bit slice)

* = rappresentazioni incomplemento a 2

+

a

b

opcin

cout

0

1

2

y

01

invertiB

--011

Inv.B

00 011 01 01 0

op

a AND ba OR b

(a+b+cin) mod 2(a+NOT b)

(a-b)*

---01

ycin

ALU a 32 bit

cin

cout

ALU0

cin

cout

ALU1

cin

cout

ALU31

a0

b0

a1

b1

a31

b31

y0

y1

y31

… ……

opNegaB

A AND BA OR CA + BA-B

--01

0 00 11 01 0

yNegaBop

Per verificare overflowÈ sufficiente confrontare sein corrispondenza del MSB, cin≠cout

Overflowdetection

Overflow

Supporto ALU per i saltiObiettivo: ampliare la ALU con il test della

condizione a=b (utile per eseguire istruzioni inmodo condizionato - jump)

• Sia Zero la variabile binaria cosi definita:– Zero=1 se e solo se a=b

• Nota che Zero=1 <-> a=b <-> a-b=0– Pertanto Zero=1 se e solo se tutti i bit dell’operazione a-b

sono nulli: Zero coincide col mintermine m0 definito sui nbit r0 … rn-1 che rappresentano la differenza.

– Zero=m0= (not r0)(not r1)…(notrn-1)= not (r0+r1 .. +rn-1)

ALU a 32 bit

cin

cout

ALU0

cin

cout

ALU1

cin

cout

ALU31

a0

b0

a1

b1

a31

b31

y0

y1

y31

… ……

opNegaB

Overflowdetection

Overflow

Zero