SIMPLIFICASIMPLIFICAÇÃO SIMPLIFICAÇÃO DE CIRCUITOS …iris.sel.eesc.usp.br/sel414/15-Simplificacao_Sequenciais.pdf · EquivalênciaEquivalência Os Estados S1, S2, ...., Sj de

Sel 414 - Sistemas Digitais Prof. Homero Schiabel

Sel 414 Sel 414 -- Sistemas Digitais Sistemas Digitais Prof. Homero SchiabelProf. Homero Schiabel

SIMPLIFICAÇÃO DE CIRCUITOS SEQUENCIAIS

SIMPLIFICASIMPLIFICAÇÇÃO ÃO DE CIRCUITOS DE CIRCUITOS SEQUENCIAISSEQUENCIAIS

EquivalênciaEquivalência

Dois Estados são equivalentes se não podemos distinguir um do outro, ou seja, não podemos determinar em qual dos

dois estados equivalentes o Circuito Sequencial começa, aplicando-se entradas e observando suas saídas.

Se essa condição ocorrer, para qualquer seqüência de entrada, um dos Estados é redundante e pode ser removido

sem alterar o comportamento do circuito.

Dois Estados são equivalentes se não podemos distinguir um do outro, ou seja, não podemos determinar em qual dos

dois estados equivalentes o Circuito Sequencial começa, aplicando-se entradas e observando suas saídas.

Se essa condição ocorrer, para qualquer seqüência de entrada, um dos Estados é redundante e pode ser removido

sem alterar o comportamento do circuito.

Remover estados

redundantes éimportante

para

Remover estados

redundantes éimportante

para

Equivalência de estadosEquivalência de estados

1) Reduzir Custos2) Reduzir a Complexidade do Circuito3) Facilitar a Análise de Falhas

1) Reduzir Custos2) Reduzir a Complexidade do Circuito3) Facilitar a Análise de Falhas

EquivalênciaEquivalência

Os Estados S1, S2, ...., Sj de um Circuito Sequencial são ditos equivalentes se e somente se, para toda seqüência de entrada possível, a mesma seqüência de saída será

produzida independentemente de qual S1, S2, ...., Sj seja o Estado Inicial.

Os Estados S1, S2, ...., Sj de um Circuito Sequencial são ditos equivalentes se e somente se, para toda seqüência de entrada possível, a mesma seqüência de saída será

produzida independentemente de qual S1, S2, ...., Sj seja o Estado Inicial.

Equivalência de estadosEquivalência de estados

Sejam Sk e Sl os Próximos Estados de um Circuito Sequencial quando a entrada Ip é aplicada, estando o

circuito nos estados Si e Sj respectivamente.Si e Sj são equivalentes se e somente se, para toda

entrada possível Ip:1 - A saída produzida pelo estado Si é igual à saída

produzida pelo estado Sj2 - Os Próximos Estados Sk e Sl são equivalentes.

Sejam Sk e Sl os Próximos Estados de um Circuito Sequencial quando a entrada Ip é aplicada, estando o

circuito nos estados Si e Sj respectivamente.Si e Sj são equivalentes se e somente se, para toda

entrada possível Ip:1 - A saída produzida pelo estado Si é igual à saída

produzida pelo estado Sj2 - Os Próximos Estados Sk e Sl são equivalentes.

1.1.

2.2.

Eliminação est. redundantesEliminação est. redundantes

1. Por Inspeção1. Por Inspeção

Eliminação de Estados redundantesEliminação de Estados redundantes

EstadoPresente

ABCDE

X = 0 X = 1Est. Futuro / Saída

B / 0C / 0D / 1C / 0D / 0

C / 1A / 1B / 0A / 1C / 1

EstadoPresente

ABCE


B / 0C / 0B / 1B / 0

C / 1A / 1B / 0C / 1

1. Por Inspeção1. Por Inspeção


EstadoPresente

ABC


B / 0C / 0B / 1

C / 1A / 1B / 0

