Estudo sobre Estados de Transição

Estudo sobre Estados de Transição

Luan de Oliveira Moreira, Marcos Norberto, Mayara Dias

Universidade Estadual de Feira de Santana (UEFS) – Feira de Santana – BA - Brazil

[e-mail], [e-mail], [e-mail]

Resumo. Este artigo é referente à disciplina de Introdução ao Hardware do curso de Engenharia de Computação, da Universidade Estadual de Feira de Santana, e trata-se do produto de um problema proposto em seções de PBL que tem como finalidade compreender o funcionamento e sintetizar máquinas de estados e expor os conhecimentos específicos obtidos durante o processo de entendimento e resolução do mesmo.

1. Introdução

O projeto que nos foi passado nos introduziu a outra realidade: pensar algoritcamente mesmo em hardware. Se pensarmos bem, isso já era feito, mas só com a introdução das maquinas de estado é que sentimos essa necessidade na pele.  

As máquinas de estados foram originalmente definidas na Teoria de Autômatos e depois retomadas na Teoria da Computação. Devido sua modelagem composta por entradas, estados, transições e saídas, aliadas a simplificação mais precisa e de implementação razoavelmente fácil, elas são utilizadas tanto para a produção de hardware quanto de software.

As máquinas de estado estão geralmente associadas a dois modelos básicos, o de Moore, que possui uma função que gera uma palavra de saída (que pode ser vazia) para cada estado da máquina. Esta saída só depende do estado atual da máquina, já o de Mealy que é uma maquina modificada de forma a gerar uma palavra de saída para cada transição entre os estados. Neste tipo de máquina de estados estas palavras de saída dependem do estado atual e do valor das entradas.

A sua representação pode ser implementada por meio de diagramas de estados. A partir desses diagramas são feitas tabelas, que expressam todas as informações sobre as entradas e saídas, no acaso de hardware, a partir das expressões fornecidas por essas tabelas o projeto do circuito é montado.

O projeto a descrito a seguir é uma demonstração da utilização de uma maquina de estados para uma situação de automação do processo de embalagem de alguns produtos.

2. Metodologia

Para elaborar o circuito, primeiramente foi feito o diagrama de estados mostrando as possíveis transições ocorridas em cada estado, em relação a uma determinada entrada do circuito. Com o diagrama foi possível elaborar a tabela de estados do projeto, fundamental para a construção do circuito.

O próximo passo foi retirar as expressões do decodificador de próximo estado e do decodificador de saída do circuito e fazer a simplificação booleana com o auxílio do mapa de Karnaugh de 6 variáveis.

 A partir daí foi possível implementar o circuito usando o software “Quartus II” como ferramenta. O circuito é composto por 4 flip-flops e circuitos combinacionais.

        Após a implementação, foram realizados testes para constatar a eficácia da máquina de estados. Um dos testes verificou se havia descarte de objetos, quando sua repetição passava de 2 vezes. Outros testes foram feitos com o intuito de verificar se as saídas se comportavam perfeitamente quando recebidas 3 palavras iguais, em ordens diferentes e o comportamento do circuito quando recebe a palavra 00.

        Os detalhes sobre o projeto, sua implementação e os testes realizados serão discutidos na seção 3, “Descrição do Projeto” e 4,  Resultados das Simulações”.

3. Descrição do Projeto

De acordo com as especificações do problema, três tipos de componentes (resistores, capacitores e transistores) contidos inicialmente em um mesmo recipiente deveriam ser embalados em pacotes contendo quatro produtos. Este processo deveria ser feito de maneira que houvesse a repetição de, no máximo, dois componentes de um mesmo tipo. Com base nos critérios descritos, foi projetado um circuito digital com a função de realizar o controle deste processo.

O projeto do circuito foi dividido em: elaboração do diagrama de estados, desenvolvimento da tabela de estados, cálculo das expressões dos decodificadores e implementação do circuito.  

O diagrama de estados foi desenvolvido com base nas situações de entrada que o projeto poderá receber no decorrer do processo de empacotamento e quais saídas ele deverá gerar. Como entradas, são usadas palavras de dois bits (01, 10, 11), representando cada um dos três tipos de produto, além destas, há uma entrada que representa a recepção de um produto nulo (00), indicando que o recipiente está vazio ou o sensor não detectou presença de elemento algum. Foram pensadas três saídas, sendo elas: acionamento do motor de descarte, ativação de alarme e acionamento de um motor que irá dar o processo de empacotamento como terminado. A saída do motor de descarte será ativa caso o circuito receba mais de duas entradas repetidas ou uma entrada nula, situação que também irá ativar o alarme. Quando o pacote contiver 4 componentes, não havendo a repetição de mais de dois produtos do mesmo tipo ou entrada nula, a saída do motor de término de operação será ativa.

O diagrama inicial apresentava 37 estados, porém com a análise de cada um destes, foi possível identificar estados que, com as mesmas entradas geravam saídas iguais, considerados então como iguais, sendo assim possível simplificar o diagrama. A primeira simplificação gerou a redução para 17 estados (ANEXO E). Apesar de simplificado, o diagrama ainda apresentava estados iguais, então sucessivo a esta ultima citada, foi possível uma outra redução, que resultou na presença final de um total de 14 estados diferentes. O diagrama pode ser visualizado no Anexo 1.  

O número de variáveis de estado necessárias para o desenvolvimento da tabela de estados segue a seguinte fórmula:

[pic 1]

O que resulta em um total de 4 variáveis de estado, sendo possível uma contagem de 0000 a 1111, ou seja de 0 a 15, possibilitando que se nomeie 16 estados. Como o diagrama apresentou somente 14, haverá 2 estados Don´t Care, sendo convencionado para eles as saídas que ativam o alarme e o descarte independente de quais entradas o circuito receba.  

Os 4 Flip-Flops optado para o elemento de memória foram do tipo D, que contém a seguinte tabela de excitação: