Circuiti digitali - Metodo K-Map
Nei capitoli precedenti, abbiamo semplificato le funzioni booleane utilizzando postulati e teoremi booleani. È un processo che richiede tempo e dobbiamo riscrivere le espressioni semplificate dopo ogni passaggio.
Per superare questa difficoltà, Karnaughha introdotto un metodo per la semplificazione delle funzioni booleane in modo semplice. Questo metodo è noto come metodo della mappa di Karnaugh o metodo K-map. È un metodo grafico, che consiste di 2 n celle per "n" variabili. Le celle adiacenti differiscono solo per la posizione di un singolo bit.
K-Maps da 2 a 5 variabili
Il metodo K-Map è il più adatto per ridurre al minimo le funzioni booleane di 2 variabili in 5 variabili. Ora parliamo delle K-Maps per 2-5 variabili una per una.
2 K-Map variabile
Il numero di celle in 2 variabili K-map è quattro, poiché il numero di variabili è due. La figura seguente mostra2 variable K-Map.
C'è solo una possibilità di raggruppare 4 termini min adiacenti.
Le possibili combinazioni di raggruppamento di 2 termini min adiacenti sono {(m 0 , m 1 ), (m 2 , m 3 ), (m 0 , m 2 ) e (m 1 , m 3 )}.
3 K-Map variabile
Il numero di celle in 3 variabili K-map è otto, poiché il numero di variabili è tre. La figura seguente mostra3 variable K-Map.
C'è solo una possibilità di raggruppare 8 termini min adiacenti.
Le possibili combinazioni di raggruppamento di 4 termini min adiacenti sono {(m 0 , m 1 , m 3 , m 2 ), (m 4 , m 5 , m 7 , m 6 ), (m 0 , m 1 , m 4 , m 5 ), (m 1 , m 3 , m 5 , m 7 ), (m 3 , m 2 , m 7 , m 6 ) e (m 2 , m 0 , m 6 , m 4 )}.
Le possibili combinazioni di raggruppamento di 2 termini min adiacenti sono {(m 0 , m 1 ), (m 1 , m 3 ), (m 3 , m 2 ), (m 2 , m 0 ), (m 4 , m 5 ) , (m 5 , m 7 ), (m 7 , m 6 ), (m 6 , m 4 ), (m 0 , m 4 ), (m 1 , m 5 ), (m 3 , m 7 ) e ( m 2 , m 6 )}.
Se x = 0, allora 3 variabili K-map diventano 2 variabili K-map.
4 K-Map variabile
Il numero di celle in 4 variabili K-map è sedici, poiché il numero di variabili è quattro. La figura seguente mostra4 variable K-Map.
C'è solo una possibilità di raggruppare 16 termini min adiacenti.
Siano R 1 , R 2 , R 3 e R 4 rispettivamente i termini minimi di prima riga, seconda riga, terza riga e quarta riga. Allo stesso modo, C 1 , C 2 , C 3 e C 4 rappresentano i termini minimi di prima colonna, seconda colonna, terza colonna e quarta colonna rispettivamente. Le possibili combinazioni di raggruppare 8 termini min adiacenti sono {(R 1 , R 2 ), (R 2 , R 3 ), (R 3 , R 4 ), (R 4 , R 1 ), (C 1 , C 2 ) , (C 2 , C 3 ), (C 3 , C 4 ), (C 4 , C 1 )}.
Se w = 0, allora 4 K-map variabili diventano 3 K-map variabili.
5 K-Map variabile
Il numero di celle in 5 variabili K-map è trentadue, poiché il numero di variabili è 5. La figura seguente mostra 5 variable K-Map.
C'è solo una possibilità di raggruppare 32 termini min adiacenti.
Ci sono due possibilità di raggruppare 16 termini min adiacenti. cioè, raggruppamento di termini minimi da m 0 a m 15 e m 16 a m 31 .
Se v = 0, allora 5 variabili K-map diventano 4 variabili K-map.
In tutte le K-map sopra, abbiamo usato esclusivamente la notazione dei termini minimi. Allo stesso modo, puoi utilizzare esclusivamente la notazione dei termini Max.
Minimizzazione delle funzioni booleane utilizzando K-Maps
Se consideriamo la combinazione di input per i quali la funzione booleana è '1', otterremo la funzione booleana, che è in standard sum of products dopo aver semplificato la K-map.
Allo stesso modo, se consideriamo la combinazione di input per i quali la funzione booleana è '0', otterremo la funzione booleana, che è in standard product of sums dopo aver semplificato la K-map.
Segui questi rules for simplifying K-maps per ottenere la somma standard del modulo prodotti.
Selezionare la rispettiva K-map in base al numero di variabili presenti nella funzione booleana.
Se la funzione booleana è data come somma dei termini minimi, posizionare quelli nelle rispettive celle dei termini minimi nella mappa K. Se la funzione booleana è data come forma di somma dei prodotti, posizionare quelli in tutte le celle possibili di K-map per cui sono validi i termini di prodotto dati.
Verificare le possibilità di raggruppare il numero massimo di adiacenti. Dovrebbero essere potenze di due. Inizia dalla potenza massima di due fino alla potenza minima di due. La potenza massima è uguale al numero di variabili considerate in K-map e la potenza minima è zero.
Ogni raggruppamento darà un termine letterale o un prodotto. È noto comeprime implicant. Si dice che il primo implicante siaessential prime implicant, se almeno il singolo '1' non è coperto da altri raggruppamenti ma solo da quel raggruppamento.
Annotare tutti i primi implicanti e i primi implicanti essenziali. La funzione booleana semplificata contiene tutti i primi implicanti essenziali e solo i primi implicanti richiesti.
Note 1 - Se gli output non sono definiti per una combinazione di input, i valori di output verranno rappresentati con don’t care symbol ‘x’. Ciò significa che possiamo considerarli come "0" o "1".
Note 2- Se non sono presenti anche i termini di cura, inserisci la 'x' di non importa nelle rispettive celle di K-map. Considera solo le "x" non importa che sono utili per raggruppare il numero massimo di quelle adiacenti. In questi casi, considera il valore "don't care" come "1".
Esempio
Lasciateci simplify la seguente funzione booleana, f(W, X, Y, Z)= WX’Y’ + WY + W’YZ’ utilizzando K-map.
La funzione booleana data è in forma di somma dei prodotti. Ha 4 variabili W, X, Y e Z. Quindi, abbiamo bisogno4 variable K-map. Il4 variable K-map con quelli corrispondenti ai termini di prodotto dati è mostrato nella figura seguente.
Qui, gli 1 sono inseriti nelle seguenti celle di K-map.
Le celle, che sono comuni all'intersezione della riga 4 e delle colonne 1 e 2, corrispondono al termine del prodotto, WX’Y’.
Le celle, che sono comuni all'intersezione delle righe 3 e 4 e delle colonne 3 e 4, corrispondono al termine prodotto, WY.
Le celle, che sono comuni all'intersezione delle righe 1 e 2 e della colonna 4, corrispondono al termine del prodotto, W’YZ’.
Non ci sono possibilità di raggruppare né 16 adiacenti né 8 adiacenti. Ci sono tre possibilità di raggruppare 4 adiacenti. Dopo questi tre raggruppamenti, non ne rimane nessuno come non raggruppato. Quindi, non è necessario verificare il raggruppamento di 2 adiacenti. Il4 variable K-map con questi tre groupings è mostrato nella figura seguente.
Qui abbiamo tre implicanti primi WX ', WY e YZ'. Tutti questi primi implicanti lo sonoessential per i seguenti motivi.
Due (m8 & m9)del raggruppamento della quarta riga non sono coperti da altri raggruppamenti. Solo il quarto raggruppamento di riga copre questi due.
Uno solo (m15)di raggruppamento di forma quadrata non è coperto da altri raggruppamenti. Solo il raggruppamento di forma quadrata copre quello.
Due (m2 & m6)del raggruppamento della quarta colonna non sono coperti da altri raggruppamenti. Solo il quarto raggruppamento di colonne copre questi due.
quindi, il simplified Boolean function è
f = WX’ + WY + YZ’
Segui questi rules for simplifying K-maps al fine di ottenere il prodotto standard della forma delle somme.
Selezionare la rispettiva K-map in base al numero di variabili presenti nella funzione booleana.
Se la funzione booleana viene fornita come prodotto della forma dei termini Max, posizionare gli zeri nelle rispettive celle dei termini Max nella K-map. Se la funzione booleana è data come prodotto della forma delle somme, posizionare gli zeri in tutte le celle possibili di K-map per le quali sono validi i termini di somma dati.
Verificare le possibilità di raggruppare il numero massimo di zeri adiacenti. Dovrebbero essere potenze di due. Inizia dalla potenza massima di due fino alla potenza minima di due. La potenza massima è uguale al numero di variabili considerate in K-map e la potenza minima è zero.
Ogni raggruppamento darà un termine letterale o una somma. È noto comeprime implicant. Si dice che il primo implicante siaessential prime implicant, se almeno il singolo "0" non è coperto da altri raggruppamenti, ma solo da quel raggruppamento.
Annotare tutti i primi implicanti e i primi implicanti essenziali. La funzione booleana semplificata contiene tutti i primi implicanti essenziali e solo i primi implicanti richiesti.
Note- Se non sono presenti anche termini di cura, inserisci la 'x' di non importa nelle rispettive celle di K-map. Considera solo le "x" non importa che sono utili per raggruppare il numero massimo di zeri adiacenti. In questi casi, considera il valore "don't care" come "0".
Esempio
Lasciateci simplify la seguente funzione booleana, $ f \ left (X, Y, Z \ right) = \ prod M \ left (0,1,2,4 \ right) $ usando K-map.
La funzione booleana data è il prodotto della forma massima dei termini. Ha 3 variabili X, Y e Z. Quindi, abbiamo bisogno di 3 variabili K-map. I termini Max indicati sono M 0 , M 1 , M 2 e M 4 . Il 3variable K-map con zeri corrispondenti ai termini Max dati è mostrato nella figura seguente.
Non è possibile raggruppare 8 zeri adiacenti o 4 zeri adiacenti. Ci sono tre possibilità di raggruppare 2 zeri adiacenti. Dopo questi tre raggruppamenti, non è rimasto alcun singolo zero come non raggruppato. Il3 variable K-map con questi tre groupings è mostrato nella figura seguente.
Qui abbiamo tre primi implicanti X + Y, Y + Z e Z + X. Tutti questi primi implicanti sono essential perché uno zero in ogni raggruppamento non è coperto da altri raggruppamenti se non dai loro raggruppamenti individuali.
quindi, il simplified Boolean function è
f = (X + Y).(Y + Z).(Z + X)
In questo modo, possiamo facilmente semplificare le funzioni booleane fino a 5 variabili utilizzando il metodo K-map. Per più di 5 variabili, è difficile semplificare le funzioni utilizzando K-Maps. Perché il numero di filecells in K-map ottiene doubled includendo una nuova variabile.
A causa di questo controllo e raggruppamento di quelli adiacenti (termini minimi) o zeri adiacenti (termini massimi) sarà complicato. Noi discuteremoTabular method nel prossimo capitolo per superare le difficoltà del metodo K-map.