Lógica digital

O panorama: bits, sinais e dois tipos de circuitos

Um [[bit|abreviação de binary digit (dígito binário): a menor informação possível, um 0 ou um 1]] é a resposta de uma pergunta de sim ou não, como um interruptor de luz. Em um circuito real, 1 costuma ser uma tensão alta e 0 uma tensão baixa. Um fio carrega um bit, e um grupo de fios carrega um grupo de bits.

Por que só dois valores? Porque é muito fácil distinguir "alto" de "baixo" mesmo quando o sinal tem um pouco de ruído. Distinguir dez níveis de tensão seria bem mais difícil e daria erros.

Os circuitos digitais têm duas famílias. Um [[circuito combinacional|circuito cuja saída depende apenas das entradas que ele tem agora]] é como o botão de uma calculadora: aperte 2 + 3 e dá 5, não importa o que você fez antes. Um [[circuito sequencial|circuito cuja saída depende das entradas e também do que aconteceu antes, que ele guarda como um estado]] é como o placar de um jogo: depende do passado, porque ele lembra.

O resto do resumo segue uma escada. Primeiro os números e códigos que os bits representam, depois as portas e a álgebra que as descreve, depois os blocos combinacionais (somadores, seletores), depois a memória (flip-flops, registradores, contadores) e, por fim, a ponte para o mundo analógico.

Sistemas de numeração e conversão de bases

Contamos de dez em dez porque temos dez dedos. O número 347 significa 3 centenas, 4 dezenas e 7 unidades: cada casa vale dez vezes a casa à sua direita. Isso se chama [[sistema posicional|um jeito de escrever números em que o valor de um dígito depende da casa onde ele está]], e o número 10 é a sua base.

O computador tem dois estados, então usa a base 2, o binário. As casas valem 1, 2, 4, 8, 16 e assim por diante, dobrando a cada passo para a esquerda. A contagem das casas sempre começa em 0, pela direita.

Para ler um número binário, some os pesos das casas que têm 1. Assim, 10011 é 16 + 2 + 1 = 19. O bit mais à esquerda tem o maior peso e se chama MSB (bit mais significativo). O mais à direita tem o menor e é o LSB (bit menos significativo). Um grupo de 4 bits é um nibble e um grupo de 8 bits é um byte.

Com n bits existem 2^n padrões diferentes. Começando em 0, o maior número sem sinal é 2^n − 1, em que todos os bits são 1. Em um byte, isso dá 255. Para guardar N valores diferentes você precisa do menor n com 2^n ≥ N.

Convertendo decimal para binário

Divida por 2 várias vezes, anote cada resto e leia os restos do último para o primeiro.

25 / 2 = 12 resto 1   <- LSB
12 / 2 =  6 resto 0
 6 / 2 =  3 resto 0
 3 / 2 =  1 resto 1
 1 / 2 =  0 resto 1   <- MSB

lendo de baixo para cima: 11001  (16 + 8 + 1 = 25)

Octal e hexadecimal

Sequências longas de bits são difíceis de ler. Por isso agrupamos. O octal (base 8) usa os dígitos 0 a 7, e um dígito vale exatamente 3 bits. O hexadecimal (base 16) usa 0 a 9 e depois A a F, que valem 10 a 15. Um dígito hexa vale exatamente 4 bits, então um byte são sempre dois dígitos hexa.

binário  1101 0110
          |    |
hexa      D    6      -> D6

D6 = 13 x 16 + 6 = 214

binário 1010011 -> agrupe de 3 em 3 a partir da direita: 001 010 011 -> octal 123

Endereços de memória são escritos em hexa. Se as posições vão do endereço 0000 ao 0FFF, existem 0FFF + 1 = 1000 em hexa, que é 16^3 = 4.096 posições. Uma faixa que começa em zero e termina em X tem X + 1 posições.

Frações

Depois da vírgula binária os pesos caem pela metade: 1/2, 1/4, 1/8, 1/16. Assim, 110,01 é 4 + 2 + 0,25 = 6,25. Uma fração decimal só pode ser escrita exatamente em binário se o denominador, na forma irredutível, for uma potência de 2. Por isso 0,375 (3/8) é exato, mas 0,1 (1/10) se repete para sempre em binário e acaba arredondado.

