Sistemas Seqüenciais e Modelagem por MdE

Prévia do material em texto

1 
Sistemas Seqüenciais e modelagem por MdE 
1. Caracterização de Máquinas de Estados 
Os circuitos lógicos podem ser de dois tipos: combinacionais e seqüenciais. Os circuitos 
combinacionais se caracterizam por apresentar saída(s) que depende(m) única e exclusivamente da(s) 
entrada(s) aplicada(s) enquanto que os circuitos seqüenciais se caracterizam por apresentar saída(s) 
que depende(m) da(s) entrada(s) aplicada(s) e do histórico (estado interno atual) do sistema. 
Para se compreender estes conceitos podem-se tomar como exemplos dois modelos de TV: 
• num primeiro modelo, o seletor é composto por um conjunto de chaves, uma por canal, 
onde apenas uma está ativa a cada instante e que; 
• num segundo modelo existem duas chaves do tipo push-bottom (chave UP e chave 
DOWN) através das quais, pode-se selecionar um canal imediatamente acima, ou 
imediatamente abaixo do atual, caso seja dado, respectivamente, um toque no botão UP 
ou um toque no botão DOWN. 
Na operação de uma TV que usa o primeiro modelo, quando se assiste a programação de um 
dado canal, para acionar outro canal, basta pressionar a chave correspondente ao canal desejado que a 
saída do vídeo passa a mostrar o novo sinal. Já no segundo modelo, para assistir a programação de um 
canal não imediatamente abaixo ou acima do atual, têm-se que saber quantos toques sucessivos no 
botão DOWN ou no botão UP, devem ser dados para se chegar ao canal desejado. 
No primeiro caso, a TV se comporta como um circuito lógico combinacional, onde a saída é 
função única da entrada aplicada e, no segundo caso, a TV se comporta como um circuito lógico 
seqüencial onde, a saída depende da seqüência de sinais aplicados associados a condição do estado 
atual do seletor. 
Relembrando o comportamento dos circuitos combinacionais estudados como, por exemplo, 
conversores de código, somadores, geradores e testadores de paridade, multiplexadores e 
demultiplexadores, etc, chega-se a conclusão que sua representação é equivalente ao diagrama de bloco 
da figura 1, onde, qualquer saída Fi será dada por: 
Fi = Gi(I1, I2,..., In), i variando de 1 até k 
 
Figura 1 – Representação de um Circuito Lógico Combinacional 
 2 
Admitiu-se implicitamente que não existem atrasos entre os terminais de entrada e os terminais 
de saída. Sabe-se que essas condições de atraso zero não ocorrem na prática, pode-se, no entanto, 
considerar que os atrasos da malha de pior caso são tais que não influenciam no comportamento do 
circuito. 
Nos circuitos lógicos seqüenciais onde o comportamento das variáveis de saída depende tanto 
dos valores das variáveis de entrada presentes quanto do estado interno atual ou, simplesmente, do 
estado atual do sistema, é necessário estabelecer algumas variáveis internas, chamadas de variáveis 
de estado, através das quais seja possível conhecer um estado passado e prever um estado futuro. 
De maneira geral, para um circuito seqüencial com n variáveis de estado, têm-se 2n possíveis 
estados internos ou, simplesmente, estados. Por maior que seja n, teremos sempre um número finito 
de estados possíveis. Razão por que os Circuitos Seqüenciais podem ser definidos ou modelados por 
Máquinas de Estado Finito ou simplesmente Máquinas de Estado (MdE ). 
Num circuito seqüencial, as mudanças de um estado atual para um novo estado ou estado 
próximo podem ocorrer de forma natural ou forçada. No primeiro caso, o circuito é dito operar no 
modo fundamental e, apenas atrasos de malhas estão envolvidos. No segundo caso, o circuito é dito 
operar no modo de pulsos já que qualquer mudança de estado só ocorre em resposta a um pulso de 
sincronismo externo chamado de pulso de clock (relógio) ou simplesmente de clock. 
Na figura 2, é mostrado um circuito seqüencial que opera no modo fundamental e, na figura 3 é 
mostrado um circuito seqüencial que opera no modo de pulsos. Para diferenciar o estado de uma 
variável no momento atual para seu valor num momento próximo, foi usada uma letra em maiúsculo 
para representar o estado atual e a mesma letra em minúsculo para representar o seu estado próximo. 
Os sistemas seqüenciais que operam no modo de pulsos são classificados, de acordo com a 
forma com que o pulso de relógio é aplicado, em sistemas seqüenciais síncronos e assíncronos. Os 
sistemas seqüenciais síncronos são aqueles em que todos os dispositivos de memória (flip-flops ou 
registradores de estado) respondem ao mesmo pulso de clock. Já os sistemas seqüenciais assíncronos 
são aqueles em que um pulso de clock externo provoca mudanças em alguns dispositivos de memória 
(flip-flops ou registradores de estado) os quais, podem servir de fonte de clock para outros dispositivos 
de memória internos. Em outras palavras, num sistema seqüencial síncrono, todas as mudanças nas 
variáveis de estado presentes no circuito acontecem simultaneamente sob o controle do sinal de relógio 
aplicado enquanto que, nos sistemas seqüenciais assíncronos, algumas variáveis de estado respondem 
ao sinal de clock aplicado e são usadas para provocar mudanças em outras unidades internas. 
 3 
 
Figura 2 – Representação de um circuito seqüencial que opera no modo fundamental. 
 
Figura 3 – Representação de um circuito seqüencial que opera no modo de pulsos 
 
Um circuito lógico seqüencial, em modo fundamental ou em modo de pulsos, pode ser 
representado por dois modelos distintos, conhecidos por Modelos de Mealy e de Moore. Como se trata 
de duas representações diferentes para um mesmo circuito, será sempre possível a conversão de um 
modelo para o outro. 
Na representação dos circuitos seqüenciais mostrados nas figuras 2 e 3 acima, as variáveis de 
entrada juntamente com as variáveis de estado atual representam um estado presente total o qual, 
irá definir valores para as variáveis de saída e a condição de estado próximo como sendo: 
 4 
Fi = Gi ((Y1, Y2, Y3, ..., Ym), (I1, I2, I3, ..., In)) para i = 1, 2, 3, ..., k 
yi = Hi ((Y1, Y2, Y3, ..., Ym), (I1, I2, I3, ..., In)) para i = 1, 2, 3, ..., m 
Este tipo de representação, onde as saídas dependem do estado presente total (variáveis de 
entrada e variáveis de estado atual) é conhecido por Modelo de Mealy. Numa representação por 
Modelo de Moore, as saídas são funções apenas das variáveis de estado atual e, portanto, têm-se: 
Fi = Gi (Y1, Y2, Y3, ..., Ym) para i = 1, 2, 3,..., k 
yi = Hi ((Y1, Y2, Y3, ..., Ym), (I1, I2, I3, ..., In)) para i = 1, 2, 3, ..., m 
Esquemas representativos de um circuito lógico seqüencial, nos Modelos de Mealy e de Moore, 
ambos operando no modo de pulsos, são apresentados nas figuras 4 e 5 seguintes. 
 
Figura 4 – Representação de um circuito lógico seqüencial usando o modelo de Mealy 
 
 
Figura 5 – Representação de um circuito lógico seqüencial usando o modelo de Moole. 
 5 
2. Comportamento das Máquinas de Estado 
2.1. Representação por Tabela de Estado ou por Diagrama de Estado 
As relações entre as variáveis de estado (atual e próximo), as variáveis de entrada e as variáveis 
de saída, que modelam o comportamento de um sistema seqüencial, podem ser estabelecidas através de 
uma Tabela de Estado ou de um Diagrama de Estado. 
Existem várias maneiras de representar/modelar o comportamento de um sistema seqüencial 
por meio de uma Tabela de Estado. Numa destas, deve-se proceder da seguinte maneira: 
• numa primeira coluna, descrever os possíveis estados atuais da MdE; 
• numa segunda coluna, fazer uma designação (nomear) estes possíveis estados atuais; 
• numa terceira coluna estabelecer, separados por barras, os possíveis estados próximos e 
as saídas em função das entradas e dos estados atuais aplicados. Para uma representação 
por uma MdE no modelo de Moore, caso a saída seja igual ao estado atual, representar 
apenas os possíveis estados próximos. 
Na figura 6, é mostrada uma tabela modelo onde, Ic representa uma das 2n combinações das 
variáveis de entrada, Yc representaum dos possíveis estados atuais, yc representa o estado próximo 
para a condição Ic, Yc aplicada e Fc representa a saída do sistema, também para o estado presente total 
(Ic, Yc) aplicado. 
 
