Pregunta de entrevista de VHDL: detectar si un número se puede dividir por 5 sin resto

Vi una buena pregunta de entrevista para VHDL: crea un sistema que recibe un número y detecta si se puede dividir entre 5 sin resto. Traté de resolver eso con una máquina de estado (supongo que no quieren que uses mod o rem ) y aunque tuve éxito inicial (números como 5, 10, 15 y números como 20, 40, 80 funcionaron ), otros números como 130, 75, etc. me fallaron.

Mostraría mi máquina de estados, pero es un desastre total (no es un código, es un dibujo) y, como dije, ni siquiera funciona.

Básicamente, lo que intenté hacer es escribir en números binarios que son divisibles por 5, y construir una máquina de estado que funcione para ellos.

Me alegraría que me mostraras cómo resolver este problema y cómo pensar al enfrentar algo como esto.

¡Gracias!

Hacer una operación restante en forma serial es realmente bastante fácil. La suposición clave es que los datos vienen primero en MSB si son seriales. Solo necesita N estados para calcular el resto del módulo N. Comience en el estado "0" y si termina en el estado "0" después del último bit (no importa cuántos bits haya), el resto es cero.

^{simular este circuito : esquema creado con CircuitLab}

Piense en cómo haría una división larga si lo único que necesitara hacer un seguimiento fue el resto:

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;

También puede diseñar una máquina de estado si los datos vienen primero con LSB:

La existencia de dicho autómata finito determinista (DFA) se deduce directamente de la otra respuesta , que describe el DFA para MSB-first. Debido a que los idiomas aceptados por los DFA son regulares y se sabe que los idiomas regulares están cerrados bajo inversión (por ejemplo, consulte aquí ), debe haber un DFA que acepte el siguiente idioma:

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

Construcción

1. Copie el primer DFA de MSB de la respuesta de Dave Tweed . Usé la herramienta de autómata JFLAP para eso.

2. Aplique el algoritmo de transformación explícito para las reversiones de DFA, por ejemplo, como se describe en CS.SE: Diseño de un DFA y su reverso .
   Puede ver el resultado (no minimizado) de este paso en la revisión anterior de esta respuesta.

3. 
   
   
   $q_0$$q_1$

De hecho, el autómata resultante da las respuestas correctas:

$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$

Una forma de crear la máquina de estado (primero MSB) es la siguiente:

1. El número recibido hasta ahora es N. Suponga que conoce el resto M = N mod 5.

2. Hay una nueva entrada y ahora hay un nuevo valor N' = N*2 + b.

3. Nuevo resto es entonces M' = (N*2 + b) mod 5 = (M*2 + b) mod 5.

Esto es bastante fácil de tabular a mano:

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

Lo que coincide con la máquina de estado en la respuesta de Dave Tweed.

Uno espera que la pregunta de la entrevista fuera sobre cómo resolvería el problema, en lugar de los entresijos de VHDL o Verilog. Los detalles del idioma son sencillos una vez que tiene un algoritmo.

Si el número se pasa bit a bit con MSB primero, entonces el valor del número módulo 5 se puede calcular inicializando el estado y luego acumulando el valor con$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$

Dependiendo de para qué se está escribiendo el VHDL, es posible que desee adoptar un enfoque que lo describa como un cálculo directo y combinacional. Recibir un número puede significar que el número completo estará en un registro durante un ciclo de reloj.

Podría, por ejemplo, anotar el mod 5 del valor que representa cada uno de los bits, sumarlos y luego repetir el proceso hasta que quede algo menor que 5. Implemente esto de manera combinada para todos los pasos de reducción, o reutilice la lógica para un pequeño número de ciclos.

Pero si usa el operador rem VHDL, esa puede ser la respuesta correcta. Suponiendo que la compañía tenga herramientas de síntesis decentes, eso le daría una implementación bastante eficiente, quizás un poco más de área que las soluciones de máquina de estado, pero rendimiento total y, por lo tanto, probablemente una buena energía por cálculo. ¡Es la opción que costaría menos tiempo de implementación y, por lo tanto, probablemente el menor dinero para el empleador!

Para ser justos, probablemente no sea la respuesta que buscan con esa pregunta, pero también es una oportunidad para mostrar cualquier experiencia de diseño real.

Si el número se presenta en fragmentos de más de un bit, puede ser útil usar algunos cálculos paralelos para calcular el residuo mod 15, con la condición de que el cálculo pueda producir 15 es exactamente si el residuo es cero. Una manera simple de calcular el residuo de mod-15 es observar que para cualquier valor de N> = 1, al agregar los 4N bits más a la izquierda a la parte de un número más allá, se obtendrá un valor congruente con el mod 15. Esto permite que el problema se subdivida de muchas maneras diferentes según los recursos disponibles.

