Sistemas Digitais II - Poli - P1 2015 - EC2 (currículo reformulado)

Prévia do material em texto

y +1/1/60+ y
PCS3225 2015S2 Primeira Prova 31/08/2015
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
Utilize caneta azul ou preta para marcar as caixas e preencha a caixa totalmente
para correta interpretação. Exemplo: ⌅. Não use ⇥.
1 M. Túlio 2 Pedro 3 Bruno 4 Midorikawa
Marque as caixas ao lado para formar o seu número USP e escreva seu nome
abaixo.
Nome (completo):
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(a) (b)
Figura 1: Circuitos com FF D
Pergunta 1 [1 ponto] Considere os circuitos da Figura 1, construídos em torno de flip-flops tipo D (FF-D), com
entradas e1 e e2, saídas Q e Q, e clock. Marque somente a afirmação correta:
A (a) é um FF-SR e (b) é um FF-JK
B ambos são FF-SR
C ambos são FF-JK
D ambos são FF-D com enables
E (a) é um FF-JK e (b) é um FF-SR
Figura 2
Pergunta 2 [1 ponto] Sobre o circuito da Figura 2,
marque a(s) afirmação(ões) correta(s):
A É um FF-D, onde a entrada tem a função lógica da
entrada D.
B Possui o mesmo problema de instabilidade de um
latch tipo JK quando J=K=1.
C É um latch tipo D, onde a entrada tem a função
lógica da entrada D.
D É um latch tipo T, onde a entrada tem a função
lógica da entrada T.
E É um FF-T de ação direta, onde a entrada tem a
função lógica da entrada T.
y y
y +1/2/59+ y
Figura 3: Descrição VHDL da entidade biestavel.
Pergunta 3 [1 ponto] Considere a descrição VHDL da
Figura 3 de um circuito biestável. Marque a(s) afirma-
ção(ões) correta(s).
A O biestável descrito no código é um latch tipo D,
onde a porta de entrada C corresponde ao dado de
entrada a ser armazenado.
B Este biestável possui um sinal de reset assíncrono.
C Para que a entidade biestavel seja um flip-flop
sensível a borda de descida, é necessário que so-
mente a linha 14 seja alterada para if A’event
and A<=’0’ then X <= C; Y <= not C; .
D A lista de sensibilidade do processo deve conter os
sinais que ativam a sua execução. Assim, para a
entidade biestavel, a lista de sensibilidade deve
conter somente os sinais A e B.
E O componente biestavel descrito no código da fi-
gura não é um flip-flop porque não possui um sinal
de entrada chamado clock.
Figura 4: Descrição de uma máquina de estados em VHDL.
Pergunta 4 [1 ponto] Assinale as afirmações corretas
sobre máquinas de estados em VHDL e considerando a
descrição VHDL mostrada na Figura 4 abaixo.
A O processo descrito entre as linhas 15 a 27 descreve
a lógica de próximo estado de uma máquina de es-
tados do tipo Moore.
B Esta máquina de estados descreve um flip-flop JK,
onde os sinais ENTRADA 1 e ENTRADA2 se re-
ferem aos sinais K e J, respectivamente.
C Falta um processo na descrição, pois uma máquina
de estados que modela um circuito sequencial sín-
crono deve ter três processos que descrevem a me-
mória de estado, a lógica de próximo estado e a
lógica de saída.
D O comando with select usado nas linhas 29 a 32
é um comando sequencial que descreve a lógica de
saída da máquina de estados.
E A descrição modela um circuito sequencial que de-
tecta a ocorrência de um padrão de entradas onde
o número de ZEROs na ENTRADA1 é maior que
o número de UMs na ENTRADA2.
y y
y +1/3/58+ y
Pergunta 5 [1 ponto] Existe um problema importante que um Engenheiro de projetos deve resolver: Como se pode
verificar a equivalência entre dois circuitos digitais? Pode-se entender que dois circuitos são equivalentes quando para
os mesmos valores de dados de entradas, obtém-se os mesmos valores de saída. Em outras palavras, dois circuitos
que realizam a mesma função (operação lógica) sobre os mesmos dados obtendo os mesmos resultados podem ser
considerados equivalentes. Sobre este assunto fazem-se algumas asserções que devem ser marcadas somente se forem
verdadeiras:
A O Diagrama ASM (sigla em inglês de Algorithm State Machine) é uma representação gráfica do algoritmo que
descreve o comportamento de um sistema digital. Trata-se de uma ferramenta de descrição de uma FSM que
propõe uma maneira diagramática de representar funções de saída e de próximo estado em função do estado
atual e das entradas.
B Pode-se verificar a equivalência entre dois circuitos digitais puramente combinatórios pela comparação de sua
descrição comportamental por meio da aplicação das técnicas de Tabelas da Verdade, de Mapas de Karnaugh ou
de Equações Algébricas, mesmo quando os dois circuitos estejam descritos por técnicas distintas entre as citadas.
C Pode-se verificar a equivalência entre dois circuitos digitais puramente sequenciais pela comparação de sua
descrição comportamental por meio do modelo de Máquinas de Estados Finitos (FSM – sigla em inglês). Porém
os Diagramas de Transição de Estados dos modelos FSM dos dois circuitos devem ser exatamente iguais para
garantir a equivalência.
D Não se pode verificar a equivalência entre dois circuitos digitais mistos, combinatório-sequenciais, pela compara-
ção de sua descrição comportamental por meio do modelo de Máquinas de Estados Finitos (FSM ) simplesmente
porque este modelo não é aderente à descrição comportamental desta classe de circuitos.
E Desafortunadamente a aplicação da técnica de descrição comportamental do DiagramaASM não permite verificar
a equivalência entre dois circuitos digitais mistos, combinatório-sequenciais, simplesmente porque esta técnica
não permite a representação de variáveis de saída cujo valor seja independente do valor das variáveis de entrada
(dependentes apenas do valor do estado atual).
Pergunta 6 [1 ponto] A técnica ASM permite a tradução de diagramas de transição de estados de FSMs em
fluxogramas de blocos gráficos primitivos ASM. Estes possibilitam o mapeamento de elementos primitivos de hardware
associados, sendo possível obter o diagrama lógico de um circuito a partir de sua descrição comportamental realizada
com ASM. Sobre este assunto fazem-se algumas asseverações que devem ser marcadas somente se forem verdadeiras:
A Sabe-se que em uma FSM construída com base no modelo de Mealy o valor de uma qualquer de suas variáveis
de saída depende do valor do estado atual e dos valores das variáveis de entrada. Por outro lado, em uma FSM
construída com base no modelo de Moore, o valor de uma qualquer de suas variáveis de saída depende apenas
e tão somente do valor do estado atual. Por esta razão em um fluxograma ASM de uma FSM construída com
base no modelo de Moore, não se faz uso do Bloco de Saída Condicional.
B Sabe-se que ao simular a execução de um fluxograma ASM que forneça a descrição comportamental de uma FSM
de n estados, em cada período do clock, um e apenas um dos estados estará ativo, e todos os demais n�1 estados
estarão inativos. Isto ocorre tanto para um circuito no modelo deMealy como no modelo deMoore. Suponha que
em m < n destes estados, em seus respectivos Blocos de Estado, aparece o nome da variável habilita. Nestas
condições a maneira adequada de se gerar a saída externa habilita é utilizar um Bloco de Saída Condicional
em cada um dos m estados onde habilita aparece.
C Uma vantagem no uso da técnica ASM para a síntese de FSMs é que todos os blocos primitivos ASM – Bloco
de Estado, Bloco de Decisão, Bloco de Junção, Bloco de Saída Condicional – possam e devam ser utilizados no
processo de síntese de FSMs, na elaboração dos fluxogramas, tanto no modelo de Mealy como no de Moore. Um
fluxograma correto por construção (para os dois modelos) só poderá ser obtido e será consistente (coerente) se
contiver em seu diagrama pelo menos uma instância, de todos e cada um destes 4 blocos.D Sabe-se que ao simular a execução de um fluxograma ASM que forneça a descrição comportamental de uma FSM
de n estados, em cada período do clock, um e apenas um dos estados estará ativo, e todos os demais n�1 estados
estarão inativos. Isto ocorre tanto para um circuito no modelo de Mealy como no modelo de Moore. Suponha
que em m < n destes estados, em seus respectivos Blocos de Estado, aparece o nome da variável habilita.
Nestas condições a maneira adequada de se gerar a saída externa habilita é utilizar um Bloco de Junção de m
entradas e uma saída.
E Imagine uma FSM, modelo de Moore com 10 estados, cuja descrição comportamental está determinada por um
fluxograma ASM. Imagine que para 3 quaisquer destes estados, dentro de seus respectivos Blocos de Estado,
aparece o escrito o nome da variável habilita. Neste caso pode-se afirmar que para a variável habilita só será
atribuído o valor lógico 1 quando pelo menos 2, daqueles 3 estados, estiverem ativos ao mesmo tempo.
y y
y +1/4/57+ y
Esta página poderá ser usada como rascunho e não será avaliada.
y y
y +1/5/56+ y
Pergunta 1 [4 pontos] Considere o circuito sequencial apresentado na Figura 5.
Figura 5: Circuito sequencial.
(a) [0.2 ponto] O circuito segue o modelo de Mealy ou de Moore? Justifique. Para uso do professor: 0 1 2
(b) [0,4 ponto] Identifique as variáveis de entrada, de saída, de excitação e de estado.
Para uso do professor: 0 1 2 3 4
Variável de entrada: Variável de saída:
Variáveis de excitação: Variáveis de estado:
(c) [0,5 ponto] Descreva as equações referentes às variáveis de excitação e de saída.
Para uso do professor: 0 1 2 3 5
(d) [1,0 ponto] Preencha as Tabelas de Excitação e do Flip-Flop do tipo JK, respectivamente a seguir:
Para uso do professor: 0 1 2 3 4 5
y y
y +1/6/55+ y
(e) [1,0 ponto] Considere as Tabelas de Designação de Estados (Tabela 3) e a do Flip-Flop do tipo JK (Tabela 2).
Preencha as Tabelas de Estados/Saída (Tabelas 3a e 3b).
Para uso do professor: 0 1 2 3 4 5 6 7 8 9 10
(f) [0,4 ponto] Faça o Diagrama de Transição de Estados correspondente ao circuito da Figura 5.
Para uso do professor: 0 1 2 3 4
(g) [0,5 ponto] Faça a interpretação da função do Circuito fornecido na Figura 5.
Para uso do professor: 0 1 2 3 4 5
y y
Catálogo
PCS3225 2015S2 Primeira Prova 31/08/2015
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
0
1
2
3
4
5
6
7
8
9
Utilize caneta azul ou preta para marcar as caixas e preencha a caixa totalmente
para correta interpretação. Exemplo: ⌅. Não use ⇥.
1 M. Túlio 2 Pedro 3 Bruno 4 Midorikawa
Marque as caixas ao lado para formar o seu número USP e escreva seu nome
abaixo.
Nome (completo):
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
(a) (b)
Figura 1: Circuitos com FF D
Pergunta [bca1] [1 ponto] Considere os circuitos da Figura 1, construídos em torno de flip-flops tipo D (FF-D),
com entradas e1 e e2, saídas Q e Q, e clock. Marque somente a afirmação correta:
A (a) é um FF-JK e (b) é um FF-SR
B (a) é um FF-SR e (b) é um FF-JK
C ambos são FF-D com enables
D ambos são FF-SR
E ambos são FF-JK
Figura 2
Catálogo
Pergunta [bca2] [1 ponto] Sobre o circuito da Figura 2,
marque a(s) afirmação(ões) correta(s):
A Possui o mesmo problema de instabilidade de um
latch tipo JK quando J=K=1.
B É um latch tipo T, onde a entrada tem a função
lógica da entrada T.
C É um FF-T de ação direta, onde a entrada tem a
função lógica da entrada T.
D É um latch tipo D, onde a entrada tem a função
lógica da entrada D.
E É um FF-D, onde a entrada tem a função lógica da
entrada D.
Figura 3: Descrição VHDL da entidade biestavel.
Pergunta [etm1] [1 ponto] Considere a descrição VHDL
da Figura 3 de um circuito biestável. Marque a(s) afir-
mação(ões) correta(s).
A O biestável descrito no código é um latch tipo D,
onde a porta de entrada C corresponde ao dado de
entrada a ser armazenado.
B Este biestável possui um sinal de reset assíncrono.
C O componente biestavel descrito no código da fi-
gura não é um flip-flop porque não possui um sinal
de entrada chamado clock.
D Para que a entidade biestavel seja um flip-flop
sensível a borda de descida, é necessário que so-
mente a linha 14 seja alterada para if A’event
and A<=’0’ then X <= C; Y <= not C; .
E A lista de sensibilidade do processo deve conter os
sinais que ativam a sua execução. Assim, para a
entidade biestavel, a lista de sensibilidade deve
conter somente os sinais A e B.
Figura 4: Descrição de uma máquina de estados em VHDL.
Catálogo
Pergunta [etm2] [1 ponto] Assinale as afirmações corre-
tas sobre máquinas de estados em VHDL e considerando
a descrição VHDL mostrada na Figura 4 abaixo.
A Esta máquina de estados descreve um flip-flop JK,
onde os sinais ENTRADA 1 e ENTRADA2 se re-
ferem aos sinais K e J, respectivamente.
B O processo descrito entre as linhas 15 a 27 descreve
a lógica de próximo estado de uma máquina de es-
tados do tipo Moore.
C Falta um processo na descrição, pois uma máquina
de estados que modela um circuito sequencial sín-
crono deve ter três processos que descrevem a me-
mória de estado, a lógica de próximo estado e a
lógica de saída.
D A descrição modela um circuito sequencial que de-
tecta a ocorrência de um padrão de entradas onde
o número de ZEROs na ENTRADA1 é maior que
o número de UMs na ENTRADA2.
E O comando with select usado nas linhas 29 a 32
é um comando sequencial que descreve a lógica de
saída da máquina de estados.
Pergunta [mtca1] [1 ponto] Existe um problema importante que um Engenheiro de projetos deve resolver: Como se
pode verificar a equivalência entre dois circuitos digitais? Pode-se entender que dois circuitos são equivalentes quando
para os mesmos valores de dados de entradas, obtém-se os mesmos valores de saída. Em outras palavras, dois circuitos
que realizam a mesma função (operação lógica) sobre os mesmos dados obtendo os mesmos resultados podem ser
considerados equivalentes. Sobre este assunto fazem-se algumas asserções que devem ser marcadas somente se forem
verdadeiras:
A Pode-se verificar a equivalência entre dois circuitos digitais puramente combinatórios pela comparação de sua
descrição comportamental por meio da aplicação das técnicas de Tabelas da Verdade, de Mapas de Karnaugh ou
de Equações Algébricas, mesmo quando os dois circuitos estejam descritos por técnicas distintas entre as citadas.
B Pode-se verificar a equivalência entre dois circuitos digitais puramente sequenciais pela comparação de sua
descrição comportamental por meio do modelo de Máquinas de Estados Finitos (FSM – sigla em inglês). Porém
os Diagramas de Transição de Estados dos modelos FSM dos dois circuitos devem ser exatamente iguais para
garantir a equivalência.
C Não se pode verificar a equivalência entre dois circuitos digitais mistos, combinatório-sequenciais, pela compara-
ção de sua descrição comportamental por meio do modelo de Máquinas de Estados Finitos (FSM ) simplesmente
porque este modelo não é aderente à descrição comportamental desta classe de circuitos.
D O Diagrama ASM (sigla em inglês de Algorithm State Machine) é uma representação gráfica do algoritmo que
descreve o comportamento de um sistema digital. Trata-se de uma ferramenta de descrição de uma FSM que
propõe uma maneira diagramática de representar funções de saída e de próximo estado em função do estado
atual e das entradas.
E Desafortunadamente a aplicação da técnica de descrição comportamental do DiagramaASM não permite verificara equivalência entre dois circuitos digitais mistos, combinatório-sequenciais, simplesmente porque esta técnica
não permite a representação de variáveis de saída cujo valor seja independente do valor das variáveis de entrada
(dependentes apenas do valor do estado atual).
Catálogo
Pergunta [mtca2] [1 ponto] A técnica ASM permite a tradução de diagramas de transição de estados de FSMs em
fluxogramas de blocos gráficos primitivos ASM. Estes possibilitam o mapeamento de elementos primitivos de hardware
associados, sendo possível obter o diagrama lógico de um circuito a partir de sua descrição comportamental realizada
com ASM. Sobre este assunto fazem-se algumas asseverações que devem ser marcadas somente se forem verdadeiras:
A Uma vantagem no uso da técnica ASM para a síntese de FSMs é que todos os blocos primitivos ASM – Bloco
de Estado, Bloco de Decisão, Bloco de Junção, Bloco de Saída Condicional – possam e devam ser utilizados no
processo de síntese de FSMs, na elaboração dos fluxogramas, tanto no modelo de Mealy como no de Moore. Um
fluxograma correto por construção (para os dois modelos) só poderá ser obtido e será consistente (coerente) se
contiver em seu diagrama pelo menos uma instância, de todos e cada um destes 4 blocos.
B Imagine uma FSM, modelo de Moore com 10 estados, cuja descrição comportamental está determinada por um
fluxograma ASM. Imagine que para 3 quaisquer destes estados, dentro de seus respectivos Blocos de Estado,
aparece o escrito o nome da variável habilita. Neste caso pode-se afirmar que para a variável habilita só será
atribuído o valor lógico 1 quando pelo menos 2, daqueles 3 estados, estiverem ativos ao mesmo tempo.
C Sabe-se que em uma FSM construída com base no modelo de Mealy o valor de uma qualquer de suas variáveis
de saída depende do valor do estado atual e dos valores das variáveis de entrada. Por outro lado, em uma FSM
construída com base no modelo de Moore, o valor de uma qualquer de suas variáveis de saída depende apenas
e tão somente do valor do estado atual. Por esta razão em um fluxograma ASM de uma FSM construída com
base no modelo de Moore, não se faz uso do Bloco de Saída Condicional.
D Sabe-se que ao simular a execução de um fluxograma ASM que forneça a descrição comportamental de uma FSM
de n estados, em cada período do clock, um e apenas um dos estados estará ativo, e todos os demais n�1 estados
estarão inativos. Isto ocorre tanto para um circuito no modelo de Mealy como no modelo de Moore. Suponha
que em m < n destes estados, em seus respectivos Blocos de Estado, aparece o nome da variável habilita.
Nestas condições a maneira adequada de se gerar a saída externa habilita é utilizar um Bloco de Junção de m
entradas e uma saída.
E Sabe-se que ao simular a execução de um fluxograma ASM que forneça a descrição comportamental de uma FSM
de n estados, em cada período do clock, um e apenas um dos estados estará ativo, e todos os demais n�1 estados
estarão inativos. Isto ocorre tanto para um circuito no modelo deMealy como no modelo deMoore. Suponha que
em m < n destes estados, em seus respectivos Blocos de Estado, aparece o nome da variável habilita. Nestas
condições a maneira adequada de se gerar a saída externa habilita é utilizar um Bloco de Saída Condicional
em cada um dos m estados onde habilita aparece.
Esta página poderá ser usada como rascunho e não será avaliada.
	
  	
  