Figura 6 – Representação de uma MdE por Tabela de Estado 
 
Para construir um Diagrama de Estado que defina o comportamento de um sistema 
seqüencial, deve-se proceder da seguinte forma: 
 6 
• representar os possíveis estados atuais por meio de círculos, anotando dentro destes 
círculos os correspondentes estados atuais; 
• indicar através de setas as mudanças de estado, tendo sempre como ponto de partida da 
seta um estado atual e como ponto final o seu correspondente estado próximo. Caso um 
estado próximo seja igual a um estado atual, a seta deve partir e retornar para o mesmo 
círculo; 
• para uma modelagem por MdE de um circuito seqüencial no modelo de Mealy, 
descrever os valores das variáveis de entrada e das variáveis de saída, correspondentes a 
cada transição estado atual para estado próximo, ao lado da seta, separados por uma 
barra como mostram as Figuras 7a (quando o estado próximo é diferente do estado 
atual) e 7b (quando o estado próximo é igual ao estado atual); 
• para uma modelagem por MdE de um circuito seqüencial no modelo de Moore, 
representar os valores das variáveis de entrada correspondentes a cada transição estado 
atual para estado próximo, ao lado da seta e representar as variáveis de saída, 
correspondentes a condição de estado presente total, dentro do circulo, separada da 
representação do estado atual, por uma barra como mostram as Figuras 8a (quando o 
estado próximo é diferente do estado atual) e 8b (quando o estado próximo é igual ao 
estado atual). Caso a saída seja igual ao estado atual, representar apenas o estado atual. 
 
Y
i
I
i
 / F
i+1
 
 Figura 7a Figura 7b 
 
Y
i
/F
i
I
i
 
 Figura 8a Figura 8b 
Exemplos: 
Ex. 1.1 – Representar por Diagrama de Estado o comportamento de um circuito seqüencial construído 
no modelo de Moore que apresenta sequencialmente uma saída F = 0 por três períodos consecutivos de 
clock e uma saída F = 1 por um período de clock, como mostrado no diagrama de tempo abaixo. 
 
 7 
Entradas: não existem. 
Saída(s): F 
Definição dos estados internos e do comportamento do circuito por Tabela e Diagrama de 
Estado: 
a. Condição inicial: chamar de estado E0 (primeira condição F = 0). 
Estado próximo: chamar de e1 (segunda condição F = 0) 
 
Descrição do estado atual Estado Atual Estado Próximo/Saída F 
Estado Inicial E0 e1/0 
 
 
b. Estado E1 (segunda condição F = 0). 
Estado próximo: chamar de e2 (terceira condição F = 0) 
 
Descrição do estado atual Estado Atual Estado Próximo/Saída F 
Estado Inicial E0 e1/0 
Estado E1 E1 e2/0 
 
 
c. Estado E2 (segunda condição F = 0). 
Estado próximo: chamar de e3 (condição F = 1) 
Descrição do estado atual Estado Atual Estado Próximo/Saída F 
Estado Inicial E0 e1/0 
Estado E1 E1 e2/0 
Estado E2 E2 e3/0 
 
 
d. Estado E3 (condição F = 1). 
Estado próximo: a condição inicial ou estado e0 se repete (primeira condição F = 0). 
Descrição do estado atual Estado Atual Estado Próximo/Saída F 
Estado Inicial E0 e1/0 
Estado E1 E1 e2/0 
Estado E2 E2 e3/0 
Estado E3 E3 e0/1 
 8 
 
Ex. 1.2 – Modificar a mdE da questão 1, incluindo uma entrada de controle I de tal forma que a 
passagem do estado E0 para o estado E1 só ocorra quando a variável I de entrada estiver em 1 e venha 
a ocorrer um pulso de clock. 
Clk
Saída F 0 0 0 0 0 0 01
Entrada I 0 0 0 0 0 01 1 0
0
 
Entrada(s): I. 
Saída(s): F 
Definição dos estados internos e do comportamento do circuito por Tabela e por Diagrama de 
Estado: 
a. Condição inicial: chamar de estado E0 (primeira condição F = 0). 
Possíveis estados próximos: e0 se I = 0 e e1 se I = 1. 
Descrição do estado atual Estado Atual Estado Próximo/Saída F para 
 Entrada I = 0 Entrada I = 1 
Estado Inicial E0 e0/0 e1/0 
 
 
b. Estado E1 (segunda condição F = 0). 
Estado próximo: chamar de e2 (terceira condição F = 0) 
Descrição do estado atual Estado Atual Estado Próximo/Saída F para 
 Entrada I = 0 Entrada I = 1 
Estado Inicial E0 e0/0 e1/0 
Estado E1 E1 e2/0 e2/0 
 
 9 
c. Estado E2 (segunda condição F = 0). 
Estado próximo: chamar de e3 (condição F = 1) 
Descrição do estado atual Estado Atual Estado Próximo/Saída F para 
 Entrada I = 0 Entrada I = 1 
Estado Inicial E0 e0/0 e1/0 
Estado E1 E1 e2/0 e2/0 
Estado E2 E2 e3/0 e3/0 
 
 
 
d. Estado E3 (condição F = 1). 
Estado próximo: condição inicial ou estado e0 se repete (primeira condição F = 0). 
Descrição do estado atual Estado Atual Estado Próximo/Saída F para 
 Entrada I = 0 Entrada I = 1 
Estado Inicial E0 e0/0 e1/0 
Estado E1 E1 e2/0 e2/0 
Estado E2 E2 e3/0 e3/0 
Estado E3 E3 e0/1 e0/1 
 
Considerando que a máquina opera no modo de pulsos, onde cada mudança de estado só ocorre 
na presença de um pulso de clock o diagrama acima pode ter sua representação simplificada para o 
Diagrama de Estado abaixo. Como se trata de uma máquina de Moore, onde a saída só depende dos 
estados atuais, uma melhor representação na tabela seria colocar uma quarta coluna para representar a 
saída F. 
 
 10 
Ex. 1.3 – Descreva uma MdE que represente o comportamento de um detector de seqüência com uma 
entrada x e uma saída w sabendo que o circuito detector busca em sua entrada x por uma seqüência 
igual a 1011. Se em quatro pulsos consecutivos de clock essa seqüência é detectada, então sua saída 
será igual a 1 por exatamente um período de clock. O circuito executa continuamente essa busca e 
permite seqüências sobrepostas (overlapping sequences). Por exemplo, uma seqüência de 01011011 
causa dois pulsos positivos na saída. A Figura abaixo mostra o diagrama de timing exemplificando essa 
busca. Para análise, admitir que ao ser ligado, o sistema assume um estado E0 onde a entrada x é igual 
a 0 e a saída w é igual a 0. 
 
 
Definição dos estados internos e do comportamento do circuito por Tabela e por Diagrama de 
Estado na defecção da seqüência 1011: 
a. Condição inicial: estado E0 (entrada x = 0 e saída w =0). 
Possíveis estados próximos: chegar x = 0 ou chegar x = 1. 
- se chegar x = 0, como a máquina deve detectar a seqüência 1011, a chegada de outro zero não influí 
no comportamento do sistema que continua em e0 (aguardando o primeiro 1). 
- se chegar x = 1, o sistema deve ir para a condição de ter chegado um 1 e esperar um 0 (chamar de 
estado e1). 
Descrição do estado atual Estado Atual Estado Próximo/Saída w para 
 Entrada x=0 Entrada x=1 
1- Estado Inicial E0 e0/0 e1/0 
 
b. Estado E1 (x = 1, w = 0): 
Possíveis próximos estados: chegar x = 0 ou chegar x = 1. 
- se chegar x = 0, como a máquina deve detectar a seqüência 1011, a chegada de um 0 significa que 
pode ser a seqüência e o sistema deve ir para um estado de ter chegado 10 e esperar um 1 (chamar de 
estado e2). 
 11 
