conteudo sobres as Síntese de FSMs1.pptx

apostila sobre as sintese de fsm modulo 1

1. 1 Síntese de FSMs Diagrama de blocos da máquina de vendas Quando uma moeda é inserida, o sensor de moedas mantém a saída correspondente em 1 durante um ciclo de clock As entradas M50 e M1R nunca estão ativas simultaneamente Quando o crédito é maior/igual a R$ 1,50, o bloco de controle mantém OK=1 durante um ciclo de clock Quando o crédito é R$ 2,00, o bloco de controle mantém TR50=1 durante um ciclo de clock Sintetizar seguindo os modelos de Moore e Mealy Bloco de controle da máquina de vendas Sensor de moedas Mecanismo de liberação M50 M1R OK Clock Reset Mecanismo de troco TR50

2. 2 Síntese de FSMs Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy) Moore

3. 3 Síntese de FSMs Construir a tabela de próximo estado e saídas Estado atual M50/M1R OK TR50 Q 2 Q 1 Q 00 01 10 11 1 1 1 1 1 Q 2 * Q 1 * Q * 000 001 010 100 011

4. 4 Síntese de FSMs Construir a tabela de próximo estado e saídas Estado atual M50/M1R OK TR50 Q 2 Q 1 Q 00 01 10 11 000 010 001 xxx 1 001 011 010 xxx 1 010 100 011 xxx 1 1 000 000 000 xxx 1 1 000 000 000 xxx 1 1 Q 2 * Q 1 * Q * 000 001 010 100 011

5. Síntese de FSMs Determinar as equações de próximo estado e de saídas Mapa de Karnaugh com mais de 4 entradas! Geração automática do circuito com Logisim Estado atual M50/M1R OK TR50 Q 2 Q 1 Q 00 01 10 11 000 010 001 xxx 1 001 011 010 xxx 1 010 100 011 xxx 1 1 000 000 000 xxx 1 1 000 000 000 xxx 1 1 Q 2 * Q 1 * Q *

6. 6 Síntese de FSMs Logisim

7. 7 Síntese de FSMs Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy) Mealy

8. 8 Síntese de FSMs Construir a tabela de próximo estado e saídas Estado atual M50/M1R Q 1 Q 00 01 10 11 00, 00 10, 00 01, 00 xx, xx 1 01, 00 00, 10 10, 00 xx, xx 1 10, 00 00, 11 00, 10 xx, xx 1 1 xx, xx xx, xx xx, xx xx, xx Q 1 * Q *, OK/TR50 Q 1 Q = 00 Q 1 Q = 10 Q 1 Q = 01

9. Síntese de FSMs Determinar as equações de próximo estado e de saídas Estado atual M50/M1R Q 1 Q 00 01 10 11 00, 00 10, 00 01, 00 xx, xx 1 01, 00 00, 10 10, 00 xx, xx 1 10, 00 00, 11 00, 10 xx, xx 1 1 xx, xx xx, xx xx, xx xx, xx Q 1 * Q *, OK/TR50 Q 1 * M50/M1R Q 1 Q 00 01 11 10 00 01 11 10

10. Síntese de FSMs Determinar as equações de próximo estado e de saídas Estado atual M50/M1R Q 1 Q 00 01 10 11 00, 00 10, 00 01, 00 xx, xx 1 01, 00 00, 10 10, 00 xx, xx 1 10, 00 00, 11 00, 10 xx, xx 1 1 xx, xx xx, xx xx, xx xx, xx Q 1 * Q *, OK/TR50 Q 1 * M50/M1R Q 1 Q 00 01 11 10 00 1 X 01 X 1 11 x x X x 10 1 x Q 1 * = Q 1 .!M50.!M1R + !Q 1 .!Q .M1R + Q .M50

