2026年FPGA校招笔试Verilog代码题，为什么「用状态机实现序列检测」总在画状态转移图上丢分？

先说个根子上的事：很多人画状态图丢分，不是不会画，是没先把「重叠」和「输出时机」这两个词翻译成状态图语言。重叠检测的意思是匹配成功后，序列的尾巴还能当下一段的前缀用，比如检测101，遇到10101时那个中间的1要留着继续用；非重叠就是匹配完直接清零重来。你画图前先在心里过一遍：这个题是哪种？然后决定匹配态回到哪个状态。再就是Moore和Mealy的区别，Mealy输出挂在转移边上，输入一变输出可能立刻变；Moore输出挂在状态里，晚一拍。笔试里如果只让你画状态转移图，通常标的是「输入/输出」写在边上。状态数一般就是按最长匹配前缀来定，检测几位就大致几位加一个初始态，别自己发明。画完拿输入序列走一遍，能走通基本就稳了。你平时练的时候是先用代码推图，还是先画图再写代码？

先别急着画，拿张纸写三行字：目标序列、重叠还是不重叠、输出在状态里还是在边上。重叠的定义说白了就是匹配完成后保留最长后缀，比如检测1011，输入1011011时第二个1011的前两位可以复用前一次的尾巴；不重叠就直接回初始态。这三行定了，状态数基本就定了：按最长匹配前缀列，1011就是S0空、S1收到1、S10收到10、S101收到101、S1011匹配，五个状态，初始态也算一个。画的时候每条转移边上写清输入和输出，Moore把输出写在状态圈里，Mealy写在箭头旁。画完自己拿一串含重叠的输入走一遍，走不通就是回边接错了。你现在的卡点是分不清重叠，还是不确定输出该挂哪？

先给你一个判断标准：判分时老师看的是状态转移图能不能和代码一一对应，而不是图漂不漂亮。所以丢分基本就两个原因，一是状态定义没按最长匹配前缀来，二是回边接错。检测1011这种序列，状态就是空、1、10、101、1011五个，初始态也算，很多人偷懒只画四个，回边就乱了。重叠的意思说白了就是匹配完成后保留最长后缀，比如输入1011011，第二个1011的前两位可以复用前一次的尾巴；不重叠就直接回初始态。你画的时候每条转移边上写清输入和输出，Moore输出写圈里，Mealy写箭头旁。画完自己拿一串含重叠的输入走一遍，走不通就是回边接错了。你平时练的时候是先用代码推图，还是先画图再写代码？

这个问题我当年也栽过，后来复盘才明白，画状态图丢分不是画功问题，是你没把「重叠」和「输出时机」这两个词翻译成状态图语言。先说重叠。检测序列比如101，输入流是10101，中间那个101匹配完之后，末尾的1还能当下一段的前缀用，这就是重叠；非重叠就是匹配完直接清零重来。很多人一上来就凭感觉画，画到匹配态就不知道回哪去，其实规则很简单：匹配态的回边接到「当前输入能构成的最长前缀」对应的那个状态上。1011检测里，匹配态收到0，因为10110的后缀10正好是前缀，就回S10，不是回初始态。这条规则吃透了，任何序列都能推。

再说输出时机。Moore输出挂在状态圈里，输入一变输出晚一拍才稳；Mealy输出挂在转移箭头上，输入一变输出可能立刻抖。笔试如果只让画状态转移图，一般默认标「输入/输出」在边上，也就是Mealy形式，因为这样状态数少、表达紧凑。但有些题会明确要求Moore，这时候状态数可能要多一个，别硬套。

状态数方面，通用套路就是按最长匹配前缀列：检测N位，状态数大致是N加一个初始态，别自己发明中间态。画完一定要拿输入序列走一遍，特别是含重叠的那串，走不通就是回边接错了。

最后说个学习路径上的取舍。很多人喜欢先用Verilog写出来再反推图，这在课设里没问题，但笔试时间紧，反推容易漏状态。我建议平时练的时候强制自己先手画图，再用代码验证，画图那步别省。你现在的卡点具体是分不清重叠，还是不确定输出该挂哪？

