Máquinas de estado em VHDL

Máquinas de estado são muito comuns pois, em sistemas digitais, todos os circuitos sequenciais podem ser vistos como uma máquina de estados finita. No entanto, especificá-las em VHDL é um desafio para os projetistas novatos devido aos problemas que surgem quando o tempo está envolvido. Circuitos combinatórios não dependem de tempo e não possuem memória, porém máquinas de estado possuem e precisam ser projetadas com o devido cuidado. Neste artigo mostrarei algumas formas seguras de especificar corretamente máquinas de estado finitas síncronas e determinísticas em VHDL.

Revisitando o conceito de máquinas de estado

O modelo base de qualquer máquina de estados em sistemas digitais pode ser visto na figura. É composto por um elemento de memória (S) e duas funções combinatórias, uma de transição de estados (T) e outra de saída (G). Quando a função de saída depende somente do estado (ausência da seta tracejada na figura), dizemos que a máquina segue o modelo de Moore. Ao contrário, quando a saída da máquina depende do estado e da entrada (presença da seta tracejada na figura), dizemos que a máquina segue o modelo de Mealy. Em ambos os casos, somente o elemento de memória é sequencial. As funções são puramente combinatórias e dependem somente da entrada (da função) para produzir a saída. Note que, apesar de dependerem apenas na sua entrada, ambas as funções recebem a saída do elemento combinatório como entrada.

Resumindo:

• T é combinatória, recebe o estado e a entrada e produz o próximo estado;
• G é combinatória, recebe o estado (Moore) ou o estado e a entrada (Mealy), e produz a saída;
• S é um elemento de memória que armazena o estado atual.

Descrevendo a FSM em VHDL usando Moore ou Mealy

Aqui parte-se do pressuposto que você desenhou o diagrama de transição de estados da sua máquina de estados, ela é finita e determinística. De fato, a grande maioria dos problemas sequenciais em sistemas digitais possuem a sua dificuldade no desenho do diagrama de transição e não na implementação. Em outras palavras, implementar uma máquina de estados em VHDL é relativamente simples, pois a parte difícil da solução do problema está imbuída no diagrama de transição.

Comece sua máquina de estados declarando a entidade e, consequentemente, a interface de entrada e saída da sua máquina de estados.

Na arquitetura, sempre teremos duas partes: a parte sequencial e a parte combinatória. O elemento de memória representa a parte sequencial da máquina de estado e portanto é sensível ao clock. Para implementá-lo dessa maneira, utiliza-se o process. Para detalhes sobre o uso correto do process, veja o artigo sobre circuitos síncronos. De fato, você não precisa usar process para mais nada em VHDL, exceto para a parte sequencial das máquinas de estado finitas. A parte combinatória é o que diferencia os estilos de codificação em VHDL, e neste artigo veremos duas formas, através de exemplos, portanto não deixe de lê-los e entendê-los.

Exemplo 1 (Moore)

A máquina que iremos implementar como exemplo é a máquina de Moore da figura ao lado. Contém apenas dois estados e todas as quatro transições possíveis totalmente especificadas. Comecemos pela declaração de uso das bibliotecas e pela entidade:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

library ieee;
use ieee.numeric_bit.rising_edge;

entity fsm is
  port(
    entrada: in bit;
    saida: out bit;
    clock, reset_n: in bit
  );
end fsm;

Na descrição da arquitetura, o que teremos de novidade é a utilização de um tipo composto definido pelo usuário. O tipo composto é uma enumeração e representa o conjunto S (todos os estados possíveis). Após declarado o tipo composto, é possível declarar sinais e variáveis deste tipo, então usaremos o tipo declarado para declarar a variável de estado, ou seja, o elemento de memória que armazenará o estado.

Exemplo 1 (Moore) - Estilo tradicional

Neste primeiro estilo de descrição, a arquitetura é descrita usando exatamente o modelo tradicional de máquina de estados, ou seja, o elemento de memória é sequencial (dentro do process) e as funções combinatórias (fora do process).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

architecture proccomb of fsm is
  type estado_t is (A,B);
  signal PE,EA : estado_t;
begin
  sincrono: process(clock, reset_n)
  begin
    if (reset_n='0') then
      EA <= A;
    elsif (rising_edge(clock)) then
      EA <= PE;
    end if;
  end process sincrono;
  PE <=
    A when entrada='0' and EA=A else
    B when entrada='1' and EA=A else
    B when entrada='0' and EA=B else
    A when entrada='1' and EA=B else
    A;
  saida <=
    '0' when EA=A else
    '1' when EA=B else
    '0';
end architecture proccomb;

