pregunta de la entrevista VHDL: detectar si un número se puede dividir entre 5 sin el resto

24

Vi una pregunta de entrevista agradable para VHDL: construya un sistema que reciba un número y detecte si se puede dividir entre 5 sin el resto. Traté de resolver eso con una máquina de estados (supongo que no quieren que uses mod o rem ) y mientras tuve un éxito inicial (números como 5, 10, 15 y números como 20, 40, 80 funcionaron), otros números como 130, 75 y así sucesivamente fallaron para mí.

Mostraría mi máquina de estado pero es un desastre completo (no es un código, es un dibujo), y como he dicho, ni siquiera funciona.

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

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

¡Gracias!

    
pregunta Eran

11 respuestas

37

En realidad, hacer una operación de resto en forma serial es bastante fácil. El supuesto clave es que los datos vienen primero en MSB si son en serie. Solo necesita N estados para calcular un módulo de resto 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 usando CircuitLab

Piensa en cómo harías una división larga si lo único que necesitabas hacer un seguimiento fuera 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;
    
respondido por el Dave Tweed
14

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

Laexistenciadetal autómata finito determinista (DFA) se deriva directamente de la otra respuesta , que describe el DFA para MSB en primer lugar. Debido a que los idiomas aceptados por los DFA son regulares, se sabe que los idiomas regulares se cierran por reversión (por ejemplo, consulte aquí ), debe ser un DFA que acepte el siguiente idioma:

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

Construcción

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

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

  3. Minimiza el DFA resultante. Desafortunadamente, esta característica tiene un poco de buggy en la última versión de JFLAP, así que me resigné a minimizarla a mano.
    Una vez más, hay muchos algoritmos y fuentes para ellos, utilicé el descrito en “Minimización de DFA” en tutorialspoint.com .

    (En realidad, si sus ojos están lo suficientemente bien como para mirar las DFA, podría ver directamente que \ $ q_0 \ $ y \ $ q_1 \ $ son estados equivalentes en la DFA según se obtiene en el punto 2. Los míos no lo son, gracias por notarlo, ¡vaya al comentario de supercat!)

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

Tablecondoscolumnas"Entrada" y "Resultado" que indican si varios números dan como resultado "Aceptar" o "Rechazar".

Apéndice: Por razones de accesibilidad, el DFA que acepta números binarios que son divisibles por 5 con LSB-first es \ $ A_ {rev5} = (Q, \ Sigma, \ delta, q_0, F) \ $ with \ $ Q = \ {q_0, q_1, q_2, q_3, q_4 \} \ $, \ $ \ Sigma = \ {0,1 \} \ $, \ $ F = \ {q_0 \} \ $ y \ $ \ delta \ $ de la siguiente manera:

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

    
respondido por el ComFreek
7

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

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

  2. Está llegando un nuevo bit y el nuevo valor ahora es N' = N*2 + b .

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

Esto es bastante fácil de tabular a mano:

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

Que coincide con la máquina de estados en la respuesta de Dave Tweed.

    
respondido por el jpa
5

Uno espera que la pregunta de la entrevista sea 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 tienes un algoritmo.

Si el número se pasa bit a bit con MSB primero, entonces el el valor del número módulo 5 se puede calcular inicializando el estado \ $ S = 0 \ $ y luego acumulando el valor con \ $ S \ leftarrow (2 S + d) \ text {mod} 5 \ $. Al final, el número es divisible por 5 iff \ $ S \ $ es cero. Como \ $ S, d \ $ están delimitados, la ecuación de actualización se puede escribir como una simple máquina de estados con estados \ $ S = 0, \ cdots, 4 \ $.

Si el número se pasa bit a bit con LSB primero, necesitamos hacer un poco más de trabajo. Fuera del bate podemos intentar inicializar el estado \ $ S = 0, k = 0 \ $ y luego acumulando el valor con \ $ S \ leftarrow (S + 2 ^ k d) \ text {mod} 5, k \ leftarrow k + 1 \ $. El problema con esto es que \ $ k \ $ es potencialmente ilimitado, sin embargo, ya que \ $ 2 ^ 4 = 1 \ text {mod} 5 \ $, podemos simplificar lo anterior para \ $ S \ leftarrow (S + 2 ^ k d) \ text {mod} 5, k \ leftarrow (k + 1) \ text {mod} 4 \ $. Nuevamente, dado que \ $ S, k, d \ $ están delimitados, la ecuación de actualización se puede escribir como una máquina de estado simple con estados \ $ (S, k) \ $ donde \ $ S = 0, \ cdots, 4 \ $ , \ $ k = 0, \ cdots, 3 \ $.

    
respondido por el copper.hat
3

Dependiendo de para qué se escribe 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 todo el número estará en un registro para 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 le quede algo menos de 5. O implemente esto de manera combinada para todos los Reducir los pasos, o reutilizar la lógica durante un pequeño número de ciclos.