- se chegar x = 1, como a máquina deve detectar a seqüência 1011, chegar x = 1 não influi no 
comportamento do sistema e ele continua aguardando uma entrada x = 0. 
 
Descrição do estado atual Estado atual Estado Próximo/Saída w para 
 Entrada x=0 Entrada x=1 
1- Estado Inicial E0 e0/0 e1/0 
2- Chegou 1 em x E1 e2/0 e1/0 
 
c. Estado E2 (chegou 10 através de x, w = 0): 
Possíveis próximos estados: chegar x = 0 ou chegar x = 1. 
- se chegar x = 0, como a máquina deve detectar a seqüência 1011, estando em E2 esperando chegar 
um 1, significa que não é a seqüência (chegou 100) e o sistema volta a esperar 1 (Estado próximo e0). 
- se chegar x = 1, como a máquina deve detectar a seqüência 1011, chegar x = 1, pode ser a seqüência e 
o sistema deve ir para um estado de ter chegado 101 e esperar por x=1 (chamar de estado e3). 
 
Descrição do estado atual Estado Atual Estado Próximo/Saída wpara 
 Entrada x=0 Entrada x=1 
1- Estado Inicial E0 e0/0 e1/0 
2- Chegou 1 em x E1 e2/0 e1/0 
3- Chegou 10 em x E2 e0/0 e3/0 
 
d. Estado E3 (chegou 101 em x, w = 0): 
Possíveis próximos estados: chegar x = 0 ou chegar x = 1. 
- se chegar x = 0, como a máquina deve detectar a seqüência 1011, estando em E3, significa que não é 
a seqüência e o sistema volta a esperar o segundo 1 (Estado próximo e2, chegou 10). 
- se chegar x = 1, completa a seqüência 1011 e o sistema deve ir para um estado e4, onde w = 1. 
 12 
Descrição do estado atual Estado Atual Estado Próximo/Saída w para 
 Entrada x=0 Entrada x=1 
1- Estado Inicial E0 e0/0 e1/0 
2- Chegou 1 em x E1 e2/0 e1/0 
3- Chegaram 10 em x E2 e0/0 e3/0 
4- Chegaram 101 em x E3 e2/0 e4/0 
 
e. Estado E4 (chegou 1011 em x, w = 1): 
Possíveis próximos estados: chegar x = 0 ou chegar x = 1. 
- se chegar x = 0, como a máquina deve detectar a seqüência 1011, estando em E4 esperando chegar 
um 0, significa que pode ser nova seqüência já que já existe um 1 (condição igual ao estado E2). 
- se chegar x = 1 o sistema deve ir aguardar um 0 após ter chegado um 1 (condição igual ao estado E1). 
 
Descrição do estado atual Estado Atual Estado Próximo/Saída w para 
 Entrada x=0 Entrada x=1 
1- Estado Inicial E0 e0/0 e1/0 
2- Chegou 1 em x E1 e2/0 e1/0 
3- Chegou 10 em x E2 e0/0 e3/0 
4- Chegou 101 em x E3 e2/0 e4/0 
5- Chegou 1011 em x E4 e2/1 e1/1 
 
Como se trata de uma máquina de Moore, uma melhor representação da Tabela é mostrada abaixo: 
Descrição do estado atual Estado Atual Estado Próximo w para Saída 
 Entrada x=0 Entrada x=1 w 
1- Estado Inicial E0 e0 e1 0 
2- Chegou 1 em x E1 e2 e1 0 
3- Chegou 10 em x E2 e0 e3 0 
4- Chegou 101 em x E3 e2 e4 0 
5- Chegou 1011 em x E4 e2 e1 1 
 
 13 
3. Projeto de Máquinas de Estado Síncronas 
Um sistema seqüencial está totalmente caracterizado quando lhe é atribuído uma tabela de 
estado ou um diagrama de estado. Daí, qualquer sistema seqüencial proposto pode ser implementado 
desde que, pela sua descrição/modelagem, uma destas representações possa ser desenvolvida. É claro 
que este não é um passo simples e que, depende exclusivamente do conhecimento e da capacidade 
idealizadora do projetista. Fato é que podem surgir várias proposições para o mesmo circuito. 
Neste primeiro momento do curso, o projeto de sistemas seqüências será restrito a sistemas 
síncronos, com representação por Modelo de Mealy ou por Modelo de Moore, que apresentem apenas 
um registrador de estado como elemento de memória. Este modelo padrão de um sistema seqüencial 
(conhecido também por Modelo de Huffman), mostrado na figura 10, é normalmente usado no projeto 
de unidades controladoras digitais ou, simplesmente, controladores, como são frequentemente 
chamados. 
Figura 10 – Modelo de Huffman 
3.1 Projeto de Unidades Controladoras Digitais Síncronas 
Um procedimento para projeto de controladores, como os caracterizados acima, pode ser o 
seguinte: 
 14 
a. Procurar modelar o circuito por MdE, usando uma Tabela de Estado ou um Diagrama de 
Estado, que represente o comportamento do controlador que se deseja projetar. 
b. Opcionalmente, já que o número de portas hoje não é mas fator restritivo de um projeto, 
procurar minimizar o número de estados da Tabela ou do Diagrama de Estado. 
c. Designar um número binário único e exclusivo para cada estado do controlador (tarefa de 
designação de estados e equivalente a uma codificação de estados). Esta designação pode ser qualquer, 
no entanto, existem regras, a serem vistas futuramente, que permitem se chegar a melhor designação e 
consequentemente, ao melhor circuito, quanto ao número de componentes, para o controlador (fato 
hoje também não mais tão relevante assim). 
d. Desenhar a arquitetura do controlador (com base na arquitetura padrão mostrada na figura 
10), usando um registrador de estado com um número de bits apropriado, definindo as variáveis de 
entrada e de saída do controlador e estabelecendo que os bits de entrada e de saída do registrador de 
estado são, respectivamente, as variáveis de estado atual e as variáveis de estado próximo da MdE que 
se deseja projetar. 
e. Construir uma tabela verdade tendo, como parâmetros de entrada, as variáveis de entrada e as 
variáveis de estados atuais e, como parâmetros de saída, as variáveis de saída e as variáveis de estados 
próximos. 
f. Montar as equações lógicas que definem as variáveis de saída e as variáveis de estados 
próximos em função das variáveis de entrada e das variáveis de estados atuais. 
g. Implementar o circuito lógico usando qualquer método ou ferramenta. 
Dos passos acima descritos, o passo a é o mais importante, considerando que aí se enquadra o 
projeto propriamente dito e o seu desenvolvimento pode ser comparado a um processo criativo que 
pode ser comparado com a elaboração de um programa de computador. Os demais são muito 
mecanizados e requerem apenas uma certa prática em projetos de sistemas seqüências. 
Exemplos: 
Ex.1.4. Projetar um controlador que possa ser descrito pelo diagrama de estado mostrado abaixo, 
resultante do ex 1.2. 
 
Seguindo o procedimento proposto para projeto de controladores, têm-se: 
 15 
a. Descrição do sistema por Tabela de Estado ou por Diagrama de Estado: esta tarefa está 
cumprida já que o Diagrama de Estado foi desenvolvido no exemplo 1.2. 
b. Minimização do número de estados da Tabela ou do Diagrama de Estado: esta tarefa, 
para este exemplo, será desconsiderada. 
c. Designação de estados: como a MdE apresenta quatro estados (E0, E1, E2 e E3), estes 
quatro estados podem ser representados com no mínimo duas variáveis de estado (22 = 4). Nomeando 
as variáveis internas com a letra y, uma das designações possíveis seria então: 
Estados atuais: E0 = Y1Y0 = 00, E1 = Y1Y0 = 01, E2 = Y1Y0 = 10 e E3 = Y1Y0 = 11. 
Estados próximos: e0 = y1y0 = 00, e1 = y1y0 = 01, e2 = y1y0 = 10 e e3 = y1y0 = 11. 
Outras designações poderiam ser usadas e inclusive, com maior número de variáveis de estado, 
como por exemplo: E0 = Y3Y3Y1Y0 = 0001, E1 = Y3Y3Y1Y0 = 0010, E2 = Y3Y3Y1Y0 = 0100 e E3 = 
Y3Y3Y1Y0 = 1000. 
Como colocado anteriormente, existem técnicas que permitem definir a melhor designação. No 
entanto, nesta fase do curso estas técnicas serão desconsideradas e poderá ser usada qualquer 
designação (melhor ou pior) mas que leve a uma implementação da MdE. 
d. Desenho da arquitetura do controlador: como já foi definido que seriam duas variáveis de 
estado, pode-se utilizar então um registrador de dois bits na implementação do circuito, como mostrado 
abaixo: 
Circuito combinacionalI
Y
0
Y
1
F
y
0
y
1
Clock
 
 
e. Construção da tabela verdade: 
Estados atuais Entrada Estados próximos Saída 
Y1 Y0 I y1 y0 F 
0 0 0 0 0 0 
0 0 1 0 1 0 
0 1 0 1 0 0 
0 1 1 1 0 0 
1 0 0 1 1 0 
1 0 1 1 1 0 
1 1 0 0 0 1 
1 1 1 0 0 1 
 16 
