Risolutore di Mappa di Karnaugh (K-Map)

Il Risolutore di Mappa di Karnaugh (K-Map) minimizza qualsiasi funzione logica booleana da 2 a 5 variabili e visualizza la semplificazione come una classica K-map con raggruppamenti codificati a colori. Inserisci i tuoi mintermini, maxtermini o usa la tabella di verità interattiva — il risolutore esegue l'algoritmo di Quine-McCluskey internamente, trova ogni implicante primo, contrassegna quelli essenziali e produce l'espressione minima in Somma di Prodotti (SOP) o Prodotto di Somme (POS) con una spiegazione passo dopo passo. Clicca su qualsiasi chip di implicante primo per far pulsare le celle che copre e vedere come il raggruppamento semplifica la logica.

Cos'è una Mappa di Karnaugh?

Una mappa di Karnaugh (inventata da Maurice Karnaugh nel 1953) è una rappresentazione grafica di una tabella di verità, strutturata in modo che le celle che differiscono per una sola variabile di input siano fisicamente adiacenti. Il trucco fondamentale è l'ordinamento in codice Gray di righe e colonne: etichette consecutive come 00, 01, 11, 10 differiscono per esattamente un bit. Questa adiacenza permette di individuare visivamente gruppi di 1 (o 0) che possono essere combinati in un unico termine semplificato.

Per n variabili di input, la K-map ha 2^n celle. Una K-map a 4 variabili è una griglia 4×4 di 16 celle; una mappa a 5 variabili è disegnata come due griglie 4×4 adiacenti.

SOP vs POS: Quale Forma Scegliere

Somma di Prodotti (SOP)

La SOP raggruppa le celle con valore 1. Ogni gruppo diventa un prodotto (AND) di letterali e tutti i gruppi sono messi in OR tra loro. Esempio: AB'C + BD. La SOP è solitamente l'impostazione predefinita perché mappa direttamente alle reti di porte AND–OR.

Prodotto di Somme (POS)

Il POS raggruppa le celle con valore 0. Ogni gruppo diventa una somma (OR) dei letterali complementati e tutte le somme sono messe in AND tra loro. Esempio: (A + B')(C + D'). Il POS è spesso più compatto quando la funzione ha più 1 che 0.

Lo strumento calcola entrambe le forme in modo indipendente: cambia la modalità di output per confrontare il numero di letterali e scegliere quella più semplice per la tua implementazione.

Regole di Raggruppamento per le Mappe di Karnaugh

• Solo gruppi di potenze di due: i gruppi devono contenere 1, 2, 4, 8 o 16 celle. Un gruppo di 3 o 5 non è consentito.
• Forma rettangolare: le celle in un gruppo formano un rettangolo (orizzontalmente, verticalmente o avvolgendosi attorno ai bordi).
• Adiacenza Wrap-around: la riga superiore è adiacente alla riga inferiore; la colonna più a sinistra è adiacente alla colonna più a destra. Ecco perché l'ordinamento in codice Gray è importante.
• Prima i gruppi più grandi: i gruppi più grandi eliminano più variabili, producendo termini di prodotto più brevi. Un gruppo di 8 celle elimina 3 variabili; un gruppo di 4 celle ne elimina 2; un gruppo di 2 celle ne elimina 1.
• Ogni 1 deve essere coperto: almeno un gruppo deve coprire ogni cella con 1 (per SOP) o ogni cella con 0 (per POS).
• La sovrapposizione è consentita: lo stesso 1 può essere coperto da più gruppi se ciò porta a gruppi più grandi.
• I don't-care sono flessibili: possono essere raggruppati se ciò produce gruppi più grandi, ma non è obbligatorio coprirli.

Implicanti Primi e Implicanti Primi Essenziali

Un implicante primo è un gruppo che non può essere ulteriormente espanso: ingrandirlo includerebbe una cella con valore 0 (per SOP). Il risolutore elenca ogni implicante primo trovato. Successivamente, sceglie una copertura minima: il set più piccolo di implicanti primi che copre ogni mintermine richiesto.

Un implicante primo essenziale è contrassegnato come ESSENZIALE quando è l'unico implicante primo che copre almeno un mintermine specifico. Ogni espressione minima deve includere tutti gli implicanti primi essenziali. Dopo averli selezionati, i restanti mintermini non coperti vengono coperti dagli implicanti primi aggiuntivi più economici.

Condizioni Don't-Care

Un don't-care (mostrato come X sulla K-map) è una combinazione di input il cui output è irrilevante: o non si verifica mai nel circuito reale o il suo valore non ha importanza. L'algoritmo è libero di trattare ogni X come 0 o 1, scegliendo il valore che produce l'espressione più semplice. In pratica, i don't-care riducono spesso il numero di letterali del 30–60%. Una fonte comune nel mondo reale: i decodificatori di cifre decimali che utilizzano solo 10 delle 16 combinazioni di input a quattro bit, lasciando le combinazioni 10–15 come don't-care.

L'Algoritmo di Quine-McCluskey

La K-map è un metodo visivo, ma per più di 4–5 variabili diventa poco pratica. L'algoritmo di Quine-McCluskey (QM) è l'equivalente tabellare — matematicamente rigoroso e scalabile. Questo risolutore utilizza internamente il QM:

1. Elenca i mintermini in binario, raggruppandoli per numero di bit a 1.
2. Combina le coppie di gruppi adiacenti (che differiscono per un bit), sostituendo il bit differente con un trattino. Esempio: 0011 + 0111 → 0-11.
3. Ripete finché non sono più possibili ulteriori combinazioni. I termini che non possono essere combinati sono implicanti primi.
4. Costruisce una tabella degli implicanti primi — le righe sono gli implicanti primi, le colonne sono i mintermini richiesti. Identifica gli implicanti essenziali (colonne con un unico segno di spunta).
5. Metodo di Petrick / ricerca esaustiva: per i restanti mintermini non coperti, trova il set più piccolo di implicanti aggiuntivi che li copre.

