Reti combinatorie e mappe di Karnaugh

Una rete combinatoria è un circuito senza memoria: le uscite dipendono solo dai valori attuali degli ingressi (a meno del ritardo di propagazione). Non ha cicli di retroazione. Se ci sono cicli, la rete può ricordare: è una rete sequenziale (vedi Latch e flip-flopReti sequenziali e retroazione; latch SR con porte NOR e stato proibito; latch SR e D abilitati dal clock; flip-flop D master-slave sensibile al fronte; flip-flop JK e T; tempi di setup e hold; clock e periodo minimo.Latch e flip-flop →).

Forme canoniche

Dalla tabella di verità si scrive sempre la funzione in due forme.

• Mintermine: prodotto (AND) di tutte le variabili, dirette o negate, che vale 1 su una sola riga. Per la riga $A=0, B=1, C=1$ è $\overline{A}BC$ ($m_3$, dal numero binario 011).
• Somma di prodotti (SOP): OR dei mintermini delle righe in cui $F = 1$.
• Maxtermine: somma (OR) che vale 0 su una sola riga: per $A=0,B=1,C=1$ è $A + \overline{B} + \overline{C}$.
• Prodotto di somme (POS): AND dei maxtermini delle righe in cui $F = 0$.

Esempio:

$$F = \sum m(1, 3, 5, 6, 7) = \overline{A}\,\overline{B}C + \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC$$

La forma canonica è corretta ma costosa: 5 AND a 3 ingressi e un OR a 5 ingressi. Si semplifica.

Mappe di Karnaugh

La tabella di verità disposta in una griglia in cui righe e colonne seguono il codice Gray (00, 01, 11, 10): due celle adiacenti differiscono per una sola variabile, e sono adiacenti anche i bordi opposti (la mappa "si chiude" a cilindro e a toro).

Regole:

1. si raggruppano gli 1 in rettangoli di 1, 2, 4, 8, … celle adiacenti (potenze di 2);
2. gruppi più grandi possibile e meno gruppi possibile; un 1 può stare in più gruppi;
3. ogni gruppo dà un prodotto con le sole variabili che non cambiano nel gruppo; un gruppo di $2^k$ celle elimina $k$ variabili.

Mappa dell'esempio (righe $A$, colonne $BC$):

• Gruppo da 4: colonne 01 e 11, entrambe le righe. Cambiano $A$ e $B$, resta $C = 1$ → $C$.
• Gruppo da 2: riga $A = 1$, colonne 11 e 10. Cambia $C$, restano $A = 1, B = 1$ → $AB$.

$$F = C + AB$$

Verifica su una riga: $A=1, B=1, C=0$ → $0 + 1 = 1$ ✓.

Esempio a 4 variabili

$F(A,B,C,D) = \sum m(0, 2, 5, 7, 8, 10, 13, 15)$.

• I quattro angoli (0, 2, 8, 10) sono adiacenti tra loro: restano $B = 0, D = 0$ → $\overline{B}\,\overline{D}$.
• Il quadrato centrale (5, 7, 13, 15): restano $B = 1, D = 1$ → $BD$.

$$F = \overline{B}\,\overline{D} + BD = \overline{B \oplus D}$$

Condizioni di indifferenza

Se alcune combinazioni di ingresso non possono presentarsi (es. i codici 1010–1111 in BCD), in quelle celle si mette una X (don't care) e si usa come 1 o 0, a seconda di cosa allarga i gruppi.

Per la forma POS si raggruppano gli 0 nello stesso modo e si scrive il prodotto di somme (variabile negata se nel gruppo vale 1).

Costo e ritardo

Una SOP si realizza con due livelli di porte (AND poi OR): il ritardo è di circa due porte, qualsiasi sia la funzione. Semplificare riduce il numero di porte e di ingressi, cioè area e consumo. Con molte variabili (più di 5–6) le mappe diventano scomode e si usano algoritmi (Quine-McCluskey, strumenti di sintesi).

Errori tipici

• Ordinare le colonne 00, 01, 10, 11 (binario) invece di 00, 01, 11, 10 (Gray): i gruppi trovati sono sbagliati.
• Fare gruppi da 3 o da 6 celle.
• Dimenticare le adiacenze tra bordi opposti e tra i quattro angoli.