Sistemas	
  Digitais	
  II	
   Prova	
  1	
   Data	
   	
  PCS3225	
   2015S2	
   31/08/2015	
  
Nome:	
   GABARITO	
   #USP:	
   	
   Turma:	
   	
  
	
  
Questão 1 (valor: 4,0 pontos) 
 Considere	
  o	
  circuito	
  sequencial	
  apresentado	
  na	
  Figura	
  1.	
  	
  
	
  
Figura	
  1:	
  Circuito	
  sequencial.	
  	
  (a) (0,2	
  ponto)	
  O	
  circuito	
  segue	
  o	
  modelo	
  de	
  Mealy	
  ou	
  de	
  Moore?	
  Justifique:	
  O	
  circuito	
  segue	
  o	
  modelo	
  de	
  Moore,	
  pois	
  a	
  saída	
  z1	
  depende	
  apenas	
  das	
  variáveis	
  	
  de	
  estados	
  y1	
  e	
  y2.	
  	
  (b) (0,4	
  ponto)	
  Identifique	
  as	
  variáveis	
  de	
  entrada,	
  de	
  saída,	
  de	
  excitação	
  e	
  de	
  estado.	
  Variável	
  de	
  entrada	
  :	
  x	
  Variáveis	
  de	
  saída	
  :	
  z1	
  Variáveis	
  de	
  excitação	
  :	
  J1,	
  K1,	
  J2	
  e	
  K2	
  Variáveis	
  de	
  estado:	
  y1	
  e	
  y2	
  	
  (c) (0,5	
  ponto)	
  Descreva	
  as	
  equações	
  referentes	
  às	
  variáveis	
  de	
  excitação	
  e	
  de	
  saída.	
  J1	
  =	
  (xy2)’	
  K1	
  =	
  y'2	
  J2	
  =	
  “1”	
  K2	
  =	
  “1”	
  z1	
  	
  =	
  y1’y2	
  	
  (d) (1,0	
  pontos)	
  Preencha	
  as	
  Tabelas	
  de	
  Excitação	
  e	
  do	
  Flip-­‐Flop	
  JK	
  ,	
  respectivamente	
  a	
  seguir:	
  
