Pergunta de entrevista VHDL - detectando se um número pode ser dividido por 5 sem deixar resto

Eu vi uma boa pergunta de entrevista para o VHDL - construa um sistema que receba um número e detecte se ele pode ser dividido por 5 sem deixar resto. Tentei resolver isso com uma máquina de estado (suponho que eles não querem que você use mod ou rem ) e, embora tenha tido sucesso inicial (números como 5, 10, 15 e números como 20, 40, 80 funcionaram ), outros números como 130, 75 e assim por diante falharam para mim.

Eu mostraria minha máquina de estado, mas é uma bagunça completa (não é um código, é um desenho) e, como eu disse, nem funciona.

Basicamente, o que eu tentei fazer é escrever em números binários que são divisíveis por 5 e criar uma máquina de estado que funcione para eles.

Ficaria feliz se você pudesse me mostrar como resolver esse problema e como pensar ao enfrentar algo assim.

Obrigado!

Realizar uma operação restante na forma serial é realmente bastante fácil. A principal suposição é que os dados sejam fornecidos primeiro pelo MSB, se forem seriais. Você só precisa de N estados para calcular um módulo restante N. Comece no estado "0" e se você terminar no estado "0" após o último bit (não importa quantos bits existam), o restante será zero.

^{simular este circuito - esquemático criado usando o CircuitLab}

Pense em como você faria a divisão longa se a única coisa que você precisava acompanhar fosse o restante:

process (clk)
begin
  if rising_edge(clk) then
    if reset = 1 then
      state <= 0;
    else
      if (state & din) >= N then
        state <= (state & din) - N;
      else
        state <= state & din;
      end if;
    end if;
  end if;
end process;

Você também pode projetar uma máquina de estado se os dados chegarem primeiro ao LSB:

A existência desse autômato finito determinístico (DFA) segue diretamente da outra resposta , que descreve o DFA para MSB-first. Como os idiomas aceitos pelos DFAs são regulares e os idiomas regulares são fechados por reversão (por exemplo, veja aqui ), deve haver um DFA que aceite o seguinte idioma:

.$L = \{w\in \{0,1\}^* |\ \text{reverse}(w)_{10}\ \text{is divisible by }5\}$

Construção

1. Copie o primeiro DFA do MSB da resposta de Dave Tweed . Eu usei a ferramenta de autômatos JFLAP para isso.

2. Aplique o algoritmo de transformação explícita para reversões do DFA, por exemplo, conforme descrito no CS.SE: projetando um DFA e o inverso dele .
   Você pode ver o resultado (não minimizado) desta etapa na revisão antiga desta resposta.

3. 
   
   
   $q_0$$q_1$

De fato, o autômato resultante fornece as respostas corretas:

$A_{rev5} = (Q, \Sigma, \delta, q_0, F)$$Q = \{q_0, q_1, q_2, q_3, q_4\}$$\Sigma = \{0,1\}$$F = \{q_0\}$$\delta$

$\delta(q_0, 0) = q_0,\quad\delta(q_0, 1) = q_1\\ \delta(q_1, 0) = q_4,\quad\delta(q_1, 1) = q_3\\ \delta(q_2, 0) = q_1,\quad\delta(q_2, 1) = q_2\\ \delta(q_3, 0) = q_2,\quad\delta(q_3, 1) = q_4\\ \delta(q_4, 0) = q_3,\quad\delta(q_4, 1) = q_0$

Uma maneira de criar a máquina de estados (primeiro MSB) é a seguinte:

1. O número recebido até agora é N. Suponha que você saiba o restante M = N mod 5.

2. Há um novo pedaço chegando e novo valor é agora N' = N*2 + b.

3. Novo restante é então M' = (N*2 + b) mod 5 = (M*2 + b) mod 5.

Isso é fácil o suficiente para tabular manualmente:

    M b | M '
------------------
    0 0 0 0
    1 0 2
    2 0 4
    3 0 1 1
    4 0 | 3
    0 1 1 1
    1 1 | 3
    2 1 | 0 0
    3 1 | 2
    4 1 | 4

O que corresponde à máquina de estado na resposta de Dave Tweed.

Espera-se que a pergunta da entrevista seja sobre como você resolveria o problema, e não os meandros do VHDL ou da Verilog. Os detalhes do idioma são diretos quando você tem um algoritmo.