11. Síntese de FSMs Determinar as equações de próximo estado e de saídas Estado atual M50/M1R Q 1 Q 00 01 10 11 00, 00 10, 00 01, 00 xx, xx 1 01, 00 00, 10 10, 00 xx, xx 1 10, 00 00, 11 00, 10 xx, xx 1 1 xx, xx xx, xx xx, xx xx, xx Q 1 * Q *, OK/TR50 Q * M50/M1R Q 1 Q 00 01 11 10 00 01 11 10

12. Síntese de FSMs Determinar as equações de próximo estado e de saídas Estado atual M50/M1R Q 1 Q 00 01 10 11 00, 00 10, 00 01, 00 xx, xx 1 01, 00 00, 10 10, 00 xx, xx 1 10, 00 00, 11 00, 10 xx, xx 1 1 xx, xx xx, xx xx, xx xx, xx Q 1 * Q *, OK/TR50 Q * M50/M1R Q 1 Q 00 01 11 10 00 x 1 01 1 x 11 x x x x 10 x Q * = Q .!M50.!M1R + !Q 1 .!Q .M50

13. Síntese de FSMs Determinar as equações de próximo estado e de saídas Estado atual M50/M1R Q 1 Q 00 01 10 11 00, 00 10, 00 01, 00 xx, xx 1 01, 00 00, 10 10, 00 xx, xx 1 10, 00 00, 11 00, 10 xx, xx 1 1 xx, xx xx, xx xx, xx xx, xx Q 1 * Q *, OK/TR50 OK M50/M1R Q 1 Q 00 01 11 10 00 01 11 10

14. Síntese de FSMs Determinar as equações de próximo estado e de saídas Estado atual M50/M1R Q 1 Q 00 01 10 11 00, 00 10, 00 01, 00 xx, xx 1 01, 00 00, 10 10, 00 xx, xx 1 10, 00 00, 11 00, 10 xx, xx 1 1 xx, xx xx, xx xx, xx xx, xx Q 1 * Q *, OK/TR50 OK M50/M1R Q 1 Q 00 01 11 10 00 x 01 1 x 11 x x x x 10 1 x 1 OK = Q .M1R + Q 1 .M1R + Q 1 .M50

15. Síntese de FSMs Determinar as equações de próximo estado e de saídas Estado atual M50/M1R Q 1 Q 00 01 10 11 00, 00 10, 00 01, 00 xx, xx 1 01, 00 00, 10 10, 00 xx, xx 1 10, 00 00, 11 00, 10 xx, xx 1 1 xx, xx xx, xx xx, xx xx, xx Q 1 * Q *, OK/TR50 TR50 M50/M1R Q 1 Q 00 01 11 10 00 01 11 10

16. Síntese de FSMs Determinar as equações de próximo estado e de saídas Estado atual M50/M1R Q 1 Q 00 01 10 11 00, 00 10, 00 01, 00 xx, xx 1 01, 00 00, 10 10, 00 xx, xx 1 10, 00 00, 11 00, 10 xx, xx 1 1 xx, xx xx, xx xx, xx xx, xx Q 1 * Q *, OK/TR50 TR50 M50/M1R Q 1 Q 00 01 11 10 00 x 01 x 11 x X x x 10 1 x TR50 = Q 1 .M1R

17. 17 Síntese de FSMs Determinar as equações de excitação Equação caracterísca do flip-flop D: Q* = D D = Q .!M50.!M1R + !Q 1 .!Q .M50 D 1 = Q 1 .!M50.!M1R + !Q 1 .!Q .M1R + Q .M50

18. Síntese de FSMs Desenhar o circuito D = Q .!M50.!M1R + !Q 1 .!Q .M50 D 1 = Q 1 .!M50.!M1R + !Q 1 .!Q .M1R + Q .M50 OK = Q .M1R + Q 1 .M1R + Q 1 .M50 TR50 = Q 1 .M1R Próximo estado Saídas

19. 19 Síntese de FSMs Logisim