f. Definição das equações lógicas para as variáveis de saída e para as variáveis de estados 
próximos: pela tabela verdade têm-se: 
01010 YYIYYy += , 01011 YYYYy += e 01 YYF = 
g. Implementação do circuito lógico: sem qualquer simplificação se obtém o circuito 
mostrado abaixo onde, o registrador de dois bits foi implementado com dois flip-flops tipo D: 
 
 
Ex.1.5. Projetar um controlador que possa ser descrito pelo diagrama de estado mostrado 
abaixo, resultante do ex 1.3. 
 
a. Descrição do sistema por Tabela de Estado ou por Diagrama de Estado: esta tarefa, 
como no exemplo anterior, também já está cumprida no exemplo 1.3. 
b. Minimização do número de estados da Tabela ou do Diagrama de Estado: esta tarefa, 
para este exemplo, será também desconsiderada. 
 17 
c. Designação de estados: como a MdE apresenta cinco estados (E0, E1, E2, E3 e E4), estes 
cinco estados só podem ser representados com no mínimo três variáveis de estado já que 22 < 5 < 23. 
Nomeando as variáveis internas com a letra y, uma das designações possíveis seria então: 
Estados atuais: E0 = Y2Y1Y0 =000, E1 = Y2Y1Y0 = 001, E2 = Y2Y1Y0 = 010, 
E3 = Y2Y1Y0 = 011 e E4 = Y2Y1Y0 = 100. 
Estados próximos: e0 = y2y1y0 = 000, e1 = y2y1y0 = 001, e2 = y2y1y0 = 010, 
e3 = y2y1y0 = 011 e e4 = y2y1y0 = 100. 
Como no exemplo anterior, diversas outras designações também poderiam ser usadas. 
d. Desenho da arquitetura do controlador: como já foi definido que seriam três variáveis de 
estado, pode-se utilizar então um registrador de três bits na implementação do circuito, como mostrado 
abaixo: 
 
e. Construção da tabela verdade: 
Estados atuais Entrada Estados próximos Saída 
Y2 Y1 Y0 x y2 y1 y0 w 
0 0 0 0 0 0 0 0 
0 0 0 1 0 0 1 0 
0 0 1 0 0 1 0 0 
0 0 1 1 0 0 1 0 
0 1 0 0 0 0 0 0 
0 1 0 1 0 1 1 0 
0 1 1 0 0 1 0 0 
0 1 1 1 1 0 0 0 
1 0 0 0 0 1 0 1 
1 0 0 1 0 0 1 1 
1 0 1 0 - - - - 
1 0 1 1 - - - - 
1 1 0 0 - - - - 
1 1 0 1 - - - - 
1 1 1 0 - - - - 
1 1 1 1 - - - - 
Obs: os traços (-) representam situações don´t cares (é usual também o uso do X em lugar do traço). 
 18 
f. Definição das equações lógicas para as variáveis de saída e para as variáveis de estados 
próximos: nas situações em que o número de variáveis é maior ou igual a 4, uma melhor opção é usar 
mapas de Karnaugh para definir as equações dos estado próximo e da(s) saída(s). As combinações não 
usadas na designação dos estados são consideradas como don´t cares (não importam ou não influem) o 
que pode levar a uma melhor simplificação nas equações a se implementar, como se pode ver abaixo. 
 
xYYy 012 = , xYxYxYYy 02011 ++= , xYxYy 100 += e 2Yw = 
g. Implementação do circuito lógico: no circuito resultante, mostrado abaixo, o registrador de 
três bits foi implementado usando três flip-flops tipo D: 
 
 
 19 
Ex. 1.6. Projetar uma máquina de estado síncrona com duas entradas A e B e uma saída Z. A 
saída será 1 se A apresentar o mesmo valor (0 ou 1) durante dois ciclos prévios de clock ou se, após 
uma ocorrência verdadeira da primeira condição (A=0 ou A=1 durante dois ciclos prévios de clock), a 
entrada B for igual a 1 ou se mantiver em 1. Para qualquer outra situação a saída será 0 (zero). 
a. Descrição do sistema por Tabela de Estado e/ou por Diagrama de Estado: 
Entradas: AB. 
Saída(s): Z 
Desenvolvimento da Tabela de Estado: 
Descrição do estado atual Estado Estados próximos para Saída 
 Atual AB = 00 AB = 01 AB = 11 AB = 10 Z 
1 - Estado inicial Ein EcA0 EcA0 EcA1 EcA1 0 
2 - Chegou um 0 em A EcA0 EcA00 EcA00 EcA1 EcA1 0 
3 - Chegou um 1 em A EcA1 EcA0 EcA0 EcA11 EcA11 0 
4 - Chegou 00 em A EcA00 EcA00 EcA00 EcA1B1 EcA1 1 
5 - Chegou 11 em A EcA11 EcA0 EcA0B1 EcA11 EcA11 1 
6 - Chegou 001 em A mas B 
é igual a 1 
EcA1B1 EcA0 EcA0B1 EcA11 EcA11 1 
7 - Chegou 110 em A mas B 
é igual a 1 
EcA0B1 EcA00 EcA00 EcA1B1 EcA1 1 
 
b. Minimização do número de estados da Tabela: fazendo uma análise da Tabela de Estado 
acima percebe-se que o estado atual EcA00 (linha 4) é perfeitamente idêntico ao estado atual EcA0B1 
(linha 7) e que o estado EcA11 (linha 5) é perfeitamente idêntico ao estado EcA1B1 (linha 6). De tal 
forma que a Tabela de Estado que representa o sistema proposto pode ser minimizada com a exclusão 
dos estados EcA0B1 e EcA1B1 resultando na Tabela de Estado mostrada abaixo. 
Descrição do estado atual Estado Estados próximos para Saída 
 Atual AB = 00 AB = 01 AB = 11 AB = 10 Z 
1 - Estado inicial Ein EcA0 EcA0 EcA1 EcA1 0 
2 - Chegou um 0 em A EcA0 EcA00 EcA00 EcA1 EcA1 0 
3 - Chegou um 1 em A EcA1 EcA0 EcA0 EcA11 EcA11 0 
4 - Chegou 00 em A EcA00 EcA00 EcA00 EcA11 EcA1 1 
5 - Chegou 11 em A EcA11 EcA0 EcA00 EcA11 EcA11 1 
 
c. Designação de estados: como a MdE apresenta cinco estados (Ein, EcA0, EcA1, EcA00 e 
EcA11), estes cinco estados, como no caso anterior, só podem ser representados com no mínimo três 
variáveis de estado já que 22 < 5 < 23. Nomeando as variáveis internas com a letra y, uma das 
designações possíveis seria então: 
Estados atuais: Ein = Y2Y1Y0 = 000, EcA0 = Y2Y1Y0 = 001, EcA1 = Y2Y1Y0 = 010, 
 20 