TABELA FINALTABELA FINAL




EstadoPresente

ABCDEFGH


B / 0D / 0G / 0H / 0G / 0G / 1D / 0H / 0

C / 0E / 0E / 0F / 0A / 0A / 0C / 0A / 0

1. Só est. F tem comportamento diferente dos outros quanto àsaída;2. Vamos assumir que, inicial-mente, todos os demais corres-pondem ao mesmo estado.3. Dividir os estados, então, em duas classes (PARTIÇÕES)

1. Só est. F tem comportamento diferente dos outros quanto àsaída;2. Vamos assumir que, inicial-mente, todos os demais corres-pondem ao mesmo estado.3. Dividir os estados, então, em duas classes (PARTIÇÕES)

2. Por Partição2. Por Partição


2. Por Partição2. Por PartiçãoEliminação de Estados redundantesEliminação de Estados redundantes

EstadoPresente

A1

B1

C1

D1

E1

F2

G1

H1


B1 / 0D1 / 0G1 / OH1 / 0G1 / 0G1 / 1D1 / 0H1 / 0

C1 / 0E1 / 0E1 / 0F2 / 0A1 / 0A1 / 0C1 / 0A1 / 0

Dois estados cujos Est. Futuros em cada coluna (x=0 e x=1) não estão nas mesmas Partições devem ser estados diferentes

Dois estados cujos Est. Futuros em cada coluna (x=0 e x=1) não estão nas mesmas Partições devem ser estados diferentes

EstadoPresente

A1

B1

C1

D3

E1

F2

G1

H1


B1 / 0D3 / 0G1 / 0H1 / 0G1 / 0G1 / 1D3 / 0H1 / 0

C1 / 0E1 / 0E1 / 0F2 / 0A1 / 0A1 / 0C1 / 0A1 / 0



EstadoPresente

A1

B4

C1

D3

E1

F2

G4

H1


B4 / 0D3 / 0G4 / 0H1 / 0G4 / 0G4 / 1D3 / 0H1 / 0

C1 / 0E1 / 0E1 / 0F2 / 0A1 / 0A1 / 0C1 / 0A1 / 0

EstadoPresente

A5

B4

C5

D3

E5

F2

G4

H1


B4 / 0D3 / 0G4 / 0H1 / 0G4 / 0G4 / 1D3 / 0H1 / 0

C5 / 0E5 / 0E5 / 0F2 / 0A5 / 0A5 / 0C5 / 0A5 / 0



EstadoPresente

abcde


b / 0c / 0e / 0b / 1e / 0

a / 0a / 0d / 0a / 0a / 0




EstadoPresente

ABCDEFGH


E / 0A / 1C / OB / 0D / 1C / 0H / 1C / 1

D / 0F / 0A / 1A / 0C / 0D / 1G / 1B / 1

2. Por Partição (outro modelo)2. Por Partição (outro modelo)

P0 = ( A B C D E F G H )P0 = ( A B C D E F G H )

X=0 0 1 0 0 1 0 1 1 X=1 0 0 1 0 0 1 1 1X=0 0 1 0 0 1 0 1 1 X=1 0 0 1 0 0 1 1 1

P1 = (AD) (BE) (CF) (GH)P1 = (AD) (BE) (CF) (GH)



EstadoPresente

ABCGH


B / 0A / 1C / 0H / 1C / 1

A / 0C / 0A / 1G / 1B / 1


2. Por Partição (outro modelo)2. Por Partição (outro modelo)


Eliminação de Estados redundantesEliminação de Estados redundantes2. Por Partição – múltiplas entradas2. Por Partição – múltiplas entradas

EstadoPresente

ABCDEFGH

00 01Est. Futuro / Saída

D / 0C / 1C / 1D / 0C / 1D / 0G / 0B / 1

D / 0D / 0D / 0B / 0F / 0D / 0G / 0D / 0

00 01F / 0E / 1E / 1A / 0E / 1A / 0A / 0E / 1

