Álgebra booleana, transformações equivalentes e custo de implementação

Expressões equivalentes coincidem para todas as entradas

Simplificar um circuito combinacional não é apenas encurtar a expressão. Preservando a função, considere estágios lógicos, fan-in, fan-out e células disponíveis. Primeiro interprete $+$ e o produto da álgebra booleana^{iÁlgebra booleana Álgebra de 0, 1 e das operações AND, OR e NOT. O sinal de soma costuma representar OR, portanto suas regras diferem das da soma de inteiros.} como OR e AND.

A segunda identidade pode ser verificada por casos: com $A=1$, ambos os lados valem 1; com $A=0$, ambos valem $B$. Você deve conseguir explicar uma identidade mesmo depois de aplicá-la de memória.

Leia estruturas NAND e NOR com De Morgan

Por exemplo, $Y=AB+AC=A(B+C)$. A primeira forma usa duas AND e uma OR; a segunda, uma OR e uma AND. Porém, diferenças na carga ou na chegada das entradas podem fazer a opção com menos portas não ser a mais rápida.

O teorema do consenso também é útil:

Se $BC=1$, com $A=0$ o termo $\overline A C$ já vale 1; com $A=1$, o termo $AB$ já vale 1. Portanto, $BC$ é redundante para a função estável. Eliminá-lo pode mudar os riscos de pulsos espúrios durante as transições, como veremos ao estudar atrasos.

Cada coluna abaixo representa uma combinação ABC, não a passagem do tempo. Confira que as duas saídas coincidem em todas elas: embora portas e caminhos sejam diferentes, a função para entradas 0/1 estáveis é a mesma.

Critério de verificação de equivalência

Chame de y_ref e y_opt as versões anterior e posterior e compare todas as entradas quando o espaço for pequeno. Passar em um ou dois exemplos não demonstra equivalência.

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

mismatch deve permanecer em 0 nas oito combinações 0/1. A simulação de quatro estados com X/Z e a equivalência sequencial exigem condições adicionais. Declarar o alcance exato do que foi demonstrado é uma base da revisão de projeto.