Circuitos combinacionais: somar, escolher e decodificar com portas

Circuitos combinacionais: somar, escolher e decodificar com portas

Imagine uma fila de pessoas num caixa antigo. Cada uma recebe um bilhete com a soma parcial de quem está atrás, acrescenta o próprio número e passa o resultado adiante, junto com um recado de “passei de dez”. Ninguém consegue responder antes de receber o recado, e a última pessoa da fila só termina quando todas as anteriores terminaram. Um somador de vários bits montado em cadeia funciona exatamente assim, com a diferença de que os “bilhetes” são fios e cada pessoa é um conjunto de portas lógicas. A fila também mostra o que incomoda nesse arranjo: o recado viaja de um lado ao outro, e o tempo de espera cresce com o tamanho da fila. A analogia tem limite claro: as pessoas da fila podem falar ao mesmo tempo e levar um tempo qualquer para pensar, enquanto o circuito tem um atraso fixo por porta.

Esta aula trata desse tipo de circuito, chamado combinacional, e de um conjunto de blocos que aparecem em quase todo processador: somadores, subtratores, comparadores, multiplexadores, decodificadores e a ULA em miniatura. O pré-requisito principal são as portas e as tabelas-verdade de Álgebra booleana e portas lógicas, além de binário, de Bits e binário, e de complemento de dois, que aparece em Inteiros, complemento de dois e overflow. A aula seguinte, que ainda não foi escrita, vai acrescentar memória ao circuito. O ponto de partida é este: enquanto o circuito não tiver memória, a saída depende apenas das entradas do momento.

Mapa da aula

1. O que é um circuito combinacional

Um circuito combinacional é aquele cuja saída depende somente das entradas que estão presentes agora. Se você trocar as entradas por outras e esperar o tempo de propagação, a saída passa a ser a função das novas entradas, e nada do passado influencia o resultado. A lógica de uma porta E ou de um somador de 4 bits são exemplos: dados os mesmos bits de entrada, a saída é sempre a mesma.

O contraste é o circuito sequencial, que tem memória. Um latch ou um flip-flop guarda um bit, de modo que a saída depende também do que foi guardado antes. Essa diferença explica por que um somador não precisa de clock para funcionar, e por que um registrador precisa. A fronteira entre os dois tipos é a memória, e não a complexidade: um somador de 64 bits tem milhares de portas e continua sendo combinacional, porque não guarda nada entre um cálculo e o seguinte.

Vale fixar um detalhe que costuma passar despercebido. Um circuito combinacional não é instantâneo. Cada porta leva um atraso de propagação para refletir uma mudança na entrada, e a saída só fica estável depois que o sinal atravessa o caminho mais longo de portas. Por isso a palavra “combinacional” descreve a função que o circuito calcula, e não a velocidade com que ele a calcula.

2. Para que serve

Um processador faz, na maior parte do tempo, três coisas com números: soma, compara e escolhe qual valor usar. Somar é o que a ULA faz de mais caro. Comparar aparece em cada desvio condicional de um programa. Escolher aparece quando um registrador, um dado da memória ou o resultado de uma operação precisa ser encaminhado para um destino entre vários.

Sem um vocabulário de blocos prontos, cada um desses casos viraria um desenho novo. Com o vocabulário, o projetista monta o somador de 64 bits a partir de um somador de 1 bit repetido, o seletor de registrador a partir de um decodificador, e a ULA a partir de um somador e de um multiplexador. O ganho é o mesmo de qualquer abstração: a peça pequena é verificada uma vez, e a grande herda essa verificação. A aula mostra essa montagem passo a passo, com os números que circulam dentro de uma CPU.

3. Exemplos em contextos diferentes

O primeiro contexto é a calculadora de bolso. Não sabemos, nesta aula, qual circuito uma calculadora comercial usa por dentro, e por isso não afirmamos que ela tenha um somador de 4 bits. O que sabemos é que a mesma lógica de soma com vai-um serve para qualquer tamanho de número, e processadores a usam com 64 bits para somar endereços e valores.

O segundo contexto é o controle de acesso. Um sistema libera uma porta quando o cartão bate com o código, e a comparação de dois números de 4 bits é um caso de comparador de igualdade. Quando os bits são iguais, cada par gera 1, e a porta E final só libera se todos os pares derem 1. Se um único par diferir, o resultado é 0.

O terceiro contexto é o seletor de canais. Um multiplexador escolhe uma entre várias fontes e a encaminha a um único destino, como um painel de câmeras que mostra uma delas na tela. Dentro de um processador, o mesmo princípio pode decidir de onde vem o operando da ULA, por exemplo de um registrador ou de um valor embutido na instrução.

O quarto contexto é o endereçamento de memória. Quando a CPU quer escrever no registrador número 5, ela não envia o número 5 diretamente ao registrador. Ela envia o código 101 a um decodificador, e só a saída de número 5 fica ativa. A figura 07 mostra essa seleção.

4. Como funciona

4.1 Meio somador e somador completo

Começamos pela unidade de soma. Somar dois bits A e B produz dois resultados: um bit de soma S e um bit de vai-um C. A soma é 1 quando A e B são diferentes, e isso é exatamente o XOR. O vai-um é 1 quando A e B são ambos 1, e isso é o E. Essa combinação tem nome: meio somador, em inglês half adder. Ela soma dois bits e não aceita um vai-um de entrada, por isso só serve para o bit menos significativo.