Note que há somente um processo. O processo faz o reset assíncrono da máquina de estados, colocando-a no estado A (veja a seta de início chegando no estado A do diagrama de transição de estados). Caso o reset não esteja ativo, o processo faz uma única tarefa que é copiar o sinal PE (de Próximo Estado) para o sinal EA (de Estado Atual) na borda de subida do clock. Neste contexto, apenas o sinal EA representa um elemento combinatório pois fora destas duas condições, o sinal EA é mantido inalterado. O comportamento é exatamente o de um flip-flop tipo D e, de fato, podemos ver que o circuito gerado contém exatamente um flip-flop, pois temos somente dois estados possíveis. Caso o tipo composto estado_t possuísse mais de dois estados, o número de flip-flops seria maior para acomodar o maior número de estados.

Fora do processo, temos duas declarações concorrentes ao process, que representam as duas funções combinatórias. A primeira calcula o próximo estado (PE<=...) e a segunda calcula a saída (saida<=...).

Este estilo tem a vantagem de ser muito próximo do modelo tradicional de máquinas de estado. O processo síncrono é muito simples (será similar independentemente da máquina) e com pouco espaço para erros. A desvantagem é que este estilo se torna críptico rapidamente, pois a descrição combinatória das funções de transição e de próximo estado crescerão exponencialmente em complexidade e tamanho junto com a complexidade da máquina, tornando-se ilegíveis rapidamente.

Use esse estilo nas suas primeiras máquinas de estado, para garantir que você não terá problemas de sincronismo, ou se a máquina for muito simples ou com poucos estados.

Exemplo 1 (Moore) - Estilo com dois process

No segundo estilo, levamos a descrição combinatória para dentro de um process novo, mantendo o process sequencial que faz o papel de elemento de memória inalterado. Este estilo exige um cuidado muito grande pois estamos descrevendo um elemento combinatório dentro de uma primitiva de VHDL que indica para o sintetizador que estamos descrevendo algo sequencial. Temos que ser claros com a descrição para que o sintetizador entenda que a variável de estados é o sinal EA somente, e os outros sinais (neste caso o PE e a saida), são combinatórios.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

architecture doisproc of fsm is
  type estado_t is (A,B);
  signal PE,EA : estado_t;
begin

  sincrono: process(clock, reset_n, PE)
  begin
    if (reset_n='0') then
      EA <= A;
    elsif (rising_edge(clock)) then
      EA <= PE;
    end if;
  end process sincrono;

  combinatorio: process(EA, entrada)
  begin
    saida <= '0';
    case(EA) is
      when A =>
        saida <= '0';
        if entrada='1' then
          PE <= B;
        else
          PE <= A;
        end if;
      when B =>
        saida <= '1';
        if entrada='1' then
          PE <= A;
        else
          PE <= B;
        end if;
      when others =>
        saida <= '0';
        PE <= A;
    end case;
  end process combinatorio;

end architecture doisproc;

A vantagem desta abordagem é que temos acesso a estruturas sequenciais, como o case usado como decisor no processo combinatório, que facilitam a descrição comportamental de máquinas de estado. A desvantagem é que um pequeno deslize pode levar o sintetizador a registrar ou inferir latches para os sinais combinatórios, comprometendo a sequencialidade da máquina.

Note que o sinal PE foi incluído na lista de sensibilidade do processo sequencial, o que foi omitido no estilo anterior. A presença na lista de sensibilidade indica que PE pode mudar devido a fatores externos ao processo sequencial, e que o processo deve ser reavaliado se isto acontecer (mesmo que o resultado seja o mesmo pois não há borda nem reset). Já o processo combinatório depende de EA (obrigatório), fechando a cadeia de dependência entre os sinais dos processos (um ativa o outro). Esta ligação amplia as possibilidades de otimização do sintetizador pois ele entende que os dois processos são partes de um circuito único e os algoritmos de síntese foram preparados para otimizar esta situação (é um pouco mais complexo que isso, mas basta saber que é melhor assim). Note que o circuito gerado contém um multiplexador no lugar das portas lógicas.

Este exemplo é simples e há pouca diferença entre em manter o circuito combinatório isolado do sequencial (primeiro estilo), ou descrevê-los em conjunto usando dois processos interligados (segundo estilo). Em circuitos complexos as otimizações podem ser bem diferentes, quase sempre com vantagem para o estilo de descrição com dois processos.

Outro ponto importante é a ausência de sinais temporais no processo combinatório e a completude de todas as atribuições. Se esquecermos de uma atribuição para PE em qualquer um dos casos possíveis (incluindo a cláusula when others), a atribuição estará incompleta e o processo pode se tornar sequencial (e nesse caso assíncrono ainda por cima), fazendo com que a descrição não se comporte como o esperado.

