QMC - Command-line tool per la semplificazione logica

Antonio Bonifati <antonio.bonifati@libero.it>

Introduzione

In questo articolo presenterò un programma a riga di comando per effettuare la sintesi ottima di reti combinatorie col metodo algoritmico di Quine-McCluskey.

Un programma di questo tipo è di interesse per il progettista di circuiti, ma anche per il programmatore interessato ad ottimizzare la compilazione o l'interpretazione di espressioni booleane, anche se le espressioni logiche molto complicate (con un elevato numero di variabili ed operatori logici) non sono (per fortuna!) molto comuni nell'attività quotidiana di programmazione.

Il programma si chiama QMC ed è distribuito sotto licenza GPL dal sito qmc.pollaknet.at.

Gli utenti di FreeBSD possono trovarlo comodamente sul primo cd-rom di FreeBSD come pacchetto binario in packages/misc/qmc-*.tgz o compilarlo tramite la collezione delle Port in /usr/ports/misc/qmc.

Richiamo delle funzioni logiche principali

Verrà indicato in grassetto tutto quello che deve essere digitato dall'utente.

Per ottenere un breve riassunto dell'uso del comando qmc usate l'opzione --help o -h come al solito:

bash$ qmc --help
Usage: qmc [OPTION]
Simplification tool by using the Quine - McClusky process.

  -g, --gettable       get boolean table
  -G  --gethtmltable   get boolean table as HTML output
  -h, --help           display this help and exit
  -p, --prompt         prompt for equation
  -s, --source EQU     set one side of the equation
  -t, --table          set boolean table
  -v, --verbose        print progress
      --version        output version information and exit

Please report bugs to <thomas@pollaknet.at>.

È un fatto notevole che nell'algebra della logica, o di Boole, in onore di George Boole (1815-1864), tutte le infinite funzioni logiche che si possono definire possono essere costruite a partire solamente da poche funzioni logiche o operatori di base. Questi si dice che costituiscono un insieme funzionalmente completo di operatori. Un insieme di questo tipo è quello formato dai seguenti operatori logici elementari:

bash$ qmc -g -s /a
| a | Q |
+---+---+
| 0 | 1 |
| 1 | 0 |
Result: Q=/a

bash$ qmc -g -s a+b
| a | b | Q |
+---+---+---+
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
Result: Q=a+b

bash$ qmc -g -s 'a*b'
| a | b | Q |
+---+---+---+
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
Result: Q=ab

Come forse sapete si tratta rispettivamente dei seguenti operatori:

NOT
negazione o complementazione, indicato in qmc con uno / prefisso
OR
somma (logica) o disgiunzione (inclusiva), indicato in qmc con +
AND
prodotto (logico) o congiunzione, indicato in qmc con *

L'operatore * si può sottointendere in qmc:

bash$ qmc -g -s ab
| a | b | Q |
+---+---+---+
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
Result: Q=ab

Quindi {NOT,AND,OR} costituiscono un insieme funzionalmente completo, anche se non minimo, in quanto anche {NOT,AND} e {NOT,OR} sono funzionalmente completi. Infatti Augustus De Morgan (1806-1871) trovò che è possibile esprimere un OR tramite soli NOT e AND, e un AND tramite soli NOT e OR:

bash$ qmc -s /[a+b]
Result: Q=/a/b

bash$ qmc -s /[ab]
Result: Q=/b+/a

Si noti che in qmc per alterare l'ordine degli operatori si usano le parentesi quadre.

Le proprietà di De Morgan sono analoghe a quelle degli operatori di complemento, unione e intersezione della teoria degli insiemi, per cui in un paragone insiemistico, potremmo dire che:

1a proprietà di De Morgan
Il complemento dell'unione di due insiemi è uguale all'intersezione dei rispettivi complementi.
2a proprietà di De Morgan
Il complemento dell'intersezione di due insiemi è uguale all'unione dei rispettivi complementi.

La dimostrazione di queste è evidente per via grafica tramite i diagrammi di Venn. Non è invece possibile esprimere un NOT tramite una combinazione dei soli operatori AND e OR, per cui {AND,OR} non è un insieme funzionalmente completo.

Invece tutti gli altri operatori logici o funzioni fondamentali di due variabili logiche possono essere espressi, in vari modi, in termini di operatori dell'insieme {NOT,AND,OR}. Eccoli elencati di seguito, ciascuno con un esempio di realizzazione:

il NOR
bash$ qmc -g -s /a/b
| a | b | Q |
+---+---+---+
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 0 |
Result: Q=/a/b
il NAND
bash$ qmc -g -s /b+/a
| b | a | Q |
+---+---+---+
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
Result: Q=/a+/b
lo XOR, detto anche disgiunzione esclusiva o OR esclusivo
bash$ qmc -g -s a/b+/ab
| a | b | Q |
+---+---+---+
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
Result: Q=a/b+/ab
l'identità logica
bash$ qmc -g -s /a/b+ab
| a | b | Q |
+---+---+---+
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
Result: Q=/a/b+ab
l'implicazione logica
bash$ qmc -g -s /a+b
| a | b | Q |
+---+---+---+
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
Result: Q=/a+b