EcA00 = Y2Y1Y0 = 011 e EcA11 = Y2Y1Y0 = 100. 
Estados próximos: ein0 = y2y1y0 = 000, e cA0 = y2y1y0 = 001, e cA1 = y2y1y0 = 010, 
e cA00 = y2y1y0 = 011 e e cA11 = y2y1y0 = 100. 
Como nos exemplos anteriores, outras designações poderiam ter ser usadas. 
d. Desenho da arquitetura do controlador: como já foi definido que seriam três variáveis de 
estado, pode-se utilizar então, como no exemplo anterior, um registrador de três bits na implementação 
do circuito, como mostrado abaixo: 
 
 
e. Construção da tabela verdade: 
Estados atuais Entradas Estados próximos Saída 
Y2 Y1 Y0 A B y2 y1 y0 Z 
0 0 0 0 - 0 0 1 0 
0 0 0 1 - 0 1 0 0 
0 0 1 0 - 0 1 1 0 
0 0 1 1 - 0 1 0 0 
0 1 0 0 - 0 0 1 0 
0 1 0 1 - 1 0 0 0 
0 1 1 0 - 0 1 1 1 
0 1 1 1 0 0 1 0 1 
0 1 1 1 1 1 0 0 1 
1 0 0 0 0 0 0 1 1 
1 0 0 0 1 0 1 1 1 
1 0 0 1 - 1 0 0 1 
1 0 1 - - - - - - 
1 1 0 - - - - - - 
1 1 1 - - - - - - 
Obs: os traços (-) estão representando situações don´t cares. 
f. Definição das equações lógicas para as variáveis de saída e para as variáveis de estados 
próximos: usando mapas de Karnaugh para cinco variáveis obtêm-se: 
AYYBAYAYy 01122 ++= , AYYBAYYy 12201 ++= , Ay0 = e 1012 YYYZ += 
 21 
 
 
g. Implementação do circuito lógico: no circuito resultante, mostrado abaixo, o registrador de 
três bits foi implementado usando três flip-flops tipo D: 
(Desenhar esquema do circuito com flip-flops tipo D) 
3.1.1. Estado inicial de um controlador 
Nas implementações das MdE acima, após a designação dos estados, observa-se que algumas 
combinações, constituintes das tabelas de estado, podem não se constituir em estados válidos da MdE 
(nas simplificações consideradas como d´ont cares). No entanto, quando se liga um componente 
seqüencial, tipo latch, flip-flop, registro, etc, não se pode garantir qual o seu estado inicial e que, por 
fatalidade, pode ser um estado não constituinte da MdE. Caso isso venha a ocorrer, pode levar a MdE a 
ter um comportamento imprevisível. Existem duas possibilidades reais de se evitar que isto venha a 
ocorrer: a primeira é verificar todos os estados possíveis de uma tabela de estado, inicialmente não 
constituintes da MdE e os incluir na MdE, gerando-se um caminho direto deste estado para um estado 
válido da MdE na primeira ocorrência de clock e; a segunda é garantir que ao ser ligado, a MdE 
assuma um estado inicial válido e de preferência que este estado válido seja um no qual, todas as 
variáveis assumam o valor zero ao ligar (condição de power-on reset). Sendo esta segunda, a melhor 
alternativa de projeto. Pode-se incluir no circuito de power-on reset uma chave de reset manual que 
permita reinicializar o circuito sempre que desejável. O circuito modelado pela MdE do exemplo 1.6, 
com esta opção incluída, pode ser visto na figura 11 onde, a malha RC irá determinar o tempo do pulso 
de reset ao se ligar o circuito ou ao ser reinicializado através da chave S. O resistor Rc deve ser 
dimensionado simplesmente para reduzir a corrente de descarga do capacitor C na reinicialização e o 
diodo D auxilia na descarga do capacitor quando o circuito é desligado. 
 
 22 
 
Figura 11 – Circuito modelado pela MdE do exemplo 1.6 com malha de reset 
Exercício: 
Implementar o marcador de passo descrito no livro texto do Vahid (pags 138, 139). 
4. Projeto de Sistemas Seqüenciais usando flip-flops 
4.1. Projeto de Sistemas Seqüenciais Síncronos usando flip-flops 
O procedimento para projeto de sistemas seqüenciais síncronos usando flip-flops é muito 
semelhante ao projeto de sistemas seqüências usando registradores, isto pode ser constatado nos itens 
descritos abaixo, diferenciando-se basicamente nos três itens destacados em negrito. 
1. Pela descrição feita para o sistema construir uma tabela ou um diagrama de estado que o 
caracterize. Procurar usar caracteres simbólicos (mnemônicos) na definição dos estados. 
2. (Opcionalmente) Minimizar o número de estados da tabela/diagrama de estado. 
3. Escolher umgrupo de variáveis que possam representar os estados anteriormente nomeados 
(lembrando que para codificar 2n estados é necessário um número mínimo de n variáveis de 
estado). 
4. Codificados os estados, montar uma tabela de transição onde seja possível definir a 
condição de estado próximo/saída para cada condição de entrada/estado atual aplicado. 
5. Construir uma tabela de desenvolvimento para cada variável de estado. 
6. Escolher um flip-flop como elemento de memória para cada variável de estado. 
7. Definir, a partir da tabela de desenvolvimento, equações de excitação simplificadas 
para os diversos flip-flops associados às variáveis de estado. 
 23 
8. Definir, a partir da tabela de transição, equações simplificadas para as variáveis de saída. 
9. Desenhar um circuito lógico que represente as equações anteriormente definidas tendo, 
todas as unidades de memória (flip-flops) ligadas ao clock externo aplicado. 
Exemplo: Projetar a máquina de estado síncrona do exmplo 1.6 usando flip-flops. 
1. Desenvolvimento da tabela de estado: 
Descrição do estado Estado Atual Estados Próximos para AB iguais a Saída 
 AB=00 AB=01 AB=11 AB=10 Z 
1-Inicial In A0 A0 A1 A1 0 
2-Chegou 0 em A A0 A00 A00 A1 A1 0 
3-Chegou 1 em A A1 A0 A0 A11 A11 0 
4-Chegou 00 em A A00 A00 A00 A1B1 A1 1 
5-Chegou 11 em A A11 A0 A0B1 A11 A11 1 
6-Chegou 001 em A e B é 1 A1B1 A0 A0B1 A11 A11 1 
7-Chegou 110 em A e B é 1 A0B1 A00 A00 A1B1 A1 1 
2. Minimização de estados: 
A idéia básica de um procedimento formal para minimização de estados é um processo de 
identificação de estados equivalentes. Dois estados são considerados equivalentes se para todas as 
combinações de estado total aplicadas duas condições forem verdadeira: a primeira que os dois estados 
produzam os mesmos valores para as variáveis de saída e a segunda é que apresentem os mesmos, ou 
equivalentes, estados próximos. 
Como colocado acima, fazendo-se uma análise da tabela de estado desenvolvida percebe-se que 
os estados 4 e 5 são, respectivamente, equivalentes aos estados 7 e 6. De tal forma que a tabela de 
estado que representa o sistema proposto pode ser simplificada, gerando a tabela mostrada abaixo. 
Descrição do estado Estado Atual Estados próximos para Saída 
 AB=00 AB=01 AB=11 AB=10 Z 
1-Inicial In A0 A0 A1 A1 0 
2-Chegou 0 em A A0 A00 A00 A1 A1 0 
3-Chegou 1 em A A1 A0 A0 A11 A11 0 
4-Chegou 00 em A A00 A00 A00 A11 A1 1 
5-Chegou 11 em A A11 A0 A00 A11 A11 1 
3. Codificação: 
Como a máquina apresenta cinco estados será possível codificá-los com um número mínimo de 
3 variáveis denominadas, por exemplo, de Y0, Y1 e Y2. Qualquer código binário poderá ser usado na 
designação dos estados. Escolhendo o código binário puro tem-se: 
 24 