Códigos: BCD, Gray, ASCII e complemento de 2

Um padrão de bits não significa nada até combinarmos um código: uma regra que diz o que cada padrão representa. Os mesmos 8 bits podem ser um número, uma letra ou uma cor. Estes são os códigos que todo estudante precisa conhecer.

BCD: um dígito decimal por vez

O [[BCD|decimal codificado em binário: cada dígito decimal é escrito separadamente com 4 bits]] (pesos 8-4-2-1) é útil em relógios e calculadoras, porque cada dígito vai direto para um visor. O número decimal 83 é 1000 0011 em BCD, um dígito de cada vez. Em binário puro seria 101 0011.

O BCD desperdiça espaço: os padrões 1010 a 1111 nunca aparecem. Quando um somador binário comum de 4 bits soma dois dígitos BCD e o resultado passa de 9 (ou gera carry), some 6 para pular os seis padrões não usados. Em 7 + 6: o somador dá 1101, somando 0110 resulta 1 0011, que se lê como os dígitos 1 e 3, ou seja, 13.

Código Gray: só um bit muda

Em binário, ir de 0111 para 1000 muda quatro bits de uma vez. Se um sensor lê durante a troca, pode pegar um valor errado no meio. No código Gray cada passo muda exatamente um bit, então uma leitura nunca erra por mais de um passo.

Para converter binário em Gray, mantenha o primeiro bit e faça XOR de cada par de bits vizinhos. Outro jeito: Gray = n XOR (n deslocado uma casa para a direita). Para 1100: 1100 XOR 0110 = 1010. O código Gray é usado em encoders de posição e nos rótulos do mapa de Karnaugh.

ASCII e paridade

O ASCII dá um número a letras, dígitos, pontuação e caracteres de controle. O ASCII padrão tem 7 bits, então 2^7 = 128 caracteres. O 8º bit do byte ficou livre. Muitas vezes é usado como bit de paridade: um bit extra escolhido para que o total de 1s seja par (paridade par) ou ímpar (paridade ímpar).

A letra E é 100 0101, que tem três 1s. Com paridade par o bit de paridade é 1, e o byte enviado é 1100 0101. Se um bit virar no caminho, o receptor conta uma quantidade ímpar de 1s e percebe o problema. Mas a paridade não diz qual bit mudou, e dois bits trocados se cancelam.

Complemento de 2: números negativos

No complemento de 2 o bit mais à esquerda tem peso negativo. Em 8 bits os pesos são −128, 64, 32, 16, 8, 4, 2, 1. Assim, 1011 0100 = −128 + 32 + 16 + 4 = −76. O bit da esquerda é 1 nos números negativos, e existe um único zero.

• Para negar um número: inverta todos os bits e some 1. Para 5 = 0000 0101: invertendo dá 1111 1010, somando 1 dá 1111 1011, que é −5.
• Conferência rápida: o negativo de um módulo m em n bits é 2^n − m. Em 8 bits, 256 − 5 = 251 = 1111 1011.
• Faixa com n bits: de −2^(n−1) a 2^(n−1) − 1. Em 8 bits, de −128 a 127.
• Para ampliar um número (de 4 para 8 bits) sem mudar o valor, copie o bit de sinal em todos os novos bits da esquerda: 1010 (−6) vira 1111 1010.

Portas lógicas e tabelas-verdade

Uma porta lógica é um tomador de decisões com uma regra bem curta. Pense em uma porta vigiada por duas crianças: a porta AND só abre se as duas tiverem a chave, a porta OR abre se pelo menos uma tiver.

Uma [[tabela-verdade|uma lista de todas as combinações possíveis das entradas, com a saída de cada uma]] descreve uma porta por completo. Com n entradas há 2^n linhas, normalmente listadas na ordem de contagem binária. Duas entradas dão 4 linhas, três dão 8, quatro dão 16.

