Notice
  • Image could not be created 'cache/e/ee8c63c01404f3c8ad2ed70bae9feeda.jpeg'
  • Image could not be created 'cache/e/ee8c63c01404f3c8ad2ed70bae9feeda.jpeg'

Tutorial sulle mappe di Karnaugh - parte prima

Stampa
( 0 Votes ) 
Valutazione attuale:  / 0
ScarsoOttimo 
Categoria: Elettronica
Data pubblicazione
Scritto da TheAlu10000 Visite: 5536

Le mappe di Karnaugh (prima parte)


Dopo gli ADC, questa volta cercherò di spiegare in maniera comprensibile che cosa sono le mappe di Karnaugh.

Che cosa sono?

Le mappe di Karnaugh sono uno strumento per semplificare la progettazione di una rete logica combinatoria. Può capitare che una rete logica non semplificata abbia molte porte logiche: questa mappa permette di ridurre più o meno drasticamente il numero delle porte logiche richieste per generare una funzione logica in uscita quindi la complessità della rete stessa. Un vantaggio, ad esempio, è la riduzione di spazio occupato dalla rete su un circuito integrato (usando meno porte logiche si usano meno transistor).

Come sono fatte?

Si presentano come un insieme di celle disposte a rettangolo o a quadrato. Il numero di celle è una potenza di due, perchè ogni variabile booleana può assumere solamente due stati e perchè il numero di combinazioni è appunto una potenza di due, cioè 2^(numero variabili). Ogni cella di una mappa corrisponde a una sola combianzione. Ecco mappe a 2, 3 e 4 variabili (da sinistra a destra):

 

Con più di 4 variabili si incominciano a mettere mappe delle variabili meno significative dentro quelle delle variabili più significative. Per 5 variabili diventa così:

In questo caso la mappa di sinistra sarà valida quando la variabile E varrà zero, mentre l'altra varrà per E=1.
Comunque di solito non si va oltre le 4 variabili.
Le mappe di Karnaugh sono utili finchè si usa un basso numero di variabili. Se il numero di variabili aumenta (10-12 variabili o anche di più) la cosa diventa molto complessa anche con le mappe. In questi casi si ricorre a una EPROM programmata a dovere. Una mappa di Karnaugh è definita per una sola funzione, quindi per una sola uscita. Per n uscite si devono fare n mappe.
 Come funzionano?
Vi faccio notare una cosa: nella mappa a tre e quattro variabili compare la seguente sequenza di combinazioni: 00-01-11-10. Uno si potrebbe chiedere perchè non sia 00-01-10-11.
Ebbene, le mappe sono basate su due semplici postulati dell'algebra di Boole:
                                                                 
 
Il primo mi dice che se sommo a una variabile il suo complemento il risultato è sempre uno. Infatti, se A=0, sarà 0+1=1 e se A=1 sarà 1+0=1.
Il secondo mi dice che moltiplicando una variabile per 1 il risultato è la variabile stessa, come nell'algebra classica dove 1 è l'elemento neutro del prodotto.
Le combinazioni sono sistemate in quel modo perchè così, passando da una cella a una adiacente ad essa, cambia solamente un bit. Quindi sarà possibile utilizzare il primo postulato. In combinazione con il secondo postulato la variabile che cambia da una cella a una adiacente potrà essere eliminata.
 Come si usano?
Per poter usare la mappa bisogna disporre di una funzione logica espressa sotto forma di equazione logica (somma di mintermini) o meglio ancora sotto forma di tabella. Ad esempio:
                                                                 
Si inserisce un 1 dentro una cella le cui coordinate corrispondano a una combinazione della tabella la cui uscita vale 1, cioè nella cella individuata da un mintermine. Ci sono tre mintermini in uscita quindi si inseriranno tre 1 dentro la mappa, che è grande 2x2 perchè è a due variabili:
                                                                 
