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

Question

Yo vi una buena pregunta de la entrevista de VHDL - construir un sistema que recibe una cantidad y detecta si se puede dividir por 5 sin resto. Traté de resolver que con una máquina de estado (supongo que ellos no quieren que usted utilice mod o rem) y mientras yo tenía el éxito inicial (números 5, 10, 15, y los números como de 20, 40, 80 trabajado), otros números como 130, 75 y así sucesivamente no para mí.

Me gustaría mostrar mi estado de la máquina, pero es un completo desastre (que no es un código, es un dibujo), y como dije, ni siquiera trabajo.

Básicamente lo que he intentado hacer es escribir en binario los números que son divisibles por 5, y construir una máquina de estado que va a trabajar para ellos.

Yo estaría encantado si usted podría enseñarme cómo resolver este problema, y cómo pensar cuando se enfrenta a algo como esto.

Gracias!

Answer 1

Haciendo un balance de la operación en serie de la moda es en realidad bastante fácil. El supuesto clave es que la información viene en MSB-primero, si la serie. Usted sólo necesita N a los estados para calcular el resto modulo N. de Inicio en el "0", y si usted termina para arriba en el "0" del estado después de que el último bit (no importa cuántos bits hay), el resto es cero.

^{simular este circuito – Esquema creado mediante CircuitLab}

Piense en cómo le gustaría hacer una división larga si la única cosa que usted necesita para mantener un seguimiento de se 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;

Answer 2

También puede diseñar una máquina de estado si los datos provienen de la LSB-primero:

La existencia de un autómata finito determinista (DFA)se sigue directamente de la otra respuesta, que describe el DFA de MSB-primero. Debido a que los lenguajes aceptados por los DFAs son regulares y regulares de idiomas son conocidos por ser cerrado bajo inversión (por ejemplo, ver aquí), no debe ser un afd que acepte el siguiente lenguaje:

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

Construcción

1. Copia el MSB-primer DFA de Dave Tweed de la respuesta. He utilizado el autómata herramienta de JFLAP para que.

2. Aplicar el explícito transformación algoritmo para el DFA retrocesos, por ejemplo, como se describe en la CS.SE: Diseño de un DFA y el reverso de la misma.
   Usted puede ver el (unminimized) resultado de este paso en la revisión anterior de esta respuesta.

3. Minimizar el resultante de la DFA. Por desgracia, esta característica es un poco buggy en la última JFLAP versión, así que me resigné a minimizar a mano.
   De nuevo, hay muchos algoritmos y fuentes para ellos por ahí, yo la que se describe en "DFA de Minimización" en tutorialspoint.com.
   
   (En realidad, si sus ojos están entrenados buena suficiente con mirar DFAs, usted puede ver que \ $q_0\$ \ $q_1\$ son equivalentes a los estados en el DFA como los obtenidos en el punto 2. La mía no, gracias por darse cuenta de que se vaya a supercat comentario!)

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

---

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

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

Answer 3

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

1. El número recibido hasta el momento es de N. Suponga que usted sabe el resto M = N mod 5.

2. Hay un nuevo bit viene en y el nuevo valor es ahora N' = N*2 + b.

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

Esto es bastante fácil de tabular la 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 el estado de la máquina en Dave Tweed de la respuesta.

Answer 4

Uno espera que la pregunta de la entrevista fue sobre cómo se podría resolver el problema, en lugar de los pros y los contras de VHDL o Verilog. Los detalles de lenguaje es sencillo una vez que usted tiene un algoritmo.

Si el número se pasa poco a poco con el MSB primero, y luego el valor del número modulo 5 puede ser calculada por inicializar el estado de \$S=0\$ y, a continuación, acumulando el valor de \$S \leftarrow (2 S + d) \text{ mod } 5\$. Al final, el número es divisible por 5 ffi \$S\$ es cero. Desde \$S,d\$ están delimitadas, la actualización de la ecuación puede ser escrita como una simple máquina de estados con los estados \$S=0,\cdots, 4\$.

Si el número se pasa poco a poco con LSB primero, tenemos que hacer un poco más de trabajo. El murciélago podemos intentar inicializar el estado de \$S=0, k= 0\$ y, a continuación, acumulando el valor de \$ S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow k+1 \$. El problema con esto es que \$k\$ es potencialmente ilimitada, sin embargo, desde \$2^4 = 1 \text{ mod } 5\$, podemos simplificar el de arriba para \$ S \leftarrow (S + 2^k d) \text{ mod } 5 , k \leftarrow (k+1) \text{ mod } 4\$. De nuevo, desde \$S,k,d\$ están delimitadas, la actualización de la ecuación puede ser escrita como una simple máquina de estados con los estados \$(S,k)\$ donde \$S=0,\cdots, 4\$, \$k=0,\cdots, 3\$.

Answer 5

Dependiendo de lo que el VHDL es la que se escriben para, es posible que desee tomar un enfoque que se describe como una combinatoria de cálculo. La recepción de un número puede significar que el número entero será en un registro para un ciclo de reloj.

Usted podría, por ejemplo, anote el mod 5 de el valor que cada uno de los bits que representan, añadir estos juntos y, a continuación, repita el proceso hasta que se quedan con algo menos de 5. Implementar este combinationally para todos la reducción de pasos, o volver a utilizar la lógica para algunos pequeño número de ciclos.

Pero si usas el VHDL rem operador, que puede ser la respuesta correcta. Suponiendo que la empresa ha decente herramientas de síntesis, que le daría una manera bastante eficiente de la implementación de un poco más de área de estado de la máquina de soluciones tal vez, pero llena de rendimiento y por lo tanto, probablemente la buena energía en cada cálculo. Es la opción que costaría menos tiempo para implementar y por lo tanto, probablemente la menos dinero para el empleador.

Para ser justos, no es probable que la respuesta que están buscando con tales preguntas, pero también es una oportunidad para mostrar cualquier diseño real de la experiencia.