Forma normal canônica

Na álgebra Booleana, qualquer função Booleana pode ser colocada na forma normal canônica disjuntiva (do inglês, CDNF) ou na forma canônica de mintermos e a sua dupla forma normal canônica conjuntiva (do inglês,  CCNF) ou forma canônica de maxtermos. Outras formas canônicas incluem a soma completa dos implicantes primos ou Forma canônica de Blake (e seu dual), e a forma normal algébrica (também chamada de forma normal de Zhegalkin ou forma normal de Reed–Muller).

Mintermos são chamados de produtos, pois eles são a conjunção lógica de um conjunto de variáveis, e maxtermos são chamados de somas, porque eles são a disjunção lógica de um conjunto de variáveis. Estes conceitos estão conectados por causa de sua relação de simetria expressa pelas leis de De Morgan.

A forma canônica de qualquer função Booleana pode ser expressa de duas maneiras: como uma "soma de mintermos" ou um "produto de maxtermos". O termo "Soma de Produtos" ou "SdP" é amplamente utilizado para a forma canônica que é composta por uma disjunção (OU) de mintermos. Seu "dual" de De Morgan é o "Produto de Somas" ou "PdS" para a forma canônica que é uma conjunção (E) de maxtermos. Essas formas podem ser úteis para a simplificação dessas funções, que são de grande importância na otimização de fórmulas Booleanas em geral e, principalmente, circuitos digitais.

## Resumo

[editar | editar código-fonte]

Uma aplicação da álgebra Booleana é no desenho de circuitos digitais. O objetivo pode ser o de minimizar o número de portas, para minimizar o tempo de assentamento, etc.

Há dezesseis possíveis funções de duas variáveis, mas, na lógica digital de hardware, os mais simples circuitos de portas implementam apenas quatro delas: conjunção (E), disjunção (OU inclusivo), e os respectivos complementos (NAND e NOR).

A maioria dos circuitos lógicos aceitam mais de 2 variáveis de entrada; por exemplo, o computador de bordo espacial Apollo Guidance Computer, que foi pioneiro na aplicação de circuitos integrados na década de 60, foi construído com apenas um tipo de porta, a de 3 entradas NOR, cuja saída é verdadeira somente quando todas as 3 entradas são falsas.[1]

## Mintermos

[editar | editar código-fonte]

Para uma função booleana de  n {\displaystyle n} variáveis  x 1 , … , x n {\textstyle {\displaystyle {x_{1},\dots ,x_{n}}}} , um produto de termos em que cada uma das  n {\displaystyle n} variáveis aparece uma vez (em sua forma complementar ou não-complementar) é chamado de mintermo. Assim, um mintermo é uma expressão lógica de n variáveis que emprega apenas o operador de complemento e o de conjunção.

Por exemplo,  a b c {\displaystyle abc} ,  a b ′ c {\displaystyle ab'c} e  a b c ′ {\displaystyle abc'} são 3 exemplos dos 8 mintermos para uma função Booleana de três variáveis  a {\displaystyle a} ,  b {\displaystyle b} e  c {\displaystyle c} . A leitura costumeira deste último é: a E b E NÃO-c.

Há 2n mintermos de n variáveis, uma vez que uma variável num mintermo pode estar na sua forma direta ou em sua forma complementar—duas escolhas por variável.

### Indexação de mintermos

[editar | editar código-fonte]

