Portas e Álgebra Booleana

Prévia do material em texto

Organização e Arquitetura de Computadores 
Aula 02 
 
Prof. Harlei Miguel de Arruda Leite 
Sumário 
• Organização Estruturada de Computadores 
• Portas e Álgebra Booleana 
• Homework 
• Referências 
Organização Estruturada de Computadores 
• Introdução 
 
– Existe uma grande lacuna entre o que é conveniente para as pessoas e o que 
é conveniente para computadores. As pessoas querem fazer X, mas os 
computadores só podem fazer Y, o que dá origem a um problema. 
 
• Linguagens, níveis e máquinas virtuais 
 
– O problema pode ser abordado de duas maneiras, e ambas envolvem 
projetar um novo conjunto de instruções que é mais conveniente para as 
pessoas usarem do que o conjunto embutido de instruções de máquina. 
 
– Juntas, essas novas instruções também formam uma linguagem, que 
chamaremos de L1, assim como as instruções de máquina embutidas formam 
uma linguagem, que chamaremos de L0. 
 
 
Organização Estruturada de Computadores 
• Linguagens, níveis e máquinas virtuais 
 
– Um método de execução de um programa escrito em L1 é primeiro substituir 
cada instrução nele por uma sequência equivalente de instruções em L0. O 
programa resultante consiste totalmente em instruções L0. O computador, 
então, executa o novo programa L0 em vez do antigo programa L1. Essa 
técnica é chamada de tradução. 
 
– A outra técnica é escrever um programa em L0 que considere os programas 
em L1 como dados de entrada e os execute, examinando cada instrução por 
sua vez, executando diretamente a sequência equivalente de instruções L0. 
Essa técnica não requer que se gere um novo programa em L0. Ela é chamada 
de interpretação, e o programa que a executa é chamado de interpretador. 
Organização Estruturada de Computadores 
• Linguagens, níveis e máquinas virtuais 
 
– Tradução e interpretação são semelhantes. Nos dois métodos, o computador 
executa instruções em L1 executando sequências de instruções equivalente 
em L0. 
 
– A diferença é que, na tradução, o programa L1 inteiro primeiro é convertido 
para um L0, o programa L1 é desconsiderado e depois o novo L0 é carregado 
na memória do computador e executado. 
 
– Na interpretação, depois que cada instrução L1 é examinada e decodificada, 
ela é executada de imediato. Nenhum programa traduzido é gerado. Aqui, o 
interpretador está no controle do computador. Para ele, o programa L1 é 
apenas dados. 
Organização Estruturada de Computadores 
• Linguagens, níveis e máquinas virtuais 
 
– Em vez de pensar em termos de tradução ou interpretação, muitas vezes é 
mais simples imaginar a existência de um computador hipotético ou máquina 
virtual cuja linguagem seja L1. Vamos chamar essa máquina virtual de M1. 
 
– Para tornar prática a tradução ou a interpretação, as linguagens L0 e L1 não 
deverão ser “muito” diferentes. Sendo assim, L1 ainda é mais próxima da 
máquina do que do humano. Uma abordagem para solucionar isso seria criar 
um novo conjunto de instruções que seja mais orientado a pessoas e menos 
orientado a máquinas que a L1. 
 
– As pessoas poderiam escrever em L2 como se de fato existisse uma máquina 
real com a linguagem L2. Esses programas podem ser traduzidos para L1 ou 
executados por um interpretador escrito em L1. 
Organização Estruturada de Computadores 
• Linguagens, níveis e máquinas virtuais 
 
– A invenção de toda uma série de linguagens, cada uma mais conveniente que 
suas antecessoras, pode prosseguir indefinidamente, até que, por fim, se 
chegue a uma adequada. 
 
– Cada linguagem usa sua antecessora como base, portanto, podemos 
considerar um computador que use essa técnica como uma série de camadas 
ou níveis, um sobre o outro. 
 
– A linguagem ou nível mais embaixo é a mais simples, e a linguagem ou nível 
mais em cima é a mais sofisticada. 
Organização Estruturada de Computadores 
• Linguagens, níveis e máquinas virtuais 
 
 
Máquina virtual Mn, com 
linguagem de máquina Ln 
Máquina virtual M3, com 
linguagem de máquina L3 
Máquina virtual M2, com 
linguagem de máquina L2 
Máquina virtual M1, com 
linguagem de máquina L1 
Computador real M0, com 
linguagem de máquina L0 
Nível n 
Nível 3 
Nível 2 
Nível 1 
Nível 0 
Programas em Ln são interpretados por um interpretador 
rodando em uma máquina de nível inferior ou são traduzidos 
para a linguagem de máquina de uma máquina de nível inferior 
Programas em L2 são interpretados por interpretadores 
rodando em M1 ou M0, ou são traduzidos para L1 ou L0 
Programas em L1 são interpretados por interpretadores 
rodando em M0, ou são traduzidos para L0 
Programas em L0 podem ser executados diretamente 
pelos circuitos eletrônicos 
Organização Estruturada de Computadores 
• Linguagens, níveis e máquinas virtuais 
 
