Cap. 3 — Nível de
Lógica Digital

introdução / o nível 0 da máquina multinível

Introdução: o nível de lógica digital na máquina multinível

No Capítulo 2, o computador foi apresentado como uma máquina multinível: uma hierarquia de máquinas virtuais em que cada nível M_n oferece uma linguagem L_n ao nível superior e executa seus programas por tradução ou interpretação com o auxílio do nível imediatamente inferior. No modelo de seis níveis (TANENBAUM; AUSTIN, 2013), cada degrau acima esconde detalhes do degrau de baixo e oferece uma interface mais simples e mais próxima do raciocínio humano.

Este capítulo trata do degrau da base: o nível 0 — lógica digital. Ele é o nível mais primitivo do modelo, ou seja, o de menor abstração. Nele não existem instruções, variáveis nem programas; existem apenas sinais binários (0 e 1) e portas lógicas que os combinam segundo funções booleanas. Tudo o que os níveis superiores realizam — somar, comparar, deslocar, armazenar — precisa, em última instância, ser executado por redes de portas.

Abaixo do nível 0 situa-se o nível de dispositivo — transistores, tensões, correntes e física dos semicondutores —, domínio da engenharia eletrônica e, por isso, fora do escopo do modelo. O nível de lógica digital funciona como uma primeira abstração sobre ele: em vez de tensões contínuas, interessa apenas se o sinal é alto (1) ou baixo (0).

3.1 / álgebra booleana

Álgebra Booleana

3.1.1 Proposição e valor lógico

A proposição que só contém uma afirmação ou negação é chamada de proposição simples. As proposições simples podem ser concatenadas, gerando as proposições compostas, através de operadores lógicos, que indicam operações lógicas.

3.1.2 Operação lógica de conjunção — AND

A proposição composta S resultante da conjunção de duas proposições simples p e q é indicada por:

Lê-se "S é igual a p e q", cujo resultado depende dos valores lógicos de p e q:

3.1.3 Operação lógica de disjunção — OR

A proposição composta S resultante da disjunção de duas proposições simples p e q é indicada por:

Lê-se "S é igual a p ou q":

3.1.4 Operação de inversão lógica, negação — NOT

A proposição S resultante da operação unária (um só operando) de negação de uma proposição simples p é indicada por:

Lê-se "S é igual a não p":

3.1.5 Expressões lógicas ou booleanas

As expressões lógicas consistem na operação de proposições por meio de operadores lógicos, cujo resultado depende do valor lógico de cada proposição constituinte. Termos importantes:

• Variável lógica: representação simbólica de qualquer proposição, que assume um dos valores do conjunto $C=\{0,1\}$
• Constante lógica: um valor lógico 0 ou 1
• Função lógica: definida por uma expressão lógica (constantes e variáveis operadas), produzindo um valor 0 ou 1. Indicada por $Y=f(X_0,X_1,...,X_n)$

3.2 / tabela-verdade

Tabela-verdade

As tabelas-verdade representam todas as combinações de saída das funções de variáveis. São formadas por colunas das variáveis, colunas intermediárias (facultativas) e uma coluna de saída.

3.2.1 Exemplos de funções de três variáveis

Com três variáveis, A, B e C, há 2³ = 8 combinações. Por convenção, as linhas são listadas na ordem da contagem binária de 000 a 111, com A como bit mais significativo. As colunas intermediárias registram os termos da expressão e facilitam a verificação do resultado.

A saída vale 1 quando A e B valem 1 simultaneamente ou quando C vale 0. Pela precedência, resolve-se primeiro a negação, depois a conjunção e, por fim, a disjunção.

A saída vale 1 quando a maioria das entradas — isto é, pelo menos duas das três — vale 1. É a lógica de um sistema de votação com três votantes.

A saída vale 1 quando um número ímpar de entradas vale 1. Aqui a função é dada por uma descrição verbal; a tabela-verdade é construída diretamente pela contagem de uns em cada linha. Lendo as linhas em que P = 1, obtém-se a expressão $P = \bar{A}\bar{B}C + \bar{A}B\bar{C} + A\bar{B}\bar{C} + ABC$.