Sintesi ottima di reti a due livelli

Progettiamo un confrontatore: cioè un circuito, parte di una ALU, che ha in ingresso due numeri n1, n2 di n bit e produce una uscita pari al valore logico della proposizione n1>=n2. Per semplicità fissiamo n=2.

È piuttosto semplice compilare interattivamente una tabella che definisca per enumerazione la funzione logica Q del confrontatore che vogliamo realizzare e nel contempo passarla a qmc per la minimizzazione.

Questa tabella ha 24=16 righe, corrispondenti alle altrettante possibili combinazioni delle 4 variabili d'ingresso a,b,c,d, per chiarezza ordinate da qmc a partire da quella di tutti zero fino a quella di tutti uno e nel compilarla supponiamo inoltre che n1=ab, n2=cd (giustapposizione di bit, non and-logico):

bash$ qmc -t

how much variables are needed? 4
| A | B | C | D | Q |
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 1
| 1 | 0 | 0 | 0 | 1
| 0 | 1 | 0 | 0 | 1
| 1 | 1 | 0 | 0 | 1
| 0 | 0 | 1 | 0 | 0
| 1 | 0 | 1 | 0 | 1
| 0 | 1 | 1 | 0 | 0
| 1 | 1 | 1 | 0 | 1
| 0 | 0 | 0 | 1 | 0
| 1 | 0 | 0 | 1 | 1
| 0 | 1 | 0 | 1 | 1
| 1 | 1 | 0 | 1 | 1
| 0 | 0 | 1 | 1 | 0
| 1 | 0 | 1 | 1 | 0
| 0 | 1 | 1 | 1 | 0
| 1 | 1 | 1 | 1 | 1
Result: Q=/C/D+A/D+A/C+B/C+AB

La minimizzazione è relativa al numero di blocchi logici del tipo AND e OR necessari per realizzare un circuito che abbia cablata la logica della funzione booleana Q. A parità di questo numero viene anche minimizzato il numero totale dei morsetti di ingresso di tali blocchi.

In generale esistono vari tipi di forme minime. Attualmente qmc genera solo forme minime di tipo SP, ovvero formate da somme di prodotti logici, come ad esempio il risultato precedente per un comparatore di numeri di 2 bit:

Q=/C/D+A/D+A/C+B/C+AB

Si contano facilmente i requisiti hardware:

I NOT non vengono computati in quanto si suppone di poter uno strato di negatori condiviso anche tra più circuiti.

La forma PS (prodotti di somme logiche) minima è riportata di seguito tramite un comando che verifica l'equivalenza tra le due forme:

bash$ qmc -s [A+/C][A+B+/D][B+/C+/D]
Result: Q=/C/D+A/D+A/C+/CB+AB

La forma PS minima richiede:

Una mappa di Karnaugh che risolve il problema è questa:

AB/CD 00 01 11 10
00 1 0 0 0
10 1 1 0 1
11 1 1 1 1
01 1 1 0 0

e questi sono gli implicanti primi tutti essenziali per la copertura della funzione:

/C/D
AB/CD 00 01 11 10
00 1 0 0 0
10 1 1 0 1
11 1 1 1 1
01 1 1 0 0
A/D
AB/CD 00 01 11 10
00 1 0 0 0
10 1 1 0 1
11 1 1 1 1
01 1 1 0 0
A/C
AB/CD 00 01 11 10
00 1 0 0 0
10 1 1 0 1
11 1 1 1 1
01 1 1 0 0
B/C
AB/CD 00 01 11 10
00 1 0 0 0
10 1 1 0 1
11 1 1 1 1
01 1 1 0 0
AB
AB/CD 00 01 11 10
00 1 0 0 0
10 1 1 0 1
11 1 1 1 1
01 1 1 0 0

Analogamente potete ricavare espressioni SP minime per i confrontatori di 3,4,... bit.

qmc può essere utilizzato anche per ottenere in formato HTML pubblicabile sul web le tavole di verità a partire dalle espressioni logiche algebriche:

bash$ qmc -G -s /C/D+A/D+A/C+B/C+AB >comparatore.html

Ci sono alcuni casi di funzioni logiche importanti nella pratica ma in cui purtroppo non è possibile effettuare alcuna semplificazione o solo un modesto guadagno rispetto alla forma SP o PS canonica ottenuta direttamente dalla tabella. Per esempio consideriamo la progettazione di un circuito per la generazione del bit di parità di n bit. Per fissare le idee supponiamo n=4, ma le conclusioni a cui giungeremo valgono per qualsiasi n. Il bit di parità, per definizione, deve valere 1 per quelle configurazioni di bit di ingresso che hanno un numero dispari di 1, e 0 per tutte le altre (cioè per tutte e sole quelle che hanno un numero pari di 0). Aggiungendo il bit di parità alla configurazione di 4 bit, si ottengono sempre delle configurazioni di 5 bit in cui il numero di 1 è pari (per questo il bit aggiunto viene chiamato così).