• NOT inverte sua única entrada: 0 vira 1 e 1 vira 0. Escreve-se A'.
• AND (escrita A·B) vale 1 só quando todas as entradas são 1. É um produto.
• OR (escrita A + B) vale 1 quando pelo menos uma entrada é 1. É uma soma.
• XOR vale 1 quando as entradas são diferentes. É a soma de dois bits sem o carry: A'·B + A·B'.
• NAND, NOR, XNOR são AND, OR e XOR seguidas de um NOT. Assim, a NAND vale 0 só na única linha em que todas as entradas são 1, e uma NAND de n entradas vale 1 nas outras 2^n − 1 linhas.

Para reconhecer uma porta pela tabela, procure a linha diferente das outras. AND e NOR têm um único 1. NAND e OR têm um único 0.

Lendo um circuito e um diagrama de tempo

Para achar a tabela de um circuito, dê nome a cada fio e escreva o que ele carrega, passo a passo. Neste circuito, X = A·B, W = C' e Y = X + W.

A ----+
      AND ---- X ----+
B ----+              OR ---- Y
                     |
C ---- NOT ---- W ---+

Um diagrama de tempo mostra os sinais ao longo do tempo, uma coluna por instante. Sem atrasos, você aplica a tabela-verdade a cada coluna. Na NAND a saída é 0 exatamente nos instantes em que todas as entradas são 1.

Portas universais

Qualquer função booleana pode ser feita com AND, OR e NOT. Um conjunto de portas que consegue fazer essas três é universal. A NAND sozinha é universal, e a NOR sozinha também. Se você ligar as duas entradas de uma NAND juntas, A·A = A, então ela calcula A' e funciona como NOT. A NAND seguida desse NOT faz a AND. E a OR sai da lei de De Morgan, vista na próxima seção.

NOT A    = NAND(A, A)
A AND B  = NOT( NAND(A, B) )
A OR B   = NAND( NOT A, NOT B )

XOR com 4 NANDs:   M = NAND(A, B)
                   XOR = NAND( NAND(A, M), NAND(B, M) )

Álgebra booleana e leis de De Morgan

A álgebra booleana é a aritmética do 0 e do 1. Ela permite escrever um circuito como uma fórmula e depois encurtar a fórmula, o que significa um circuito mais barato. Cada porta vira um símbolo: o apóstrofo é NOT, o ponto é AND e o mais é OR.

A ordem de prioridade é a mesma da matemática da escola: primeiro NOT, depois AND (como a multiplicação), depois OR (como a soma). Então A + B·C significa A + (B·C).

Repare que a segunda lei distributiva, A + B·C = (A + B)·(A + C), não existe na aritmética comum. Na álgebra booleana os dois sentidos funcionam.

Leis de De Morgan

Para negar uma expressão, negue cada variável e troque AND por OR. Em símbolos, (A·B)' = A' + B' e (A + B)' = A'·B'. Imagine a regra "você não pode ter bolo e sorvete": ela quer dizer "sem bolo, ou sem sorvete".