3.3 / portas lógicas

Portas lógicas

Os circuitos digitais são circuitos elétricos com elementos básicos que operam com dois níveis de sinais lógicos: H (high, alto) e L (low, baixo). O nível H é abstraído como 1, e o nível L, como 0.

As portas lógicas (gates) são dispositivos eletrônicos com duas ou mais entradas e uma saída, resultante da operação lógica das entradas em um instante. As portas básicas são: AND, OR e NOT.

3.3.1 Portas OR

Implementam a operação de disjunção.

Fabricantes como a Texas Instruments produzem portas OR como a SN54HC32/SN74HC32.

3.3.2 Portas AND

Implementam a operação de conjunção.

A Motorola fabrica portas AND como a MC14081/MC14082 (variam pelo número de entradas). A Philips também fabrica, como a 74HC08N.

3.3.3 Inversor NOT

Implementa a operação de negação.

A Philips produz os inversores 7404.

3.3.4 Os circuitos lógicos digitais

Os circuitos lógicos classificam-se em dois tipos:

Exemplo ilustrativo: um circuito com duas entradas A e B, em que a porta 1 (AND) combina A e B, a porta 2 (NOT) inverte B, e a porta 3 (OR) combina as saídas das portas 1 e 2:

Cada saída pode ser definida como uma função das entradas. Logo, a cada saída corresponde uma tabela-verdade.

3.4 / circuito somador

Circuito somador de um número de 2 bits

A soma binária é a operação aritmética fundamental de qualquer processador. Somar dois números de 2 bits, A = A₁A₀ e B = B₁B₀, produz um resultado de até 3 bits, C_outS₁S₀, pois o maior resultado possível é 3 + 3 = 6 = 110₂. O procedimento é o mesmo da soma decimal feita à mão: coluna a coluna, da direita para a esquerda, levando o vai-um (carry) para a coluna seguinte.

  vai-um:   1 1  
       A:     1 1    (3)
       B:   + 0 1    (1)
            -----
            1 0 0    (4)

Na coluna 0, 1 + 1 = 10₂: escreve-se 0 e vai 1. Na coluna 1, 1 + 0 + 1 (o vai-um) = 10₂: escreve-se 0 e vai 1, que se torna o bit mais significativo do resultado. Nota-se que a coluna 0 soma dois bits, enquanto a coluna 1 soma três (os dois bits e o vai-um). Essa diferença define os dois blocos do somador: o meio-somador e o somador completo. Antes, porém, convém apresentar uma porta adicional.

3.4.1 Porta XOR (ou-exclusivo)

A porta XOR produz 1 quando as entradas são diferentes: $S = A \oplus B = A\cdot\bar{B} + \bar{A}\cdot B$. Ela não é uma operação primitiva — pode ser construída com AND, OR e NOT —, mas é tão frequente que é fabricada como componente próprio, por exemplo o circuito integrado 74HC86, com quatro portas XOR de duas entradas.

3.4.2 Meio-somador (half adder)

Soma dois bits, A e B, e produz o bit de soma S e o vai-um C. Pela tabela-verdade, S vale 1 quando as entradas diferem (XOR) e C vale 1 apenas quando ambas valem 1 (AND).

3.4.3 Somador completo (full adder)

Soma três bits: A, B e o vai-um de entrada C_in, vindo da coluna anterior. A tabela-verdade mostra que S é a paridade ímpar das três entradas (Exemplo 3) e que C_out é a função maioria (Exemplo 2). A implementação usual reaproveita o sinal intermediário $P = A \oplus B$:

3.4.4 Somador de 2 bits

O somador de 2 bits resulta da composição dos dois blocos: um meio-somador na coluna 0 e um somador completo na coluna 1, cuja entrada C_in recebe o vai-um C₁ gerado na coluna 0. Como o vai-um “ondula” de uma coluna para a seguinte, essa organização é chamada de somador com propagação de vai-um (ripple-carry adder). Ao todo, são 7 portas e 11 sinais.