换个角度看，这类题笔试判分其实有个隐藏逻辑：老师想看你有没有「状态机设计」的思维，而不是背模板。所以状态转移图丢分，往往不是画错一个箭头，而是暴露了你对状态定义的理解是模糊的。

举个例子，检测1101，有人画了四个状态就交卷，结果重叠输入1101101一来就崩了。其实你只要问自己一句：匹配成功后，我能不能保留尾巴继续用？能，就是重叠，回边要接到最长后缀对应的状态；不能，就回初始态。这一句话能解决大部分回边问题。

另外提醒一个风险点：有些题表面问状态图，实际在考你区分Moore和Mealy。如果题目没说，一般按Mealy画，输出标在箭头上，状态数少；如果明确要Moore，输出写圈里，状态数可能多一个，这时候别嫌麻烦，多一个状态反而清晰。

替代做法也有，比如先列状态转移表，把每个状态在0和1下的次态和输出都填出来，再照着表画图，错不了。这个方法慢一点，但笔试里稳。你平时练题是直接画图，还是先列表？

说白了就一句：状态定义按「最长匹配前缀」来，别自己拍脑袋。检测1101就五个态（含空态），匹配态收到0时回哪个态，取决于当前后缀里最长的那段前缀。重叠就保留这个尾巴，非重叠就回空态。判分老师看的是图能不能和代码对上，不是你画得漂不漂亮。你现在是卡在回边，还是压根没想清楚重叠这回事？

先说一个很多人没意识到的点：笔试里的序列检测题，判分重点根本不在你代码写得多优雅，而在于状态图能不能和你的代码、和题目要求三者自洽。你代码能跑通，很可能是因为你写的是「暴力移位寄存器 + 比较」那种写法，压根没用状态机，或者用了但状态定义是「凑」出来的。这种写法在工程里没问题，但笔试让你画状态图，考的就是你有没有把时序逻辑抽象成状态的能力。

那为什么偏偏丢在状态图上？我观察下来，根因是大家把「重叠」当成一个玄学概念，而不是一个可以机械推导的规则。其实重叠检测的定义非常死板：匹配成功后，把当前已匹配序列的某个后缀，当作下一段匹配的前缀继续用，取最长的那个后缀。非重叠就是匹配成功直接回初始态。你只要记住「最长后缀等于最长前缀」这条，任何序列的回边都能推出来，不需要灵感。

举个能说明问题的例子。检测 1101，状态按最长匹配前缀列：S0（空）、S1（收到1）、S11（收到11）、S110（收到110）、S1101（匹配）。现在看匹配态 S1101 收到 0 该回哪。当前串是 11010，看它的后缀：0 不是前缀 1 的开头？0 对不上，10 也对不上 1 开头，110 对不上 11……一路退，发现没有任何后缀是 1101 的前缀，所以回 S0。但如果输入是 11011，后缀 1 正好是前缀，就回 S1。你看，这就是机械推导，不需要「感觉」。

真正值得你花时间的是把这个推导过程练成肌肉记忆：拿到序列，先写前缀集合，再对每个状态在 0/1 下的次态做后缀匹配。练三五道，你会发现状态数永远是「序列长度 + 1」，回边永远落在前缀集合里的某个状态。这个套路一旦内化，状态图画错几乎不可能。

最后提一句输出时机：如果题目没明说，默认按 Mealy 画，输出标在箭头上，状态数就是长度加一；如果明确要 Moore，输出写圈里，通常要多一个状态来「记住」匹配完成这件事。你现在是卡在回边推导，还是根本没意识到自己代码里其实没用状态机？

先别急着背套路，我建议你把这件事当成一个「翻译」问题来看：脑子里对重叠和非重叠的理解，要翻译成状态图上的回边。丢分基本都出在这一步没翻译干净。

