Introdução às FSM 1

Introdução às Máquinas de Estados Finitos (Finite State Machine - FSM)

Material cedido por: ANTONIO AUGUSTO LISBOA DE SOUZA

Prof.: José Mauricio Neto

Introdução às FSM 2

Plano da aula

• Circuito Sequencial Genérico• Exemplos de Maquinas de Estados Simples• Introdução aos contadores• Exemplo de metodologia de concepção de FSMs

simples

Introdução às FSM 3

Circuito Sequencial Genérico

Introdução às FSM 4

Exemplos de configurações de saída

Introdução às FSM 5

Exemplos de configurações de controle

Introdução às FSM 6

Exemplos de Máquinas de Estados Simples

Como descrever o comportamento de uma FSM?Como descrever o comportamento de uma FSM?

d3 d2d1d0

4 MUX 2:1

GND +1

=9?

b3b2b1b0

b0b1b2b3

clk1Hz

4 Flip-Flops D

Este é um Este é um ContadorContador (também conhecido como (também conhecido como gerador de sequência de estados):gerador de sequência de estados):

Quantas são as entradas (além do sinal CLK)?Quantas são as entradas (além do sinal CLK)?

Introdução às FSM 7

Diagramas de Estados

00000000 00010001 00100010 00110011

10001000 01110111 01100110 01010101

01000100

10011001

Exemplo de Exemplo de diagrama de diagrama de estados para estados para um contador:um contador:

Diagrama Diagrama genérico de genérico de

uma FSM com uma FSM com entradas:entradas:

AA

CondiçãoCondiçãoXX

CondiçãoCondiçãoYY

CC

CondiçãoCondiçãoZZ

BB

CondiçãoCondiçãoWW

CondiçãoCondiçãoTT

CondiçãoCondiçãoVV

CondiçãoCondiçãoUU

A condição de transição (flecha) é a A condição de transição (flecha) é a ocorrência de um pulso de clockocorrência de um pulso de clock

Numa FSM genérica, as Numa FSM genérica, as transições ocorrem de transições ocorrem de

acordo com o estado atual e acordo com o estado atual e as entradasas entradas

Introdução às FSM 8

Introdução aos contadores

• Também denominado Gerador de Sequência de Estados.O nº de estados é denominado MÓDULOS.

• A cada pulso de relógio, este circuito muda de estado segundo uma seqüência pré-estabelecida.

• Um registrador com n bits, possui 2n estados possíveis. O ciclo pode conter todos os possíveis estados, ou não. O módulo máximo é portanto 2n.

Ex.: Contador de dois bits que Ex.: Contador de dois bits que conta todos os estados conta todos os estados

possíveis, logo tem módulo 4:possíveis, logo tem módulo 4:

Introdução às FSM 9

• Caso o módulo do contador não seja máximo, o diagrama de estados deve indicar o próximo estado para cada estado não pertencente ao ciclo:

Exemplo: Contador de dois bits com módulo 3,Exemplo: Contador de dois bits com módulo 3,no qual o estado 3 está fora do ciclo de contagemno qual o estado 3 está fora do ciclo de contageme caso este estado ocorra, o contador fique presoe caso este estado ocorra, o contador fique preso

(CONTADOR BLOQUEANTE)(CONTADOR BLOQUEANTE)::

Introdução aos contadores

Introdução às FSM 10

• Se mesmo saindo do ciclo de contagem, houver a certeza que após um número determinado pulsos de relógio, haverá retorno ao ciclo, o contador é dito AUTO-INICIANTE:

Introdução aos contadores

Introdução às FSM 11

• Os contadores podem ser classificados de acordo com a seqüência de contagem dada por algum código binário particular.• Contador binário – a seqüência de estados é o código binário puro

• Contador não binário – um código qualquer dita a sequência de estados, tal como o código gray ou outro qualquer.

• Ou ainda de acordo com o sentido de contagem:• Crescente

• Decrescente

• Reversível

Introdução aos contadores

Introdução às FSM 12

• Aplicações principais:•Gerador de seqüência: Usado para gerar continuamente a seqüência de estados correspondente ao ciclo de contagem

•Contador de eventos: Usado para contar continuamente um número de pulsos (eventos) igual ao módulo do ciclo de contagem

•Divisor de frequencia: O contador normalmente pode ser usado para gerar um trem de pulsos com frequência de valor igual ao resultado da divisão da frequencia do trem de pulsos aplicado à entrada de relógio pelo módulo do ciclo de contagem.

Introdução aos contadores

Introdução às FSM 13

