ED4 - Maquinas de Estados - Projeto Parte I

Máquinas de Estados Finitos - FSMIntrodução e Projeto

24453F-02 - Eletrônica Digital (ECA)

Máquinas de Estados - Definição

Máquina de Estados Finitos ou Finite State Machine (FSM)

Uma máquina de estados representa um sistema comoum conjunto de estados, a transição entre eles, emconjunto com as entradas e saídas associadas.

Máquinas de estados podem ser utilizadas em outrassituações além de projeto de circuitos digitais earquitetura de computadores.


Finite State Machines

Qualquer circuito com memória é uma Máquina de Estados Finitos

Computadores podem ser vistos como grandes Máquinas de Estados

O projeto de Máquinas de Estados Finitos envolve

Definição dos Estados

Definição da Transição entre Estados

Otimização / Minimização dos Estados e Transições


Aplicações - Exemplos

Circuitos Seqüenciais Complexos

Controladores de seqüências.

Lavadora de Roupas

Fornos de Microondas

Videocassetes

CD Players


Exemplos

Máquina de Lavar Roupa

Seqüência de Estados

Desligada

Enchendo

Molho (Cheia)

Lavando (Batendo)

Molho (Cheia)

Esvaziar

Centrifugar

Desligar

Level Sensor


Diagrama de Estados - Telefone

IDLE (telefone no gancho)


Diagrama de Estados

Dispensador de Refrigerantes


Termos e Definições

Diagrama de Estados

Mostra a forma e a funcionalidade de uma máquina de estados.

Estados

Conjunto de valores unicamente identificáveis.

Transição de Estados

A troca do estado atual para o próximo estado baseado nas variáveis de entrada.


Termos e Definições

Estado Atual

O estado onde a FSM está em determinado momento.

Próximo Estado

O estado para o qual a FSM faz a próxima transição determinada pelas entradas no momento em que ocorre um sinal de clock.

Máquina Moore

Modelo de FSM onde a Saída depende somente do estado atual.

Máquina Mealy

Modelo de FSM onde a Saída depende do estado atual e das variáveis de entrada.


Máquinas Moore e Mealy

Os dois tipos de máquinas seguem as características básicas de uma máquina de estados, mas diferem em como as saídas são determinadas.

Máquina Moore: As saídas são independentes das entradas, isto é, as

saídas são determinadas somente a partir do estado atual da máquina de estados.

Máquina Mealy: As saídas podem ser determinadas somente pelo estado

atual ou pelo estado atual e as entradas atuais, isto é, as saídas são determinadas enquanto a máquina faz a transição de um estado para outro estado.


Modelos de Máquinas


Arquitetura Moore

Lógica dePróximoEstado

Decodificadordo Estado Atual

para Saída

Elementode Memória

FF D,T,JK

Variáveisde Entrada

SaídaDesejada

A saída depende somente do estado atual.

Decodificador

F FDecodificador

F F

Clock

LPE=f (EA,X)X

S=f (EA)

SaídaEA

EA


Arquitetura Moore

A saída depende somente do estado atual.


Arquitetura Mealy



para Saída

Elementode Memória

FF D,T,JK


SaídaDesejada

A saída depende do estado atual e da entrada.

DecodificadorF F

Decodificador

F F

Clock

S=f (EA,X)X

Saída

LPE=f (EA,X)

EA

EA


Arquitetura Mealy

A saída depende do estado atual e da entrada.



Moore MealyEntradas

Lógica Comb.para Determinar

o Estado

Estado AtualFF

Lógica Comb.para Determinar asaída Baseado no:

Estado Atual

Saída

Entradas

Lógica Comb.para Determinar

o Estado

Estado AtualFF

Lógica Comb.para Determinar asaída Baseado no:

Estado Atual Entradas Atuais

Saída



Moore

MealyX Deco

dificadorF FDeco

dificador

F F

Clock

S=f (EA,X)

Saída

LPE=f (EA,X)

Decodificador

F FDecodificador

F F

Clock

LPE=f (EA,X)X

S=f (EA)

Saída


Diagrama de Estados - Moore

Denominação do Estado

Saída Desejada para o Estado

Condição das variáveis de entrada para transição de estados

A4

B5

Variável deEntrada

Denominaçãodo Estado

SaídaDesejada

X=0

X=1 Variável deEntrada

SaídaDesejada


X=0

X=1


Tabela de Estados - Moore

EA – Estado Atual

EF – Estado Futuro

X – Variável de Entrada

S – Saída Desejada

EA X EF S

A0 B

41 A

B0 B

51 A

A4

B5

X=1

X=0

X=0 X=1


Diagrama de Estados - Mealy

Denominação do Estado

Condição das variáveis de entrada para transição de estados associada a saída desejada para cada transição.

A

B Variável de EntradaDenominação

do EstadoSaída Desejada

S=5

X=1


X=0

X=1

S=5

X=0

S=4

S=4

Variável de Entrada

Saída Desejada


Tabela de Estados - Mealy

EA – Estado Atual




EA X EF S

A0 B 5

1 A 4

B0 B 5

1 A 4

ABS=5 X=1

