VHDL interview question - detecting if a number can be divided by 5 without remainder

Doing a remainder operation in serial fashion is actually quite easy. The key assumption is that the data comes in MSB-first if it's serial. You only need N states to compute a remainder modulo N. Start in the "0" state and if you end up in the "0" state after the last bit (it doesn't matter how many bits there are), the remainder is zero.

^{simulate this circuit – Schematic created using CircuitLab}

Think about how you'd do long division if the only thing you needed to keep track of was the remainder:

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;

You can also design a state machine if the data comes LSB-first:

The existence of such a deterministic finite automaton (DFA) directly follows from the other answer, which describes the DFA for MSB-first. Because languages accepted by DFAs are regular and regular languages are known to be closed under reversal (e.g. see here), there must be a DFA which accepts the following language:

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

Construction

1. Copy the MSB-first DFA from Dave Tweed's answer. I used the automaton tool JFLAP for that.

2. Apply the explicit transformation algorithm for DFA reversals, e.g. as described on CS.SE: Designing a DFA and the reverse of it.
   You can see the (unminimized) result of this step in the old revision of this answer.

3. Minimize the resulting DFA. Unfortunately, this feature is a little buggy in the latest JFLAP version, so I resigned myself to minimizing it by hand.
   Again, there are many algorithms and sources for them out there, I used the one described at “DFA Minimization” on tutorialspoint.com.
   
   (Actually, if your eyes are trained good enough with looking at DFAs, you could directly see that \$q_0\$ and \$q_1\$ are equivalent states in the DFA as obtained in point 2. Mine aren't, thanks for noticing it go to supercat's comment!)

Indeed, the resulting automaton gives the right answers:

---

Appendix: For accessibility reasons, the DFA which accepts binary numbers which are divisible by 5 with LSB-first is \$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\}\$ and \$\delta\$ as follows:

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

One way to come up with the (MSB first) state machine is as follows:

1. The number received so far is N. Assume you know the remainder M = N mod 5.

2. There is a new bit coming in and new value is now N' = N*2 + b.

3. New remainder is then M' = (N*2 + b) mod 5 = (M*2 + b) mod 5.

This is easy enough to tabulate by hand:

    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

Which matches the state machine in Dave Tweed's answer.