ENGA78 – Síntese de Circuitos Digitais 1

Máquina de Estados Finita

Wagner L. A. de Oliveira

wagner@ecomp.uefs.br

2

Como funciona uma máquina de vendas?

3

Máquina de Estados Finita É um circuito sequencial capaz de

implementar um algoritmo em hardware

Conhecida por sua sigla em inglês FSM: Finite State Machine

FSM é um modelo de comportamento, formado por um número finito de estados, transições entre tais estados e ações

4

Circuito da FSM

Decodificador de Próximo

Estado

Elementode

Memória

Decodifcadorde

SaídaEntradas Saídas

Clock

FSM de Moore (orientada a estados)

5

Circuito da FSM FSM de Mealy (orientada a transições)

6

Diagrama de estados Utilizado para descrever o

comportamento de um circuito sequencial

Formado por 2 tipos de elementos

Estado

Entradas/Saídas

EstadoSaídas

FSM de MooreFSM de Mealy

Entradas

7

Variáveis de estado São informações internas da FSM

Sinalizam o estado atual da máquina

Exemplo: Uma máquina de 7 estados terá, pelo menos, 3 variáveis de estado

EstadosdeNúmeroInteiro log2

Estado de VariáveisdeNo.

8

Variáveis de estado Há 3 formas de codificação de estados

Numeração Binária Sequencial One Hot Código Gray

9

Variáveis de estado Há 3 formas de codificação de estados

Numeração Binária Sequencial• recomendada para FSMs com poucos estados

(até 4)• utiliza o menor número de Flip-Flops (FFs)• decodificador de próximo estado mais complexo,

uma vez que utiliza todos os FFs• exige maior cuidado na verificação de

temporização, devido a maior propensão à metaestabilidade

One Hot Código Gray

10

Variáveis de estado Há 3 formas de codificação de estados

Numeração Binária Sequencial One Hot

• recomendada para FSMs entre 4 e 32 estados• número de bits (isto é, o número de variáveis)

é igual ao número de estados• para cada estado, um único bit é 1• utiliza o maior número de FFs• simplifica decodificadores (próximo estado / saída)• simplifica a verificação de temporização• opção default de ferramentas de geração

automática de FSMs para FPGA (Altera / Xilinx) Código Gray

11

Variáveis de estado Há 3 formas de codificação de estados

Numeração Binária Sequencial One Hot Código Gray

• recomendada para FSMs acima de 32 estados• número de FFs igual ao da codificação sequencial• baixa propensão à metaestabilidade

(menor que One Hot)• aumento de complexidade (tamanho do circuito)

devido a contadores Gray

12

13

Tabela de estados É a transcrição do diagrama de estados

para a forma de tabela Permite encontrar as relações binárias

entre as informações de entrada, variáveis de estado e saídas

(obs.: considerando codificação sequencial ou codificação Gray)

