Quando si fa l'analisi di una funzione logica, si devono eseguire i seguenti passi:
- si parte dalla funzione logica scritta nella forma Y=..... (esempio Y=A+B)
- si scrive la tavola della verità
- si disegna il circuito logico
Invece quando si fa la sintesi di una funzione logica, si devono eseguire i seguenti passi:
- si parte dalla tavola della verità oppure da un enunciato (specifiche)
- si deve determinare con uno dei metodi possibili la funzione che implementa la tavola della verità
- si disegna il circuito logico
La tavola della verità, si ricorda, è una tabella che ha tante righe quante sono le possibili combinazioni in binario delle variabili di ingresso.
In più ha la riga di intestazione (header).
Con N variabili di ingresso ha 2N righe.
Ad esempio con due variabili di ingresso, A e B, ha 22=4 righe righe; con tre variabili di ingresso A, B, C ha 23=8 righe righe; con quattro variabili di ingresso A, B, C, D ha 24=16 righe.
Inoltre la tavola della verità ha tante colonne quante sono gli ingressi e le uscite (in generale si possono aggiungere anche le colonne per i risultati intermedi, in modo da facilitare il calcolo finale).
L'enunciato è una frase in italiano (o in inglese ;-) ) che specifica cosa la funzione logica deve fare, anche se ovviamente non dice come deve essere fatto, perché SPECIFICARE COME è compito del processo di sintesi.
Un esempio di enunciato è "realizzare un antifurto elettronico per un appartamento con due camere da letto e un soggiorno cucina, che produca un allarme quando in una di queste tre stanze si introduca un ladro".
In generale si puo' dire che il processo di Sintesi non è deterministico, nel senso che data una tabella della verità o un enunciato non esiste una unica funziona logica che la implementa, ossia che realizza cio' che si vuole ottenere.
Invece il processo di Analisi è deterministico, ossia data una funzione logica, sostanzialmente, esiste una unica tabella della verità, ed un unico schema logico.
La Sintesi puo' essere fatta in due modi:
- attraverso le forme canoniche
- attraverso le mappe di Karnaugh
Forme canoniche
Esistono due forme canoniche:
- La somma di mintermini
- Il prodotto di maxtermini
Si definisce Mintermine il prodotto di tutte le variabili di ingresso, prese in forma normale se valgono uno e prese in forma negata se valgono zero.
Nella prima forma canoniche vanno considerati solo la somma dei mintermini corrispondenti all'uscita uguale a uno, perché i mintermini corrispondenti a zero non vanno considerati.
Si definisce Maxtermine la somma di tutte le variabili di ingresso, prese in forma normale se valgono zero e prese in forma negata se valgono uno.
Nella seconda forma canonica vanno considerati solo i prodotti dei Maxtermine corrispondenti all'uscita uguale a zero , perché i Maxtermini corrispondenti a uno non vanno considerati.
Consideriamo il processo di sintesi a partire dalla seguente tavola della verità con tre ingressi
| A | B | C | Y | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | m0 |
| 0 | 0 | 1 | 1 | m1 |
| 0 | 1 | 0 | 1 | m2 |
| 0 | 1 | 1 | 0 | m3 |
| 1 | 0 | 0 | 1 | m4 |
| 1 | 0 | 1 | 0 | m5 |
| 1 | 1 | 0 | 0 | m6 |
| 1 | 1 | 1 | 1 | m7 |
Si indicano con la m minuscola i mintermini, mettendo con pedice la riga corrispondente partendo da zero.
posso scrivere
m1=A B C
m2=A B C
m4=A B C
m7=A B C
La prima forma canonica (somma di mintermini) si esprime con
Y=m1+m2+m4+m7 =A B C + A B C + A B C + A B C
Nel caso della seconda forma canonica vanno considerati i Maxtermini che si indicano con la M maiuscola, mettendo sempre a pedice la riga corrispondente partendo da zero.
| A | B | C | Y | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | M0 |
| 0 | 0 | 1 | 1 | M1 |
| 0 | 1 | 0 | 1 | M2 |
| 0 | 1 | 1 | 0 | M3 |
| 1 | 0 | 0 | 1 | M4 |
| 1 | 0 | 1 | 0 | M5 |
| 1 | 1 | 0 | 0 | M6 |
| 1 | 1 | 1 | 1 | M7 |
Posso scrivere
M0=A + B + C
M3=A + B + C
M5=A + B + C
M6=A + B + C
La seconda forma canonica (prodotto di Maxtermini) si esprime con
Y=M0° M3°M5°M6 =(A + B + C)(A + B + C)(A + B + C)(A + B + C)
Le mappe di Karnaugh
Le mappe di Karnaugh permettono di rappresentare e minimizzare funzioni logiche fino ad un massimo di cinque variabili.
Ma a livello di scuola superiore si studiano fino a quattro variabili.
Per costruire una mappa di Karnaugh a partire dalla tavola della verità, oppure a partire da una funzione espressa in forma canonica, occorre applicare alcune
regole:
- una mappa è un diagramma contenente tante caselle (o celle) quante sono le configurazioni possibili delle variabili indipendenti della funzione; se n sono le variabili d’ingresso della funzione, la mappa conterrà 2n celle;
- ciascuna casella è individuabile tramite una riga e una colonna, ove la riga e la colonna riportano gli stati delle variabili che hanno determinato quella uscita;
- su ogni lato della mappa possono essere riportate soltanto due variabili d’ingresso. Questa regola unita alla precedente porta a concludere che una mappa può contenere al massimo funzioni di 4 variabili;
- riportando i valori delle variabili d’ingresso sui lati della mappa, occorre che nel passaggio da una casella a quella adiacente cambi di stato soltanto una variabile e, in particolare i bit adiacenti
rimangano invariati. Pertanto, nelle righe o colonne con due variabili la progressione è:
Le caselle adiacenti corrispondono a configurazioni delle variabili che differiscono per il valore di una ed una sola variabile.
Minimizzazione mediante le mappe
Le mappe di Karnaugh, utilizzate nel modo ottimale, consentono di minimizzare le funzioni logiche, in modo da ottenere schemi circuitali realizzati con il numero minimo di porte
logiche con un minor numero di ingressi.
Costruita la mappa, per ricavare la funzione di commutazione minimizzata, relativa ad una sola uscita del sistema, ci si avvale delle seguenti regole:
- per ottenere la funzione logica semplificata dalla mappa di Karnaugh, occorre individuare i raggruppamenti di ‘1’ nelle caselle adiacenti della mappa, fino a collocare ogni 1 in un raggruppamento (un 1 può far parte di più raggruppamenti).
- Poiché le mappe si possono vedere come chiuse su se stesse, sono adiacenti anche le caselle poste lungo i bordi, pertanto è possibile individuare raggruppamenti tra caselle poste lungo il bordo destro e quello sinistro, oppure lungo il bordo superiore e quello inferiore, cioè considerando tutti i possibili modi in cui la mappa può richiudersi su se stessa;
- un raggruppamento può essere un quadrato o un rettangolo con un numero totale di celle pari ad una potenza di due. Le proprietà dei raggruppamenti sono:
- una coppia di 1, orizzontale o verticale, produce un mintermine in cui manca la variabile che ha cambiato di stato nel raggruppamento;
- un quartetto di 1, orizzontale o verticale e di forma 4x1 oppure 2x2, produce un mintermine da cui risultano eliminate le due variabili che cambiano di stato nel raggruppamento;
- un ottetto di 1, in un qualsiasi verso e di qualsiasi forma, produce un mintermine in cui risulta presente l’unica variabile che non cambia di stato.
- un sedicetto di 1, produce, ovviamente, direttamente Y=1
- La funzione di commutazione è costituita da tanti mintermini quanti sono i raggruppamenti; ciascun mintermine è formato dal prodotto delle variabili che nel passaggio da una casella all’altra del raggruppamento, mantengono lo stato 1, per i negati di quelle che mantengono lo stato 0;
- Le variabili che cambiano di stato nel passaggio tra caselle adiacenti non vengono prese in considerazione;
- La semplificazione è tanto migliore quanto minore è il numero di raggruppamenti e maggiore la dimensione del singolo raggruppamento;
- Le condizioni di indifferenza: vengono definite in questo modo: le combinazioni delle variabili d’ingresso che non danno luogo ad uscita determinata per il problema in esame.
- In questo caso, anziché lasciare libera la corrispondente casella della mappa, è possibile porvi un simbolo (per esempio X) che assume valore di 1 nella ricerca dei raggruppamenti, in modo da migliorare la minimizzazione.
ESEMPIO
Consideriamo la funzione algebrica con quattro variabili d’ingresso ed una uscita espressa nella prima forma canonica.
Y = A B C D + A B CD + A BC D + A BCD + AB C D + AB CD + ABC D + ABCD
Le variabili sono essere raggruppate a due a due e costituiscono i riferimenti di riga e di colonna, l’indicazione delle righe e delle colonne riporta dunque una coppia di zero e uno.
Tali riferimenti sono riportati facendo in modo che due caselle adiacenti differiscano tra loro solo per una variabile.
L'esempio di cui sopra ha dato luogo a tre raggruppamenti:
- il raggruppamento in nero di quattro variabili, il cui contributo finale è BD in quanto la A e la C spariscono perché cambiano all'interno del raggruppamento
- il raggruppamento in blu di quattro variabili, il cui contributo finale è CD in quanto la A e la B spariscono perché cambiano all'interno del raggruppamento
- il raggruppamento in rosso di due variabili, il cui contributo finale è B C D in quanto la A sparisce perché cambia all'interno del raggruppamento
Pertanto, la Y minimizzata attraverso l'uso delle mappe K è
Y = BD + CD + B C D
Si specifica che un raggruppamento da due elimina una variabile, uno da quattro due variabili, un raggruppamento da otto elimina tre variabili.