Solucionador de circuitos lógicos em C++

UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE DEPARTAMENTO DE ENGENHARIA DE COMPUTAÇÃO E AUTOMAÇÃO – DCA

Solucionador de circuitos lógicos em C++

Camila de Oliveira Silva, 2009028716 Victor Neves Nogueira, 2009030702

Natal, 04 de novembro de 2011.

Resumo

O presente trabalho consiste na aplicação dos conceitos de programação orientada a objetos na lógica combinacional de circuitos, no contexto da obtenção da tabela-verdade a partir de um arquivo contendo dados de um circuito lógico descrito em linguagem formal. Na parte inicial do trabalho, serão apresentados os conceitos referentes à lógica combinacional de circuitos e programação orientada a objetos. Em um momento posterior, será realizada a correta modelagem do problema da tabela-verdade. A seguir, todos os detalhes de implementação desse programa, na linguagem C++, serão apresentados. Alguns circuitos de teste servirão de entrada para o projeto, e os resultados obtidos serão comentados. Finalmente, será feita uma breve conclusão sobre os resultados obtidos, bem como uma análise da possibilidade de melhorias e trabalhos futuros.

Conteúdo 1 Introdução

6

2 Desenvolvimento

7

2.1 Bases teóricas

7

2.1.1 Lógica combinacional de circuitos

7

2.1.2 Programação orientada a objetos

13

2.2 Especificações e descrições do projeto

13

2.3 Implementação do projeto

15

3 Resultados 3.1 Teste e validação do projeto 4 Conclusões

19 19 24

Lista de Figuras

2.1

Representação de um circuito combinacional

8

2.2

Representação de uma porta OR

8

2.3

Representação de uma porta AND

9

2.4

Representação de uma porta NOT

10

2.5

Representação de uma porta NOR

10

2.6

Representação de uma porta NAND

11

2.7

Circuito combinacional de uma porta XOR

11

2.8

Representação de uma porta XOR

12

2.9

Circuito combinacional de uma porta XNOR

12

2.10

Representação de uma porta XNOR

13

2.11

Circuito combinacional a ser avaliado

14

2.12

Modelo de arquivo texto com a especificação do circuito

14

2.13

Resultado gerado

15

2.14

Trecho do código em C++

15

2.15

Outro trecho do código em C++

17

3.1

Circuito 2

19

3.2

Especificação do circuito 2

20

3.3

Saída do programa para o circuito 2

21

3.4

Circuito 3

22

3.5

Especificação do circuito 3

22

3.6

Saída do programa para o circuito 3

23

Lista de Tabelas

2.1 Tabela Verdade da porta OR

8

2.2 Tabela Verdade da porta AND

9

2.3 Tabela Verdade da porta NOT

9

2.4 Tabela Verdade da porta NOR

10

2.5 Tabela Verdade da porta NAND

11

2.6 Tabela Verdade da porta XOR

12

2.7 Tabela Verdade da porta XNOR

13

Capítulo1 Introdução

Hoje em dia, o termo “digital” tornou-se parte do nosso vocabulário diário devido ao modo intenso pelo qual os circuitos digitais e as técnicas digitais passaram a ser amplamente utilizados em quase todas as áreas: computadores, automação, robôs, tecnologia e ciência médica, transportes, entretenimento, exploração espacial e assim por diante. Nesse contexto, torna-se útil inserir a programação orientada a objetos para resolver problemas na lógica combinancional de circuitos, já que é uma maneira mais clara e fácil de programação e o código torna-se mais flexível. Este relatório busca citar vantagens e explicar os métodos que foram utilizados para gerar um programa que mostra todas as possíveis soluções de um circuito digital, em C++. Para tanto, optamos por modelar o sistema de uma forma clara, bem como utilizar os conceitos e métodos já existentes na linguagem orientada a objetos para apresentarmos a solução, unindo os conceitos de portas lógicas (AND, OR, XOR, NOT, XNOR, NAND, NOR), números binários e manipulação de arquivos.

6