Tabela1:	
  Excitação.	
   	
   	
   	
   	
   Tabela	
  2:	
  Flip-­‐Flop	
  do	
  tipo	
  JK.	
  	
  
	
  y1t	
   y2t	
  
xt	
  0	
   1	
  0	
   0	
   11/11	
   11/11	
  0	
   1	
   10/11	
   00/11	
  1	
   1	
   10/11	
   00/11	
  1	
   0	
   11/11	
   11/11	
  	
   	
   J1tK1t/J2tK2t	
  
Entradas	
   Saídas	
  
J	
   K	
   Q	
   Q’	
  0	
   0	
   Q	
   Q’	
  0	
   1	
   0	
   1	
  1	
   0	
   1	
   0	
  1	
   1	
   Q’	
   Q	
   	
  
	
  	
  (e) (1,0	
  ponto)	
  Considere	
  as	
  Tabelas	
  de	
  Designação	
  de	
  Estados	
  (Tabela	
  3)	
  e	
  a	
  do	
  Flip-­‐Flop	
  do	
   tipo	
   JK	
  (Tabela	
  2).	
  Preencha	
   	
  as	
  Tabelas	
  de	
  Estados/Saída	
  (Tabelas	
  3a	
  e	
  3b).	
  
	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  	
  Tabela3:	
  Designação	
  dos	
  Estados.	
  	
  	
  	
  	
  	
  	
  	
  	
  
