Circuitos Sequenciais Máquinas Síncronas Ou de Estados Finitos - Circuitos Elétricos 2 2021-2

Faculdade de Engenharia de Ilha Solteira – Departamento de Engenharia Elétrica Circuitos Digitais II –Profa Suely Cunha Amaro Mantovani. – 2osem/2021 Circuitos Sequenciais Máquinas Síncronas ou de Estados Finitos Sumário 1. Introdução 1.1 Circuitos Combinacionais 1.2 Circuitos Sequenciais 2. Considerações sobre Máquinas Síncronas 3. Tipos de Máquinas Sequenciais 4. Considerações sobre Máquinas Assíncronas 5. Procedimento de Projeto 6. Análise de Circuitos Sequenciais 6.1 Exercícios 7. Representando Circuitos Sequenciais por Diagrama de estados. 8. Síntese de Projeto de Circuitos Sequenciais 9. Máquinas Sequenciais de Moore e Mealy 9.1 Exercícios 10. Seleção das Variáveis de Estado (Atribuição de Estados) 11. Eliminação (ou Simplificação) de Estados Redundantes em FSM ( Finite State Machine ou autômatos finitos) Bibliografia 2 1. Introdução Quando se estuda a teoria de circuitos sequenciais é importante lembrar que existem dois tipos de circuitos em sistemas digitais: os combinacionais e os sequenciais definem-se os dois para saber a diferença. 1.1 Circuitos Combinacionais As saídas são determinadas pelas entradas das portas: não dependem dos estados anteriores destas entradas;  Quando as entradas variam, as variações estarão disponíveis na saída por um breve intervalo de tempo, limitado pelo retardo de propagação finito do sinal através das portas;  Não há realimentação entre as entradas e saídas, Figura 1. Ex: Full-adder, Mux, decoder, etc. Figura 1- Diagrama de Bloco para o Circuito Combinacional 1.2 Circuitos Sequenciais Em um circuito lógico sequencial as saídas das portas não dependem apenas das entradas presentes, mas também da história das entradas no passado. Em outras palavras, o comportamento das variáveis de saída depende tanto dos valores das variáveis de entradas presentes, quanto do estado interno atual do sistema, Figura 2.  As saídas dependem das entradas presentes e das histórias das entradas no passado: 3  Cada estágio de um circuito sequencial é chamado de ESTADO. Em cada estado o circuito armazena uma recordação de sua história passada, de modo a seguir o próximo passo.  Tem realimentação. Ex: latch estático, contadores de módulo, caixa eletrônico, microcomputador , etc. Figura 2- Modelo Geral ou Diagrama de Blocos para um Circuito Sequencial ou Máquina Sequencial. sendo, x1,...xn – entradas; z1,...zm – saídas; Y1,...Yp - variáveis de excitação; y1,...yk - variáveis de estado. zi = fi (x1,x2,...,xn,y1,y2,...,yk), i=1,2,...,m e Yj= Fj (x1,x2,...,xn,y1,y2,...,yk), j=1,2,...,p Outros exemplos: Sejam dois modelos de TV: Modelo 1: o seletor é composto por um conjunto de chaves, uma por canal, onde apenas uma está ativa a cada instante, Figura 3(a) ; 4 Figura 3. (a) Modelo de TV com chave de canal combinacional. (b) Modelo de TV (controle remoto) com chave de canal sequencial. (a) (b) odelo 2 : Figura 3 (b), tem-se duas chaves "push-bottom" (chave "UP" e chave "DOWN") por meio das quais, seleciona-se um canal imediatamente acima, ou imediatamente abaixo do atual, caso seja dado um toque no botão "UP" ou no botão"DOWN", respectivamente. No aparelho de TV que usa o primeiro modelo, para trocar de canal, basta pressionar a chave correspondente ao canal desejado que a saída do vídeo passa a mostrar o novo sinal. No segundo modelo, para acionar outro canal, não imediatamente acima ou abaixo, é necessário saber qual o atual, para por meio de toques sucessivos no "push-botton DOWN" ou "push-botton UP", chegar-se ao desejado. No primeiro caso, o aparelho de TV se comporta como um circuito lógico combinacional - a saída é função única da entrada aplicada. No segundo caso, a TV se comporta como um circuito lógico sequencial - a saída depende do sinal aplicado associado ao estado atual do seletor. 2. Considerações sobre Máquinas Síncronas Se os elementos que definem o estado do circuito são memórias com capacidade de sincronização (serem alteradas exatamente ao mesmo tempo), o circuito é dito síncrono.  O valor contido em cada elemento de memória é chamado variável de estado;  O conjunto (y1, y2,...,yk) constitui o conjunto das variáveis de estado; 5  Os valores contidos nos k elementos de memória definem o estado interno atual da máquina;  Então k variáveis de estados corresponderá a 2k estados;  Y define o próximo estado da máquina. Aparece na saída do circuito combinacional no instante t, determina os valores das variáveis de estado no instante t+1;  Todas as linhas de entrada e saída da seção L.C. são sinais de níveis, ou seja, podem permanecer em „1‟ ou „0‟, para um período de tempo arbitrário;  Como a seção L.C. independe do tempo, a saída pode mudar a qualquer momento, desde que mude a entrada x;  As mudanças na memória (FFs) causadas por mudanças das entradas, somente ocorrerão caso exista um pulso de clock;  Durante o pulso de clock as variáveis de excitação (Y) devem permanecer estáveis;  A máquina M pode ter uma variedade infinita de passados possíveis , mas neste tópico considera-se as máquinas, cujo passado pode ser resumido em um conjunto finito de variáveis. Os circuitos sequenciais síncronos são os de mais fácil execução. Nestes circuitos as variáveis de entrada (internas ou externas) podem variar simultaneamente. O circuito só faz uma mudança de estado, cada vez que o clock (elemento de sincronismo das memórias) é ativado. A transição é um conjunto de ações a serem executadas quando uma condição for cumprida ou quando um evento é recebido. Indica uma mudança de estado e é descrita por uma condição que precisa ser realizada para que ocorra a transição. Uma ação é a descrição de uma atividade que deve ser realizada num determinado momento. Máquinas de estados são utilizadas para descrever circuitos sequenciais. Uma máquina de estado costuma ser usada para controlar o evento, diferentemente de um contador que conta eventos. A máquina está em apenas um estado por vez, este estado é chamado de estado atual. Um estado armazena informações sobre o passado, isto é, ele reflete as mudanças desde a entrada em um estado, no início do sistema, até o momento presente. 6 3. Tipos de Máquinas Sequenciais As máquinas sequenciais podem ser síncronas ou assíncronas: Síncronas - todos os FFs são comandados pela mesma forma de onda de sincronização; Assíncronas - não têm sincronismo de relógio, também chamados de circuitos sequenciais no Modo Fundamental, Modo Assíncrono ou Modo Nível. 4. Considerações sobre Máquinas Assíncronas  Os “retardos” representam os retardos distribuídos dos elementos combinacionais concentrados em um único elemento;  A cada variável realimentada tem-se um “retardo” associado;  Cada “retardo” pode ser encarado como um elemento de memória, Figura 4; Figura 4- Diagrama de blocos para o circuito sequencial assíncrono. para yi(t+1) = Yi(t) , com i=1,2,...,r Se forem usados atrasos ou memórias sem capacidade de sincronização, o circuito é assíncrono. Estes circuitos têm resposta mais rápida, mas de muito difícil execução, sobretudo se o número de variáveis de memória é elevado. Apenas uma variável, interna ou externa, pode ser alterada de cada vez (veja análise da tabela de transição para o latch estático, Figura 5). O atraso que se apresenta é o atraso de propagação das portas. Desta forma, os circuitos sequenciais assíncronos têm sido evitados, sempre que possível, em favor do uso de circuitos sequenciais síncronos. Mostra-se a seguir, uma análise para um circuito sequencial assíncrono, Figura 5, para um latch estático. 7 Figura 5- (a) Circuito sequencial assíncrono e em (b) Tabela de transição. (a) A tabela de transição para o circuito Y (b) Na tabela de transição o círculo representa os estados estáveis, sendo que Y=y , o que quer dizer que o estado seguinte é igual ao estado presente. 5. Procedimentos de Projeto Para os circuitos sequenciais síncronos existem dois modos de trabalho: análise e síntese. Na Análise: 1) Circuito. 2) Equações de saída e equações dos FFs. 3) Equações dos Próximos Estados. 4) Tabela de Transição. 5) Tabela de Estados. 6) Diagrama de Estados. Na Síntese: 1) Descrição do problema. 2) Diagrama de Estados. 3) Tabela de Estados (Simplificação dos Estados). 4) Tabela de Transição. 5) Equações dos elementos de memória (escolha dos FFs). 6) Equações de excitação dos FFs e saídas. 7) Esquema do Circuito. 6. Análise de Circuitos Sequenciais. Um exemplo de análise de uma Máquina Sequencial ou FSM- Finite State Machine, Figura 6. 8 Figura 6- Exemplo de Máquina Sequencial. 10 Achar as equações das saídas e de entradas dos FFs J1 = x J0 = (x + y1).y0‟ K1 = x‟ K0 = ((x + y1).y0‟)‟ z = (x + y1).y0‟, z=g(x,y) e J , K são f(x,y) 20 Equações dos próximos Estados Equação do próximo estado para o flip-flop JK: Q t+1 = J. (Qt)‟ + K‟. Qt (equação característica)  p/ o FF1 => y1 t+1 = J1 . (y1 t)‟ + K1 ‟ . y1 t y1 t+1 = x . (y1)‟ + x . y1 y1 t+1 = x  p/ o FF0 => y0 t+1 = J0 . (y0 t)‟ + K0 ‟. y0 t y0 t+1 = [(x+ y1).(y0)‟].(y0)‟ + [(x + y1).(y0)‟].(y0) 9 y0 t+1 = (x + y1).(y0)‟ zt+1 = (x + y1 t).(y0 t)‟ 30 Tabela de Transição 40 Tabela de Estados e Diagrama de Estados 10 6.1 Exercícios 1- Levantar as equações características dos seguintes flip-flops: SR, T, JK e D 2- Fazer a análise dos circuitos sequenciais a seguir: a) b) 7. Representando Circuitos Sequenciais por Diagrama de estados. O comportamento de um circuito sequencial latch RS, pode ser expresso por meio de diagrama de estados, conforme mostrado na Figura 7. 11 Figura 7- Diagrama de estados para o latch RS Neste diagrama os estados reset e set estão representados por nodos (círculos). A transição entre estados é mostrada por uma aresta (seta). A condição de entradas segundo a qual uma determinada transição pode ocorrer está definida junto a aresta respectiva. Por exemplo, estando o latch RS no estado reset, para que ele vá para o estado set é necessário que R=0 e S=1. Caso R=0 e S=0, o latch RS ficará no estado em que se encontra. O símbolo completo do latch RS, é mostrado na Figura 8. Figura 8 - Símbolo do latch RS. 12 8. Síntese de Projeto de Circuitos Sequenciais Vários contadores estão disponíveis em CIs que são assíncronos, síncronos e combinados assíncrono/síncrono. Sendo que a maioria deles conta na sequência normal, embora esta sequência possa ser alterada, ex: CI 74293, 74193, 74192. Mas, algumas vezes podemos necessitar de contadores com sequências que nenhum CI contador pode oferecer ex. 0, 2,4,1,..... Existem alguns métodos para projetar estes contadores que seguem sequências arbitrárias. Apresentam-se aqui, um método usual seguindo os passos já mencionados para a síntese, detalhados a seguir: 1-Definir a sequência de operações através da qual o sistema deve progredir, ou seja, verificar saídas geradas e cada etapa na sequência. A partir disso, construir um diagrama de fluxo e/ou diagrama de estados de memória; 2- Determinar o número necessário de ffs. Se o número de estados estiver na faixa de 2n-11 a 2n serão necessários n ffs. Uma atribuição de estado deve ser feita associando cada estado do diagrama de estados a um estado do ff. Pode haver mais estados dos ffs do que estados de memória; 3- Com a atribuição de estado construímos uma tabela de transição. Depois se escolhe o ff (D, JK, etc.) arbitrariamente, que pode ser determinado pela disponibilidade; 4- Obtenção das equações lógicas de excitação dos terminais de entrada de dados dos ffs a partir da tabela de estados; 5- Por fim, desenhar o circuito usando portas lógicas discretas ou a realização das equações diretamente nos dispositivos lógicos programáveis. Exemplo 1- Contador módulo 5 13 Tabela de transição do circuito Estado Atual Próximo Estado Ct Bt At Ct+1 Bt+1 At+1 JC KC JB KB JA KA 0 0 0 0 0 1 0 x 0 x 1 x 0 0 1 0 1 0 0 x 1 x x 1 0 1 0 0 1 1 0 x x 0 1 x 0 1 1 1 0 0 1 x x 1 x 1 1 0 0 0 0 0 x 1 0 x 0 x 1 0 1 0 0 0 x 1 0 x x 1 1 1 0 0 0 0 x 1 x 1 0 x 1 1 1 0 0 0 x 1 x 1 x 1 Tabela de transição do JK Tabela Verdade JK J K Qt Qt+1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 Obs: As saídas do circuito contador se confundem com as saídas dos ffs. Mapa de Karnaugh para encontrar as equações dos FF: QCQB QA 00 01 11 10 0 1 1 0 0 1 x x x x QCQB QA 00 01 11 10 0 x x x x 1 1 1 1 1 Ja= Qc‟ Ka=1 Se escolhermos o FF – JK para a realização do circuito, são necessários 3 FFs ( 8 estados diferentes ). Resolvendo para a tabela de transição com o FF escolhido, têm-se as seguintes equações para os FF-JCKC, JBKB e JAKA: JA=QC‟, KA=1; JB= QA.QC‟, KB= QA+QC, JC =QA.QB, KC=1 (fazer e conferir o resultado). 14 2- Contador de módulo 4 incrementador/decrementador. Este contador tem um terminal M de controle do modo de entrada: M Modo de entrada 0 Conta na direção inversa: 0,3,2,1,0,3,.... 1 Conta na direção direta: 0,1,2,3,0,1,2,.... Figura 9-Diagrama de Estado Realizar este exercício com o FF-D sabendo que a tabela verdade para o FF-D é: D Qt Qt+1 0 0 0 0 1 0 1 0 1 1 1 1 Baseada na tabela do FF-D podemos achar a tabela de transição do FF-D: Qt Qt+1 D 0 0 0 0 1 1 1 0 0 1 1 1 O que se conclui que o D assume o próximo estado, Qt+1. Tendo essas informações, acha-se o circuito para o contador módulo 4 incrementador /decrementador. 15 Tabela de transição do circuito EA (PS) Q1 t Q0 t PE (NS) Q1 t+1 Q0 t+1 M D1 D0 completar??? 0 1 0 0 11 01 0 0 1 00 10 1 1 0 01 11 0 1 1 10 00 1 3-Projetar um sistema de modo que Z=1 quando e somente quando X=1 durante 3 ou mais intervalos de clocks consecutivos ( supor que o nível Z lógico de saída depende apenas do estado da máquina). (explicado em classe). Fazer com o FF-T Tabela de Estados EA (PS) Q1 t Q0 t PE (NS) Q1 t+1 Q0 t+1 X Z 0 1 A A B 0 B A C 0 C A D 0 D A D 1 16 Tabela de Transição EA (PS) Q1 t Q0 t PE (NS) Q1 t+1 Q0 t+1 X Z T1 T0 0 1 0 0 00 01 0 0 1 00 C 0 1 0 00 D 0 1 1 00 D 1 9. Máquinas Sequenciais de Moore e Mealy No último exemplo vimos que o circuito sequencial tinha a saída como função apenas do estado do sistema: saída=f(estados) Isso implica que o valor de uma entrada no ciclo k de relógio não pode afetar a saída até no mais próximo, ciclo k+1. As mudanças na entrada devem ter uma influência no estado do sistema, antes que possam afetar a saída.  Um circuito sequencial em que as saídas são funções apenas do estado presente são referenciados como Máquinas de Estados de Moore, saída = g (estado atual). Para Moore o simbolismo é: Z é introduzido no círculo que representa o estado, pois Z= f (y). As máquinas de Moore podem ser representadas por diagramas de estados onde um círculo representa o estado atual, e uma seta representa a transição entre dois estados (atual e futuro). Neste caso, dentro de cada círculo, que representa o estado, coloca-se uma letra ou número que identifique o estado e o valor das saídas correspondentes a este estado, e em cada flecha que representa uma transição, coloca-se o valor das entradas do circuito. 17  Um circuito sequencial em que as saídas são funções tanto do estado atual quanto das entradas é chamado Máquina de Estados de Mealy, saída= f(estado atual, X) Para Mealy – o simbolismo X/Z, pois Z=f(y, X) As máquinas de Mealy podem ser representadas por diagramas de estados onde um círculo representa o estado atual, e uma seta representa a transição entre dois estados (atual e futuro). Neste caso dentro de cada círculo que representa o estado, coloca-se uma letra ou número que identifique o estado, e em cada flecha, que representa uma transição, coloca-se o valor das entradas e das saídas. Com estas máquinas sequenciais síncronas é possível fazer contadores de qualquer sequência, inclusive contadores tipo “up/down”, que contam incrementando ou decrementando, neste tipo de contador uma entrada indica o sentido correto de contagem. Portanto, a diferença entre os dois modelos de máquinas está na forma em que as saídas são geradas (Figuras 10 e 11). Figura 10- Diagrama de blocos - Máquina de Moore Figura 11-Diagrama de blocos - Máquina de Mealy 18 Resumindo: As representações podem ser transformadas de uma para a outra. Tem-se na Tabela 1 um resumo de suas desvantagens/vantagens. Tabela 1- Vantagens e desvantagens Mealy Moore glitches (ruídos) sem glitches problemas de amostragem mais fácil de projetar menor número total de estados Projeto do detector anterior segundo a concepção de Mealy Exemplo 4: Projetar um circuito que no intervalo k de relógio forneça uma saída Z=1 sempre que, levando em conta o valor de X no intervalo k, houver uma sequência de 3 ou mais valores sucessivos X=1. X=0000111 Z=0000001 Portanto, a versão Mealy de um circuito sequencial é mais econômica de componentes físicos (hardware) do que a versão Moore. Geralmente é o caso, embora nem sempre. Se não houver nenhuma linha de entrada, a tabela de estados para o sistema terá apenas uma única coluna no estado seguinte:  Uma entrada X gera 2 colunas no estado seguinte. Generalizando, n entradas X geram 2n colunas no estado seguinte. Ex: 5 entradas geram 25 = 32 colunas no estado seguinte. Em outras palavras, desde que haja somente uma entrada na máquina de estado, há somente 2 possíveis combinações de entrada e 2 setas deixando cada estado. Em uma 19 máquina com n entradas , tem-se 2n setas deixando cada estado. Na Figura 12, mostra-se o diagrama de estados a) por Moore e b) por Mealy do detector de 3 uns consecutivos. Diagrama de Estados Fig. 12 - Diagrama de estados. a) por Moore e b) por Mealy Claramente observa-se pelos diagramas de estados que por Mealy é possível obtermos uma redução no número de estados, porém em alguns casos a característica assíncrona das saídas Mealy pode trazer problemas. Nas tabelas a seguir são mostrados os estados para ambos os diagramas anteriormente representados. Tabela de Estados (a) Tabela de Estados para Moore (b) Tabela de Estados para Mealy 20 Tabela de Transição Para construirmos a tabela de transição basta substituirmos os nomes dos estados pelas combinações escolhidas ou atribuição de estados, para as variáveis de estados como mostram as tabelas a) e b) a seguir. (a) Máquina de Moore EA PE Z X = 0 X = 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 (b) Máquina de Mealy(incompleta) Fazer a escolha do FF, por exemplo, pode ser o JK, minimizar usando Mapa de Karnaugh, em seguida desenhar o circuito. Projeto Intuitivo Projetar heuristicamente e montar um circuito que detecte a sequência 10010, ou seja, a saída só vai ser „1‟ para essa sequência de entrada, Figura 13. Figura 13- Projeto heurístico de um detector de sequencias 10. Seleção das Variáveis de Estados (Atribuição de Estados) A seleção das variáveis de estados consiste em determinar o código binário de cada estado que será formado pelas saídas dos flip-flops. Se em um exemplo têm-se quatro estados, 2 flip-flops são necessários para que sejam representados todos os estados, pois haverá 2n combinações possíveis (onde n é o número de flip-flops). 21 Dependendo da conveniência, pode-se selecionar outro tipo de código para os estados, utilizando mais flip-flops, isto resultará em um número menor de portas para gerar os sinais de excitação dos flip-flops (equação de excitação menor). Na tabela a seguir, Tabela 2 mostram-se alguns códigos usuais, onde o projetista deve escolher conforme a necessidade e aplicação. Tabela 2- Códigos de Atribuição de Estados Nos códigos da terceira e quarta coluna da tabela, observa-se que exigem um número maior de flip-flops que o mínimo expressado na segunda coluna, porém resultam em um número menor de portas lógicas para construir as equações de excitação. A diferença entre os códigos ONE-HOT E QUASE ONE-HOT está no estado inicial “A”, pois a inicialização do sistema é facilmente obtida por meio de entradas diretas de clear (000) e preset (111) dos flip-flops. Nos casos em que o número de estados é menor que o número de combinações possíveis das saídas dos 2n flip-flops existirão estados não usados (ou ilegais). Quando isso ocorre, existem duas aproximações ou técnicas:  Mínimo risco - Esta aproximação assume que o sistema pode ir para um estado ilegal por motivo qualquer (falha no hardware, ou uma entrada inesperada, ou erro no projeto). Então, todas as combinações não usadas são identificadas e se alguma destas ocorrer, imediatamente o sistema será levado ao estado inicial ou qualquer estado de segurança.  Mínimo custo – Esta aproximação assume que a máquina de estados jamais encontrará um estado ilegal, com isto as combinações não usadas podem ser indicadas como “don’t care” (X) na tabela de transição e assim resultando em simplificações nas equações de excitação. Por outro lado, caso um estado ilegal ocorra, um comportamento indefinido surgirá. 11. Eliminação (ou Simplificação) de Estados Redundantes em FSM ( Finite State Machine ou autômatos finitos) A primeira etapa no projeto de um sistema sequencial consiste em verificar os estados necessários para o projeto (realização do diagrama de estados). Na escolha dos estados podemos falhar ou acrescentar estados além do necessário. No primeiro caso, o sistema não vai funcionar, mas no segundo caso não vai haver prejuízo, pois existem procedimentos simples para eliminar os estados supérfluos (que estão sobrando). Portanto, quase sempre é possível realizar o sistema com uma máquina equivalente com menos estados. 22 Terminologias Máquina equivalente reproduz as mesmas saídas para as correspondentes mesmas entradas. Estados Redundantes ou equivalentes são estados atuais, cujas saídas Z atuais e os estados seguintes são idênticos, de modo que um estado pode ser eliminado. Esta teoria serve tanto para Moore quanto para Mealy. Métodos existentes para Redução de Estados  Redução por Inspeção  Redução por Partição  Redução por Carta de Implicação Consideremos a tabela de estados de um sistema Mealy: Próximo Estado /Saída X Estado Atual 0 1 . . . . . . p r/0 s/1 . . . . . . q r/0 s/1 . . . . . .  p e q => são estados atuais e r e s =>são estados seguintes;  p e q são redundantes ou equivalentes, pois para p ou q as saídas são as mesmas. Se X=0, p ou q levam para o próximo estado r. Se X=1, p ou q levam para o próximo estado s. 11.1 Redução por Inspeção - Procura-se na tabela de estados pelas saídas diferentes: saídas diferentes não podem constituir estados equivalentes; - Em seguida observam-se os estados equivalentes. Veja um exemplo: seja a seguinte tabela de estados: Próximo Estado /Saída X Estado Atual 0 1 A B/0 C/1 B C/0 A/1 C D/1 B/0 D C/0 A/1 E D/0 C/1 23  os estados “B” e “D” são idênticos. Neste caso, esta tabela pode ser reescrita substituindo-se a letra “D” pela letra “B”. E.A. P.E. P.E. - X=0 X=1 A B/0 C/1 B C/0 A/1 C B/1 B/0 E B/0 C/1  os estados “A” e “E” são idênticos (redundantes), portanto, elimina-se um deles. Tabela de estados reduzida: Próximo Estado /Saída X Estado Atual 0 1 A B/0 C/1 B C/0 A/1 C B/1 B/0 11.2 Carta de Implicação (Serve para o caso em que existam condições irrelevantes (ou não especificadas). Na carta de implicação monta-se uma espécie de mapa onde são anotadas todas as condições para que um estado seja igual ao outro. O mapa deve ter na primeira coluna e na última linha os estados da máquina. Na interseção de cada uma destas linhas e colunas são anotadas as condições para que estes estados sejam iguais. Aos poucos surgirão condições que não podem ser satisfeitas o que impede a igualdade de vários estados. Estas impossibilidades vão sendo marcadas até que não existam mais. Neste momento devem-se anotar quais destes estados têm condição de serem iguais:  A compatibilidade é indicada por uma marca de prova ( ) – significado: em cada coluna, ou as entradas são as mesmas, ou, se houver uma entrada numa coluna de uma linha, a mesma coluna da outra linha tem uma condição irrelevante;  São estabelecidas hipóteses;  Desigualdades são introduzidas como cruzes (X) na carta de implicação. O processo continua até que não sejam geradas novas desigualdades;  Uma classe compatível é um grupo de estados, cada um dos quais, sendo compatível com cada um dos outros no grupo;  Classe compatível é máxima quando não é possível achar quaisquer membros adicionais da classe. 24 Exemplo: Redução da tabela a seguir, por Carta de Implicação, para uma tabela de estados completamente especificada. Próximo Estado /Saída X Estado Atual 0 1 A B/0 C/0 B D/0 E/0 C G/0 E/0 D H/0 F/0 E G/0 A/0 F G/1 A/0 G D/0 C/0 H H/0 A/0 Carta de Implicação Para montar esta carta de implicação deve-se proceder da seguinte maneira:  Primeiro deve-se procurar pelas saídas diferentes na tabela e marcar com X na carta. 25  Na interseção de cada uma destas linhas e colunas são anotadas as condições para que estes estados sejam iguais  Desigualdades são introduzidas como cruzes (X) na carta de implicação e o processo continua até que não sejam geradas novas desigualdades; 26 Não havendo mais nada para simplificar pode-se dizer que todas as possibilidades (que não estão com X) representam estados iguais. Neste exemplo o estado “A” é igual ao estado “C” e ao estado “E” , pois a interseção entre a coluna “A” e as linhas “C” e “E” não foram marcadas com “X”. Da mesma forma pode-se afirmar que o estado “C” é igual ao estado “E”, o que já era de se esperar, pois “A” é igual a estes dois estados. Desta forma, pode-se montar uma tabela simplificada, se substituirmos os estados da tabela original por: Estados A, C e E serão representados por “a” Estados B e G serão representados por “b” Estado D será representado por “c” Estado F será representado por “d” Estado H será representado por “e” 27 A tabela original simplificada ao máximo: E.A. P.E. P.E. - X=0 X=1 a b/0 a/0 b c/0 a/0 c e/0 d/0 d b/1 a/0 e e/0 a/0 Exercício: 1) Eliminar os estados redundantes se houver, da seguinte tabela de estados. Construir a tabela de estado reduzida. Bibliografia TAUB, H. - Circuitos Digitais e Microprocessadores, 1a edição, São Paulo: McGraw-Hill do Brasil, 1984, 510p. TOCCI, R. J., WIDMER, N.S., MOSS, G.L. Sistemas Digitais, Princípios e Aplicações.10ª edição, Editora Pearson Prentice Hall, 2007, 940p.