Capítulo 2 Desenvolvimento 2.1 - Bases teóricas 2.1.1) Lógica combinacional de circuitos a) Circuitos Lógicos

Os circuitos digitais operam no modo binário, em que cada tensão de entrada e saída é 0 ou 1. Uma tabela-verdade é uma técnica para determinar como a saída de um circuito lógico depende dos níveis lógicos presentes nas entradas do circuito. Essa tabela relaciona todas as combinações possíveis para os níveis lógicos presentes nas entradas com o correspondente nível lógico na saída. Logo, se tivermos n entradas, a tabela conterá 2𝑛 linhas diferentes relacionando entradas com saídas.

b) Topologia do circuito

Considera-se um circuito combinancional composto por portas lógicas ligadas por fios de interconexão. Por simplicidade, é assumido que cada porta lógica possui uma saída e uma ou duas entradas. Cada saída é conectada à entrada de outra porta lógica, ou é uma saída primária do circuito, enquanto que cada entrada é conectada à saída de outra porta lógica, ou é uma entrada primária do circuito. Também assumimos que o caminho é acíclico, ou seja, não há caminhos que levam a mesma porta lógica ao percorrer tal circuito. Pode-se, então, representar o circuito por um grafo acíclico direto (DAG – Directed Acyclic Graph), onde cada nodo representa uma porta lógica, e cada arco representa uma interconexão. A figura abaixo representa um circuito com três entradas (A, B e C), uma saída (D), e oito portas lógicas.

7

Figura 2.1: Representação de um circuito

c) Operações em circuitos lógicos 

Porta OR A operação mostra que a saída de uma porta OR com várias entradas terá nível

lógico 1 quando pelo menos uma entrada tiver nível lógico 1. Sejam A e B, por exemplo, duas entradas de uma porta NOR, dizemos que x é a saída e x=A+B é a expressão lógica desta porta. As figuras abaixo mostram a sua tabela verdade, bem como a sua representação: Tabela 2.1: Tabela Verdade da porta OR

A

B

x

0

0

0

0

1

1

1

0

1

1

1

1

Figura 2.2: Representação de uma porta OR

8



Porta AND A saída de uma porta AND só terá nível 1 quando todas as suas entradas forem de

nível lógico 1. Para duas entradas A e B, a expressão lógica para essa porta para a saída x é x = A.B. As figuras abaixo mostram a tabela verdade dessa porta para duas entradas, bem como a sua representação: Tabela 2.2: Tabela Verdade da porta AND

A

B

x

0

0

0

0

1

0

1

0

0

1

1

1

Figura 2.3: Representação de uma porta AND



Porta NOT Essa porta, também chamada de inversor, recebe apenas uma entrada e sua saída

será o inverso do nível lógico de entrada. Abaixo estão representados expressão lógica, tabela verdade, bem como a sua representação:

x=A Tabela 2.3: Tabela Verdade da pota NOT

A

x

0

1

1

0

9

Figura 2.4: Representação de uma porta NOT



Portas NOR e NAND

Dois outros tipos de portas lógicas, as portas NOR e NAND, são muito utilizadas em circuitos lógicos. A porta NOR é uma porta OR seguida de um inversor. Logo, a saída desta porta só será 1 quando todas as entradas tiverem nível lógico 0.

x=𝐴+𝐵 Tabela 2.4: Tabela Verdade de porta NOR

A

B

x

0

0

1

0

1

0

1

0

0

1

1

0

Figura 2.5: Representação de uma porta NOR

Já a porta NAND é uma porta AND seguida de um inversor. Dessa maneira, a sua saída terá nível lógico 0 apenas quando todas as entradas tiverem nível lógico 1.

x = 𝐴. 𝐵

10

Tabela 2.5: Tabela Verdade de uma porta NAND

A

B

x

0

0

1

0

1

1

1

0

1

1

1

0

Figura 2.6: Representação de uma porta NAND



Porta XOR

Essa porta deriva de um circuito combinancional com portas OR e AND, também chamado de Exclusive-OR. O circuito combinacional Exclusive-OR está representado abaixo:

Figura 2.7: Circuito combinacional da porta XOR