• Um registrador de deslocamento com ES/SS pode implementar um contador, bastando realimentar a SS para a ES. Se a SS é ligada à ES, o contador é dito CONTADOR EM ANEL (RING COUNTER).

Exemplo: Um contador em anel é obtido a partir de um registrador de Exemplo: Um contador em anel é obtido a partir de um registrador de deslocamento deslocamento AA de 4 bits tipo EP/SS conforme figura abaixo. Supondo que o de 4 bits tipo EP/SS conforme figura abaixo. Supondo que o contador seja iniciado no estado 0001 (1 em decimal) através da entrada contador seja iniciado no estado 0001 (1 em decimal) através da entrada paralela, obtem-se o ciclo de contagem abaixo. paralela, obtem-se o ciclo de contagem abaixo.

Introdução aos contadores

Introdução às FSM 14

Exemplo de Contador Assíncrono

Introdução às FSM 15

Problema dos Contadores Assíncronos

atnmáxf

1

Introdução às FSM 16

Contadores Síncronos

• Em Contadores Síncronos:• Todos os FFs são acionados pelo “mesmo” sinal de Clock

•Todas as transições dos FFs ocorrem ao “mesmo” tempo

• Implementação:•FFs para amazenamento do estado atual

•Circuito Combinacional para cálculo do próximo estado

Introdução às FSM 17

Proposta de Metodologia de ConcepçãoProposta de Metodologia de Concepção

• Passo 1: Passo 1: Definir número e tipo de FFsDefinir número e tipo de FFs

• Passo 2: Passo 2: Estabelecer um diagrama de EstadosEstabelecer um diagrama de Estados

• Passo 3: Passo 3: Estabelecer um diagrama de Transições Estabelecer um diagrama de Transições “E“ENN E EN+1N+1” para cada FF” para cada FF

• Passo 4: Passo 4: Estabelecer a Tabela de Excitação do FFEstabelecer a Tabela de Excitação do FF

• Passo 5: Passo 5: Para cada Estado, definir as expressões das Para cada Estado, definir as expressões das entradas dos FFsentradas dos FFs

• Passo 6: Passo 6: Simplificar as expressões das entradas dos FFsSimplificar as expressões das entradas dos FFs

• Passo 7: Passo 7: Implementar o Diagrama ElétricoImplementar o Diagrama Elétrico

Introdução às FSM 18

Contadores Síncronos de Módulo = 2n

Exemplo: Projete um contador binário crescente e que Exemplo: Projete um contador binário crescente e que tenha módulo oito, utilizando três flip-flops do tipo JK tenha módulo oito, utilizando três flip-flops do tipo JK

sensíveis à subida.sensíveis à subida.

Introdução às FSM 19

Uma Metodologia de Concepção

Estrutura Estrutura propostaproposta

Funcionalidade:Funcionalidade:Diagrama de estadosDiagrama de estados

TabelaTabelaEstado Atual “E(t)”Estado Atual “E(t)”Próximo Estado “E(t+Próximo Estado “E(t+t)”t)”

Introdução às FSM 20

Definir todas as entradas Definir todas as entradas dos FFs de acordo com o dos FFs de acordo com o próximo estado desejadopróximo estado desejado

Tabela Estado Atual “E(t)”Tabela Estado Atual “E(t)”Próximo Estado “E(t+Próximo Estado “E(t+t)”t)”

Específico aoEspecífico aoFF em usoFF em uso

Uma Metodologia de Concepção

Introdução às FSM 21

Observar que JObservar que Jii=K=Kii, ou seja, todos os flip-flops JK são , ou seja, todos os flip-flops JK são usados como flip-flops tipo T.usados como flip-flops tipo T.

Simplificar as equações das entradas usando métodos Simplificar as equações das entradas usando métodos conhecidos conhecidos

Uma Metodologia de Concepção

Introdução às FSM 22

Implementação:Implementação:

DiagramaDiagramade tempo:de tempo:

Uma Metodologia de Concepção

Introdução às FSM 23

Exercícios: trazer próxima aula

Usando a metodologia proposta, implementar um Usando a metodologia proposta, implementar um contador síncrono que conte de 0 a 15 (módulo=16=2contador síncrono que conte de 0 a 15 (módulo=16=244) )

a partir de 4 FFs JKa partir de 4 FFs JK

Usando a metodologia proposta, implementar um Usando a metodologia proposta, implementar um contador síncrono que conte de 0 a 7 (módulo=8=2contador síncrono que conte de 0 a 7 (módulo=8=233) a ) a

partir de 3 FFs Dpartir de 3 FFs D