Com vários níveis, trabalhe de fora para dentro e deixe a dupla negação se cancelar. Por exemplo, (A + B'·C)' = A'·(B'·C)' = A'·(B + C').

Simplificações úteis

• X·Y + X·Y' = X: dois termos que diferem em uma variável se juntam, e essa variável desaparece.
• A + A'·B = A + B: se A é 1 o resultado já é 1, se A é 0 sobra só B. Apenas o literal A' sai, não o termo inteiro.
• Consenso: A·B + A'·C + B·C = A·B + A'·C. O último termo é redundante.
• Como X + X = X, o mesmo termo pode ser usado em mais de um agrupamento.

Formas canônicas: mintermos e maxtermos

Um [[mintermo|um produto que contém todas as variáveis da função, normais ou negadas, e vale 1 em exatamente uma linha da tabela-verdade]] tem o índice da sua linha. Leia a linha em binário com a primeira variável como bit mais significativo. A variável aparece normal se seu bit é 1 e negada se é 0. Com três variáveis, a linha 5 (101) é o mintermo A·B'·C.

A soma de produtos canônica soma os mintermos das linhas em que a função vale 1, escrita Σm(...). Um maxtermo é uma soma que vale 0 em exatamente uma linha. O produto de somas canônico, ΠM(...), multiplica os maxtermos das linhas em que a função vale 0, e no maxtermo os bits são usados ao contrário: 0 dá a variável normal e 1 dá a variável negada.

Cada linha é um mintermo ou um maxtermo, nunca os dois. Então o número de mintermos mais o de maxtermos é sempre 2^n. Uma função com poucos 0s tem um produto de somas curto.

Mapas de Karnaugh

Simplificar com álgebra exige bom olho e sorte. O mapa de Karnaugh transforma isso em um desenho. É uma tabela-verdade redesenhada como uma grade, de modo que duas células vizinhas diferem em exatamente uma variável. E já sabemos que X·Y + X·Y' = X, então dois 1s vizinhos podem se juntar em um termo mais curto.

Para que células vizinhas difiram em uma variável, os rótulos de linhas e colunas seguem o código Gray: 00, 01, 11, 10, e não a ordem binária. O mapa também dá a volta: a primeira e a última coluna são vizinhas, e a primeira e a última linha também. Um grupo pode atravessar a borda, e os quatro cantos são vizinhos.

        BC
       00  01  11  10
A=0 |   1   0   0   1
A=1 |   1   1   0   1

A receita é curta. Cubra todos os 1s com os maiores grupos possíveis, usando o menor número de grupos. Uma célula pode pertencer a vários grupos.

• Um grupo é um retângulo de 1, 2, 4, 8 ou 16 células: sempre uma potência de 2. Uma região de 6 células precisa de dois grupos, que podem se sobrepor.
• Cada vez que o grupo dobra, uma variável some. Um grupo de 2^k células em um mapa de n variáveis dá um termo com n − k literais. Em um mapa de 4 variáveis: 2 células dão 3 literais, 4 células dão 2, 8 células dão 1.
• Para escrever o termo, mantenha só as variáveis que não mudam dentro do grupo. Se a variável vale 1 no grupo, escreva-a normal; se vale 0, escreva-a negada.
• Some os termos de todos os grupos: essa é a soma de produtos mínima.

No mapa acima, as quatro células das colunas 00 e 10 (as colunas que dão a volta) formam um grupo com C = 0: o termo é C'. O par A=1, B=0 (células 100 e 101) dá A·B'. Então F = C' + A·B'.

      CD
     00  01  11  10
AB=00 | 1   0   0   1
AB=01 | 0   1   1   0
AB=11 | 0   1   1   0
AB=10 | 1   0   0   1

cantos (00,00)(00,10)(10,00)(10,10)  -> B'·D'
bloco central                        -> B·D
F = B'·D' + B·D   (XNOR de B e D)

Produto de somas, don't-cares e implicantes primos

• Produto de somas: agrupe os 0s. Cada grupo dá um termo de soma em que a variável é normal quando vale 0 e negada quando vale 1. É o mesmo que simplificar F' e aplicar De Morgan.
• Don't-care (X): uma combinação de entrada que nunca ocorre ou cuja saída não importa, por exemplo os códigos 1010 a 1111 em um circuito BCD. Você pode contar um X como 1 para aumentar um grupo, ou ignorá-lo. Só os 1s de verdade precisam ser cobertos. Exemplo: 1s nos mintermos 1, 3, 7 e um X no 5 dão C, enquanto sem o X seriam necessários dois pares.
• Implicante primo: um grupo que não pode ser aumentado. Ele é essencial quando cobre um 1 que nenhum outro implicante primo cobre. Pegue primeiro todos os essenciais e depois acrescente o mínimo de outros para cobrir o que sobrou. É exatamente o que o método de Quine-McCluskey faz por procedimento.
• Padrão de tabuleiro de xadrez: quando os 1s nunca se tocam (como o XOR de três variáveis, paridade ímpar), nada se junta e a soma de produtos não encolhe.

Circuitos aritméticos: somadores e subtratores

Somar em binário é como somar no papel em decimal, mas o carry ("vai um") aparece assim que uma coluna chega a 2. As regras: 0+0 = 0, 0+1 = 1, 1+1 = 10 (escreve 0, vai 1) e 1+1+1 = 11 (escreve 1, vai 1).

  carries:  1 1 1
            0 1 1 0   (6)
          + 0 1 1 1   (7)
          ---------
            1 1 0 1   (13)

O meio somador

Somar dois bits dá um bit de soma e um carry. A soma vale 1 para 01 e 10, então é XOR. O carry vale 1 só para 11, então é AND. Esse circuito é o meio somador (half adder): S = A XOR B e C = A·B. Ele é "meio" porque não tem entrada para o carry que vem da direita.

O somador completo

Uma coluna no meio de um número tem três bits para somar: A, B e o carry de entrada Cin. O somador completo (full adder) recebe os três. Sua soma é a paridade dos três bits, S = A XOR B XOR Cin. Seu carry de saída vale 1 quando pelo menos duas entradas valem 1 (maioria): Cout = A·B + A·Cin + B·Cin. Ele pode ser feito com dois meios somadores e uma OR.

O somador ripple-carry

Para somar números de n bits, encadeie n somadores completos: o carry de saída do estágio i entra no carry de entrada do estágio i + 1. Esse é o somador ripple-carry. É o projeto mais simples, mas um carry pode ter de passar por todos os estágios, como um balde passado por uma fila de pessoas. No pior caso (1111...1 + 1) o atraso é proporcional a n. Com 3 ns por estágio, 16 estágios levam 16 × 3 = 48 ns. Projetos mais rápidos, como o somador carry-lookahead, preveem os carries para reduzir esse tempo.

Subtração com o mesmo somador

No complemento de 2, A − B = A + B' + 1. No circuito, uma porta XOR em cada bit de B é controlada por um fio SUB (XOR com 1 inverte, XOR com 0 deixa passar). O mesmo fio SUB vai para o primeiro carry de entrada, que fornece o +1. Com SUB = 0 o circuito soma, com SUB = 1 ele subtrai.

6 - 2 com 4 bits:  A = 0110
                   B' = 1101   (2 = 0010 invertido)
                   Cin = 1
                   -----------
                   soma = 0100  carry de saída = 1
6 - 2 = 4 e o carry de saída é 1: sem empréstimo

Carry de saída e overflow são coisas diferentes

• Subtração sem sinal: o carry de saída funciona como o inverso do empréstimo (borrow). Carry 1 significa que não foi preciso emprestar (A ≥ B). Carry 0 significa que houve empréstimo (A < B). É assim que um processador compara dois números sem sinal: subtrai e olha a flag de carry.
• Overflow com sinal: o resultado não cabe em n bits. Ocorre quando dois operandos de mesmo sinal dão um resultado de sinal oposto. É o mesmo que o carry que entra no bit de sinal ser diferente do carry que sai dele. Exemplo em 4 bits: 0111 + 0001 = 1000, ou seja, 7 + 1 = −8.
• O carry de saída sozinho só indica overflow para números sem sinal.

Multiplexadores, demultiplexadores, codificadores e decodificadores

Esses são os "guardas de trânsito" de um circuito. Eles escolhem qual sinal vai para onde. Todos são combinacionais.

Multiplexador (mux): muitas entradas, uma saída

Um multiplexador tem várias entradas de dados, uma saída e algumas entradas de seleção. As entradas de seleção formam um número binário que diz qual entrada de dados está ligada à saída. É como um controle remoto de TV que escolhe um canal entre muitos.

Para escolher entre 2^n entradas de dados são necessárias n linhas de seleção: 1 para um mux 2:1, 2 para 4:1, 3 para 8:1, 4 para 16:1. Um processador usa muxes para escolher qual registrador alimenta a ULA.

I0 --+
I1 --|  4:1
I2 --|  MUX ---- Y
I3 --+   |  |
        S1 S0

S1 S0 = 1 0  ->  Y = I2

Muxes grandes são construídos como uma árvore de muxes pequenos. Um mux 16:1 com peças 4:1: quatro muxes no primeiro nível recebem os dados e os dois bits baixos da seleção, e um mux no segundo nível escolhe entre as saídas deles com os dois bits altos da seleção. São 4 + 1 = 5 componentes.

Um mux também pode calcular uma função. Um mux com n linhas de seleção implementa qualquer função de n + 1 variáveis. Ligue n das variáveis às seleções. Para cada valor de seleção, a saída só pode ser 0, 1, a variável restante ou seu complemento, e é isso que se liga à entrada de dados. Exemplo: F = A XOR B com um mux 2:1 cuja seleção é A: I0 = B (quando A = 0, F = B) e I1 = B' (quando A = 1, F = B').

