Algebra di Boole, forme canoniche e mappe di Karnaugh

I circuiti digitali lavorano con due soli valori, 0 e 1, e il loro comportamento si descrive con l’algebra di Boole. Progettare una rete logica significa scrivere la funzione che deve calcolare e semplificarla, perché un’espressione più corta richiede meno porte, meno area, meno consumo e meno ritardo. In questa lezione vediamo gli assiomi e i teoremi dell’algebra booleana, le forme canoniche e il metodo delle mappe di Karnaugh.

Le operazioni e i teoremi

Le operazioni fondamentali sono il prodotto logico (AND, o ), la somma logica (OR, ) e la negazione (NOT, ). Valgono le proprietà commutativa, associativa e distributiva, con una sorpresa: in Boole sono distributive entrambe le operazioni, anche . Altre identità utili:

Nome	Forma con OR	Forma con AND
elemento neutro
elemento assorbente
idempotenza
complemento
assorbimento
De Morgan

Ogni identità ha una duale, ottenuta scambiando AND con OR e 0 con 1.

Teorema (De Morgan). .

Dimostrazione. Con due variabili ci sono solo quattro casi, e basta controllarli tutti (dimostrazione per esaustione, sempre possibile in un’algebra con valori finiti): per entrambi i membri valgono 1; negli altri tre casi almeno una variabile è 1, quindi e il primo membro vale 0, e il secondo pure, perché almeno uno dei due fattori negati è 0. ∎

De Morgan ha una conseguenza pratica fondamentale: con le sole porte NAND (o le sole NOR) si costruisce qualsiasi funzione, ed è proprio così che sono fatte le porte CMOS (lezione sulla logica CMOS di Dispositivi elettronici).

Le forme canoniche

Qualsiasi funzione si può scrivere partendo dalla sua tabella di verità.

• Somma di prodotti (SOP): per ogni riga in cui la funzione vale 1 si scrive il prodotto delle variabili, negate dove valgono 0 (un mintermine), e si sommano tutti. Si abbrevia con la lista dei numeri delle righe: .
• Prodotto di somme (POS): il duale, partendo dalle righe in cui la funzione vale 0.

La forma canonica è corretta ma lunga: una funzione di 4 variabili con 8 mintermini richiede 8 porte AND a 4 ingressi e una OR a 8 ingressi.

Le mappe di Karnaugh

L’idea per semplificare è il teorema : due mintermini che differiscono per una sola variabile si fondono, e quella variabile sparisce. La mappa di Karnaugh dispone la tabella di verità in una griglia in cui le caselle adiacenti differiscono per una sola variabile: righe e colonne seguono il codice Gray (00, 01, 11, 10), e i bordi opposti sono anch’essi adiacenti, come se la mappa fosse avvolta su un toro.

Il procedimento.

1. Si riportano gli 1 della funzione nelle caselle.
2. Si raggruppano gli 1 in rettangoli di 1, 2, 4, 8… caselle adiacenti, i più grandi possibile; un 1 può stare in più gruppi.
3. Ogni gruppo di caselle elimina variabili: restano quelle che nel gruppo non cambiano.
4. La funzione è la somma dei termini dei gruppi, scelti in numero minimo per coprire tutti gli 1.

Esempio. . I mintermini 5, 7, 13, 15 formano un quadrato al centro della mappa: in tutti e , mentre e cambiano, quindi il gruppo vale . I mintermini 0, 2, 8, 10 sono nei quattro angoli, che sono adiacenti tra loro: hanno e , e danno . Quindi

cioè la funzione vale 1 quando e sono uguali: è il complemento di uno XOR, . Otto mintermini a quattro variabili si riducono a un’unica porta XNOR.

Le condizioni di indifferenza. Spesso alcune combinazioni d’ingresso non possono presentarsi (per esempio i codici da 10 a 15 in un circuito che riceve cifre decimali in BCD). Nella mappa si segnano con una X e si possono considerare 1 o 0, come conviene per formare gruppi più grandi.

Oltre le mappe

Le mappe funzionano bene fino a 4-5 variabili. Per funzioni più grandi si usano algoritmi (Quine-McCluskey, Espresso), che oggi sono dentro gli strumenti di sintesi logica: il progettista descrive la funzione in un linguaggio come VHDL o Verilog (lezione sulle FPGA) e il programma trova la rete di porte, ottimizzando area, ritardo e consumo.