重叠检测的本质定义很死板：匹配成功后，不是清零重来，而是把当前已匹配串的某个后缀，当成下一段匹配的前缀继续用，取最长的那一个。非重叠就是匹配成功后直接回初始态。你只要把这句话当成机械规则，任何序列的回边都能推出来，不需要灵感。

举个能说明问题的例子。检测1101，状态按最长匹配前缀列就是S0、S1、S11、S110、S1101五个。匹配态S1101收到0时回哪？看11010的后缀里，最长能当前缀的是「0」，没有对应状态，那就回S0；收到1时，后缀「1」正好是S1，就回S1。你看，回边不是拍脑袋，是拿「后缀等于前缀」这条去卡。

为什么笔试偏偏爱考这个？因为老师想看的不是你代码能不能跑，而是你有没有把时序逻辑抽象成状态的能力。你写个移位寄存器加比较器，功能完全对，但让你画图你就露馅了，说明你没真正理解状态机。

还有个容易被忽略的点：Moore和Mealy。题目没说一般按Mealy画，输出标在箭头上，状态数少；明确要Moore就把输出写圈里，可能多一个状态。别嫌麻烦，多一个状态反而清晰。

画完一定要拿一串含重叠的输入自己走一遍，走不通就是回边接错了。你现在是卡在回边推导，还是压根没分清重叠这回事？

我先说个可能有点扎心的判断：状态转移图丢分，多数时候不是画错箭头，而是你脑子里对「状态是什么」这件事没有形成统一口径，所以每次做题都在重新发明一遍。

你代码能跑，说明你其实理解时序逻辑，但代码里你用的很可能是移位寄存器加比较，或者干脆用计数器凑出来的「伪状态机」。这种写法在工程里完全能用，甚至综合出来资源还更省，但笔试让你画图，考的是另一件事：你能不能把「检测一个序列」这件事抽象成有限个记忆单元。状态的定义只有一个合法口径，就是「当前已经匹配上的最长前缀」。检测1101，前缀集合是空、1、11、110、1101，五个状态，初始态也算一个。这个口径不是老师定的，是数学上唯一能保证不漏检不误检的定义。你只要承认这一点，后面所有箭头都是机械推导，不需要灵感。

回边为什么总错？因为大家把「重叠」当成一个需要理解的玄学概念。其实它是个非常死板的后缀匹配问题：匹配态收到一个输入后，把「已匹配串加这个输入」这个新串拿出来，找它最长的、同时也是目标序列前缀的后缀，那个后缀对应的状态就是次态。重叠检测允许这个后缀长度大于零，非重叠检测则强制清零回初始态。举例，检测1101，匹配态收到1，新串是11011，最长后缀里能当前缀的是「1」，回S1；收到0，新串11010，后缀里最长能当前缀的是「0」，没有这个状态，回S0。你看，没有一步需要感觉，全是查表。

那为什么还是有人反复错？我观察下来是练习方式的问题。很多人做完题对一下答案就过了，没有把「任意序列都能推」这条规则内化成肌肉记忆。建议你拿一张纸，写一个目标序列，然后强制自己把每个状态在两个输入下的次态、输出全部列成表，再照表画图。表对了图一定对，图错了表里一定能找到那一格。这个顺序别反，先画图再补表，等于用感觉去校对规则，效率很低。

输出时机那块，Moore和Mealy的取舍其实也有个实用判据：笔试如果只写「画状态转移图」，默认按Mealy画，输出标在箭头上，状态数少，回边也少，出错概率低。如果题目明确要Moore，那就把输出写进圈里，匹配态本身带输出，这时候状态数可能多一个，但结构反而更清晰。别在没要求的时候自作主张画Moore，多出来的状态很容易让你在回边上多绕一圈。

最后一个建议：画完之后别只拿一条输入走一遍，专门构造一条含重叠的输入，比如检测1101就用1101101，走通了才算真会。你现在的卡点，是回边推导本身不熟，还是Moore和Mealy该选哪个拿不准？