Redução de Estados em Digital Design-Técnicas de Minimização de Estados

Digital Design Copyright 2006 Frank Vahid 29 Redução de Estados Minimização de Estados 63 x y if x 1100 then y 01100 Objetivo Reduzir o número de estados de uma FSM sem modificar o seu comportamento sequencial Menos estados implica em se ter registradores menores menos FF Considere as duas FSMs abaixo x state y x state y S0 S0 S1 S1 S1 S1 S2 S0 S2 S0 S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Entrada x Saída y S0 S1 y0 y1 x x x x Para a mesma sequencia de entradas a Saída das duas FSM é a mesma a Digital Design Copyright 2006 Frank Vahid 30 Redução de Estados Estados Equivalentes Dois estados são equivalentes se 1 Eles fazem que as saídas vão para um mesmo valor lógico Ex S0 e S2 ambas fazem que y vá para 0 S1 e S3 ambas fazem que y vá para 1 2 E para todas as sequencias possíveis de entradas as saídas da FSM serão as mesmas começando de qualquer estado Ex suponha x1100 Começando de S1 y1100 Começando de S3 y1100 S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Inputs x Outputs y Estados S0 e S2 são equivalentes Estados S1 e S3 são equivalentes S0 S2 S1 S3 y0 y1 x x x x a Digital Design Copyright 2006 Frank Vahid 31 Redução de Estados Exemplo sem Estados Equivalentes Outro exemplo Estado S0 não é equivalente a nenhum outro estado pois sua saída y0 difere da saída dos demais estados S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Entrada x Saída y S0 Observe o exemplo de S1 e S3 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x S0 Começando de S1 x0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x S0 Começando de S3 x0 Saída inicialmente é a mesma y1 De S1 quando x0 vá para S2 onde y1 De S3 quando x0 vá para S0 onde y0 As saídas diferem Logo S1 e S3 não são equivalentes a Digital Design Copyright 2006 Frank Vahid 32 Redução de estados feita de forma visual por inspeção como fizemos nos slides anteriores não é um método confiável e não pode ser automatizada Uma técnica sistemática é normalmente usada tabelas de implicação Exemplo Redução de Estados com Tabelas de Implicação S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Entrada x Saída y Redundantes Diagonal S0 S0 S1 S2 S3 S1 S2 S3 Para comparar cada par de estados construimos uma tabela de pares de estados mostrada acima a direita Removemos pares de estados redundantes e os estados ao longo da diagonal pois cada estado da diagonal é equivalente a si mesmo S0 S0 S1 S2 S3 S1 S2 S3 S0 S1 S2 S1 S2 S3 Digital Design Copyright 2006 Frank Vahid 33 Marque com um X como sendo não equivalentes os pares de estado que têm saídas diferentes Redução de Estados com Tabelas de Implicação S0 S1 S2 S1 S2 S3 S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Inputs x Outputs y S1S0 Em S1 y1 e em S0 y0 Logo S1 e S0 são não equivalentes S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Inputs x Outputs y S2 S0 Em S2 y0 e em S0 y0 Logo não marcamos S2 e S0 por enquanto S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Inputs x Outputs y S2 S1 Não equivalentes S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Inputs x Outputs y S3 S0 Não equivalentes S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Inputs x Outputs y S3 S1 Não marque S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Inputs x Outputs y S3 S2 Não equivalentes S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Inputs x Outputs y Podemos observar que S2 S0 são possíveis candidatos a equivalencia e que S3 S1 também são mas somente se seus próximos estados forem equivalentes lembre do exemplo mostrado dois slides atrás S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Inputs x Outputs y a Digital Design Copyright 2006 Frank Vahid 34 Redução de Estados com Tabelas de Implicação Necessitamos checar os próximos estados que correspondem aos mesmos valores de estado para cada par de estados sem marca na tabela Podemos começar por listar para cada casa sem marca os próximos estados que os mesmos vão para cada combinação de entradas S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Entrada x Saída y S0 S1 S2 S1 S2 S3 S2 S0 Em S2 quando x1 vai para S3 Em S0 quando x1 vai para S1 S3 S1 Logo incluimos S3 S1 como um próximo par de estados Em S2 quando x0 vai para S2 Em S0 quando x0 vai para S0 S2 S0 Logo incluimos S2 S0 como próximo par de estados S3 S1 S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 De forma equivalente geramos como próximos pares de estados S3 S1 e S0 S2 S3 S1 S0 S2 S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 S3 S1 S0 S2 a Digital Design Copyright 2006 Frank Vahid 35 S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 S3 S1 S0 S2 Redução de Estados com Tabelas de Implicação Em seguida verifique par a par os próximos estados de cada casa sem marcação Marcaremos o par de estados se um dos seus próximos estados estiver marcado S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Entrada x Saída y S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 S3 S1 S0 S2 S2 S0 Continuamos Par de próximos estados S3 S1 não tem marca S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 S3 S1 S0 S2 Par de próximos estados S2 S0 não tem marca S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 S3 S1 S0 S2 S3 S1 S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 S3 S1 S0 S2 Par de próximos estados S3 S1 não tem marca S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 S3 S1 S0 S2 Par de próximos estadosS0 S2 não tem marca S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 S3 S1 S0 S2 Não marcamos nada e continuamos S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 S3 S1 S0 S2 Digital Design Copyright 2006 Frank Vahid 36 Redução de Estados com Tabelas de Implicação Acabamos de fazer uma passagem através da tabela implicação Faça novas passagens até que nenhuma mudança ocorra Em seguida mescle os pares de estado desmarcados eles são considerados equivalentes S0 S1 y0 y1 S2 y0 S3 y1 x x x x x x x x Entrada x Saida y S0 S1 S2 S1 S2 S3 S3 S1 S2 S0 S3 S1 S0 S2 S0S2 S1S3 y0 y1 x x x x Digital Design Copyright 2006 Frank Vahid 37 Redução de Estados com Tabelas de Implicação Digital Design Copyright 2006 Frank Vahid 38 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S0 S1 S2 S1 S2 S3 Exemplo de Redução de Estados em FSMs Dada a FSM a direita Passo 1 Marque como sendo não equivalentes os pares de estados que têm saídas diferentes S0 S1 S2 S1 S2 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S0 S1 S2 S1 S2 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S0 S1 S2 S1 S2 S3 S0 S1 S2 S1 S2 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S0 S1 S2 S1 S2 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S0 S1 S2 S1 S2 S3 S0 S1 S2 S1 S2 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Entrada x Saída y a Digital Design Copyright 2006 Frank Vahid 39 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S0 S1 S2 S1 S2 S3 Exemplo de Redução de Estados em FSMs Dada a FSM a direita Passo 1 Marque como sendo não equivalentes os pares de estados que têm saídas diferentes Passo 2 Para cada par de estados não marcado escreva os pares de próximos estados que correspondem aos mesmos valores de entrada S0 S1 S2 S1 S2 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y x0 S2 S2 x x x1 S2 S2 S0 S1 S2 S1 S2 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y x x S3 S1 x0 S2 S2 S0 S1 S2 S1 S2 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S3 S1 x x S0 S2 x1 S0 S1 S2 S1 S2 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S0 S2 x x S3 S1 x0 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S2 S2 S0 S1 S2 S1 S2 S3 S3 S1 S0 S2 S3 S1 x x S0 S2 x1 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Inputs x Outputs y S2 S2 S0 S1 S2 S1 S2 S3 S3 S1 S0 S2 S3 S1 S0 S2 x x S3 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Entrada x Saída y S2 S2 S0 S1 S2 S1 S2 S3 S3 S1 S0 S2 S3 S1 S0 S2 S3 S3 a Digital Design Copyright 2006 Frank Vahid 40 Exemplo de Redução de Estados em FSMs Dada a FSM a direita Passo 1 Marque como sendo não equivalentes os pares de estados que têm saídas diferentes Passo 2 Para cada par de estados não marcado escreva os pares de próximos estados que correspondem aos mesmos valores de entrada Passo 3 Para cada par de estados não marcado assinale como não equivalente os pares estados cujos pares de próximos estados não são equivalentes Repita isso até que não ocorram mais alterações ou até que todos estados estejam marcados Passo 4 Combine os pares restantes de estados Todos os pares estão marcados não existem mais pares de estados equivalentes a serem combinados S2 S2 S0 S1 S2 S1 S2 S3 S3 S1 S0 S2 S3 S1 S0 S2 S3 S3 S0 S1 y0 y1 S2 y1 S3 y1 x x x x x x x x Entrada x Saída y a Outro Exemplo de Redução de Estados com Tabelas de Implicação Passo 1 Marque como sendo não equivalentes os pares de estados que têm saídas diferentes Passo 2 Para cada par de estados não marcado escreva os pares de próximos estados que correspondem aos mesmos valores de entrada Passo 3 Para cada par de estados não marcado assinale como não equivalente os pares estados cujos pares de próximos estados não são equivalentes Repita isso até que não ocorram mais alterações ou até que todos estados estejam marcados Passo 4 Combine os pares restantes de estados Digital Design Copyright 2006 Frank Vahid 41 Outro Exemplo de Redução de Estados com Tabelas de Implicação cont Passo 1 Marque como sendo não equivalentes os pares de estados que têm saídas diferentes Passo 2 Para cada par de estados não marcado escreva os pares de próximos estados que correspondem aos mesmos valores de entrada Passo 3 Para cada par de estados não marcado assinale como não equivalente os pares estados cujos pares de próximos estados não são equivalentes Repita isso até que não ocorram mais alterações ou até que todos estados estejam marcados Passo 4 Combine os pares restantes de estados Digital Design Copyright 2006 Frank Vahid 42 Automação do Processo de Redução de Estados Exemplo onde a automação desse processso é necessária A tabela para uma FSM grande fica enorme para se minimizar dessa forma n entradas cada para de estado pode ter 2n pares de próximos estados 4 entradas 2416 pares de próximos estados 100 estados gerariam uma tabela com 100100100000 células O processo de redução de estados é automatizado computador Heurísticas são adotadas para reduzir o tempo computacional Digital Design Copyright 2006 Frank Vahid 43 Codificação de Estados Codificação de Estados Atribuir uma única combinação de bits a um único estado Codificações distintas podem produzir FSM menores ou mais rápidas Vejamos o caso do Temporizador de laser que fica ativo por 3 Ciclos Exemplo de codificação que usamos na seção 37 produzia 15 entradasportas lógica Tente outra forma de codificação x s1 s0 n1 s0 n0 s1b s1s0 Somente 8 entradasporta lógica Digital Design Copyright 2006 Frank Vahid 44 Codificação de Estados OneHot Encoding Onehot encoding Um bit por estado um bit igual a 1 corresponde a um único estado É um modo alternativo a codificação com número mínimo de bits slide anterior Para A B C D A 0001 B 0010 C 0100 D 1000 Exemplo FSM que produz como saída 0 1 1 1 Equações produzidas usandoonehot encoding n3 s2 n2 s1 n1 s0 x s3 s2 s1 Número menor de portas menor tempo de propagação possibilita CLK com maior frequência Digital Design Copyright 2006 Frank Vahid 45 Exemplo do Temporizador de Laser usando a técnica de OneHot Encoding Quatro estados Usaremos 4 bits para fazer onehot encoding Tabela de estados produzem as equações x s3 s2 s1 n3 s2 n2 s1 n1 s0b n0 s0b s3 Menor 300222 9 portasentrada Codificação binária 2 bits usada no cap 3 15 portasentrada Mais rápido Caminho crítico n0 s0b s3 Antes n0 s1s0b s1s0 Uma AND de 2 entradas é um pouco mais rápida que uma AND de 3 entradas Digital Design Copyright 2006 Frank Vahid 46 Digital Design Copyright 2006 Frank Vahid 47 Codificação das Saídas Output encoding Output encoding Método de codificação onde a codificação do estado segue a mesma codificação dos valores das saídas Possível se o número de saídas for suficientes para representar todos as combinações de estados com valores de combinações de saída única 00 01 Entrada nenhuma Saídas xy xy00 xy11 A B 11 10 D C xy01 xy10 Uso os valores das saídas para codificar os estados a Digital Design Copyright 2006 Frank Vahid 48 Exemplo de Output Encoding Gerador de Sequencias Gerador de sequencias 0001 0011 1110 1000 repete FSM mostrada ao lado Usaremos os valores das saídas para codificar os estados Montamos a tabela de transição de estados Obtemos as equações para os próximos estados circuito combinacional n3 s1 s2 n2 s1 n1 s1s0 n0 s1s0 s3s2 Entradas nenhuma Saídas w x y z wxyz0001 wxyz0011 A B D C wxyz1000 wxyz1100 clk n0 s3 s2 s1 s0 n1 n2 n3 State register wxy z Digital Design Copyright 2006 Frank Vahid 49 Arquiteturas Diferentes de FSMs FSM de Moore versus FSM de Mealy Formas diferentes de se implementar FSMs Arquiteturas diferentes de FSM Registrador Circuito combinacional Vista mais detalhada Lógica do próximo estado função do estado atual e das entradas da FSM Lógica da saída Se for só em função do estado atual Moore Se for função do estado atual e das entrada da FSM Mealy clk I O State register Combinational logic S N clk I O Stateregister Nextstate logic Output logic FSM outputs FSM inputs N S a clk I O State register Nextstate logic Output logic FSM outputs FSM inputs N S b Mealy FSM a dds thi s Moore Mealy x0 bx1 bx0 Entrada b Saída x S1 S0 Graficamente mostra saídas nos arcos não nos estados a Digital Design Copyright 2006 Frank Vahid 50 Mealy FSMs podem produzir menos estados Exemplo da máquina de refrigerantes Iniciar I Esperar até encher o copo W Retirar D Moore 3 estados Mealy 2 estados Moore Mealy Entrada enough bit Saída d clear bit Wait Disp Init enough enough d0 clear1 d1 Entrada enough bit Saída d clear bit Wait Init enough enoughd1 clk Inputs enough State Outputs clear d I I W W D a clk Inputs enough State Outputs clear d I I W W b d0 clear1 Digital Design Copyright 2006 Frank Vahid 51 Exemplo Mealy vs Moore Relógio de Pulso com Bip Botão b Ao pressionar gera uma sequencia de seleção das entradas de controle s1s0 de um MUX 41 00 01 10 e 11 Cada combinação mostra uma funcionalidade diferente do relógio no mostrador Cada pressionar gera um 1 bip de duração de 1 ciclo com p1 representando o bip Deve esperar o botão ser solto b e pressionado novamente b antes de passar para uma nova função Observe que a FSM de Moore demanda estados específicos para p1 enquanto que a FSM de Mealy faz isso nas transições Tradeoff Na FSM de Mealy p1 pode não durar um ciclo completo de clock Mealy Moore Entrada b Saída s1 s0 p Time Alarm Date Stpwch bs1s000 p0 bs1s000 p1 bs1s001 p1 bs1s010 p1 bs1s011 p1 bs1s001 p0 bs1s010 p0 bs1s011 p0 Entrada b Saída s1 s0 p Time S2 Alarm b b b b b b b s1s000 p0 s1s000 p1 s1s001 p0 s1s001 p1 s1s010 p0 s1s010 p1 s1s011 p0 s1s011 p1 S4 Date S6 Stpwch S8 b b b b Digital Design Copyright 2006 Frank Vahid 53 Tradeoff FSM de Mealy versus FSM Moore As saídas da FSM de Mealy mudam no meio do ciclo se as entradas mudam Observe o exemplo da máquina de refrigerantes Mealy possui um número menor de estados mas faz com que d não fique em 1 no ciclo completo Isso representa uma relação de compromisso tradeoff Moore Mealy Entrada enough bit Saída d clear bit Wait Disp Init enough enough d0 clear1 d1 Entradas enough bit Saída d clear bit Wait Init enough enoughd1 clk Entrada enough State Saída clear d I I W W D a clk Entrada enough State Saída clear d I I W W b d0 clear1 Digital Design Copyright 2006 Frank Vahid 54 Implementando uma FSM Mealy Modo direto Converta em uma tabela de estados Escreva as equações para cada saída Diferença principal para a FSM de Moore Saídas externas d clear podem assumir valores lógicos diferentes no mesmo estado dependendo dos valores das entradas Entradas enough bit Saídas d clear bit Wait Init enoughd0 enoughd1 d0 clear1