In = 000, A0 = 001, A1 = 010, A00 = 011 e A11 = 100 
Os estados 101, 110 e 111 serão considerados irrelevantes para efeito de simplificação por 
mapa de Karnauh. 
4/5. Tabela de transição/desenvolvimento: 
A tabela de transição mostra o comportamento das variáveis de estado na mudança de estado 
atual para estado próximo. Este comportamento pode ser representado por uma tabela de 
desenvolvimento onde: 
a. Se uma variável apresentar valores de estado atual e de estado próximos iguais diz-se que 
houve um desenvolvimento estático que pode ser do tipo "0" (0→0) ou "1" (1→1). 
b. Se uma variável apresentar valores diferentes de estado atual e de estado próximo diz-se que 
houve um comportamento dinâmico que pode ser do tipo α (0→1) ou β (1→0). 
Entradas Estado Atual Estado 
Próximo 
Comportamento Desenvolvimento Saída 
A B Y0 Y1 Y2 yo y1 y2 Y0' Y1' Y2' Y0' Y1' Y2' Z 
0 X 0 0 0 0 0 1 0→0 0→0 0→1 0 0 α 0 
1 X 0 0 0 0 1 0 0→0 0→1 0→0 0 α 0 0 
0 X 0 0 1 0 1 1 0→0 0→1 1→1 0 α 1 0 
1 X 0 0 1 0 1 0 0→0 0→1 1→0 0 α β 0 
0 X 0 1 0 0 0 1 0→0 1→0 0→1 0 β α 0 
1 X 0 1 0 1 0 0 0→1 1→0 0→0 α β 0 0 
0 X 0 1 1 0 1 1 0→0 1→1 1→1 0 1 1 1 
1 0 0 1 1 0 1 0 0→0 1→1 1→0 0 1 β 1 
1 1 0 1 1 1 0 0 0→1 1→0 1→0 α β β 1 
0 0 1 0 0 0 0 1 1→0 0→0 0→1 β 0 α 1 
0 1 1 0 0 0 1 1 1→0 0→1 0→1 β α α 1 
1 X 1 0 0 1 0 0 1→1 0→0 0→0 1 0 0 1 
 
6. Escolha do flip-flop: 
Embora a escolha do tipo do flip-flop num primeiro momento seja puramente intuitiva 
sugere-se a escolha dos tipos D e JK. Neste exemplo, será feito opção pelo tipo D. 
7. Tabela de excitação: 
Antes de montar a tabela de excitação, por análise de sua tabela verdade, é necessário que se 
definam as condições de entrada que levam o tipo de flip-flop escolhido à apresentar um 
 25 
desenvolvimento "0", "1", α ou β. As tabelas de excitação para os flip-flops RS, D, JK e T são 
mostradas a seguir. 
7.1 Tabelas de excitação para os flip-flops D, JK, T e RS. 
RS: 
 
 
JK 
 
 
D 
 
 
T 
 
 
Escolhendo-se o flip-flop tipo D para o projeto, a tabela de transição, de comportamento dos 
flip-flops e suas correspondentes condições de excitação são mostradas a seguir. 
 26 
Entradas Estado Atual Estado Próximo Comportamento Condição de entrada para 
o flip-flop D 
Saída 
A B Y0 Y1 Y2 yo y1 y2 Y0' Y1' Y2' D0 D1 D2 Z 
0 X 0 0 0 0 0 1 0→0 0→0 0→1 0 0 1 0 
1 X 0 0 0 0 1 0 0→0 0→1 0→0 0 1 0 0 
0 X 0 0 1 0 1 1 0→0 0→1 1→1 0 1 1 0 
1 X 0 0 1 0 1 0 0→0 0→1 1→0 0 1 0 0 
0 X 0 1 0 0 0 1 0→0 1→0 0→1 0 0 1 0 
1 X 0 1 0 1 0 0 0→1 1→0 0→0 1 0 0 0 
0 X 0 1 1 0 1 1 0→0 1→1 1→1 0 1 1 1 
1 0 0 1 1 0 1 0 0→0 1→1 1→0 0 1 0 1 
1 1 0 1 1 1 0 0 0→1 1→0 1→0 1 0 0 1 
0 0 1 0 0 0 0 1 1→0 0→0 0→1 0 0 1 1 
0 1 1 0 0 0 1 1 1→0 0→1 0→1 0 1 1 1 
1 X 1 0 0 1 0 0 1→1 0→0 0→0 1 0 0 1 
 
Para concluir o projeto basta agora montar os mapas de Karnauh, simplificar as funções de 
saída e de estado próximo e implementar o circuito. 
4.2. Projeto de Sistemas Seqüenciais Assíncronos usando flip-flops 
 O projeto de um sistema seqüencial assíncrono se caracteriza pela possibilidade de alguns 
elementos internos (normalmente flip-flops de estágios menos significativos) servirem de fontes de 
clock internos. 
 Para se proceder no projeto assíncrono, deve-se selecionar o elemento de memória que 
apresenta malha de execução mais simples (normalmente o que apresenta o maior número de 
transições) e nele entrar com o clock externo. Usando as transições dos flip-flops que são operados 
como fontes geradoras de clock, construir nova lógica combinacional para as variáveis de estados 
próximos, para as saídas e também para os sinais de clock gerados internamente, se necessário. 
Proceder sempre de um estágio para o próximo na tabela de transições, sem nunca retroceder (se um 
estágio n1 gera clock para um estágio n2, n2 não pode ser usado como fonte de clock para n1). 
 Para construir a nova lógica combinacional (o que significa construir nova tabela de transições), 
deve-se levar em conta que um flip-flop ao ser operado, pode apresentar um desenvolvimento 
dinâmico do tipo α ou β . Um desenvolvimento dinâmico α ocorre quando esse flip-flop passa de 
um estado RESET (Q = 0) para um estado SET (Q = 1) e um desenvolvimento β ocorre quando um 
flip-flop passa de um estado SET (Q = 1) para um estado RESET (Q = 0). Logicamente a saída 
complementar a Q passa por transições opostas. Pode-se observar que qualquer dessas transições 
podem ser utilizadas como fontes de clock internos basta que a transição escolhida coincida sempre 
com todas as transições sofridas nos estágios que as recebem como clock gerado internamente. 
 27 
 A decisão de qual das transições pode ser utilizada deve ser tomada à partir da análise da tabela 
de transições originalmente desenvolvida (equivalente a desenvolvida para o projeto síncrono). A 
prática de desenvolvimento de projetos seqüenciais síncronos volta-se exclusivamente ao uso de flip-
flops que respondem na transição negativa ou positiva do clock. 
 Parte-se da premissa de que um pulso de clock só precisa ocorrer para um flip-flop quando ele 
precisar apresentar um comportamento dinâmico. 
 Exemplo. 
 Projetar, com flip-flops tipo JK, um circuito seqüencial que implemente a MdE cujo 
comportamento é especificadopelo diagrama de estado abaixo. 
 
 Designação dos estados: 
E0 = 000, E1 = 001, E2 = 010, E3 = 011, E4 = 100, E5 = 101, E6 = 110, E7 = 111 
 
Variáveis de 
Estado Atual 
Variáveis de 
Estado Próximo 
Desenvolvimento 
(Proj. Síncrono) 
Flip-
flop 2 
Flip-
flop 1 
Flip-
flop 0 
Q2 Q1 Q0 q2 q1 q0 q2’ q1’ q0’ J2 K2 J1 K1 J0 K0 
0 0 0 0 0 1 0 0 α 0 X 0 X 1 X 
0 0 1 0 1 0 0 α β 0 X 1 X X 1 
0 1 0 0 1 1 0 1 α 0 X X 0 1 X 
0 1 1 1 0 0 α β β 1 X X 1 X 1 
1 0 0 1 0 1 1 0 α X 0 0 X 1 X 
1 0 1 1 1 0 1 α β X 0 1 X X 1 
1 1 0 1 1 1 1 1 α X 0 X 0 1 X 
1 1 1 0 0 0 β β β X 1 X 1 X 1 
Simplificando se obtêm: 
J0 = K0 = 1; J1 = K1 = Q0; J2 = K2 = Q1.Q0 
Para complementar a tabela de transição que definirá a nova lógica combinacional para o 
sistema assíncrono se considera que: 
a. A malha combinacional do flip-flop que recebe o clock externo deve permanecer a mesma 
do projeto síncrono. 
 28 
b. Qualquer tipo de desenvolvimento de um flip-flop, receptor de linha de clock gerado 
internamente só deverá ser mantido igual ao do projeto síncrono se, coincidente com a 
transição do flip-flop fonte de clock, ele sofra também uma transição. Todas as outras 
situações devem ser consideradas d’ont cares. 
 Observando o mapa de transição do projeto síncrono se observa que: o estado próximo de mais 
