TécnicasTécnicasDigitais paraDigitais paraComputaçãoComputação

INF01 118

AnáliseAnálise de de CircuitosCircuitos SequënciaisSequënciaisMáquinasMáquinas de Mealy e Moore de Mealy e Moore

Aula 23

Técnicas Digitais

• circuito seqüencial síncrono• reconhecido se contém flip-flops (ou latches)• circuito pode conter parte combinacional ou não

• comportamento do circuito seqüencial é determinado pela seqüência de valores das entradas, saídas e estados (valores dos FF’s)

• saídas = f (entradas, estado atual) ou máquina de Mealy f (estado atual) máquina de Moore• próximo estado = f (entradas, estado atual)

1. 1. IntroduçãoIntrodução

• equações de entrada = equações booleanas para as entradas de dadosdos FF’s

• correspondem a uma lógica combinacional• para cada entrada de dados de um FF deve haver uma equação

Técnicas Digitais

Máquinas de Estados• Uma máquina de estados é uma combinação de 5

elementos:

(Σ, X, g, x0, F)

Onde:Σ é um alfabeto finitoX é um conjunto finito de estadosg é a função de transição de estado g : X x Σ -> XX0 é o estado inicial, x0 ∈ XF é o conjunto de estados finais, F ⊆ X.

Definição

Técnicas Digitais

Diagrama de Estados

• O diagrama de estados representa a máquina de estados finitoe contem:– Circulos: que representam os estados da máquina rotulados

com o nome do estado e tambem ou não com suacodificação.

– Arcos diretos: que representam as transições entre estadosrotulados com entradas/saídas para a transição de estados.

Técnicas Digitais

Máquina de Estados Finitos

• Saída depende apenas doestado atual.

TIPO MOORE

Lógica de próximo estado

clk

estado

Entradas

saídas

resetA=‘0’

A=‘1’reset

A=‘0’

A=‘1’

S0

S1

F=‘0’;

F=‘1’;

A

F

Técnicas Digitais

Maquina de Estados FinitosTIPO MEALY

• Saída depende da entrada e doestado atual.

Lógica de próximo

Estado e saída

clk

estado

Entradas

resetA=‘0’

A=‘1’reset

A=‘0’

A=‘1’

S0

S1

F=‘0’;

AF

F=‘1’;

F=‘1’;

F=‘0’;

Técnicas Digitais

Maquina de Estados FinitosTIPO MEALY

• Saída depende apenas doestado atual.

Lógica de próximo

Estado e saída

clk

estado

Entradas

resetA=‘0’

A=‘1’reset

A=‘0’

A=‘1’

S0

S1

F=‘0’;

AF

F=‘1’;

F=‘1’;

F=‘0’;

Solucionar problemas de estabilização

clk clk

Saída

Técnicas Digitais

Considerações sobre Diagramas de Estados

• Máquinas de estado (FSM) podem estar em apenas um estado por vez notempo, logo há em apenas um estado ou circulo em um determinado tempot.

• Transição de estados são permitidas apenas na transição de subida OUdescida do relógio (clk), dependendo do elemento de armazenamento deestado (se é sensivel a borda de descida ou subida). FSM sincronas!!!

• A representação de máquinas de Mealy e Moore são diferentes como visto.– Máquinas de Mealy, as entradas e saidas são definidas nos arcos

(transições entre estados).– Máquina de Moore, as entradas são definidas nos arcos (transições

entre estados) e a saída é definida no estado (dentro do círculo).

Técnicas Digitais

• processo de projetoespecificação (p.ex. FSM)

tabela de estados

equações de entrada (para FF’s) e de saída

síntese a partir das equações (problema de lógica combin.)• número de flip-flops

com codificação: n FF’s 2n estadossem codificação: n FF’s n estados

• escolha do tipo dos FF’sinfluencia determinação das equações de entrada

ProjetoProjeto do Hardware de do Hardware de umauma FSM FSM

Técnicas Digitais

ProjetoProjeto com flip-flops com flip-flops tipotipo D Dprocessoprocesso de de projetoprojeto1. Obter tabela de estados2. Derivar equações de entrada a partir do “próximo estado” na tabela3. Derivar equações de saída a partir da “saída” na tabela4. Simplificar equações de entrada e saída5. Desenhar circuito lógico com FF’s D e portas lógicas de acordo com as equações.

exemploexemplo

00

1101

10

1/1

0/0

1/0

1/1

4 estados 2 FF’s: A B

1 entrada X1 saída Y1/0

0/0

0/0

0/0

Técnicas Digitais

TabelaTabela de de EstadosEstadosEstado Atual A B 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1