$S=0$$S \leftarrow (2 S + d) \text{ mod } 5$ $S$$S,d$$S=0,\cdots, 4$

$S=0, k= 0$$S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow k+1$$k$$2^4 = 1 \text{ mod } 5$$S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow (k+1) \text{ mod } 4$$S,k,d$$(S,k)$$S=0,\cdots, 4$$k=0,\cdots, 3$

Dependendo do que o VHDL está sendo escrito, convém adotar uma abordagem que o descreva como um cálculo combinatório direto. Receber um número pode significar que o número inteiro estará em um registro para um ciclo de relógio.

Você pode, por exemplo, anotar o mod 5 do valor que cada um dos bits representa, adicioná-los e repetir o processo até ficar com algo menor que 5. Você pode implementar isso combinatoriamente para todas as etapas de redução, ou reutilize a lógica por um pequeno número de ciclos.

Mas se você usar o operador rem VHDL, essa pode ser a resposta certa. Supondo que a empresa possua ferramentas de síntese decentes, isso daria uma implementação bastante eficiente - talvez um pouco mais de área do que as soluções de máquinas de estado, mas com rendimento total e, portanto, provavelmente boa energia por cálculo. É a opção que custaria menos tempo para implementar e, portanto, provavelmente o menos dinheiro para o empregador!

Para ser justo, provavelmente não é a resposta que eles estão procurando com essa pergunta - mas também é uma oportunidade de mostrar qualquer experiência real de design.

Se o número for apresentado em blocos maiores que um bit, pode ser útil usar alguns cálculos paralelos para calcular o resíduo mod 15, com a condição de que o cálculo possa render 15 é exatamente se o resíduo for zero. Uma maneira simples de calcular o resíduo mod-15 é observar que, para qualquer valor de N> = 1, adicionar os bits 4N mais à esquerda à parte de um número além desse resultará em um valor que é congruente com o mod 15. original. permite que o problema seja subdividido de várias maneiras diferentes, dependendo dos recursos disponíveis.

Por exemplo, se alguém começa com um valor de 32 bits, isso pode ser tratado como oito valores de 4 bits. Esses podem ser adicionados em pares para produzir quatro valores de 5 bits, que por sua vez podem ser combinados em dois valores de 6 bits ou um valor de 7 bits. A adição dos três bits superiores desse valor de 7 bits aos 4 bits inferiores produzirá um valor de 5 bits que é no máximo 21. É possível determinar se o valor original é múltiplo de 5 observando se o valor final é um de 0, 5, 10, 15 ou 20.

Não me lembro do meu VHDL, mas aqui está um esboço da idéia que veio à mente:

Os últimos dígitos (na base 10) das primeiras potências de dois são 1, 2, 4, 8, 6, 2, ... e o ciclo se repete. Portanto, os restantes mod 5 de potências de dois são 1, 2, 4, 3, ....

Usando isso, poderíamos mudar os bits do LSB e acumular o restante mod 5 correspondente à posição sempre que um 1bit for visto. Faça também o mod 5 de acumulação, e é suficiente verificar se a soma é zero no final.

Podemos usar a idéia da resposta aqui , de que na base 4 podemos derivar que um número é divisível por 5 somente se a soma do dígito alternado for. Por isso

1. agrupe os dígitos 2 por 2,
2. somar o ímpar e subtrair os blocos pares de 2 bits.
3. Se o resultado estiver na região dos dois complementos de alguns bits, por exemplo [-4,3] (fácil de verificar, assumindo que usamos dois complementos), então estaremos finalizados e poderemos dividir o número original por 5 somente se o resultado do somatório é 0, que é uma expressão lógica muito simples de verificar (basicamente apenas uma grande nem em todos os bits resultantes, não?)
4. caso contrário, iteramos no novo (número muito menor).

Vamos tentar o número 166 = (10) (10) (01) (10): 2,2,1,2

2-2 + 1-2 = -1

que é <= 3 em valor absoluto e não 0, por que podemos concluir em apenas uma iteração que 166 não é dividido igualmente por 5.

Pode ser que uma pequena memória seja mais barata / melhor em termos de velocidade / número de portas do que na iteração. É claro que é possível pré-calcular o pior (maior resultado possível, considerando as entradas permitidas) e planejar o projeto de acordo.