Por ejemplo, si uno comienza con un valor de 32 bits, eso puede tratarse como ocho valores de 4 bits. Esos se pueden sumar por pares para obtener cuatro valores de 5 bits, que a su vez se pueden combinar en dos valores de 6 bits o un valor de 7 bits. Agregar los tres bits superiores de ese valor de 7 bits a los 4 bits inferiores producirá un valor de 5 bits que es como máximo 21. Por lo tanto, se puede determinar si el valor original es un múltiplo de 5 al observar si el valor final es uno de 0, 5, 10, 15 o 20.

No recuerdo mi VHDL, pero aquí hay un boceto de la idea que se me ocurrió por primera vez:

Los últimos dígitos (en la base 10) de las primeras potencias de dos son 1, 2, 4, 8, 6, 2, ... y el ciclo se repite. Por lo tanto, los restos mod 5 de potencias de dos son 1, 2, 4, 3, ...

Usando eso, podríamos cambiar en bits desde el LSB y acumular los restos mod 5 correspondientes a la posición cada vez que 1se ve un bit. Realice el mod 5 de acumulación también, y es suficiente para verificar si la suma es cero al final.

Podemos usar la idea de la respuesta aquí , que en la base 4 podemos deducir que un número es divisible por 5 solo si la suma de dígitos alterna es. Nosotros por lo tanto

1. agrupe los dígitos 2 por 2,
2. suma lo impar y resta los bloques pares de 2 bits.
3. Si el resultado está en la región de dos complementos de unos pocos bits, por ejemplo [-4,3] (fácil de verificar suponiendo que usamos dos complementos), entonces hemos terminado y podemos dividir el número original por 5 solo si el resultado de la suma es 0, que es una expresión lógica muy simple para verificar (básicamente solo una gran cantidad de todos los bits resultantes, ¿no?)
4. de lo contrario, iteramos en el nuevo (número mucho más corto).

Probemos con el número 166 = (10) (10) (01) (10): 2,2,1,2

2-2 + 1-2 = -1

que es <= 3 en valor absoluto y no 0 por qué podemos concluir en una sola iteración que 166 no está dividido equitativamente por 5.

Podría ser que una memoria pequeña podría ser más barata / mejor en términos de velocidad / nr de puertas que iterar. Por supuesto, uno puede calcular previamente lo peor (el mayor resultado posible dadas las entradas permitidas) y planificar el diseño en consecuencia.

El enfoque MSB es definitivamente más fácil, pero logré hacer el diagrama de estado LSB sin necesidad de generar la solución MSB ... solo me tomó un par de horas. Resulta ser equivalente al que muestra @ComFreek, solo anotado de manera diferente.

Vamos a seguir dos números. Primero, vamos a rastrear la suma acumulada, módulo 5 ("SUMA"). En segundo lugar, rastrearemos el valor de la próxima potencia de 2 que se cambiará, módulo 5 ("NEXT"). Representaré cada estado con posibles valores para "SUMA" en la parte superior, y sus correspondientes valores "SIGUIENTE" debajo de ellos.

Comenzaremos con el caso donde "SUMA" módulo 5 es 0:

Tenga en cuenta que un estado que se parece a:
3,2,4,1
1,4,3,2

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

Debido a que ambos estados representan que:
SUM = 1 y NEXT = 4 OR
SUM = 2 y NEXT = 3 OR
SUM = 3 y NEXT = 2 OR
SUM = 4 y NEXT = 1.

Bien, entonces ahora necesitamos desarrollar estados adicionales, ya que la mayoría de los entrevistadores no se impresionarán con un diagrama de estado con un solo estado. Terminamos cuando cada estado tiene dos transiciones.

Cada vez que realice la transición a un nuevo estado, cada número en "SIGUIENTE" se duplica, luego el módulo 5. Para la "SUMA", siga estas reglas:

• Si realizó la transición a lo largo de un 0, la fila superior mantiene sus valores.
• Si realizó la transición a lo largo de un 1, cada columna es el módulo 5 "SUMA" + "SIGUIENTE" del estado anterior.

Entonces, comencemos completando las transiciones cuando el bit entrante es 1.

Muy bien, ahora completamos los ceros. Solo hay un estado agregado, así que seguiremos adelante y completaremos sus transiciones también.

¡Y voilá! Tenemos una máquina de estado que acepta el LSB primero, sin tener que generar la solución MSB.