Para o bit seguinte, precisamos somar três bits: A, B e o vai-um que veio do bit anterior, chamado de cin, de carry in. Isso é o somador completo, ou full adder. A forma mais simples é ligar dois meios somadores em sequência e combinar os dois vai-uns com um OU. O primeiro meio soma A com B, o segundo soma o resultado parcial com o cin, e o OU junta os dois vai-uns, porque no máximo um deles pode ser 1 em cada caso. A figura mostra esse arranjo com os valores A = 1, B = 1 e cin = 1.

Siga a figura de cima para baixo. O XOR de cima dá 1 XOR 1, que é 0, e a porta E de baixo dá 1 E 1, que é 1. O segundo XOR recebe o parcial 0 e o vai-um 1, e sai com soma 1. A segunda porta E recebe o mesmo parcial 0 e o vai-um 1, e sai 0. O OU junta o 1 da primeira E com o 0 da segunda e devolve o vai-um de saída 1. O resultado 1 mais 1 mais 1 é 3, que em binário é 11: soma 1 e vai-um 1. As cores dos fios seguem o nível de cada sinal, verde para 1 e cinza para 0, e o ArchFlow calcula essa propagação a partir dos valores de entrada de cada porta.

A figura tem um detalhe de desenho que vale comentar. As entradas A, B e cin não aparecem como fios separados, porque cada porta recebe o nível escrito na própria entrada do diagrama. Isso mantém a figura legível, mas significa que a figura mostra um caso, e não todas as combinações. As oito combinações são conferidas pelo programa da seção 7.

4.2 Somador de n bits em cadeia

Para somar números maiores, empilhamos somadores completos. O vai-um de saída de cada bit alimenta o cin do bit seguinte, e o primeiro bit recebe cin igual a 0. Esse arranjo se chama ripple-carry, algo como vai-um em cascata, porque o vai-um se propaga de bit em bit como uma onda.

Vamos resolver 0111 mais 0001 bit a bit. Como o binário escreve o bit mais à direita como o menos significativo, a conta começa pela direita. No bit 0, somamos 1, 1 e cin 0: dá 10, então a soma é 0 e o vai-um é 1. No bit 1, somamos 1, 0 e o vai-um 1: dá 10 de novo, soma 0 e vai-um 1. No bit 2, somamos 1, 0 e vai-um 1: soma 0 e vai-um 1. No bit 3, somamos 0, 0 e vai-um 1: dá 1, soma 1 e vai-um 0. O resultado lido de cima para baixo é 1000, que é 8. O vai-um saiu do bit 0 e atravessou três somadores até virar o bit 3, e foi o que deu o resultado.

A figura mostra os quatro blocos com os valores de cada bit no título, e os fios de vai-um estão animados e engrossados, porque são o caminho que decide o resultado. Repare que os fios das somas, as saídas s de cada bloco, não aparecem ligados a nada, porque o resultado é lido depois. Os fios de vai-um são os únicos que conectam um bloco ao seguinte.

4.3 Por que o vai-um atrasa tudo

O problema da cadeia é que cada bit só pode fechar a sua soma depois de receber o vai-um do bit anterior. O bit 3 depende do bit 2, que depende do bit 1, que depende do bit 0. Se cada somador demora o tempo de algumas portas, o último bit só fica pronto depois que o sinal atravessou todos os anteriores. Esse caminho de portas que mais demora para estabilizar o resultado é o caminho crítico, e num somador em cadeia ele vai do vai-um do primeiro bit até a saída do último.

Isso tem consequência direta para o projeto. Um somador de 64 bits em cadeia tem um caminho crítico 16 vezes maior que um somador de 4 bits, e como o clock do processador precisa esperar o pior caminho, a frequência cai na mesma proporção. A seção 6 mostra a conta com um modelo de atraso unitário. Antes disso, precisamos de uma forma de pular o caminho da cadeia, e essa forma é o lookahead.

4.4 Carry lookahead: o vai-um calculado de uma vez

O carry lookahead, ou vai-um antecipado, parte de uma observação simples. Para cada bit, o vai-um de saída depende de dois sinais locais, que não precisam esperar o bit anterior. O primeiro é a geração, g = A · B: o bit gera vai-um sozinho quando A e B são 1, não importa o que vem de trás. O segundo é a propagação, p = A ⊕ B: o bit deixa passar um vai-um que chega, quando A e B são diferentes. Com essas duas listas, o vai-um de cada posição é uma expressão fechada: c(i+1) = g(i) OU (p(i) E c(i)).

Essa expressão ainda é uma cadeia, porque c(i) entra nela. A ideia do lookahead é desdobrar a recorrência até que cada vai-um dependa só dos g, dos p e do cin inicial. Para o vai-um c4 de 4 bits, o desdobramento dá c4 = g3 OU (p3 E g2) OU (p3 E p2 E g1) OU (p3 E p2 E p1 E g0) OU (p3 E p2 E p1 E p0 E cin). Todos os termos são produtos de sinais que já existem no começo, e uma árvore de portas E e OU calcula o resultado em poucos níveis, sem esperar o bit anterior.

O mecanismo existe porque a cadeia obriga o sinal a passar por cada bit, e o lookahead permite que o vai-um pule bits inteiros. O custo é área: as expressões crescem com o número de bits, e um lookahead de 64 bits com portas planas seria grande demais. Por isso as implementações reais combinam blocos, com lookahead dentro de grupos de 4 bits e uma segunda camada entre os grupos. Essa é a razão de a figura 03 mostrar só 4 bits.