20. 20 Síntese de FSMs Diagrama de blocos da máquina de vendas Quando uma moeda é inserida, o sensor de moedas mantém a saída correspondente em 1 durante um ciclo de clock As entradas M25, M50 e M1R nunca estão ativas simultaneamente Quando o crédito é maior/igual a R$ 1,50, o bloco de controle mantém OK=1 durante um ciclo de clock Quando necessário, o bloco de controle mantém as saídas de troco em 1 durante um ciclo de clock TR25 e TR50 podem estar ativas simultaneamente ( R$ 0,75) Bloco de controle da máquina de vendas Sensor de moedas Mecanismo de liberação M25 M50 OK Clock Reset Mecanismo de troco TR25 TR50 M1R

21. 21 Síntese de FSMs Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy) Moore

22. 22 Síntese de FSMs Construir o diagrama de estados adotando um modelo de FSM (Moore ou Mealy) Mealy

23. 23 Síntese de FSMs Construir a tabela de próximo estado e saídas (Moore) Estado atual M25/M50/M1R OK TR25 TR50 S 000 100 010 001 S0 S25 S50 S75 S1R S1R25 S1R50 S1R75 S2R S2R25 S* Apenas combinações relevantes das entradas

24. 24 Síntese de FSMs Construir a tabela de próximo estado e saídas (Moore) Estado atual M25/M50/M1R OK TR25 TR50 S 000 100 010 001 S0 S0 S25 S50 S1R S25 S25 S50 S75 S1R25 S50 S50 S75 S1R S1R50 S75 S75 S1R S1R25 S1R75 S1R S1R S1R25 S1R50 S2R S1R25 S1R25 S1R50 S1R75 S2R25 S1R50 S0 S0 S0 S0 1 S1R75 S0 S0 S0 S0 1 1 S2R S0 S0 S0 S0 1 1 S2R25 S0 S0 S0 S0 1 1 1 S* Codificar os estados Apenas combinações relevantes das entradas

25. Síntese de FSMs Determinar as equações de próximo estado e de saídas Mapa de Karnaugh com 7 entradas! Geração automática do circuito com Logisim Estado atual M25/M50/M1R OK TR25 TR50 Q 3 Q 2 Q 1 Q 000 100 010 001 0000 0000 0001 0010 0100 0001 0001 0010 0011 0101 0010 0010 0011 0100 0110 0011 0011 0100 0101 0111 0100 0100 0101 0110 1000 0101 0101 0110 0111 1001 0110 0110 0000 0000 0000 1 0111 0000 0000 0000 0000 1 1 1000 0000 0000 0000 0000 1 1 1001 0000 0000 0000 0000 1 1 1 Q 3 *Q 2 *Q 1 *Q *

26. 26 Síntese de FSMs Logisim

27. 27 Síntese de FSMs Diminuir o número de entradas da FSM Entradas M25, M50 e M1R nunca estão ativas simultaneamente Codificar as entradas M25 Bloco de controle da máquina de vendas Sensor de moedas Mecanismo de liberação M50 OK Clock Reset Mecanismo de troco TR25 TR50 M1R Bloco de controle da máquina de vendas Sensor de moedas Mecanismo de liberação M25 M50 OK Clock Reset Mecanismo de troco TR25 TR50 M1R Decoder 2 code

28. 28 Síntese de FSMs Diminuir o número de entradas da FSM Entradas M25, M50 e M1R nunca estão ativas simultaneamente Codificar as entradas Code 00 : No coin 01 : M25 10 : M50 11 : M1R Bloco de controle da máquina de vendas Sensor de moedas Mecanismo de liberação M25 M50 OK Clock Reset Mecanismo de troco TR25 TR50 M1R Decoder 2 code

29. 29 Síntese de FSMs Diminuir o número de entradas da FSM Decoder Code 00 : No coin 01 : M25 10 : M50 11 : M1R M25 M50 M1R Code 1 Code 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 M25 M50 M1R Decoder 2 code Problema de múltiplas entradas de moeda ativas resolvido