2)entradas. estado de variáveis.(

.nono

tabeladalinhasdeNo

14

Processo de Síntese de uma FSM

1. Definir a quantidade de estados, as entradas e as saídas Adotar uma convenção de nomenclatura Ex.: identificar variáveis de estado

por letras do começo do alfabeto e as entradas/saídas por letras do meio para o final do alfabeto

Ideal: usar nomes significativos

15

Processo de Síntese de uma FSM

1. Definir a quantidade de estados, as entradas e as saídas

2. Definir a estrutura da FSM e desenhar o diagrama de estados Escolher entre Mealy / Moore

16

Processo de Síntese de uma FSM

1. Definir a quantidade de estados, as entradas e as saídas

2. Definir a estrutura da FSM e desenhar o diagrama de estados

3. Preencher a tabela de estados Escolher a forma de

codificação de estados Calcular a quantidade de

variáveis de estado Associar estados à valoração

das variáveis de estado

17

Processo de Síntese de uma FSM

1. Definir a quantidade de estados, as entradas e as saídas

2. Definir a estrutura da FSM e desenhar o diagrama de estados

3. Preencher a tabela de estados4. Calcular as expressões booleanas

dos decodificadores Próximo Estado Saída

18

Processo de Síntese de uma FSM

1. Definir a quantidade de estados, as entradas e as saídas

2. Definir a estrutura da FSM e desenhar o diagrama de estados

3. Preencher a tabela de estados4. Calcular as expressões booleanas

dos decodificadores5. Desenhar o circuito

Definir um FF para cada variável de estado

19

Processo de Síntese de uma FSM

1. Definir a quantidade de estados, as entradas e as saídas

2. Definir a estrutura da FSM e desenhar o diagrama de estados

3. Preencher a tabela de estados4. Calcular as expressões booleanas

dos decodificadores5. Desenhar o circuito6. Verificar os estados iniciais

Definir a situação dos sinais de CLEAR e PRESET dos FFs

20

Exemplo

TANQUEBOMBA

Reservatório

HighLow

Sistema de Controle

BOMBA

Alarme

21

Exemplo: Identificando as Variáveis

De estado 4 estados 2 variáveis de estado

• A e B

Entradas 2 entradas

• H (high) e L (low)

Saídas 2 saídas

• M (motor) e A (alarme)

22

Exemplo: Fazendo o Diagrama de Estados (Modelo de Mealy)

Cheio

Vazio

EnchendoEsvaziando

HL/MA

11/00

01/0010/0111/01

01/00

00/0110/0111/00

00/0101/1010/01

01/10

00/1010/0111/01

00/00

23

Exemplo: Definindo a Estrutura da FSMFSM de Moore (orientada a estados) Os FFs compõem o elemento de memória As saídas do DPE são as entradas do EM (entradas dos FFs) As saídas do EM (saídas dos FFs) são as entradas do DS

Decodificador de Próximo

Estado

Elementode

Memória

Decodifcadorde

SaídaEntradas Saídas

Clock

24

Exemplo: Definindo a Estrutura da FSMFSM de Mealy (orientada a transições) Os FFs compõem o elemento de memória As saídas do DPE são as entradas do EM (entradas dos FFs) As entradas do circuito e as saídas do EM (saídas dos FFs) são

as entradas do DS

25

Exemplo: Preenchendo a Tabela de Estados para Síntese

ESTADO ATUAL

ENTRADAS ESTADO FUTURO

SAÍDAS SAÍDAS DO D.P.E.

Variáveis de estado

Variáveis de Entrada

Variáveis de estado

Variáveis de Saída

Entradas dos FF

26

Exemplo: Demais Tarefas

Após obter a tabela, use os conhecimentos referentes à construção de circuitos combinacionais Extraia as expressões do decodificador de saída e

do decodificador de próximo estado Simplifique tais expressões Desenhe o circuito correspondente

Por fim, defina o estado default dos sinais de CLEAR e PRESET dos FFs, de acordo com os estados iniciais

27

Processo de Análise de uma FSM

1. Calcular a quantidade de estados a partir do total de FFs Cada FF corresponde a uma

variável de estado O total de variáveis de estado

é o total de FFs

28

Processo de Análise de uma FSM

1. Calcular a quantidade de estados a partir do total de FFs

2. Identificar as entradas e saídas externas Separar as entradas e saídas de dados

das entradas de clock e RESET

29

Processo de Análise de uma FSM

1. Calcular a quantidade de estados a partir do total de FFs

2. Identificar as entradas e saídas externas3. Levantar as expressões algébricas

das saídas dos decodificadores

30

Processo de Análise de uma FSM

1. Calcular a quantidade de estados a partir do total de FFs

2. Identificar as entradas e saídas externas3. Levantar as expressões algébricas

das saídas dos decodificadores4. Preencher a tabela de estados

31

Processo de Análise de uma FSM

1. Calcular a quantidade de estados a partir do total de FFs

2. Identificar as entradas e saídas externas3. Levantar as expressões algébricas

das saídas dos decodificadores4. Preencher a tabela de estados 5. Desenhar o diagrama de estados

Informar quais são os estados iniciais, caso existam, sinalizando a operação de RESET

32

Tabela de Estados para Análise

ESTADO ATUAL

ENTRADAS SAÍDAS DO D.P.E.

ESTADO FUTURO

SAÍDAS

Variáveis de estado

Variáveis de Entrada

Entradas dos FF Variáveis de estado

Variáveis de Saída

33

Exercício (Análise)

34

Exercício (Síntese) Projete uma máquina de estados que

funcione como um contador crescente ou decrescente de 0-9. Entradas

• START/STOP• Sentido de contagem (0=crescente; 1=decrescente)• RESET• CLOCK

SAÍDAS• Valor do contador