我看到了一个很好的 VHDL 面试问题 - 构建一个接收数字并检测它是否可以除以 5 而没有余数的系统。我试图用状态机解决这个问题（我想他们不希望你使用mod或rem），虽然我确实取得了初步成功（数字如 5、10、15 和数字如 20、40、80 有效)，其他数字如 130、75 等对我来说都失败了。
我会展示我的状态机，但它完全是一团糟（它不是代码，它是一幅画），就像我说的那样，甚至无法正常工作。
基本上我试图做的是写下可被 5 整除的二进制数，并构建一个适用于它们的状态机。
如果你能告诉我如何解决这个问题，以及在面对这样的事情时如何思考，我会很高兴。
谢谢！
以串行方式进行余数运算实际上非常容易。关键假设是如果数据是串行的，则数据以 MSB 优先。您只需要 N 个状态来计算模 N 的余数。从“0”状态开始，如果在最后一位之后进入“0”状态（无论有多少位），余数为零。
想想如果您唯一需要跟踪的是余数，您将如何进行长除法：
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;
如果数据以 LSB 为先，您还可以设计状态机：
这种确定性有限自动机（DFA）的存在直接来自另一个答案，该答案描述了 MSB 优先的 DFA。因为 DFA 接受的语言是常规语言，并且已知常规语言在反转时是封闭的（例如，请参阅此处），因此必须有一个 DFA 接受以下语言：
\$L = \{w\in \{0,1\}^* |\ \text{reverse}(w)_{10}\ \text{可被}5\}\$整除。
从Dave Tweed 的回答中复制 MSB-first DFA 。为此，我使用了自动机工具JFLAP。
对 DFA 反转应用显式变换算法，例如 CS.SE：Designing a DFA and the reverse of it中所述。您可以在此答案的旧版本
中
看到此步骤的（未最小化）结果。
最小化生成的 DFA。不幸的是，这个特性在最新的 JFLAP 版本中有一点缺陷，所以我只能手动将其最小化。
同样，那里有许多算法和资源，我使用了tutorialspoint.com 上“DFA 最小化”中描述的一种。
（实际上，如果你的眼睛在看 DFA 方面训练得足够好，你可以直接看到\$q_0\$ 和 \$q_1\$ 是在第 2 点中获得的 DFA 中的等效状态。我的不是，谢谢注意到它去超级猫的评论！）
事实上，生成的自动机给出了正确的答案：
附录：出于可访问性的原因，接受 LSB 优先的可被 5 整除的二进制数的 DFA 是 \$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\}\$ 和 \$\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 \$
提出（MSB 优先）状态机的一种方法如下：
目前收到的号码是N。假设您知道余数M = N mod 5。
有一个新的位进来，新的价值是现在N' = N*2 + b。
新的余数是 then M' = (N*2 + b) mod 5 = (M*2 + b) mod 5。
这很容易手工制表：
mb | 米'
------------------
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
这与 Dave Tweed 回答中的状态机相匹配。
人们希望面试问题是关于如何解决问题，而不是 VHDL 或 Verilog 的来龙去脉。一旦有了算法，语言细节就很简单了。
如果数字是先用 MSB 逐位传递的，那么可以通过初始化状态 \$S=0\$ 然后用 \$S \leftarrow (2 S + d ) \文本{ mod } 5\$。最后，如果\$S\$ 为零，则该数字可被 5 整除。由于 \$S,d\$ 是有界的，更新方程可以写成一个简单的状态机，状态为 \$S=0,\cdots, 4\$。
如果数字是用LSB在前的，我们需要做更多的工作。我们可以尝试初始化状态 \$S=0, k= 0\$ 然后用 \$ S \leftarrow (S + 2^kd) \text{ mod } 5 , k \leftarrow k+ 累加值1 \$。问题在于 \$k\$ 可能是无界的，但是由于 \$2^4 = 1 \text{ mod } 5\$，我们可以将上述简化为 \$ S \leftarrow (S + 2^kd) \text{ mod } 5 , k \leftarrow (k+1) \text{ mod } 4\$. 同样，由于 \$S,k,d\$ 是有界的，因此更新方程可以写成具有状态 \$(S,k)\$ 的简单状态机，其中 \$S=0,\cdots, 4\$ , \$k=0,\cdots, 3\$.