基本概念
什么是序列检测？比如我们要检测 11011 序列。我们不断接收序列信号：
111010101001011011110101010110001001 （每次只接收一个，右边是过去的，左边是过来的信号）
当遇到 11011 序列（又名模式串）（上面加粗的部分）时，就输出 1，否则输出 0。所以状态机输出是这样的：
_____
Input: 111010101001011011110101010110001001
Output:000000000000010000000000000000000000
---Direction of Data Flow--->
什么是重叠检测？
注意下面用 - 标出的序列，如果检测重叠，则会在 11011011 中检测到两次 11011。（Output B）
_____
_____
Input: 111010101001011011011101010110001001
_
OutputA:000000000000010000000000000000000000
_ _
OutputB:000000000000010010000000000000000000
---Direction of Data Flow--->如果不检测重叠，则只检测到一次（Output A）
检测原理
我们以检测 11011 为例。有五个 bit，我们只需要五个状态即可检测：
State Has Awaiting
A -- 11011
B 1 1011
C 11 011
D 110 11
E 1101 1画出检测顺利时的状态转移：
其余输入都会打破正常序列。我们现在要把它们的状态迁移补上。问题是，打破序列的后，要回跳到哪里继续检测？自然不能跳到开头，因为那样就会错过重叠检测。
我们一个一个来。
| PS（现态） | 次态（NS） | 解释 |
|---|---|---|
| A, 0/ | A | A 得到 0 后是 0，11011 不以 0 的尾部字串开头，所以，只能停留原地等待 1 |
| B, 0/ | A | B 得到 0 后是 10，11011 不以 10 的尾部字串开头，所以，只能退到 A |
| C, 1/ | C | C 得到 1 后是 111, 11011 以 111 的尾部字串 11 开头，所以可以回到 C。 |
| D, 0/ | A | D 得到 1 后是 1100，只能退到 A |
| E, 1/ | C | E 得到 1 后是 11011,11011 以 11011 的尾部字串 11 开头，所以可以回到 C。并输出 1 表示检测到了模式串。（此处就是重叠检测和不重叠检测的唯一区别所在，如果不重叠检测，就跳回到 A） |
| E, 0/ | A | E 得到 0 后是 11010，只能退到 A。 |
据此，可画出完整的状态转移图：
有了状态图，就可以设计程序或者电路了，这里不详述。
实际上，这也是 KMP 算法的原理。
不重叠检测
至于不重叠的检测：在最后一步，如果完成之后的串结尾和开头有重复部分，就要跳过开头的到达一个中间状态。
例子：在 0010100 序列中检测 010
不重叠的检测：s0 → s1 → s2 → s0
重叠的检测：s0 → s1 → s2 → s1（010，开头结尾都是 0，所以跳过一个状态）
例子：在 00100100 序列中检测 00100。
不重叠的检测：s0 → s1 → s2 → s3 → s4 → s0
重叠的检测：s0 → s1 → s2 → s3 → s4 → s2，00100 重叠（00）长度是 2，跳过两个状态。
【例子】画出 01011 序列检测器的状态转移图，X 为序列输入，Z 为检测输出。(序列不重叠)
【分析】
状态设计：
| ID | Got | Expected | 0/ Next | 1/ Next |
|---|---|---|---|---|
| S0 A | - | 0 | B /0 | A /0 |
| S1 B | 0 | 1 | B /0 | C /0 |
| S2 C | 01 | 0 | D /0 | A /0 |
| S3 D | 010 | 1 | B /0 | E /0 |
| S4 E | 0101 | 1 | D /0 | A /1 |
由此可得设计图如下：
优化方法
有没有办法提高效率呢？例如检测 01011。我们用 KMP 算法：
| 0 | 01 | 010 | 0101 | ||
|---|---|---|---|---|---|
| next[i] | 0 | 1 | 0 | 1 | 3 |
https://www.bilibili.com/video/av76248417/
所以失配分别跳转到：S0, S1, S0, S1, S3 （本方法感谢 qyq 同学指导）
本文主要是参考自：http://studytronics.weebly.com/sequence-detectors.html。