Eduardo Pereira Ribeiro Alves

Introdução

No post anterior, finalmente conseguimos montar nossa primeira pequena máquina de somar. Combinando duas operações lógicas que já conhecíamos, o XOR e o E, conseguimos criar o nosso primeiro half-adder, uma pequena máquina capaz de somar dois bits e ainda descobrir quando acontecia aquele famoso “vai um”, o nosso carry.

Se você ainda não viu os posts anteriores, recomendo começar por eles. Primeiro falamos sobre binário e operações lógicas e depois colocamos esses conceitos em prática para criar o nosso half-adder. Mas ficou uma coisa pendente.

Lembra que eu falei que o half-adder ainda não era suficiente? Pois é. Hoje vamos resolver esse problema e finalmente montar uma máquina capaz de fazer a soma completa de dois bits. Vamos criar o nosso full-adder.

O problema do nosso half-adder

Antes de continuar, vamos relembrar o que o nosso half-adder fazia.

Ele recebia dois valores:

A e B

E produzia dois resultados:

Soma e Carry

A tabela era essa:

Até aqui tudo muito bonito.

Quando colocamos 1 + 1, o resultado é:

10

Ou seja, temos:

• 0 na casa atual;
• 1 que precisa ir para a próxima casa.

Esse 1 é o nosso carry. O problema é que existe uma coisa que o nosso half-adder não sabe fazer. Ele não sabe receber um carry que veio de uma soma anterior. E isso é um problema enorme.

O famoso “vai um”

Vamos voltar um pouco para a matemática que aprendemos na escola.Imagine a seguinte soma:

Vamos começar pela direita.

Temos:

1 + 1 = 10

Então colocamos 0 na primeira casa e mandamos 1 para a próxima.

Só que agora precisamos fazer:

1 + 0 + 1

Perceba que agora temos três valores envolvidos.

Temos o primeiro 1, o segundo 0 e também aquele 1 que veio da soma anterior.

É justamente aqui que o nosso half-adder começa a ficar limitado. Ele sabe fazer:

A + B

Mas precisamos fazer:

A + B + Carry

Esse carry que veio da soma anterior recebe um nome específico: carry-in.

E é justamente ele que vai transformar nosso half-adder em algo mais completo.

Conhecendo o carry-in

Vamos chamar nossos três valores de:

• A: primeiro bit;
• B: segundo bit;
• C-in: carry que veio da soma anterior.

O C-in significa Carry In, ou seja, o carry que está entrando.

Agora nossa máquina precisa receber três entradas:

E produzir duas saídas:

O Carry Out, ou simplesmente C-out, é o carry que vai sair dessa operação e ser enviado para a próxima casa. Agora sim estamos começando a falar de uma máquina de somar de verdade.

Vamos montar a tabela

Como temos três entradas e cada uma pode ser 0 ou 1, temos oito possibilidades.

Vamos colocar tudo na tabela:

Vamos pegar alguns casos para entender.

Caso 1: 0 + 0 + 0

Não temos nada para somar.

Resultado:

0

Então:

Soma = 0
C-out = 0

Nada de muito interessante aqui.

Caso 2: 0 + 1 + 0

Temos:

0 + 1 = 1

Então:

E finalmente fazemos um OU entre os dois resultados.

Soma = 1
C-out = 0

Também já conhecemos esse caso.

Caso 3: 1 + 1 + 0

Aqui temos o nosso velho conhecido:

1 + 1 = 10

Portanto:

Soma = 0
C-out = 1

Isso também já sabemos fazer com o half-adder.

Mas agora vem a parte interessante.

Caso 4: 1 + 1 + 1

Agora temos:

1 + 1 + 1 = 11

Ou seja:

Soma = 1
C-out = 1

Esse é justamente o caso que o nosso half-adder sozinho não consegue resolver.

Precisamos de uma máquina um pouco mais esperta.

Descobrindo um padrão

Mas espera aí, se você acompanhou os posts anteriores, já deve estar pensando:

“Eduardo, não dá para transformar essa tabela em operações lógicas também?”

É claro que dá. Vamos começar pela soma.

Quando fazemos:

A + B

já descobrimos que podemos utilizar um XOR.

Então:

A XOR B

produz a primeira parte da nossa soma.

Só que ainda temos o C-in.

Precisamos pegar o resultado desse XOR e somar novamente com o C-in.

Então:

(A XOR B) XOR Cin

Pronto.

Essa é a nossa expressão para a saída de soma:

Soma = A XOR B XOR Cin

Perceba que não inventamos nenhuma operação nova.

Estamos apenas reutilizando aquilo que já aprendemos.

E o Carry?

Agora precisamos descobrir quando o C-out deve ser 1.

Vamos olhar novamente para a nossa tabela:

Perceba uma coisa interessante.

O carry acontece quando:

• A e B são 1;
• ou quando C-in é 1 e o resultado de A XOR B também é 1.

Isso pode ser escrito assim:

Cout = (A E B) OR (C-in E (A XOR B))

Olha só que legal.

Estamos novamente usando apenas as operações que já conhecemos:

• XOR;
• E;
• OU.

Nada de magia.

Mas precisamos mesmo montar tudo isso?

Agora vem a parte que eu acho mais interessante.

Se você olhar para a expressão:

Soma = A XOR B XOR C-in

vai perceber que podemos simplesmente fazer um XOR de A com B.

Depois pegamos o resultado e fazemos outro XOR com C–in.

Ou seja:

A ─────┐
       XOR ─────┐
B ─────┘        │
                XOR ─────> Soma
Cin ────────────┘

Temos nossa soma.

E podemos fazer algo parecido com o carry.

Primeiro descobrimos se:

A E B

é verdadeiro.

Depois verificamos:

(A XOR B) E C-in

Visualmente:

A ─────┐
       E   ─────┐
B ─────┘        │
                OU ─────> C-out
A ─────┐        │
       XOR ─┐   │
B ─────┘    E   ┘
            │
Cin ────────┘

Agora sim temos todas as peças necessárias.

O truque: dois half-adders

Mas existe uma maneira ainda mais interessante de enxergar tudo isso.

Lembra do nosso half-adder? Ele já sabe fazer exatamente uma parte dessa operação. Então, ao invés de criar tudo novamente do zero, podemos simplesmente colocar dois half-adders juntos.

O primeiro recebe:

A
B

E produz:

Soma parcial
Carry parcial

Depois pegamos a soma parcial e colocamos junto com o C-in no segundo half-adder.

Fica mais ou menos assim:

Só que agora temos um pequeno problema.

Podemos ter dois carries diferentes:

Carry Parcial
Carry 2

Precisamos juntar esses dois valores.

E aqui entra o nosso velho amigo:

OU.

Se qualquer um dos dois carries for 1, precisamos mandar 1 para a próxima casa.

Então:

Carry 1 ───┐
           OU ─────> C-out
Carry 2 ───┘

Pronto.

Acabamos de montar um full-adder usando dois half-adders e uma porta OU.

Vamos colocar tudo junto

Nosso circuito completo fica aproximadamente assim:

Pode parecer um pouco assustador olhando pela primeira vez, mas perceba que nós já conhecemos todas as peças. Não criamos uma nova operação lógica, apenas pegamos aquilo que já construímos e começamos a conectar as peças.

Vamos testar nosso full-adder

Vamos testar justamente o caso que o half-adder não conseguia resolver:

1 + 1 + 1

O primeiro half-adder recebe:

A = 1
B = 1

Ele produz:

Soma = 0
Carry = 1

Agora o segundo half-adder recebe:

Soma parcial = 0
C-in = 1

Então temos:

0 + 1 = 1

A segunda soma produz:

Soma = 1
Carry = 0

Agora pegamos os dois carries:

Carry 1 = 1
Carry 2 = 0

Passamos pelo OU:

1 OU 0 = 1

Então nosso resultado final é:

Soma = 1
Cout = 1

Ou seja:

1 + 1 + 1 = 11

Funcionou!

E agora?

Agora temos algo muito mais poderoso do que aquele primeiro half-adder.

Temos uma pequena máquina capaz de receber:

A
B
C-in

e devolver:

Soma
C-out

Isso parece uma coisa extremamente simples. E, de fato, é. Mas é justamente essa simplicidade que torna tudo isso tão interessante. Porque agora podemos pegar vários desses pequenos componentes e colocar um atrás do outro.

Por exemplo, podemos ter um full-adder para cada casa de um número binário:

$\begin{array}{rrrrr}  & & 1 & 1 & \\ 0 & 0 & 1 & 0 & 1 \\ + \quad 0 & 0 & 0 & 1 & 1 \\ \hline 0 & 1 & 0 & 0 & 0 \end{array}$

O carry de uma casa passa para a próxima.

E assim conseguimos somar números cada vez maiores.

Aquela simples operação:

5 + 3

que para nós parece extremamente trivial, começa a ganhar uma nova perspectiva quando percebemos que, lá embaixo, podemos reduzir tudo a pequenos componentes trabalhando com apenas dois valores:

0 e 1.

Transistores. Portas lógicas. Half-adders. Full-adders.

E, quando juntamos muitos deles…

Temos uma máquina capaz de fazer contas.

E essa máquina é o computador.

Conclusão

Nesse post finalmente transformamos nosso half-adder em um full-adder.

Descobrimos que o grande problema do half-adder era não conseguir receber o carry de uma operação anterior. Para resolver isso, adicionamos o nosso Cin e descobrimos que podemos construir um full-adder utilizando dois half-adders e uma porta OR.

No fim das contas, a lógica ficou:

Soma = A XOR B XOR Cin
Cout = (A AND B) OR (Cin AND (A XOR B))

E isso nos permite continuar aumentando a nossa pequena máquina de somar.

No próximo passo, podemos fazer justamente isso: juntar vários full-adders e descobrir como o computador consegue somar números binários maiores do que apenas 1 + 1 + 1.

Afinal, se já conseguimos fazer uma pequena máquina que soma bits…

Por que não fazer uma que soma números inteiros?

Até a próxima!