Ora si fa la semplificazione vera e propria. La semplificazione avviene formando gruppi di celle che contengono 1. I gruppi devono avere un numero di celle pari a una potenza di 2, il lato di questi gruppi (che possono essere quadrati o rettangolari) devono avere un numero di celle pari a una potenza di 2, si devono cercare di realizzare gruppi più ampi possibili (più un gruppo è ampio, più la funzione verrà semplificata) e una cella contenente 1 può essere presa più volte, quindi può far parte di più gruppi contemporaneamente. La mappa di prima quindi diventa così:
                                                                                                            
Ogni gruppo che è stato fatto corrisponde a un mintermine della funzione semplificata. Per ricavare questo mintermine bisogna guardare le variabili che il gruppo prende in considerazione e scrivere solamente quelle che non variano (si sta applicando il primo postulato). Il gruppo in basso prende due celle; in entrambe le celle la variabile A vale 1 mentre la B cambia da 0 a 1: la variabile B può essere eliminata e quindi rimane la A. Nell'altro gruppo invece la B vale sempre 1 mentre la A varia: la A può essere eliminata lasciando B. La funzione di uscita quindi si esprime come somma dei mintermini ottenuti. Quindi U = A + B. Notato niente? E' la funzione OR, e la cosa è confermata dalla tabella della verità.
Ribadisco che le celle si possono raggruppare solo se adiacenti: non si possono raggruppare celle poste in diagonale.
Un'altra cosa: sono adiacenti anche due celle che in realtà si trovano agli estremi della mappa, però sulla stessa riga o sulla stessa colonna. Per esempio qui:
                                                                                                            
Infatti fra le due celle raggruppate varia solamente una variabile, mentre le altre rimangono uguali.
Passo ora a mostrarvi la mappa che verrà usata di più, cioè quella a 4 variabili, quindi con 16 celle. Le regole per la semplificazione delle mappe a 3 e 4 variabili sono le stesse viste per le mappe a 2 variabili.
Si ha la funzione:

D C B A U
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 0
0 1 1 1 0
1 0 0 0 1
1 0 0 1 0
1 0 1 0 1
1 0 1 1 1
1 1 0 0 1
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0

La sua mappa sara questa:
                                                                                      
La stessa mappa dopo aver raggruppato le celle contenenti 1:
                                                                                      
Quindi ricavando i mintermini da i 4 gruppi si ottiene la funzione semplificata:
                                                                                                            
La semplificazione è evidente: prima i mintermini erano 10, ora solamente 4.
Varianti
 Può capitare che una funzione presenti molti mintermini che generano un 1 in uscita rispetto al numero totale di combinazioni possibili. Cioè si hanno poche combinazioni in cui la funzione varrà zero. Con le mappe di Karnaugh al posto degli "1" dentro le celle si possono mettere gli "0". Il funzionamento è identico, anche le regole non cambiano, ma ci sono due differenze: la funzione di uscita dovrà essere espressa come prodotto di maxtermini (prodotto di somme) ed ogni variabile che sarà inserita nella somma dovrà essere complementata rispetto alla mappa (se si deve prendere A, nella funzione si scriverà A negato).                 
Può capitare inoltre che ci siano delle condizioni particolari chiamate "condizioni di indifferenza": queste condizioni capitano quando non è importante il livello di uscita della funzione a una particolare combinazione degli ingressi, quindi è indeterminato. Queste condizioni sulla mappa vengono segnate con una X e possono essere molto utili per la semplificazione: dato che non è importante il loro livello (è indifferente appunto), si può scambiare la X con un 1 o con uno 0 in modo da poter fare gruppi più grandi, quindi una maggiore semplificazione.

Un ultima cosa: in una stessa mappa non si possono mettere sia "1" che "0": o si usa solo "1" (quindi funzioni espresse come somma di prodotti) oppure solo "0" (prodotto di somme).

Tratterò più approfonditamente queste varianti nella terza parte.

Nella seconda parte invece sarà mostrato come creare una rete di decodifica da binario a sette segmenti facendo uso delle mappe k.

Joomla 1.7 Templates designed by College Jacke