Algebra booleana, equivalenza e costo d’implementazione

Espressioni equivalenti producono la stessa uscita per ogni ingresso

Semplificare un circuito combinatorio non significa soltanto accorciare una formula. Occorre mantenere la funzione considerando livelli logici, fan-in, fan-out e celle realmente disponibili. Leggiamo anzitutto $+$ e moltiplicazione dell'algebra booleana^{iAlgebra booleana Algebra di 0,1, AND, OR e NOT. Il simbolo più indica normalmente OR e segue regole diverse dall’addizione intera.} come OR e AND.

La seconda identità si verifica per casi: con $A=1$ entrambi i membri valgono 1; con $A=0$ valgono entrambi $B$. Anche dopo aver applicato un'identità memorizzata bisogna saperne spiegare il significato.

Leggere strutture NAND e NOR con De Morgan

Per esempio, $Y=AB+AC$ equivale ad $A(B+C)$. La prima forma si disegna con due AND e una OR, la seconda con una OR e una AND. Tuttavia, con tempi d'arrivo o carichi diversi, la soluzione con meno porte non è sempre più veloce.

È utile anche il teorema del consenso:

Quando $BC=1$, se $A=0$ è già 1 il termine $\overline A C$, mentre se $A=1$ è già 1 $AB$. Quindi $BC$ è ridondante per la funzione a regime. Eliminarlo può però modificare gli hazard durante le transizioni; vedremo questa differenza nella lezione sui ritardi.

Ogni colonna rappresenta una combinazione ABC, non il trascorrere del tempo. Controllate che le due uscite coincidano in tutte le colonne. Numero di porte e cammini possono differire, ma la funzione per ingressi 0/1 stabili è uguale.

Criterio per verificare l'equivalenza

Chiamate y_ref e y_opt le versioni prima e dopo la trasformazione e, per spazi d'ingresso piccoli, confrontate tutte le combinazioni. Uno o due casi verificati con successo non bastano a concludere l'equivalenza.

assign y_ref = (a & b) | (a & c);
assign y_opt = a & (b | c);
assign mismatch = y_ref ^ y_opt;

In tutte le otto combinazioni 0/1, mismatch deve essere sempre 0. Una simulazione a quattro stati con X/Z o l'equivalenza di circuiti sequenziali richiede condizioni aggiuntive. Dichiarare l'ambito effettivamente dimostrato è fondamentale nella revisione del progetto.