Vamos resolver 0111 mais 0001 com g e p. O bit 0 tem A = 1 e B = 1, então g0 = 1 e p0 = 0. O bit 1 tem A = 1 e B = 0, então g1 = 0 e p1 = 1. O bit 2 tem A = 1 e B = 0, então g2 = 0 e p2 = 1. O bit 3 tem A = 0 e B = 0, então g3 = 0 e p3 = 0. Com cin = 0, o vai-um de cada posição sai assim: c1 = g0 = 1. O c2 é g1 OU (p1 E g0), que dá 0 OU (1 E 1), ou seja, 1. O c3 é g2 OU (p2 E g1) OU (p2 E p1 E g0), que dá 0 OU 0 OU 1, ou seja, 1. O c4 é 0 pela expressão acima, porque todos os termos valem 0. As somas são então s_i = A ⊕ B ⊕ c_i, e o programa da seção 7 confirma que o resultado é 1000 com vai-um final 0.

A figura separa as duas etapas. Os blocos de cima calculam g e p de cada bit, com os valores escritos no título. O bloco de baixo recebe as oito listas e entrega os quatro vai-uns. Os fios de g e p saem de cada bit e chegam ao bloco de baixo sem passar por nenhum outro bit, o que é a propriedade que dá o nome ao circuito. A figura mostra a forma do circuito, e não o atraso dele. Quanto ele ganha em atraso, a seção 6 explica com o modelo.

4.5 Subtração com complemento de dois

O somador faz também a subtração, sem circuito extra de subtração. A regra vem do complemento de dois, descrito na aula de inteiros: para calcular A menos B em n bits, somamos A com o complemento de B, que é o inverso de cada bit de B, e somamos 1. Em forma de circuito, isso é A + NOT(B) + 1 módulo 2 elevado a n.

O vai-um de saída tem um significado próprio nesse caso. Quando o cin inicial é 1, o somador faz A + NOT(B) + 1, e o vai-um final é 1 exatamente quando A é maior ou igual a B, sem precisar de empréstimo. O programa confere essa afirmação para todos os pares de números de 4 bits.

Para fazer um só circuito servir para soma e subtração, colocamos um XOR antes de cada bit de B, com uma linha de controle SUB. Quando SUB é 0, o XOR deixa B passar como está. Quando SUB é 1, o XOR inverte B, e a linha SUB também entra como cin. Um XOR com 1 é a própria inversão, e por isso uma única linha de controle escolhe a operação.

Vamos resolver 5 menos 3 em 4 bits. O 5 é 0101 e o 3 é 0011. Com SUB = 1, o XOR inverte o 3 e dá 1100. O somador recebe 0101 mais 1100 mais o cin 1. No bit 0, 1 mais 0 mais 1 dá 10: soma 0 e vai-um 1. No bit 1, 0 mais 0 mais 1 dá 1: soma 1 e vai-um 0. No bit 2, 1 mais 1 mais 0 dá 10: soma 0 e vai-um 1. No bit 3, 0 mais 1 mais 1 dá 10: soma 0 e vai-um 1. O resultado é 0010, que é 2, e o vai-um final 1 indica que não houve empréstimo, porque 5 é maior que 3.

A figura mostra os dois blocos e os quatro fios que levam o B invertido ao somador. A linha SUB e o cin não aparecem ligados ao somador, porque o cin entra como 1 nesse caso e o diagrama não traz uma entrada de controle separada. O texto explica essa ligação, e a figura mostra o caso concreto.

Essa é a razão de as flags de um processador serem úteis. O vai-um de saída de uma soma, lido como carry, diz que o resultado não coube em n bits sem tratamento. Quando a operação é subtração, o mesmo bit diz se houve empréstimo, com o sentido invertido. A flag de overflow é outra coisa: ela diz se o resultado com sinal saiu da faixa dos inteiros representáveis. Num somador de complemento de dois, o overflow pode ser calculado como o XOR entre o vai-um que entra no bit de sinal e o vai-um que sai dele. Esta regra é padrão, mas o programa desta aula não a testa, e a seção de limites declara isso.

4.6 Comparadores de igualdade e de magnitude

Um comparador de igualdade responde se dois números são iguais. A forma mais simples compara cada par de bits com um XNOR, que vale 1 quando os dois bits são iguais, e junta os resultados com uma porta E de quatro entradas. Se todos os pares forem iguais, a saída é 1. Se um único par diferir, a saída cai para 0.

A figura abaixo compara 1010 com 1011. Os bits 3, 2 e 1 são iguais, e o bit 0 difere, porque A tem 0 e B tem 1. Cada XNOR sai no nível de sua comparação, e o E de quatro entradas recebe 1, 1, 1 e 0.

O comparador de magnitude responde qual dos dois é maior. Ele é mais difícil, porque a comparação precisa começar pelo bit mais significativo. Se os dois bits de maior peso forem iguais, a decisão passa para o bit seguinte. A regra completa é: A é maior que B se, no bit mais significativo em que os dois diferem, A tem 1. O circuito monta isso com um termo por bit, que vale 1 quando A tem 1, B tem 0 e todos os bits de maior peso são iguais. O programa confere essa forma contra a comparação aritmética para os 256 pares de números de 4 bits. Não há figura para ele, porque o circuito fica grande e a figura de igualdade já mostra o princípio.

4.7 Multiplexador e demultiplexador