Mintermos muitas vezes são contados por uma codificação binária padrão, onde as variáveis são escritas geralmente em ordem alfabética. Esta convenção atribui o valor 1 para a forma direta ( x i {\displaystyle x_{i}} ) e 0 para as formas complementares ( x i ′ {\displaystyle x'_{i}} ); o mintermo é  ∑ i = 1 n 2 i value ⁡ ( x i ) {\displaystyle {\displaystyle \sum \limits _{i=1}^{n}2^{i}\operatorname {value} (x_{i})}} . Por exemplo, o mintermo a b c ′ {\displaystyle abc'} é associado a 1102 = 610 e denotado  m 6 {\displaystyle m_{6}} .

### Equivalência funcional

[editar | editar código-fonte]

Um dado mintermo n dá um valor verdadeiro (por exemplo, 1) por apenas uma combinação das variáveis de entrada. Por exemplo, mintermo 5, a b' c, é verdadeiro somente quando a e c são ambos verdadeiros e b é falso—a entrada do arranjo, onde a = 1, b = 0 e c = 1, resulta em 1.

Dada a tabela verdade de uma função lógica, é possível escrever a função como uma "soma de produtos". Esta é uma forma especial da forma normal disjuntiva. Por exemplo, se dada a tabela-verdade para a soma aritmética de bits u, que faz parte de um circuito somador, como função de x e y a partir da própria adição e do "carry in", ci:

ci  | x  | y  | u(ci,x,y)

|
|
|

0  | 0  | 0  | 0
0  | 0  | 1  | 1
0  | 1  | 0  | 1
0  | 1  | 1  | 0
1  | 0  | 0  | 1
1  | 0  | 1  | 0
1  | 1  | 0  | 0
1  | 1  | 1  | 1

Observando que as linhas que têm uma saída em 1 são as 2º, 3º, 5º e 8º, podemos escrever u como uma soma de mintermos  m 1 , m 2 , m 4 , {\displaystyle m_{1},m_{2},m_{4},} e  m 7 {\displaystyle m_{7}} . Se quisermos verificar isso:  u ( c i , x , y ) = m 1 + m 2 + m 4 + m 7 = ( c i ′ , x ′ , y ) + ( c i ′ , x , y ′ ) + ( c i , x ′ , y ′ ) + ( c i , x , y ) {\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}=(ci',x',y)+(ci',x,y')+(ci,x',y')+(ci,x,y)} avaliado por todas as 8 combinações de três variáveis, que vai coincidir com a tabela.

## Maxtermos

[editar | editar código-fonte]

Para uma função booleana de  n {\displaystyle n} variáveis  x 1 , … , x n {\textstyle {\displaystyle {x_{1},\dots ,x_{n}}}} {\displaystyle } , uma soma de termos em que cada uma das  n {\displaystyle n} variáveis aparece uma vez (em sua forma complementar ou não-complementar) é chamado um maxtermo. Assim, um maxtermo é uma expressão lógica de n variáveis que emprega apenas os operadores de complemento e o de disjunção. Maxtermos são um dual à ideia do mintermo (por exemplo, exibindo uma simetria complementar em todos os aspectos). Em vez de usar os operadores AND e complementos, usamos OR e complementos e procedemos da mesma forma.

Por exemplo, a seguir estão dois dos oito maxtermos de três variáveis:

a \+ b' \+ c
a' \+ b \+ c

Há 2n maxtermos de n variáveis, uma vez que uma variável na expressão de maxtermos pode ser em sua forma direta ou em sua forma complementar—duas escolhas por variável.

### Indexação maxtermos

[editar | editar código-fonte]

