Eliminação de Estados Redundantes
A primeira etapa do projeto de um circuito seqüêncial é considerar todos os estados de lembrança necessários. Em geral, são considerados alguns estados irrelevantes para a história do circuito. Então, deve-se eliminar os estados redundantes.
Tabela de Estado de Sistema Mealy com entrada X e saída Z
Fig.1
Nos estados p e q, independente de X, a saída Z é mesma e os estados seguintes os mesmos; então, p e q são iguais e um ou outro estado podem ser eliminado.
Para X=0, o estado seguinte é r, então os próximos estados do sistema dependem de r, e não se p ou q precederam r.
Exemplo
Fig.2
(a)Estados B e D tem saídas e estados seguintes iguais; o estado D é desnecessário e pode ser eliminado; substituir o estado D pelo estado B na tabela (a) para gerar a tabela (b).
(b)Os estados A e E são equivalentes, então eliminamos o estado E e substituimos o estado E pelo estado A na tabela (b) para se obter a tabela (c).
(c) A tabela (c) não tem estados semelhantes, então é a tabela de estados reduzida.
Eliminação de Estados Redundantes por Partição
Estados Idênticos - têm estados seguintes e saídas idênticas, então um estado pode ser eliminado.
Uma tabela de estados pode ter estados redundantes mesmo quando a tabela de estados não mostra linhas com estados seguintes e saídas idênticas.
A tabela de estados abaixo não mostra linhas com dados de saídas e estados seguintes idênticos.
|
PS
|
NS/Z
|
|
X=0
|
X=1
|
|
A
|
B/0
|
C/0
|
|
B
|
D/0
|
E/0
|
|
C
|
G/0
|
E/0
|
|
D
|
H/0
|
F/0
|
|
E
|
G/0
|
A/0
|
|
F
|
G/1
|
A/0
|
|
G
|
D/0
|
C/0
|
|
H
|
H/0
|
A/0
|
- os itens dos dados de saída são os mesmos em todos os estados, exceto F; o estados F é diferente de todos os demais; todos outros estados têm a mesma saída, então esses estados são todos o mesmo estado.
- os estados A, B, C, D, E, G, e H estão em uma partição(1) e F em outra partição(2)
|
PS
|
NS/Z
|
|
X=0
|
X=1
|
|
A1
|
B1
|
C1
|
|
B1
|
D1
|
E1
|
|
C1
|
G1
|
E1
|
|
D1
|
H1
|
F2
|
|
E1
|
G1
|
A1
|
|
F2
|
G1
|
A1
|
|
G1
|
D1
|
C1
|
|
H1
|
H1
|
A1
|
- o estado D para X=1 vai para F2, enquanto os outros estados vão para estados na mesma partição 1; então D não pertence á partição 1, então D deve ser removido da partição 1 e colocado na partição 3
|
PS
|
NS/Z
|
|
X=0
|
X=1
|
|
A1
|
B1
|
C1
|
|
B1
|
D3
|
E1
|
|
C1
|
G1
|
E1
|
|
D3
|
H1
|
F2
|
|
E1
|
G1
|
A1
|
|
F2
|
G1
|
A1
|
|
G1
|
D3
|
C1
|
|
H1
|
H1
|
A1
|
- os estados B e G não podem ficar na partição 1 porque o estado seguinte está na partição 3, então B e G ficam na mesma partição 4
|
PS
|
NS/Z
|
|
X=0
|
X=1
|
|
A1
|
B4
|
C1
|
|
B4
|
D3
|
E1
|
|
C1
|
G4
|
E1
|
|
D3
|
H1
|
F2
|
|
E1
|
G4
|
A1
|
|
F2
|
G4
|
A1
|
|
G4
|
D3
|
C1
|
|
H1
|
H1
|
A1
|
- os estados A, C e E devem ser removidos da partição 1 e ficarem na partição 5
|
PS
|
NS/Z
|
|
X=0
|
X=1
|
|
A5
|
B4
|
C5
|
|
B4
|
D3
|
E5
|
|
C5
|
G4
|
E5
|
|
D3
|
H1
|
F2
|
|
E5
|
G4
|
A5
|
|
F2
|
G4
|
A5
|
|
G4
|
D3
|
C5
|
|
H1
|
H1
|
A5
|
- todos os estados que estão na mesma partição (A, C e E na partição 5, e B e G na partição 4) têm itens de dados de entradas de estado seguinte em cada coluna que estão na mesma partição; quando a partição estiver completa, todos os estados ainda na mesma partição constituem o mesmo estado.
- como existem cinco partições então existem 5 estados diferentes.
- a = (A, C, E)
- b = (B, G)
- c = D
- d = F
- e = H
|
PS
|
NS/Z
|
|
X=0
|
X=1
|
|
a
|
b/0
|
a/0
|
|
b
|
c/0
|
a/0
|
|
c
|
e/0
|
d/0
|
|
d
|
b/1
|
a/0
|
|
e
|
e/0
|
a/0
|
Atribuições de Estados
Algumas atribuições de estados são melhores que outras. Dependendo das atribuições escolhidas há um efeito sobre os 0s, 1s e Xs nos mapas K, produzindo expressões lógicas mais simples. Porém não há regras facilmente aplicáveis para escolher uma boa atribuição de estados.
Projetos Alternativos
A sistemática desenvolvida acima busca a economia do projeto de sistemas seqüênciais: usar a menor quantidade de flip-flops para a memória do sistema e de portas para a lógica. Quando o hardware não é um fator limitador do projeto, isto é, o custo do hardware é baixo, então é vantajoso empregar sistemáticas de projeto mais intuitivas, que aproveitem componentes comuns e forneçam circuitos cujas funções sejam mais explicítas.
A figura abaixo mostra um detetor de seqüências baseado em registrador de deslocamento. O detetor responde a seqüência de entrada X=10010 que é capaturada serialmente em seqüência no tempo e tornandos disponíveis em determinado instante.
Fig.3
O sistema da figura acima usa quatro flip-flops que produzem dezesseis estados, enquanto que empregando a sistemática de menos estados seriam necessários apenas cinco estados, ou três flip-flops, que significa uma memória menor.