X=0X=1

S=5

X=0

S=4

S=4


Questões Existenciais ...

Onde estou ?

O que faço aqui ?

Para onde vou ?

De onde eu vim ?

Em qual estado a máquina está ?

Qual a saída da máquina no estado atual ?

Para qual estado a máquina vai ?

De qual estado a máquina veio ?


Exercício 1 – Moore

Projetar uma máquina de estados, comarquitetura Moore com FF tipo D, que execute afunção de um contador com as seguintescaracterísticas:

Progressivo

Habilitação da contagem

Ao chegar ao fim da contagem deve voltar ao início

Faça a contagem na seguinte faixa de números: 2 à 5

24

Arquitetura Moore



para Saída

Elementode Memória

FF D,T,JK


SaídaDesejada

Decodificador

F FDecodificador

F F

Clock

LPE=f (EA,X)X

S=f (EA)

SaídaEA

EA

1. Definição das variáveis de entrada e saída

2. Definição do diagrama de estado e da tabela de transições de estado

3. Definição do número de Flip-Flops

4. Codificação dos estados e saídas

5. Projeto dos decodificadores de saída e próximo estado


1. Definição das Variáveis de Entrada e Saída

Entrada Habilitação da Contagem – Entrada X 0 – Não Conta

1 – Conta Saída Valor do Contador em Binário – Saída S 2,3,4,5 - Decimal

010, 011, 100, 101 - Binário

Estados / Saída A = 2 B = 3 C = 4 D = 5


2. Diagrama de Estados – Moore

A2

B3

D

5

C

4

X=1

X=1 X=1

X=1

X=0

X=0X=0

X=0


2. Tabela de Estados – Moore

EA – Estado Atual




EA X EF S


2. Tabela de Estados – Moore

EA – Estado Atual




EA X EF S

A0 A

21 B

B0 B

31 C

C0 C

41 D

D0 D

51 A


3. Número de Estados e Flip-Flops

O número de Flip-Flops utilizados na máquina deestados depende do número de estados que deveser “memorizado” pela máquina de estados.

Com N Flip-Flops consegue-se “memorizar” 2N

estados

A quantidade de Flip-Flops deve ser tal que:

2N ≥ Número de EstadosOnde:

N = Quantidade de Flip-Flops


4. Codificação dos Estados e Saídas – Moore

EA EA1 EA0 X EF EF1 EF0 S S2 S1 S0

A0 A

21 B

B0 B

31 C

C0 C

41 D

D0 D

51 A


4. Codificação dos Estados – Moore

Uma codificação possível


A 1 10 A 1 1

2 0 1 01 B 1 0

B 1 00 B 1 0

3 0 1 11 C 0 1

C 0 10 C 0 1

4 1 0 01 D 0 0

D 0 00 D 0 0

5 1 0 11 A 1 1


4. Codificação dos Estados – Moore

Outra codificação mais adequada


A 0 00 A 0 0

2 0 1 01 B 0 1

B 0 10 B 0 1

3 0 1 11 C 1 0

C 1 00 C 1 0

4 1 0 01 D 1 1

D 1 10 D 1 1

5 1 0 11 A 0 0


5. Projeto dos Decodificadores

Decodificador de Saída

Decodificador de Próximo Estado

Passos para projetar um Decodificador:

Tabela Verdade (Relaciona Entrada pela Saída)

Mapas de Karnaugh

Equações Simplificadas

Circuito Lógico

Tabela Verdade

Entrada Saída

A B S


5.1. Decodificador de Saída – Moore

Moore



para Saída

Elementode

MemóriaFF D,T,JK


SaídaDesejada

Decodificador

F FDecodificador

F F

Clock

LPE=f (EA,X)X

S=f (EA)

SaídaEA

EA




A 0 00 A 0 0

2 0 1 01 B 0 1

B 0 10 B 0 1

3 0 1 11 C 1 0

C 1 00 C 1 0

4 1 0 01 D 1 1

D 1 10 D 1 1

5 1 0 11 A 0 0

Entrada Saídas




A 0 00 A 0 0

2 0 1 01 B 0 1

B 0 10 B 0 1

3 0 1 11 C 1 0

C 1 00 C 1 0

4 1 0 01 D 1 1

D 1 10 D 1 1

5 1 0 11 A 0 0

Entrada Saídas



Por observação da TabelaVerdade, determinamos asEquações Booleanas dasvariáveis de saída

S2 = EA1

S1 = EA1

S0 = EA0

EA1 EA0 S2 S1 S0

0 0 0 1 0

0 1 0 1 1

1 0 1 0 0

1 1 1 0 1

Entrada Saídas



Diagrama do decodificador de saída


5.2. Decodificador de Próximo Estado

Moore



para Saída

Elementode Memória

FF D,T,JK


SaídaDesejada

Decodificador

F FDecodificador

F F

Clock

LPE=f (EA,X)X

S=f (EA)

SaídaEA

EA



Podemos utilizar qualquer Flip-Flop como elemento de memória: D, T , JK.

O decodificador de próximo estado deve estimularo Flip-Flop para que o mesmo faça a transição doEstado Atual (EA) para o Estado Futuro (EF) baseadona sua entrada.



