Esercizio 13funzione con don't care, forme minime SOP e multiplexer (tema d'esame settembre 2025)

---

Teoria usata: Mappe di Karnaugh - implicanti e copertura minimaLa mappa di Karnaugh è la tabella di verità disposta in una griglia con righe e colonne in codice Gray, così che celle adiacenti (anche tra bordi opposti) differiscano in una sola variabile. Si raggruppano gli 1 in rettangoli di $2^k$ celle: ogni gruppo elimina $k$ variabili e dà un prodotto. Implicante primo = gruppo massimo; essenziale = unico a coprire un mintermine; la copertura minima contiene tutti gli essenziali più il minimo di altri primi (può non essere unica). Efficace fino a 4 variabili.Mappe di Karnaugh - implicanti e copertura minima →, Mappe di Karnaugh - POS, condizioni di don't care e paritàPer la POS minima si raggruppano gli 0 della mappa, si ottiene la SOP minima di $\overline F$ e si scrive $F$ come prodotto di somme (variabile diretta se vale 0 nel gruppo, negata se vale 1). Le condizioni di don't care (X) sono combinazioni di ingresso che non si presentano o la cui uscita è indifferente: si usano come 1 o come 0 a seconda di quel che allarga i gruppi (mai raggruppamenti fatti solo di X). Le funzioni XOR a più variabili (disparità) e XNOR (parità) hanno mappa a scacchiera: non si semplificano con i gruppi.Mappe di Karnaugh - POS, condizioni di don't care e parità →, Multiplexer e funzioni logiche realizzate con decoder e multiplexerIl multiplexer (MUX) $2^n$-to-1 ha $2^n$ ingressi dati, $n$ ingressi di selezione e un'uscita che copia l'ingresso selezionato: $Y=\sum_i m_i(S),I_i$. Si realizza con decoder + AND di enable + OR (costo 22 per il 4-to-1) o direttamente (costo 18). Un MUX $2^n$-to-1 realizza qualunque funzione di $n$ variabili (ingressi dati = colonna della tabella di verità); con un MUX $2^{n-1}$-to-1 si usano le $n-1$ variabili come selezione e gli ingressi dati valgono $0$, $1$, $X$ o $\overline X$ (l'ultima variabile). I MUX a vettori selezionano gruppi di bit.Multiplexer e funzioni logiche realizzate con decoder e multiplexer →.

a) Mappa di Karnaugh

Righe $XY$, colonne $WZ$ (Gray). Gli 1 sono nelle celle $1,7,14,15$, le X nelle celle $0,3,4,8,10,12$:

(Tra parentesi l'indice della cella.)

b) Forme minime SOP

Implicanti primi (si usano le X come 1 per allargare i gruppi):

• $X\overline Z$: celle $8,10,12,14$ (righe $XY=10$ e $11$, colonne $WZ=00$ e $10$);
• $YWZ$: celle $7,15$;
• $\overline X\,\overline Y\,Z$: celle $1,3$;
• $\overline X\,\overline Y\,\overline W$: celle $0,1$;
• $\overline X WZ$: celle $3,7$;
• $XYW$: celle $14,15$;
• $\overline W\,\overline Z$: celle $0,4,8,12$.

Nessun implicante primo è essenziale: ogni 1 è coperto da due primi diversi ($1$ da $\overline X\overline YZ$ o $\overline X\overline Y\overline W$; $7$ da $YWZ$ o $\overline XWZ$; $14$ da $X\overline Z$ o $XYW$; $15$ da $YWZ$ o $XYW$). Bisogna quindi scegliere la copertura minima per confronto. Il minimo è di 3 prodotti e 8 letterali:

• $YWZ$ (copre $7,15$) $+$ $X\overline Z$ (copre $14$, usando X $8,10,12$) $+$ un implicante che copre la cella $1$.

La cella $1$ si copre in due modi equivalenti, quindi le forme minime sono due: $$F=YWZ+\overline X\,\overline Y\,\overline W+X\overline Z\qquad\text{oppure}\qquad F=YWZ+\overline X\,\overline Y\,Z+X\overline Z .$$ Altre coperture con 3 prodotti (per esempio $\overline XWZ+XYW+\dots$) hanno più letterali (9). Non c'è una forma con 2 prodotti.

c) Implementazione con multiplexer

Si sceglie una delle due forme e si sceglie come valgono i don't care in modo coerente con essa: con la seconda forma, $F=YWZ+\overline X\,\overline Y\,Z+X\overline Z$, la funzione è completamente specificata:

$F=\sum m(1,3,7,8,10,12,14,15)$ (le X $3,8,10,12$ valgono $1$; $0,4$ valgono $0$).

Si cerca il multiplexer più piccolo. Un MUX 8-to-1 ($8$ dati $+3$ selezioni $=11$ ingressi) realizza ogni funzione di 4 variabili con dati in $\{0,1,Z,\overline Z\}$. Ma qui conviene un MUX 4-to-1 ($4$ dati $+2$ selezioni $=6$ ingressi): si usano come selezione due variabili e come dati funzioni (costanti o letterali) delle altre due. Con selezione $S_1S_0=(Y,Z)$ per ogni coppia $(Y,Z)$ si guarda come $F$ dipende da $X,W$:

Schema: MUX 4-to-1 con selezione $S_1=Y$, $S_0=Z$ e ingressi $I_0=X$, $I_1=\overline X$, $I_2=X$, $I_3=W$, uscita $F$; serve un inverter per $\overline X$. Riscontro con la tabella: per $XYWZ=1011$ ($YZ=01$, $X=1$): $I_1=\overline X=0$ ✓ ($F=0$); per $0101$ ($YZ=11$, $W=0$): $I_3=W=0$ ✓; per $1110$ ($YZ=10$, $X=1$): $I_2=1$ ✓.

Con la prima forma non esiste una simile semplificazione con $Y,Z$ come selezione: servirebbe un MUX 8-to-1 (con selezione $X,Y,W$ i dati sono $1,0,0,Z,\overline Z,\overline Z,\overline Z,1$). Per questo la richiesta di "una sola delle forme" e del "minimo numero di ingressi" porta a scegliere la seconda.

Errori comuni

• Dimenticare che le X vanno usate come 1 o 0 a scelta, e che dopo aver scelto la forma i valori sono fissati.
• Credere che esista una sola forma minima: qui sono due (e nessun implicante primo è essenziale).
• Usare sempre un MUX $2^{n-1}$-to-1 con dati $0,1,Z,\overline Z$: con l'ultima scelta delle variabili e le X si può scendere a un MUX $2^{n-2}$-to-1 con dati letterali.
• Dimenticare l'inverter per $\overline X$ nel conteggio.