A abordagem MSB é definitivamente mais fácil, mas eu consegui fazer o diagrama de estados LSB sem precisar gerar a solução MSB ... levei apenas algumas horas. É equivalente ao mostrado pelo @ComFreek, apenas anotado de maneira diferente.

Nós vamos rastrear dois números. Primeiro, vamos acompanhar a soma corrente, módulo 5 ("SUM"). Segundo, rastrearemos o valor da próxima potência de 2 a ser deslocada, módulo 5 ("NEXT"). Representarei cada estado com valores possíveis para "SUM" na parte superior e os valores correspondentes "NEXT" abaixo deles.

Começaremos com o caso em que "SUM" módulo 5 é 0:

Observe que um estado parecido com:
3,2,4,1
1,4,3,2

é equivalente a:
1,3,4,2
2,1,3,4

Como os dois estados representam isso:
SOMA = 1 e NEXT = 4 OU
SOMA = 2 e NEXT = 3 OU
SOMA = 3 e NEXT = 2 OU
SOMA = 4 e NEXT = 1.

Ok, agora precisamos desenvolver estados extras, pois a maioria dos entrevistadores não ficará impressionada com um diagrama de estados com apenas um estado. Nós terminamos quando todo estado tem duas transições.

Sempre que você faz a transição para um novo estado, cada número em "NEXT" é dobrado e, em seguida, modulado em 5. Para o "SUM", siga estas regras:

• Se você fez a transição ao longo de um 0, a linha superior mantém seus valores.
• Se você fez a transição ao longo de um 1, cada coluna será o módulo 5 "SUM" + "NEXT" do estado antigo.

Então, vamos começar preenchendo as transições quando o bit recebido for 1.

Tudo bem, agora preenchemos os zeros. Há apenas um estado adicionado, por isso iremos em frente e preencheremos suas transições.

E pronto! Temos uma máquina de estado que aceita o LSB primeiro, sem precisar gerar a solução MSB.

Tudo isso parece tão complicado! Existe uma maneira matemática fácil de detectar se um número inteiro binário é divisível por cinco. Para começar, você se lembra de como "eliminar nove" na aritmética decimal comum? O módulo de resíduo 9 de um número inteiro decimal é o mesmo que o módulo de resíduo 9 da soma de seus dígitos. Isso funciona porque 9 é um a menos que a base numérica.

Existe um processo semelhante, "eliminando onze", em que os sinais de dígitos alternativos são negativos. Isso funciona porque onze é um maior que a base numérica.

Portanto, se queremos "eliminar cinco", podemos representar nosso número inteiro na base numérica quatro. Começamos com o menor par de dígitos como uma soma inicial e subtraímos do próximo par de dígitos para obter a próxima soma. Depois de analisar nosso número inteiro candidato dessa maneira, a soma final será zero ou divisível por 5 se o número inteiro original for divisível por 5.

Exemplo 70: 01 00 01 10 -> 01 00 -1 -> 01 01 -> 00, divisível por 5 Exemplo 49: 11 00 01 -> 11 -1 -> 1 00 -> 1, NÃO divisível por 5

Observe que você deve transportar bits extras para o sinal da diferença acumulada e para os casos em que há transporte.

Outro caminho a seguir é simplesmente adicionar os dígitos hexadecimais para obter o módulo de resíduo 15. É claro que você precisa de uma etapa lógica final para identificar os três resultados aceitáveis ​​de zero, cinco e dez.

Exemplo 70: 4 6 -> A, então 70 é divisível por 5 (mas não por 15) Exemplo 49: 3 1 -> 4, então 70 NÃO é divisível por 5.

Observe que você pode usar diferentes bases de números para construir muitos testes de divisibilidade, embora na lógica do computador sejam mais fáceis de implementar as potências de 2 +/- 1.

Na aritmética decimal, um dos meus favoritos é o meu teste para o resíduo mod 7. Observe que 100 é dois maior que um múltiplo de 7, portanto, agrupe os dígitos em pares (trabalhe na base numérica 100) e adicione as centenas DUAS VEZES das unidades. Aqui trabalhamos da esquerda para a direita ...

