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

24

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!

Eran
fonte
Você quer dizer uma implementação de hardware (sintetizável), não apenas um código para testar se um literal inteiro é divisível por 5 (por exemplo, para testbench).
SMCI
@smci Na verdade, estava pedindo um desenho esquemático / de uma máquina de estado, mas um código dessa máquina de estado não faria mal. Dave Tweed respondeu à pergunta perfeitamente.
Eran
então eu o redigitava * "Pergunta da entrevista em VHDL - cct para detectar se ..."
smci
Responda aqui por egreg math.stackexchange.com/a/2569882/213607 pode dar alguma inspiração para uma abordagem mais paralela.
mathreadler

Respostas:

37

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.

esquemático

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;
Dave Tweed
fonte
6
Uau, vejo que funciona, mas você poderia explicar como criou a máquina de estado? Qual foi o ponto de partida? Eu nunca vi isso feito antes. Estou apenas curioso sobre o que é a lógica de como chegar a isso?
Zd #
7
O diagrama de estados é exatamente o que você obtém do código VHDL para o caso específico de N = 5. Em outras palavras, se o estado representa o restante atual, o próximo estado é o que você obtém quando muda o estado para a esquerda um pouco, adiciona o bit de entrada a ele e subtrai 5, se necessário.
Dave Tweed
3
Isso, se for bonito, eu ficaria realmente impressionado se alguém descobrir isso sozinho em uma entrevista. E, em seguida, solicitava que eles comentassem como os resultados da síntese difeririam em comparação ao uso de um operador rem para processar um vetor completo a cada ciclo do relógio.
Casperrw
8
@zoder Os estados são os resíduos mod 5; a seta 0 aponta para 2n mod 5e a seta 1 aponta para (2n + 1) mod 5.
Hbbs #
2
Você pode adicionar as declarações de state, dine Nao seu código?
mkrieger1
15

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

Uma representação gráfica do DFA, conforme descrito no final desta resposta no apêndice.

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:

.eu={W{0 0,1 1}| marcha ré(W)10 é divisível por 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. q0 0q1 1

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

Tabela com duas colunas "Entrada" e "Resultado", listando se vários números resultam em "Aceitar" ou "Rejeitar".


UMArev5=(Q,Σ,δ,q0 0,F)Q={q0 0,q1 1,q2,q3,q4}Σ={0 0,1 1}F={q0 0}δ

δ(q0 0,0 0)=q0 0,δ(q0 0,1 1)=q1 1δ(q1 1,0 0)=q4,δ(q1 1,1 1)=q3δ(q2,0 0)=q1 1,δ(q2,1 1)=q2δ(q3,0 0)=q2,δ(q3,1 1)=q4δ(q4,0 0)=q3,δ(q4,1 1)=q0 0

ComFreek
fonte
Se estiver com dificuldades para reverter o DFA, você também pode reverter a equação: em vez de new_state = state * 2 + input, você pode usar (new_state - input) / 2 = state, depois trocar estado e new_state. O DFA para a nova equação deve resolver o problema do LSB-primeiro.
Eyal
Por que os q3 e q4 são rotulados de modo que não vice-versa? Troque as etiquetas q3 e q4 e a máquina implementa o algo "metade (mod 5) e adicione o bit de entrada".
Rosie F
2
@RosieF: A frase "reduzir pela metade (mod 5)" talvez possa usar mais explicações para aqueles que não estão familiarizados com a matemática discreta. A divisão neste contexto implica adicionar qualquer múltiplo da base necessário para dividir o número igualmente, portanto 3/2 (mod 5) seria (3 + 5) / 2, ou seja, 4.
supercat
7

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.

jpa
fonte
5

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 0S(2S+d) mod 5 SS,dS=0 0,,4

S=0 0,k=0 0S(S+2kd) mod 5,kk+1 1k24=1 1 mod 5S(S+2kd) mod 5,k(k+1 1) mod 4S,k,d(S,k)S=0 0,,4k=0 0,,3

copper.hat
fonte
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.

Casperrw
fonte
3

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.

supercat
fonte
... ou você pode usar somadores de 4 bits por toda parte e apenas certifique-se de que cada transporte se torne um transporte para um adicionador mais tarde no circuito. Após três camadas de adição, você obtém um único resultado de 4 bits e quatro carregamentos ainda não utilizados. Adicione três dos carregamentos juntos em paralelo com a última adição de 4 bits e adicione sua soma ao resultado com o último transportador como transporte. Isso gera no máximo 19, então você não precisa igualar os 20 depois.
Henning Makholm
@ HenningMakholm: Existem muitas maneiras de organizar os adicionadores para obter o resultado desejado. Qual abordagem é melhor em uma determinada situação provavelmente dependeria de problemas de roteamento ou utilização de recursos específicos do projeto. Outro truque seria usar os adicionadores de carry-save, mas explorar o fato de que a parte superior da saída deslocada pode ser movida para a parte inferior. Assim, uma camada pode transformar 8 entradas em 6, depois 6 em 4, depois 4 em 3 e 3 em 2. Uma saída de cada camada seria simplesmente portas AND e a outra porta XOR, para que o tempo de propagação se reduza a par de valores de 4 bits para o ...
supercat
... uma e única corrente de transporte seria a de quatro portões xor. Quanto a se é melhor obter uma saída abaixo de 19 ou se é melhor verificar se há 20 como um possível resíduo, isso provavelmente depende da disponibilidade e utilização de recursos. Dado um número não superior a 30, a adição de nybbles superior e inferior produziria um valor no máximo 15 (16 + 14-> 1 + 14 ou 0 + 15-> 0 + 15), mas adicionando explícita as verificações de alguns ou de todos (20, 25, 30) podem ser mais baratas.
Supercat
2

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.

ilkkachu
fonte
1

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.

mathreadler
fonte
1

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:

Inicial

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.

Todos os 1s

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

Completo

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

Glasses2C_Sharp
fonte
1

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.

richard1941
fonte
Gostaria de saber se nossos primos canadenses podem ter alguns algoritmos especiais. Como eles proibiram o centavo canadense, todos os preços são arredondados para os $ 0,05 mais próximos.
richard1941
1

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:

dave_tweed.png (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:

divmod5_tb.png

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.

user8352
fonte