Como um computador soma números? Clique aqui e entenda! [CIRCUITOS DIGITAIS]
Fala, pessoal, tudo bem? Hoje, como o próprio título já diz, vamos aprender a somar dois números.
Vamos usar o esse-lentíssimo javascript para isto.
Primeiro vamos criar uma variável para armazenar um número inteiro: var num1 = 1
Agora, vamos criar uma segunda variável nos mesmos moldes: var num2 = 2
Por último, vamos aplicar o operador + do javascript, cuja a função é somar:
console.log(num1 + num2)
output: 3
E voilà, é assim que o computador soma dois números.
Obrigado a todos que leram - é nessa hora que começaria a tocar "curb your enthusiasm" se isso não fosse um texto.
Brincadeiras à parte, este conteúdo objetiva introduzir de maneira clara e simples o incrível mundo dos hardwares, quero fazer vocês experimentarem o delicioso gosto do silício, do bare metal, e desmitificar um pouco o que o que rege os processadores, pelo menos da unidade de lógica e aritmética (ULA).
Um processador é em essência algo extremamente simples, e justamente por ser tão simples, ele se torna complexo. Da mesma forma que na própria matemática, usando apenas três regras extremamente simples, conseguimos sair de simples processos de contagem para a criação da teoria do cálculo, o mesmo se aplica a processadores: usando apenas princípios extremamente simples, conseguimos fazer um Intel 14900K, por exemplo. Claro que não vamos desenvolver um processador aqui, nós vamos nos ater a construir um circuito simples de soma, o que já será o suficiente para entender o que está por trás de como os processadores operam.
Pois bem, vamos começar fundamentando alguns conceitos importantes:
Depois vamos para a construção do circuito propriamente dito, e de bônus, criaremos um circuito subtrator.
Não será abordado aqui circuitos sequenciais, registradores, máquinas de turing, como o processador sabe qual instrução deve executar, unidade de controle, cache, etc. O foco aqui é explicar uma das instruções mais importantes que o processador pode executar, que é a instrução de soma, porém abstraída em um circuito combinacional e de fácil compreensão. Não será explicado circuitos de soma mais complexos, como o carry look-ahead.
Números Binários
Números binários sempre é um assunto difícil de tratar com pessoas que nunca tiveram um contato com outras bases além da decimal, pois apesar do raciocínio de construção ser o mesmo para todas as bases, sair da usual pode ser um pouco confuso no começo, mas não desanime se não entender de cara.
Aprendendo a contar
Vamos começar primeiro destrinchando a base 10, que é a base do nosso dia-a-dia.
Pelo fato do ser humano ter dez dedos, criamos 10 símbolos para representar cada número natural menor que o número 10, isto é, começamos no número que dá início ao conjunto dos números naturais, o zero - há controvérsias, mas por convenção vamos assumir que zero é o primeiro - e criamos um símbolo para ele, o símbolo '0'
0 = '0'
depois fomos para o seu sucessor e criamos um símbolo para ele, o símbolo '1'
s(0) = '1'
depois fomos para o sucessor do sucessor de 0 e criamos o símbolo '2'
s(s(0)) = '2'
depois fomos para o sucessor do sucessor do sucessor de 0:
s(s(s(0))) = '3'
e repetimos esse processo até um total de 10 vezes. O décimo símbolo é o '9'.
Esses símbolos recebem o nome de “algarismos”.
Mas sabemos que existem números acima de 9, os números são infinitos. Então como fazemos para contar até números maiores ou iguais a 10? Nós começamos pelas unidades e contamos até os algarismos se esgotarem, e quando se esgotam, reiniciamos a contagem no dígito e incrementamos o próximo dígito à esquerda. Se o dígito à esquerda também estiver sem algarismos disponíveis, nós reiniciamos ele também e propagamos o incremento. Fazemos este processo até encontrar um dígito diferente de '9'.
Este processo se trata de um algoritmo recursivo:
contar_ao_inf(dígito)
{
Se os algarismos se esgotaram
{
troque algarismo do dígito para o algarismo '0',
contar_ao_inf(dígito à esquerda)
}
troque algarismo do dígito pelo o algarismo que o sucede,
contar_ao_inf(digito das unidades)
}
contar_ao_inf(dígito das unidades iniciado com o algarismo '0')
Vamos executar o algoritmo:
Começamos no dígito das unidades com o algarismo '0'
⟶
Os algarismos se esgotaram? Não. Troque o algarismo '0' pelo algarismo '1' e vá para o dígito das unidades
⟶ 1...9 ⟶
Os algarismos se esgotaram? Sim. Troque '9' por '0' e vá para o dígito à esquerda
| posição do dígito atual | algarismo atual | número depois da troca de algarismo |
|---|---|---|
| 0 (unidades) | 0 | 1 |
| ... | ... | 2...8 |
| 0 | 8 | 9 |
| 0 | 9 | 0 |
| 1 (dezenas) | 0_ | 10 |
| 0 | 0 | 11 |
| ... | ... | 12...99 |
| 0 | 9 | 90 |
| 1 | 9_ | 00 |
| 2 (centenas) | 0__ | 100 |
| ... | ... | ... |
Note que o dígito das unidades é atualizado a cada contagem. O das dezenas é atualizado a cada 10 contagens. O das centenas a cada 100, dos milhares a cada 1000, e por aí vai. Podemos generalizar esse padrão da seguinte forma:
Em uma contagem onde os dígitos envolvidos são d_n...d_2d_1d_0,
um dígito qualquer d_k (0 \lt k \leq n), terá uma taxa de atualização 10 vezes menor que o dígito que estiver imediatamente à sua direita, isto é, d_{k-1}.
Agora que sistematizamos o processo de contagem, vamos aplicar o mesmo algoritmo, porém ao invés de usarmos 10 algarismos (base decimal), vamos usar apenas 2 algarismos, 0 e 1 (base binária).
| posição do dígito atual | algarismo atual | número depois da troca de algarismo |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0_ | 10 |
| 0 | 0 | 11 |
| 0 | 1 | 10 |
| 1 | 1_ | 00 |
| 2 | 0__ | 100 |
| 0 | 0 | 101 |
| 0 | 1 | 100 |
| 1 | 0_ | 110 |
| 0 | 0 | 111 |
| 0 | 1 | 110 |
| 1 | 1_ | 100 |
| 2 | 1__ | 000 |
| 3 | 0___ | 1000 |
| ... | ... | ... |
Em resumo, se o dígito for '0', ainda temos algarismos disponíveis que o sucedem, então trocamos ele pelo seu sucessor, o algarismo '1'. Se o dígito for '1', esgotamos os algarismos, e então reiniciamos o dígito para '0' e pulamos para o dígito à esquerda. Nós vamos caminhando para à esquerda até encontrar um dígito com algarismo '0', e ao encontrar, trocamos ele por '1' (seu sucessor), e voltamos para o primeiro dígito. Enquanto não encontramos um dígito '0', devemos reiniciar todos os dígitos no caminho, já que todos eles serão '1'.
Convertendo de decimal para binário e vice-versa
Reparem que podemos "quebrar" um número na base 10 em uma soma de outros números naturais menores do que 10 multiplicados por uma potência de 10.
Exemplo:
7913 = 7000 + 900 + 10 + 3
7913 = 7\cdot1000 + 9\cdot100 + 1\cdot10 + 3\cdot1
7913 = 7\cdot10^3 + 9\cdot10^2 + 1\cdot10^1 + 3\cdot10^0
E se "quebrassemos" um número também representado na base 10, seguindo os mesmos moldes acima, porém ao invés de usarmos potências de 10 para ponderar os dígitos, nós usássemos potências de outras base, como por exemplo, a base 2? Se fizermos isso, nós conseguimos converter um número em base decimal para binário.
Exemplo:
13 = 6\cdot2 + 1
6 = 3\cdot2, então
13 = (3\cdot2)\cdot2 + 1
3 = 1\cdot2 + 1, então
13 = ((1\cdot2 + 1)\cdot2)\cdot2 + 1
13 = 1\cdot2^3 + 1\cdot2^2 + 1
13 = 1\cdot2^3 + 1\cdot2^2 + 0\cdot2^1 + 1\cdot2^0
Logo 13_{10} = 1101_2 (os números subscritos ao lado indicam a base)
Para convertermos de binário para decimal, basta seguirmos o caminho contrário ao que acabamos de fazer.
dígito 0 contém algarismo '1', dígito 1 contém algarismo '0', dígito 2 contém algarismo '1', dígito 3 contém algarismo '1'. Sendo assim:
1101_2 = 1\cdot2^0 + 0\cdot2^1 + 1\cdot2^2 + 1\cdot2^3
1101_2 = 1\cdot1 + 0\cdot2 + 1\cdot4 + 1\cdot8
1101_2 = 8 + 4 + 0 + 1
1101_2 = 13_{10}
Aprendendo a somar dois números em binário
Primeiro vamos fazer um pequeno ensaio de como números na base 10 são somados:
Para somarmos 59 mais 78, podemos fazer o seguinte procedimento:
59 = 5\cdot10^1 + 9\cdot10^0
78 = 7\cdot10^1 + 8\cdot10^0
59 + 78 = 5\cdot10^1 + 9\cdot10^0 + 7\cdot10^1 + 8\cdot10^0
59 + 78 = (5 + 7)\cdot10^1 + (9 + 8)\cdot10^0
59 + 78 = (12)\cdot10^1 + (17)\cdot10^0
De fato o resultado acima está correto, porém lembre-se que os números ponderados pelas potências de 10 precisam ser menores que 10. Então
59 + 78 = (10 + 2)\cdot10^1 + (10 + 7)\cdot10^0
59 + 78 = 10\cdot10^1 + 2\cdot10^1 + 10\cdot10^0 + 7\cdot10^0
59 + 78 = (0 + 1)\cdot10^2 + 2\cdot10^1 + 1\cdot10^1 + 7\cdot10^0
59 + 78 = 1\cdot10^2 + (2 + 1)\cdot10^1 + 7\cdot10^0
59 + 78 = 1\cdot10^2 + 3\cdot10^1 + 7\cdot10^0
Logo, 59 + 78 = 137
Quando fazemos uma conta na mão, o procedimento "vai 1" acontece justamente quando a soma de dois dígitos de mesma posição excede o valor representado pelo maior algarismo disponível. Na base 10, o maior algarismo representa o número 9, já na base 2, o maior algarismo representa o número 1. Olhando para as contas acima, conseguimos perceber isso.
Vamos agora somar 11 mais 39 em binário para fixar os conceitos.
11_{10} = 1011_2
39_{10} = 100111_2
Sendo assim
| valor | 2⁵ | 2⁴ | 2³ | 2² | 2¹ | 2⁰ |
|---|---|---|---|---|---|---|
| Vai 1? | 0 | 1 | 1 | 1 | 1 | 0 |
| 11 | 0 | 0 | 1 | 0 | 1 | 1 |
| + 39 | 1 | 0 | 0 | 1 | 1 | 1 |
| = 50 | 1 | 1 | 0 | 0 | 1 | 0 |
De fato, 50_{10} = 2^1 + 2^4 + 2^5 = 2 + 16 + 32
Portas Lógicas
i. Conjunção (AND)
Se a proposição P for verdadeira (V) e a proposição Q for verdadeira, então a proposição P and Q é verdadeira.
Se P for V e Q for falso (F), P and Q é falso.
Se P for F e Q for V, P and Q é F.
Se P for F e Q for F, P and Q é F.
Na álgebra booleana
- uma proposição é verdadeira ⇔ a proposição vale 1
- uma proposição é falsa ⇔ a proposição vale 0
Já que as proposições têm seu valor lógico associado a números, podemos aplicar operações matemáticas sobre elas. Sendo assim, podemos representar P and Q como uma multiplicação de P e Q:
| P | Q | PQ |
|---|---|---|
| 0 | 0 | 0 = 0•0 |
| 0 | 1 | 0 = 0•1 |
| 1 | 0 | 0 = 1•0 |
| 1 | 1 | 1 = 1•1 |
Como podemos conferir, de fato P and Q só é V - isto é, vale 1 - quando P e Q valem 1 simultaneamente.
Note que as entradas da tabela-verdade estão em uma sequência de 0 a 3 em binário:
na 1º linha, 00_2 = 0_{10},
na 2º linha, 01_2 = 1_{10},
na 3º linha, 10_{2} = 2_{10},
na 4º linha, 11_{2} = 3_{10}
Note também que aquele padrão das unidades se atualizarem a cada contagem, das dezenas a cada 10, das centenas a cada 100..., acontece também de forma parecida nos números binários, com a diferença de que ao invés da taxa de atualização do dígito à esquerda diminuir de 10 em 10 vezes, ela diminui de 2 em 2 vezes. Podemos usar isso para construir de forma mecanizada tabelas-verdade com linhas enumeradas.
O diagrama da porta lógica AND é a seguinte:
**Creio que não será necessário detalhar os próximos conceitos, suponho que a maioria esmagadora dos leitores já estejam familiarizados com eles.
ii. Disjunção (OR)
Na álgebra booleana, podemos representar P or Q como uma soma de P e Q:
| P | Q | P + Q |
|---|---|---|
| 0 | 0 | 0 = 0+0 |
| 0 | 1 | 1 = 0+1 |
| 1 | 0 | 1 = 1+0 |
| 1 | 1 | 1 = 1+1 |
Atentai-vos para a última linha da tabela-verdade. Na álgebra "normal", 1 + 1 obviamente é igual a 2. Entretanto, como só existem dois valores lógicos, V e F, e na álgebra booleana temos o axioma de que uma proposição é verdadeira ⇔ a proposição vale 1, podemos chegar a conclusão de que uma proposição nunca pode assumir um valor maior que 1.
O diagrama da porta lógica OR é o seguinte:
iii. Negação (NOT)
Negar uma proposição significa inverter seu valor lógico, isto é, se P vale 0, NOT P vale 1, e vice-versa.
| P | !P |
|---|---|
| 0 | 1 |
| 1 | 0 |
O diagrama da porta lógica NOT é o seguinte:
Tendo em mente somente essas três portas lógicas apresentadas, podemos criar qualquer circuito digital que a nossa inventividade e imaginação permitirem, tais como circuitos para somar, subtrair, multiplicar, comparar se um número é maior que outro, enfim, literalmente uma infinidade de possibilidades.
Vou apresentar só mais uma porta que será de grande utilidade para nós futuramente: a Exclusive OR.
iv. Disjunção Exclusiva (XOR)
O operador que simboliza um ou exclusivo é um símbolo de soma circunscrito em um círculo ( ⊕ ).
E como o nome sugere, somente uma entrada deve ser verdadeira, se as duas forem simultaneamente verdadeiras ou falsas, a saída será falsa.
| P | Q | P⊕Q | minterms |
| --- | --- | --- | | --- |
| 0 | 0 | 0 = 0⊕0 | - |
| 0 | 1 | 1 = 0⊕1 | Q•!P |
| 1 | 0 | 1 = 1⊕0 | P•!Q |
| 1 | 1 | 0 = 1⊕1 | - |
Como dito anteriormente, qualquer porta lógica pode ser escrita em função das três vistas já vistas, então vamos colocar P⊕Q em função delas usando minterms:
P⊕Q = P!Q + Q!P
Fica como exercício fazer a tabela-verdade para esta expressão acima. Você vai conferir que de fato ela será exatamente igual à tabela verdade acima.
**Não se preocupe com os minterms, não vou explicar essa parte, mas que fique plantada a semente da curiosidade.
O diagrama da porta lógica XOR é o seguinte:
Uma propriedade do XOR que será importante no futuro é a seguinte:
P⊕0 = P
P⊕1 = !P
Isto pode ser observado na tabela-verdade.
Prova:
P⊕Q = P!Q + Q!P
sem perda de generalidade:
- Se Q = 0: P⊕0 = P!0 + 0!P = P•1 + 0 = P
- Se Q = 1: P⊕1 = P!1 + 1!P = P•0 + 1•!P = !P
Desenvolvendo um somador simples (*carry-ripple*)
Vamos analisar como funciona a soma de dois dígitos binários, isto é, a soma de dois bits.
Se ambos os bits valerem 0, a soma vale 0.
Se o primeiro bit valer 0 e o segundo valer 1, a soma vale 1.
Se o primeiro bit valer 1 e o segundo valer 0, a soma vale 1.
Se ambos os bits valerem 1, vai 1 para o próximo bit à esquerda e a soma vale 0.
**Caso tenha dúvidas nessa parte, você pode voltar para o tópico Aprendendo a somar dois números em binário
Dispondo estas informações em uma tabela-verdade, temos o seguinte:
| A | B | soma |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Você nota alguma semelhança com alguma tabela-verdade que já vimos anteriormente? Esta é exatamente a mesma tabela-verdade da função lógica XOR.
Portando para somarmos dois bits, basta passarmos ambos por uma porta XOR, e a saída será a soma.
Porém nosso trabalho ainda não acabou, ainda precisamos nos debruçar sobre o "vai 1".
A única situação onde precisamos carregar 1 para somar com a soma dos próximos bits à esquerda, é quando ambos os dois bits somados valem 1. Caso contrário, carregamos o valor 0.
Dispondo estas informações na tabela-verdade abaixo, conseguimos notar que se trata de uma função lógica AND.
| A | B | carrega |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Isto significa que usando uma porta lógica AND, nós conseguimos determinar se vai 1 ou não.
Usando então uma porta AND e uma porta XOR, nós conseguimos montar o circuito abaixo, que é capaz tanto de somar dois bits quanto de determinar qual valor deve ser carregado para a próxima soma de dois bits, caso haja.
A e B são entradas do circuito, isto é, os bits a serem somados. S é a saída que informa o resultado da soma de dois bits. E Co (Carry output) é a saída que informa o "vai 1".
Este circuito é chamado "half-adder", ou "meio-somador" em português. E é justamente "meio" porque só conseguimos somar dois bits, ele não considera a existência de uma soma de bits anterior, que poderia gerar um "vai 1".
Para considerarmos o carregamento de 1 para o próximo bit à esquerda, devemos criar um circuito "full-ader", ou "somador-completo".
Um somador-completo deve ter de entrada os bits a serem somados e o carregamento da soma anterior. E de saída teremos a soma dos três bits de entrada, obviamente, e ele também deverá informar o valor excedente para a próxima soma. Se não exceder, Co vale 0, e se exceder, Co vale 1.
Vamos construí-lo de forma intuitiva, pois se fossemos construí-lo analisando a tabela-verdade, precisaríamos de um conhecimento além do explicado aqui, como minterms, propriedades de funções lógicas e mapas de Karnaugh. Entretanto, fica a sugestão para pesquisar esses temas por conta própria.
Bom, a principal diferença de um meio-somador para um somador-completo, é que o meio-somador soma apenas dois bits, já o somador completo precisa considerar o Carry input (Ci). Então nós podemos fazer o seguinte:
- Somamos o bit do primeiro número com o bit do segundo número: A + B
- Depois somamos A + B com o excedente vindo da soma dos bits anteriores: (A + B) + Ci
Como se trata de duas somas de dois bits, no qual na segunda soma nós usamos como variável o resultado da primeira, concorda que podemos usar dois meio-somadores interligados, onde a entrada do primeiro meio-somador é A e B, e a entrada do segundo é a saída S do primeiro (A + B) e Ci?
O resultado da soma dos três bits já conseguimos resolver, mas e o "vai 1"?
O "vai 1" acontece caso o primeiro meio-somador OU o segundo meio-somador exceda sua capacidade de armazenamento. Então para resolvermos esse problema, basta ligar a saída "Co" de ambos meio-somadores a uma porta lógica OR, assim quando um dos dois acusar o "vai 1", ele será propagado por uma porta Co no somador-completo.
Passando para diagrama de circuito tudo o que discutimos, o somador-completo ficará assim:
A, B e Ci são as entradas a serem somadas. HA significa "half-adder". S é a saída que informa o resultado da soma de três bits. E Co é a saída que informa o "vai 1".
Ao testarmos o circuito acima com as 8 possibilidades de entrada, chegaremos na seguinte tabela-verdade:
| Ci | A | B | S | Co | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 1 | 0 | |
| 0 | 1 | 0 | 1 | 0 | |
| 0 | 1 | 1 | 0 | 1 | |
| 1 | 0 | 0 | 1 | 0 | |
| 1 | 0 | 1 | 0 | 1 | |
| 1 | 1 | 0 | 0 | 1 | |
| 1 | 1 | 1 | 1 | 1 |
Muito bem, agora que já temos um circuito somador-completo, somos capazes de somar de fato um número em binário com outro número em binário. Basta interligá-los em cascata, ligando a saída Co de um com a e entrada Ci do próximo circuito.
A quantidade de ligações dependerá do número de bits dos números a serem somados. Por exemplo, para somarmos números inteiros positivos normais, precisaríamos de 1 half-adder no começo e 31 full-adder's após, já que hoje em dia um número inteiro é geralmente armazenado em um espaço de 32 bits. No nosso caso, vamos considerar números de apenas 4 bits.
Montando então o circuito em cascata e usando ele para somar 9 + 3, temos o seguinte:
CONTINUAÇÃO NOS COMENTÁRIOS