Exemplo: 98 76 -> 2 72 -> 76, então 9876 não é divisível por 7. É 6 mod 7. Exemplo: 03 45 67 -> 51 67 -> 1 69 -> 71 por isso é 1 mod 7.

Obviamente, em binário, basta pegar a soma dos dígitos octais (grupos de 3 bits).

Desculpe, eu queria ser um guru da Verilog, mas a aritmética é tudo o que posso oferecer nesta fase da vida. Veja "Dead Reckoning" de Ron Doerfler para muitos truques como este.

Uma pergunta de entrevista em VHDL deve resultar em algum código VHDL.

Eu tive a ocasião de encontrar um bug no backend do ghdl llvm com uma implementação da tabela de transição de estado de Dave Tweed, na qual o autor do ghdl destilou a implementação em uma função para 17 linhas:

type remains is (r0, r1, r2, r3, r4); -- remainder values

    function mod5 (dividend: bit_vector) return boolean is
        type remain_array is array (NBITS downto 0) of remains;
        type branch is array (remains, bit) of remains;
        constant br_table:  branch := ( r0 => ('0' => r0, '1' => r1),
                                        r1 => ('0' => r2, '1' => r3),
                                        r2 => ('0' => r4, '1' => r0),
                                        r3 => ('0' => r1, '1' => r2),
                                        r4 => ('0' => r3, '1' => r4)
                                      );
        variable  remaind:    remains := r0;
        variable tbit:        bit_vector (NBITS - 1 downto 0) := dividend;
    begin
        for i in dividend'length - 1 downto 0 loop
            remaind := br_table(remaind,tbit(i));
        end loop;
        return remaind = r0;
end function;

O caso de teste associado é bem pequeno, facilitando a depuração e usa nomes de estado compatíveis com VHDL no tipo enumerado:

(criado com Dia)

A idéia aqui é que a função (ou mesmo um programa VHDL de exemplo de 27 linhas) seja curta o suficiente para escrever uma resposta VHDL durante uma entrevista. Não há necessidade de se preocupar em estragar uma pergunta de entrevista que exija demonstração de conhecimento e habilidade; espera-se que um entrevistado defenda uma implementação quando questionado.

(O bug do back-end do llvm foi corrigido no commit 1f5df6e hoje cedo.)

Uma das coisas a observar é que a tabela de transição de estados também nos diz onde um bit quociente seria um '1' mostrado por uma transição para um estado com um valor restante mais baixo (ou ambas as transições para r4) ao subtrair 5 do dividendo. Isso pode ser codificado em uma tabela separada (ou em uma tabela com um tipo de registro que parece complicado). Fazemos isso historicamente em hardware gráfico que lida com resoluções de tela horizontais com múltiplos de 5 pixels.

Fazer isso nos dá um div / mod5 produzindo um quociente e o restante:

library ieee;
use ieee.std_logic_1164.all;

entity divmod5 is
    generic (
        NBITS:  natural := 13 
    );
    port (
        clk:        in  std_logic;
        dividend:   in  std_logic_vector (NBITS - 1 downto 0);
        load:       in  std_logic;
        quotient:   out std_logic_vector (NBITS - 3 downto 0);
        remainder:  out std_logic_vector (2 downto 0);
        remzero:    out std_logic
    );
end entity;

architecture foo of divmod5 is
    type remains is (r0, r1, r2, r3, r4); -- remainder values
    type remain_array is array (NBITS downto 0) of remains;
    signal remaindr:    remain_array := (others => r0);
    signal dividendreg: std_logic_vector (NBITS - 1 downto 0);
    signal quot:        std_logic_vector (NBITS - 3 downto 0);
begin

parallel:
    for i in NBITS - 1 downto 0 generate
        type branch is array (remains, bit) of remains;
        -- Dave Tweeds state transition table:
        constant br_table:  branch := ( r0 => ('0' => r0, '1' => r1),
                                        r1 => ('0' => r2, '1' => r3),
                                        r2 => ('0' => r4, '1' => r0),
                                        r3 => ('0' => r1, '1' => r2),
                                        r4 => ('0' => r3, '1' => r4)
                                      );

        type qt is array (remains, bit) of std_ulogic;
    -- Generate quotient bits from Dave Tweeds state machine using q_table.
    -- A '1' when a remainder goes to a lower remainder or for both branches
    -- of r4. A '0' for all other branches.

        constant q_table:   qt :=     ( r0 => (others => '0'),
                                        r1 => (others => '0'),
                                        r2 => ('0' => '0', '1' => '1'),
                                        r3 => (others => '1'),
                                        r4 => (others => '1')
                                      );
        signal tbit:    bit;
    begin
        tbit <= to_bit(dividendreg(i));
        remaindr(i) <= br_table(remaindr(i + 1),tbit);
