Aula 5-4 Máquinas de Estados Finitos-2022 1

Sistemas Digitais Aula 5-4 Máquinas de Estados Finitos Prof. Dr. Stefan Michael Blawid sblawid@cin.ufpe.br SD - §5 Circuitos Sequencias 2 Tópicos Introdução Análise das Máquinas de estados finitos (FSM) Equações Tabelas Diagramas Projeto das Máquinas de estados finitos (FSM) Exemplo SD - §5 Circuitos Sequencias 3 Tópicos Introdução Análise das Máquinas de estados finitos (FSM) Equações Tabelas Diagramas Projeto das Máquinas de estados finitos (FSM) Exemplo SD - §5 Circuitos Sequencias 4 Circuitos Sequenciais Síncronos Circuitos que tem operação controlada pelo sinal de clock são denominados circuitos sequenciais síncronos O termo borda ativa do clock se refere à borda que causa mudança no estado do circuito (positiva ou negativa) Implementado usando lógica combinacional e um ou mais flip-flops Dois modelos para circuitos seqüenciais síncronos: Modelo de Moore: a saída do circuito depende somente do estado atual Modelo de Mealy: a saída do circuito depende do estado atual e do(s) sinal(is) de entrada(s) Circuitos sequenciais são também chamados de máquinas de estados finita (MEF ou FSM, do inglês: finite state machines) SD - §5 Circuitos Sequencias 5 Máquina de Estados Finitos SD - §5 Circuitos Sequencias 6 Diagrama de Estados A primeira etapa do projeto de uma máquina de estado finita é determinar quantos estados são necessários e quantas transições são possíveis de um estado para outro: Nenhum terminal de preset deve ser usado O projetista deve pensar sobre qual tarefa o circuito deve executar Um bom começo é definir um estado de reset que o circuito deve entrar quando energia é aplicada em seus terminais ou quando o sinal de reset é recebido SD - §5 Circuitos Sequencias 7 Tabela de Estados|Saídas Um diagrama de estados descreve a funcionalidade de um circuito mas não descreve a implementação desse circuito A “tradução” para um formato tabular é necessária A tabela de estados deve conter: Todas as transições de cada estado atual para cada próximo estado para todos os valores dos sinais de entrada A saída, z, é especificada em relação ao estado atual SD - §5 Circuitos Sequencias 8 Atribuição de Estados Os estados são definidos em termos de variáveis (por exemplo A, B, e C) Cada estado é representado por um valor particular das variáveis de estado Cada variável de estado é implementada por um flip- flop Exemplo: Se 3 estados devem ser executados é suficiente usar 2 variáveis de estado. SD - §5 Circuitos Sequencias 9 Transições e Mapa de Saídas Mapas de Karnaugh são construídos a partir da tabela de estados para: Obter as saídas do circuito Entradas dos flip-flops (mapas de Karnaugh dos próximos estados) Construir os mapas dos próximos estados depende do tipo de flip- flop (D, T, JK) usado para a implementação D é o mais direto: os mapas do próximo estado são construídos diretamente da tabela de estados Por exemplo: Q(t+1) = Q* = D SD - §5 Circuitos Sequencias 10 Tópicos Introdução Análise das Máquinas de estados finitos (FSM) Equações Tabelas Diagramas Projeto das Máquinas de estados finitos (FSM) Exemplo SD - §5 Circuitos Sequencias 11 Análise de FSMs Equações Caraterísticas Descreve o próximo estado (QN) do flip-flop como função do estado atual (Q) e das entradas: QN = f(Q, inputs) [or Q* = f(Q, inputs)] Derivado da tabela de funcionamento básico para os vários tipos de flip-flops. SD - §5 Circuitos Sequencias 12 Equações Características Input Present state Next state D Q Q* 0 0 0 0 1 0 1 0 1 1 1 1 Q* = D Q* = S + R’ Q Input Present state Next state S R Q Q* 0 0 0 0 0 0 1 1 0 1 x 0 1 0 x 1 1 1 x x SD - §5 Circuitos Sequencias 13 Equações Características hold reset set toggle Q* = J Q’ + K’ Q EN Q Q* 0 0 0 0 1 1 1 0 1 1 1 0 Q* = EN Q’ + EN’ Q J K Q Q* 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 SD - §5 Circuitos Sequencias 14 Resumo: Equações Características Tipo de dispositivo Equação característica S-R latch Q* = S + R’ Q Master/slave S-R flip-flop Q* = S + R’ Q D latch Q* = D Edge-triggered D flip-flop Q* = D Master/slave J-K flip-flop Q* = J Q’ + K’ Q Edge-triggered J-K flip-flop Q* = J Q’ + K’ Q T flip-flop Q* = Q’ T flip-flop with enable Q* = EN Q’ + EN’ Q SD - §5 Circuitos Sequencias 15 Máquinas Síncronas Análise Como funciona um determinado circuito? O que o circuito faz? Como as sequencias do input mapeia para as sequencias do output? Máquina de Mealy Próximo estado = F(estado atual, inputs) Output = G(estado atual, inputs) Máquina de Moore Próximo estado = F(estado atual, inputs) Output = G (estado atual) SD - §5 Circuitos Sequencias 16 Máquina Mealy vs Moore Next- State Logic State Registers Output Logic current_state next_state Inputs Outputs Mealy Machine Next- State Logic Output Logic current_state next_state Inputs Outputs Moore Machine State Registers SD - §5 Circuitos Sequencias 17 Análise Básico das Máquinas 1. Determina a função do próximo estado (F) e do output (G) 2. Usa F e G para construir a tabela de estados 3. Desenha o diagrama do estado que representa a tabela do estado na forma de gráfico SD - §5 Circuitos Sequencias 18 Análise Detalhada das Máquinas 1. Encontre as equações da excitação dos input do flip-flop, D = f1(state, inputs) 2. Substitua as equações de excitação nas equações características dos flip-flops originando as equações de transição,
 Q* = f2(estado, inputs) 3. Construa a tabela de transições das equações de transição 4. Encontre as equações de saída, OUT = g(estado) ou OUT=g(estado, inputs) 5. Adicione as saídas para a tabela de transições para formar a tabela de transições/saídas 6. Nomeie os estados na tabela de transições/saídas originando a tabela estados/saídas 7. Desenhe o diagrama de estados e diagrama de temporização da tabela de estados/saídas SD - §5 Circuitos Sequencias 19 Exemplo 1: FSM com Flip-Flops T EN T Q C EN T Q C Characteristic Equation for T: Q* = EN. Q’ + EN’ Q E0 E1 Q0 Q1 Q0* = E0 Q0’ + E0’ Q0 X Q1* =E1 Q1’+ E1’ Q1 X.Q0 Output Equation: Z = Q0 + Q1 X Q0 CLK RESET SD - §5 Circuitos Sequencias 20 Tabela Transições|Saídas e Estados+Saídas Equações de Transição: Q0* = X Q0’ + X’ Q0 Q1* = X Q0 Q1’ + X’ Q1 + Q0’ Q1 Equação de Saída: Z = Q0 + Q1 Moore Machine X Q1Q0 0 1 Z A = 0 0 0 0 0 1 0 B = 0 1 0 1 1 0 1 C = 1 0 1 0 1 1 1 D = 1 1 1 1 0 0 1 Q1*Q0* X S 0 1 Z A A B 0 B B C 1 C C D 1 D D A 1 S* SD - §5 Circuitos Sequencias 21 Diagrama de Estados D Z = 1 C Z = 1 A Z = 0 B Z = 1 X = 0 X = 0 X = 0 X = 0 X = 1 X = 1 X = 1 X = 1 X S 0 1 Z A A B 0 B B C 1 C C D 1 D D A 1 S* SD - §5 Circuitos Sequencias 22 Diagrama de Temporização RESET CLK X Z STATE Q1 Q0 A B C C D D A A SD - §5 Circuitos Sequencias 23 Exemplo 2: FSM com Flip-Flops D X Y /Q2 Q0 Q1 CLK State Memory Excitation Logic F Output Logic G D Q CLK Q D Q CLK Q D Q CLK Q Q0 Q1 Q2 /Q2 D0 D1 D2 /Z2= (Q1 Q2)’ (Moore) A mealy machine Equações de Excitação: D0 = X Y’ Q2’; D1 = X Q0; D2 = Y’ +Q1 Z1 = X Q0 + Q1’ (Mealy) SD - §5 Circuitos Sequencias 24 Equações Equações de Excitação: D0 = X Y’ Q2’ D1 = X Q0 D2 = Y’ + Q1 Equações de Transição: Q0* = X Y’ Q2’ Q1* = X Q0 Q2* = Y’ + Q1 Equação Característica do flip-flop D: Q* = D Equações de Saída: Z1 = X Q0 + Q1’ (Mealy) /Z2 = (Q1 Q2)’ (Moore) SD - §5 Circuitos Sequencias 25 Tabela de Transições, Saídas XY Q2 Q1 Q0 00 01 11 10 A = 0 0 0 100, 11 000, 11 000, 11 101, 11 B = 0 0 1 100, 11 000, 11 010, 11 111, 11 C = 0 1 0 100, 01 100, 01 100, 01 101, 01 D = 0 1 1 100, 01 100, 01 110, 11 111, 11 E = 1 0 0 100, 11 000, 11 000, 11 100, 11 F = 1 0 1 100, 11 000, 11 010, 11 110, 11 G = 1 1 0 100, 00 100, 00 100, 00 100, 00 H = 1 1 1 100, 00 100, 00 110, 10 110, 10 Q2* Q1* Q0*, Z1 /Z2 Q0* = X Y’ Q2’ Q1* = X Q0 Q2* = Y’ + Q1 Z1 = X Q0 + Q1’ /Z2= (Q1 Q2)’ SD - §5 Circuitos Sequencias 26 Tabela de Estados, Saídas XY S 00 01 11 10 A E, 11 A, 11 A, 11 F, 11 B E, 11 A, 11 C, 11 H, 11 C E, 01 E, 01 E, 01 F, 01 D E, 01 E, 01 G, 11 H, 11 E E, 11 A, 11 A, 11 E, 11 F E, 11 A, 11 C, 11 G, 11 G E, 00 E, 00 E, 00 E, 00 H E, 00 E, 00 G, 10 G, 10 S*, Z1 /Z2 SD - §5 Circuitos Sequencias 27 Diagrama de Estados (Excerto) B A C H G F E D S XY = 00 XY = 01 XY = 11 XY = 10 A E, 11 A, 11 A, 11 F, 11 B E, 11 A, 11 C, 11 H, 11 X’Y’, (11) X’Y, (11) Y, (11) X’Y’, (11) XY, (11) XY’, (11) XY’, (11) SD - §5 Circuitos Sequencias 28 Exemplo 3: Circuito e Equações D Q CLK X Q Q Y Moore Excitation: D = X · Q’ = Q* Output: Q = Q Mealy Excitation: D = X · Q’ = Q* Output: Y = X ⊕ Q SD - §5 Circuitos Sequencias 29 Tabelas Moore Tabelas de Transições/Saídas: Tabelas de Estados/Saídas: Mealey X Q 0 1 Z 0 0 1 0 1 0 0 1 Q* X S 0 1 Z A A B 0 B A A 1 Q* X Q 0 1 0 0,0 1,1 1 0,1 0,0 Q*, Y X S 0 1 A A, 0 B, 1 B A, 1 A, 0 S*, Y SD - §5 Circuitos Sequencias 30 Diagramas de Estados A Z = 0 X= 0 B Z = 1 X = 1 X = 0 , 1 Moore input State Output A X= 0 B X = 1 (Z = 0) X = 0 , 1 (Z = 1, 0) (Z = 1) Mealey SD - §5 Circuitos Sequencias 31 Tópicos Introdução Análise das Máquinas de estados finitos (FSM) Equações Tabelas Diagramas Projeto das Máquinas de estados finitos (FSM) Exemplo SD - §5 Circuitos Sequencias 32 Projetos de FSM Síncronas Tabela de Estados cobre todas as combinações de valores das entradas (input) e estados Diagrama de Estados tem arcos com combinações de inputs ou equações de transição Mais gráfico que os desenhos com tabelas de estados Geralmente mais simples, porém mais propício a erros Não garante que todas as combinações de inputs serão 
 consideradas Possibilidade de ambiguidade – possivelmente nenhum estado próximo ou mais de um estado próximo para algumas combinações de input SD - §5 Circuitos Sequencias 3 inputs - LEFT, RIGHT, HAZ 33 Exemplo: T-bird Luz Traseira LA LC LB RA RB RC Layout of tail lights SD - §5 Circuitos Sequencias 34 Sequência de Luzes Traseiras Tail Light seq. a) Left = 4 states b) Right = 4 states c) HAZ = 2 states LA LC LB Left RA RB RC Right HAZ Primeira Diagrama de Estados Moore Machine design LEFT + RIGHT + HAZ inicia a sequência, continua incondicionalmente Se várias entradas TRUE → vários próximos estados! PROBLEMA! As transições precisam ser mutuamente exclusivas e com tudo incluído (LEFT + RIGHT + HAZ)’ L2 L3 L1 IDLE LR3 R3 R1 R2 SD - §5 Circuitos Sequencias SD - §5 Circuitos Sequencias 36 Mapa de Saídas State LC LB LA RA RB RC IDLE 0 0 0 0 0 0 L1 0 0 1 0 0 0 L2 0 1 1 0 0 0 L3 1 1 1 0 0 0 R1 0 0 0 1 0 0 R2 0 0 0 1 1 0 R3 0 0 0 1 1 1 LR3 1 1 1 1 1 1 Segunda Diagrama de Estados Não ambíguo HAZ = Prioridade máxima PROBLEMA operacional: O ciclo esquerdo ou direito é concluído mesmo se o HAZ for declarado→Perigoso SD - §5 Circuitos Sequencias (LEFT + RIGHT + HAZ)’ (LEFT • HAZ’ • RIGHT’) (HAZ + LEFT • RIGHT) L2 L3 L1 IDLE LR3 R3 R1 R2 SD - §5 Circuitos Sequencias 38 Terceira Diagrama de Estados IDLE L1 L2 L3 R1 R2 R3 LR3 1 1 1 RIGHT • HAZ’• LEFT’ LEFT • HAZ’ • RIGHT’ (LEFT + RIGHT + HAZ)’ HAZ + LEFT • RIGHT HAZ’ HAZ’ HAZ’ HAZ’ HAZ HAZ HAZ HAZ HAZ interrompe sequências L, R rapidamente Pronto para completar o circuito SD - §5 Circuitos Sequencias 39 Atribuição de Estados Inicialmente todos zeros Q2 diferencia Left vs. Right turn sequencia Q1 Q0 conta a sequencia do código do gray para minimizar o número das variáveis que mudam nas transições de estados SD - §5 Circuitos Sequencias 40 Lista de Transições S Q2 Q1 Q0 Transition Expr S* Q2*Q1*Q0* IDLE 0 0 0 (LEFT+RIGHT+HAZ)’ IDLE 0 0 0 IDLE 0 0 0 LEFT.HAZ’.RIGHT’ L1 0 0 1 IDLE 0 0 0 HAZ+LEFT.RIGHT LR3 1 0 0 IDLE 0 0 0 RIGHT.HAZ’.LEFT’ R1 1 0 1 L1 0 0 1 HAZ’ L2 0 1 1 L1 0 0 1 HAZ LR3 1 0 0 L2 0 1 1 HAZ’ L3 0 1 0 L2 0 1 1 HAZ LR3 1 0 0 L3 0 1 0 1 IDLE 0 0 0 R1 1 0 1 HAZ’ R2 1 1 1 R1 1 0 1 HAZ LR3 1 0 0 R2 1 1 1 HAZ’ R3 1 1 0 R2 1 1 1 HAZ LR3 1 0 0 R3 1 1 0 1 IDLE 0 0 0 LR3 1 0 0 1 IDLE 0 0 0 Alternativa à tabela de transição para o método de design com base no diagrama de estados Uma linha por transição Geração do Próximo Estado e Output S Q2 Q1 Q0 Transition Expr S* Q2*Q1*Q0* IDLE 0 0 0 (LEFT+RIGHT+HAZ)’ IDLE 0 0 0 IDLE 0 0 0 LEFT•HAZ’•RIGHT’ L1 0 0 1 IDLE 0 0 0 HAZ+LEFT•RIGHT LR3 1 0 0 IDLE 0 0 0 RIGHT•HAZ’•LEFT’ R1 1 0 1 L1 0 0 1 HAZ’ L2 0 1 1 L1 0 0 1 HAZ LR3 1 0 0 L2 0 1 1 HAZ’ L3 0 1 0 L2 0 1 1 HAZ LR3 1 0 0 L3 0 1 0 1 IDLE 0 0 0 R1 1 0 1 HAZ’ R2 1 1 1 R1 1 0 1 HAZ LR3 1 0 0 R2 1 1 1 HAZ’ R3 1 1 0 R2 1 1 1 HAZ LR3 1 0 0 R3 1 1 0 1 IDLE 0 0 0 LR3 1 0 0 1 IDLE 0 0 0 Q2* = Q2’.Q1’.Q0’.(HAZ+RIGHT) + Q2’.Q0.HAZ+Q2.Q0 Q1* = Q0.HAZ’ Q0* = Q2’.Q1’.Q0’.HAZ’.(LEFT⊕RIGHT) + Q1’.Q0.HAZ’ SD - §5 Circuitos Sequencias SD - §5 Circuitos Sequencias 42 Mapa de Saídas State LC LB LA RA RB RC 000 IDLE 0 0 0 0 0 0 001 L1 0 0 1 0 0 0 011 L2 0 1 1 0 0 0 010 L3 1 1 1 0 0 0 101 R1 0 0 0 1 0 0 111 R2 0 0 0 1 1 0 110 R3 0 0 0 1 1 1 100 LR3 1 1 1 1 1 1 LA = Q2’.Q0 + Q2’.Q1 + Q2.Q1’.Q0’ LB = Q2’.Q1 + Q2.Q1’.Q0’ LC = Q2’.Q1.Q0’ + Q2.Q1’.Q0’ RA = Q2 RB = Q2.Q0’ + Q2.Q1 RC = Q2.Q0’ SD - §5 Circuitos Sequencias 43 Esboço do Diagrama de Blocos HAZARD RIGTH LEFT LC LB LA RA RB RC Q2 Q1 Q0 Q2* Q1* Q0* SD - §5 Circuitos Sequencias 44 Circuito: Esquemático SD - §5 Circuitos Sequencias 45 Sugestões de Leitura John F. Wakerly, “Digital Design: Principles and Practices”, Pearson Education, 2017 Capítulos 7.3, 7.4, 7.5, 7.6 Charles H. Roth, Lizy Kurian John, and Beyond Kil Lee, “Digital Systems Design Using Verilog”, Cengage Learning, 2015 Capítulos 1.7, 1.8 Jean-Pierre Deschamps, Elena Valderrama, and Lluís Terés, “Digital Systems: From Logic Gates to Processors”, Springer, 2017 Capítulos 4.1, 4.2, 4.3, 4.5, 4.7, 4.8, 4.9 SD - §5 Circuitos Sequencias 46 Pequenos Projetos Roth 1.11: Um circuito sequencial síncrono tem uma entrada e uma saída. Se a sequência de entrada 0101 ou 0110 ocorrer, ocorrerá uma saída de dois 1s sucessivos. O primeiro desses 1s deve ocorrer coincidente com a última entrada da sequência 0101 ou 0110. O circuito deve reiniciar quando a segunda saída 1 ocorrer. Por exemplo: Sequência de entrada: X = 010011101010 101101 ... Sequência de saída: Z = 000000000011 000011 … a) Derive um gráfico e tabela de estados Mealy com um número mínimo de estados (seis estados). b) Tente escolher uma boa atribuição de estado. Realize o circuito usando FFs J-K e portas NAND. Repita usando as portas NOR. SD - §5 Circuitos Sequencias 47 Pequenos Projetos Roth 1.12: Um circuito sequencial possui uma entrada (X) e duas saídas (Z1 e Z2). Uma saída Z1 = 1 ocorre toda vez que a sequência de entrada 010 é concluída, desde que a sequência 100 nunca tenha ocorrido. Uma saída Z2 = 1 ocorre toda vez que a sequência de entrada 100 é concluída. Observe que depois que uma saída Z2 = 1 ocorre, Z1 = 1 nunca pode ocorrer, mas não vice-versa. a) Derive um gráfico e tabela de estado Mealy com um número mínimo de estados (oito estados). b) Tente escolher uma boa atribuição de estado. Realize o circuito usando FFs J ‐ K e portões NAND. Repita usando as portas NOR. SD - §5 Circuitos Sequencias 48 Pequenos Projetos Roth 1.13: Um circuito sequencial possui uma entrada (X) e duas saídas (S e V). X representa um número binário de 4 bits N. A entrada recebe N com o bit menos significativo primeiro. S representa um número binário de 4 bits igual a N + 2. A saída é fornecida primeiro com o bit menos significativo. No momento em que o quarto bit (mais significativo) entra, V = 1 se N + 2 for muito grande para ser representado por 4 bits; caso contrário, V = 0. O valor de S deve ser o valor adequado, e não um “don’t care”, nos dois casos. O circuito sempre reinicia após o recebimento do quarto bit de X. a) Derive um gráfico e tabela de estados Mealy com um número mínimo de estados (seis estados). b) Tente escolher uma boa atribuição de estado. Realize o circuito usando FFs D e portas NAND. Repita usando as portas NOR. SD - §5 Circuitos Sequencias 49 Pequenos Projetos Roth 1.14: Um circuito sequencial possui uma entrada (X) e duas saídas (D e B). X representa um número binário de 4 bits N. A entrada recebe N com o bit menos significativo primeiro. D representa um número binário de 4 bits igual a N - 2. A saída é fornecida primeiro com o bit menos significativo. No momento em que o quarto bit (mais significativo) entra, B = 1 se N - 2 for negativo; caso contrário, B = 0. O circuito sempre reinicia após o recebimento do quarto bit de X. a) Derive um gráfico e tabela de estados Mealy com um número mínimo de estados (seis estados). b) Tente escolher uma boa atribuição de estado. Realize o circuito usando FFs D e portas NAND. Repita usando as portas NOR. SD - §5 Circuitos Sequencias 50 Pequenos Projetos Des 4.1: Sintetize manualmente um sistema de controle de motor de um portão de garagem. O controlador possui quatro sinais de entrada binários: Request (R), Lower (L), Upper (U) e Vehicle (V). A entrada R = 1 quando houver uma solicitação de entrada (botão). A entrada L = 1 quando o portão estiver completamente abaixado. A entrada U = 1 quando o portão foi completamente levantado. A entrada V = 1 quando houver um veículo dentro da área dude garagem. O controlador possui dois sinais de saída binários: On (O) e Direction (D). O portão é elevado quando O = 1 e D = 1. O portão é abaixado quando O = 1 e D = 0. Para manter o portão aberto ou fechado O = 0. Para sincronizar o controlador, use qualquer porta lógica necessária e os FFs D. SD - §5 Circuitos Sequencias 51 Pequenos Projetos Des 4.2: O pseudo-código a seguir define uma máquina de Moore com três estados internos 0, 1 e 2; duas entradas x0 e x1; e três saídas y0, y1 e y2. Defina o gráfico de transição de estado correspondente, a tabela de estado próximo e a tabela de saída. SD - §5 Circuitos Sequencias 52 Pequenos Projetos Des 4.3: O pseudo-código a seguir define uma máquina Mealy com três estados internos 0, 1 e 2; duas entradas x0 e x1; e três saídas y0, y1 e y2. Defina o gráfico de transição de estado correspondente, a tabela de estado próximo e a tabela de saída. SD - §5 Circuitos Sequencias 53 Pequenos Projetos Des 4.4: Considere um sistema que consiste em um processador e uma unidade de controle. O processador executa um programa de duas etapas sob o controle de dois sinais binários, step1 e step2, e gera dois status binários sinaliza end1 e end2. A unidade de controle é uma máquina de estados finitos cujas entradas são os sinais de status end1 e end2 e um comando binário externo start, e cujas saídas são os sinais de controle step1 e step2. Sintetize manualmente a unidade de controle de acordo com as seguintes especificações: Na borda positiva do sinal start, o sinal de controle step1 fica alto e o processador começa a executar o primeiro passo. Quando a primeira etapa é concluída, o processador gera o sinal de status (flag) end1. Em seguida, o sinal de controle step1 fica baixo, o sinal de controle step2 fica alto e o processador baixa o sinal de status final1 e começa a executar o segundo passo. Quando a segunda etapa é concluída, o processador gera o sinal de status end2. Então, o sinal de controle step2 fica baixo, o processador baixa o sinal de status end2 e o circuito de controle aguarda outra borda positiva da entrada start. »Wissen schafft Brücken.«