Demultiplexador (demux): uma entrada, muitas saídas

O oposto do mux. Uma entrada de dados é enviada para a saída escolhida pelas linhas de seleção, e todas as outras saídas ficam em 0. É um decodificador em que o dado faz o papel do enable.

Decodificador: um código vira uma linha

Um decodificador binário com n entradas tem 2^n saídas e exatamente uma está ativa: aquela cujo número é igual ao código de entrada. Cada saída é um mintermo das entradas. Ele seleciona uma posição de memória, um dispositivo ou a operação de uma instrução.

Decodificadores com entrada de enable podem ser expandidos. Para um decodificador 3 para 8 a partir de dois 2 para 4, os dois bits baixos vão para os dois blocos, e o bit alto A2 vai direto ao enable de um bloco e, por um inversor, ao enable do outro. Chips de memória são selecionados pelos bits altos do endereço da mesma forma.

Codificador: uma linha vira um código

O codificador faz o contrário do decodificador: 2^n entradas, das quais uma está ativa, viram o número de n bits dessa entrada. Um teclado usa um para transformar a tecla apertada em um código. Um codificador simples são só portas OR: cada bit de saída é o OR das entradas cujo índice tem esse bit em 1.

O problema começa quando duas entradas estão ativas. Suponha que I1 e I2 estejam ativas: as portas OR misturam os códigos 01 e 10 e a saída é 11, que aponta para uma terceira entrada. O codificador de prioridade resolve: ele responde com o código da entrada ativa de maior prioridade e ignora as outras. Com I3 I2 I1 I0 = 1010 e prioridade para o maior índice, a saída é 11. Ele decide qual interrupção é atendida primeiro.

