Sintesi Combinatoria - Intranet DEIBhome.deib.polimi.it/sami/reti_logiche_B/lezione7_comp78.pdf ·...

Sintesi CombinatoriaSintesi CombinatoriaUso di componenti diversi dagli operatori Uso di componenti diversi dagli operatori

elementarielementari

MariagiovannaMariagiovanna SamiSamiCorso di reti Logiche 8Corso di reti Logiche 8

Anno 2007Anno 2007--0808

20072007--0808 -- 22 --

Quali componenti, se non AND e OR (e Quali componenti, se non AND e OR (e NOT…NOT…)?)?

Si è detto inizialmente che i componenti complessi NAND e NOR costituiscono ognuno, individualmente, operatori universali – vale a dire che si può realizzare una qualsiasi funzione logica usando solamente porte NAND o porte NOR.Nella pratica, non si ricorre certo alla sostituzione di AND, ORe NOT con reti di NAND o di NOR…Si consideri una forma a due livelli del tipo POS: è esprimibilein termini generali come

F = p1 + p2 + … + pkdove ogni p2 è un termine prodotto.

20072007--0808 -- 33 --


Si utilizzi ora la proprietà della negazione per cui (x’)’ = x applicandola “da destra verso sinistra”

(F’)’ = ((p1 + p2 + … + pk)’)’ = F

applicando il teorema di De Morgan alla negazione più interna si ottiene

F = (p1’ * p2’* … *pk’)’

Ma ogni p1’ altro non è che un NAND, e l’intero prodotto negato è un altro NAND. Il numero delle porte logiche non è cambiato – sono semplicemente state sostituite tutte da NAND – come non è cambiato il ritardo.

20072007--0808 -- 44 --


Si può ora dedurre la seguente regola generale:Una forma a due livelli POS può essere trasformata in una rete di soli NAND sostituendo semplicemente tutte le porte (AND e OR) con porte NAND e lasciando immutate tutte le variabili, all’infuori delle eventuali variabili che entrano direttamente nell’OR finale, che andranno negate.In modo del tutto duale una forma a due livelli SOP si trasforma in una rete di soli NOR.Per reti a più livelli la trasformazione non è altrettanto immediata; la soluzione più semplice può essere quella di partire dall’uscita e risalire isolando sottoreti a due livelli di tipo opportuno.

20072007--0808 -- 55 --


Esistono altri componenti di uso molto ampio, anche se non costituiscono “operatori universali”; si introdurranno qui brevemente i tre principali – decodificatore (decoder), multiplexer o selettore, demultiplexer;Si presenteranno qui gli schemi logici di tali componenti e il loro uso più generale; nelle librerie tecnologiche esistono soluzioni fortemente ottimizzate, che non sono necessariamente la traduzione uno-a-uno dello schema logico.

20072007--0808 -- 66 --

Il decodificatoreIl decodificatore

Definizione: componente combinatori co n ingressi e n<k≤2n

uscite;In corrispondenza di ogni configurazione degli ingressi, (al più) una delle uscite diventa attiva (nel seguito, si intende che assuma valore 1), mentre tutte le altre restano non attive;Se k< 2n, per alcune delle configurazioni di ingresso nessunadelle uscite diventa attiva:Tipo più diffuso: decodificatore n→ 2n

20072007--0808 -- 77 --


Si consideri dapprima il decodificatore 2→ 4; ha due ingressi x1e x2 e quattro uscite corrispondenti ai quattro mintermini di due variabili; per una qualsiasi configurazione d’ingresso, solo l’uscita la cu posizione corrisponde al “numero d’ordine” codificato dalla configurazione stessa diventa attiva. Le quattro funzioni ‘uscita sono dunque semplicemente:U0= x1 ‘x2 ‘; U1= x1 ‘x2; U2= x1 x2’; ; U3= x1 x2

20072007--0808 -- 88 --


La struttura del decodificatore a due ingressi è:

x y

xy x’y’xy’ x’y

20072007--0808 -- 99 --