O multiplexador tem várias entradas de dados, um conjunto de linhas de seleção e uma única saída. As linhas de seleção decidem qual entrada chega à saída. Um multiplexador 2 para 1 tem uma linha S e duas entradas, A e B: a saída é A quando S é 0 e B quando S é 1. Ele pode ser montado com um NÃO para inverter S, duas portas E e um OU, e o programa da seção 7 o confere nas oito combinações.

Um multiplexador 4 para 1 tem quatro entradas, d0 a d3, e duas linhas de seleção, S1 e S0. O código de dois bits escolhe a entrada: 00 escolhe d0, 01 escolhe d1, 10 escolhe d2 e 11 escolhe d3. Uma forma comum de montá-lo usa um decodificador 2 para 4, que ativa uma única linha conforme o seletor, e quatro portas E, uma por entrada, que deixam passar só a entrada cuja linha está ativa. Um OU de quatro entradas junta as saídas, e como só uma linha está ativa por vez, só uma entrada chega ao resultado.

A figura mostra o caso S1 S0 = 10, que escolhe d2. Só a porta E da linha e2 tem as duas entradas em 1, e o OU de saída recebe 1 nessa posição.

O demultiplexador faz o caminho inverso: uma entrada de dados é encaminhada para uma de várias saídas, conforme o seletor. Ele tem a mesma estrutura do decodificador com a entrada de dados ligada a todas as portas E. O programa não confere o demultiplexador separadamente, mas a estrutura é a mesma que a do decodificador, e a seção seguinte testa essa estrutura.

4.8 Decodificador e codificador

O decodificador faz o inverso do que parece intuitivo: recebe um código de n bits e ativa exatamente uma das 2 elevado a n saídas, a que tem o índice escrito no código. Um decodificador 3 para 8 recebe 000 a 111 e ativa uma das oito saídas y0 a y7. Ele é o bloco de endereçamento básico, porque transforma um número em uma única linha de seleção.

Esse papel tem uma aplicação direta na fase 3 da trilha. Num banco de registradores, cada registrador tem uma linha de escrita, e a instrução carrega um número de registrador de 3 bits, no caso de oito registradores. O decodificador transforma esse número na linha certa. Como só uma linha fica ativa, só um registrador grava o resultado. A figura mostra o endereço 101, que ativa a saída y5.

A figura mostra só o bloco do decodificador. Os oito registradores não aparecem, porque o banco de registradores é tema da fase 3, e a figura mostra apenas a parte que escolhe o alvo. A linha y5 aparece destacada pela animação de ativação, e as outras sete ficam em repouso. O programa confere que a saída é exatamente um vetor com um único 1, na posição do índice, para os oito endereços.

O codificador faz a operação oposta: recebe uma entrada ativa entre várias e devolve o número dessa entrada em binário. Um codificador de 4 para 2 supõe que só uma entrada está ativa de cada vez. A aula não traz o programa do codificador, e a seção de limites declara isso.

4.9 A ULA de 1 bit

A unidade lógica e aritmética, a ULA, é o bloco que a fase 3 vai detalhar. Em miniatura, ela tem um bit de cada operando, um bit de operação e um resultado. A versão desta aula faz quatro operações: E, OU, soma com vai-um e XOR. Cada operação é calculada por um bloco próprio, e um multiplexador 4 para 1 escolhe qual resultado sai, conforme o código de operação de dois bits.

A figura mostra a ULA com A = 1 e B = 1 na operação de código 00, que é E. O multiplexador recebe os quatro resultados em paralelo: o E dá 1, o OU dá 1, o somador dá 0 com vai-um 1 e o XOR dá 0. Com o código 00, a saída é d0, que é o E, e o resultado é 1.

Esse é o ponto de ligação com a fase 3. Uma ULA real tem 64 bits, com um somador em cadeia ou com lookahead, e um multiplexador escolhe entre dezenas de operações. O princípio é o mesmo: os blocos calculam tudo em paralelo e um seletor decide o que sai. A instrução da CPU é, em grande parte, o código que vai aos seletores.

5. Hazards e glitches

A seção 4 supõe que cada porta reage no mesmo instante, e isso não é verdade. Cada caminho de portas tem um atraso, e quando o mesmo sinal chega por dois caminhos com atrasos diferentes, a saída pode ter um pulso passageiro que a lógica ideal não prevê. Esse pulso é o glitch, e a situação que o produz é o hazard.

O exemplo clássico é a função f = A · B + NÃO(A) · C. Com B = 1 e C = 1, a lógica ideal diz que f = A + NÃO A, que vale 1 o tempo todo. Mas o sinal NÃO A é produzido por um inversor, que leva um atraso. Quando A cai de 1 para 0, a primeira parte do termo some imediatamente, e a parte com NÃO A ainda não subiu para 1. Por um instante, nenhum dos dois termos vale 1, e a saída cai para 0 antes de voltar. Esse hazard é chamado de estático, porque a saída deveria ficar parada em 1, e o problema é um pulso indesejado para baixo.

A figura abaixo mostra as três curvas em unidades de atraso. A curva de A cai em t = 4, a de NÃO A sobe em t = 5 por causa do atraso de 1 unidade, e a saída f cai a 0 entre os dois instantes.

Os valores de tempo e de nível da figura são ilustrativos. Eles foram escolhidos para mostrar o mecanismo, e não medidos em nenhum circuito. A duração do pulso em hardware real depende do processo de fabricação, e esta aula não traz nenhuma medida dela. O que importa para o leitor é o mecanismo: a lógica está certa em regime permanente e errada durante a transição. Um circuito combinacional sozinho não guarda esse pulso, mas um circuito sequencial que lê a saída no momento errado pode guardá-lo, e é daí que vem a importância do clock na fase 2.