EA EA1 EA0 X EF EF1 EF0 S D1 D0

A 0 00 A 0 0

20 0

1 B 0 1 0 1

Transição

Determinar o valor lógico das entradas dos Flip-Flops de acordo com a transição das saídas dosmesmos.

Analisar a transição desejada e determinar qual oestímulo do Flip Flop.

EstímuloEstado Atual Estado Futuro


5.2. Decodificador de Próximo Estado: Transição de Saídas dos Flip-Flops

D QF

0 0

1 1

QA1 1

11 0

00 1

QA0 0

QFJ K

QA1

QA0

QFT

Transição Estímulo

QA → QF D T J K

0 → 0 0 0 0 X

0 → 1 1 1 1 X

1 → 0 0 1 X 1

1 → 1 1 0 X 0

FF

Q

Q

D

FF

Q

Q

T

FF

Q

Q

J

K




A 0 00 A 0 0

2 0 1 01 B 0 1

B 0 10 B 0 1

3 0 1 11 C 1 0

C 1 00 C 1 0

4 1 0 01 D 1 1

D 1 10 D 1 1

5 1 0 11 A 0 0

TransiçãoEstado Atual Estado Futuro


EA EA1 EA0 X EF EF1 EF0 D1 D0

A 0 00 A 0 0

1 B 0 1

B 0 10 B 0 1

1 C 1 0

C 1 00 C 1 0

1 D 1 1

D 1 10 D 1 1

1 A 0 0

TransiçãoEstímulo

D QF

0 0

1 1

FF

Q

Q

D

Estado Atual Estado Futuro




A 0 00 A 0 0 0 0

1 B 0 1 0 1

B 0 10 B 0 1 0 1

1 C 1 0 1 0

C 1 00 C 1 0 1 0

1 D 1 1 1 1

D 1 10 D 1 1 1 1

1 A 0 0 0 0

TransiçãoEstímulo

D QF

0 0

1 1

FF

Q

Q

D

Estado Atual Estado Futuro




A 0 00 A 0 0 0 0

1 B 0 1 0 1

B 0 10 B 0 1 0 1

1 C 1 0 1 0

C 1 00 C 1 0 1 0

1 D 1 1 1 1

D 1 10 D 1 1 1 1

1 A 0 0 0 0

Entrada Saídas




A0

0

0

0

0 A 0 0 0 0

1 B 0 1 0 1

B0

0

1

1

0 B 0 1 0 1

1 C 1 0 1 0

C1

1

0

0

0 C 1 0 1 0

1 D 1 1 1 1

D1

1

1

1

0 D 1 1 1 1

1 A 0 0 0 0

Entrada SaídasTabela Verdade



Moore



para Saída

Elementode Memória

FF D,T,JK


SaídaDesejada

Decodificador

F FDecodificador

F F

Clock

LPE=f (EA,X)X

S=f (EA)

SaídaEA

EA



Tabela Verdade

EA1 EA0 X D1 D0

0 0 0 0 0 0

1 0 0 1 0 1

2 0 1 0 0 1

3 0 1 1 1 0

4 1 0 0 1 0

5 1 0 1 1 1

6 1 1 0 1 1

7 1 1 1 0 0

D1 00 01 11 10

0 0 1 3 2

1 4 5 7 6

D0 00 01 11 10

0

1

EA1

EA0 X

EA1

EA0 X



Tabela Verdade

EA1 EA0 X D1 D0

0 0 0 0 0 0

1 0 0 1 0 1

2 0 1 0 0 1

3 0 1 1 1 0

4 1 0 0 1 0

5 1 0 1 1 1

6 1 1 0 1 1

7 1 1 1 0 0

D1EA0 EA0

EA1

EA1

X X X

D0EA0 EA0

EA1

EA1

X X X



Tabela Verdade

EA1 EA0 X D1 D0

0 0 0 0 0 0

1 0 0 1 0 1

2 0 1 0 0 1

3 0 1 1 1 0

4 1 0 0 1 0

5 1 0 1 1 1

6 1 1 0 1 1

7 1 1 1 0 0

D1 00 01 11 10

0 0 0 1 0

1 1 1 0 1

D0 00 01 11 10

0 0 1 0 1

1 0 1 0 1

EA1

EA0 X

EA1

EA0 X



D1EA0 EA0

EA1 0 0 1 0

EA1 1 1 0 1

X X X

D0EA0 EA0

EA1 0 1 0 1

EA1 0 1 0 1

X X X

D1 = EA1EA0X +

EA1EA0 + EA1X

D0 = EA0X + EA0X



Diagrama do decodificador de próximo estado



Exemplo 1 – Contador Progressivo 2 a 5

Circuito Completo – Arquitetura Moore FF tipo D

Exercício 1 – Máquina de Moore

Construir um contador de módulo 4 utilizando uma máquina de Moore.

Esse contador pode incrementar ou decrementar o seu valor;

Implementar utilizando Flip-Flops tipo D;

55

Documents

ED4 - Maquinas de Estados - Projeto Parte I