Tabela	
  3a:	
  Estados	
  e	
  Saída.	
   	
   	
  	
  	
  	
  	
  	
  	
   	
  	
  	
  	
  	
  	
  Tabela	
  3b:	
  Estados	
  e	
  Saída.	
  	
  	
  	
   	
  	
  	
  	
  	
  	
  	
  (f) (0,4	
  ponto)	
  Faça	
  o	
  Diagrama	
  de	
  Transição	
  de	
  Estados	
  correspondente	
  ao	
  circuito	
  da	
  Figura	
  1.	
  Resposta:	
  	
  	
  	
  	
   	
  	
  	
  	
  	
  (g) (0,5	
  ponto)	
  Faça	
  a	
  interpretação	
  da	
  função	
  do	
  Circuito	
  fornecido	
  na	
  Figura	
  1.	
  	
  Resposta:	
  Dada	
  uma	
  cadeia	
  de	
  entrada	
  com	
  dígitos	
  0’s	
  e	
  1’s,	
   	
   encontra	
  uma	
  sub-­‐cadeia	
   de	
   no	
   mínimo	
   3	
   dígitos.	
   Após	
   encontrar	
   essa	
   sub-­‐cadeia,	
   inicia	
  novamente	
  a	
  procura	
  pela	
  próxima	
  sub-­‐cadeia	
  quando	
  encontra	
  um	
  dígito	
  ‘1’.	
  	
  
