Reti combinatorie
Porte logiche, algebra di Boole, decoder e multiplexer, sintesi a costo minimo
Un calcolatore, visto da vicino, è un enorme intreccio di circuiti che elaborano segnali a due valori. Questo modulo parte dal modello che ci permette di ragionarci sopra, la rete logica, e arriva a progettare, a partire da una tabella, il circuito più economico che la realizza. Molti schemi sono interattivi: clicca sugli ingressi e guarda i fili che portano un 1 colorarsi di rosso.
Le reti logiche come modello
Variabili logiche e segnali fisici
Immaginiamo due scatole collegate da un filo: a sinistra si può impostare una tensione tra 0 e 5 volt, a destra c'è una lampadina. Se ci interessa soltanto sapere se la lampadina è accesa o spenta, possiamo dimenticare la fisica e dire che sul filo viaggia una variabile logica w, che vale 0 o 1. Una tensione bassa (tra 0 e 0,8 V) vale 0, una alta (tra 2 e 5 V) vale 1; in mezzo c'è una fascia in cui il valore non è determinato.
Rete logica. Modello astratto di un sistema fisico fatto di dispositivi che si scambiano informazioni codificate in due valori. È caratterizzata da:
- N variabili logiche di ingresso: i loro valori in un istante formano lo stato di ingresso; gli stati possibili sono 2N;
- M variabili logiche di uscita, che formano lo stato di uscita;
- una legge di evoluzione nel tempo, che dice come le uscite dipendono dagli ingressi.
Il modello astrae sia dal fenomeno fisico (tensioni, correnti, magnetizzazione: non importa) sia da chi usa la rete (chi imposta gli ingressi e chi legge le uscite). È proprio questa astrazione a renderlo potente.
Combinatorie e sequenziali, asincrone e sincronizzate
Le reti logiche si classificano secondo due criteri, entrambi legati alla legge di evoluzione:
- memoria: nelle reti combinatorie lo stato di uscita dipende solo dallo stato di ingresso presente, come una funzione matematica; nelle reti sequenziali dipende anche dalla storia degli ingressi passati, e quindi la rete deve ricordare;
- temporizzazione: nelle reti asincrone le uscite si adeguano agli ingressi continuamente; nelle reti sincronizzate solo in certi istanti, scanditi da un segnale di sincronizzazione (il clock).
| asincrona | sincronizzata | |
|---|---|---|
| combinatoria | reti combinatorie (questo modulo) | caso particolare di quella sotto |
| sequenziale | reti sequenziali asincrone (latch, flip-flop) | reti sequenziali sincronizzate (registri, contatori, automi) |
I limiti del modello
Ogni modello trascura qualcosa. Il nostro trascura due fatti fisici, che conviene avere sempre presenti:
- Le transizioni non sono istantanee. Una tensione passa da un livello all'altro in un tempo Δt, attraversando la fascia di indeterminazione. Il modello funziona se Δt è molto minore del tempo ΔT per cui i segnali restano stabili: allora possiamo dire, con un piccolo abuso, che la variabile «cambia all'istante t0».
- Due segnali non cambiano mai esattamente insieme. Se lo stato di ingresso passa da 10 a 01, la rete vedrà per un attimo uno stato intermedio, 11 oppure 00, a seconda di quale ingresso arriva prima. Nelle reti asincrone bisogna quindi supporre che stati di ingresso consecutivi siano adiacenti, cioè che differiscano per un solo bit.
Le reti combinatorie
Definizione e tempo di attraversamento
Una rete combinatoria ha N ingressi, M uscite e una descrizione funzionale F: X → Z che associa a ogni stato di ingresso uno stato di uscita. La legge di evoluzione è semplice: continuamente, detto X lo stato di ingresso, la rete porta l'uscita a F(X).
Nessun circuito reale però risponde all'istante. Una rete ha un tempo di attraversamento (o di risposta): dire che è di 20 ns significa che, 20 ns dopo un cambiamento degli ingressi, l'uscita si è adeguata e la rete è a regime.
Tabelle di verità, descrizione e sintesi
Il modo più immediato per descrivere una rete combinatoria è la tabella di verità: a sinistra tutti gli stati di ingresso, a destra le uscite corrispondenti. Si dice che un'uscita riconosce gli stati di ingresso in cui vale 1.
| x2 | x1 | x0 | z1 | z0 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
Qui z1 riconosce gli stati 010, 011, 100, 101 e z0 gli stati 001, 100, 101. A volte, per un certo stato di ingresso, il valore dell'uscita non interessa, per esempio perché quello stato non si presenterà mai. Allora si scrive un trattino, «–», detto non specificato. Non è un terzo valore logico: l'uscita varrà comunque 0 o 1, semplicemente ci riserviamo di scegliere più tardi il valore che renderà il circuito più economico.
Descrizione
Dice che cosa fa la rete: il suo comportamento osservabile. Si dà a parole, con una tabella di verità, con espressioni booleane o con un linguaggio come il Verilog.
Sintesi
Dice come è fatta: quali componenti usare e come collegarli perché si comporti come descritto. Per ogni tipo di rete vedremo come si descrive e come si sintetizza.
Quante reti combinatorie esistono
Una rete con N ingressi e un'uscita è definita dalla sua tabella, che ha 2N righe; in ciascuna l'uscita vale 0 o 1. Le tabelle diverse, e quindi le reti diverse, sono 22N. Con due ingressi sono 16: due sono costanti, quattro ripetono un ingresso (diretto o negato), le altre sono le porte che vedremo tra poco. Con tre ingressi le reti diverse sono già 28 = 256. Una rete con più uscite, poi, si può sempre pensare come M reti a un'uscita messe una accanto all'altra: per questo ci concentreremo sulle reti a un'uscita.
Le porte logiche
NOT, AND, OR e le altre
Le reti combinatorie più semplici si chiamano porte. Si trovano in commercio come componenti elettronici e sono i mattoni con cui si costruisce tutto il resto.
- NOT (invertitore): l'uscita è il contrario dell'ingresso.
- AND: l'uscita vale 1 solo se tutti gli ingressi valgono 1.
- OR: l'uscita vale 1 se almeno uno degli ingressi vale 1.
- XOR (OR esclusivo): l'uscita vale 1 se gli ingressi sono diversi.
- NAND, NOR, XNOR: le tre precedenti con l'uscita negata. La XNOR vale 1 se gli ingressi sono uguali.
- L'elemento neutro (buffer) ripete l'ingresso. Sembra inutile, ma serve a ritardare un segnale e a rigenerarlo: una rete logica interpreta correttamente ingressi un po' degradati e produce uscite vicine al fondo scala, ripulendo il segnale.
AND e OR a più ingressi
Una AND a N ingressi vale 1 se tutti gli ingressi valgono 1; una OR a N ingressi se almeno uno vale 1. Si possono costruire con N − 1 porte a due ingressi, ma conta come le si dispone: il segnale deve attraversare il minor numero possibile di porte, cioè di livelli di logica, perché ogni livello aggiunge ritardo.
Con le XOR succede una cosa interessante: un albero di XOR non generalizza la XOR «a due», ma riconosce gli stati di ingresso con un numero dispari di 1. Con le NAND e le NOR, invece, l'albero non dà né una NAND né una NOR a più ingressi: provalo con un esempio.
È il bit di parità: aggiunto a un dato, permette a chi lo riceve di accorgersi se un bit si è corrotto lungo la strada. Con le XNOR si riconosce invece un numero pari di 1.
Algebra di Boole
Operatori e proprietà
L'algebra di Boole descrive le reti combinatorie con espressioni. Lavora su variabili a due valori con tre operatori, definiti elencando tutti i casi: il complemento x (realizzato dalla NOT), il prodotto logico x · y (la AND) e la somma logica x + y (la OR). Le proprietà che seguono si dimostrano tutte con la tabella di verità, e vanno conosciute bene perché ogni semplificazione si basa su di esse.
| Proprietà | Per la somma | Per il prodotto |
|---|---|---|
| involutiva | complementare due volte restituisce x | |
| commutativa | x + y = y + x | x · y = y · x |
| associativa | (x + y) + z = x + (y + z) | (x · y) · z = x · (y · z) |
| distributiva | x + y · z = (x + y) · (x + z) | x · (y + z) = x · y + x · z |
| complementazione | x + x = 1 | x · x = 0 |
| elementi neutro e assorbente | x + 0 = x, x + 1 = 1 | x · 1 = x, x · 0 = 0 |
| idempotenza | x + x = x | x · x = x |
| assorbimento | x + x · y = x | x · (x + y) = x |
Attenzione alla distributiva: a differenza dell'aritmetica, in Boole vale in tutti e due i versi, anche la somma rispetto al prodotto. Per abbreviare, il punto del prodotto spesso si omette: xy vuol dire x · y.
Principio di dualità. Le due colonne della tabella sono speculari: ogni proprietà della somma diventa quella del prodotto scambiando + con · e 0 con 1, lasciando le variabili come sono. Vale in generale: se un'identità è vera, è vera anche la sua duale, perciò ogni teorema dimostrato ne regala un secondo. Non va confusa con la negazione: la duale di x + 0 = x è x · 1 = x, e nessuna variabile viene negata.
I teoremi di De Morgan
Sono le due identità più usate di tutta la materia, e valgono per un numero qualsiasi di variabili:
x0 · x1 · … · xN−1 = x0 + x1 + … + xN−1
x0 + x1 + … + xN−1 = x0 · x1 · … · xN−1
«Il complemento di un prodotto è la somma dei complementi, e viceversa». Per due variabili si verifica con la tabella di verità; il caso generale si dimostra per induzione: chiamato α il prodotto delle prime N variabili, si applica il caso a due variabili ad α · xN e poi l'ipotesi induttiva ad α. In termini di circuiti, De Morgan dice che una bolla di negazione si può «spostare» attraverso una porta scambiando AND e OR:
Applicando De Morgan più volte, dall'esterno verso l'interno, si nega qualsiasi espressione. Il risultato si riassume in una regola pratica: si scambiano + e ·, si scambiano 0 e 1, e si nega ogni letterale (in pratica si scrive la duale con i letterali negati). La trappola è la precedenza: il prodotto lega più forte della somma, e quando diventa una somma va protetto con le parentesi.
Sbagliato
a + bc = a · b + c
Scambiando gli operatori «a occhio» si perde il raggruppamento: bc era un prodotto, e il suo complemento deve restare tutto insieme.
Giusto
a + bc = a · bc = a · (b + c)
Un passo alla volta: prima De Morgan sulla somma esterna, poi sul prodotto. Per scoprire l'errore basta una riga: con a = 1 e c = 0 l'espressione di partenza vale 1, quindi il complemento deve valere 0; la versione giusta dà 0, quella sbagliata 1.
Espressioni, circuiti e costo
Tra espressioni booleane e reti combinatorie c'è una corrispondenza perfetta: ogni rete si descrive con un'espressione per ciascuna uscita, e ogni espressione si realizza con una rete. Espressioni equivalenti (trasformabili l'una nell'altra con le proprietà) danno reti logicamente equivalenti, che però possono avere costi molto diversi.
Un esempio di semplificazione algebrica: il cosiddetto teorema del consenso. Il trucco è moltiplicare un termine per 1 = x1 + x1, sviluppare e raccogliere:
x1x2 + x1x3 + x2x3 = x1x2 + x1x3 + (x1 + x1)x2x3
= x1x2(1 + x3) + x1x3(1 + x2) = x1x2 + x1x3
Il termine x2x3 è superfluo: un'intera porta AND risparmiata. Fare questi conti a occhio però è artigianale; tra poco vedremo un metodo sistematico.
Teoremi utili, dimostrati con l'algebra
Oltre alle proprietà di base, nelle semplificazioni tornano sempre le stesse poche identità. Conviene saperle dimostrare, non solo ricordare: bastano due righe, e la dimostrazione fa vedere quali mosse usare negli esercizi. Ognuna ha la sua duale, che si ottiene gratis.
| Nome | Identità | Duale | Dimostrazione |
|---|---|---|---|
| assorbimento | x + xy = x | x(x + y) = x | x + xy = x(1 + y) = x · 1 = x |
| letterale superfluo | x + xy = x + y | x(x + y) = xy | distributiva della somma: x + xy = (x + x)(x + y) = 1 · (x + y) |
| fusione | xy + xy = x | (x + y)(x + y) = x | xy + xy = x(y + y) = x · 1 = x |
| consenso | xy + xz + yz = xy + xz | (x + y)(x + z)(y + z) = (x + y)(x + z) | vista qui sopra: yz = (x + x)yz, poi assorbimento |
| idempotenza «al contrario» | α = α + α | α = α · α | è l'idempotenza letta da destra a sinistra: permette di usare un termine in due fusioni |
La seconda è la più sottovalutata. In x + xy il letterale x è superfluo: quando x = 1 il risultato è 1 comunque, e quando x = 0 la condizione x è già vera. Ragionare così, «caso x = 0, caso x = 1», è un ottimo modo per controllare una semplificazione: è l'espansione di Shannon.
Come si semplifica un'espressione
A mano non c'è una procedura che garantisca il risultato minimo (per quello servono Quine-McCluskey e le mappe di Karnaugh), ma una sequenza di mosse che funziona quasi sempre:
- Portare le negazioni sui letterali con De Morgan, dall'esterno verso l'interno, e togliere le doppie negazioni.
- Sviluppare con la distributiva fino a una somma di prodotti; cancellare i prodotti che contengono xx (valgono 0) e le lettere ripetute (xx = x).
- Fondere le coppie di termini che differiscono per una sola variabile, diretta in uno e negata nell'altro: αx + αx = α. Se un termine serve a due fusioni, prima lo si duplica (α = α + α).
- Assorbire: un termine che contiene per intero un altro termine sparisce (α + αβ = α), un letterale negato inutile pure (x + xβ = x + β).
- Controllare il risultato su qualche riga della tabella di verità, scegliendo righe in cui l'espressione cambia valore. Con tre o quattro variabili conviene controllarle tutte.
Per i prodotti di somme si usano le mosse duali: la fusione diventa (α + x)(α + x) = α e l'assorbimento α(α + β) = α.
Esercizi svolti di algebra di Boole
Le tracce vengono dalle dispense e dalle lezioni del corso. In ogni passaggio, a destra, c'è la proprietà usata: è proprio quello che all'esame fa la differenza tra un conto giusto e un conto «che torna». Prova a fare ogni esercizio prima di leggere lo svolgimento.
Esercizio 1 Semplificare una somma di prodotti
Semplificare al massimo, con le proprietà dell'algebra:
f = abcd + abcd + abcd + abd + bcd + abd
Prima di cominciare conviene guardare i termini a coppie. Il primo, abcd, differisce dal secondo solo per b e dal terzo solo per a: può fondersi con tutti e due, purché lo si scriva due volte. Anche abd e abd differiscono per la sola a.
Si passa da sei AND (tre a quattro ingressi e tre a tre) e una OR a sei ingressi a tre AND e una OR a tre ingressi: il costo a porte scende da 7 a 4, quello a diodi da 27 a 11.
È il minimo? Lo strumento qui sotto è una mappa di Karnaugh, che si spiega più avanti: per ora basta leggerne il risultato. La funzione ha due sintesi SP di costo minimo: questa e f = abc + bcd + bd, che costa uguale, perché lo stato abcd si può coprire in due modi. L'algebra ha trovato una buona forma, il metodo sistematico le trova tutte. E il pulsante «Sintesi PS» mostra che la forma PS, (b + d)(c + d)(a + b + d), costa ancora un diodo in meno.
Esercizio 2 Semplificare un prodotto di somme
Semplificare al massimo:
g = (a + b + c)(a + b + c)(a + b + c)(a + b + c)(a + b)
È la versione duale del precedente: i fattori che differiscono per una sola variabile si fondono con (α + x)(α + x) = α, che è la distributiva della somma rispetto al prodotto.
Cinque OR e una AND a cinque ingressi si riducono a una sola AND a due ingressi (più gli invertitori sugli ingressi, che non si contano). Controllo: g deve valere 1 solo per a = b = 0, e infatti con b = 0 i primi quattro fattori contengono b = 1 e l'ultimo vale a. Il passo chiave è lo stesso dell'esercizio 1, letto allo specchio: un fattore usato due volte grazie all'idempotenza.
Esercizio 3 Dimostrare un'identità
Dimostrare che
(x1 + x2)(x2 + x3)(x1 + x3) = (x1 + x2)(x1 + x3)
La risposta più breve è una riga: è la duale del teorema del consenso, già dimostrato, quindi è vera. Rifarla però allena alle mosse duali. Il trucco è lo stesso del consenso: si «gonfia» il fattore superfluo aggiungendogli un termine nullo, x1x1, e lo si fa poi assorbire.
Come si legge il risultato: il fattore (x2 + x3) vale 0 solo quando x2 = x3 = 0, ma in quel caso uno tra (x1 + x2) e (x1 + x3) vale già 0, qualunque sia x1. Non aggiunge nulla.
Esercizio 4 Negare un'espressione
Data z = ab + c(a + d), scrivere z come somma di prodotti.
Controllo su una riga: con a = b = c = 1 e d = 0 si ha z = 1 · 0 + 1 · (0 + 0) = 0, quindi z deve valere 1; e infatti l'ultimo termine, abd, vale 1. Fermandosi alla quarta riga e applicando la distributiva della somma a (c + ad) si ottiene invece una forma PS: z = (a + b)(a + c)(c + d), pronta per la sintesi a porte NOR.
Esercizio 5 Da somma di prodotti a prodotto di somme
Trasformare z = ab + cd in forma PS, cioè in un prodotto di somme.
Serve la distributiva della somma rispetto al prodotto, α + βγ = (α + β)(α + γ): è la mossa che in aritmetica non esiste, ed è quella che fa il lavoro.
La forma SP costa 3 porte e 6 diodi, la PS 5 porte e 12 diodi: per questa funzione la PS non conviene. Non c'è una regola generale, dipende dalla funzione: per questo la sintesi di costo minimo si fa in tutte e due le forme e poi si confronta.
Esercizio 6 Analizzare una rete: che cosa calcola?
La rete qui sotto è fatta di quattro porte NAND. Scrivere l'espressione dell'uscita in funzione degli ingressi e semplificarla. Prima di leggere la soluzione, prova a capirlo dalla tabella di verità del circuito.
Ogni NAND vale 0 solo quando entrambi i suoi ingressi valgono 1.
Si procede dagli ingressi verso l'uscita, dando un nome a ogni filo interno:
È lo XOR, costruito con sole NAND (lo si sapeva possibile, perché la NAND è universale; qui si vede come). Il filo w vale 0 solo quando x = y = 1: in quel caso porta a 1 sia p sia q, e l'uscita va a 0 proprio nell'unico caso in cui gli ingressi a 1 sono due.
L'algebra dello XOR
Lo XOR, x ⊕ y = xy + xy, vale 1 quando i due ingressi sono diversi. Non è uno degli operatori dell'algebra di Boole, ma compare dappertutto: nei sommatori, nei controlli di parità, in reti come quella appena analizzata. Le sue proprietà si verificano con la tabella di verità:
| Proprietà | Identità | Che cosa vuol dire |
|---|---|---|
| commutativa e associativa | x ⊕ y = y ⊕ x (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) | si scrive x ⊕ y ⊕ z senza parentesi, in qualunque ordine |
| elemento neutro | x ⊕ 0 = x | uno 0 lascia passare l'altro ingresso |
| invertitore comandato | x ⊕ 1 = x | un 1 nega l'altro ingresso |
| annullamento | x ⊕ x = 0 x ⊕ x = 1 | un termine ripetuto due volte si cancella |
| distributiva | x(y ⊕ z) = xy ⊕ xz | il prodotto si distribuisce sullo XOR, ma non il viceversa |
| complemento | x ⊕ y = x ⊕ y = x ⊕ y | è lo XNOR; negando entrambi gli ingressi non cambia nulla: x ⊕ y = x ⊕ y |
Le due regole d'oro. Con α ⊕ α = 0 e α ⊕ 0 = α lo XOR si «risolve» come un'equazione: se a ⊕ b = c, facendo ⊕ b da tutte e due le parti si ha a ⊕ b ⊕ b = c ⊕ b, cioè a = c ⊕ b. Un termine passa da un membro all'altro senza cambiare segno. E, contando gli 1: x1 ⊕ x2 ⊕ … ⊕ xn vale 1 se e solo se un numero dispari di variabili vale 1. È la parità, e la useremo tra poco.
Esercizio 7 La distributiva dello XOR
Dimostrare con l'algebra che x(y ⊕ z) = xy ⊕ xz.
Il contrario invece è falso: x ⊕ yz e (x ⊕ y)(x ⊕ z) sono diverse. Per dimostrare che un'identità è falsa basta un controesempio: con x = 1, y = 1, z = 0 la prima vale 1 ⊕ 0 = 1 e la seconda 0 · 1 = 0.
Decoder, demultiplexer e multiplexer
Il decoder
Un decoder N to 2N ha N ingressi e 2N uscite: ogni uscita riconosce uno e un solo stato di ingresso. L'uscita zj vale 1 se e solo se gli ingressi, letti come numero in base 2, valgono j. Ogni uscita è quindi il prodotto di tutti gli ingressi, diretti o negati: per due ingressi
z0 = x1x0 z1 = x1x0 z2 = x1x0 z3 = x1x0
Servono 2N AND a N ingressi e N invertitori, messi direttamente sugli ingressi (metterli davanti a ogni AND ne richiederebbe molti di più). La tabella di verità di un decoder è una matrice identità.
Decoder con enabler e decoder in cascata
Il decoder appena visto non è espandibile: non si possono costruire decoder grandi mettendo insieme quelli piccoli. Si aggiunge allora un ingresso di abilitazione e (enabler): se e = 1 la rete funziona da decoder, se e = 0 tutte le uscite valgono 0. Poiché y · 1 = y e y · 0 = 0, basta aggiungere e come ingresso in più a ogni AND: zj = e · (prodotto di prima). Mettere invece una seconda AND in cascata sarebbe uno spreco: due porte uguali in cascata si fondono sempre in una sola.
Il demultiplexer
Un demultiplexer (o demux) ha N + 1 ingressi e 2N uscite. Uno degli ingressi, x, è la variabile da commutare; gli altri N, bN−1 … b0, sono le variabili di comando. In pratica è un selezionatore: le variabili di comando decidono quale uscita è collegata all'ingresso.
La descrizione funzionale, a parole, è questa:
l'uscita zj insegue x se e solo se (bN−1 … b1 b0)2 = j; altrimenti vale 0
«Insegue» vuol dire che, finché i comandi non cambiano, l'uscita scelta ha lo stesso valore di x istante per istante (a meno del tempo di attraversamento). Per un demultiplexer 1 to 4 la tabella di verità si può scrivere in forma compatta, con x nelle caselle:
| b1 | b0 | z3 | z2 | z1 | z0 |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | x |
| 0 | 1 | 0 | 0 | x | 0 |
| 1 | 0 | 0 | x | 0 | 0 |
| 1 | 1 | x | 0 | 0 | 0 |
La tabella completa avrebbe 8 righe (con x = 0 tutte le uscite valgono 0); questa forma è più leggibile e dice la stessa cosa.
Dalla descrizione alle porte
Si ragiona un'uscita alla volta. Per z0 serve una rete che dia x quando i comandi valgono 00…0 e 0 altrimenti. «I comandi valgono 00» è un prodotto, b1 · b0, che vale 1 solo in quel caso. E poiché α · 1 = α e α · 0 = 0, moltiplicare per quel prodotto lascia passare x o lo azzera:
z0 = x · b1 · b0 z1 = x · b1 · b0 z2 = x · b1 · b0 z3 = x · b1 · b0
In generale zj = x · (prodotto di tutte le variabili di comando, negate dove la cifra j-esima vale 0). Servono 2N porte AND a N + 1 ingressi e N invertitori, messi una volta sola sulle variabili di comando. Prova: scegli un'uscita con b1 b0, poi accendi e spegni x.
Ogni AND riceve x più una delle combinazioni di b1 b0: è un decoder 2 to 4 con l'ingresso x al posto dell'enabler.
Decoder con enabler e demultiplexer sono la stessa rete. Confrontando le espressioni con quelle del decoder con enabler, zj = e · (prodotto degli ingressi), cambiano solo i nomi: l'enabler e diventa la variabile da commutare x, gli ingressi del decoder diventano le variabili di comando. Si sceglie il nome in base all'uso: «decoder» se interessa riconoscere uno stato di ingresso, «demultiplexer» se interessa instradare un segnale.
Due equivoci frequenti
Pensare che le uscite non scelte siano «scollegate»: valgono 0, e un'altra rete che le legge vede uno 0 vero, non un'alta impedenza (quella la danno le porte tri-state). E pensare che un demultiplexer sia un multiplexer usato al contrario: le porte hanno un verso, i segnali non tornano indietro.
Come ragionarci
Il demultiplexer è una rete combinatoria come le altre, con 2N uscite sempre definite: una vale x, tutte le altre 0. Il suo duale, il multiplexer, ha invece 2N ingressi e una sola uscita; insieme permettono di far passare più segnali, uno alla volta, su un unico filo.
Demultiplexer grandi con demultiplexer piccoli
Proprio perché è un decoder con enabler, il demultiplexer è espandibile. Un 1 to 8 si ottiene con un 1 to 2 al primo livello, comandato dalla variabile più significativa b2, che manda x a uno di due 1 to 4 comandati da b1 b0. Il demultiplexer del secondo livello che non viene scelto riceve 0 e tiene a 0 tutte le sue uscite, come deve.
La variabile di comando più significativa, b2, sta al primo livello: così le uscite si numerano in ordine, zj con j = (b2 b1 b0)2. Il demultiplexer del secondo livello che non viene scelto riceve 0, quindi tutte le sue uscite valgono 0.
Mettere la variabile più significativa al primo livello non è obbligatorio, ma fa sì che le uscite si numerino in ordine: le prime quattro sono quelle con b2 = 0. Con la scelta opposta la rete funziona lo stesso, ma le uscite vanno ricollegate con un'altra numerazione.
Esercizio. Costruire un demultiplexer 1 to 16 usando solo demultiplexer 1 to 4. Quanti ne servono, e come si collegano?
Soluzione
Servono due livelli, perché ogni livello consuma due variabili di comando. Al primo un demultiplexer 1 to 4 riceve x ed è comandato da b3 b2; le sue quattro uscite fanno da variabile da commutare per altri quattro demultiplexer 1 to 4, tutti comandati da b1 b0. In tutto cinque demultiplexer, esattamente come il decoder 4 to 16 fatto con cinque decoder 2 to 4 con enabler: è la stessa costruzione. In generale per un 1 to 2N con blocchi 1 to 2k servono ⌈N/k⌉ livelli.
Il demultiplexer in Verilog
Anche qui conviene distinguere la descrizione, che dice che cosa fa la rete, dalla sintesi, che dice con quali porte è fatta. La descrizione si scrive con l'operatore condizionale, una riga per combinazione dei comandi; la sintesi riporta le espressioni trovate sopra.
Descrizione
Sintesi
Un dettaglio di stile: le variabili di comando si raccolgono in un unico ingresso a più bit con un nome parlante (b1_b0), così i confronti si scrivono b1_b0=='B10 invece di combinare i bit a mano; e si scrive la base delle costanti ('B10, non 10, che in Verilog sarebbe dieci).
A che cosa serve
- Condividere una linea. Con un multiplexer da una parte e un demultiplexer dall'altra, comandati dalle stesse variabili, più comunicazioni si alternano sullo stesso filo: il comando sceglie insieme da quale sorgente prendere e a quale destinazione consegnare.
- Scrivere in una memoria. In una RAM i dati arrivano a tutte le righe di latch, ma solo una deve memorizzarli: il comando di scrittura passa da un demultiplexer comandato dai fili di indirizzo, che lo consegna solo alla riga scelta (lo si vede nel modulo sulle reti sequenziali).
- Abilitare una sorgente su un bus. Le abilitazioni delle porte tri-state, una sola attiva alla volta, sono le uscite di un decoder: un segnale che dice «adesso parla tu» va instradato a una sola rete.
Il multiplexer
Il multiplexer è il duale: 2N ingressi xi, N variabili di comando e una sola uscita, che vale xi quando le variabili di comando codificano i. Si sintetizza con un decoder sulle variabili di comando, una AND tra ogni uscita del decoder e l'ingresso corrispondente (tutte valgono 0 tranne una, che vale come xi) e una OR finale. Fondendo le AND del decoder con quelle dopo, resta una rete a due livelli di logica:
z = x0b1b0 + x1b1b0 + x2b1b0 + x3b1b0
Una rete a due livelli di logica (AND e OR; gli invertitori sugli ingressi non si contano): l'uscita insegue l'ingresso xi con i = (b1 b0)2.
Il multiplexer come rete universale
Un multiplexer con N variabili di comando può realizzare qualsiasi rete combinatoria a N ingressi e un'uscita: basta collegare gli ingressi della rete alle variabili di comando e attaccare all'ingresso xj la costante della riga j della tabella di verità (1 = alimentazione, 0 = massa). Anzi, ne basta uno con N − 1 variabili di comando: si prendono le righe a coppie, e per ogni coppia l'uscita vale 0, 1, x0 oppure x0.
Conseguenza fondamentale. Il multiplexer si fa con AND, OR e NOT su due livelli, realizza qualsiasi rete a un'uscita, e le reti a più uscite sono reti a un'uscita in parallelo. Quindi ogni rete combinatoria si può costruire con AND, OR e NOT in al più due livelli di logica. Questo pone un limite superiore al ritardo di qualsiasi rete combinatoria.
Esercizio svolto: un multiplexer a N − 1 variabili di comando
Esercizio 8 Un multiplexer con una variabile di comando in meno
È data la tabella di verità di una rete combinatoria a tre ingressi (le prime quattro colonne qui sotto). Realizzarla con un multiplexer a 2 variabili di comando, collegandone opportunamente gli ingressi e aggiungendo al più una porta NOT. Poi discutere la generalità del risultato: vale per tutte le tabelle di verità? Vale per qualunque numero di ingressi, cioè con N ingressi e un multiplexer a N − 1 variabili di comando?
| x2 | x1 | x0 | z | z in funzione di x0 | ingresso |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | x0 | h0 |
| 0 | 0 | 1 | 1 | ||
| 0 | 1 | 0 | 0 | 0 | h1 |
| 0 | 1 | 1 | 0 | ||
| 1 | 0 | 0 | 1 | 1 | h2 |
| 1 | 0 | 1 | 1 | ||
| 1 | 1 | 0 | 1 | x0 | h3 |
| 1 | 1 | 1 | 0 |
L'idea. Gli ingressi della rete sono tre e le variabili di comando due: due ingressi vanno sui comandi, il terzo deve arrivare agli ingressi del multiplexer. Colleghiamo i due più significativi, b1 = x2 e b0 = x1. Così l'ingresso hj viene scelto in due righe della tabella, quelle con (x2 x1)2 = j, che differiscono solo per x0. In ognuna di queste coppie l'uscita dipende solo da x0: le ultime due colonne della tabella dicono come.
Con l'algebra. L'uscita del multiplexer, con quei collegamenti, è
z = h0x2x1 + h1x2x1 + h2x2x1 + h3x2x1
La forma canonica SP della tabella si riordina raccogliendo i mintermini a coppie, secondo il valore di x2 x1:
Confrontando termine a termine con l'espressione del multiplexer: h0 = x0, h1 = 0, h2 = 1, h3 = x0. Lo 0 è la massa, l'1 l'alimentazione, e per x0 serve l'unica NOT.
La tabella che il circuito produce coincide con quella del testo. Il nome dell'ingresso scelto si colora di rosso.
Generalità del risultato.
- Vale per tutte le tabelle. In ogni coppia di righe x2 e x1 sono fissati, e l'uscita è una funzione della sola x0. Ma le funzioni di una variabile sono 221 = 4: se la coppia di valori di z è 00 serve la costante 0, se è 01 serve x0, se è 10 serve x0, se è 11 la costante 1. Non esiste un quinto caso.
- Vale per qualunque N. Con N ingressi si collegano xN−1 … x1 alle N − 1 variabili di comando: l'ingresso hj corrisponde alle righe 2j e 2j + 1, che differiscono solo per x0, e il ragionamento è identico. E basta sempre una NOT: x0 è un solo segnale, che si porta a tutti gli ingressi che ne hanno bisogno.
- La variabile «esclusa» si può scegliere. Niente obbliga a lasciare fuori x0: con x1 e x0 sui comandi, per esempio, le coppie sono le righe che differiscono per x2. Cambiano i collegamenti, non il ragionamento.
In formula, è l'espansione di Shannon fatta rispetto a tutte le variabili tranne una: f(x2, x1, x0) = x2x1 · f(0, 0, x0) + x2x1 · f(0, 1, x0) + x2x1 · f(1, 0, x0) + x2x1 · f(1, 1, x0). E se si togliesse un'altra variabile di comando? Ogni ingresso dovrebbe realizzare una funzione di due variabili: i casi diventano 24 = 16 (fra cui AND, OR e XOR), e una NOT non basta più.
Esercizio. Con un multiplexer a 2 variabili di comando, realizzare la funzione maggioranza di tre variabili, che vale 1 quando almeno due ingressi su tre valgono 1. Serve la NOT?
Soluzione
Con b1 = x2 e b0 = x1: per x2 x1 = 00 l'uscita vale 0 in tutte e due le righe (h0 = 0); per 01 e per 10 vale 1 solo se x0 = 1 (h1 = h2 = x0); per 11 vale sempre 1 (h3 = 1). La NOT non serve, perché nessuna coppia ha la forma «1, 0». In formula: z = x2x1 · 0 + x2x1 · x0 + x2x1 · x0 + x2x1 · 1, che semplificata dà z = x2x1 + x2x0 + x1x0.
Modello strutturale universale e forma SP
Un decoder seguito da una barriera di OR
C'è un modo meccanico per sintetizzare qualsiasi tabella di verità: un decoder N to 2N riconosce ogni stato di ingresso, e una porta OR per ciascuna uscita raccoglie le uscite del decoder degli stati in cui quell'uscita deve valere 1. Per la tabella vista sopra, chiamate v0 … v7 le uscite del decoder: z1 = v2 + v3 + v4 + v5 e z0 = v1 + v4 + v5.
Funziona sempre, ma costa: 8 AND a tre ingressi e due OR. Le AND degli stati che nessuna uscita riconosce (v0, v6, v7) si possono togliere subito, e restano 5 AND e 2 OR. Per scendere ancora serve l'algebra: si sostituisce a ogni vj il suo mintermine e si fondono i termini a coppie.
Il passaggio con l'idempotenza è quello che non viene spontaneo: v5 è adiacente sia a v1 (differisce per x2) sia a v4 (differisce per x0), e per fonderlo con tutti e due lo si scrive due volte. Disegnando le due reti come griglie (in alto gli ingressi diretti e negati, al centro le AND, in basso le OR; ogni punto è un collegamento) il guadagno si vede a colpo d'occhio:
Restano tre AND a due ingressi e due OR a due ingressi: da 7 porte e 22 diodi a 5 porte e 10 diodi. Si potrebbe fare ancora meglio uscendo dalla forma «somma di prodotti»: z1 = x2 ⊕ x1, una sola XOR.
Espansione di Shannon e forma canonica SP
Il punto di partenza teorico è un risultato di Shannon: ogni legge combinatoria si può scrivere come somma di prodotti degli ingressi, diretti o negati. L'espansione di Shannon scrive z come somma di 2N termini, uno per riga della tabella: il valore f di quella riga moltiplicato per il prodotto di tutti gli ingressi presi diretti (se valgono 1 in quella riga) o negati (se valgono 0). Le righe in cui f = 0 spariscono (0 · α = 0), e nelle altre il fattore 1 si toglie. Resta la forma canonica SP:
- SP perché è una somma di prodotti;
- canonica perché ogni prodotto contiene tutti gli ingressi;
- ciascun prodotto si chiama mintermine e riconosce esattamente uno stato di ingresso.
In formula, l'espansione rispetto a una sola variabile si scrive
f(xN−1, …, x1, x0) = x0 · f(xN−1, …, x1, 0) + x0 · f(xN−1, …, x1, 1)
e si dimostra sostituendo i due valori possibili: con x0 = 0 il secondo termine si annulla e il primo vale 1 · f(…, 0), cioè proprio f; con x0 = 1 succede il contrario. Per esempio, espandendo x ⊕ y rispetto a x si trova x · (0 ⊕ y) + x · (1 ⊕ y) = xy + xy. Ripetendo l'espansione su tutte le variabili, una dopo l'altra, si ottiene la somma di 2N termini da cui nasce la forma canonica. Un multiplexer 2 to 1, z = b · h0 + b · h1, è l'espansione di Shannon fatta circuito: è per questo che il multiplexer è una rete universale.
Esercizio svolto: una rete programmabile con AND e XOR
Esercizio 9 Programmare una rete con i comandi
La rete in figura ha due ingressi x, y, un'uscita z e quattro variabili di comando a, b, c, d: a seconda dei comandi realizza una legge f(x, y) diversa.
- Scrivere l'espressione che lega z agli ingressi e ai comandi.
- Calcolare a, b, c, d in modo da realizzare una generica f(x, y) nota, cioè conoscendo f(0,0), f(1,0), f(0,1) e f(1,1).
- Calcolare i comandi nei casi particolari f(x, y) = xy e f(x, y) = xy.
La XOR a quattro ingressi vale 1 quando un numero dispari dei suoi ingressi vale 1.
a) Le tre AND calcolano xb, yc e xyd, e la XOR le combina con a:
z = a ⊕ xb ⊕ yc ⊕ xyd
b) Si sostituiscono i quattro stati di ingresso, usando α · 1 = α, α · 0 = 0 e α ⊕ 0 = α:
È un sistema di quattro equazioni, e si risolve dall'alto verso il basso con le regole d'oro dello XOR: per isolare un'incognita si fa ⊕ con lo stesso termine da tutte e due le parti, e α ⊕ α = 0 lo cancella.
c) Ora basta mettere i numeri nelle formule.
f = xy (NAND)
f(0,0) = 1, f(1,0) = 1, f(0,1) = 1, f(1,1) = 0, quindi a = 1, b = 1 ⊕ 1 = 0, c = 0, d = 1 ⊕ 1 ⊕ 1 ⊕ 0 = 1.
Verifica: z = 1 ⊕ xy = xy, perché α ⊕ 1 = α.
f = xy
f(0,0) = 0, f(1,0) = 1, f(0,1) = 0, f(1,1) = 0, quindi a = 0, b = 1, c = 0, d = 1.
Verifica: z = x ⊕ xy = x(1 ⊕ y) = xy, con la distributiva del prodotto sullo XOR.
Provale sul circuito: imposta i comandi e fai scorrere x e y sulle quattro combinazioni.
Osservazione. I comandi sono 4 bit, quindi 16 combinazioni; anche le reti a due ingressi sono 222 = 16; e le formule del punto b) danno sempre una e una sola soluzione. Quindi la corrispondenza è biunivoca: questa rete realizza tutte le reti combinatorie a due ingressi, ciascuna in un modo solo. È un'altra rete universale, come il multiplexer con le costanti sugli ingressi. Eccole tutte, con i loro comandi:
| f(0,0) | f(1,0) | f(0,1) | f(1,1) | legge | a | b | c | d | z |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | la costante 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | AND: xy | 0 | 0 | 0 | 1 | xy |
| 0 | 0 | 1 | 0 | xy | 0 | 0 | 1 | 1 | y ⊕ xy |
| 0 | 0 | 1 | 1 | y | 0 | 0 | 1 | 0 | y |
| 0 | 1 | 0 | 0 | xy | 0 | 1 | 0 | 1 | x ⊕ xy |
| 0 | 1 | 0 | 1 | x | 0 | 1 | 0 | 0 | x |
| 0 | 1 | 1 | 0 | XOR: x ⊕ y | 0 | 1 | 1 | 0 | x ⊕ y |
| 0 | 1 | 1 | 1 | OR: x + y | 0 | 1 | 1 | 1 | x ⊕ y ⊕ xy |
| 1 | 0 | 0 | 0 | NOR: x + y | 1 | 1 | 1 | 1 | 1 ⊕ x ⊕ y ⊕ xy |
| 1 | 0 | 0 | 1 | XNOR: x ⊕ y | 1 | 1 | 1 | 0 | 1 ⊕ x ⊕ y |
| 1 | 0 | 1 | 0 | x | 1 | 1 | 0 | 0 | 1 ⊕ x |
| 1 | 0 | 1 | 1 | x + y | 1 | 1 | 0 | 1 | 1 ⊕ x ⊕ xy |
| 1 | 1 | 0 | 0 | y | 1 | 0 | 1 | 0 | 1 ⊕ y |
| 1 | 1 | 0 | 1 | x + y | 1 | 0 | 1 | 1 | 1 ⊕ y ⊕ xy |
| 1 | 1 | 1 | 0 | NAND: xy | 1 | 0 | 0 | 1 | 1 ⊕ xy |
| 1 | 1 | 1 | 1 | la costante 1 | 1 | 0 | 0 | 0 | 1 |
Sintesi SP a costo minimo
Che cosa vuol dire costo
Cercheremo, tra le reti a due livelli di logica in forma SP, quella di costo minimo. Non è detto che sia la rete più economica in assoluto (forme diverse o reti a più livelli possono costare meno), ma trovare l'ottimo assoluto è troppo difficile, e le reti a due livelli hanno il vantaggio di essere le più veloci. Due criteri di costo:
Costo a porte
Ogni porta conta 1. Con Ns prodotti: CP = Ns + 1 (le AND più la OR finale).
Costo a diodi
Ogni ingresso di porta conta 1: CD = Ns + Σ letterali dei prodotti (gli ingressi della OR più quelli delle AND).
Gli invertitori sugli ingressi non si contano. Il metodo vale per reti a un'uscita; per quelle a più uscite si applica uscita per uscita, sapendo che così non si trova necessariamente l'ottimo globale (due uscite potrebbero condividere un prodotto).
Implicanti e implicanti principali
Partendo dalla forma canonica si applicano a oltranza due regole: la fusione, αx + αx = α (due termini che differiscono per una sola variabile, diretta in uno e negata nell'altro, ne generano uno senza quella variabile), e l'idempotenza α + α = α (niente duplicati). I termini prodotti per fusione sono implicanti: prodotti di alcune variabili che valgono 1 solo in stati riconosciuti dalla rete. Un implicante che non si fonde con nessun altro è principale.
Un insieme di implicanti la cui somma è una forma SP della funzione: copre tutti gli stati riconosciuti.
Togliendo un qualsiasi implicante non è più una lista di copertura. La lista dei mintermini lo è; quella degli implicanti principali spesso no.
Togliere un implicante significa togliere una AND e un ingresso della OR: la sintesi minima si cerca tra le liste non ridondanti di implicanti principali.
Esercizio svolto: le due regole, a mano
Nelle slide la prima regola è scritta in una forma un po' diversa:
αx + αx = αx + αx + α α + α = α
Non è un dettaglio: il termine fuso α si aggiunge e i due di partenza restano, perché potrebbero fondersi anche con altri. È lecito perché αx + αx + α = α + α = α = αx + αx. Alla fine i termini che si sono fusi spariscono da soli per assorbimento (α + αx = α): nel metodo di Quine-McCluskey è il segno ✓. La seconda regola, invece, evita di portarsi dietro dei doppioni.
Esercizio 10 Applicare le regole esaustivamente
Applicare esaustivamente le due regole alla funzione f(x2, x1, x0) che riconosce gli stati 1, 3, 5, 6 e 7, e scriverne la forma SP semplificata. Chiamiamo mj il mintermine dello stato j. La forma canonica è
f = x2x1x0 + x2x1x0 + x2x1x0 + x2x1x0 + x2x1x0
Primo giro: coppie di mintermini. Si confronta ogni mintermine con tutti gli altri, e ogni coppia che differisce per una sola variabile genera un termine nuovo, che si aggiunge alla lista:
| coppia | stati | differiscono per | termine fuso |
|---|---|---|---|
| m1 + m3 | 001, 011 | x1 | x2x0 (0-1) |
| m1 + m5 | 001, 101 | x2 | x1x0 (-01) |
| m3 + m7 | 011, 111 | x2 | x1x0 (-11) |
| m5 + m7 | 101, 111 | x1 | x2x0 (1-1) |
| m6 + m7 | 110, 111 | x0 | x2x1 (11-) |
Tutti i mintermini si sono fusi almeno una volta, e il 7 addirittura tre volte: è la prima regola, che lascia i termini a disposizione, a permetterlo.
Secondo giro: i termini appena trovati. Si confrontano solo termini con le stesse variabili che differiscono per una sola di esse:
x2x1 non si fonde con nessuno: servirebbe x2x1 oppure x2x1, che non ci sono. Al terzo giro x0 è rimasto solo, e ci si ferma. I termini che non si sono mai fusi, x0 e x2x1, sono gli implicanti principali; tutti gli altri spariscono per assorbimento (per esempio x0 + x2x0 = x0). Risultato:
f = x0 + x2x1
La strada «furba». Con l'occhio allenato si arriva allo stesso risultato in tre righe, riusando il mintermine 7 grazie all'idempotenza:
Funziona, ma bisogna «vedere» le coppie giuste, e con più variabili è facile perdersene una. Il procedimento esaustivo non sbaglia mai: ecco perché si insiste sulla parola esaustivamente. Le mappe di Karnaugh, che vedremo tra poco, rendono le coppie visibili a colpo d'occhio: qui x0 è il quadrato delle due colonne centrali e x2x1 le due caselle a destra nella riga in basso.
Il costo scende da cinque AND a tre ingressi e una OR a cinque (6 porte e 20 diodi) a 3 porte e 5 diodi secondo la formula del corso, che conta anche l'implicante x0 come una AND a un ingresso. In realtà quel filo entra direttamente nella OR: bastano una AND e una OR, 2 porte e 4 diodi.
Il metodo di Quine-McCluskey
È il modo ordinato di trovare gli implicanti principali, adatto anche a un programma. Esempio: una rete a 4 ingressi che riconosce gli stati 1, 2, 3, 6, 7, 8, 9, 10.
- Si scrivono gli stati riconosciuti in binario e si raggruppano per numero di 1.
- Si confrontano solo gruppi adiacenti (con un 1 di differenza): due termini che differiscono in una sola posizione si fondono, e quella posizione diventa «–». Si marcano i termini che si sono fusi.
- Si ripete sulla nuova lista, finché ci sono fusioni, senza duplicati.
- I termini mai marcati sono gli implicanti principali.
| n. di 1 | mintermini | prima fusione | seconda fusione |
|---|---|---|---|
| 1 | 0001 ✓ · 0010 ✓ · 1000 ✓ | 00-1 · -001 · 001- ✓ · 0-10 ✓ · -010 · 100- · 10-0 | 0-1- |
| 2 | 0011 ✓ · 0110 ✓ · 1001 ✓ · 1010 ✓ | 0-11 ✓ · 011- ✓ | |
| 3 | 0111 ✓ |
Gli implicanti principali (in grassetto) sono sei: 0-1-, 00-1, -001, -010, 100-, 10-0. Leggere una coordinata è facile: «1» dà la variabile diretta, «0» negata, «–» assente. Per esempio 0-1- = x3x1 e 10-0 = x3x2x0.
Le mappe di Karnaugh
Una mappa di Karnaugh è una tabella di verità disegnata in modo che stati adiacenti (che differiscono per un bit) siano caselle vicine. Le coordinate seguono il codice Gray, 00, 01, 11, 10, e la mappa va pensata avvolta su sé stessa: il bordo destro tocca il sinistro e quello in alto tocca quello in basso. Le convenzioni del corso: per tre variabili x2 sulle righe e x1x0 sulle colonne; per quattro, x3x2 sulle righe e x1x0 sulle colonne.
Una casella con un 1 è un sottocubo di ordine 1. Due sottocubi adiacenti formano un sottocubo di ordine 2, due di ordine 2 adiacenti uno di ordine 4, e così via: i sottocubi sono rettangoli di 1, 2, 4, 8 caselle (anche «a cavallo» dei bordi). Il bello è che c'è una corrispondenza biunivoca: ogni sottocubo principale è un implicante principale, e un sottocubo di ordine p corrisponde a un prodotto di N − log2p variabili. Un sottocubo è principale se nessun sottocubo più grande lo contiene.
- Si segnano tutti i sottocubi del massimo ordine presenti: sono certamente principali.
- Se coprono tutti gli 1, ci si ferma. Altrimenti si passa all'ordine inferiore e si segnano tutti i sottocubi di quell'ordine non già contenuti in quelli segnati.
- Si ripete fino a coprire tutti gli 1. Errore tipico: fermarsi a metà di un passo, appena gli 1 sono coperti. Un passo iniziato va finito.
Ecco la mappa dell'esempio di prima. Lo strumento trova i sottocubi principali, li classifica e calcola la sintesi di costo minimo; clicca sulle caselle per cambiare la funzione.
Essenziali, eliminabili e liste di copertura
La lista degli implicanti principali può essere ridondante. Per ridurla si classificano i sottocubi principali. È una tipica domanda d'esame:
| Termine | Definizione |
|---|---|
| forma canonica SP | la somma di mintermini ottenuta dall'espansione di Shannon |
| mintermine | prodotto di tutte le variabili, dirette o negate; riconosce un solo stato di ingresso |
| implicante | prodotto di alcune variabili che compare in una forma SP della legge; riconosce alcuni stati |
| implicante principale | implicante che non si fonde con nessun altro (sopravvive alla regola αx + α = α) |
| essenziale | è l'unico implicante principale a coprire un certo stato riconosciuto: deve stare in ogni lista di copertura. Sulla mappa: copre un 1 cerchiato una volta sola |
| assolutamente eliminabile | riconosce solo stati già riconosciuti da implicanti essenziali: non deve stare in nessuna lista non ridondante |
| semplicemente eliminabile | riconosce solo stati riconosciuti anche da altri implicanti principali, almeno uno dei quali non essenziale |
Gli essenziali formano il cuore della mappa. Per i semplicemente eliminabili si procede con un albero binario di scelte: se ne prende uno e si fanno due ipotesi, «lo tengo come se fosse essenziale» (e altri diventano assolutamente eliminabili) oppure «lo scarto» (e altri diventano essenziali). Si continua finché non restano semplicemente eliminabili: le foglie sono tutte le liste di copertura non ridondanti, e tra queste si sceglie quella di costo minimo con il criterio voluto. Con i nomi dello strumento qui sopra (A = 0-1-, B = 00-1, C = -001, D = -010, E = 100-, F = 10-0):
z = x3x1 + x2x1x0 + x3x2x0 (costo a porte 4, a diodi 11)
Il risultato non dipende dall'ordine in cui si scelgono i sottocubi; bisogna solo evitare di aggiungere un sottocubo che renderebbe la lista ridondante. I criteri di costo intervengono soltanto alla fine, nella scelta tra le foglie.
La procedura completa
- Dalla tabella di verità (o da un'espressione) si ricava la mappa di Karnaugh, o la lista dei mintermini.
- Si trovano gli implicanti principali: con la mappa fino a 4 variabili, con Quine-McCluskey oltre.
- Si individuano gli essenziali e poi gli assolutamente eliminabili.
- Con l'albero delle scelte sui semplicemente eliminabili si generano tutte le liste di copertura non ridondanti.
- Si applica il criterio di costo e si scrive l'espressione: all'esame servono le espressioni algebriche, non i disegni.
Funzioni non completamente specificate
Un decodificatore BCD a 7 segmenti riceve una cifra decimale codificata in binario su 4 bit (BCD, Binary Coded Decimal) e accende i segmenti di un display. Gli stati da 1010 a 1111 non sono cifre e non si presenteranno mai: per quegli stati le uscite sono non specificate.
Nella sintesi i non specificati si usano a nostro vantaggio, in due modi diversi:
- per trovare i sottocubi principali si trattano come 1, così i sottocubi diventano più grandi (meno letterali);
- per classificarli e scegliere la copertura si trattano come 0: bisogna coprire solo gli 1 veri.
Per il segmento E, che si accende per le cifre 0, 2, 6 e 8, si trovano cinque sottocubi di ordine 4: due sono essenziali e gli altri tre coprono solo stati già coperti, o solo non specificati. Risultato: zE = x2x0 + x1x0.
Reti con più uscite
Sintetizzando a costo minimo una uscita alla volta non si ottiene necessariamente la rete a più uscite di costo minimo. Esempio: con z1 = ac + bc e z0 = bc + ab (le singole sintesi minime) servono 6 porte; ma scrivendo z1 = ac + abc e z0 = bc + abc, cioè usando in entrambe il mintermine comune abc, bastano 5 porte, perché quel prodotto si realizza una volta sola. In una rete a più uscite possono quindi convenire implicanti che non sono principali per nessuna delle singole uscite.
Sintesi PS
Prodotti di somme
Ogni legge si può scrivere anche in forma PS, come prodotto di somme: z = S1 · S2 · … · Sk, dove ogni Si è una somma di variabili dirette o negate, detta implicato. La teoria è duale a quella SP (forma canonica PS, maxtermini che corrispondono agli stati non riconosciuti, implicati principali…), ma in pratica si procede così:
- si scrive la mappa di F, cioè quella con 0 e 1 scambiati (i non specificati restano tali);
- si fa la sintesi SP a costo minimo di F, cioè si coprono gli 0 di F;
- si nega tutto e si applica De Morgan due volte: la somma finale negata diventa il prodotto delle negazioni, e ogni prodotto negato diventa la somma degli ingressi negati.
La sintesi PS così ottenuta ha lo stesso costo della SP di F (sia a porte sia a diodi) ed è di costo minimo tra le PS: se ne esistesse una più economica, esisterebbe anche una SP di F più economica, contro l'ipotesi. Per la nostra funzione di esempio gli implicati principali sono quattro, tutti essenziali:
z = (x2 + x1) · (x3 + x2) · (x3 + x1 + x0) · (x3 + x1 + x0)
Costa 14 a diodi contro gli 11 della SP. Non c'è una regola generale su quale delle due forme costi meno: dipende dalla funzione, e conviene provarle entrambe. Nello strumento della mappa di Karnaugh, il pulsante «Sintesi PS» fa proprio questo.
Porte universali: sintesi a NAND e a NOR
NAND e NOR bastano da sole
Con sole porte NAND (oppure con sole NOR) si costruiscono NOT, AND e OR, e quindi qualsiasi rete: per questo si chiamano porte universali. Con le NAND: un NOT è una NAND con gli ingressi collegati insieme; una AND è una NAND seguita da un NOT-NAND; una OR è una NAND con gli ingressi negati (De Morgan). Con le NOR è tutto duale.
Dalla forma SP alle NAND, dalla PS alle NOR
SP → NAND
Si nega due volte l'espressione SP e si applica De Morgan una volta:
z = P1 + P2 + … = P1 · P2 · …
Ogni AND diventa una NAND, la OR finale una NAND. Stesso circuito, stesso costo.
PS → NOR
Allo stesso modo, partendo dalla forma PS:
z = S1 · S2 · … = S1 + S2 + …
Ogni OR diventa una NOR, la AND finale una NOR. Stesso costo della PS.
Un esercizio d'esame
Sintetizzare a costo minimo la rete della mappa qui sotto sia a NAND sia a NOR, e dire quale delle due costa meno a diodi. Ricetta: SP minima e poi NAND; PS minima (cioè SP minima della mappa con 0 e 1 scambiati) e poi NOR. Prova a farlo da solo, poi controlla con lo strumento (passando da SP a PS).
Soluzione: la SP minima è z = x3x1 + x2x0 + x2x1 (costo a diodi 9), da cui a NAND z = x3x1 · x2x0 · x2x1. La PS minima è z = (x3 + x2) · (x2 + x1) · (x3 + x1 + x0) (costo 10), da cui a NOR. Vince la versione a NAND.
Esercizi svolti di sintesi
Dalla tabella di verità alla sintesi minima
Un esercizio completo nello stile della prova scritta: tutti i passi della procedura, uno dopo l'altro.
Esercizio 11 La procedura completa, come all'esame
Data la tabella di verità di una rete a 4 ingressi e 1 uscita:
- scrivere la forma canonica SP;
- trovare gli implicanti principali con il metodo di Quine-McCluskey;
- disegnare la mappa di Karnaugh e individuarvi gli implicanti principali, classificandoli;
- trovare tutte le liste di copertura non ridondanti e scegliere quella (o quelle) di costo minimo, sia a porte sia a diodi.
| x3 x2 x1 x0 | z0 | x3 x2 x1 x0 | z0 |
|---|---|---|---|
| 0 0 0 0 | 0 | 1 0 0 0 | 1 |
| 0 0 0 1 | 1 | 1 0 0 1 | 1 |
| 0 0 1 0 | 0 | 1 0 1 0 | 0 |
| 0 0 1 1 | 1 | 1 0 1 1 | 0 |
| 0 1 0 0 | 0 | 1 1 0 0 | 1 |
| 0 1 0 1 | 0 | 1 1 0 1 | 1 |
| 0 1 1 0 | 0 | 1 1 1 0 | 0 |
| 0 1 1 1 | 1 | 1 1 1 1 | 1 |
1. Forma canonica. Un mintermine per ciascuno degli stati riconosciuti, 1, 3, 7, 8, 9, 12, 13 e 15: ogni variabile compare diretta se nello stato vale 1, negata se vale 0.
z0 = x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0 + x3x2x1x0
2. Quine-McCluskey. Si raggruppano gli stati per numero di 1 e si confrontano solo gruppi vicini. Al primo giro si trovano nove termini; al secondo si fondono solo 100- con 110- (e 1-00 con 1-01, che dà lo stesso termine). Al terzo non c'è più niente da fondere.
| n. di 1 | mintermini | prima fusione | seconda fusione |
|---|---|---|---|
| 1 | 0001 ✓ · 1000 ✓ | 00-1 · -001 · 100- ✓ · 1-00 ✓ | 1-0- |
| 2 | 0011 ✓ · 1001 ✓ · 1100 ✓ | 0-11 · 1-01 ✓ · 110- ✓ | |
| 3 | 0111 ✓ · 1101 ✓ | -111 · 11-1 | |
| 4 | 1111 ✓ |
Gli implicanti principali, in grassetto, sono sei. Con i nomi che usa lo strumento qui sotto: A = 1-0- = x3x1, B = 00-1 = x3x2x0, C = -001 = x2x1x0, D = 0-11 = x3x1x0, E = -111 = x2x1x0, F = 11-1 = x3x2x0.
3. Mappa e classificazione. Prova a disegnare i sottocubi da solo, poi premi il pulsante per vedere la soluzione:
- A è essenziale: è l'unico a coprire gli stati 1000 e 1100. Copre anche 1001 e 1101.
- Tutti gli altri sono semplicemente eliminabili: ognuno copre stati coperti anche da un altro implicante principale non essenziale. Dopo aver preso A restano da coprire quattro stati, ciascuno in due modi: 0001 (B o C), 0011 (B o D), 0111 (D o E), 1111 (E o F).
4. Liste di copertura. Si costruisce l'albero delle scelte partendo da B. Se B si tiene, C diventa assolutamente eliminabile (0001 è già coperto da B, 1001 da A); poi si decide su E: tenendolo, D e F diventano inutili; scartandolo, D e F diventano essenziali. Se B si scarta, C e D diventano essenziali (sono rimasti gli unici per 0001 e per 0011), e resta da coprire 1111 con E oppure con F.
Le liste non ridondanti sono quattro, e una sola è di costo minimo con entrambi i criteri:
z0 = x3x1 + x3x2x0 + x2x1x0
Costa 4 porte e 11 diodi. Per completezza, la sintesi PS di costo minimo (pulsante «Sintesi PS») ha quattro implicati, tutti essenziali, e costa 5 porte e 14 diodi: qui conviene la SP.
Oltre la forma SP: somme esclusive di prodotti
La sintesi SP a costo minimo è minima solo tra le reti AND-OR a due livelli. Se si ammettono anche le porte XOR, a volte si scende parecchio.
Esercizio 12 Quando conviene lo XOR: la sintesi ESOP
Dimostrare che, data una legge F, una rete a due livelli costruita così ne è una sintesi:
- ogni stato riconosciuto da F è coperto da un numero dispari di prodotti;
- ogni stato non riconosciuto è coperto da un numero pari di prodotti (anche zero);
- le uscite di tutti i prodotti vanno in ingresso a una XOR.
È la sintesi ESOP (Exclusive Sum Of Products). Poi trovare una sintesi ESOP più economica della SP minima per la funzione che vale 1 quando x1 e x0 sono diversi, e per z = x3x2 ⊕ x1x0.
Dimostrazione. Fissato uno stato di ingresso, ogni prodotto vale 1 se copre quello stato e 0 altrimenti. All'ingresso della XOR arrivano quindi tanti 1 quanti sono i prodotti che coprono lo stato, e la XOR di più bit vale 1 se e solo se gli 1 sono in numero dispari (è la parità). L'uscita vale 1 esattamente negli stati coperti un numero dispari di volte, cioè in quelli riconosciuti da F. ∎
Ecco la differenza con la forma SP: lì un 1 si può coprire quante volte si vuole e uno 0 mai; qui una casella coperta due volte vale 0. Si possono quindi usare sottocubi grandi che coprono anche degli 0, purché li coprano un numero pari di volte.
Primo esempio. La funzione che vale 1 quando x1 ≠ x0 ha come SP minima x1x0 + x1x0 (3 porte, 6 diodi). In ESOP bastano i due «sottocubi» x1 e x0, di metà mappa ciascuno: si sovrappongono proprio nelle caselle con x1 = x0 = 1, che devono valere 0. Risultato: x1 ⊕ x0, una sola porta XOR.
Secondo esempio. Per z = x3x2 ⊕ x1x0 la SP minima ha quattro implicanti di tre letterali, x3x2x1 + x3x2x0 + x3x1x0 + x2x1x0. La ESOP usa una riga e una colonna intere della mappa, che si incrociano nell'unica casella da spegnere:
Porte tri-state e bus
Collegare più uscite alla stessa linea
Spesso fa comodo che più reti scrivano, a turno, sulla stessa linea: un bus condiviso, o le linee dati di una memoria, che sono a volte ingressi e a volte uscite. Ma collegare due uscite normali è un disastro: elettricamente un'uscita è un generatore di tensione con una resistenza in serie, e se una vale 1 e l'altra 0 si chiude una maglia in cui scorre molta corrente (e i circuiti bruciano), mentre la tensione sulla linea finisce chissà dove, magari nella fascia di indeterminazione.
La soluzione è la porta tri-state: con l'abilitazione b = 1 si comporta da elemento neutro, con b = 0 la sua uscita è come scollegata (in alta impedenza): qualunque tensione le si applichi, non scorre corrente. Se N uscite condividono una linea, ognuna passa da una tri-state e in ogni istante almeno N − 1 di esse sono in alta impedenza.
Due osservazioni. Primo: l'alta impedenza non è un valore logico e non si propaga: una porta che riceve in ingresso una linea «scollegata» produce comunque 0 o 1, solo che non sappiamo quale. Secondo: con le tri-state si costruisce un multiplexer decodificato (una tri-state per ingresso, con le abilitazioni prodotte da un decoder) e le linee bidirezionali, che una rete usa a volte come ingresso e a volte come uscita.
Circuiti di ritardo e formatori di impulsi
Ritardi asimmetrici e impulsi
Un elemento di ritardo Δ si fa con un numero pari di NOT in cascata, dimensionato sul ritardo voluto; il suo ritardo è simmetrico. Con una porta in più si ottengono ritardi asimmetrici: con una AND tra x e la sua copia ritardata y, l'uscita sale solo quando sale anche y (ritardo grande) ma scende appena scende x (ritardo piccolo): è il circuito Δ⁺. Con una OR si ottiene il duale Δ⁻. Negando l'ingresso ritardato si ottengono i formatori di impulsi: P⁺ genera un impulso di durata Δ dopo ogni fronte di salita, P⁻ (con una NOR) dopo ogni fronte di discesa.