Site Overlay

序列检测状态机原理详解

基本概念

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

画出检测顺利时的状态转移:

typora\20201211173437_416fea167a58177e0d9ac22c9781e4d8.png

其余输入都会打破正常序列。我们现在要把它们的状态迁移补上。问题是,打破序列的后,要回跳到哪里继续检测?自然不能跳到开头,因为那样就会错过重叠检测。

我们一个一个来。

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。

据此,可画出完整的状态转移图:

typora\20201211173444_e9490c4725784b22cfea729329be5c76.png

有了状态图,就可以设计程序或者电路了,这里不详述。

实际上,这也是 KMP 算法的原理。

不重叠检测

至于不重叠的检测:在最后一步,如果完成之后的串结尾和开头有重复部分,就要跳过开头的到达一个中间状态。

例子:在 0010100 序列中检测 010

不重叠的检测:s0 → s1 → s2 → s0

重叠的检测:s0 → s1 → s2 → s1010,开头结尾都是 0,所以跳过一个状态)

例子:在 00100100 序列中检测 00100

不重叠的检测:s0 → s1 → s2 → s3 → s4 → s0

重叠的检测:s0 → s1 → s2 → s3 → s4 → s200100 重叠(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

由此可得设计图如下:

typora\20201218163001_9d8ead84444309631f6347dd549d6a99.svg

优化方法

有没有办法提高效率呢?例如检测 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

发表评论

电子邮件地址不会被公开。 必填项已用*标注