Si tratta dunque di una semplice rete a un solo livello – un vettore di quattro porte AND a 2 ingressi (più in generale, per un decodificatore n→ 2n, un vettore di 2n porte AND a n ingressi.Si può notare che per la sintesi di una generica funzione a ningressi basta usare un decodificatore a n ingressi seguito da una porta OR con tanti ingressi quanti sono i mintermini della funzione data. In realtà, questa soluzione non è quasi mai utilizzata.

20072007--0808 -- 1010 --


Il decodificatore costituisce comunque la sezione “di indirizzamento” di una qualsiasi memoria di tipo RAM o ROM (Read Only Memory – memoria a sola lettura): in tal caso, le uscite del decodificatore sono collegate alle “parole” della memoria, e le configurazioni d’ingresso rappresentano gli indirizzi delle parole stesse;Applicando agli ingressi della sezione di decodifica un indirizzo, si attiva la linea corrispondente alla parola indirizzata (e solo quella).

20072007--0808 -- 1111 --


La realizzazione di un decodificatore con un numero elevato di ingressi in realtà non viene fatta usando porte AND con altrettanti ingressi, ma ricorrendo piuttosto a strutture “ad albero” costruite utilizzando decodificatori più piccoli. Ad esempio,si costruisca un decodificatore a quattro in gressi e sedici uscite partendo da decodificatori a 2 ingressi (e quattrouscite):

20072007--0808 -- 1212 --


a

b

c d

a’b’

a’b

ab’

ab

c’d’ c’dcd’

cd

a’b’c’d’

a’b’c’d

20072007--0808 -- 1313 --


Si ha quindi una struttura a due livelli di porte AND; chiaramente, questo tipo di struttura può essere iterata (due decodificatori 2→4 e 16 porte AND a due ingressi per realizzarne uno 4 →16, due decodificatori 4 →16 e 64 porte AND a due ingressi per realizzarne uno 8 →64, e così via).

20072007--0808 -- 1414 --

Il Il multiplexermultiplexer

Un altro componente complesso di uso molto esteso è il selettore, detto anche multiplexer (spesso abbreviato con la sigla MUX).Il multiplexer è dotato di due diversi insiemi di ingressie di una sola uscita z. Gli ingressi si suddividono in ingressi di selezione (o di indirizzamento) I1…Ike ingressi di dati D1…Dn, dove n ≤2k. Di norma si parla di “MUX a n ingressi”, facendo riferimento quindi ai soli ingressi di datiIl funzionamento del multiplexer si riassume rapidamente; per ogni configurazione degli ingressi di selezione, si trasferisce all’uscita z il valore presente sull’ingresso di dati indirizzato dalla configurazione di selezione.

20072007--0808 -- 1515 --


In pratica, il MUX può essere visto come una specie di “interruttore rotante” che collega all’uscita uno (e uno solo) degli ingressi di dati, a seconda della configurazione di selezione. Si consideri ad esempio un MUX con due ingressi di selezione I0I1 e quattro ingressi di dati D0…D3; la funzione logica che lo rappresenta èZ = I0’I1’ D0 + I0’I1 D1 + I0I1’ D2 + I0I1 D3

Si tratta quindi di una semplice forma SOP.

20072007--0808 -- 1616 --


Il MUX trova ampio uso nelle architetture digitali per “instradare” l’informazione sulla base di opportuni segnali di controllo (che si applicano come ingressi di selezione); è però interessante osservare che lo stesso dispositivo può essere usato per sintetizzare una generica funzione di commutazione (e in realtà spesso lo è). A questo scopo, si assume come elemento di partenza un MUX a due ingressi, che richiede quindi un solo bit di selezione.

D0

D1

I

zMUX

20072007--0808 -- 1717 --


Sia data una generica funzione F(x1…xm); si ricordi il teorema di espansione di Shannon, e lo si applichi – ad esempio – rispetto alla variabile x1. Il teorema di Shannon ci porta a F(x1…xm)= x1’F(0…xm)+x1F(1…xm) = x1’F0 + x1F1. Si può realizzare tale nuova forma applicando la variabile x1 come ingresso di selezione a un MUX a due ingressi (o “vie”) e le due funzioni F0 ed F1 ai due ingressi dati del MUX.

F0

F1

x1

FMUX

20072007--0808 -- 1818 --


Si può evidentemente ripetere questa operazione espandendo sia F0 sia F1 rispetto alla variabile x2, ottenendo quattro funzioni F00, F01, F10, F11 che dovranno essere applicate agli ingressi di due MUX, ambedue aventi x2 come ingresso di selezione:

x2

F0

MUX

x1

F

MUX

x2

F1

MUX

F00

F01

F10F11

Si noti: il percorso tratteggiato in rosso

corrisponde a x1’x2’F00, e così via.

20072007--0808 -- 1919 --


Procedendo, si costruisce un “albero” a m livelli di MUX a due ingressi, e agli ingressi di dati del livello più lontano dall’uscita (che sono esattamente 2m, come è ovvio) si applica direttamente la tabella delle verità della funzione data. Sia data ad esempio una funzione di tre variabili: f(a,b,c): ON-set 1,2,4,7. La sua realizzazione sulla base di quanto ora detto richiede un albero a tre livelli di MUX, per un totale di sette MUX a due vie:

20072007--0808 -- 2020 --


a

F

MUX

b

MUX

b

MUXc

MUX

cMUX

c

MUX

c

MUX

0

1

1

0

1

0

0

1

20072007--0808 -- 2121 --


La struttura ora ricavata è in realtà ridondante; considerando le coppie di valori applicati agli ingressi di ogni MUX di livello 3, essi possono essere solo “00” (cioè la costante 0, indipendentemente dal valore di c), “01” (cioè il valore di c stesso), “10” (il valore di c’) o “11” (la costante 1). È quindi sufficiente un albero di 2 soli livelli (in genere, di m-1 livelli):

a

F

MUX

b

MUX

b

MUX

c’

c

c’

c

20072007--0808 -- 2222 --


In genere, la sintesi di un a generica rete logica mediante MUX a due vie ammette spesso notevoli semplificazioni, così che il numero totale di MUX necessari può essere decisamente inferiore a 1+2+4+…+2m-1. Le possibili semplificazioni dipendono fortemente dall’ordine rispetto a cui si applica l’espansione. Si consideri ad esempio la funzione F(a,b,c,d): ON-set (4,6,8,9,11,12). Si proceda dapprima all’espansione secondo l’ordine naturale della variabili (da a fino a c). Si costruisce per prima cosa la tabella delle verità

20072007--0808 -- 2323 --


01 1 1 1

01 1 1 0

01 1 0 1

11 1 0 0

11 0 1 1

01 0 1 0

11 0 0 1

11 0 0 0

00 1 1 110 1 1 000 1 0 110 1 0 000 0 1 1 00 0 1 000 0 0 100 0 0 0Fa b c d

Espandere rispetto alla variabile a significa estrarre due funzioni Fa0ed Fa1 ambedue dipendenti da b,c,d, come in figura

Fa0

Fa1

FMUXFa0

Fa1

a

20072007--0808 -- 2424 --


01 1 111 1 001 0 111 0 000 1 1 00 1 000 0 100 0 0

Fa0b c d

Si esplicitano ora le tabelle delle verità delle due funzioni Fa0 (b,c,d) e Fa1(b,c,d) , che verranno espanse ambedue rispetto a b

Fa0

Fa1

01 1 101 1 001 0 111 0 010 1 1 00 1 010 0 110 0 0

Fa1b c d

20072007--0808 -- 2525 --


01 1 01 000 100 0

Fab00c dSi esplicitano ora le tabelle delle verità delle funzioni Fab00 (c,d), Fab01(c,d), Fab10 (c,d), Fab11(c,d), che vengono espanse rispetto a c

Fab00

01 1 11 000 110 0

Fab00c d

Fab01

11 1 01 010 110 0

Fab00c d

Fab10

01 1 01 000 110 0

Fab00c d

Fab11

20072007--0808 -- 2626 --


L’espansione finora raggiunta corrisponde a :

FMUX

aMUX0

b

MUX1

b

Fab00

Fab01

Fab10

Fab11

20072007--0808 -- 2727 --


Prima di procedere a ulteriori espansioni, si può notare che:

1. Fab00 = 0 indipendentemente dal valore di c o d –all’ingresso superiore (selezionato con b=0) di MUX0 si applica direttamente la costante 0;

2. Fab01 = d’ indipendentemente dal valore di c –all’ingresso inferiore (selezionato con b=1) di MUX0 si applica direttamente la variabile d’;

20072007--0808 -- 2828 --


Si ha quindi una prima semplificazione nello schema che si sta realizzando:

FMUX

aMUX0

b

MUX1

b

0

c’

Fab10

Fab11

20072007--0808 -- 2929 --


Infine, espandendo rispetto a c si raggiunge la struttura finale:

FMUX

a

MUX0

b

MUX1

b

0

c’

MUX10

c

1

dMUX11

c

d’

0

20072007--0808 -- 3030 --


Il costo è quindi di cinque MUX a due vie, anziché di 7. Si lascia al lettore di esplorare il costo che si otterrebbe con un’espansione – ad esempio – che riordini le variabili nella sequenza “cdab”.Non esistono soluzioni rigorose per stabilire l’ordine ottimo di espansione; si procede solo sulla base di “buone pratiche”, esplorando la struttura della tabella delle verità

20072007--0808 -- 3131 --

Il Il demultiplexerdemultiplexer

L’ultimo componente logico di ampio uso (anche se non certo di applicabilità generale nella sintesi logica quanto il multiplexer o anche il decodificatore) è il de-multiplexer, la cui struttura e comportamento possono essere riassunti come segue:Il demux è dotato di k ingressi di selezione I1, … Ik, un solo ingresso dati D e n≤2k uscite z1,…,zn.La configurazione applicata agli ingressi di selezione indica a quale delle uscite verrà trasferito il valore applicato agli ingressi dati.

20072007--0808 -- 3232 --


In sostanza, anche il demux può essere visto come un commutatore controllato, da 1 a n linee. Lo si usa, tipicamente, nelle architetture digitali per distribuire sulla base di un opprtunocontrollo l’informazione che viene da una sorgente a più destinazioni alternative.

20072007--0808 -- 3333 --


Si consideri a titolo di esempio un Demux a 2 uscite; le sue equazioni di funzionamento sono z0 = I’Dz1 = ID

D

I

Z0

Z1

Sintesi Combinatoria - Intranet DEIBhome.deib.polimi.it/sami/reti_logiche_B/lezione7_comp78.pdf ·...

Documents

Transcript of Sintesi Combinatoria - Intranet DEIBhome.deib.polimi.it/sami/reti_logiche_B/lezione7_comp78.pdf ·...