A cada maxtermo é atribuído um índice com base no oposto  ao convencional utilizado para mintermos. A conversão para maxtermos atribui o valor 0 para a forma direta  ( x i ) {\displaystyle {\displaystyle (x_{i})}} e 1 para formas complementares ( x i ′ ) {\displaystyle {\displaystyle (x'_{i})}} . Por exemplo, podemos atribuir o índice de 6 o maxtermo a ′ + b ′ + c {\displaystyle {\displaystyle a'+b'+c}} (110) e denotamo-lo como M6. Da mesma forma M0 de três variáveis é  a + b + c {\displaystyle {\displaystyle a+b+c}} (000) e M7 é  a ′ + b ′ + c ′ {\displaystyle {\displaystyle a'+b'+c'}} (111).

### Equivalência funcional

[editar | editar código-fonte]

É evidente que o maxtermo n dá um valor falso (i.é., 0) para apenas uma combinação das variáveis de entrada. Por exemplo, o maxtermo 5, a' \+ b \+ c', é falsa somente quando a e c são ambos verdadeiros e b é falso—a entrada do arranjo, onde a = 1, b = 0 e c = 1, resulta em 0.

Se é dada uma tabela verdade de uma função lógica, é possível escrever a função como um "produto de somas". Esta é uma forma especial da forma normal conjuntiva. Por exemplo, se a tabela dada for a de um bit de "carry-out" co que faz parte de um circuito somador, como função de x e y da adição e do "carry in", ci:

ci  | x  | y  | co(ci,x,y)

|
|
|

0  | 0  | 0  | 0
0  | 0  | 1  | 0
0  | 1  | 0  | 0
0  | 1  | 1  | 1
1  | 0  | 0  | 0
1  | 0  | 1  | 1
1  | 1  | 0  | 1
1  | 1  | 1  | 1

Observando-se que as linhas que têm uma saída de 0 são 1º, 2º, 3º e 5º, podemos escrever o co como um produto de maxtermos  M 0 , M 1 , M 2 {\displaystyle {\displaystyle M_{0},M_{1},M_{2}}} e  M 4 {\displaystyle {\displaystyle M_{4}}} . Se quisermos verificar isso: co(ci, x, y) =  M 0 M 1 M 2 M 4 {\displaystyle {\displaystyle M_{0}M_{1}M_{2}M_{4}}} = (ci + x + y) (ci + x + y') (ci + x' + y) (ci' + x + y) avaliado por todas as 8 combinações de três variáveis, que vai coincidir com a tabela.

## Dualização

[editar | editar código-fonte]

O complemento de um mintermo é o respectivo maxtermo. Isso pode ser facilmente verificado usando a lei de De Morgan. Por exemplo:  M 5 = a ′ + b + c ′ = ( a b ′ c ) ′ = m 5 ′ {\displaystyle M_{5}=a'+b+c'=(ab'c)'=m_{5}'}

## Formas não-canônicas de PdS e SdP

[editar | editar código-fonte]

É frequente o caso em que a forma canônica do mintermo pode ser simplificado para uma equivalente em SdP. Esta forma simplificada consiste de uma soma de termos de produtos. No entanto, na forma simplificada, é possível que existam um menor número de termos de produto e/ou produtos de termos que contém menos variáveis. Por exemplo, a seguinte função de 3 variáveis:

a  | b  | c  | f(a,b,c)

|
|
|

0  | 0  | 0  | 0
0  | 0  | 1  | 0
0  | 1  | 0  | 0
0  | 1  | 1  | 1
1  | 0  | 0  | 0
1  | 0  | 1  | 0
1  | 1  | 0  | 0
1  | 1  | 1  | 1

tem a representação do mintermo canônico:  f = a ′ b c + a b c {\displaystyle {\displaystyle f=a'bc+abc}} , mas este tem um equivalente em forma simplificada: f = b c {\displaystyle {\displaystyle f=bc}} . Neste exemplo trivial, é óbvio que  b c = a ′ b c + a b c {\displaystyle {\displaystyle bc=a'bc+abc}} , mas a forma simplificada apresenta tanto uma quantidade menor de termos, quanto de variáveis no total. A representação mais simplificada em SdP de uma função é chamada de forma mínima de SdP.

De forma semelhante, uma forma canônica de maxtermos pode ter uma forma em PdS mais simplificada.

Embora esse exemplo tenha facilmente simplificado após a aplicação de métodos algébricos normais, [ f = ( a ′ + a ) b c {\displaystyle {\displaystyle f=(a'+a)bc}} ], em casos menos óbvios, um método conveniente para encontrar a forma mínima em PdS/SdP de uma função com até quatro variáveis é usar um mapa de Karnaugh.

As formas mínimas de PdS e SdP são muito importantes para encontrar ideal implementações de funções booleanas e de minimização de circuitos lógicos.

## Exemplo de aplicação

[editar | editar código-fonte]

Os exemplos de tabelas-verdade para mintermos e maxtermos acima são suficientes para estabelecer a forma canônica para um único bit de posição na adição de números binários, mas não são suficientes para o projeto de uma lógica digital, a menos que seu inventário de portas incluir as AND e OR. Onde o desempenho é um problema (como na Apollo Guidance Computer), as peças são mais propensas a serem compostas por NAND e NOR devido à ação inerente de complementação na lógica de transistores. Os valores são definidos como estados de tensão, um perto do "terra" e outro perto da tensão de alimentação DC Vcc, i.e. +5 VDC. Se a maior tensão é definida como 1 para valor "true", uma porta NOR é o mais simples e útil elemento da lógica possível.

Especificamente, uma porta NOR de 3 entradas pode consistir de 3 transistores bipolares de junção com os seus emissores todos em "terra" e seus cobradores amarrados juntos e ligados a Vcc através de uma impedância de carga. Cada base é ligada a um sinal de entrada, e o ponto de coletor comum apresenta o sinal de saída. Qualquer entrada que tem um 1 (alta tensão) para a sua base comprime os transistores do emissor para o seu coletor, fazendo com que um fluxo de corrente passe através da impedância de carga, o que traz a tensão do coletor (saída) muito perto do "terra". O resultado disto independe das outras entradas. Somente quando todos os 3 sinais de entrada forem 0 (baixa tensão) o emissor-coletor de impedâncias de todos os 3 transistores permanecem elevados. Em seguida uma corrente muito pequena flui, e o divisor de tensão trabalhando com a impedância de carga impõe ao coletor um ponto de alta tensão (1), muito perto de Vcc.

A propriedade complementar destas portas pode parecer uma desvantagem quando tentamos implementar a uma função na forma canônica, mas há um bônus que compensa: a porta com apenas um sinal de entrada implementa a função complementar, o qual é com freqüência na lógica de circuitos.

Este exemplo assume que o estoque de peças da Apollo era constituído de portas NOR de 3 entradas apenas, mas a discussão é simplificada ao supormos que portas NOR com 4 entradas também estavam disponíveis (na Apollo, estes eram compostos de pares de portas NOR de 3 entradas).

### Consequências canônicas e não-canônicas de portas NOR

[editar | editar código-fonte]

Fato #1: um conjunto de 8 portas NOR, se as suas entradas são todas as combinações das formas diretas e complementares de 3 variáveis de entrada do ci, x, e y, sempre produzem mintermos, nunca maxtermos—isto é, das 8 portas necessárias para processar todas as combinações de 3 variáveis de entrada, apenas uma tem o valor de saída 1. Isso porque uma porta NOR, apesar do seu nome, poderia ser melhor visualizado (usando a lei de De Morgan) como um E dos complementos de seus sinais de entrada.

Fato #2: o motivo do Fato #1 não ser um problema é a dualidade de mintermos e maxtermos, i.e. cada maxtermo é o complemento do respectivo mintermo, e vice-versa.

No mintermo do exemplo acima, escrevemos u ( c i , x , y ) = m 1 + m 2 + m 4 + m 7 {\displaystyle u(ci,x,y)=m_{1}+m_{2}+m_{4}+m_{7}} mas, para realizar isso com porta NOR de 4 entradas, precisamos reafirmar-lo como um produto de somas (PdS), onde as somas são os maxtermos opostos. Que é,

u ( c i , x , y ) {\displaystyle u(ci,x,y)} = AND( M 0 , M 3 , M 5 , M 6 {\displaystyle M_{0},M_{3},M_{5},M_{6}} ) = NOR( m 0 , m 3 , m 5 , m 6 {\displaystyle m_{0},m_{3},m_{5},m_{6}} ). Tabelas de verdade:

ci  | x  | y  | M0 | M3 | M5 | M6 | AND  | u(ci,x,y)

|
|
|
|
|
|
|
|

0  | 0  | 0  | 0  | 1  | 1  | 1  | 0  | 0
0  | 0  | 1  | 1  | 1  | 1  | 1  | 1  | 1
0  | 1  | 0  | 1  | 1  | 1  | 1  | 1  | 1
0  | 1  | 1  | 1  | 0  | 1  | 1  | 0  | 0
1  | 0  | 0  | 1  | 1  | 1  | 1  | 1  | 1
1  | 0  | 1  | 1  | 1  | 0  | 1  | 0  | 0
1  | 1  | 0  | 1  | 1  | 1  | 0  | 0  | 0
1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1
ci  | x  | y  | m0 | m3 | m5 | m6 | NOR  | u(ci,x,y)

|
|
|
|
|
|
|
|

0  | 0  | 0  | 1  | 0  | 0  | 0  | 0  | 0
0  | 0  | 1  | 0  | 0  | 0  | 0  | 1  | 1
0  | 1  | 0  | 0  | 0  | 0  | 0  | 1  | 1
0  | 1  | 1  | 0  | 1  | 0  | 0  | 0  | 0
1  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 1
1  | 0  | 1  | 0  | 0  | 1  | 0  | 0  | 0
1  | 1  | 0  | 0  | 0  | 0  | 1  | 0  | 0
1  | 1  | 1  | 0  | 0  | 0  | 0  | 1  | 1

No maxtermo exemplificado acima, escrevemos c o ( c i , x , y ) = M 0 M 1 M 2 M 4 {\displaystyle {\displaystyle co(ci,x,y)=M_{0}M_{1}M_{2}M_{4}}} mas para realizar isso com porta NOR de 4 entradas nós precisamos observar a igualdade para o NOR dos mesmos mintermos. Que é,

c o ( c i , x , y ) {\displaystyle co(ci,x,y)} = AND( M 0 , M 1 , M 2 , M 4 {\displaystyle M_{0},M_{1},M_{2},M_{4}} ) = NOR( m 0 , m 1 , m 2 , m 4 {\displaystyle m_{0},m_{1},m_{2},m_{4}} ). Tabelas verdade:

ci  | x  | y  | M0 | M1 | M2 | M4 | AND  | co(ci,x,y)

|
|
|
|
|
|
|
|

0  | 0  | 0  | 0  | 1  | 1  | 1  | 0  | 0
0  | 0  | 1  | 1  | 0  | 1  | 1  | 0  | 0
0  | 1  | 0  | 1  | 1  | 0  | 1  | 0  | 0
0  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1
1  | 0  | 0  | 1  | 1  | 1  | 0  | 0  | 0
1  | 0  | 1  | 1  | 1  | 1  | 1  | 1  | 1
1  | 1  | 0  | 1  | 1  | 1  | 1  | 1  | 1
1  | 1  | 1  | 1  | 1  | 1  | 1  | 1  | 1
ci  | x  | y  | m0 | m1 | m2 | m4 | NOR  | co(ci,x,y)

|
|
|
|
|
|
|
|

0  | 0  | 0  | 1  | 0  | 0  | 0  | 0  | 0
0  | 0  | 1  | 0  | 1  | 0  | 0  | 0  | 0
0  | 1  | 0  | 0  | 0  | 1  | 0  | 0  | 0
0  | 1  | 1  | 0  | 0  | 0  | 0  | 1  | 1
1  | 0  | 0  | 0  | 0  | 0  | 1  | 0  | 0
1  | 0  | 1  | 0  | 0  | 0  | 0  | 1  | 1
1  | 1  | 0  | 0  | 0  | 0  | 0  | 1  | 1
1  | 1  | 1  | 0  | 0  | 0  | 0  | 1  | 1

### Projetos de trade-offs considerados em complemento às formas canônicas

[editar | editar código-fonte]

Pode-se supor que o trabalho de projetar um somador está concluída, mas ainda não abordamos o fato de que as 3 variáveis de entrada têm que aparecer em sua forma direta ou complementar. Não há nenhuma dificuldade sobre adicionar x e y até o momento, porque eles são estáticos durante a adição e, portanto, são normalmente utilizados em circuitos que têm casualmente saídas tanto em forma direta, quanto na complementar. (O mais simples circuito "Latch" feito de portas NOR é um par de portas cruzadas com um objetivo de fazer um flip-flop: a saída de cada um é ligada por fio como uma das entradas dos outros). Também não há necessidade de se criar a forma complementar da soma u. No entanto, o "carry out" de uma posição de bit deve ser passado como o carry para o bit da posição seguinte em ambas as formas (direta e complementar). A maneira mais simples para fazer isto é passar co através de uma porta NOR de 1 entrada e com nome de saída co', mas isto adicionaria uma porta de atraso no pior lugar possível, diminuindo a ondulação de todos os outros carry's da direita para a esquerda. Uma porta NOR adicional de 4 entradas formando a forma canônica de co' (o oposto mintermos como co) resolve este problema.

c o ′ ( c i , x , y ) {\displaystyle co'(ci,x,y)} = AND( M 3 , M 5 , M 6 , M 7 {\displaystyle M_{3},M_{5},M_{6},M_{7}} ) = NOR( m 3 , m 5 , m 6 , m 7 {\displaystyle m_{3},m_{5},m_{6},m_{7}} ).

Tabelas-verdade:

ci  | x  | y  | M3 | M5 | M6 | M7 | And  | co'(ci,x,y)

|
|
|
|
|
|
|
|

0  | 0  | 0  | 1  | 1  | 1  | 1  | 1  | 1
0  | 0  | 1  | 1  | 1  | 1  | 1  | 1  | 1
0  | 1  | 0  | 1  | 1  | 1  | 1  | 1  | 1
0  | 1  | 1  | 0  | 1  | 1  | 1  | 0  | 0
1  | 0  | 0  | 1  | 1  | 1  | 1  | 1  | 1
1  | 0  | 1  | 1  | 0  | 1  | 1  | 0  | 0
1  | 1  | 0  | 1  | 1  | 0  | 1  | 0  | 0
1  | 1  | 1  | 1  | 1  | 1  | 0  | 0  | 0
ci  | x  | y  | m3 | m5 | m6 | m7 | NOR  | co'(ci,x,y)

|
|
|
|
|
|
|
|

0  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 1
0  | 0  | 1  | 0  | 0  | 0  | 0  | 1  | 1
0  | 1  | 0  | 0  | 0  | 0  | 0  | 1  | 1
0  | 1  | 1  | 1  | 0  | 0  | 0  | 0  | 0
1  | 0  | 0  | 0  | 0  | 0  | 0  | 1  | 1
1  | 0  | 1  | 0  | 1  | 0  | 0  | 0  | 0
1  | 1  | 0  | 0  | 0  | 1  | 0  | 0  | 0
1  | 1  | 1  | 0  | 0  | 0  | 1  | 0  | 0

O trade-off para manter a velocidade máxima desta forma inclui um custo inesperado (além de ter que usar uma porta maior). Se tivéssemos usado apenas aquela porta de 1 entrada para complementar co, não teria havido nenhum uso para o mintermo  {\displaystyle } e a porta que o gerou poderia ter sido eliminada. Mesmo assim, é ainda um bom negócio.

Contundo nós poderíamos ter implementado as funções exatamente de acordo com suas formas canônicas SdP e PdS , transformando portas NOR para as funções especificadas. Uma porta NOR é usada  para fazer uma OR passando a sua saída através de uma porta de 1 entrada NOR; e é usada para fazer uma AND passando por cada uma de suas entradas através de uma NOR de 1 entrada. No entanto, esta abordagem não só aumenta o número de portas usadas, mas também dobra o número de atrasos de processamento de sinais, cortando a velocidade de processamento na metade. Consequentemente, sempre que o desempenho é vital, ir além das formas canônicas e se utilizar de porta NOR é um trabalho que vale a pena.

### Planejamento top-down vs. bottom-up

[editar | editar código-fonte]

Temos visto até agora como as ferramentas de mintermo/maxtermo podem ser usadas para criar um somador de estágio na forma canônica com a adição de um pouco de álgebra Booleana, custando apenas 2 porta atrasos para cada uma das saídas. Essa é a maneira "top-down"(de cima para baixo) de se construir um circuito digital para esta função, mas é o melhor caminho? A discussão centrou-se em identificar o "mais rápido" como "melhor", e a forma canônica aumentada atende a esse critério de maneira impecável, mas, às vezes, outros fatores predominam. O designer pode ter um objetivo principal de minimizar o número de portas, e/ou minimizar as divisões de sinais para as outras portas, já que grandes divisões reduzem a resiliência da degradação da fonte de alimentação, entre outros fatores ambientais. Em tal caso, o designer deve desenvolver a forma canônica de planejamento como base, e, em seguida, tentar um desenvolvimento "bottom-up"(de baixo para cima), e, finalmente, comparar os resultados.

O desenvolvimento bottom-up envolve perceber que u = ci XOR (x XOR y), onde XOR significa OU exclusivo [true quando uma entrada é verdade, mas não quando ambas são verdadeiras], e que co = ci x + x y + y ci. Um tal desenvolvimento leva doze portas NOR: seis de 2 entradas e duas de 1 entrada para produzir u em 5 atrasos de portas, além de três de 2 entradas e um de 3 entradas para produzir co' em 2 portas de atraso. A linha canônica de base levou oito portas NOR de 3 entradas, além de três de 4 entradas para produzir u, co e co' em 2 portas de atraso. Se o circuito de inventário, na verdade, inclui portas de 4 entradas NOR, o projeto top-down canônico parece um vencedor nos quesitos quantidade de portas e velocidade. Mas se (ao contrário de nossa suposição conveniente) os circuitos são, na verdade, de 3 entradas em portas NOR, das quais duas são necessárias para cada função NOR de  4 entradas, então, o projeto canônico tem 14 portas em comparação a 12 para a abordagem bottom-up, mas ainda produz a soma de dígitos u consideravelmente mais rápido. O fan-out de comparação é tabulado com:

Variáveis  | De cima para baixo  | De baixo para cima

|
|

x  | 4  | 1
x'  | 4  | 3
y  | 4  | 1
y'  | 4  | 3
ci  | 4  | 1
ci'  | 4  | 3
M ou m  | 4@1,4@2  | N/A
x XOR y  | N/A  | 2
Diversos  | N/A  | 5@1
Max.  | 4  | 3

Qual a melhor opção a se fazer? Um atento terá notado que a descrição do desenvolvimento bottom-up menciona co' como uma saída, mas não co. Será que o projeto simplesmente nunca precisará da forma direta do "carry out"? Bem, sim e não. Em cada fase, o cálculo de co' só depende de ci', x' e y', o que significa que a propagação de ondas de "carry" ao longo das posições dos bits é tão rápido como no projeto canônico sem nunca produzir a saída co. O cálculo de u, o que requer ci a ser feita a partir de ci' por uma NOR de 1 entrada, é mais lento, mas, para qualquer comprimento de palavra, o projeto paga a penalidade apenas uma vez (quando o bit mais à esquerda da soma é desenvolvido). Isso porque os cálculos se sobrepõem, onde cada um se amontoa em seu próprio "encanamento" sem afetar sobre o momento quando a próxima posição do bit da soma de bits pode ser calculado. E, com certeza, o co' do bit mais à esquerda provavelmente terá de ser complementado como parte da lógica de determinar se a adição gerou um "overflow" ou não. Mas usando portas NOR de 3 entradas,o projeto bottom-up é quase tão rápido para fazer adição paralela em um comprimento de palavra não-trivial, reduz a contagem de portas, e usa menores fanouts ... então ele ganha se a contagem de portas e/ou fanout são fundamentais!

Vamos deixar o circuito exato do projeto bottom-up no qual todas estas afirmações são verdadeiras, como um exercício para o leitor interessado, assistido por mais uma fórmula algébrica u = ci(x XOR y) + ci'(x XOR y)']'. Dissociar a propagação do carry na formação da soma desta forma é o que eleva o desempenho de um carry "precoupado com o futuro", quando comparado ao carry ondulatório adder.

Para ver como as portas lógicas NOR foram utilizadas na Apollo Guidance Computer's ALU, visite: http://klabs.org/history/ech/agc_schematics/index.htm, selecione qualquer um dos MÓDULOS 4 BITS de entradas no Índice e expanda as imagens como desejar.

## Veja também

[editar | editar código-fonte]

* Algébricas forma normal
* Forma canônica
* Forma canônica Blake
* Lista de álgebra Booleana

## Rodapé

[editar | editar código-fonte]

1. ↑ Hall, Eldon C. (1996). Journey to the Moon: The History of the Apollo Guidance Computer. [S.l.]: AIAA. ISBN 1-56347-185-X

## Referências

[editar | editar código-fonte]

* Bender, Edward A.; Williamson, S. Gill (2005). A Short Course in Discrete Mathematics. Mineola, NY: Dover Publications, Inc: Dover Publication. ISBN 0-486-43946-1
* McCluskey, E. J. (1965). Introduction to the Theory of Switching Circuits. NY: McGraw: Hill Book Company. 78 páginas. LCCN 65-17394
* Hill, Fredrick J.; Peterson, Gerald R. (1974). Introduction to Switching Theory and Logical Design (2nd ed.). NY: John Wiley & Sons. 101 páginas. ISBN 0-471-39882-9

## Ligações externas

[editar | editar código-fonte]

* Boole, George. «"The Calculus of Logic"». Cambridge and Dublin Mathematical Journal. III: 183—198