Entrada X 0 1 0 1 0 1 0 1

Próx. Estado A B 0 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0

Saída Y 0 1 0 0 0 1 0 0

equaçõesequações de de entradaentrada parapara FFFF’’ss tipotipo D DA(t+1) = DA (A,B,X) = Σ m (2,4,5,6)

B(t+1) = DB (A,B,X) = Σ m (1,3,5,6)

equaçãoequação de de saídasaídaY(A,B,X) = Σ m (1,5)

MINTERMO 0 1 2 3 4 5 6 7

Técnicas Digitais

simplificaçãosimplificação dasdas equaçõesequaçõesDA DB

DA = AB + BX DB = AX + BX + ABX

““desenhardesenhar”” circuitocircuito lógicológico

Y

Y = BX

Reconhecer: - entrada - saída - FF’s - realimentações - lógica combinac.

00 01 11 100

1111 1

BXA 00 01 11 10

0

1 1

1 1

BXA

1

00 01 11 10

0

1

11

BXA

XXD Q

C Q

D Q

C Q

A

A

BB

YClock

Técnicas Digitais

ProjetoProjeto com com estadosestados nãonão utilizadosutilizados

001

011

101100

0

0

01

010

1

0

1

1

5 estados 3 FF’sestados não utilizados: 000

110 111

saídas do circuito = saída dos FF’s

0

1

Técnicas Digitais

TabelaTabela de de estadosestadosEstado Atual A B C 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1

Entrada X 0 1 0 1 0 1 0 1 0 1

Próx. Estado A B C 0 0 1 0 1 0 0 1 1 1 0 0 0 0 1 1 0 0 1 0 1 1 0 0 0 0 1 1 0 0

MINTERMO 2 3 4 5 6 7 8 9 10 11

equaçõesequações de de entradaentradaA(t+1) = DA = Σ m (5,7,8,9,11)

B(t+1) = DB = Σ m (3,4) C(t+1) = DC = Σ m (2,4,6,8,10)

Técnicas Digitais

simplificaçãosimplificação

00 01 11 1000

01

11

10

CXAB

DA

1 1 1 X X X XX X X X

1 1 X XX X 00 01 11 10

00

01

11

10

CXAB

DB

X X X X

00 01 11 1000

01

11

10

CXAB

DC

1 1 X X X X1 1 X X 1

X 1X1

DC=X

DA=AX+BX+BC

Mintermos don’t care: 0,1,12,13,14,15

DB=ACX + ABX

Técnicas Digitais

T As váriáveis de estado vão de 0 1 e de volta 1 0 (ex. contadores)

D Quando a informação de entrada deve ser armazenada por um tempo

SR Quando sinais diferentes podem dar SET ou RESET nos flip-flops

JK Quando queremos combinar as vantagens de um FF T com SR

SR e JK Tendem a reduzir o custo das equações de entrada, mas demandam até o dobro de conexões do que os FF’s D e T

Como os FF’s D e T requerem um número menor de conexões, são preferidos para implementações VLSI

EscolhaEscolha dos flip-flops dos flip-flops

Técnicas Digitais

ExemploExemplo 1: FSM 1: FSM

11

01

101/0

1/0

1/0

1/00/1 0/1

0/100

0/0

a/b indica entrada/saída

Estado Atual A B 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1

Entrada X 0 1 0 1 0 1 0 1

Próx. Estado A B 0 0 0 1 0 0 1 1 0 0 1 0 0 0 1 0

Saída Y 0 0 1 0 1 0 1 0

Máquinade Mealy

saída = f (entradas, estado)

Tab

ela

Tab

ela

1 1

Técnicas Digitais

FSM para o exemplo da Tabela 2

0 1

01,10

01,1000,11

00,11

só as entradas estãoindicadas nos arcos(saídas FF’s)

Estado AtualA00001111

EntradasX Y0 00 11 01 10 00 11 01 1

Próximo EstadoA01101001

Máquinade Moore

saída = f (estado)Tab

ela

Tab

ela

2 2ExemploExemplo 2: FSM 2: FSM

Técnicas Digitais

FSM FSM parapara o o exemploexemplo dada TabelaTabela 3 3

00

1110

010

1 0

0

0

1

11

Estado Atual A B 0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1

Entrada X 0 1 0 1 0 1 0 1

Entradas dos FF’sJA KA JB KB0 0 1 00 0 0 1 1 1 1 01 0 0 1 0 0 1 10 0 0 0 1 1 1 11 0 0 0

Próximo Estado A B 0 1 0 0 1 1 1 0 1 1 1 0 0 0 1 1

ExemploExemplo 3: FSM 3: FSM