A / 0F / 0A / 0F / 0A / 0F / 0A / 0A / 0

A0000

A0000

B1010

B1010

C1010

C1010

D0000

D0000

E1010

E1010

F0000

F0000

G0000

G0000

H1010

H1010

P0 =P0 =

(ADDFA

(ADDFA

DDBAF

DDBAF

FDDAF

FDDAF

G)GGAA

G)GGAA

(BCDEF

(BCDEF

CCDEA

CCDEA

ECFEA

ECFEA

H)BDEA

H)BDEA

P1 =P1 =00 -01 -11 -10 -

00 -01 -11 -10 -D está em outra partiçãoD está em outra partição




2. Por Partição – múltiplas entradas2. Por Partição – múltiplas entradas

EstadoPresente

ABDEG


D / 0B / 1D / 0B / 1G / 0

D / 0D / 0B / 0A / 0G / 0

00 01A / 0E / 1A / 0E / 1A / 0

A / 0A / 0A / 0A / 0A / 0



Detector de sequência (mod. Mealy)(entrada X, saída Z)Detector de sequência (mod. Mealy)(entrada X, saída Z)

2. Por Partição – Exemplo completo2. Por Partição – Exemplo completo

• Para X = 0 Z = 1 SE anteriormente X = 1001• Para X = 0 Z = 1 SE anteriormente X = 1001

sequência bem sucedida para Z = 1 é X = 10010sequência bem sucedida para Z = 1 é X = 10010

• Vamos supor a sequência:• Vamos supor a sequência:

Ck = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21X = 1 1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0Ck = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21X = 1 1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0

Z = 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0Z = 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0



(a) Diagrama de Estados(a) Diagrama de Estados


• Consideraremos o primeiro estado como aquele atingido após a sucessão de dois ou mais 1 consecutivos (no ex., é o estado do sistema no terceiro pulso de Ck) primeiro bit de uma sequência que pode ser bem sucedida foi recebido (qualquer coisa anterior é irrelevante)

• Consideraremos o primeiro estado como aquele atingido após a sucessão de dois ou mais 1 consecutivos (no ex., é o estado do sistema no terceiro pulso de Ck) primeiro bit de uma sequência que pode ser bem sucedida foi recebido (qualquer coisa anterior é irrelevante)

Ck = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21X = 1 1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0Ck = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21X = 1 1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 0 1 0 0

Z = 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0Z = 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0



(b) Tabela de Estados(b) Tabela de Estados


EstadoPresente

ABCDEFG


B / 0C / 0G / 0E / 1C / 0B / 0G / 0

A / 0F / 0D / 0A / 0A / 0A / 0F / 0

EstadoPresente

ABCDEG


B / 0C / 0G / 0E / 1C / 0G / 0

A / 0A / 0D / 0A / 0A / 0A / 0



EstadoPresente

ABCDG


B / 0C / 0G / 0B / 1G / 0

A / 0A / 0D / 0A / 0A / 0


(b) Tabela de Estados(b) Tabela de Estados




Exercício: Determine a Tabela de Estados final para o mesmo detector de sequência se o diagrama de estados fosse o seguinte:

Exercício: Determine a Tabela de Estados final para o mesmo detector de sequência se o diagrama de estados fosse o seguinte:


A B C D

0 / 00 / 0

0 / 10 / 11 / 0 1 / 0 0 / 00 / 00 / 00 / 011 / 0011 / 00E

1 / 01 / 0

G

0 / 00 / 00 / 00 / 0

F1 / 01 / 0

1 / 01 / 0

1 / 01 / 0

1 / 01 / 0

1 / 01 / 0

0 / 00 / 0



EstadoPresente

ABCDE


C / 1C / 1B / 1D / 0E / 0

B / 0E / 0E / 0B / 1A / 1

3. Pela Tabela de Implicação3. Pela Tabela de Implicação

BB

CC

DD

EE

AA BB CC DD