simples implementação, além de representar o bit menos significativo nas designações feitas, 
corresponde a variável q0; que a variável q1 muda de estado sempre que a variável q0 sofre uma 
transição do tipo β e que, a variável q3 só muda de estado quando ocorre uma transição também do 
tipo β na variável q1. Das observações feitas pode-se concluir que a saída do flip-flop 0 pode servir de 
clock para o flip-flop 1 e que a saída do flip-flop 1 pode servir de clock para o flip-flop 3. O mapa de 
transição complementar para o projeto assíncrono, com as respectivas condições de excitação para os 
três flip-flops JK é mostrado abaixo. 
Variáveis de 
Estado Atual 
Var. de Estado 
Próximo 
Desenvolvimento 
(Proj. Síncrono) 
Desenvolvimento 
(Proj.Assíncrono) 
Flip-
flop 2 
Flip-
flop 1 
Flip-
flop 0 
Q2 Q1Q0 q2 q1 q0 q2’ q1’ q0’ Q2’ q1’ q0’ J2 K2 J1 K1 J0 K0 
0 0 0 0 0 1 0 0 α X X α X X X X 1 X 
0 0 1 0 1 0 0 α β X α β X X 1 X X 1 
0 1 0 0 1 1 0 1 α X X α X X X X 1 X 
0 1 1 1 0 0 α β β α β β 1 X X 1 X 1 
1 0 0 1 0 1 1 0 α X X α X X X X 1 X 
1 0 1 1 1 0 1 α β X α β X X 1 X X 1 
1 1 0 1 1 1 1 1 α X X α X X X X 1 X 
1 1 1 0 0 0 β β β β β β X 1 X 1 X 1 
 O que leva a implementação: 
 J2 = K2 = 1, J1 = K1 = 1 J0 = K0 = 1 
Se os flip-flops escolhidos respondem na transição negativa de clock, a saída Q0 será clock para 
o flip-flop 1 e a saída Q1 será clock para o flip-flop 2 e se respondem na transição positiva, as saída 
complementares Q0 e Q1 é que servirão, respectivamente, de sinais de clock para os flip-flops 1 e 2. 
Exercício: 
Implementar um contador up-dowm módulo 8 que opere assincronamente. O controle de contar 
up ou down é feito por uma variável de entrada I. Use flip-flops JK que respondem a transição negativa 
de clock. 
 29 
5. Análise de Sistemas Seqüenciais – Engenharia Reversa 
5.1. Análise de Sistemas Seqüenciais que Operam no Modo Fundamental 
Para que um circuito seqüencial seja operado no modo fundamental existe uma restrição 
básica: que possíveis mudanças nas variáveis de entrada só venham a ocorrer a partir do instante em 
que o sistema atinja um estado interno estável1. 
Ocorrerá a estabilidade de um sistema seqüencial operando no modo fundamental quando, para 
uma mesma condição de entrada, o estado próximo venha a se tornar igual ao estado atual. 
Por regra, quando a análise é feita por tabela de estado, costuma-se colocar um círculo sobre os 
estados próximos que determinam uma estabilidade ao sistema. 
Se num sistema seqüencial que opera no modo fundamental, um estado presente total é mantido 
por longo tempo e este circuito não atinge um estado interno estável, para esta dada condição de 
entrada o circuito poderá variar continuamente seus valores de saída, inviabilizando seu uso (pelo 
menos se esta condição de entrada não for evitada) em algumas aplicações práticas. 
A partir do instante em que é aplicado um estado presente total até o instante em que o circuito 
atinge um estado interno estável, podem surgir, como característica de saída, alguns estados espúrios. 
A existência e o tempo de ocorrência destes estados espúrios de saída podem ser previstos com certa 
precisão, por análise de uma tabela ou de um diagrama de estado, considerados os atrasos típicos de 
todos os elementos presentes ao circuito. 
Um procedimento que pode ser seguido para se fazer à análise de um circuito seqüencial que 
opera no modo fundamental é o seguinte: 
1. identificar no circuito, quem são as variáveis de entrada, as variáveis de saída e as variáveis 
de estado que o caracterizam; 
2. definir equações lógicas para as variáveis de saída e de estado próximo em função das 
variáveis de entrada e de estado atual; 
3. montar uma tabela de estado considerando todas as combinações possíveis das variáveis de 
entrada e de estado atual; 
 
1É recomendável também que se opere o sistema de tal forma que apenas uma variável mude de estado a cada instante. 
 30 
4. gerar uma tabela auxiliar a partir da tabela anterior tendo como estados iniciais os estados 
internos estáveis e, através de mudanças nas condições de entrada (de forma que apenas uma das 
variáveis mude a cada instante), completar a tabela acompanhando o comportamento do circuito; 
5. verificar se na mudança de um estado atual para estado próximo não existe possibilidade de 
ocorrerem estados espúrios e, como o circuito se comporta em caso destes estados virem a ocorrer; 
6. verificar a estabilidade total do circuito; 
7. Identificar estados redundantes ou desnecessários; 
8. montar um diagrama de estado definitivo e conclusivo do comportamento do circuito. 
 
Exemplo: Analisar o circuito em modo fundamental representado abaixo: 
 
 
5.2. Análise de Sistemas Seqüenciais Síncronos 
Um procedimento que pode ser seguido para se fazer a análise de um circuito seqüencial 
síncrono é o seguinte: 
1. identificar as variáveis de entrada, as variáveis de saída e as variáveis de estado do circuito; 
2. identificar no circuito, quais as variáveis de excitação para cada variável de estado e a sua 
relação com as variáveis de entrada e de estado atual; 
3. definir equações lógicas para as variáveis de estado próximo dos diversos flip-flops presentes 
no circuito em função de suas variáveis de excitação; 
 31 
4. definir equações para as variáveis de saída; 
5. montar uma tabela de estado e um diagrama de estado que caracterize completamente o 
circuito; 
6. identificar estados redundantes ou desnecessários. 
Exemplos. 
5.3. Análise de Sistemas Seqüenciais Assíncronos 
O Procedimento para a análise de sistemas seqüencial assíncronos é o seguinte: 
1. identificar as variáveis de entrada, as variáveis de saída, as variáveis de estado e 
adicionalmente, identificar que sinais de clock são gerados internamente; 
2. identificar no circuito, quais as variáveis de excitação para cada variável de estado e a sua 
relação com as variáveis de entrada e de estado atual; 
3. definir equações lógicas para as variáveis de estado próximo dos diversos flip-flops presentes 
no circuito em função de suas variáveis de excitação; 
4. definir equações para as variáveis de saída; 
5. definir equações lógicas para o(s) clock(s) gerado(s) internamente; 
6. montar um timing através do qual se possa identificar a presença de estados espúrios; 
7. montar uma tabela de estado e um diagrama de estado que caracterize completamente o 
circuito; 
8. identificar estados redundantes ou desnecessários. 
 
 32 
6. Otimização de Sistemas Seqüenciais 
 A otimização de um sistema seqüencial podeser obtida otimizando-se o circuito da malha 
combinacional ou o circuito da malha de realimentação (lógica seqüencial) 
6.1. Otimização da lógica combinacional 
 A otimização da lógica combinacional pode ser através de: 
� K-Mapas 
� Métodos algébricos. 
6.2. Otimização da lógica seqüencial 
 A otimização da lógica seqüencial pode ser obtida por: 
� Redução de estados 
� Boa designação de estados 
6.2.1. Métodos de redução de estados 
 Os métodos usados para redução de estados são: 
� Inspeção 
� Particionamento sucessivo 
� Tabela de Implicação 
Uma redução de estados só será possível se a MdE apresentar estados equivalentes. Dois 
estados são ditos equivalentes quando; 
� Apresentam para as mesmas condições de entrada os mesmos valores de saída; 
� Para todas as possíveis seqüências de entrada, apresentem estados próximos iguais ou 
equivalentes. 
Propriedades entre estados equivalentes: 
� Simetria: A ≡ A 
� Reflexibilidade: A ≡ B → B ≡ A 
� Transitividade: A ≡ B e B ≡ C → A ≡ C 
 
 
 33 
6.2.1.1. Redução de estados por inspeção 
Exemplo 1. Por inspeção, ver-se que as linhas do estado 'B' e do estado 'D' são idênticas, logo o 
estado 'B' é equivalente ao estado 'D' (B ≡ D). A tabela de estado simplificada é obtida eliminando uma 
das linhas (no caso optou-se pela linha D). 
 → 
Exemplo 2: Por inspeção, pode-se perceber que os estado 'B' e 'D' da tabela abaixo, à esquerda, 
são equivalentes (B ≡ D) resultando na tabela mostrada à direita por eliminação do estado D, 
substituindo os estados próximos ‘D’ por ‘B’. 
 
