2 sistemasdigitais parte 2

Prévia do material em texto

Sistemas Digitais
Resumo/adaptac¸a˜o de partes do livro
LEMOS,F.A.; Concepc¸a˜o e projeto de sistemas digitais – vol.1 Estudo da
lo´gica sequencial. Editado pelo autor.
Esta apresentac¸a˜o tem cara´ter preliminar, realizada para apoiar as aulas teo´ricas.
Esta´ sendo colocada, sem reviso˜es, a` disposic¸a˜o do aluno apenas para guiar seus estudos
quanto ao conteu´do abordado em sala de aula.
Na˜o substitui o livro em que foi baseada. O livro deve sempre estar dispon´ıvel para
completar lacunas e permitir a detecc¸a˜o de falhas.
(ICET) Sistemas Digitais 2017 1 / 176
O Me´todo Cla´ssico de Huffman
Plano
1 O Me´todo Cla´ssico de Huffman
2 O processo de reduc¸a˜o de tabelas de fluxo
3 Designac¸a˜o de Estados Internos
(ICET) Sistemas Digitais 2017 2 / 176
O Me´todo Cla´ssico de Huffman
O Me´todo Cla´ssico de Huffman
A noc¸a˜o fundamental vinculada a este me´todo, e´ a de estado interno.
A ana´lise do problema e´ feita pela aplicac¸a˜o sucessiva de entradas que
fara˜o evoluir o sistema numa sequeˆncia de estados.
Se associarmos a cada um destes estados um enderec¸o (co´digo), o
conhecimento deste enderec¸o e´ das varia´veis de entrada num determinado
instante permitira´ determinar a sa´ıda neste instante, e prever o novo
estado do sistema nos instantes seguintes.
(ICET) Sistemas Digitais 2017 3 / 176
O Me´todo Cla´ssico de Huffman
O Me´todo Cla´ssico de Huffman
O processo de s´ıntese vai, portanto, se constituir em definir de maneira
o´tima a codificac¸a˜o dos estados:
a) evitando modos de funcionamento erra´ticos ou na˜o previstos do sistema,
b) ao mesmo tempo simplificar (minimizar) ao ma´ximo as equac¸o˜es
correspondentes.
(ICET) Sistemas Digitais 2017 4 / 176
O Me´todo Cla´ssico de Huffman
O Me´todo Cla´ssico de Huffman
Vamos procurar escrever equac¸o˜es dos seguintes tipos:
Modelo de Moore:
Z (t) = F [x(t)] −→ Equac¸o˜es de sa´ıda
X (t + ∆t) = G [X (t),E (t)] −→ Equac¸o˜es de estado
Modelo de Mealy
Z (t) = F [X (t),E (t)] −→ Equac¸o˜es de sa´ıda
X (t + ∆t) = G [X (t),E (t)] −→ Equac¸o˜es de estado
(ICET) Sistemas Digitais 2017 5 / 176
O Me´todo Cla´ssico de Huffman
O Me´todo Cla´ssico de Huffman
O processo de s´ıntese que sera´ apresentado esta´ esquematizado no
diagrama:
(ICET) Sistemas Digitais 2017 6 / 176
O Me´todo Cla´ssico de Huffman
O Me´todo Cla´ssico de Huffman
Etapas 1, 2 e 3:
Consistem na ana´lise do problema proposto, e posterior formulac¸a˜o do
mesmo utilizando um mecanismo de descric¸a˜o adequado. Sera˜o
apresentados dois mecanismos de descric¸a˜o denominados Tabela primitiva
de Fluxo, e Diagrama de Estados.
Ambos devera˜o indicar a forma pela qual o sistema evolui com o tempo
(seu conjunto de sa´ıdas e de estados internos), em func¸a˜o do conjunto de
entradas aplicadas ao mesmo.
Fornecera˜o tambe´m, com ou sem redundaˆncias, o nu´mero de estados
internos necessa´rios a` s´ıntese.
(ICET) Sistemas Digitais 2017 7 / 176
O Me´todo Cla´ssico de Huffman
O Me´todo Cla´ssico de Huffman
Etapa 4:
Consiste na simplificac¸a˜o da descric¸a˜o inicial do problema, obtida a partir
das etapas anteriores. (etapas 1, 2 e 3) .
Esta simplificac¸a˜o esta´ baseada na detecc¸a˜o e eliminac¸a˜o das redundaˆncias
cometidas, procurando reduzir ao m´ınimo o nu´mero de estados internos
necessa´rios a` descric¸a˜o do sistema.
(ICET) Sistemas Digitais 2017 8 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman
Etapa 5:
Nesta etapa e´ feita a “designac¸a˜o de estados” internos do sistema.
Ela consiste em associar aos estados internos existentes, varia´veis
booleanas bina´rias, de modo que a cada estado interno corresponda uma e
uma so´ combinac¸a˜o destas varia´veis booleanas, ou seja: Os estados
internos do sistema devem ser codificados.
O problema da designac¸a˜o de estados e´ mais complexo, pois o crite´rio de
escolha deve levar em considerac¸a˜o o funcionamento correto do dispositivo
f´ısico que ira´ materializar a descric¸a˜o, e a minimizac¸a˜o do nu´mero de
varia´veis internas utilizadas. Este assunto sera´ retomado com detalhes
posteriormente.
(ICET) Sistemas Digitais 2017 9 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman
Etapas 6 e 7:
Uma vez conclu´ıda a designac¸a˜o dos estados internos, pode-se obter as
equac¸o˜es do sistema sequencial com aux´ılio dos mapas de
Veitch-Karnaugh.
Estas equac¸o˜es, por sua vez, permitira˜o a materializac¸a˜o f´ısica do circuito
sequencial desejado.
(ICET) Sistemas Digitais 2017 10 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Tabela Primitiva de Fluxo
E´ um mecanismo de descric¸a˜o de tarefas sequenciais, e como tal, deve
permitir que se represente de forma precisa o comportamento do sistema
em estudo.
Como os sistemas estudados neste curso processam informac¸o˜es digitais
(s´ıncronas ou ass´ıncronas) e evoluem por estados internos, esta tabela
deve fixar estes estados e seu relacionamento.
Deve tambe´m permitir o conhecimento das sa´ıdas do sistema para um
determinado conjunto de entradas que lhe foi aplicado.
(ICET) Sistemas Digitais 2017 11 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Tabela Primitiva de Fluxo
A tabela tem a forma mostrada na figura, onde as colunas representam
todas as combinac¸o˜es poss´ıveis das entradas permitidas no sistema, e as
linhas representam os estados internos tidos como necessa´rios.
A construc¸a˜o de tabela primitiva de fluxo se faz a medida em que a tarefa
vai sendo descrita, e tem como caracter´ıstica ba´sica possuir apenas um
estado esta´vel por estado interno (um estado esta´vel por linha da tabela).
(ICET) Sistemas Digitais 2017 12 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Tabela Primitiva de Fluxo
Um determinado conjunto de entradas permitidas (identificac¸a˜o das
colunas), aplicadas quando o sistema se encontra em um determinado
estado interno (identificac¸a˜o da linha), define uma u´nica ce´lula da tabela
primitiva de fluxo, que sera´ denominado estado total do sistema.
Nesta ce´lula devera´ constar o pro´ximo estado interno (atualizac¸a˜o de
estado) e as sa´ıdas que o sistema apresenta para o conjunto de entradas
que lhe foi aplicado.
A tarefa estara´ com sua descric¸a˜o completa, quando todas as ce´lulas
(estados totais) da tabela primitiva tiverem sido preenchidas.
(ICET) Sistemas Digitais 2017 13 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Considerar um dispositivo conforme esquematizado na figura
Nesta figura, Y e Z sa˜o motores alimentados por releˆs do mesmo nome.
Quando Y e´ alimentado, o carro se desloca da direita para a esquerda e
quando Z e´ alimentado, o carro se desloca da esquerda para a direita. A e
B sa˜o contatos de fim de curso indicando que o carro se encontra em uma
destas duas posic¸o˜es.
(ICET) Sistemas Digitais 2017 14 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Deseja-se descrever um ciclo de operac¸a˜o do carro tal que, se for acionado
o bota˜o M quando o carro estiver em repouso em A, ele deve deixar A, ir
ate´ B e voltar novamente a A, onde para e espera que o bota˜o de pressa˜o
M seja novamente acionado.
Supor tambe´m que sempre que o carro deixar A iniciando o movimento,
na˜o sera´ permitido apertar novamente o bota˜o M ate´ que o ciclo seja
completado.
(ICET) Sistemas Digitais 2017 15 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Para construir a tabela primitiva de fluxo do problema, deve-se, antes de
mais nada, definir suas entradas e sa´ıdas.
1 Definic¸a˜o de entradas: Sa˜o o bota˜o M, os contatos de fim de curso
A (que para o carro) e B (que inverte o sentido de deslocamento do
carro).
2 Definic¸a˜o dassa´ıdas:
Sa˜o os releˆs Y e Z que acionam os motores a eles associados colocando ou
na˜o o carro em movimento.
(ICET) Sistemas Digitais 2017 16 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O fato do sistema possuir treˆs entradas bina´rias que sa˜o M, A e B permite
combinar estas entradas de 23 = 8 maneiras distintas, fazendo com que a
tabela de fluxo possua um ma´ximo de 8 colunas.
M A B 000 001 011 010 110 111 101 100
Estado 1
(ICET) Sistemas Digitais 2017 17 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Admita que, por imposic¸a˜o de projeto, nunca ira´ ocorrer A = 1 e B = 1 ao
mesmo tempo.
Isto elimina a necessidade de analisar 2 colunas (011 e 111) da tabela.
M A B 000 001 011 010 110 111 101 100
Estado 1
(ICET) Sistemas Digitais 2017 18 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Admita que, por imposic¸a˜o de projeto, nunca ira´ ocorrer A = 1 e B = 1 ao
mesmo tempo.
Isto elimina a necessidade de analisar 2 colunas (011 e 111) da tabela.
M A B 000 001 011 010 110 111 101 100
Estado 1
(ICET) Sistemas Digitais 2017 18 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Admita que, por imposic¸a˜o de projeto, nunca ira´ ocorrer A = 1 e B = 1 ao
mesmo tempo.
Isto elimina a necessidade de analisar 2 colunas (011 e 111) da tabela.
M A B 000 001 011 010 110 111 101 100
Estado 1
(ICET) Sistemas Digitais 2017 18 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Como M e´ um bota˜o de pressa˜o, e suporemos que ele na˜o pode ser
apertado durante o percurso do carro.
Assim, na˜o e´ poss´ıvel ter M = 1 e B = 1 , o que elimina mais uma coluna
(101) da tabela.
M A B 000 001 011 010 110 111 101 100
Estado 1
(ICET) Sistemas Digitais 2017 19 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Como M e´ um bota˜o de pressa˜o, e suporemos que ele na˜o pode ser
apertado durante o percurso do carro.
Assim, na˜o e´ poss´ıvel ter M = 1 e B = 1 , o que elimina mais uma coluna
(101) da tabela.
M A B 000 001 011 010 110 111 101 100
Estado 1
(ICET) Sistemas Digitais 2017 19 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Como M e´ um bota˜o de pressa˜o, e suporemos que ele na˜o pode ser
apertado durante o percurso do carro.
Assim, na˜o e´ poss´ıvel ter M = 1 e B = 1 , o que elimina mais uma coluna
(101) da tabela.
M A B 000 001 011 010 110 111 101 100
Estado 1
(ICET) Sistemas Digitais 2017 19 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Escolher um estado inicial de partida (estado 1) que sera´ esta´vel, e
corresponde ao carro estacionado sobre o contato de fim de curso A.
(ICET) Sistemas Digitais 2017 20 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tem-se, portanto:
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
(ICET) Sistemas Digitais 2017 21 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tem-se, portanto:
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
(ICET) Sistemas Digitais 2017 21 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tem-se, portanto:
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
(ICET) Sistemas Digitais 2017 21 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tem-se, portanto:
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
(ICET) Sistemas Digitais 2017 21 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tem-se, portanto:
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
(ICET) Sistemas Digitais 2017 21 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
M A B 000 001 011
010
110 111 101 100
Estado 1
1,00
em resumo, o sistema fica no estado 1.
(ICET) Sistemas Digitais 2017 22 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
M A B 000 001 011 0
10
110 111 101 100
Estado 1
1,00
em resumo, o sistema fica no estado 1.
(ICET) Sistemas Digitais 2017 22 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
M A B 000 001 011 01
0
110 111 101 100
Estado 1
1,00
em resumo, o sistema fica no estado 1.
(ICET) Sistemas Digitais 2017 22 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
M A B 000 001 011 010 110 111 101 100
Estado 1
1,00
em resumo, o sistema fica no estado 1.
(ICET) Sistemas Digitais 2017 22 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
M A B 000 001 011 010 110 111 101 100
Estado 1 1,00
em resumo, o sistema fica no estado 1.
(ICET) Sistemas Digitais 2017 22 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
M = 0 (bota˜o na˜o foi apertado )
A = 1 (contato A acionado pelo carro) e
B = 0 (contato B na˜o acionado).
As sa´ıdas, neste caso, sera˜o Y = 0 e Z = 0, significando que o carro se
encontra parado.
M A B 000 001 011 010 110 111 101 100
Estado 1 1,00
em resumo, o sistema fica no estado 1.
(ICET) Sistemas Digitais 2017 22 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Estando o sistema no estado 1, quando M for pressionado, passa-se a um
outro estado, de nome “2”.
(ICET) Sistemas Digitais 2017 23 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Quando
M for pressionado, passa-se a um outro estado, de nome “2”.
M A B 000 001 011 010
1
10 111 101 100
Estado 1 1,00
2,00
(ICET) Sistemas Digitais 2017 24 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Quando M for pressionado,
passa-se a um outro estado, denome “2”.
M A B 000 001 011 010 110 111 101 100
Estado 1 1,00
2,00
(ICET) Sistemas Digitais 2017 24 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Quando M for pressionado, passa-se a um outro estado, de nome “2”.
M A B 000 001 011 010 110 111 101 100
Estado 1 1,00 2,00
(ICET) Sistemas Digitais 2017 24 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Quando M for pressionado, passa-se a um outro estado, de nome “2”.
O estado 2 e´ registrado em uma linha da tabela de fluxo.
O sistema permanecera´ neste estado ate´ que as entradas se alterem.
As sa´ıdas neste estado mante´m o motor Z ligado.
M A B 000 001 011 010 110 111 101 100
Estado 1 1,00 2,00
Estado 2 2,01
(ICET) Sistemas Digitais 2017 25 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Quando M for pressionado, passa-se a um outro estado, de nome “2”.
O estado 2 e´ registrado em uma linha da tabela de fluxo.
O sistema permanecera´ neste estado ate´ que as entradas se alterem.
As sa´ıdas neste estado mante´m o motor Z ligado.
M A B 000 001 011 010 110 111 101 100
Estado 1 1,00 2,00
Estado 2
2,01
(ICET) Sistemas Digitais 2017 25 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Quando M for pressionado, passa-se a um outro estado, de nome “2”.
O estado 2 e´ registrado em uma linha da tabela de fluxo.
O sistema permanecera´ neste estado ate´ que as entradas se alterem.
As sa´ıdas neste estado mante´m o motor Z ligado.
M A B 000 001 011 010 110 111 101 100
Estado 1 1,00 2,00
Estado 2 2
,01
(ICET) Sistemas Digitais 2017 25 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Quando M for pressionado, passa-se a um outro estado, de nome “2”.
O estado 2 e´ registrado em uma linha da tabela de fluxo.
O sistema permanecera´ neste estado ate´ que as entradas se alterem.
As sa´ıdas neste estado mante´m o motor Z ligado.
M A B 000 001 011 010 110 111 101 100
Estado 1 1,00 2,00
Estado 2 2,01
(ICET) Sistemas Digitais 2017 25 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Com o sistema no estado 1, na˜o sera´ considerada a entrada 000.
Significaria que o carro saiu da posic¸a˜o A sem que o motor fosse ligado.
Marcaremos a situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1
X
1,00 2,00
Estado 2 2,01
(ICET) Sistemas Digitais 2017 26 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Com o sistema no estado 1, na˜o sera´ considerada a entrada 000.
Significaria que o carro saiu da posic¸a˜o A sem que o motor fosse ligado.
Marcaremos a situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1
X
1,00 2,00
Estado 2 2,01
(ICET) Sistemas Digitais 2017 26 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Com o sistema no estado 1, na˜o sera´ considerada a entrada 000.
Significaria que o carro saiu da posic¸a˜o A sem que o motor fosse ligado.
Marcaremos a situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X 1,00 2,00
Estado 2 2,01
(ICET) Sistemas Digitais 2017 26 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tambe´m na˜o sera´ considerada a entrada 001.
Significaria que o carro atingiu a posic¸a˜o B, sem que o motor fosse ligado.
Marcaremos a situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X
X
1,00 2,00
Estado 2 2,01
(ICET) Sistemas Digitais 2017 27 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tambe´m na˜o sera´ considerada a entrada 001.
Significaria que o carro atingiu a posic¸a˜o B, sem que o motor fosse ligado.
Marcaremos a situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X
X
1,00 2,00
Estado 2 2,01
(ICET) Sistemas Digitais 2017 27 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tambe´m na˜o sera´ considerada a entrada 001.
Significaria que o carro atingiu a posic¸a˜o B, sem que o motor fosse ligado.
Marcaremos a situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00
Estado 2 2,01
(ICET) Sistemas Digitais 2017 27 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tambe´m na˜o sera´ considerada a entrada 100.
Significaria que o carro saiu da posic¸a˜o, sem que o motor fosse ligado.
Marcaremos a situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00
X
Estado 2 2,01
(ICET) Sistemas Digitais 2017 28 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tambe´m na˜o sera´ considerada a entrada 100.
Significaria que o carro saiu da posic¸a˜o, sem que o motor fosse ligado.
Marcaremos a situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00
X
Estado 2 2,01
(ICET) Sistemas Digitais 2017 28 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Tambe´m na˜o sera´ considerada a entrada 100.
Significaria que o carro saiu da posic¸a˜o, sem que o motor fosse ligado.
Marcaremos a situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 2,01
(ICET) Sistemas Digitais 2017 28 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
No estado 2, o motor Z esta´ ligado.
Com o motor que desloca o carro para a direita ligado, podem ocorrer
duas hipo´teses:
1 O bota˜o M e´ solto antes que o carro deixe o contato A;
2 O carro deixa A, e a seguir o bota˜o M e´ solto pelo operador;
3 O carro deixa A, e o operador mante´m M pressionado.
(ICET) Sistemas Digitais 2017 29 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O bota˜o M e´ solto antes que o carro deixe o contato A
A primeira hipo´tese deve ser registrada na quarta coluna, como destacado
na tabela de fluxo. (entrada MAB = 010 )
Neste caso, o sistema passa a um estado 3.
O motor Z deve permanecer ligado (sa´ıda YZ = 01).
O estado 3 e´ registrado em uma coluna da tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2
3,01
2,01
Estado 3
(ICET) Sistemas Digitais 2017 30 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O bota˜o M e´ solto antes que o carro deixe o contato A
A primeira hipo´tese deve ser registrada na quarta coluna, como destacado
na tabela de fluxo. (entrada MAB = 010 )
Neste caso, o sistema passa a um estado 3.
O motor Z deve permanecer ligado (sa´ıda YZ = 01).
O estado 3 e´ registrado em uma coluna da tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 3
,01
2,01
Estado 3
(ICET) Sistemas Digitais 2017 30 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O bota˜o M e´ solto antes que o carro deixe o contato A
A primeira hipo´tese deve ser registrada na quarta coluna, como destacado
na tabela de fluxo. (entrada MAB = 010 )
Neste caso, o sistema passa a um estado 3.
O motor Z deve permanecer ligado (sa´ıda YZ = 01).
O estado 3 e´ registrado em uma coluna da tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 3,01 2,01
Estado 3
(ICET) Sistemas Digitais 2017 30 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O bota˜o M e´ solto antes que o carro deixe o contato A
A primeira hipo´tesedeve ser registrada na quarta coluna, como destacado
na tabela de fluxo. (entrada MAB = 010 )
Neste caso, o sistema passa a um estado 3.
O motor Z deve permanecer ligado (sa´ıda YZ = 01).
O estado 3 e´ registrado em uma coluna da tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 3,01 2,01
Estado 3
(ICET) Sistemas Digitais 2017 30 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 3,01 2,01
Estado 3
Leia a ce´lula destacada assim: estando no estado 2, e as entradas
assumindo o valor 010, o sistema deve ir ao estado 3.
(ICET) Sistemas Digitais 2017 31 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O carro deixa A, e a seguir o bota˜o M e´ solto pelo operador
Esta hipo´tese deve ser registrada na primeira coluna, pois MAB = 000 (o
carro deixou o ponto A, o bota˜o M na˜o esta´ pressionado, e o carro na˜o
atingiu o ponto B.
Sera´ criado um novo estado, de nome 4.
Estamos no estado 2, e neste estado, o motor Z esta´ ligado.
O estado 4 e´ registrado em uma linha da tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2
4,01
3,01 2,01
Estado 3
Estado 4
(ICET) Sistemas Digitais 2017 32 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O carro deixa A, e a seguir o bota˜o M e´ solto pelo operador
Esta hipo´tese deve ser registrada na primeira coluna, pois MAB = 000 (o
carro deixou o ponto A, o bota˜o M na˜o esta´ pressionado, e o carro na˜o
atingiu o ponto B.
Sera´ criado um novo estado, de nome 4.
Estamos no estado 2, e neste estado, o motor Z esta´ ligado.
O estado 4 e´ registrado em uma linha da tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4
,01
3,01 2,01
Estado 3
Estado 4
(ICET) Sistemas Digitais 2017 32 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O carro deixa A, e a seguir o bota˜o M e´ solto pelo operador
Esta hipo´tese deve ser registrada na primeira coluna, pois MAB = 000 (o
carro deixou o ponto A, o bota˜o M na˜o esta´ pressionado, e o carro na˜o
atingiu o ponto B.
Sera´ criado um novo estado, de nome 4.
Estamos no estado 2, e neste estado, o motor Z esta´ ligado.
O estado 4 e´ registrado em uma linha da tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 3,01 2,01
Estado 3
Estado 4
(ICET) Sistemas Digitais 2017 32 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O carro deixa A, e a seguir o bota˜o M e´ solto pelo operador
Esta hipo´tese deve ser registrada na primeira coluna, pois MAB = 000 (o
carro deixou o ponto A, o bota˜o M na˜o esta´ pressionado, e o carro na˜o
atingiu o ponto B.
Sera´ criado um novo estado, de nome 4.
Estamos no estado 2, e neste estado, o motor Z esta´ ligado.
O estado 4 e´ registrado em uma linha da tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 3,01 2,01
Estado 3
Estado 4
(ICET) Sistemas Digitais 2017 32 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O carro deixa A, e o operador mante´m M pressionado
Esta hipo´tese sera´ registrada na oitava coluna (entrada MAB = 100)
, e o
sistema ira´ para o estado 7.
O estado 7 e´ registrado em uma linha da tabela de fluxo
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 3,01 2,01
7,01
Estado 3
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 33 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O carro deixa A, e o operador mante´m M pressionado
Esta hipo´tese sera´ registrada na oitava coluna (entrada MAB = 100), e o
sistema ira´ para o estado 7.
O estado 7 e´ registrado em uma linha da tabela de fluxo
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 3,01 2,01 7,01
Estado 3
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 33 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
O carro deixa A, e o operador mante´m M pressionado
Esta hipo´tese sera´ registrada na oitava coluna (entrada MAB = 100), e o
sistema ira´ para o estado 7.
O estado 7 e´ registrado em uma linha da tabela de fluxo
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 3,01 2,01 7,01
Estado 3
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 33 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
A segunda coluna do estado 2 corresponde a` entrada MAB = 001.
Neste
caso, o carro chegaria imediatamente ao ponto B, o que sera´ considerado
imposs´ıvel de ocorrer.
Marcaremos essa situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01
X
3,01 2,01
7,01
Estado 3
Estado 4
Estado 7
Terminamos de analisar as possibilidades de comportamento do sistema no
estado 2. Vamos ao estado 3.
(ICET) Sistemas Digitais 2017 34 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
A segunda coluna do estado 2 corresponde a` entrada MAB = 001. Neste
caso, o carro chegaria imediatamente ao ponto B, o que sera´ considerado
imposs´ıvel de ocorrer.
Marcaremos essa situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01
X
3,01 2,01 7,01
Estado 3
Estado 4
Estado 7
Terminamos de analisar as possibilidades de comportamento do sistema no
estado 2. Vamos ao estado 3.
(ICET) Sistemas Digitais 2017 34 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
A segunda coluna do estado 2 corresponde a` entrada MAB = 001. Neste
caso, o carro chegaria imediatamente ao ponto B, o que sera´ considerado
imposs´ıvel de ocorrer.
Marcaremos essa situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3
Estado 4
Estado 7
Terminamos de analisar as possibilidades de comportamento do sistema no
estado 2. Vamos ao estado 3.
(ICET) Sistemas Digitais 2017 34 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
A segunda coluna do estado 2 corresponde a` entrada MAB = 001. Neste
caso, o carro chegaria imediatamente ao ponto B, o que sera´ considerado
imposs´ıvel de ocorrer.
Marcaremos essa situac¸a˜o como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3
Estado 4
Estado 7
Terminamos de analisar as possibilidades de comportamento do sistema no
estado 2. Vamos ao estado 3.
(ICET) Sistemas Digitais 2017 34 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 3
Devemos recordar que chegamos ao estado 3 vindo do estado 2, quando a
entrada valia MAB = 010, que corresponde ao carro parado no ponto A, e
o bota˜o ja´ foi desativado.
O sistema deve esperar que o carro ande. O que significa ficar neste
estado, ate´ que isso ocorra, como registrado na quarta coluna do estado 3.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3
3,01
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 35 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 3
Devemos recordar que chegamos ao estado 3 vindo do estado 2, quando a
entrada valia MAB = 010, que corresponde ao carro parado no ponto A, e
o bota˜oja´ foi desativado.
O sistema deve esperar que o carro ande. O que significa ficar neste
estado, ate´ que isso ocorra, como registrado na quarta coluna do estado 3.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 3,01
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 35 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 3
Quando o carro andar, a entrada MAB valera´ 000 (primeira coluna), que
corresponde ao carro em movimento, bota˜o M desativado.
Esta hipo´tese e´ ideˆntica a`quela analisada no estado 2, e aqui o sistema
tera´ o mesmo comportamento: ir ao estado 4.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3
4,01
3,01
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 36 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 3
Quando o carro andar, a entrada MAB valera´ 000 (primeira coluna), que
corresponde ao carro em movimento, bota˜o M desativado.
Esta hipo´tese e´ ideˆntica a`quela analisada no estado 2, e aqui o sistema
tera´ o mesmo comportamento:
ir ao estado 4.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3
4,01
3,01
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 36 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 3
Quando o carro andar, a entrada MAB valera´ 000 (primeira coluna), que
corresponde ao carro em movimento, bota˜o M desativado.
Esta hipo´tese e´ ideˆntica a`quela analisada no estado 2, e aqui o sistema
tera´ o mesmo comportamento: ir ao estado 4.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 3,01
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 36 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 3
As demais possibilidades sera˜o desconsideradas:
Entrada MAB = 001 descreveria a possibilidade do carro atingir
imediatamente o ponto B.
Marcaremos como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01
X
3,01
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 37 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 3
As demais possibilidades sera˜o desconsideradas:
Entrada MAB = 001 descreveria a possibilidade do carro atingir
imediatamente o ponto B.
Marcaremos como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 37 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
MAB = 110 significa que o carro voltou ao ponto A, e ale´m disso, o
operador pressionou o bota˜o M apo´s o in´ıcio do ciclo.
Marcaremos como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01
X
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 38 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
MAB = 110 significa que o carro voltou ao ponto A, e ale´m disso, o
operador pressionou o bota˜o M apo´s o in´ıcio do ciclo.
Marcaremos como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 38 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
MAB = 100 implica em acionar o bota˜o M apo´s o in´ıcio do ciclo.
Marcaremos como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01
X X
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 39 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
MAB = 100 implica em acionar o bota˜o M apo´s o in´ıcio do ciclo.
Marcaremos como irrelevante.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4
Estado 7
(ICET) Sistemas Digitais 2017 39 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 4
A condic¸a˜o para se chegar a este estado e´ MAB = 000, em resumo, o
carro esta´ a meio caminho, indo ao ponto B, e deve permanecer neste
estado ate´ que isso ocorra.
O que deve ser registrado na primeira coluna do estado 4.
O motor Z deve permanecer ligado.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4
4,01
Estado 7
(ICET) Sistemas Digitais 2017 40 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 4
A condic¸a˜o para se chegar a este estado e´ MAB = 000, em resumo, o
carro esta´ a meio caminho, indo ao ponto B, e deve permanecer neste
estado ate´ que isso ocorra.
O que deve ser registrado na primeira coluna do estado 4.
O motor Z deve permanecer ligado.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4
,01
Estado 7
(ICET) Sistemas Digitais 2017 40 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 4
A condic¸a˜o para se chegar a este estado e´ MAB = 000, em resumo, o
carro esta´ a meio caminho, indo ao ponto B, e deve permanecer neste
estado ate´ que isso ocorra.
O que deve ser registrado na primeira coluna do estado 4.
O motor Z deve permanecer ligado.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01
Estado 7
(ICET) Sistemas Digitais 2017 40 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 4
A u´nica outra possibilidade e´ o carro atingir o ponto B (MAB = 001), que
deve portanto ser registrada na segunda coluna.
Criaremos um estado de nome 5 para esta situac¸a˜o.
Registraremos o estado 5 na tabela.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01
5,01
Estado 5
Estado 7
(ICET) Sistemas Digitais 2017 41 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 4
A u´nica outra possibilidade e´ o carro atingir o ponto B (MAB = 001), que
deve portanto ser registrada na segunda coluna.
Criaremos um estado de nome 5 para esta situac¸a˜o.
Registraremos o estado 5 na tabela.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01
Estado 5
Estado 7
(ICET) Sistemas Digitais 2017 41 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 4
A u´nica outra possibilidade e´ o carro atingir o ponto B (MAB = 001), que
deve portanto ser registrada na segunda coluna.
Criaremos um estado de nome 5 para esta situac¸a˜o.
Registraremos o estado 5 na tabela.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01
Estado 5
Estado 7
(ICET) Sistemas Digitais 2017 41 / 176
O Me´todo Cla´ssico de Huffman
Me´todoCla´ssico de Huffman – Exemplo 1
Ana´lise do estado 4
As outras possibilidades na˜o podem ocorrer.
Sa˜o marcadas como irrelevantes.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01
X X X
Estado 5
Estado 7
(ICET) Sistemas Digitais 2017 42 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 4
As outras possibilidades na˜o podem ocorrer.
Sa˜o marcadas como irrelevantes.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5
Estado 7
(ICET) Sistemas Digitais 2017 42 / 176
O Me´todo Cla´ssico de Huffman
Ana´lise do estado 5
Como visto, neste estado o carro atingiu o ponto B (MAB = 001).
O sistema deve permanecer neste estado enquanto (MAB = 001), o que
deve ser registrado na segunda coluna.
A sa´ıda deve assumir o valor YZ = 10, acionando o motor Y, para que o
carro volte.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5
5,10
Estado 7
(ICET) Sistemas Digitais 2017 43 / 176
O Me´todo Cla´ssico de Huffman
Ana´lise do estado 5
Como visto, neste estado o carro atingiu o ponto B (MAB = 001).
O sistema deve permanecer neste estado enquanto (MAB = 001), o que
deve ser registrado na segunda coluna.
A sa´ıda deve assumir o valor YZ = 10, acionando o motor Y, para que o
carro volte.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 5
,10
Estado 7
(ICET) Sistemas Digitais 2017 43 / 176
O Me´todo Cla´ssico de Huffman
Ana´lise do estado 5
Como visto, neste estado o carro atingiu o ponto B (MAB = 001).
O sistema deve permanecer neste estado enquanto (MAB = 001), o que
deve ser registrado na segunda coluna.
A sa´ıda deve assumir o valor YZ = 10, acionando o motor Y, para que o
carro volte.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 5,10
Estado 7
(ICET) Sistemas Digitais 2017 43 / 176
O Me´todo Cla´ssico de Huffman
Quando o carro de deslocar, iniciando a volta ao ponto A, o sistema ira´ a
outro estado
, que sera´ criado com o nome 6.
O estado 6 e´ registrado na tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5
6,10
5,10
Estado 6
Estado 7
(ICET) Sistemas Digitais 2017 44 / 176
O Me´todo Cla´ssico de Huffman
Quando o carro de deslocar, iniciando a volta ao ponto A, o sistema ira´ a
outro estado, que sera´ criado com o nome 6.
O estado 6 e´ registrado na tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10
Estado 6
Estado 7
(ICET) Sistemas Digitais 2017 44 / 176
O Me´todo Cla´ssico de Huffman
Quando o carro de deslocar, iniciando a volta ao ponto A, o sistema ira´ a
outro estado, que sera´ criado com o nome 6.
O estado 6 e´ registrado na tabela de fluxo.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10
Estado 6
Estado 7
(ICET) Sistemas Digitais 2017 44 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 5
As demais possibilidades sera˜o desprezadas:
MAB = 010 implica em atingir o ponto A imediatamente;
MAB = 110 idem, ale´m do acionamento do bota˜o M durante o ciclo.
MAB = 100 descreve o acionamento do bota˜o M durante o ciclo, situac¸a˜o
que na˜o sera´ considerada.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10
X X X
Estado 6
Estado 7
(ICET) Sistemas Digitais 2017 45 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 5
As demais possibilidades sera˜o desprezadas:
MAB = 010 implica em atingir o ponto A imediatamente;
MAB = 110 idem, ale´m do acionamento do bota˜o M durante o ciclo.
MAB = 100 descreve o acionamento do bota˜o M durante o ciclo, situac¸a˜o
que na˜o sera´ considerada.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X
X X
Estado 6
Estado 7
(ICET) Sistemas Digitais 2017 45 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 5
As demais possibilidades sera˜o desprezadas:
MAB = 010 implica em atingir o ponto A imediatamente;
MAB = 110 idem, ale´m do acionamento do bota˜o M durante o ciclo.
MAB = 100 descreve o acionamento do bota˜o M durante o ciclo, situac¸a˜o
que na˜o sera´ considerada.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X
X
Estado 6
Estado 7
(ICET) Sistemas Digitais 2017 45 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 5
As demais possibilidades sera˜o desprezadas:
MAB = 010 implica em atingir o ponto A imediatamente;
MAB = 110 idem, ale´m do acionamento do bota˜o M durante o ciclo.
MAB = 100 descreve o acionamento do bota˜o M durante o ciclo, situac¸a˜o
que na˜o sera´ considerada.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6
Estado 7
(ICET) Sistemas Digitais 2017 45 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
Em 6, o carro esta´ voltando.
O sistema deve permanecer em 6 ate´ atingir
o ponto A. Com o motor Y ligado.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6
6,10
Estado 7
(ICET) Sistemas Digitais 2017 46 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
Em 6, o carro esta´ voltando. O sistema deve permanecer em 6 ate´ atingir
o ponto A.
Com o motor Y ligado.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6
,10
Estado 7
(ICET) Sistemas Digitais 2017 46 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
Em 6, o carro esta´ voltando. O sistema deve permanecer em 6 ate´ atingir
o ponto A. Com o motor Y ligado.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10
Estado 7
(ICET) Sistemas Digitais 2017 46 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
Ao atingir o ponto A (MAB = 010), o ciclo se encerra, e o sistema deve ir
ao primeiro estado.
Isso deve ser descritona quarta coluna.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10
1,10
Estado 7
(ICET) Sistemas Digitais 2017 47 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
Ao atingir o ponto A (MAB = 010), o ciclo se encerra, e o sistema deve ir
ao primeiro estado. Isso deve ser descrito na quarta coluna.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10
1,10
Estado 7
(ICET) Sistemas Digitais 2017 47 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
Ao atingir o ponto A (MAB = 010), o ciclo se encerra, e o sistema deve ir
ao primeiro estado. Isso deve ser descrito na quarta coluna.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10 1,10
Estado 7
(ICET) Sistemas Digitais 2017 47 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
As demais possibilidades na˜o sera˜o consideradas:
A segunda coluna (MAB = 001) implica na volta do carro ao ponto B.
As colunas 5 e 8 descrevem o acionamento na˜o previsto do bota˜o M.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10
X
1,10
X X
Estado 7
(ICET) Sistemas Digitais 2017 48 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
As demais possibilidades na˜o sera˜o consideradas:
A segunda coluna (MAB = 001) implica na volta do carro ao ponto B.
As colunas 5 e 8 descrevem o acionamento na˜o previsto do bota˜o M.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10
X
1,10
X X
Estado 7
(ICET) Sistemas Digitais 2017 48 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
As demais possibilidades na˜o sera˜o consideradas:
A segunda coluna (MAB = 001) implica na volta do carro ao ponto B.
As colunas 5 e 8 descrevem o acionamento na˜o previsto do bota˜o M.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10 X 1,10
X X
Estado 7
(ICET) Sistemas Digitais 2017 48 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
As demais possibilidades na˜o sera˜o consideradas:
A segunda coluna (MAB = 001) implica na volta do carro ao ponto B.
As colunas 5 e 8 descrevem o acionamento na˜o previsto do bota˜o M.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10 X 1,10
X X
Estado 7
(ICET) Sistemas Digitais 2017 48 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 6
As demais possibilidades na˜o sera˜o consideradas:
A segunda coluna (MAB = 001) implica na volta do carro ao ponto B.
As colunas 5 e 8 descrevem o acionamento na˜o previsto do bota˜o M.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10 X 1,10 X X
Estado 7
(ICET) Sistemas Digitais 2017 48 / 176
O Me´todo Cla´ssico de Huffman
Ana´lise do estado 7
O sistema atinge este estado vindo do estado 2, na situac¸a˜o do carro sair
do ponto A antes do operador desativar o bota˜o M.
Deve-se permanecer em 7 ate´ o bota˜o ser desativado. Com o motor Z
ligado.
Isso leva a` condic¸a˜o descrita pelo estado 4: carro a meio caminho do
ponto A. Que deve ser registrado na primeira coluna do estado 7.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10 X 1,10 X X
Estado 7 4
,01 7,01
(ICET) Sistemas Digitais 2017 49 / 176
O Me´todo Cla´ssico de Huffman
Ana´lise do estado 7
O sistema atinge este estado vindo do estado 2, na situac¸a˜o do carro sair
do ponto A antes do operador desativar o bota˜o M.
Deve-se permanecer em 7 ate´ o bota˜o ser desativado.
Com o motor Z
ligado.
Isso leva a` condic¸a˜o descrita pelo estado 4: carro a meio caminho do
ponto A. Que deve ser registrado na primeira coluna do estado 7.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10 X 1,10 X X
Estado 7 4
,01
7
,01
(ICET) Sistemas Digitais 2017 49 / 176
O Me´todo Cla´ssico de Huffman
Ana´lise do estado 7
O sistema atinge este estado vindo do estado 2, na situac¸a˜o do carro sair
do ponto A antes do operador desativar o bota˜o M.
Deve-se permanecer em 7 ate´ o bota˜o ser desativado. Com o motor Z
ligado.
Isso leva a` condic¸a˜o descrita pelo estado 4: carro a meio caminho do
ponto A. Que deve ser registrado na primeira coluna do estado 7.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10 X 1,10 X X
Estado 7 4
,01
7,01
(ICET) Sistemas Digitais 2017 49 / 176
O Me´todo Cla´ssico de Huffman
Ana´lise do estado 7
O sistema atinge este estado vindo do estado 2, na situac¸a˜o do carro sair
do ponto A antes do operador desativar o bota˜o M.
Deve-se permanecer em 7 ate´ o bota˜o ser desativado. Com o motor Z
ligado.
Isso leva a` condic¸a˜o descrita pelo estado 4: carro a meio caminho do
ponto A.
Que deve ser registrado na primeira coluna do estado 7.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10 X 1,10 X X
Estado 7 4
,01
7,01
(ICET) Sistemas Digitais 2017 49 / 176
O Me´todo Cla´ssico de Huffman
Ana´lise do estado 7
O sistema atinge este estado vindo do estado 2, na situac¸a˜o do carro sair
do ponto A antes do operador desativar o bota˜o M.
Deve-se permanecer em 7 ate´ o bota˜o ser desativado. Com o motor Z
ligado.
Isso leva a` condic¸a˜o descrita pelo estado 4: carro a meio caminho do
ponto A. Que deve ser registrado na primeira coluna do estado 7.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,01 2,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10 X 1,10 X X
Estado 7 4,01 7,01
(ICET) Sistemas Digitais 2017 49 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 1
Ana´lise do estado 7
Coluna 2: Carro atinge o ponto B imediatamente
Coluna 4: Carro voltaria ao ponto A
Coluna 5: acionamento na˜o previsto do bota˜o M
Finalmente, a tabela primitiva de fluxo esta´ completa.
M A B 000 001 011 010 110 111 101 100
Estado 1 X X 1,00 2,00 X
Estado 2 4,01 X 3,012,01 7,01
Estado 3 4,01 X 3,01 X X
Estado 4 4,01 5,01 X X X
Estado 5 6,10 5,10 X X X
Estado 6 6,10 X 1,10 X X
Estado 7 4,01 X X X 7,01
(ICET) Sistemas Digitais 2017 50 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Um disco e´ colocado em rotac¸a˜o por um motor M alimentado por um releˆ
Z.
(ICET) Sistemas Digitais 2017 51 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Na posic¸a˜o inicial, o disco P pressiona um contato X. O operador ao tocar
o bota˜o de pressa˜o B coloca o motor em movimento.
(ICET) Sistemas Digitais 2017 51 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O disco devera´ enta˜o fazer uma volta completa e parar novamente
(desligando o motor) quando voltar a` posic¸a˜o inicial (sobre o contato X).
(ICET) Sistemas Digitais 2017 51 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Deseja-se obter a tabela primitiva de fluxo correspondente.
(ICET) Sistemas Digitais 2017 51 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Neste problema temos o bota˜o B e o contato X como informac¸o˜es de
entrada e Z como sa´ıda (correspondendo ao acionamento ou na˜o do motor
M).
A tabela primitiva de fluxo possuira´ 4 colunas, correspondentes a`s
combinac¸o˜es poss´ıveis das varia´veis de entrada.
B X 00 01 11 10
Estado 1
(ICET) Sistemas Digitais 2017 52 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O estado escolhido para iniciar a ana´lise foi a posic¸a˜o em que o disco P
pressiona o contato X com o motor desligado.
B X 00 01 11 10
Estado 1 1,0
(ICET) Sistemas Digitais 2017 53 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o disco acionando X
(X = 1), o operador ira´ pressionar o bota˜o B
(B = 1) passando o sistema ao estado total (2− 11), acionando o motor
(Z = 1) que inicia o movimento do disco.
B X 00 01
11
10
Estado 1
X
1,0
2,1 X
Estado 2
Demais casos irrelevantes, pois implicam no movimento imediato do disco
(X = 0).
Registra-se o Estado 2 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 54 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o disco acionando X (X = 1),
o operador ira´ pressionar o bota˜o B
(B = 1) passando o sistema ao estado total (2− 11), acionando o motor
(Z = 1) que inicia o movimento do disco.
B X 00 01
1
1 10
Estado 1
X
1,0
2,1 X
Estado 2
Demais casos irrelevantes, pois implicam no movimento imediato do disco
(X = 0).
Registra-se o Estado 2 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 54 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o disco acionando X (X = 1), o operador ira´ pressionar o bota˜o B
(B = 1) passando o sistema ao estado total (2− 11), acionando o motor
(Z = 1) que inicia o movimento do disco.
B X 00 01
1
1 10
Estado 1
X
1,0
2,1 X
Estado 2
Demais casos irrelevantes, pois implicam no movimento imediato do disco
(X = 0).
Registra-se o Estado 2 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 54 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o disco acionando X (X = 1), o operador ira´ pressionar o bota˜o B
(B = 1)
passando o sistema ao estado total (2− 11), acionando o motor
(Z = 1) que inicia o movimento do disco.
B X 00 01 11 10
Estado 1
X
1,0
2,1 X
Estado 2
Demais casos irrelevantes, pois implicam no movimento imediato do disco
(X = 0).
Registra-se o Estado 2 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 54 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o disco acionando X (X = 1), o operador ira´ pressionar o bota˜o B
(B = 1) passando o sistema ao estado total (2− 11),
acionando o motor
(Z = 1) que inicia o movimento do disco.
B X 00 01 11 10
Estado 1
X
1,0 2
,1 X
Estado 2
Demais casos irrelevantes, pois implicam no movimento imediato do disco
(X = 0).
Registra-se o Estado 2 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 54 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o disco acionando X (X = 1), o operador ira´ pressionar o bota˜o B
(B = 1) passando o sistema ao estado total (2− 11), acionando o motor
(Z = 1) que inicia o movimento do disco.
B X 00 01 11 10
Estado 1
X
1,0 2
,1 X
Estado 2
Demais casos irrelevantes, pois implicam no movimento imediato do disco
(X = 0).
Registra-se o Estado 2 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 54 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o disco acionando X (X = 1), o operador ira´ pressionar o bota˜o B
(B = 1) passando o sistema ao estado total (2− 11), acionando o motor
(Z = 1)
que inicia o movimento do disco.
B X 00 01 11 10
Estado 1
X
1,0 2,1
X
Estado 2
Demais casos irrelevantes, pois implicam no movimento imediato do disco
(X = 0).
Registra-se o Estado 2 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 54 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o disco acionando X (X = 1), o operador ira´ pressionar o bota˜o B
(B = 1) passando o sistema ao estado total (2− 11), acionando o motor
(Z = 1) que inicia o movimento do disco.
B X 00 01 11 10
Estado 1
X
1,0 2,1
X
Estado 2
Demais casos irrelevantes, pois implicam no movimento imediato do disco
(X = 0).
Registra-se o Estado 2 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 54 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o disco acionando X (X = 1), o operador ira´ pressionar o bota˜o B
(B = 1) passando o sistema ao estado total (2− 11), acionando o motor
(Z = 1) que inicia o movimento do disco.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2
Demais casos irrelevantes, pois implicam no movimento imediato do disco
(X = 0).
Registra-se o Estado 2 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 54 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o disco acionando X (X = 1), o operador ira´ pressionar o bota˜o B
(B = 1) passando o sistema ao estado total (2− 11), acionando o motor
(Z = 1) que inicia o movimento do disco.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2
Demais casos irrelevantes, pois implicam no movimento imediato do disco
(X = 0).
Registra-se o Estado 2 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 54 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O sistema deve permanecer no estado 2, com o motor ligado, enquanto as
entradas se mantiverem em (11).
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 2,1
(ICET) Sistemas Digitais 2017 55 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
A seguir, com o bota˜o B ainda pressionado o disco deixa o contato X
(X = 0)
, e o sistema passa ao estado (3− 10).
Registra-se o Estado 3 na tabela de fluxo.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2
X X
2,1
3,1
Estado 3
Demais casos irrrelevantes.
(ICET) Sistemas Digitais 2017 56 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
A seguir, com o bota˜o B ainda pressionado o disco deixa o contato X
(X = 0), e o sistema passa ao estado (3− 10).
Registra-se o Estado 3 na tabela de fluxo.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2
X X
2,1 3,1
Estado 3
Demais casos irrrelevantes.
(ICET) Sistemas Digitais 2017 56 / 176
O Me´todo Cla´ssico de HuffmanMe´todo Cla´ssico de Huffman – Exemplo 2
A seguir, com o bota˜o B ainda pressionado o disco deixa o contato X
(X = 0), e o sistema passa ao estado (3− 10).
Registra-se o Estado 3 na tabela de fluxo.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2
X X
2,1 3,1
Estado 3
Demais casos irrrelevantes.
(ICET) Sistemas Digitais 2017 56 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
A seguir, com o bota˜o B ainda pressionado o disco deixa o contato X
(X = 0), e o sistema passa ao estado (3− 10).
Registra-se o Estado 3 na tabela de fluxo.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3
Demais casos irrrelevantes.
(ICET) Sistemas Digitais 2017 56 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O sistema permanece
no estado 3, com o motor ligado, enquanto as
entradas permanecerem em (10).
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3
3,1
(ICET) Sistemas Digitais 2017 57 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O sistema permanece no estado 3, com o motor ligado, enquanto as
entradas permanecerem em (10).
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3 3,1
(ICET) Sistemas Digitais 2017 57 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o sistema no estado 3, e
o bota˜o B e´ solto, passa-se ao estado (4-00).
Registra-se o estado 4 na tabela de fluxo.
B X
0
0 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3
4,1 X X
3,1
Estado 4
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 58 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o sistema no estado 3, e o bota˜o B e´ solto,
passa-se ao estado (4-00).
Registra-se o estado 4 na tabela de fluxo.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3
4,1 X X
3,1
Estado 4
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 58 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o sistema no estado 3, e o bota˜o B e´ solto, passa-se ao estado (4-00).
Registra-se o estado 4 na tabela de fluxo.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3 4,1
X X
3,1
Estado 4
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 58 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o sistema no estado 3, e o bota˜o B e´ solto, passa-se ao estado (4-00).
Registra-se o estado 4 na tabela de fluxo.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3 4,1
X X
3,1
Estado 4
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 58 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Com o sistema no estado 3, e o bota˜o B e´ solto, passa-se ao estado (4-00).
Registra-se o estado 4 na tabela de fluxo.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 58 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O sistema permanece no estado 4,
enquanto o disco esta´ a meio caminho,
girando.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4
4,1
(ICET) Sistemas Digitais 2017 59 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O sistema permanece no estado 4, enquanto o disco esta´ a meio caminho,
girando.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1
(ICET) Sistemas Digitais 2017 59 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Quando o disco completar a volta,
e acionar novamente o contato X,
retorna-se ao estado 1.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1
1,0 X X
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 60 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Quando o disco completar a volta, e acionar novamente o contato X,
retorna-se ao estado 1.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0
X X
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 60 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Quando o disco completar a volta, e acionar novamente o contato X,
retorna-se ao estado 1.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X X 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 60 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O pro´ximo passo sera´ considerar uma situac¸a˜o que na˜o foi vista no in´ıcio,
e que passamos a ver agora. Isso e´ u´til ao aprendizado.
Note que, a partir do estado 2− 11, existe a possibilidade do operador
soltar o bota˜o B antes que o disco solte o contato X.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X
5,1
2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5
Neste caso, adiciona-se um estado, e o sistema vai ao estado. (5− 01)
Registra-se o estado 5 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 61 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O pro´ximo passo sera´ considerar uma situac¸a˜o que na˜o foi vista no in´ıcio,
e que passamos a ver agora. Isso e´ u´til ao aprendizado.
Note que, a partir do estado 2− 11, existe a possibilidade do operador
soltar o bota˜o B antes que o disco solte o contato X.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X
5,1
2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5
Neste caso, adiciona-se um estado,
e o sistema vai ao estado. (5− 01)
Registra-se o estado 5 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 61 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O pro´ximo passo sera´ considerar uma situac¸a˜o que na˜o foi vista no in´ıcio,
e que passamos a ver agora. Isso e´ u´til ao aprendizado.
Note que, a partir do estado 2− 11, existe a possibilidade do operador
soltar o bota˜o B antes que o disco solte o contato X.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X 5,1 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5
Neste caso, adiciona-se um estado, e o sistema vai ao estado. (5− 01)
Registra-se o estado 5 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 61 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O pro´ximo passo sera´ considerar uma situac¸a˜o que na˜o foi vista no in´ıcio,
e que passamos a ver agora. Isso e´ u´til ao aprendizado.
Note que, a partir do estado 2− 11, existe a possibilidade do operador
soltar o bota˜o B antes que o disco solte o contato X.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X 5,1 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5
Neste caso, adiciona-se um estado, e o sistema vai ao estado. (5− 01)
Registra-se o estado 5 na tabela de fluxo.
(ICET) Sistemas Digitais 2017 61 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O sistema deve permanecer
no estado 5, com o motor ligado, ate´ que o
disco deixe o contato X (enquanto persistir 01).
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X 5,1 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5
5,1(ICET) Sistemas Digitais 2017 62 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O sistema deve permanecer no estado 5,
com o motor ligado, ate´ que o
disco deixe o contato X (enquanto persistir 01).
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X 5,1 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5 5
,1
(ICET) Sistemas Digitais 2017 62 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O sistema deve permanecer no estado 5, com o motor ligado,
ate´ que o
disco deixe o contato X (enquanto persistir 01).
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X 5,1 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5 5,1
(ICET) Sistemas Digitais 2017 62 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
O sistema deve permanecer no estado 5, com o motor ligado, ate´ que o
disco deixe o contato X (enquanto persistir 01).
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X 5,1 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5 5,1
(ICET) Sistemas Digitais 2017 62 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Quando o disco deixar o contato X,
o sistema deve ir ao estado 4, que
corresponde ao disco girando.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X 5,1 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5
4,1
5,1
X X
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 63 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Quando o disco deixar o contato X, o sistema deve ir ao estado 4, que
corresponde ao disco girando.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X 5,1 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5 4,1 5,1
X X
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 63 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
Quando o disco deixar o contato X, o sistema deve ir ao estado 4, que
corresponde ao disco girando.
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X 5,1 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5 4,1 5,1 X X
Demais casos sa˜o irrelevantes.
(ICET) Sistemas Digitais 2017 63 / 176
O Me´todo Cla´ssico de Huffman
Me´todo Cla´ssico de Huffman – Exemplo 2
B X 00 01 11 10
Estado 1 X 1,0 2,1 X
Estado 2 X 5,1 2,1 3,1
Estado 3 4,1 X X 3,1
Estado 4 4,1 1,0 X X
Estado 5 4,1 5,1 X X
A tabela de fluxo primitiva esta´ terminada.
(ICET) Sistemas Digitais 2017 64 / 176
O processo de reduc¸a˜o de tabelas de fluxo
Plano
1 O Me´todo Cla´ssico de Huffman
2 O processo de reduc¸a˜o de tabelas de fluxo
3 Designac¸a˜o de Estados Internos
(ICET) Sistemas Digitais 2017 65 / 176
O processo de reduc¸a˜o de tabelas de fluxo
O processo de reduc¸a˜o de tabelas de fluxo
A tabela primitiva de fluxo pode conter erros de redundaˆncia decorrentes
da interpretac¸a˜o do problema analisado.
Ocorre enta˜o um aumento no nu´mero de estados internos do sistema,
tornando-o maior e menos confia´vel pelo aumento do nu´mero de blocos
lo´gicos necessa´rios para sua implementac¸a˜o.
Apresentaremos um me´todo para minimizar o nu´mero de estados internos
da tabela primitiva de fluxo, atrave´s da detecc¸a˜o e eliminac¸a˜o dos estados
redundantes, e tambe´m dos subconjuntos de estados internos que possam
ser reduzidos a um u´nico estado, e que sera˜o denominados “estados
compat´ıveis”.
(ICET) Sistemas Digitais 2017 66 / 176
O processo de reduc¸a˜o de tabelas de fluxo
O processo de reduc¸a˜o de tabelas de fluxo
Relac¸a˜o de cobrimento para estados
Considere as tabelas de fluxo. Se, ao aplicar a mesma sequeˆncia de
entradas a dois estados, um em cada tabela, for obtida a mesma sequeˆncia
de sa´ıda, diz-se que um estado cobre o outro.
A B C D
1 1,0 1,0 1,0 2,0
2 2,1 2,0 1,0 2,0
A B C D
1 6,0 1,0 2,0 4,0
2 X 6,0 2,0 4,0
3 X 1,0 3,0 4,0
4 5,1 X 2,0 4,0
5 5,1 5,0 3,0 4,0
6 1,0 6,0 3,0 4,0
(ICET) Sistemas Digitais 2017 67 / 176
O processo de reduc¸a˜o de tabelas de fluxo
O processo de reduc¸a˜o de tabelas de fluxo
Relac¸a˜o de cobrimento para estados
Note que o estado 2 da tabela A cobre o estado 4 da tabela B.
Mas o inverso na˜o ocorre, devido a` condic¸a˜o irrelevante.
Tabela A
A B C D
1 1,0 1,0 1,0 2,0
2 2,1 2,0 1,0 2,0
Tabela B
A B C D
1 6,0 1,0 2,0 4,0
2 X 6,0 2,0 4,0
3 X 1,0 3,0 4,0
4 5,1 X 2,0 4,0
5 5,1 5,0 3,0 4,0
6 1,0 6,0 3,0 4,0
(ICET) Sistemas Digitais 2017 68 / 176
O processo de reduc¸a˜o de tabelas de fluxo
O processo de reduc¸a˜o de tabelas de fluxo
Relac¸a˜o de cobrimento para tabelas
Uma tabela de fluxo A cobre uma tabela de fluxo B, se todos os estados
da tabela B sa˜o cobertos por pelo menos um estado da tabela A.
A tabela que cobre pode ser empregada para realizar o circuito sequencial
desejado.
O problema, da reduc¸a˜o de tabelas de fluxo, se resume em determinar uma
tabela com m´ınimo nu´mero de estados, que cubra a tabela primitiva
obtida da ana´lise do problema sequencial que deve ser resolvido.
(ICET) Sistemas Digitais 2017 69 / 176
O processo de reduc¸a˜o de tabelas de fluxo
O processo de reduc¸a˜o de tabelas de fluxo
Relac¸a˜o de cobrimento para tabelas
E´ importante lembrar que a relac¸a˜o de cobrimento tanto para estados
quanto para tabelas, e´ reflexiva e transitiva mas na˜o e´ sime´trica, ou seja:
A. Uma tabela de fluxo cobre a si mesma;
B. Se uma tabela A cobre uma tabela B e B cobre a tabela C enta˜o a
tabela A cobre a tabela C;
C. e uma tabela A cobre a tabela B esta na˜o necessariamente cobre a
tabela A. (devido a existeˆncia de condic¸o˜es irrelevantes).
(ICET) Sistemas Digitais 2017 70 / 176
O processo de reduc¸a˜o de tabelas de fluxo
O processo de reduc¸a˜o de tabelas de fluxo
Estados Compat´ıveis
Dada uma tabela de fluxo A, se for poss´ıvel obter uma nova tabela B que
cubra a primeira e possua um menor nu´mero de estados internos, pode-se
concluir que existem pelo menos dois estados da tabela A que sa˜o
cobertos por um u´nico estado da tabela B.
Isto leva a definic¸a˜o de dois estados compat´ıveis de uma dada tabela de
fluxo, como sendo aqueles que sa˜o cobertos por um u´nico estado de uma
outra tabela.
(ICET) Sistemas Digitais 2017 71 / 176
O processo de reduc¸a˜o de tabelas de fluxo
O processo de reduc¸a˜o de tabelas de fluxo
Estados Compat´ıveis
Pode-se determinar estados compat´ıveis (equivalentes), aplicando as
condic¸o˜es:
1 Dois estados sa˜o compat´ıveis, se suas sa´ıdas respectivas tomadas
duas a duas para a mesma entrada forem na˜o contradito´rias (iguais
ou irrelevantes).
2 os estados seguintes a ambos os estados sejam tambe´m, compat´ıveis
entre si.
A compatibilidade entre estados sera´ anotada em uma Tabela de Pares
compat´ıveis
(ICET) Sistemas Digitais 2017 72 / 176
O processo de reduc¸a˜o de tabelas de fluxo
O processo de reduc¸a˜o de tabelas de fluxo
Tabela de Pares
Possuira´ tantas linhas quantos forem os estados internos da tabela de
fluxo menos uma, e pode fornecer em cada uma de suas ce´lulas treˆs tipos
diferentes de informac¸o˜es:
A. A ce´lula vazia indica que os estados sa˜o compat´ıveis;
B. A ce´lula contera´ um ou mais pares de estados que implicam na
compatibilidade do estado considerado.
C. A ce´lula contera´ um ”X”se os estados na˜o sa˜o compat´ıveis.
1
16 2
23 16 3
X 23 4
X 23, 56 15 23 5
23 23 16 X X 6
(ICET) Sistemas Digitais 2017 73 / 176
O processo de reduc¸a˜o de tabelas de fluxo
O processo de reduc¸a˜o de tabelas de fluxo
Tabela de Pares
Como exemplo, vamos minimizar a seguinte tabela de fluxo:
Entradas
Est. 00 01 11 10
1 6,0 1,0 2,0 4,0
2 X 6,0 2,0 4,0
3 X