Impara › Argomento 4

Mappe di Karnaugh a 2, 3 e 4 variabili con condizioni X

7 min di lettura · Team bitGateLab

Semplificare con l'algebra di Boole funziona, ma dipende dal fatto che tu "veda" quale legge applicare. La mappa di Karnaugh trasforma questa ricerca in un esercizio visivo: dispone la tabella di verità in una griglia in cui le celle vicine differiscono per una sola variabile, e semplificare diventa racchiudere gruppi di uni. Qui imparerai a costruire mappe a 2, 3 e 4 variabili, a raggruppare correttamente (compresi i bordi che "fanno il giro") e a sfruttare le condizioni di indifferenza.

L'idea: celle vicine, una sola variabile di differenza

La legge di adiacenza dice che AB + AB = A: due termini che differiscono per una sola variabile si fondono e quella variabile scompare. La mappa di Karnaugh dispone i mintermini in modo che qualsiasi coppia di celle con un lato in comune soddisfi questa condizione. Per riuscirci, le intestazioni di righe e colonne non seguono l'ordine binario 00, 01, 10, 11, ma il codice Gray: 00, 01, 11, 10. Tra due valori consecutivi cambia un solo bit, e così anche tra l'ultimo e il primo (10 e 00). Per questo la mappa si comporta come se i suoi bordi opposti fossero incollati.

Mappe a 2 e 3 variabili

La mappa a due variabili ha 4 celle: A sulle righe e B sulle colonne. Quella a tre variabili ha 8 celle: A sulle righe e BC sulle colonne, in ordine Gray. Il numero dentro ogni cella indica il mintermine corrispondente:

Nota che m3 e m2 compaiono in quest'ordine: è l'effetto del codice Gray, e la causa di molti errori quando si compila la mappa a mano.

Regole di raggruppamento

• I gruppi possono contenere soltanto uni (o X, come vedrai più avanti), mai zeri.
• La dimensione di ogni gruppo deve essere una potenza di 2: 1, 2, 4, 8 o 16 celle.
• I gruppi sono rettangoli di celle adiacenti, compresa l'adiacenza attraverso i bordi. Le diagonali non contano.
• Fai ogni gruppo il più grande possibile: un gruppo di 2^k celle elimina k variabili.
• Usa il minor numero di gruppi che copra tutti gli uni. I gruppi possono sovrapporsi.

Per leggere un gruppo, esamina ogni variabile: se mantiene lo stesso valore in tutte le celle del gruppo, compare nel termine (senza barra se vale 1, con la barra se vale 0); se cambia, viene eliminata.

Mappa a 4 variabili e adiacenza ai bordi

Con quattro variabili la mappa ha 16 celle: AB sulle righe e CD sulle colonne, entrambe in ordine Gray.

La colonna di sinistra è vicina a quella di destra, e la riga superiore è vicina a quella inferiore. Di conseguenza, i quattro angoli (m0, m2, m8, m10) formano un gruppo valido di 4 celle: in tutte B = 0 e D = 0, quindi si leggono come BD.

Condizioni di indifferenza (X)

A volte certe combinazioni di ingresso non si verificano mai, oppure la loro uscita non ha conseguenze. Per esempio, in una cifra BCD i codici da 1010 a 1111 non esistono. In quelle righe si scrive una X (detta anche don't care) e la si annota a parte come d(...). Nel raggruppare, ogni X può essere considerata un 1 se ti aiuta a formare un gruppo più grande, oppure ignorata in caso contrario. Non è mai necessario coprire una X.

Errori comuni

• Ordinare le intestazioni in binario (00, 01, 10, 11) invece che in Gray. La mappa non ha più vicini che differiscono per una sola variabile e i gruppi risultano sbagliati.
• Formare gruppi di 3 o 6 celle. Valgono solo le potenze di 2.
• Dimenticare l'adiacenza dei bordi e dei quattro angoli, e ottenere così gruppi più piccoli del necessario.
• Aggiungere un gruppo le cui celle sono già tutte coperte da altri. È superfluo e aggiunge porte.
• Sentirsi obbligati a coprire le X. Si usano solo quando ingrandiscono un gruppo.

Provalo nel simulatore

Il modulo delle mappe di Karnaugh dispone la funzione in ordine Gray, evidenzia i gruppi e scrive l'espressione minima, così puoi confrontare il tuo raggruppamento con quello proposto dallo strumento.

1. Crea una funzione di quattro variabili e inserisci gli uni dell'esempio 2.
2. Raggruppa prima tu sulla carta e scrivi il tuo risultato.
3. Osserva i gruppi evidenziati nella mappa e l'espressione risultante; se è diversa dalla tua, controlla quale gruppo non era massimo.
4. Inserisci l'esempio 3 segnando come X le celle 0, 2 e 5, e osserva come cambia la semplificazione togliendo quelle X.
5. Converti il risultato in circuito e cambia gli ingressi per confermare che coincide con la tabella.

Esercizi

1. Semplifica F(A, B, C) = Σm(0, 2, 4, 6).
   Risposta

   Le colonne BC = 00 e BC = 10 sono vicine attraverso il bordo e sono piene. Nelle quattro celle C = 0: F = C.

2. Semplifica F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).
   Risposta

   Angoli: BD. Blocco centrale m5, m7, m13, m15: BD. F = BD + BD, che è la XNOR di B e D.

3. Semplifica F(A, B, C, D) = Σm(4, 5, 6, 7, 12, 13, 14, 15).
   Risposta

   Le righe AB = 01 e AB = 11 formano un gruppo di 8; solo B resta a 1. F = B.

4. Una cifra BCD (A è il bit più significativo) deve attivare un'uscita quando vale 5 o più. Semplifica F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15).
   Risposta

   Con le X, le righe AB = 11 e AB = 10 formano un gruppo di 8: A. Il blocco m5, m7, m13, m15 dà BD e il blocco m6, m7, m14, m15 dà BC. F = A + BD + BC = A + B(C + D).

Quando ci sono più di quattro o cinque variabili la mappa diventa difficile da leggere; per quei casi esiste un procedimento tabulare, il metodo di Quine-McCluskey.