¡Todo lo anterior parece tan complicado! Hay una manera matemática fácil de detectar si un entero binario es divisible por cinco. Para empezar, ¿recuerdas cómo hacer "lanzar nueves" en la aritmética decimal ordinaria? El módulo de residuo 9 de un entero decimal es el mismo que el módulo de residuo 9 de la suma de sus dígitos. Esto funciona porque 9 es uno menos que la base numérica.

Hay un proceso similar, "expulsar once", donde los signos de dígitos alternativos se ponen negativos. Esto funciona porque once es uno mayor que la base numérica.

Entonces, si queremos "echar cinco", podríamos representar nuestro número entero en la base número cuatro. Luego comenzamos con el par de dígitos más bajo como una suma inicial, y lo restamos del siguiente par de dígitos para obtener la siguiente suma. Después de pasar por nuestro entero candidato de esta manera, la suma final será cero o divisible por 5 si nuestro entero original es divisible por 5.

Ejemplo 70: 01 00 01 10 -> 01 00 -1 -> 01 01 -> 00, divisible por 5 Ejemplo 49: 11 00 01 -> 11 -1 -> 1 00 -> 1, NO divisible por 5

Tenga en cuenta que debe llevar bits extra para el signo de la diferencia acumulada y para los casos en los que hay transporte.

Otra forma de hacerlo es simplemente agregar los dígitos hexadecimales para obtener el módulo de residuo 15. Por supuesto, necesita un paso lógico final para identificar los tres resultados aceptables de cero, cinco y diez.

Ejemplo 70: 4 6 -> A, entonces 70 es divisible por 5 (pero no por 15) Ejemplo 49: 3 1 -> 4, entonces 70 no es divisible por 5.

Tenga en cuenta que puede usar diferentes bases numéricas para construir muchas pruebas de divisibilidad, aunque en lógica informática las que tienen potencias de 2 +/- 1 son más fáciles de implementar.

En aritmética decimal, uno de mis favoritos es mi prueba para el mod 7 de residuos. Tenga en cuenta que 100 es dos mayor que un múltiplo de 7, por lo tanto, agrupe los dígitos en pares (trabaje en la base de número 100) y agregue los cientos DOS VECES de las unidades. Aquí trabajamos de izquierda a derecha ...

Ejemplo: 98 76 -> 2 72 -> 76, entonces 9876 no es divisible por 7. Es 6 mod 7. Ejemplo: 03 45 67 -> 51 67 -> 1 69 -> 71 entonces es 1 mod 7.

Por supuesto, en binario, simplemente tome la suma de los dígitos octales (grupos de 3 bits).

Lo siento, desearía ser un gurú de Verilog, pero la aritmética es todo lo que puedo ofrecer en esta etapa de la vida. Vea "Dead Reckoning" de Ron Doerfler para muchos trucos como este.

Una pregunta de entrevista VHDL debería dar lugar a algún código VHDL.

Tuve la oportunidad de encontrar un error de backend de ghdl llvm con una implementación de la tabla de transición de estado de Dave Tweed donde el autor de ghdl destiló la implementación en una función en 17 líneas:

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;

El caso de prueba asociado es bastante pequeño, lo que permite una depuración más fácil y utiliza nombres de estado compatibles con VHDL en los tipos enumerados:

(creado con Dia)

La idea aquí es que la función (o incluso un ejemplo de programa VHDL de 27 líneas) es lo suficientemente corta como para escribir una respuesta VHDL durante una entrevista. No es necesario preocuparse por estropear una pregunta de la entrevista que requiere la demostración de conocimiento y habilidad, se espera que un entrevistado defienda una implementación cuando se le pregunta.

(El error de backend llvm se ha solucionado en commit 1f5df6e hoy).

Una de las cosas notables es que la tabla de transición de estado también nos dice dónde un bit de cociente sería un '1' que se muestra mediante una transición a un estado con un valor restante más bajo (o ambas transiciones para r4) al restar 5 del dividendo. Eso se puede codificar en una tabla separada (o una tabla de un tipo de registro que parece engorroso). Hacemos esto históricamente en hardware de gráficos que trata con resoluciones de pantalla horizontales que se multiplican por 5 píxeles.

Hacerlo nos da un div / mod5 que produce un cociente y resto:

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 aquí con una declaración de generación, una declaración de generación interna que produce bits de cociente. La matriz remaindr proporciona una traza de transición de estado:

Todo sin una operación aritmética.

También es posible implementar en un procedimiento sin que todos los registros aprovechen los parámetros con el modo fuera. Eso se acercaría a un número mínimo de líneas para una entrevista.

Una implementación secuencial con reloj requeriría un contador de bits y control de flujo (un flip flop JK y un par de compuertas).

Hay una compensación de tiempo / complejidad que depende del tamaño del dividendo que probablemente también deba defender en una entrevista.