Come usare questo calcolatore

1. Seleziona il numero di variabili: 2, 3, 4 o 5. La griglia della K-map si adatta automaticamente.
2. Scegli un metodo di inserimento:
   • Mintermini: inserisci gli indici dove F = 1 (es. 1, 3, 5, 7) ed eventuali don't-care.
   • Maxtermini: inserisci gli indici dove F = 0. Il risolutore calcola automaticamente il resto come 1.
   • Tabella di Verità: clicca su ogni riga per scorrere l'output tra 0, 1 e X. Perfetto per la logica progettata a mano.
3. Scegli l'output SOP o POS. Confronta entrambe le forme cambiando opzione: una è spesso più corta dell'altra.
4. Clicca su Risolvi. Appare la K-map con ogni implicante primo in un colore distinto. Clicca su qualsiasi chip per far pulsare le celle che copre.
5. Ispeziona i passaggi: il dettaglio di Quine-McCluskey mostra come è stato derivato ogni implicante primo e quali sono essenziali.

Esempio Pratico: Funzione a 4 Variabili con Don't-Care

Considera F(A,B,C,D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).

Senza i don't-care, la SOP minima richiederebbe diversi termini. Trattando {0, 2} come 1, il risolutore può costruire il gruppo di 4 celle A'B' (che copre 0, 1, 2, 3). Trattando 5 come un 1, può estendere la copertura di CD. La semplificazione risultante è:

Solo 4 letterali — rispetto agli oltre 10 senza il trucco dei don't-care. Puoi caricare questo esatto esempio con l'esempio rapido "4 var con Don't-Care" qui sopra.

Perché Minimizzare le Funzioni Booleane?

• Meno porte = minor costo dell'hardware, area del chip più piccola, minor consumo energetico.
• Circuiti più veloci: meno ritardi delle porte sul percorso critico.
• Documentazione più pulita: un'espressione concisa è più facile da verificare e mantenere.
• Fondamento del design digitale: ogni strumento di sintesi FPGA esegue un discendente di Quine-McCluskey (Espresso-II e successivi).

Limitazioni e Quando Usare Altri Strumenti

• Oltre 5 variabili: le K-map diventano visivamente confuse. Questo strumento ne supporta fino a 5 suddividendole in due mappe 4×4. Oltre questo limite, affidati ai passaggi di Quine-McCluskey o usa strumenti di sintesi come ABC / Espresso.
• Hazard e glitch: una copertura minima può contenere hazard statici. Per un design privo di hazard, includi implicanti primi ridondanti — questo strumento li evidenzia ma non aggiunge automaticamente le coperture per gli hazard.
• Minimizzazione multi-output: se diverse funzioni condividono variabili, la minimizzazione congiunta (condivisione delle porte) produce hardware più piccolo. Questo strumento minimizza una funzione alla volta.

Domande Frequenti

Cos'è una mappa di Karnaugh?

Una mappa di Karnaugh (K-map) è un metodo visivo per minimizzare le espressioni booleane. Le celle sono disposte in modo che le celle adiacenti differiscano per una sola variabile (ordinamento in codice Gray). Il raggruppamento degli 1 in rettangoli di dimensione 1, 2, 4, 8 o 16 rivela l'espressione minima della Somma di Prodotti.

Qual è la differenza tra SOP e POS?

SOP (Sum of Products) raggruppa le celle con 1 e mette in OR i loro termini di prodotto, ad esempio A'B + CD. POS (Product of Sums) raggruppa le celle con 0 e mette in AND i loro termini di somma, ad esempio (A + B')(C' + D). Entrambe descrivono la stessa funzione, ma una forma è solitamente più compatta.

Cosa sono i don't-care e perché usarli?

I termini don't-care (contrassegnati con X) sono combinazioni di input il cui valore di output è irrilevante: non si verificano mai o il loro valore non ha importanza. Il risolutore può trattarli come 0 o 1, a seconda di quale produca l'espressione più semplice. I don't-care spesso riducono drasticamente il numero di letterali.

Cos'è un implicante primo?

Un implicante primo è il gruppo più grande possibile di celle adiacenti con valore 1 (dimensione potenza di due) che non può essere ulteriormente espanso. Un implicante primo essenziale è quello che copre in modo univoco almeno un mintermine e deve essere incluso in ogni espressione minima.

Come funziona l'algoritmo di Quine-McCluskey?

Quine-McCluskey è l'equivalente tabellare di una K-map, adatto a molte variabili. Elenca tutti i mintermini in binario, li raggruppa per numero di 1 e combina iterativamente le coppie che differiscono per esattamente un bit. I termini che non possono essere ulteriormente combinati sono implicanti primi. Una tabella degli implicanti primi seleziona quindi la copertura minima.

Quante variabili supporta questo risolutore K-map?

Questo strumento supporta da 2 a 5 variabili. Una K-map a 5 variabili è visualizzata come due mappe 4×4 adiacenti (una per A=0, una per A=1). Oltre le 5 variabili, le K-map diventano poco pratiche; si consiglia di utilizzare i passaggi di Quine-McCluskey per funzioni più grandi.

Ulteriori Letture

• Mappa di Karnaugh — Wikipedia
• Algoritmo di Quine-McCluskey — Wikipedia
• Metodo di Petrick — Wikipedia