Latches e flip-flops

Até agora todo circuito esquecia tudo no momento em que as entradas mudavam. Para lembrar um bit precisamos de realimentação: uma saída ligada de volta a uma entrada. Duas portas que escutam uma à outra conseguem segurar um valor, como duas crianças que ficam repetindo a mesma palavra uma para a outra.

O latch RS

Um [[latch|uma célula básica de memória que guarda um bit e reage às entradas enquanto está habilitada]] feito de duas portas com acoplamento cruzado tem duas saídas, Q e Q', que devem ser sempre opostas. Ele tem uma entrada Set (faz Q = 1) e uma entrada Reset (faz Q = 0).

No latch NOR uma entrada em 1 força a sua porta a 0. Pedir set e reset juntos deixa as duas saídas em 0, o que quebra a regra de que Q' é o oposto de Q. E se as duas entradas voltam a 0 ao mesmo tempo, o estado final depende de qual porta é mais rápida, então é imprevisível. No latch NAND o nível que comanda é 0, então as entradas são ativas em baixo: é o mesmo comportamento com os níveis de cabeça para baixo.

Nível ou borda?

Um latch D tem uma entrada de dado D e uma entrada de habilitação, normalmente ligada ao clock. Enquanto a habilitação vale 1 o latch fica transparente: Q segue D. Quando a habilitação vai a 0, Q guarda o último valor. Ele é sensível ao nível.

Um flip-flop é sensível à borda: ele olha D só no instante em que o clock sobe (ou desce) e mantém Q até a próxima borda. Um flip-flop D pode ser feito com dois latches D em série com habilitações opostas (mestre-escravo). A forma de onda mostra a diferença:

t:           0 1 2 3 4 5 6 7
clock:       0 1 1 0 0 1 1 0
D:           1 1 0 0 1 0 1 1
latch D:     0 1 0 0 0 0 1 1   <- segue D enquanto clock = 1
flip-flop:   0 1 1 1 1 0 0 0   <- olha D só nas subidas do clock

Olhe o instante 6: o clock vale 1 e D vira 1, então o latch segue, mas o flip-flop não se move porque não há uma nova borda de subida.

Os tipos de flip-flop