do_quotient:
        if i < quot'length generate   
            quot(i) <= q_table(remaindr(i + 1),tbit);
        end generate;
    end generate;

dividend_reg:
    process (clk)
    begin
        if rising_edge(clk) then
            if load = '1' then
                dividendreg <= dividend;
            end if;
        end if;
    end process;

quotient_reg:
    process (clk)
    begin
        if rising_edge (clk) then
            quotient <=  quot;
        end if;
    end process;

remainders:
    process (clk)
    begin
        if rising_edge(clk) then 
            remzero <= '0';
            case remaindr(0) is
                when r0 =>
                    remainder <= "000";
                    remzero <= '1';
                when r1 =>
                    remainder <= "001";
                when r2 =>
                    remainder <= "010";
                when r3 =>
                    remainder <= "011";
                when r4 =>
                    remainder <= "100";
            end case;
        end if;
    end process;

end architecture;

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity divmod5_tb is
end entity;

architecture foo of divmod5_tb is
    constant NBITS:    integer range 0 to 13 := 8;
    signal clk:        std_logic := '0';
    signal dividend:   std_logic_vector (NBITS - 1 downto 0);
    signal load:       std_logic := '0';

    signal quotient:   std_logic_vector (NBITS - 3 downto 0);
    signal remainder:  std_logic_vector (2 downto 0);
    signal remzero:    std_logic;
    signal psample:    std_ulogic;
    signal sample:     std_ulogic;
    signal done:       boolean;
begin
DUT:
    entity work.divmod5
        generic map  (NBITS)
        port map (
            clk => clk,
            dividend => dividend,
            load => load,
            quotient => quotient,
            remainder => remainder,
            remzero => remzero
        );
CLOCK:
    process
    begin
        wait for 5 ns;
        clk <= not clk;
        if done'delayed(30 ns) then
            wait;
        end if;
    end process;
STIMULI:
    process
    begin
        for i in 0 to 2 ** NBITS - 1 loop
            wait for 10 ns;
            dividend <= std_logic_vector(to_unsigned(i,NBITS));
            wait for 10 ns;
            load <= '1';
            wait for 10 ns;
            load <= '0';
        end loop;
        wait for 15 ns;
        done <= true;
        wait;
    end process;

SAMPLER:
    process (clk)
    begin
        if rising_edge(clk) then
            psample <= load;
            sample <= psample after 4 ns;
        end if;
    end process;

MONITOR:
    process (sample)
        variable i:     integer;
        variable div5:  integer;
        variable rem5:  integer;
    begin
        if rising_edge (sample) then
            i := to_integer(unsigned(dividend));
            div5 := i / 5;
            assert div5 = unsigned(quotient)
                report LF & HT &
                    "i = " & integer'image(i) &
                    " div 5 expected " & integer'image(div5) & 
                    " got " & integer'image(to_integer(unsigned(quotient)))
                SEVERITY ERROR;
            rem5 := i mod 5;
            assert rem5 = unsigned(remainder)
                report LF & HT &
                    "i = " & integer'image(i) &
                    " rem 5 expected " & integer'image(rem5) & 
                    " got " & integer'image(to_integer(unsigned(remainder)))
                SEVERITY ERROR;
        end if;
    end process;

end architecture;

Implementado aqui com uma instrução generate, uma instrução generate interna que produz bits quocientes. A matriz remanescente fornece um rastreamento de transição de estado:

Tudo sem uma operação aritmética.

Também é possível implementar em um procedimento sem todos os registradores tirando proveito dos parâmetros com mode out. Isso aproximaria um número mínimo de linhas para uma entrevista.

Uma implementação seqüencial com clock exigiria um pouco de controle de fluxo e contador (um flip-flop JK e algumas portas).

Há uma troca de tempo / complexidade, dependendo do tamanho dos dividendos que você provavelmente também precisaria defender em uma entrevista.