Existe uma solução comum, que é adicionar um termo redundante à expressão. Para f = A · B + NÃO(A) · C, adicionar o termo B · C não muda a função, porque o termo já está coberto, e mantém a saída em 1 durante a transição de A. Esse tipo de correção pode ser usado quando o projeto não aceita o pulso, mas tem custo de área. A aula não mede o custo, e a seção de limites declara isso.

6. Atraso em números

Vale fazer a conta do atraso com um modelo simples antes de conferir a figura. Suponha que cada porta tenha atraso de uma unidade, e que o caminho do vai-um de cada somador completo tenha 2 unidades: uma para a porta E que gera o vai-um e outra para o OU que o junta. Num somador em cadeia de n bits, o vai-um atravessa n blocos, então o caminho crítico cresce em torno de 2n unidades. Num lookahead em árvore, cada nível da árvore soma uma quantidade fixa de portas, e o número de níveis cresce com o logaritmo de n. O modelo da figura 10 usa 2n para a cadeia e 2 log2(n) + 2 para a árvore.

O modelo não é uma medida. As fontes usam convenções diferentes para contar atrasos. A página em inglês sobre lookahead diz que um somador de 16 bits em cadeia precisa de 16 × 2 − 1 = 31 atrasos de porta no caminho do vai-um, e que um projeto de lookahead de 16 bits precisa de no máximo 8. A página sobre somadores em geral dá (2n + 1) atrasos de porta para o pior caso de um somador em cadeia, contando também a soma. As duas contagens são coerentes entre si, mas usam critérios diferentes. O modelo da figura não reproduz nenhuma das duas, e a figura tem essa limitação declarada no título.

A leitura da figura é a seguinte. A reta da cadeia sobe em 2 unidades por bit, e no ponto n = 16 vale 32 unidades. A curva do lookahead chega a 10 unidades no mesmo ponto e cresce devagar, porque cada dobra de bits só acrescenta uma constante ao caminho. A distância entre as duas curvas cresce com n, e é isso que justifica usar lookahead em somadores largos. Para somadores curtos, a cadeia é mais simples e a diferença é pequena.

7. O programa que confere os circuitos

O programa abaixo implementa cada bloco a partir das portas, com as funções NÃO, E, OU e XOR, e confere cada um contra a aritmética de Python em todas as combinações de entrada. A regra é que a lógica construída com portas precisa bater com a conta direta, e um erro de montagem aparece como um False. O programa foi executado com Python 3.12.8, com o modo isolado -I, e a saída abaixo é a real, sem edição.

import itertools

def NOT(a): return 1 - a
def AND(a, b): return a & b
def OR(a, b): return a | b
def XOR(a, b): return a ^ b
def XNOR(a, b): return NOT(XOR(a, b))

def to_bits(x, n):
    return [(x >> i) & 1 for i in range(n)]

def from_bits(bits):
    return sum(b << i for i, b in enumerate(bits))

def meio_somador(a, b):
    return XOR(a, b), AND(a, b)

def somador_completo(a, b, cin):
    s1, c1 = meio_somador(a, b)
    s2, c2 = meio_somador(s1, cin)
    return s2, OR(c1, c2)

def somador_ripple(a_bits, b_bits, cin=0):
    s, c = [], cin
    for a, b in zip(a_bits, b_bits):
        si, c = somador_completo(a, b, c)
        s.append(si)
    return s, c

def subtrator(a_bits, b_bits):
    nb = [NOT(b) for b in b_bits]
    return somador_ripple(a_bits, nb, 1)

def lookahead_carries(g, p, cin):
    n = len(g)
    carries = []
    for i in range(n + 1):
        termos = []
        for j in range(i):
            t = g[j]
            for k in range(j + 1, i):
                t = AND(t, p[k])
            termos.append(t)
        t = cin
        for k in range(i):
            t = AND(t, p[k])
        termos.append(t)
        r = 0
        for t in termos:
            r = OR(r, t)
        carries.append(r)
    return carries

def somador_lookahead(a_bits, b_bits, cin=0):
    g = [AND(a, b) for a, b in zip(a_bits, b_bits)]
    p = [XOR(a, b) for a, b in zip(a_bits, b_bits)]
    c = lookahead_carries(g, p, cin)
    s = [XOR(XOR(a, b), c[i]) for i, (a, b) in enumerate(zip(a_bits, b_bits))]
    return s, c[-1]

def comparador_igual(a_bits, b_bits):
    r = 1
    for a, b in zip(a_bits, b_bits):
        r = AND(r, XNOR(a, b))
    return r

def comparador_maior(a_bits, b_bits):
    # A > B: no bit mais significativo diferente, A tem 1 e B tem 0
    n = len(a_bits)
    r = 0
    for i in range(n):
        t = AND(a_bits[i], NOT(b_bits[i]))
        for k in range(i + 1, n):
            t = AND(t, XNOR(a_bits[k], b_bits[k]))
        r = OR(r, t)
    return r

def mux2(a, b, s):
    return OR(AND(NOT(s), a), AND(s, b))

def mux4(d, s1, s0):
    sel = [AND(NOT(s1), NOT(s0)), AND(NOT(s1), s0),
           AND(s1, NOT(s0)), AND(s1, s0)]
    r = 0
    for di, si in zip(d, sel):
        r = OR(r, AND(di, si))
    return r

