Transcription
I circuiti digitali: dalle funzioni logiche aicircuiti (le SOP)Prof. Alberto BorgheseDipartimento di Informaticaalberto.borghese@unimi.itUniversità degli Studi di MilanoRiferimento al testo: Sezione C.3; Approfondimento sulle forme canoniche:Fummi et al., Progettazione Digitale, McGrawHill, capitolo 3.A.A. 2017-20181/41http:\\borghese.di.unimi.it\SommarioI circuiti combinatori.Semplificazione algebrica.Dalla tabella della verità al circuito: la prima forma canonica: SOP.Criteri di ottimalità.A.A. 2017-20182/41http::borghese.di.unimi.it\1
Circuiti combinatori Circuiti logici digitali in cui le operazioni (logiche) dipendono solo da una combinazionedegli input. Come nelle funzioni algebriche, il risultato è aggiornato immediatamente dopo ilcambiamento dell’input (si suppone il tempo di commutazione trascurabile, tempo di attesaprima di guardare l’output sufficientemente ampio per permettere a tutti i circuiti lacommutazione). Circuiti senza memoria. Ogni volta che si inseriscono in ingresso gli stessi valuri, siottengono le stesse uscite. Il risultato non dipende dallo stato del circuito. I circuiti combinatori descrivono delle funzioni Booleane. Queste funzioni si ottengonocombinando tra loro (in parallelo o in cascata) gli operatori logici: NOT, AND, OR. Il loro funzionamento può essere descritto come tabella della verità. Dato un circuito è univoca l’espressione algebrica che ne rappresenta il funzionamento.A.A. 2017-20183/41http::borghese.di.unimi.it\Un po’ di tassonomia Funzione logica. Corrispondenza tra un insieme di ingresso(valori possibili di A, B, C) e insieme di uscita (valori possibilidi F)F A B BC Espressione logica. Combinazione di operatori logici cheimplementa la funzione logica. Ad ogni espressione logica èassociato un ben preciso circuito.AB BCA.A. 2017-20184/41http::borghese.di.unimi.it\2
Regole manipolazione algebrica x xDoppia InversioneIdentitàElemento nulloIdempotenzaAND1x x0x 0xx xOR0 x x1 x 1x x xInversoCommutativaAssociativaxx 0xy yx(x y) z x (y z)x x 1x y y x(x y) z x (y z)AND rispetto ad OROR rispetto ad ANDx (y z) x y x zx (x y) xxy x yx y z (x y ) (x z)x xy xx y xyDistributivaAssorbimentoDe MorganSi possono dimostrare sostituendo 0/1 alle variabili.5/41A.A. 2017-2018http::borghese.di.unimi.it\Regole algebriche su più variabiliCommutativa x y z y x z z x yDistributivaDe Morganx y z y x z z x yAND rispetto ad OROR rispetto ad ANDx (yh z) xyh xzxyz x y zxh yz (xh y) (xh z)x y z x y zSi possono dimostrare sostituendo 0/1 alle variabili.A.A. 2017-20186/41http::borghese.di.unimi.it\3
Una seconda rappresentazioneF A B BCApplico De Morgan ai prodotti logici:F A B B CNB !B e !B non si sommano!!ABCApplico ancora De Morgan e ottengo: 0 0 00 0 10 1 0F (A B)(B C)0 1 11 0 01 0 11 1 01 1 18/41A.A. io – rappresentazione 1A.A. 2017-20189/41http::borghese.di.unimi.it\4
Esempio – tabella 11000011110011001100110011A.A. imi.it\Manipolazione algebricaApplichiamo De Morgan.L A B AC D BC D BC A B AC D BC D B C (A B) (AC D) (B C) ( BC D)A.A. 2017-201811/41xy x yx y xyhttp::borghese.di.unimi.it\5
Esempio – rappresentazione 2ABCD 1010101010101010101111101000111A.A. 2017-201812/41http::borghese.di.unimi.it\SommarioI circuiti combinatori.Semplificazione algebrica.Dalla tabella della verità al circuito: la prima forma canonica: SOP.Criteri di ottimalità.A.A. 2017-201813/41http::borghese.di.unimi.it\6
Semplificazioni notevoliDimostrare che: A AB A BProprietà distributiva di OR rispetto ad AND:A AB (A A) (A B)Sviluppando il prodotto:(A B )(A A) AA A A BA BA A AB ABRaccogliendo A:A AB AB A (A A)B A BNB: posso anche identificare i 3 «1» della funzione OR:A AB A(B B) AB AB AB AB A BA.A. cazioni notevoliDimostrare che: (A B )(B C) AB AC BCDimostrare che: A AB A BA.A. 2017-201815/41http:\\borghese.di.unimi.it\7
Esempio di semplificazione algebrica(esercizio)F ABC ABC ABC Raccogliendo BC:(A A)BC ABC Proprietà dell’inverso: “A A 1” 1BC ABC ABCABCABCProprietà dell’identità: “1B B” BC ABC BCDalla slide precedente: B (C AC) B(C A)A.A. i di manipolazione algebricaF !xyv yz !y!zv !xy!v x!yv F A !B !C A B C A B !C A !B C F A ? Somma di prodotti di 3 variabili: A, B, C (inversodell’esercizio precedente):A.A. 2017-201817/41http::borghese.di.unimi.it\8
EserciziUsare la sola porta NAND per realizzare AND, OR e NOT e disegnarne gli schemilogici Calcolare le TT per le seguenti funzioniDA AC BA B C D D ABC DABC D AB C DAB C Trasformare in funzioni equivalenti le seguenti (ABCD) (DA) (B C)A.A. 2017-201818/41http::borghese.di.unimi.it\SommarioI circuiti combinatori.Dall’espressione logica al circuito. Semplificazione algebrica.Dalla tabella della verità al circuito: la prima forma canonica: SOP.Criteri di ottimalità.A.A. 2017-201819/41http::borghese.di.unimi.it\9
Funzione come espressione logica o cometabella delle veritàF ABC ABABC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1F 1F00100011iifA 0B 1C 0ORA 1B 1C 0ORA 1B 1C 120/41A.A. 2017-2018http::borghese.di.unimi.it\Circuito associatoF 1iifA 0B 1C 0ORA 1B 1C 0ORA 1B 1C 1A.A. 2017-201821/41http::borghese.di.unimi.it\10
La prima forma canonicaF (NOT(A) AND B AND NOT(C)) OR( A AND B) Implicante:prodotto delle variabili (informa asserita o negata) per le quali lafunzione vale 1F ABC ABABC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1F00100011Mintermine, mj,: un implicante checontiene tutte le N variabili della funzione(e.g. ABC) associato agli 1 della funzione.j indica il numero progressivo in base 10.QPrima forma canonica: F mi 1iQ 2NF AB C AB C AB C22/41A.A. 2017-2018http::borghese.di.unimi.it\Mmintermini e MaxterminiF ABC ABABC0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1A.A. 2017-2018F00100011Mintermine, mj,: un implicante checontiene tutte le N variabili della funzione(e.g. ABC) associato agli 1 della funzione.j indica il numero progressivo in base 10.F AB C AB C AB CMaxtermine, Mk: un implicante checontiene tutte le N variabili dellafunzione associato agli 0 della funzione.23/41http::borghese.di.unimi.it\11
Dall’espressione algebrica alla SOP Passare attraverso la tabella della verità F (NOT(A) AND B AND NOT(C)) OR ( A AND B) A B C AB (C C) ABC ABC ABCA.A. 2017-201824/41http::borghese.di.unimi.it\La SOP è la prima forma canonica La forma canonica di una funzione è la somma dei suoi mintermini.Qualunque funzione è esprimibile in forma canonica.Esempio: Z(A,B,C,D) AC BC ABC A(B B)C(D D) (A A)BC (D D) ABC(D D) ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCDLa stessa espressione si ricaverebbe dalla tabella della verità:Z ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABC ABC ABC ABC ABC ABC AC A B C C (A A B) A B C A C B CA.A. 2017-201825/41http::borghese.di.unimi.it\12
Perchè SOP è una forma canonica Forma universale mediante la quale è possibile rappresentare qualunque funzionebooleana. In generale una forma canonica non è una forma ottima, ma un punto di partenza perl’ottimizzazione. Si basa su componenti caratterizzanti la struttura della funzione(mintermine), che traducono le condizioni logiche espresse dalla funzione.Minternine, mi: E’ una funzione booleana a n ingressi che vale 1 in corrispondenza della sola iesima configurazione di ingresso. Al massimo, 2n mintermini per ogni n variabili. ogni mintermine è rappresentabile con un AND con n ingressi.A.A. 2017-201826/41http::borghese.di.unimi.it\Il circuito della prima forma canonica:SOPF ABC ABC ABCA.A. 2017-201827/41http::borghese.di.unimi.it\13
SOP a più usciteRiutilizzo alcune “parti”, in questo caso alcuni mintermini.Ricavare la funzione in forma di tabella della verita’28/41A.A. 2017-2018http::borghese.di.unimi.it\Dalla SOP al circuito: osservazioni Dalla forma canonica (somma di mintermini) è facile passare al circuito:Ogni mintermine è un ANDTutti gli AND entrano in un OR Implementazione regolare Solo due livelli di porte Blocchi generali personalizzabili purché ci sia un numero sufficiente di componentielementari.A.A. 2017-201829/41http::borghese.di.unimi.it\14
SommarioI circuiti combinatori.Dall’espressione logica al circuito. Semplificazione algebrica.Dalla tabella della verità al circuito: la prima forma canonica: SOP.Criteri di ottimalità.30/41A.A. ione logica al circuitoAd ogni espressione logica corrisponde un circuito, ad ogni circuito corrisponde unatabella delle verità, ad ogni tabella della verità, in generale, non corrisponde un unicocircuito possibile. Esistono più espressioni tra loro equivalenti: 2 espressioni sono equivalenti sehanno la stessa tabella di verità. Quale è la “migliore”? È possibile trovare un metodo di semplificazione sfruttando le proprietàdell’algebra booleana. Esistono tecniche automatiche o semi-automatiche di semplificazione.A.A. 2017-201831/41http::borghese.di.unimi.it\15
Valutazione della semplicità di un circuitoArea (numero di porte) “ampiezza”Tempo di commutazione (numero di transistor attraversati “profondità”)Soddisfazione di vincoli, potenza dissipata, facilità di debug.A.A. 2017-201832/41http::borghese.di.unimi.it\Esempio di trasformazione in un’implementazionecon porte a 2 ingressi Gli elementi costruttivi di base tipici sono porte a 2 ingressi– Porta a N ingressi N-1 porte a 2 ingressiNumero di porte: N-1 4Cammino Critico: N-1 4A.A. 2017-201833/41Non è efficientehttp::borghese.di.unimi.it\16
Esempio di trasformazione in un’implementazioneefficiente con porte a 2 ingressiNumero di porte: 4Cammino Critico: 334/41A.A. 2017-2018http::borghese.di.unimi.it\Cammino critico Ogni circuito logico è caratterizzato da un tempo di commutazione– Più porte devo attraversare, più è lungo il tempo della transizione del circuitonel suo complesso. CAMMINO CRITICO– max numero di porte da attraversare da ingresso a uscita– Non si contano gli inverters (inclusi nelle porte)DAABBDECCCFEFT0T0A e C commutano contemporaneamente in To, E raggiunge il valore corretto dopo un tempo 2 DT(la commutazione di D segue la commutazione di B con un ritardo DT.A.A. 2017-201835/41http::borghese.di.unimi.it\17
SOP dell’ORSintetizziamo la funzione OR come SOPY AB AB ABComplessità 5 – Cammino critico 3Semplifico:Y AB AB AB B(A A) AB B AB B A A B OR(A,B)A.A. del camminocriticoo xyzv xyzv xyzv xyzv xyzv xyzv xyzv xyzv xyzvCammino critico pari a 11: cammino più lungo in circuiti con porte a 2 ingressi.Numero di porte: 35.A.A. 2017-201837/41http::borghese.di.unimi.it\18
Semplificazione2o e 3o ANDo x yz v x yz v x y z (v v) x y zCammino critico pari a 10. Numero di porte pari a 30.A.A. zione del cammino criticoRiorganizzando gli ORCammino critico pari a 6. Numero di porte pari a 30.A.A. 2017-201839/41http::borghese.di.unimi.it\19
Criteri di progettoI circuiti a 2 livelli sono difficili da realizzare.Si utilizzano insiemi di porte logiche (FPGA), la cui cablatura viene ricavata mediantecomplesse procedure di ottimizzazione che tengono conto del cammino critico, numero diporte, .Questa procedura si chiama “fitting”.A.A. 2017-201840/41http::borghese.di.unimi.it\SommarioI circuiti combinatori.Dall’espressione logica al circuito. Semplificazione algebrica.Dalla tabella della verità al circuito: la prima forma canonica: SOP.Criteri di ottimalità.A.A. 2017-201841/41http::borghese.di.unimi.it\20
Dipartimento di Informatica alberto.borghese@unimi.it Università degli Studi di Milano Riferimento al testo: Sezione C.3; Approfondimento sulle forme canoniche: . iif A 0 B 1 C 0 OR A 1 B 1 C 0 OR A 1 B 1 C 1. 11 A.A. 2017-2018 22/41 http::borghese.di.unimi.it\ La prima forma canonica