O painel abaixo do circuito mostra a análise porta a porta: cada porta é avaliada a partir dos valores presentes em suas entradas, seguindo o método da seção 3.3.4, da entrada até a saída. A Tabela 3.7 resume alguns casos.

3.5 / escalada de abstração

Do nível de lógica digital aos demais níveis

A resposta do somador pode ser analisada com graus crescentes de abstração. Em cada passo, o observador deixa de enxergar parte dos detalhes do passo anterior e passa a raciocinar com objetos mais complexos. Os três primeiros passos ainda ocorrem dentro do nível 0; os demais percorrem os níveis superiores do modelo.

3.5.1 Dentro do nível 0: das portas à caixa-preta

1. Porta a porta. É o grau mais fino de análise. Conhece-se cada uma das 7 portas e cada um dos 11 sinais; a saída é obtida propagando valores pela rede, como no painel da Figura 3.10. Esse é o único ponto de vista em que o atraso de propagação e o caminho crítico são visíveis.
2. Blocos funcionais. As portas são agrupadas em meio-somador e somador completo, cada qual descrito apenas por sua tabela-verdade. O observador passa a contar 2 blocos, não 7 portas, e já não precisa saber como cada bloco foi construído (Figura 3.11a).
3. Caixa-preta aritmética. O circuito inteiro passa a ser visto como uma função sobre números: entram A e B, sai A + B. O raciocínio deixa de ser sobre bits isolados (Figura 3.11b). Ampliado para n bits e combinado com outros blocos — operações lógicas bit a bit, deslocadores e um multiplexador que seleciona a operação —, o somador torna-se o núcleo da Unidade Lógica e Aritmética (ULA).

3.5.2 Acima do nível 0: a mesma soma em cada nível

4. Nível 1 — microarquitetura. A ULA é um componente do caminho de dados (datapath): registradores fornecem os operandos por barramentos, a ULA executa a operação e o resultado é gravado em outro registrador. As perguntas mudam: quais registradores alimentam a ULA, qual sinal de controle seleciona a soma e em que ciclo de clock o resultado é armazenado. O atraso de propagação das portas reaparece aqui de forma indireta, limitando a frequência máxima do clock.
5. Nível 2 — ISA. A soma é uma instrução de máquina, por exemplo ADD R3, R1, R2, codificada como uma palavra binária. O programador desse nível enxerga registradores, formato de instrução e flags; não enxerga a ULA nem o caminho de dados. O vai-um final (C_out) reaparece como a flag de carry. Uma mesma ISA pode ser implementada por microarquiteturas diferentes — com somador ripple-carry ou com somadores mais rápidos, como o carry-lookahead —, o que concretiza a distinção entre arquitetura e organização vista no Capítulo 2.
6. Nível 3 — máquina do sistema operacional. A instrução de soma é executada diretamente pelo nível 2, pois o SO realiza apenas uma interpretação parcial: acrescenta chamadas de sistema, memória virtual e gerência de processos. Para o SO, a soma é parte de um processo; ao trocar de processo, ele salva e restaura os registradores e as flags no contexto.
7. Nível 4 — linguagem de montagem. A instrução aparece em forma simbólica e legível, ADD R3, R1, R2, que o montador traduz para o binário do nível 2.
8. Nível 5 — linguagem orientada a problemas. O programador escreve simplesmente c = a + b;. O compilador escolhe os registradores e a instrução; o tipo da variável (por exemplo, inteiro de 32 bits) determina a largura do somador utilizado. O vai-um final, que no nível 0 era apenas um fio, aparece aqui como o fenômeno do estouro (overflow) da aritmética de inteiros.

referências

Referências

TANENBAUM, Andrew S.; AUSTIN, Todd. Organização estruturada de computadores. 6. ed. São Paulo: Pearson Prentice Hall, 2013.

TOCCI, Ronald J.; WIDMER, Neal S.; MOSS, Gregory L. Sistemas digitais: princípios e aplicações. 11. ed. São Paulo: Pearson Prentice Hall, 2011.