def decodificador3x8(a2, a1, a0):
    saidas = []
    for i in range(8):
        alvo = [(i >> 2) & 1, (i >> 1) & 1, i & 1]
        t = 1
        for bit, want in zip((a2, a1, a0), alvo):
            t = AND(t, bit if want else NOT(bit))
        saidas.append(t)
    return saidas

def ula1(a, b, cin, op1, op0):
    soma, cout = somador_completo(a, b, cin)
    res = mux4([AND(a, b), OR(a, b), soma, XOR(a, b)], op1, op0)
    return res, (cout if (op1, op0) == (1, 0) else 0)

# 1. somador de 4 bits em cadeia, todas as combinacoes (16 x 16 x 2 = 512)
ok = True
for a, b, c in itertools.product(range(16), range(16), [0, 1]):
    s, co = somador_ripple(to_bits(a, 4), to_bits(b, 4), c)
    if from_bits(s) + 16 * co != a + b + c:
        ok = False
print("somador ripple 4 bits, 512 casos:", ok)

# 2. exemplo 0111 + 0001 bit a bit
a, b = 0b0111, 0b0001
s, co = somador_ripple(to_bits(a, 4), to_bits(b, 4))
print("0111 + 0001 = %s, vai-um final = %d" % (format(from_bits(s), "04b"), co))

# 3. subtracao 5 - 3 com complemento de dois, 16 casos
ok = True
for a, b in itertools.product(range(16), range(16)):
    s, cout = subtrator(to_bits(a, 4), to_bits(b, 4))
    if from_bits(s) != (a - b) % 16 or cout != (1 if a >= b else 0):
        ok = False
print("subtracao 4 bits (mod 16) e flag de carry, 256 casos:", ok)
s, cout = subtrator(to_bits(5, 4), to_bits(3, 4))
print("5 - 3 = %s, carry = %d" % (format(from_bits(s), "04b"), cout))

# 4. lookahead confere com ripple em todas as combinacoes
ok = True
for a, b, c in itertools.product(range(16), range(16), [0, 1]):
    s1, c1 = somador_ripple(to_bits(a, 4), to_bits(b, 4), c)
    s2, c2 = somador_lookahead(to_bits(a, 4), to_bits(b, 4), c)
    if s1 != s2 or c1 != c2:
        ok = False
print("lookahead igual ao ripple, 512 casos:", ok)
g = [AND(x, y) for x, y in zip(to_bits(7, 4), to_bits(1, 4))]
p = [XOR(x, y) for x, y in zip(to_bits(7, 4), to_bits(1, 4))]
print("0111 + 0001: g (bit 0 a 3) =", g, " p =", p)
print("0111 + 0001: carries c0..c4 =", lookahead_carries(g, p, 0))

# 5. comparadores
ok_eq = all(comparador_igual(to_bits(a, 4), to_bits(b, 4)) == int(a == b)
            for a, b in itertools.product(range(16), repeat=2))
ok_gt = all(comparador_maior(to_bits(a, 4), to_bits(b, 4)) == int(a > b)
            for a, b in itertools.product(range(16), repeat=2))
print("comparador de igualdade, 256 casos:", ok_eq)
print("comparador de magnitude, 256 casos:", ok_gt)
print("1010 == 1011 ->", comparador_igual(to_bits(10, 4), to_bits(11, 4)),
      "  1010 > 1011 ->", comparador_maior(to_bits(10, 4), to_bits(11, 4)))

# 6. multiplexadores
ok = True
for d in itertools.product([0, 1], repeat=4):
    for s1, s0 in itertools.product([0, 1], repeat=2):
        if mux4(list(d), s1, s0) != d[2 * s1 + s0]:
            ok = False
print("mux 4:1, 64 casos:", ok)
ok = all(mux2(a, b, s) == (b if s else a)
         for a, b, s in itertools.product([0, 1], repeat=3))
print("mux 2:1, 8 casos:", ok)

# 7. decodificador 3:8: exatamente uma saida ativa, a que tem o indice do endereco
ok = True
for n in range(8):
    bits = to_bits(n, 3)
    saidas = decodificador3x8(bits[2], bits[1], bits[0])
    if saidas != [int(i == n) for i in range(8)]:
        ok = False
print("decodificador 3:8, 8 casos:", ok)
print("endereco 101 ->", decodificador3x8(1, 0, 1))

# 8. ULA de 1 bit: 00 AND, 01 OR, 10 soma, 11 XOR
ok = True
for a, b, cin, op1, op0 in itertools.product([0, 1], repeat=5):
    esperado = [a & b, a | b, a ^ b ^ cin, a ^ b][2 * op1 + op0]
    res, cout = ula1(a, b, cin, op1, op0)
    if res != esperado:
        ok = False
    if (op1, op0) == (1, 0) and cout != int(a + b + cin >= 2):
        ok = False
print("ULA 1 bit, 32 casos:", ok)
print("ULA a=1 b=1 cin=0 op=00 (AND):", ula1(1, 1, 0, 0, 0))
print("ULA a=1 b=1 cin=1 op=10 (soma):", ula1(1, 1, 1, 1, 0))

Saída real, com Python 3.12.8 e o comando python3 -I circuitos.py:

somador ripple 4 bits, 512 casos: True
0111 + 0001 = 1000, vai-um final = 0
subtracao 4 bits (mod 16) e flag de carry, 256 casos: True
5 - 3 = 0010, carry = 1
lookahead igual ao ripple, 512 casos: True
0111 + 0001: g (bit 0 a 3) = [1, 0, 0, 0]  p = [0, 1, 1, 0]
0111 + 0001: carries c0..c4 = [0, 1, 1, 1, 0]
comparador de igualdade, 256 casos: True
comparador de magnitude, 256 casos: True
1010 == 1011 -> 0   1010 > 1011 -> 0
mux 4:1, 64 casos: True
mux 2:1, 8 casos: True
decodificador 3:8, 8 casos: True
endereco 101 -> [0, 0, 0, 0, 0, 1, 0, 0]
ULA 1 bit, 32 casos: True
ULA a=1 b=1 cin=0 op=00 (AND): (1, 0)
ULA a=1 b=1 cin=1 op=10 (soma): (1, 1)

A saída confere com as contas feitas à mão nas seções 4.2, 4.4 e 4.5. O caso 1010 contra 1011 dá 0 nos dois comparadores, como esperado, porque os números são diferentes e o 1011 é maior que o 1010, o que faz a comparação de magnitude de A contra B dar 0 também, já que A é o menor. Os resultados da ULA na última linha usam os valores a = 1, b = 1, cin = 1 e operação 10, e o retorno (1, 1) significa resultado 1 e vai-um 1, que é 1 + 1 + 1 = 11 em binário.

8. Erros comuns e boas práticas

O primeiro erro é achar que o vai-um final diz tudo sobre a soma. Quase todo mundo confia nele sem olhar a conta, e quem diz que nunca fez isso ainda não cruzou um overflow às três da manhã. Ele diz se o resultado saiu do tamanho do registrador, em soma sem sinal, mas não diz se o resultado com sinal estourou. Quem usa o mesmo vai-um para as duas coisas se engana em metade dos casos. Quando você quiser saber se um resultado com sinal estourou, use a regra do XOR entre os dois últimos vai-uns, e confira com um caso de limite, como 0111 mais 0001 em complemento de dois de 4 bits.

O segundo erro é ligar a subtração sem a linha de cin. Se você inverte B e esquece de somar 1, o resultado sai uma unidade errada, e o erro é difícil de notar porque o número parece quase certo. A boa prática é testar 0 menos 0, que deve dar 0, e 0 menos 1, que deve dar 1111 em 4 bits.

O terceiro erro é tratar o hazard como problema de simulação. Uma simulação lógica em regime permanente nunca mostra o glitch, porque ela pula a transição. O glitch aparece quando o atraso das portas é modelado, e por isso a análise de hazard precisa de um modelo de tempo, mesmo que seja simples como o da figura 09.

O quarto erro é usar o lookahead sem olhar a área. A expressão de vai-um cresce com o número de bits, e a implementação real divide o somador em grupos. Antes de escolher a técnica, pergunte quanto atraso você precisa cortar e quanta área pode gastar, porque as duas coisas puxam em direções opostas.

O quinto erro é confundir o decodificador com o multiplexador. Ambos usam as mesmas linhas de seleção, mas o decodificador ativa uma saída conforme o código, e o multiplexador deixa passar uma entrada de dados conforme o código. Se você troca um pelo outro, o circuito ainda compila, mas o significado muda por completo.

A boa prática geral é a mesma da aula anterior: escreva a tabela-verdade antes de montar o circuito, e confira o circuito montado contra a aritmética em todas as combinações possíveis. Para blocos de até 8 bits de entrada, isso é barato, e cobre os erros de montagem que a leitura do desenho deixa passar.

9. Exercícios

1. Some 1011 com 0110, em 4 bits, usando o somador em cadeia. Escreva o vai-um de cada bit e o resultado final. Resposta: o bit 0 soma 1 mais 0 mais 0, que dá 1, com vai-um 0. O bit 1 soma 1 mais 1 mais 0, que dá 10, com soma 0 e vai-um 1. O bit 2 soma 0 mais 1 mais 1, que dá 10, com soma 0 e vai-um 1. O bit 3 soma 1 mais 0 mais 1, que dá 10, com soma 0 e vai-um 1. O resultado é 0001 com vai-um final 1, ou seja, 11 mais 6 é 17, que é 10001 em binário.

2. Calcule 3 menos 5 em 4 bits pelo somador-subtrator. Diga o resultado e o valor do vai-um final, e explique o que o vai-um final significa aqui. Resposta: o resultado é 1110, que é 14 em binário sem sinal, ou −2 em complemento de dois de 4 bits. O vai-um final é 0, porque 3 é menor que 5 e houve empréstimo. Esse resultado segue a mesma regra que o programa testou para os 256 pares.

3. Um decodificador de 5 entradas tem quantas saídas, e quantas portas E de quantas entradas ele precisa? Resposta: 2 elevado a 5 é 32 saídas, e cada saída usa uma porta E com 5 entradas, que pode ser feita com inversores para os bits que devem ser 0.

4. Escreva a expressão de c4 para o lookahead de 4 bits sem cin, isto é, com cin igual a 0, e diga quantos termos ela tem. Resposta: c4 = g3 OU (p3 E g2) OU (p3 E p2 E g1) OU (p3 E p2 E p1 E g0), com quatro termos, porque o termo de cin some quando cin é 0.

5. Um mux 4:1 recebe d0 = 1, d1 = 0, d2 = 1, d3 = 1 e seletor S1 S0 = 01. Qual é a saída? Resposta: 0, porque o seletor 01 escolhe d1, que vale 0.