Nele, observamos que a saída x terá nível lógico 1 apenas quando as entradas tiverem níveis lógicos opostos, ou seja:

x = 𝐴B + A𝐵

11

Tabela 2.6: Tabela Verdade da porta XOR

A

B

X

0

0

0

0

1

1

1

0

1

1

1

0

Ao invés de desenhar todo este circuito, podemos optar por uma representação mais simplificada para ele, que é a porta XOR mostrada abaixo:

Figura 2.8: Representaçãol da porta XOR

Diferentemente das outras portas, esta tem apenas duas entradas. 

Porta XNOR

O circuito que esta porta representa atua de forma inversa à lógica da porta XOR: a saída estará em nível ALTO (nível lógico 1) apenas quando as entradas tiverem níveis lógicos iguais. Da mesma forma, este circuito aceita apenas duas entradas e está representado abaixo:

Figura 2.9: Circuito combinacional da porta XNOR

12

O desenho simplificado é a porta XOR seguida de um inversor:

x = 𝐴𝐵 + AB

Figura 2.10: Representação da porta XNOR

Tabela 2.7: Tabela Verdade da porta XNOR

A

B

X

0

0

1

0

1

0

1

0

0

1

1

1

2.1.2) Programação orientada a objetos Objetos são instâncias de classes, que determinam qual informação um objeto contém e como ele pode manipulá-la. Um programa desenvolvido com uma linguagem de programação orientada a objetos manipula estruturas de dados através dos objetos da mesma forma que um programa em linguagem tradicional utiliza variáveis. Um dos grandes diferenciais da programação orientada a objetos em relação a outros paradigmas de programação está no conceito de herança, mecanismo através do qual definições existentes podem ser facilmente estendidas. Juntamente com a herança, deve ser enfatizada a importância do polimorfismo, que permite selecionar funcionalidades que um programa irá utilizar de forma dinâmica, durante sua execução.

2.2 Especificações e descrições do projeto 13

O projeto baseia-se na construção de um programa em C++ que calcule tabelasverdade para circuitos lógicos combinacionais descritos em linguagem formal de especificação de circuito. Esta ferramenta lê a descrição de um dado circuito escrito em um arquivo de texto simples e então apresenta os resultados da expressão lógica correspondente. Seja o circuito combinacional abaixo (figura 2.11):

Figura 2.11: Exemplo de circuito combinacional

Como exemplo dado, o programa deve ler o arquivo de texto abaixo (figura 2.12), que é a interpretação do circuito acima, e imprimir na tela o que mostra na figura 2.13:

Figura 2.12: Modelo de arquivo de texto com as especificações do circuito acima

14

Figura 2.13: Resultado gerado

2.3 – Implementação do projeto Começamos elaborando o arquivo texto que serviu como a entrada do programa. Com ele pronto, tivemos a base para programação da ferramenta. Utilizamos as seguintes bibliotecas: iostream, fstream, sstream, cmath, vector, queue e set. Posteriormente, criamos duas classes: Conexão e Circuito.

15

Figura 2.14: Trecho do código em c++

A primeira recebe os dados de cada linha do arquivo texto e armazena-os em variáveis inteiras (entrada1, entrada2, porta, saida). O valor constante lido antes de ser armazenado em ‘porta’ é uma string (visto que estamos lidando com as palavras INPUT, OUTPUT, AND, OR, NOT, NOR, NAND, XOR, XNOR) que será substituído por um número de 1 a 7, caso seja uma porta lógica, ou ficará armazenado em um vetor de inteiros chamado ‘inCircuito’ (localizada na classe Circuito), se for uma entrada independente, ou em um vetor de inteiros chamado ‘outCircuito’ (que está na classe Circuito), se for uma saída independente. Já a classe Circuito armazena os objetos “Conexão” lidos durante a execução do programa. Para isso, ela possui um vector , ou seja, um vetor de conexões, e verifica se as leituras estão sendo feitas com sucesso. Caso o armazenamento tenha sido feito de forma eficiente, é esta classe que chamará outras funções para manipularem esse vetor. Na função void resolver (), serão armazenados apenas os valores das saídas em uma fila chamada ‘caixaDeSaidas’. Posteriormente, a partir do vetor ‘inCircuito’ e da fila ‘caixaDeSaidas’, será construída uma matriz de

