Esercizio 31rete combinatoria con condizioni di indifferenza

1. Tabella di verità

Divisibili per 3 tra 0 e 9: $0, 3, 6, 9$. Le righe $10, \dots, 15$ sono condizioni di indifferenza ($X$): l'uscita può valere 0 o 1, si sceglie il valore che semplifica di più.

$$F(A,B,C,D) = \sum m(0, 3, 6, 9) + d(10, 11, 12, 13, 14, 15).$$

Senza usare le condizioni di indifferenza la forma canonica avrebbe 4 mintermini da 4 variabili: $\overline{A}\,\overline{B}\,\overline{C}\,\overline{D} + \overline{A}\,\overline{B}CD + \overline{A}BC\overline{D} + A\overline{B}\,\overline{C}D$.

2. Mappa di Karnaugh

Righe $AB$ e colonne $CD$ in codice Gray (00, 01, 11, 10); le celle adiacenti, anche ai bordi, differiscono per una sola variabile.

Si raggruppano gli 1 usando le $X$ solo se servono a ingrandire i gruppi (e non è obbligatorio coprire le $X$):

• $m_9$ con $m_{11}$, $m_{13}$, $m_{15}$: gruppo da 4 (righe 10 e 11, colonne 01 e 11): restano $A = 1$ e $D = 1$ → $AD$;
• $m_3$ con $m_{11}$: gruppo da 2 nella colonna 11, righe 00 e 10: restano $B = 0$, $C = 1$, $D = 1$ → $\overline{B}CD$ ($A$ cambia e sparisce);
• $m_6$ con $m_{14}$: gruppo da 2 nella colonna 10, righe 01 e 11: restano $B = 1$, $C = 1$, $D = 0$ → $BC\overline{D}$;
• $m_0$: nessuna cella adiacente a 1 o X (i vicini $m_1$, $m_2$, $m_4$, $m_8$ valgono 0): resta un mintermine da solo, $\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}$.

$$F = \overline{A}\,\overline{B}\,\overline{C}\,\overline{D} + \overline{B}CD + BC\overline{D} + AD$$

I 4 gruppi sono implicanti primi essenziali: ciascuno contiene un 1 che nessun altro copre. Le $X$ usate come 1 sono $m_{11}$, $m_{13}$, $m_{14}$, $m_{15}$; le non usate ($m_{10}$, $m_{12}$) restano 0 nella rete: fuori dal campo del BCD, il valore non importa.

3. Realizzazione con soli NAND

Una somma di prodotti si realizza con NAND-NAND (legge di De Morgan): si invertono gli ingressi dove serve (4 inverter per $\overline{A}, \overline{B}, \overline{C}, \overline{D}$), si calcola ogni prodotto con un NAND e si combinano le uscite con un NAND:

$$F = \overline{\;\overline{\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}}\ \cdot\ \overline{\overline{B}CD}\ \cdot\ \overline{BC\overline{D}}\ \cdot\ \overline{AD}\;}$$

• primo livello: NAND a 4 ingressi ($\overline{A}, \overline{B}, \overline{C}, \overline{D}$), NAND a 3 ($\overline{B}, C, D$), NAND a 3 ($B, C, \overline{D}$), NAND a 2 ($A, D$);
• secondo livello: un NAND a 4 ingressi con le quattro uscite.

Costo: 4 inverter + 5 NAND. Il doppio livello di inversione si cancella: l'uscita è la somma dei prodotti.

4. Verifica

def nand(*x):
    return 0 if all(x) else 1

def F(a, b, c, d):
    na, nb, nc, nd = 1 - a, 1 - b, 1 - c, 1 - d
    t1 = nand(na, nb, nc, nd)        # NAND(A' B' C' D')
    t2 = nand(nb, c, d)              # NAND(B' C D)
    t3 = nand(b, c, nd)              # NAND(B C D')
    t4 = nand(a, d)                  # NAND(A D)
    return nand(t1, t2, t3, t4)      # secondo livello

for n in range(10):                  # cifre BCD valide
    a, b, c, d = (n >> 3) & 1, (n >> 2) & 1, (n >> 1) & 1, n & 1
    assert F(a, b, c, d) == int(n % 3 == 0), n
print("0..9 verificate")
print([(n, F((n >> 3) & 1, (n >> 2) & 1, (n >> 1) & 1, n & 1)) for n in range(10, 16)])
# [(10, 0), (11, 1), (12, 0), (13, 1), (14, 1), (15, 1)]: valori scelti dalla minimizzazione sulle combinazioni vietate

La rete dà l'uscita giusta per le 10 cifre; per le combinazioni 10-15 (che non si presentano) vale 0, 1, 0, 1, 1, 1, cioè quanto serve per avere gruppi più grandi.

Errori comuni

• Trattare le condizioni di indifferenza come 0 (e perdere i gruppi $AD$, $\overline{B}CD$, $BC\overline{D}$) o come 1 obbligatori (e fare gruppi che non servono).
• Scrivere il gruppo da 2 della colonna 11 come $\overline{A}\,\overline{B}CD$: l'adiacenza con $m_{11}$ ($A = 1$) elimina $A$.
• Dimenticare che $m_0$ non ha vicini utili e resta un mintermine completo.
• Nella realizzazione NAND-NAND, dimenticare gli inverter sugli ingressi negati.
• Verificare solo sulle cifre dove $F = 1$: bisogna controllare tutte le 10 cifre.