– Cada máquina tem uma linguagem de máquina, consistindo em todas as 
instruções que esta pode executar. Com efeito, uma máquina define uma 
linguagem. De modo semelhante, uma linguagem define uma máquina. 
 
– De certa forma, um computador com n níveis pode ser visto como n 
diferentes máquinas virtuais, cada uma com uma linguagem de máquina 
diferente. Os termos “nível” e “máquina virtual” indica a mesma coisa. 
 
– Abaixo do nível 0 existe mais um nível, chamado de nível de dispositivo. Nele, 
o projetista vê transistores individuais, que são os primitivos de mais baixo 
nível para projetistas de computador. Se alguém quiser saber como os 
transistores funcionam no interior, isso nos levará para o campo da física no 
estado sólido. 
Organização Estruturada de Computadores 
• Máquinas multiníveis contemporâneas 
 
– A maioria dos computadores modernos consistem de dois ou mais níveis. 
Existem máquinas com até seis níveis. 
Organização Estruturada de Computadores 
• Máquinas multiníveis contemporâneas 
 
Nível lógico digital 
Nível de microarquitetura 
Nível de arquitetura do conjunto de instrução 
Nível de máquina do sistema operacional 
Nível de linguagem de montagem (Assembly) 
Nível de linguagem orientada a problemas 
Nível 0 
Nível 1 
Nível 2 
Nível 3 
Nível 4 
Nível 5 
Tradução (compilador) 
Tradução (montador ou assembler) 
Interpretação parcial (sistema operacional) 
Interpretação (microprograma) ou execução direta 
Hardware 
(gates – constituídos de 
transistores – e registradores – 
que compõem a memória) 
(registradores e o circuito ALU – 
 Arithmetic Logic Unit) 
(instruções de máquina) 
(instruções para permitir 
concorrência e uma organização 
diferente da memória) 
(mnemônicos para as 
Instruções de máquina) 
(BASIC, C, C++, Java, 
LISP, Prolog, ...) 
Organização Estruturada de Computadores 
Portas e Álgebra Booleana 
• Portas 
 
– Um circuito digital é aquele em que estão presentes somente dois valores 
lógicos. O normal é que um sinal entre 0 e 0.5 volt represente um valor (por 
exemplo, 0 binário) e um sinal entre 1 e 1.5 volt represente o outro valor (por 
exemplo, 1 binário). Não são permitidas tensões fora dessas duas faixas. 
 
– Minúsculos dispositivos eletrônicos, denominados portas (gates), podem 
calcular várias funções desses sinais de dois valores. 
 
– Essas portas formam a base do hardware sobre a qual todos os 
computadores digitais são construídos. 
Portas e Álgebra Booleana 
• Principais elementos 
 
– As cinco portas da figura abaixo são os principais elementos de construção do 
nível lógico digital 
Portas e Álgebra Booleana 
• Álgebra Booleana 
 
– Para descrever os circuitos que podem ser construídos combinando portas, é 
necessário um novo tipo de álgebra, no qual variáveis e funções podem 
assumir somente os valores 0 e 1. 
 
– Essa álgebra é denominada álgebra booleana, nome quese deve a seu 
descobridor, o matemático inglês George Boole (1815-1864). 
 
– Assim como há funções na álgebra “ordinária”, também há funções na 
álgebra booleana. 
 
– Uma função booleana tem uma ou mais variáveis de entrada e produz um 
resultado que depende somente dos valores dessas variáveis. 
 
 
Portas e Álgebra Booleana 
• Álgebra Booleana 
 
– Uma função simples, f, pode ser definida ao se dizer que f(A) é 1 se A for 0 e 
F(A) é 0 se A for 1. Essa função é a função NOT. 
Portas e Álgebra Booleana 
• Álgebra Booleana 
 
– Como uma função booleana de n variáveis só tem 2n combinações possíveis 
de valores de entrada, ela pode ser completamente descrita por uma tabela 
com 2n linhas, na qual cada linha informa o valor da função para uma 
combinação diferente de valores de entrada. Ela é denominada tabela 
verdade. 
Portas e Álgebra Booleana 
• Exemplo 
 