• Flip-flop D: na borda ativa Q assume o valor de D, no resto do tempo mantém. É a célula básica dos registradores.
• Flip-flop JK: J = K = 0 mantém, J = 1 K = 0 faz set, J = 0 K = 1 faz reset e J = K = 1 faz toggle (Q inverte). Diferente do RS, não tem combinação proibida. O toggle divide a frequência do clock por 2, que é a base dos contadores.
• Para acompanhar um JK no tempo, aplique o modo ao Q anterior em cada borda ativa. Entre as bordas Q fica parado.

Temporização: setup, hold e o clock mais rápido

Um flip-flop lê D corretamente só se D estiver estável em uma pequena janela ao redor da borda do clock: o tempo de setup (antes da borda) e o tempo de hold (depois dela). Violar essa janela pode deixar a saída em um estado instável no meio do caminho, chamado metaestabilidade.

Entre dois flip-flops no mesmo clock, o dado precisa sair do primeiro (atraso de propagação), atravessar a lógica e chegar ao segundo com folga (tempo de setup). Então o período do clock deve ser pelo menos a soma dos três, e a frequência máxima é 1 dividido por esse período (frequência é quantos pulsos de clock cabem em um segundo; 1 MHz é um milhão por segundo). Para 6 ns + 10 ns + 4 ns = 20 ns a frequência máxima é 1 / 20 ns = 50 MHz.

Registradores e contadores

Um flip-flop guarda um bit. Vários lado a lado guardam uma palavra, como uma fileira de caixas de correio em que cada uma guarda uma carta.

Registradores

Um registrador de n bits são n flip-flops D que compartilham o mesmo clock, então os n bits são capturados juntos. Para que ele mantenha a palavra mesmo com o clock batendo, um multiplexador na frente de cada flip-flop realimenta o bit para ele mesmo quando o sinal load vale 0. Registradores guardam operandos, resultados e endereços dentro de um processador.

Registradores de deslocamento

Em um registrador de deslocamento (shift register) a saída de cada flip-flop vai para a entrada do vizinho. A cada pulso de clock todos os bits andam uma casa, um bit novo entra em uma ponta e um sai pela outra. Carregar n bits pela única entrada serial leva n pulsos. Na transferência paralela há um fio por bit e um pulso carrega a palavra inteira.

desloca à direita, entrada serial = 0
início  Q3 Q2 Q1 Q0 = 1 1 0 0   (12)
pulso 1               0 1 1 0   (6)
pulso 2               0 0 1 1   (3)

Contadores

Um contador é um registrador que percorre uma sequência de estados, um por pulso de clock. Um contador binário crescente de n bits tem até 2^n estados e depois recomeça; esse número de estados é o seu módulo. Um contador de 4 bits tem módulo 16: vai 0, 1, ... 15 e volta ao 0. O contador de programa de um processador é um registrador assim, somando 1 a cada instrução.

O bit menos significativo inverte a cada pulso, o seguinte a cada 2 pulsos, depois a cada 4. Então o bit k tem a frequência do clock dividida por 2^(k+1), e um contador de n bits divide a frequência por 2^n no último bit.

Assíncrono e síncrono

Em um contador assíncrono (ripple) a saída de cada flip-flop é o clock do próximo. Eles não mudam juntos, e enquanto a mudança se propaga o contador mostra valores errados no meio do caminho. O tempo de acomodação é o número de estágios vezes o atraso de um flip-flop. Com 3 flip-flops de 5 ns os pulsos precisam ter pelo menos 15 ns entre si, então 1 / 15 ns ≈ 66,7 MHz no máximo. Em um contador síncrono todos os flip-flops compartilham o clock e os atrasos não se somam.

Outros módulos e o contador Johnson

Para contar menos de 2^n estados, detecte o primeiro estado indesejado e use-o para zerar (clear) o contador. Para contar de 0 a 5 (módulo 6), detecte 0110 e zere. Com clear assíncrono, o estado 0110 aparece só por um instante, como um pulso curto (glitch), e o módulo é o valor detectado. Esse glitch é uma desvantagem; projetos síncronos preferem detectar o último estado válido e zerar na borda seguinte.