Se la configurazione viene trasmessa tramite una linea di comunicazione, e se si verificano alterazioni dei segnali che comportano l'alterazione di un solo bit, per cui il numero totale di 1 risulta dispari all'atto della ricezione, il ricevente può rilevare l'errore. Tuttavia, con un solo bit di ridondanza quale il bit di parità, il ricevente non può rilevare errori che comportano la complementazione di due bit differenti rispetto al codice originale corretto e nemmeno può correggere questi errori autonomamente: l'unico modo per tentare la correzione è richiedere la trasmissione al generatore del segnale.

bash$ qmc -t

how much variables are needed? 4
| A | B | C | D | Q |
+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0
| 1 | 0 | 0 | 0 | 1
| 0 | 1 | 0 | 0 | 1
| 1 | 1 | 0 | 0 | 0
| 0 | 0 | 1 | 0 | 1
| 1 | 0 | 1 | 0 | 0
| 0 | 1 | 1 | 0 | 0
| 1 | 1 | 1 | 0 | 1
| 0 | 0 | 0 | 1 | 1
| 1 | 0 | 0 | 1 | 0
| 0 | 1 | 0 | 1 | 0
| 1 | 1 | 0 | 1 | 1
| 0 | 0 | 1 | 1 | 0
| 1 | 0 | 1 | 1 | 1
| 0 | 1 | 1 | 1 | 1
| 1 | 1 | 1 | 1 | 0
Result: Q=A/B/C/D+/AB/C/D+/A/BC/D+ABC/D+/A/B/CD+AB/CD+A/BCD+/ABCD

Si noti che ogni riga ha un numero di 1 pari o nullo. Una possibile mappa di Karnaugh per questa funzione logica a 4 variabili è la seguente:

AB/CD 00 01 11 10
00 0 1 0 1
10 1 0 1 0
11 0 1 0 1
01 1 0 1 0

Si nota che la mappa ha la forma di una scacchiera. Gli implicanti primi (corrispondenti agli 1) sono tutti essenziali e sono di dimensione 1, così come gli implicati (corrispondenti agli zero), e rappresentano dunque rispettivamente i mintermini e i maxtermini. La forma minima coincide proprio con quella PS o PS e non sono possibili ulteriori semplificazioni.

La situazione è analoga per 5 variabili o qualsiasi altro numero di variabili:

bash$ qmc -t

how much variables are needed? 5
| A | B | C | D | E | Q |
+---+---+---+---+---+---+
| 0 | 0 | 0 | 0 | 0 | 0
| 1 | 0 | 0 | 0 | 0 | 1
| 0 | 1 | 0 | 0 | 0 | 1
| 1 | 1 | 0 | 0 | 0 | 0
| 0 | 0 | 1 | 0 | 0 | 1
| 1 | 0 | 1 | 0 | 0 | 0
| 0 | 1 | 1 | 0 | 0 | 0
| 1 | 1 | 1 | 0 | 0 | 1
| 0 | 0 | 0 | 1 | 0 | 1
| 1 | 0 | 0 | 1 | 0 | 0
| 0 | 1 | 0 | 1 | 0 | 0
| 1 | 1 | 0 | 1 | 0 | 1
| 0 | 0 | 1 | 1 | 0 | 0
| 1 | 0 | 1 | 1 | 0 | 1
| 0 | 1 | 1 | 1 | 0 | 1
| 1 | 1 | 1 | 1 | 0 | 0
| 0 | 0 | 0 | 0 | 1 | 1
| 1 | 0 | 0 | 0 | 1 | 0
| 0 | 1 | 0 | 0 | 1 | 0
| 1 | 1 | 0 | 0 | 1 | 1
| 0 | 0 | 1 | 0 | 1 | 0
| 1 | 0 | 1 | 0 | 1 | 1
| 0 | 1 | 1 | 0 | 1 | 1
| 1 | 1 | 1 | 0 | 1 | 0
| 0 | 0 | 0 | 1 | 1 | 0
| 1 | 0 | 0 | 1 | 1 | 1
| 0 | 1 | 0 | 1 | 1 | 1
| 1 | 1 | 0 | 1 | 1 | 0
| 0 | 0 | 1 | 1 | 1 | 1
| 1 | 0 | 1 | 1 | 1 | 0
| 0 | 1 | 1 | 1 | 1 | 0
| 1 | 1 | 1 | 1 | 1 | 1
Result: Q=A/B/C/D/E+/AB/C/D/E+/A/BC/D/E+ABC/D/E+/A/B/CD/E+AB/CD/E+A/BCD/E+
/ABCD/E+/A/B/C/DE+AB/C/DE+A/BC/DE+/ABC/DE+A/B/CDE+/AB/CDE+/A/BCDE+ABCDE