Novamente, por inspeção, ver-se que na nova tabela os estado ‘A' e ‘E' são equivalentes 
resultando na tabela abaixo por eliminação do estado E. 
 
6.2.1.2. Redução de estados por particionamento sucessivo 
Definição de partição: 
Se Pk = {A1, A2, …, Aq} é uma coleção de subconjuntos de S, Pk será uma partição de S se e 
somente se: 
SA
q
i
i =
=
U
1
 e jiAA ji ≠∀Φ=I 
 34 
Todos os subconjuntos Ai de Pk são chamados de blocos (ou partes) da partição Pk. 
O método da partição consiste na determinação de uma partição Pk,, composta por blocos de S, 
cada um deles contendo um ou mais estados de S, onde, os estados contidos em cada bloco de Pk 
devem ser 'k' equivalentes, ou seja, equivalentes para qualquer seqüência de comprimento 'k'. 
O processo para determinação das partições sucessivas envolve os seguintes passos: 
1. A primeira partição P1 deve ser formada por um conjunto de blocos onde, os elementos de 
cada bloco apresentam as mesmas saídas para cada uma das possíveis condições de entrada. 
2. As partições sucessivas P2, P3, até Pk são determinadas mantendo-se, num mesmo bloco de Pi, 
apenas os estados de S, que apresentem, para as mesmas condições de entrada, estados próximos 
pertencentes a um mesmo bloco de Pi-1. O processo é interativo e só deve parar quando for encontrada 
uma partição Pk = Pk-1. Neste caso, Pk é dita k equivalente e os estados contidos em cada um dos seus 
blocos são equivalentes. 
Exemplo 1: analisar por particionamento sucessivo a redução de estados da tabela dada a seguir. 
 
Para formar a partição P1 é necessário agrupar em blocos os estados que possuem as mesmas 
saídas para cada um dos valores das entradas. 
Observando a tabela anterior verifica-se que P1 = {(A, D), (B, E), (C, F), (G, H)} já que: 
• A e D apresentam saídas iguais a 0 (para x = 0 e para x = 1); 
• B e E apresentam saídas iguais a 1 (para x = 0) e a 0 (para x = 1); 
• C e F apresentam saídas iguais a 0 (para x = 0) e a 1 (para x = 1) e; 
• G e H, apresentam saídas iguais a 1 (para x = 0 e para x = 1). 
A partição P2 é obtida observando-se se, para as mesmas condições de entrada, os estados 
próximos de cada bloco de P1 se mantêm ou pertencem a um mesmo bloco. Caso isto ocorra, o bloco é 
repetido em P2. Caso contrário o bloco deve ser particionado e as novas partições colocadas em P2 
como demonstrado a seguir. 
 35 
Definição dos estados próximos para cada bloco de P1 para x = 0 e para x = 1: 
( )
( )

→
→
→
AD
BE
DA
,1
,0
),( , 
( )
( )

→
→
→
CF
DA
EB
,1
,0
),( , 
( )
( )

→
→
→
DA
CC
FC
,1
,0
),( , 
( )
( )

→
→
→
BG
CH
HG
,1
,0
),( 
Pelas definições de estados próximos acima, percebe-se que apenas o bloco (G, H) apresenta 
estados próximos pertencentes a blocos diferentes em P1 o que força ao bloco (G, H) ser particionado 
nos blocos (G) e (H). 
Daí se concluí que P2 = {(A, D), (B, E), (C, F), (G), (H)}. Como P2 ≠ P1, o processo de 
particionamento deve ser continuado. Como os três primeiros blocos não se alteraram e os dois 
particionados possuem apenas um estado, pode-se concluir que P3 = {(A, D), (B, E), (C, F), (G), (H)} 
ou seja: P3 = P2. O processo de particionamento pode ser encerrado obtendo-se que A ≡ D, B ≡ E e que 
C ≡ F. 
Fazendo E1 ≡ A ≡ D, E2 ≡ B ≡ E, E2 ≡ C ≡ F, E4 ≡ G e E5 ≡ H, obtêm-se a tabela de estado 
mínima dada a seguir. 
Estados Próximos/Saídas para Estados 
Atuais Y x = 0 x = 1 
E1 e2/0 e1/0 
E2 e1/1 e3/0 
E3 e3/0 e1/1 
E4 e5/1 e4/1 
E5 e3/1 e2/1 
Exercício: pelo método das partições sucessivas reduzir o número de estados das tabelas abaixo: 
1: 
2: 
 36 
6.2.1.3 Algoritmo para redução de estados através de uma Tabela de Implicação 
1. Construir uma tabela triangular onde se apresentem, não repetitivos, todos os estados 
possíveis da máquina. 
2. Marcar os pares de estado que apresentam diferentes saídas como não equivalentes. 
3. Para cada par de estado não marcado escrever os estados próximos para os mesmos valores 
de entrada. 
4. Para cada par de estados não marcado, marcar os estados que apresentem estados próximos 
não equivalentes como não equivalentes. 
5. Repetir o passo 3 até que não ocorra qualquer mudança ou que todos os estados sejam 
marcados. 
6. Reduzir a um estado todos os pares não marcados, observando possíveis estados 
equivalentes pela propriedade da transitividade. 
7. Quando o estado próximo for o próprio par em análise, marcar já como equivalente 
utilizando a marcação de um ponto cheio “•” ou da marca de ok “�”. 
Exemplo: usando tabela de implicação reduzir o número de estados da tabela abaixo. 
Tabela original Passo 1 
 
 
Passo 2 Passo 3 
 
 37 
Passo 4 Passo 5 
 
Após o passo 5, verifica-se que nenhuma célula poderá ser riscada novamente, portanto todos os 
pares de estados não riscados, bem como aqueles com a marca '•' nas células, correspondem aos pares 
de estados equivalentes entre si, que são: 
A≡F, B≡C, B≡H e C≡H. 
Pela propriedade da transitividade, tem-se: B≡C≡H. Para se construir a nova tabela de estado 
reduzida, faz-se: a≡A≡F, b≡B≡C≡H, c≡D, d≡E e e≡G. 
Tabela de estado reduzida 
 
 
Exercício: usando tabela de implicação reduzir o número de estados da tabela abaixo. 
 
 38 
6.2.2. Regras para escolha de uma boa designação de estados 
1. (R ↓) Estados que apresentem o mesmo estado próximo para uma mesma condição de 
entrada devem receber designações adjacentes. 
2. (R →) Estados que são os estados seguintes de um único estado presente, sob condições de 
entradas adjacentes, devem receber designações adjacentes. 
3. (R ×) Estados que apresentem o mesmo estado próximo para condições de entradas 
diferentes devem receber designações adjacentes. 
4. As saídas devem ter a máxima adjacência para os seus 1´s (ou 0´s). 
5. Devem ser satisfeitas o maior número possível de adjacências. Todos os conflitos existentes 
entre as regras devem ser resolvidas à favor das regras 1, 2, 3 e 4, nesta ordem. 
Exemplo: estabelecer uma boa designação para os estados da tabela abaixo. 
Estados Próximos/Saídas para Estados 
Atuais Y x = 0 x = 1 
A a/0 b/0 
B a/0 c/0 
C d/0 c/0 
D a/0 b/1 
 Pela regra 1 (↓): 
(A, B), (A,D) e (B, D) devem ser adjacentes (mesmo estado próximo para x = 0). 
(A, D) e (B, C) devem ser adjacentes (mesmo estado próximo para x = 1) 
(A, D) se apresentando com peso2. 
 Pela regra 2 (→) 
 2(A, B), (A, C) e (D, C) devem ser adjacentes por serem estados próximos sob condições 
de entradas adjacentes. 
 Pela regra 3 (x) 
 Não existem estados com estados próximos iguais para condições distintas de entrada. 
 Pela regar 4 
 Só existe uma condição de saída 1. 
Resumo: melhores designações serão aquelas que tenham (A, D) adjacentes e (A, B) adjacentes: 
Com duas variáveis Y1 e Y0, duas boas designações seriam: 
 
 
 39 
Exercício: estabelecer uma boa designação para os estados da tabela abaixo. 
Estados Próximos/Saídas para Estados 
Atuais Y x = 0 x = 1 
A e/0 b/0 
B a/1 d/1 
C e/0 a/0 
D a/0 b/1 
E d/0 c/0