Um contador Johnson (em anel torcido) é um registrador de deslocamento em que o complemento do último flip-flop volta ao primeiro. Ele primeiro se enche de 1s e depois se esvazia, então n flip-flops dão 2n estados, e apenas um bit muda entre estados vizinhos.

3 flip-flops Q2 Q1 Q0, deslocando à direita, Q0' entra em Q2:
0 0 0 -> 1 0 0 -> 1 1 0 -> 1 1 1 -> 0 1 1 -> 0 0 1 -> 0 0 0
6 estados = 2 x 3

Conversão analógico-digital

O mundo real é analógico: temperatura, som e luz variam de forma suave. Um circuito digital só entende bits. Um conversor D/A (DAC) transforma um código em uma tensão. Um conversor A/D (ADC) transforma uma tensão em um código. O seu celular usa um ADC para cada som que o microfone ouve.

Conversor D/A e resolução

Um DAC de N bits pode gerar 2^N níveis com degraus iguais. A resolução é o tamanho de um degrau, a variação da saída quando o código sobe 1 (o LSB). Se o maior código, 2^N − 1, dá a tensão de fundo de escala, o degrau é essa tensão dividida por 2^N − 1. A saída para qualquer código é o degrau vezes o valor do código.

DAC de 4 bits, 0 V para 0000 e 3,0 V para 1111
degrau = 3,0 V / 15 = 0,2 V
código 0101 = 5  ->  5 x 0,2 V = 1,0 V

Três jeitos de construir um ADC

Todos comparam a tensão de entrada com a saída de um DAC interno ou com níveis de referência fixos. Um comparador é um circuito que diz se uma tensão está acima de outra.

• Rampa digital: um contador sobe um degrau por clock até o DAC interno alcançar a entrada. É o mais simples, mas o tempo depende da entrada, e o pior caso é 2^N − 1 ciclos de clock. Dobra a cada bit acrescentado. Com 10 bits e clock de 1 MHz são 1.023 ciclos, cerca de 1,023 ms.
• Aproximações sucessivas (SAR): uma busca binária. Teste o bit mais significativo em 1, mantenha só se a saída do DAC não passar da entrada, depois siga para o próximo bit. Sempre leva exatamente N ciclos, qualquer que seja a entrada.
• Flash: um divisor de resistores gera todos os níveis de referência e um comparador por nível testa a entrada ao mesmo tempo. Um codificador de prioridade transforma o resultado em um código. É praticamente instantâneo, mas o custo dobra a cada bit: 2^N − 1 comparadores.

SAR, 4 bits, degrau do DAC 0,5 V, entrada 4,7 V
testa 1000 = 4,0 V  <= 4,7  mantém  ->  1000
testa 1100 = 6,0 V  >  4,7  descarta ->  1000
testa 1010 = 5,0 V  >  4,7  descarta ->  1000
testa 1001 = 4,5 V  <= 4,7  mantém  ->  1001
resultado 1001 = 4,5 V, erro de quantização 0,2 V

A diferença que sobra entre a entrada real e o valor do código final é o erro de quantização. Ele é sempre menor que um degrau.

Juntando tudo

Veja como as ideias se empilham, de baixo para cima. Cada nível é feito do anterior.

bits e códigos (binário, hexa, complemento de 2, BCD, Gray)
   |
portas (AND, OR, NOT, NAND, NOR, XOR)
   |
álgebra booleana + mapas de Karnaugh  (deixam o circuito pequeno)
   |
blocos combinacionais: somadores, mux, decodificador, codificador
   |
realimentação -> latch -> flip-flop
   |
registradores, registradores de deslocamento, contadores
   |
processador (ULA + registradores + muxes + decodificador)
   |
conversores A/D e D/A ligam tudo ao mundo real

Um processador pequeno é exatamente essa escada: um somador com portas XOR vira uma ULA, flip-flops viram registradores e um contador de programa, muxes escolhem qual registrador alimenta a ULA, e um decodificador transforma a instrução em sinais de controle. Se você quiser ver tudo construído a partir de uma única porta NAND, os mini-projetos deste repositório fazem isso.

Erros que aparecem sempre

Dois vídeos mostram todo esse caminho, e depois você pode testar por conta própria em um simulador.