BEBE

BEBEBCBC

BCBC

DEDE

ABAB



EstadoPresente

ABCDE


C / 1C / 1B / 1D / 0E / 0

B / 0E / 0E / 0B / 1A / 1

3. Pela Tabela de Implicação3. Pela Tabela de Implicação

BB

CC

DD

EE

AA BB CC DD

BEBE

BEBEBCBC

✔✔

DEDE

ABAB


Eliminação de Estados redundantesEliminação de Estados redundantes3. Pela Tabela de Implicação3. Pela Tabela de Implicação

BB

CC

DD

EE

AA BB CC DD

BEBE

BEBEBCBC

✔✔

DEDE

ABAB

Partições de Equivalência PK = (A) (BC) (D) (E)Partições de Equivalência PK = (A) (BC) (D) (E)

A -

B (BC)

C -

D -

E -

A -

B (BC)

C -

D -

E -


Eliminação de Estados redundantesEliminação de Estados redundantes3. Pela Tabela de Implicação

MÉTODO3. Pela Tabela de Implicação

MÉTODO

BB

CC

DD

EE

AA BB CC DD

1. Formar a tabela:• Vertical estados exceto o 1⍜• Horizontal estados exceto o último

(*) Cruzamento linha-coluna teste de equivalência dos estados

1. Formar a tabela:• Vertical estados exceto o 1⍜• Horizontal estados exceto o último

(*) Cruzamento linha-coluna teste de equivalência dos estados

2. Colocar X nas células em que as saídas não são = para qualquer entrada

2. Colocar X nas células em que as saídas não são = para qualquer entrada




MÉTODO

BB

CC

DD

EE

AA BB CC DD

BEBE

BEBEBCBC

BCBC

DEDE

ABAB

3. Completar células vazias com pares de Estados Futuros cuja equivalência está implicada pelos dois estados da intersecção


4. Se os pares implicados numa célula são os que a definem, ou se os Estados Futuros da célula são os mesmos marcar ✔ (esses estados são equivalentes)





MÉTODO

BB

CC

DD

EE

AA BB CC DD

BEBE

BEBEBCBC

ABAB



✔✔






MÉTODO

BB

CC

DD

EE

AA BB CC DD

BEBE

BEBEBCBC

ABAB

6. Montar a tabela final, listando os estados que definem a linha horizontal na Tab. Implicação (examiná-la coluna a coluna procurando células não cruzadas – Estados EQUIVALENTES).

6. Montar a tabela final, listando os estados que definem a linha horizontal na Tab. Implicação (examiná-la coluna a coluna procurando células não cruzadas – Estados EQUIVALENTES).

✔✔

5. Verificar se devem ser cruzadas outras células, além das jámarcadas

5. Verificar se devem ser cruzadas outras células, além das jámarcadas



EstadoPresente

ABCDEFGH


E / 0A / 1C / 0B / 0D / 1C / 0H / 1C /1

D / 0F / 0A / 1A / 0C / 0D / 1G / 1B / 1

3. Pela Tabela de ImplicaçãoEXERCÍCIOS – Simplificar as tab. de estados abaixo3. Pela Tabela de ImplicaçãoEXERCÍCIOS – Simplificar as tab. de estados abaixo

3.13.1 3.23.2

EstadoPresente

ABCDEFGH


D / 0C / 1C / 1D / 0C / 1D / 0G / 0B / 1

D / 0D / 0D / 0B / 0F / 0D / 0G / 0D / 0

00 01F / 0E / 1E / 1A / 0E / 1A / 0A / 0E / 1

A / 0F / 0A / 0F / 0A / 0F / 0A / 0A / 0

Documents

SIMPLIFICASIMPLIFICAÇÃO SIMPLIFICAÇÃO DE CIRCUITOS …iris.sel.eesc.usp.br/sel414/15-Simplificacao_Sequenciais.pdf · EquivalênciaEquivalência Os Estados S1, S2, ...., Sj de