6. Na função f = A · B + NÃO(A) · C, faça B = 0 e C = 0. Há glitch possível quando A muda? Resposta: não. Com B e C iguais a 0, os dois termos valem 0 o tempo todo, então f é 0 e não há transição para gerar pulso. O hazard exige que o termo restante esteja em 1 durante a troca de A.

Glossário

Circuito combinacional: circuito cuja saída depende só das entradas presentes, sem memória.

Circuito sequencial: circuito com memória, cuja saída depende também do estado guardado antes.

Meio somador: bloco que soma dois bits e produz soma e vai-um, sem vai-um de entrada.

Somador completo: bloco que soma dois bits e um vai-um de entrada, produzindo soma e vai-um de saída.

Vai-um, ou carry: bit que sai de uma posição e entra na posição seguinte da soma.

Ripple-carry: somador em cadeia, em que o vai-um se propaga de bit em bit.

Caminho crítico: o caminho de portas que mais demora para estabilizar a saída.

Atraso de propagação: tempo que uma porta leva para refletir uma mudança na entrada.

Geração (g): sinal que vale 1 quando um bit gera vai-um sozinho, isto é, quando A e B são 1.

Propagação (p): sinal que vale 1 quando um bit deixa passar um vai-um que chega, isto é, quando A e B são diferentes.

Lookahead: técnica que calcula os vai-uns a partir de g, p e do cin inicial, sem esperar a cadeia.

Complemento de dois: forma de representar negativos, em que a subtração vira soma com o inverso de B mais 1.

Flag de carry: bit de saída que indica vai-um da soma sem sinal, ou empréstimo na subtração.

Flag de overflow: bit de saída que indica que o resultado com sinal saiu da faixa representável.

Comparador: circuito que responde se dois números são iguais, ou qual é o maior.

Multiplexador: circuito que escolhe uma entre várias entradas de dados conforme um seletor.

Demultiplexador: circuito que encaminha uma entrada de dados para uma entre várias saídas, conforme um seletor.

Decodificador: circuito que ativa exatamente uma de suas 2 elevado a n saídas, conforme o código de n bits.

Codificador: circuito que faz a operação inversa do decodificador, devolvendo o número da entrada ativa.

ULA: unidade lógica e aritmética, bloco que calcula as operações da CPU sobre dois operandos.

Hazard estático: situação em que a saída deveria ficar fixa, mas um atraso de porta gera um pulso passageiro.

Glitch: o pulso passageiro indesejado que um hazard produz na saída.

O que não foi confirmado ou medido

Os programas desta aula foram executados e as saídas são reais. Eles verificam a lógica dos blocos contra a aritmética, mas não simulam tensão, corrente, nem tempo de porta.

A figura 09 é ilustrativa. Os níveis e os instantes da curva foram escolhidos para mostrar o mecanismo e não foram medidos em nenhum circuito. A duração real do glitch depende do processo de fabricação e não foi confirmada nesta aula.

A figura 10 é um modelo de atraso unitário, com as fórmulas 2n para a cadeia e 2 log2(n) + 2 para a árvore. Esse modelo não é uma medida. As contagens das fontes usam convenções diferentes, e a aula não tentou reconciliá-las: a página sobre lookahead dá 31 para 16 bits, e a página sobre somadores dá (2n + 1) para o pior caso.

A fórmula de overflow com sinal, como XOR entre os dois últimos vai-uns, é uma regra padrão de complemento de dois, mas o programa desta aula não a testou. Ela está declarada no texto e não deve ser citada como verificada aqui.

O codificador e o demultiplexador são descritos, mas não aparecem no programa. A estrutura do demultiplexador é a mesma do decodificador, e isso foi usado como argumento, sem teste separado.

O circuito do comparador de magnitude não tem figura, porque o desenho fica grande demais para uma figura didática. A lógica dele é testada no programa.

As figuras 01 a 08 mostram a lógica no nível de portas. Elas não representam transistores nem o caminho elétrico. A relação com a aula de transistores é conceitual.

A figura 07 mostra só o bloco decodificador. O banco de registradores que ela ilustra é tema da fase 3, e não foi desenhado aqui.

A figura 04 mostra o XOR de B como um bloco, e não como quatro portas XOR separadas, para deixar o caminho do somador mais visível.

Não há medida de atraso real de porta nesta aula. Quando a fase 2 chegar ao clock, o atraso precisará de uma fonte de processo, e as cifras atuais não entram aqui.

Fontes

Consultadas em 1 de novembro de 2026.

• Wikipedia em inglês, verbete “Carry-lookahead adder”, sobre g e p, a recorrência do vai-um, e as contagens de atraso de 16 bits que a aula cita: https://en.wikipedia.org/wiki/Carry-lookahead_adder
• Wikipedia em inglês, verbete “Adder (electronics)”, sobre meio somador, somador completo, cadeia de vai-um e a subtração com complemento de dois: https://en.wikipedia.org/wiki/Adder_(electronics)
• Wikipedia em inglês, verbete “Multiplexer”, sobre multiplexador 2 para 1 e 4 para 1, e o demultiplexador: https://en.wikipedia.org/wiki/Multiplexer

As fontes acima descrevem os blocos e as convenções de atraso. Os valores numéricos da aula, incluindo os das tabelas, foram calculados e conferidos pelo programa da seção 7, e não copiados das fontes. A regra do overflow e a estrutura do codificador não foram conferidas em fonte primária nesta sessão.

Relacionados

• Trilha de Hardware
• CPU
• Transistor como chave
• Álgebra booleana e portas lógicas
• Inteiros, complemento de dois e overflow
• Bits e binário