基本概念
什么是序列检测?比如我们要检测 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。