Mappe di Karnaugh e condizioni dei don’t-care

Collegare la tabella di verità al costo del circuito

La tabella di verità^{iTabella di verità Elenco completo delle combinazioni d’ingresso e delle rispettive uscite. Le variazioni temporali si esaminano separatamente nelle forme d’onda. Approfondisci} definisce la funzione; la minimizzazione logica decide con quale formula realizzarla. Con tre ingressi, l’indice del mintermine è rappresentato in binario da ABC, con A come bit più significativo.

Il mintermine 4 è per esempio ABC=100. Le righe non elencate, 0, 2 e 6, producono 0. Invece di usare sempre cinque prodotti, possiamo raggruppare termini che differiscono per un solo bit.

Una mappa di Karnaugh è una tabella riordinata

Disponiamo le colonne come BC=00, 01, 11, 10. È l'ordine Gray: fra colonne adiacenti cambia un solo bit. Anche la prima e l'ultima colonna sono adiacenti.

I gruppi devono essere rettangolari e contenere $1,2,4,8,\ldots$ celle. Includere una cella a 0 cambia la funzione. È consentito includere lo stesso 1 in più gruppi.

1. Raggruppando le quattro celle delle colonne C=1, l'uscita resta 1 mentre A e B variano. Resta il termine C.
2. Nella riga A=1, fra BC=00 e 01 varia solo C. Resta $A\overline B$.
3. L'OR dei due gruppi copre tutti gli 1 senza includere alcuno 0.

Confrontate definizione iniziale e formula minimizzata per tutti gli otto ingressi. Verificate separatamente che la formula sia più breve e che la funzione sia la stessa.

Il flusso seguente traduce in formula i due gruppi della mappa. Nel gruppo C variano A e B, nel gruppo di due celle varia C: quelle variabili vengono eliminate.

Don't-care: libertà di ottimizzazione e ipotesi sugli ingressi

Supponiamo che il contratto di sistema escluda ABC=000. Ponendo quella cella a X, possiamo usarla come 0 o 1 secondo necessità. Raggruppare le quattro celle con B=0 fornisce una formula più semplice:

La nuova formula vale 1 per ABC=000: differisce dalla tabella completa originaria. Per affermare l'equivalenza occorre quindi includere la condizione ABC≠000. Se 000 può comparire durante inizializzazione o recupero da errore, l'ottimizzazione può violare i requisiti di sistema.

Minimizzare la formula non equivale a minimizzare il chip

Meno letterali non garantiscono area, ritardo e consumo ottimali in una specifica libreria di celle standard. Contano carichi, fan-out, porte complesse disponibili, collegamenti e glitch. Qui accertiamo equivalenza funzionale e ipotesi sugli ingressi; i costi fisici si valutano dai risultati di sintesi e timing.

Per approfondire: MIT OpenCourseWare — Combinational Logic

Laboratorio · Sovrapposizioni e condizioni dei don't-care

1. Selezionate il gruppo C. Nelle quattro celle cambiano sia A sia B, quindi resta solo C.
2. Selezionate A·¬B: copre m4 e m5, e m5 si sovrappone al gruppo C. La sovrapposizione è ammessa, includere uno 0 no.
3. Premete m0 due volte: 0 → 1 → X. Con X la specifica è incompleta e include d(0). Il gruppo B=0 si allarga e la formula diventa $C+\overline B$.
4. Premete ancora m0 per tornare a 0. Ripristinato il requisito originale, il gruppo più grande deve scomparire.

Selezionare un gruppo non cambia valori. La formula completa continua a coprire tutti gli 1 e il bordo evidenzia solo il termine esaminato. «Minimo» indica prima il numero di prodotti, poi quello dei letterali; se esistono più soluzioni ne viene mostrata una.