R: mappe di Karnaugh

From: Maurizio Bonfanti <maurizio.bonfanti_at_tin.it>
Date: 1999/11/07

Marco wrote
>
> Ciao!
>
> non vorrei cadere in un clamoroso errore di omonimia, ma le mappe di K.
> sono dei divertenti giochini che servono a sintetizzare in modo
> ottimizzato delle reti logiche (solo) combinatorie.
> Sono la base per chi studia reti logiche, e quindi puoi trovarle
> descritte in molti testi di elettr. digitale (es. Ronald Tocci)
>
>
> Marco.
>
> P.S. Gia' visto che la domanda mi sembra un po' OT su it.scienza.fisica,
> non vorrei aver descritto un ruolo delle mappe il realta' limitato....
>
> Anna & Rocco ha scritto:
> >
> > Conosco superficialmente le mappe di Karnaugh, ma ho bisogno di
> > informazioni pi� dettagliate a carattere universitario.
> > se possedete tale informazione vi pregherei di rispondermi.
> > Vi ringrazio anticipatamente.
> >
> > ROCCO.

Le mappe di Karnaugh non servono solo per semplificare reti combinatorie
e solo nell'elettronica digitale ma sono uno strumento utile per la sintesi
di
sistemi a stati finiti di qualunque tipo: la funzione di transizione di
stato in quel tipo di sistemi si studia appunto con la tecnica delle mappe,
oltre che con i diagrammi di stato. Questo significa che anche le reti
sequenziali, non solo quelle combinatorie, tramite le tabelle di transizione
possono utilmente essere rappresentate e studiate mediante queste mappe.
Posso provare a dire le poche cose che so in proposito, e che non si trovano
comunque tutte nella stessa fonte. Giudicane tu l'utilit� per i tuoi scopi.
Intanto il numero di variabili trattabili con questa tecnica � in via di
principio illimitato, anche se, con elaborazione manuale, non si va in
genere oltre il sei. A partire dalle quattro variabili, che � il massimo per
una mappa sola, ogni aggiunta di una variabile raddoppia il numero di mappe,
cosa scomoda per l'elaborazione manuale ma non per quella automatica, che
pu� servirsi di array multidimensionali, ossia sfruttare le propriet� della
memoria di sistema, che ha la natura di matrice per definizione cos� come le
mappe sono matrici per definizione.
Come mi pare qualcuno abbia gi� osservato in un post precedente, la mappa
applica uno solo dei teoremi di base dell'algebra di Boole, che sono venti
se si includono quelli di De Morgan, quindi la sua capacit� di
semplificazione non � esauriente. D'altra parte anche altri metodi, come
quello di Quine, si fondano sul medesimo teorema e sono almeno altrettanto
laboriosi col crescere del numero di variabili, e sono meno facilmente
meccanizzabili.
Un altro aspetto � che le mappe possono essere costruite con i "mintermini"
(condizioni vere della funzione logica, 1) ma anche con i maxtermini
(condizioni false, 0). La convenienza a scegliere uno dei due modi (somma di
prodotti o prodotto di somme) dipende dal numero di mintermini e maxtermini
presenti nella colonna che rappresenta la funzione logica. Un esempio: la
tavola della verit� della funzione OR a due variabili ha un solo maxtermine,
quindi la funzione � subito scritta negando il valore corrispondente delle
variabili e sommandole, mentre usando i maxtermini la funzione � di tre
termini e ha bisogno di elaborazione successiva. Questo tipo di mappa �
duale rispetto alla mappa usuale, e in genere non � trattata dai testi,
anche perch� con il tipo usuale il risultato � sempre e comunque garantito,
sia pure con elaborazioni inutilmente lunghe in molti casi.
Un aspetto non marginale � la scelta del codice Gray, e non del codice
binario naturale, per l'ordinamento delle righe e delle colonne delle mappe.
Il codice Gray � non pesato ed � ciclico, e non � solo utile ma � necessario
per l'ordinamento. Infatti il codice Gray ha la caratteristica di cambiare
valore a un solo bit da una posizione alla successiva, e perci� si adatta
perfettamente al teorema su cui si basano le mappe: la somma logica di una
variabile e della sua negata � sempre vera, cio� 1, quindi se fra i
mintermini di due caselle contigue cambia proprio solo un bit �
legittimamente possibile eliminare la variabile corrispondente (due
variabili su quattro caselle contigue, tre su otto e cos� via); questo
corrisponde al raccoglimento a fattore dei bit comuni, lasciando fra
parentesi, appunto, la sola variabile che � cambiata sommata con la sua
negazione, quindi la parentesi � 1 e la variabile sparisce. L'altra
propriet� del codice Gray � la sua ciclicit�, intendendo con questo che
l'ultima combinazione � contigua con la prima. Di qui anche il suo uso per
la misura di posizioni angolari mediante il semplice conteggio delle
variazioni dei bit: se un disco � diviso con un codice Gray di 4 variabili,
a ogni variazione di un bit corrisponde sicuramente un passo di un
sedicesimo di 360�, senza discontinuit� fra la prima e l'ultima
combinazione. Il vantaggio, per le mappe in questione, � che l'ultima riga
in basso � contigua con la prima in alto e quella pi� a destra � contigua
con quella pi� a sinistra, perci� sono possibili semplificazioni anche fra
queste estremit�. E' come se il codice fosse, anche in questo caso,
distribuito su un cilindro. Il codice Gray si costruisce facilmente con una
tecnica a specchio: si parte da 0 1 in colonna (prima variabile), poi lo si
copia di sotto a specchio (0 1 - 1 0); alle prime due cifre si antepongono
due 0 e alle seconde due 1 (seconda variabile); questo blocco si copia di
sotto a sua volta a specchio ottenendo otto combinazioni; davanti alle prime
quattro si mette 0 e davanti alle seconde quattro 1 (terza variabile). E
cos� via.
Nel caso di pi� mappe la semplificazione fra due mappe � possibile fra
caselle omologhe che contengano 1, ma solo se le mappe, a loro volta, sono
contigue, ossia se differiscono per il valore di una sola variabile. Il
sistema, in altre parole, � annidato secondo la logica del teorema in
questione (primo teorema dei complementi: A + non-A = 1).
Una semplificazione esauriente, ripeto, deve servirsi di tutti i teoremi
dell'algebra di Boole, inclusi quelli di De Morgan, e inoltre delle
propriet� associative e distributive (diverse per�, almeno alcune, da quelle
dell'algebra ordinaria), con un vantaggio in pi� rispetto all'algebra
ordinaria: grazie a uno dei due teoremi di idempotenza (A + A = A) �
possibile usare pi� volte il medesimo termine nell'applicazione di queste
propriet�, ossia lo si pu� duplicare quante volte si vuole, possibilit� che
porta spesso a notevoli razionalizzazioni.
Spero, Rocco, di esserti stato utile
Ciao
Maurizio
Received on Sun Nov 07 1999 - 00:00:00 CET