30. 30 Síntese de FSMs Diminuir o número de entradas da FSM Decoder Code 00 : No coin 01 : M25 10 : M50 11 : M1R M25 M50 M1R Decoder 2 code

31. 31 Síntese de FSMs Construir a tabela de próximo estado e saídas Estado atual Code[1:0] OK TR25 TR50 S 00 01 10 11 S0 S0 S25 S50 S1R S25 S25 S50 S75 S1R25 S50 S50 S75 S1R S1R50 S75 S75 S1R S1R25 S1R75 S1R S1R S1R25 S1R50 S2R S1R25 S1R25 S1R50 S1R75 S2R25 S1R50 S0 S0 S0 S0 1 S1R75 S0 S0 S0 S0 1 1 S2R S0 S0 S0 S0 1 1 S2R25 S0 S0 S0 S0 1 1 1 S*

32. 32 Síntese de FSMs Logisim

33. 33 Síntese de FSMs Combinação de Mealy e Moore Frequentemente utilizam-se FSMs que são uma combinação dos modelos de Mealy e Moore Em um mesmo circuito é possível definir saídas que dependam apenas do estado atual (Moore) e outras que dependem do estado atual e das entradas (Mealy) Next state logic S tate memory Moore outputs Mealy outputs inputs clock c urrent state

34. 34 Síntese de FSMs Combinação de Mealy e Moore Exemplo: máquina de vendas Saída OK depende das entradas e do estado atual Saídas indicativas de crédito CR0 , CR50, CR1R dependem apenas do estado atual

35. 35 Síntese de FSMs Combinação de Mealy e Moore Tabela de transição de estados/saídas Estado atual M50/M1R CR0 CR50 CR1R Q 1 Q 00 01 10 11 00, 0 10, 0 01, 0 xx, x 1 1 01, 0 00, 1 10, 0 xx, x 1 1 10, 0 00, 1 00, 1 xx, x 1 1 1 xx, x xx, x xx, x xx, x X x x Q 1 * Q *, OK

36. 36 Síntese de FSMs Codificação de estados A codificação dos estados tem influência direta na síntese d os circuitos que geram as saídas e o próximo estado Dependendo da codificação escolhida, os circuitos obtidos podem ser mais simples ou mais complexos Exemplo: swap Q 1 Q = 00 Q 1 Q = 01 Q 1 Q = 11 Q 1 Q = 10 Q 1 Q = 00 Q 1 Q = 01 Q 1 Q = 10 Q 1 Q = 11 Codificação alternativa

37. 37 Síntese de FSMs Codificação de estados Tabela de próximo estado Estado atual W Q 1 Q 1 00 01 1 11 11 1 00 00 1 1 10 10 Q 1 * Q * Q 1 Q = 00 Q 1 Q = 01 Q 1 Q = 11 Q 1 Q = 10

38. 38 Síntese de FSMs Codificação de estados Equações de próximo estado Estado atual W Q 1 Q 1 00 01 1 11 11 1 00 00 1 1 10 10 Q 1 * Q * Q 1 * W Q 1 Q 1 00 01 1 1 11 1 1 10 Q * W Q 1 Q 1 00 1 01 1 1 11 10 Q 1 * = Q Q * = !Q 1 .Q + !Q 1 .W

39. Síntese de FSMs Codificação de estados Comparação Codificação alternativa: A=00, B=01, C=11, D=10 Q * = !Q 1 .Q + !Q 1 .W Q 1 *= Q Codificação trivial: A=00, B=01, C=10, D=11 Q *= !Q .W + Q 1 .!Q Q 1 *= !Q 1 .Q + Q 1 .!Q = Q 1 ^Q

40. Síntese de FSMs Codificação de estados Comparação Circuito para geração do próximo estado Codificação trivial Codificação alternativa

