用于重叠序列检测器的 FSM 的状态图，该检测器检测序列“11001”并在两个时钟周期内引发标志

Question

我需要为重叠序列检测器绘制有限状态机、FSM 的状态图，该检测器检测序列“11001”并在两个时钟周期内引发标志。我可以使用两个交互的 FSM 来完成此操作，但我应该使用一个 FSM 来完成此操作。问题是当检测到像“110011001”这样的重叠序列时。不确定状态图将如何通过一个 FSM 进行转换。谢谢您的帮助。

Answer 1

要处理重叠序列，您应该将检测和提升标志分开。这可以通过使用 5 位移位寄存器来完成，通过该移位寄存器对输入数据进行移位。您的 FSM（处于“空闲”状态）观察移位寄存器，并在检测到您的搜索模式时更改为“检测到”状态。 FSM 保持在“检测到”状态，直到搜索模式从移位寄存器中消失，然后变为“空闲”状态。提升标志可以作为转换操作来完成（在从“空闲”到“检测到”的转换期间）。也许使用像HDL-FSM-Editor这样的工具来实现移位寄存器和FSM。

Answer 2

我认为 FSM 指的是确定性有限自动机 (DFA)。

解决这个问题的经典方法是，首先使用要检测的序列构建一个非确定性有限自动机 (NFA)，然后使用 Aho-Corasick 算法将 NFA 转换为 DFA。

在您的示例中，NFA 可以构造为：

{*}s0 -> {1}s1 -> {1}s2 -> {0}s3 -> {0}s4 -> {1}s5 (match)

符号

{b}sN

表示状态#

N

，如果可达，则在下一个输入是值b（0或1）时变为

活动

。请注意，

s0

对于任何输入始终处于活动状态，并且

s5

如果处于活动状态，则表示匹配。

给定上述 NFA，可以按照 Aho-Corasick 算法构建 DFA。请注意，这是一种通用方法，它不仅可以检测一个序列，还可以检测多个重叠序列。