Pero si usa el operador rem de VHDL, esa puede ser la respuesta correcta. Suponiendo que la empresa 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 un 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 menos 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.

    
respondido por el Casperrw
3

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 forma sencilla de calcular el residuo de mod-15 es observar que para cualquier valor de N > = 1, agregar los 4N bits más a la izquierda a la parte de un número más allá de eso dará un valor que es congruente con el mod 15 original. permite que el problema se subdivida de muchas maneras diferentes dependiendo de los recursos disponibles.

Por ejemplo, si uno comienza con un valor de 32 bits, se puede tratar como ocho valores de 4 bits. Esos pueden sumarse por pares para obtener cuatro valores de 5 bits, que a su vez pueden combinarse 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 más bajos 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 observando si el valor final es uno de 0, 5, 10, 15 o 20.

    
respondido por el supercat
2

No puedo recordar mi VHDL, pero aquí hay un bosquejo de la idea que primero me vino a la mente:

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 las 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 siempre que se vea un bit 1 . Haz el mod 5 de acumulación también, y es suficiente para verificar si la suma es cero al final.

    
respondido por el ilkkachu
1

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 alternos es. Por lo tanto,

  1. agrupa los dígitos 2 por 2,
  2. suma el número 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 entre 5 solo si el el resultado de la suma es 0, que es una expresión lógica muy simple de verificar (básicamente solo una grande o en todos los bits resultantes, ¿no?)
  4. de lo contrario, iteramos en el nuevo (número mucho más corto).

Probemos 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 lo que podemos concluir en una sola iteración que 166 no está dividido en partes iguales por 5.

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

    
respondido por el mathreadler
1

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

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

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

Tengaencuentaqueunestadoqueseparecea:
3,2,4,1
1,4,3,2

esequivalentea:
1,3,4,2
2,1,3,4

Porqueambosestadosrepresentaneso:
SUM=1ySIGUIENTE=4O
SUM=2ySIGUIENTE=3O
SUM=3ySIGUIENTE=2O
SUM=4ySIGUIENTE=1.

Bien,ahoranecesitamosdesarrollarestadosadicionales,yaquelamayoríadelosentrevistadoresnosevanaimpresionarporundiagramadeestadoconunsoloestado.Hemosterminadocuandocadaestadotienedostransiciones.

Cadavezquerealicelatransiciónaunnuevoestado,cadanúmeroen"SIGUIENTE" se duplica, luego en módulo 5. Para la "SUMA" siga estas reglas:

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

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

Bien,ahorallenamoslosceros.Soloseagregóunestado,porloqueseguiremosadelanteycompletaremossustransicionestambién.

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

    
respondido por el Glasses2C_Sharp
1

¡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 "expulsar nueves" en la aritmética decimal ordinaria? El residuo módulo 9 de un entero decimal es el mismo que el residuo módulo 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 los dígitos alternativos se establecen como negativos. Esto funciona porque once es uno mayor que la base numérica.

Entonces, si queremos "lanzar cinco", podríamos representar nuestro número entero en el número base cuatro. Luego, comenzamos con el par de dígitos más bajo como suma inicial y lo restamos del siguiente par de dígitos para obtener la siguiente suma. Después de pasar por nuestro entero 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 adicionales para el signo de la diferencia acumulada y para los casos en que haya carga.

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 computacional las más fáciles de implementar son las de potencias de 2 +/- 1.

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

Ejemplo: 98 76 - > 2 72 - > 76, por lo que 9876 no es divisible por 7. Es 6 mod 7. Ejemplo: 03 45 67 - > 51 67 - > 1 69 - > 71 por lo que 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 ver muchos trucos como este.

    
respondido por el richard1941
1

Una pregunta de entrevista de VHDL debería resultar en un código de VHDL.

Tuve la oportunidad de encontrar un error de backend de ghdl llvm con un 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 a 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 sencilla y utiliza nombres de estado compatibles con VHDL en el tipo enumerado:

(creadoconDia)

Laideaaquíesquelafunción(oinclusounejemplodeprogramaVHDLde27líneas)eslosuficientementecortacomoparaescribirunarespuestaVHDLduranteunaentrevista.Noesnecesarioquesepreocupeporestropearunapreguntadelaentrevistaquerequieredemostracióndeconocimientosyhabilidades,seesperaríaqueelentrevistadodefendieraunaimplementacióncuandoseleinterrogara.

(Elerrordebackendllvmsehacorregidoencommit 1f5df6e anteriormente hoy.)

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

Al hacerlo, nos da un div / mod5 que produce un cociente y el 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 instrucció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 implementarlo en un procedimiento sin que todos los registros aprovechen los parámetros sin modo. Eso se acercaría a un número mínimo de líneas para una entrevista.

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

Hay un intercambio de tiempo / complejidad dependiendo del tamaño del dividendo que probablemente también deberías defender en una entrevista.

    
respondido por el user8352

Lea otras preguntas en las etiquetas