2𝑖𝑛𝐶𝑖𝑟𝑐𝑢𝑖𝑡𝑜.𝑠𝑖𝑧𝑒()

linhas e

(inCircuito.size() + caixaDeSaidas.size()) colunas. Se, para fins de entendimento, chamo de n o número retornado por inCircuito.size(), as n entradas independentes serão preenchidas na matriz desde 0000...n a 1111...n. Como a matriz começa na posição 0 e as entradas começam a partir do número 1, a matriz será preenchida sempre no valor da entrada menos 1. Desde que as entradas independentes sejam preenchidas de antemão na sua posição devida, o programa preenche a coluna da saída na posição (saída – 1). O trecho do código abaixo é a função 16

que retorna a matriz aonde serão colocados os resultados:

Figura 2.15: Outro trecho do código em c++

A matriz retornada será usada enquanto houver portas a serem resolvidas. Para resolver as portas, foi utilizada a teoria das filas (queue), onde o primeiro elemento da fila será pesquisado na matriz, a fim de vermos se a porta já foi ou não encontrada. Se já 17

tiver sido encontrada, o elemento da fila é excluído e o próximo será pesquisado. Se o elemento da fila não tiver sido encontrado e se as entradas pelas quais ele provém já estiverem completas, então esta porta será resolvida e colocada na matriz; se não, o elemento sai do início da fila e vai para o final. Dessa forma, é completada a matriz, ou seja, a tabela verdade do circuito. Melhorando a saída do programa para que fique com uma formatação igual a da saída da figura 13, o programa está pronto para ser usado.

18

Capítulo 3 Resultados

3.1- Teste e validação do projeto Na etapa de teste do programa, vários circuitos combinacionais podem ser fornecidos como entrada. Apenas devemos nos atentar para o fato de que o número que alguma porta deve ter tem que começar do valor ‘1’ e seguir até quantas portas existirem, sem que haja ‘pulos’ de números. As entradas independentes podem ser as primeiras portas a serem enumeradas, ou não. A validação do projeto consiste em comparar o resultado obtido nos testes com o resultado feito separadamente. Com isso, espera-se saber se o programa feito é eficiente quanto aos seus resultados. Observando o circuito abaixo (figura 3.1), cuja descrição está mostrada logo após (figura 3.2), o resultado gerado pelo programa está descrito na figura 3.3:

Figura 3.1: Circuito 2

19

Figura 3.2: Especificação do circuito 2

20

Figura 3.3: Saída do programa para o circuito 2

O segundo circuito a ser avaliado está mostrado abaixo (figura 3.4), bem como sua especificação (figura 3.5). O resultado dado pelo programa está mostrado na figura 3.6:

21

Figura 3.4: Circuito 3

Figura 3.5: Especificação do circuito 3

22

Figura 3.6: Saída do programa para o circuito 3

23

Capítulo 4 Conclusões

A utilização de programação orientada a objetos torna a idealização dos algoritmos muito mais prática, por permitir entender o código como uma abstração do mundo real, utilizando interação entre objetos. Ao que o trabalho propôs-se, os resultados obtidos através do programa foram corretos, e utilizar a programação orientada a objetos como o instrumento de efetivar essa atividade mostrou-se bastante eficiente.

24

Referências bibliográficas  Manual de Referência do C++ , disponível em http://www.cplusplus.com/reference, acessado em 6 de novembro.  The Eletronics Club – Logic Gates, disponível em http://www.kpsec.freeuk.com/ gates .htm, acessado em 26 de outubro.  O que é a programação orientada a objetos, disponível em http://www.criarweb. com/artigos/215.php, acessado em 13 de novembro.  Programação Orientada a objetos, disponível em http://www.hardware.com .br/artigos/programacao-orientada-objetos/, acessado em 19 de novembro de 2011.

25