41. Síntese de FSMs Codificação de estados A codificação alternativa resultou em menor custo nesse caso devido à mudança de apenas 1 bit de estado em cada transição Codificação alternativa : A=00 → B=01 → C=11 → D=10 → Codificação trivial: A=00 → B=01 → C=10 → D=11 → Codificação Gray Na transição de um código para outro apenas um bit ou muda Exemplo: 3 bits 000 → 001 → 011 → 010 → 110 → 111 → 101 → 100

42. Síntese de FSMs Codificação de estados One hot Utiliza um bit por estado Tem-se somente um bit em ‘1’ por estado Bit ativo identifica o estado Exemplo : codificação de 4 estados 0001, 0010, 0100, 1000 Desvantagem óbvia em relação ao número de flip-flops usados Entretando os circuitos de próximo estado e saídas tendem a ser mais simples No máximo 2 bits mudam em qualquer transição

43. Síntese de FSMs Codificação de estados Detector de borda positiva A cada transição da entrada X de ‘0’ para ‘1’, a saída Z é mantida em ‘1’ durante um ciclo de clock ↑X X Clock Z

44. 44 Síntese de FSMs Codificação de estados Tabela de próximo estado e saídas Codificação one hot Estado atual X Z Q 2 Q 1 Q 1 1 010 001 1 010 100 1 010 001 1 Q 2 * Q 1 * Q * Q 2 Q 1 Q = 001 Q 2 Q 1 Q = 010 Q 2 Q 1 Q = 100

45. 45 Síntese de FSMs Codificação de estados Equações de próximo estado e de saídas Q 2 * Q /X Q 2 Q 1 00 01 11 10 00 x x 01 1 x x 11 x x x x 10 x x Q 2 * = Q 1 .X Estado atual X Z Q 2 Q 1 Q 1 1 10 01 1 10 1 00 1 10 01 1 Q 2 * Q 1 * Q *

46. 46 Síntese de FSMs Codificação de estados Equações de próximo estado e de saídas Q 1 * Q /X Q 2 Q 1 00 01 11 10 00 x x 1 01 1 x x 11 x x x x 10 1 x x Q 1 * = !X Estado atual X Z Q 2 Q 1 Q 1 1 1 1 1 1 1 1 1 1 1 Q 2 * Q 1 * Q *

47. 47 Síntese de FSMs Codificação de estados Equações de próximo estado e de saídas Q * Q /X Q 2 Q 1 00 01 11 10 00 x x 1 01 x x 11 x x x x 10 1 x x Q * = !Q 1 .X Estado atual X Z Q 2 Q 1 Q 1 1 01 00 1 1 01 10 1 01 00 1 1 Q 2 * Q 1 * Q *

48. 48 Síntese de FSMs Codificação de estados Equações de próximo estado e de saídas Z Q Q 2 Q 1 1 00 x 01 x 11 x x 10 1 x Z = Q 2 Estado atual X Z Q 2 Q 1 Q 1 1 010 001 1 010 100 1 010 001 1 Q 2 * Q 1 * Q *

49. 49 Síntese de FSMs Codificação de estados Equações do detector de borda positiva ( one hot ) D 2 = Q 1 .X D 1 = !X D = !Q 1 .X Z = Q 2 Preset

50. Síntese de FSMs Codificação de estados Almost one hot Variação da codificação one hot Nessa codificação o estado inicial tem todos bits em ‘0’ ( no hot ) Exemplo : codificação de 4 estados 000, 001, 010, 100 Tal variação faz muito sentido É simples inicializar todos flip-flops em ‘0’ (reset)

51. Síntese de FSMs Codificação de estados Como escolher a melhor codificação ? Em geral , testando todas ! Uma codificação pode ser boa para um projeto mas ruim para outro Experiência do projetista Algumas recomendações Escolher uma codificação de estado inicial fácil de ser gerada Todos bits em ‘0’ ou todos em ‘1’ Minimizar a variação de bits entre transições de estado Considerar a utilização de mais flip-flops do o número mínimo possivel ( codificação trivial)