Eliminação de Estados Redundantes

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.

• 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

• a tabela reduzida
  

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

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.