y1t	
   y2t	
  
xt	
   z1t	
  0	
   1	
  0	
   0	
   11	
   11	
   0	
  0	
   1	
   10	
   00	
   1	
  1	
   1	
   10	
   10	
   0	
  1	
   0	
   01	
   01	
   0	
  	
   	
   y1t+1y2t+1	
   	
  
y1	
   y2	
   Estado	
  
(S)	
  0	
   0	
   A	
  0	
   1	
   B	
  1	
   1	
   C	
  1	
   0	
   D	
  	
  
	
   	
   xt	
   	
   z1t	
  	
   	
   0	
   1	
   	
  	
   A	
   A	
   B	
   1	
  st	
   B	
   C	
   C	
   1	
  	
   C	
   D	
   D	
   0	
  	
   D	
   A	
   B	
   0	
  	
   	
   st+1	
   	
   	
  	
  
St	
   x
t	
   z1t	
  0	
   1	
  A	
   C	
   C	
   0	
  B	
   D	
   A	
   1	
  C	
   D	
   D	
   0	
  D	
   B	
   B	
   0	
  	
   	
   St	
  +	
  1	
   	
  	
  
	
  	
  	
  C	
  	
  	
  	
  (0)	
  
	
  	
  	
  A	
  	
  	
  	
  (0)	
  
	
  	
  	
  D	
  	
  	
  	
  (0)	
   	
  	
  	
  B	
  	
  	
  	
  (1)	
  
1	
  	
   0	
  1	
   1	
  0	
  
1	
  0	
  	
  
0