Aconselha-se a utilização deste tipo de descrição quando você estiver habituado a descrever máquinas de estados em VHDL e confortável em encontrar problemas de sincronismo.

Se você tem uma bagagem como programador de software, é natural optar por este estilo pois é muito parecido com os processos em software, mas evite-o até estar confortável pois você não está programando e sim descrevendo um hardware. A maioria dos problemas dos alunos iniciantes em práticas de sistemas digitais advém da descrição incorreta deste estilo de máquinas de estado, principalmente ligadas a inferência de latches devido a atribuição incompleta.

Outros estilos

Mas então por que não usamos um processo só para tudo? Vamos ver:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

architecture umproc of fsm is
  type estado_t is (A,B);
  signal EA : estado_t;
begin
  sincrono: process(clock, reset_n, entrada)
  begin
    if (reset_n='0') then
      saida <= '0';
      EA <= A;
    elsif (rising_edge(clock)) then
      case(EA) is
        when A =>
          saida <= '0';
          if entrada='1' then
            EA <= B;
          else
            EA <= A;
          end if;
        when B =>
          saida <= '1';
          if entrada='1' then
            EA <= A;
          else
            EA <= B;
          end if;
        when others =>
          saida <= '0';
          EA <= A;
      end case;
    end if;
  end process sincrono;
end architecture umproc;

De fato isso é possível, mas o processo será considerado sequencial pelo sintetizador pois contém uma sensibilidade à uma borda (no rising_edge). Como processo sequencial, seus sinais serão registrados, o que é desejável para o sinal EA pois ele representa a própria variável de estado da máquina. Porém, pode não ser desejável tampouco aceitável para os demais sinais. Neste caso, a saída foi o único sinal que sobrou pois o PE pôde ser eliminado, dado que não precisamos mais calcular a função de próximo estado separadamente.

Observe que o circuito gerado possui a saída registrada (inferida pelo sintetizador). Isto não é um problema se você puder conviver com a saída sempre defasada de um ciclo de clock, mas está errado conceitualmente pois a máquina de estados se comportará em fase com o clock para as transições e defasada de um ciclo para os demais sinais. Esta característica costuma confundir muito os iniciantes e dificulta consideravelmente a depuração. Por estes motivos, se você é meu aluno, não use este estilo em nenhum momento durante a graduação (pós por favor consulte antes).

Exemplo 2 (Mealy)

Esta é a mesma máquina que a do Exemplo 1, porém no modelo de Mealy, onde a saída depende também da entrada.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

library ieee;
use ieee.numeric_bit.rising_edge;

entity fsm is
  port(
    entrada: in bit;
    saida: out bit;
    clock, reset_n: in bit
  );
end fsm;

Exemplo 2 (Mealy) - Estilo tradicional

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

architecture proccombmealy of fsm is
  type estado_t is (A,B);
  signal PE,EA : estado_t;
begin

  sincrono: process(clock, reset_n)
  begin
    if (reset_n='0') then
      EA <= A;
    elsif (rising_edge(clock)) then
      EA <= PE;
    end if;
  end process sincrono;

  PE <=
    A when entrada='0' and EA=A else
    B when entrada='1' and EA=A else
    B when entrada='0' and EA=B else
    A when entrada='1' and EA=B else
    A;
  saida <=
    '0' when entrada='0' and EA=A else
    '0' when entrada='1' and EA=A else
    '1' when entrada='0' and EA=B else
    '1' when entrada='1' and EA=B else
    '0';
end architecture proccombmealy;

Note que o circuito gerado é um pouco maior devido a arquitetura para o qual foi sintetizado (FPGA).

Exemplo 2 (Mealy) - Estilo com dois process

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

architecture doisprocmealy of fsm is
  type estado_t is (A,B);
  signal PE,EA : estado_t;
begin

  sincrono: process(clock, reset_n, PE)
  begin
    if (reset_n='0') then
      EA <= A;
    elsif (rising_edge(clock)) then
      EA <= PE;
    end if;
  end process sincrono;

  combinatorio: process(EA, entrada)
  begin
    saida <= '0';
    case(EA) is
      when A =>
        if entrada='1' then
          saida <= '0';
          PE <= B;
        else
          saida <= '0';
          PE <= A;
        end if;
      when B =>
        if entrada='1' then
          saida <= '1';
          PE <= A;
        else
          saida <= '1';
          PE <= B;
        end if;
      when others =>
        saida <= '0';
        PE <= A;
    end case;
  end process combinatorio;

end architecture doisprocmealy;

Observe que não há diferença entre o circuito gerado para esta máquina e para a máquina Moore com dois processos.