– A figura abaixo mostra a tabela verdade para uma função booleana de três 
variáveis: M= f(A,B,C). Essa função é a de lógica majoritária, isto é, ela é 0 se 
a maioria de suas entradas for 0, e 1 se a maioria de suas entradas for 1. 
Portas e Álgebra Booleana 
• Álgebra Booleana 
 
– Embora qualquer função booleana possa ser completamente especificada 
dada sua tabela verdade, à medida que aumenta o número de variáveis, essa 
notação fica cada vez mais trabalhosa. Portanto, costuma-se usar outra 
notação no lugar dela. 
 
– Para ver como ocorre essa outra notação, observe que qualquer função 
booleana pode ser especificada ao se dizer quais combinações de variáveis 
de entrada dão um valor de saída igual a 1. Para a função da figura anterior, 
há quatro combinações de variáveis de entrada que fazem com que M seja 1. 
 
– Por convenção, marcaremos a variável de entrada com uma barra para 
indicar que seu valor é invertido. A ausência de uma barra significa que o 
valor não é invertido. 
Portas e Álgebra Booleana 
• Álgebra Booleana 
 
– Além disso, usaremos a multiplicação implícita ou um ponto para representar 
a função booleana AND e + para representar a função booleana OR. Assim, 
por exemplo, 𝐴𝐵 𝐶 assume o valor 1 somente quando A = 1 e B = 0 e C = 1. 
 
– Outro exemplo, 𝐴𝐵 + 𝐵𝐶 é 1 somente quando 
• (A = 1 e B = 0) ou (B = 1 e C = 0). 
 
– As quatro linhas da figura anterior que produzem bits 1 na saída são: 𝐴 𝐵𝐶, 
𝐴𝐵 𝐶, 𝐴𝐵𝐶 e 𝐴𝐵𝐶. A função, M, é verdadeira (isto é, 1) se qualquer uma 
dessas quatro condições for verdadeira. 
 
– 𝑀 = 𝐴 𝐵𝐶 + 𝐴𝐵 𝐶 + 𝐴𝐵𝐶 + 𝐴𝐵𝐶 
Portas e Álgebra Booleana 
• Álgebra Booleana 
 
– Pelo exemplo anterior, deve ficar claro como colocar em prática um circuito 
para qualquer função booleana 
 
1. Escreva a tabela verdade para a função. 
2. Providencie inversores para gerar o complemento de cada entrada. 
3. Desenhe uma porta AND para cada termo que tenha 1 na coluna de resultado. 
4. Ligue as portas AND às entradas adequadas 
5. Alimente a saída de todas as portas AND a uma porta OR. 
Portas e Álgebra Booleana 
• Álgebra Booleana 
 
– Muitas vezes é conveniente realizar circuitos usando só um tipo de porta. 
Felizmente, converter circuitos gerados pelo algoritmo precedente à forma 
NAND pura ou NOR pura é uma operação direta. 
 
– Para fazer essa conversão, basta que tenhamos um modo de implementar 
NOT, AND e OR usando um único tipo de porta. 
Portas e Álgebra Booleana 
• Álgebra Booleana 
 
– Construção de portas (a) NOT, (b) AND e (C) OR usando portas NAND ou 
somente portas NOR. 
 
Portas e Álgebra Booleana 
• Álgebra Booleana 
 
– Embora esse procedimento não resulte em circuitos ótimos, no sentido do 
número mínimo de portas, ele mostra que sempre há uma solução viável. 
 
– Ambas as portas, NAND e NOR, são denominadas completas porque 
qualquer função booleana pode ser calculada usando quaisquer das duas. 
 
– Nenhuma outra porta tem essa propriedade, o que é outra razão para elas 
serem preferidas como blocos de construção de circuitos. 
Portas e Álgebra Booleana 
• Exercício 
 
– Dados os diagramas abaixo, descreva as expressões relacionadas a cada um. 
Portas e Álgebra Booleana 
• Exercício 
 
– Dados os diagramas abaixo, descreva as expressões relacionadas a cada um. 
 
Portas e Álgebra Booleana 
• Exercício 
 
– Implementação de circuitos lógicos à partir de expressões. Considerando as 
expressões abaixo, construa os circuitos equivalentes. 
 
– 𝑋 = 𝐴𝐵 + 𝐵 𝐶 
– 𝑋 = 𝐴𝐶 + 𝐵𝐶 + 𝐴 𝐵𝐶 
 
 
 
 
Portas e Álgebra Booleana 
• Exercício (Solução) 
 
 
Homework 
• Atividade de Leitura 
 
– Ler o capítulo 1 
– Ler o capítulo 3 (3.1) 
Referências 
• Tanenbaum, A. S.; Austin, T. Organização Estruturada de 
Computadores. 6ª Edição, Editora Pearson, 2013.