lunedì 10 novembre 2008

Mappe di Karnaugh (struttura)


Del modulo sull'algebra di Boole e le porte logiche riporterò una lezione sulle mappe di karnaugh evidenziando la minimizzazione di una funzione logica attraverso di esse.
Non preoccupatevi sarà indolore. Continuate a studiare ragazzi!!!

MAPPE DI KARNAUGH
Bene ragazzi. Parleremo di un metodo potente da applicare sulle funzioni logiche. Ricordate che finora abbiamo imparato come sia possibile implementare una funzione booleana mediante porte logiche a partire sia dall’espressione algebrica della funzione sia dalla sua tavola di verità, dopo aver ricavato una delle due forma canoniche. Su una funzione così ottenuta, il più delle volte, occorre operare in maniera da semplificarla o come si dice, da minimizzarla. Il metodo di cui parleremo in questa lezione è usato proprio per questo scopo. Si tratta delle mappe di Karnaugh o mappe K; è un metodo grafico molto utilizzato.
La mappa di Karnaugh è stata inventata nel 1953 da Maurice Karnaugh, un ingegnere in Telecomunicazioni.
Per quale motivo occorre minimizzare una funzione?
Pensate ad esempio che, una volta ricavata la funzione bisogna realizzarla mediante un circuito; è chiaro allora che minimizzare la funzione significa ridurre il numero di porte logiche da inserire nel circuito il che comporta di ridurre i costi.
Subito vi dico, per non farvi spaventare o preoccupare, che le mappe di Karnaugh sono semplici.
Le mappe di Karnaugh permettono di rappresentare e minimizzare funzioni logiche fino a sei variabili. Esse rappresentano la tabella di verità di una funzione in forma bidimensionale.

Struttura della mappa K
Le mappe di Karnaugh sono composte da un certo numero di caselle o celle.
Quante sono le celle?
Sono pari al numero dei valori delle variabili di ingresso (ovvero quante sono le righe della tavola di verità) opportunamente disposte una accanto all’altra. Un esempio ci aiuterà a capire meglio:


Nella fig.1 notiamo la corrispondenza che c’è fra le caselle della mappa di Karnaugh e le righe della tavola di verità, infatti la cella P0 corrisponde alla riga 0 della tavola di verità, con A=0, B=0; la casella P1 alla riga 1, con A=0, B=1; la casella P2 alla riga 2, con A=1, B=0; infine la casella P3 alla riga 3, con A=1, B=1.
Si può notare anche che con due variabili di ingresso (A, B) abbiamo quattro celle, quindi il numero delle caselle della mappa K è ottenuto come 2n dove n corrisponde al numero delle variabili di ingresso.
Riportiamo anche le mappe per tre (A,B,C) e quattro variabili di ingresso (A,B,C,D):


Ragazzi notate che, specialmente osservando la mappa di Karnaugh a quattro variabili, due caselle adiacenti differiscono per il valore di una sola variabile.
La casella P0 corrisponde ai valori A=0, B=0, C=0, D=0 (riga n.0 della tavola di verità) e quindi al mintermine la casella P1 individuata dalla colonna A=0, B=0 e dalla riga C=0, D=1, corrisponde al mintermine D (riga n.1 della tavola), e così via per tutte le caselle. Fra caselle adiacenti si verifica il cambiamento del valore di una sola variabile: dalla casella P12 alla P8, ad esempio, cambia solo B che passa da 1 a 0, mentre rimangono inalterate A,C e D, rispettivamente uguali a 1,0 e 0; dalla casella P5 alla P7 cambia C da 0 a 1, ecc.
Ciò è stato volutamente ottenuto disponendo opportunamente le righe e le colonne, ossia passando, nell’ordine, dalla riga o colonna 00, alla 01, alla 11, alla 10. La caratteristica dell’adiacenza deriva dal fatto che la mappa di Karnaugh pur essendo disegnata su un piano in realtà ha una struttura toroidale.
Ragazzi sono sicuro che a tutti voi piacciono le ciambelle, vero? Come le preferite? Farcite in che modo? Credo che vada bene qualsiasi gusto, purché sia una ciambella! Ora pensate alla mappa di Karnaugh: immaginatela con i lati sinistro e destro e superiore ed inferiore coincidenti come a formare una ciambella.
Le caselle dell’ultima colonna sono da considerarsi adiacenti a quelle della prima colonna disposte sulla stessa riga; così la P8 con la P0, la P9 con la P1, la P11 con la P3, la P10 con la P2. Infatti nel passaggio dalle une alle altre cambia solo il valore di A. Lo stesso vale per le caselle della prima e dell’ultima riga: le coppie di caselle P0 e P2, P4 e P6, P12 e P14, P8 e P10 sono pertanto adiacenti.


Adesso vi faccio riposare un pò.
Continueremo trattando il riempimento delle mappe di Karnaugh.

Nessun commento: