吴朝晖
（安徽师范大学 物理与电子信息学院，安徽 芜湖 241000 )
摘要：基于FPGA设计一个能够检测出重叠匹配串的序列检测器。首先从KMP字符串模式匹配算法出发，推导出next函数值与序列检测器状态之间的关系，并针对匹配串重叠的情况进行修改，得到有限状态机的状态转换图，最后用VHDL语言描述并仿真验证。
关键词：KMP模式匹配算法；序列检测器；FPGA；VHDL
0引言
序列检测器是将一个指定的序列从数字流中检测出来，在通信系统中是常用的电路［1］，有传统设计方法，也有基于现场可编程门阵列（FPGA）的EDA设计方法。EDA设计方法是以硬件描述语言为主，它可优化设计，提高设计效率，具有在系统编程的特点。序列检测器可用移位寄存器实现，也可以有限状态机（FSM）来实现。用硬件描述语言（如VHDL）设计的有限状态机具有相对固定的语句和程序表达方式，电路构建简单，运行速度快，还可使用各种容错技术保证系统性能稳定可靠。
设计序列检测器的状态转换图是设计有限状态机的主要任务，本文采用KMP字符串模式匹配算法来设计序列检测器的状态转换图，并且很容易实现一些特殊要求的序列检测器，比如能够检测出匹配串重叠的序列检测器。
1KMP串模式匹配算法
KMP串的模式匹配算法是由KNUTH D E与PRATT V R和MORRIS J H同时发现的，此算法可以在O(n+m)的时间复杂度完成串的模式匹配操作。本文首先讨论此算法的一般情况［2］。
假设主串为 S1S2…Sn ，模式串为P1P2…Pm［3］。经典的BF匹配算法的思想是将主串S的第1个字符与模式串P的第1个字符匹配，若相等，则继续比较S的第2个字符和P的第2个字符；若不相等，则回溯指针到S的第2个字符再重新与P的第1个字符进行比较。以此类推，直到全部能够匹配为止。但实际上在“失配”时，S和P前面部分的字符串已比较过，是相等的，这种已知信息说明不需要重新开始匹配。KMP算法在此作了改进，即不回溯指针，此时当主串中第i个字符与模式串的第j个字符失配时，主串中第i个字符应重新与模式串中第next［j］个字符相比较。模式串的next函数的定义如式（1）所示［3］。
从定义可推导出求next［j］的算法，在有多个重复字符的情况下，还需进一步修正。 修正之后求next［j］的C#实现代码如下：
private static int［］ GetNextVal(string T)
{
int j = 1, k = 0;
int［］ nextVal = new int［T.Length］;
nextVal［0］ = 0;
while (j < T.Length - 1)
{
if(k == 0 || T［j］ == T［k］)
{
j++; k++;
if(T［j］!=T［k］)//修正时所加的代码行
nextVal［j］=k;
else//修正时所加的代码行
nextVal［j］ = nextVal［k］;//修正时所加的代码行
}
else
k = nextVal［k］;
}
return nextVal;
}
由于C#字符串下标是从0开始的，因此字符串的第0位不使用。假设模式串为“11010011”，则通过GetNextVal("B11010011")，计算出next的函数值，如表1所示。
2序列检测器状态转换图
本文设计的序列检测器能够从连续接收到的一组串行二进制序列中检测出所需的二进制序列（即模式串）“11010011”，虽是一串二进制数，但可以看成字符串的特例。又假设待检测的输入的二进制序列为 11101001101 001101001100000000000……。对于这样的输入串一般只会检测出2个匹配串，即串中的阴影部分。但有时却需要检测出中间斜体部分的串（与其他匹配串重叠），即检测出3个匹配串，本文设计的就是这种特殊的序列检测器。
设计状态转换图之前，先定义状态。当输入串的数位与模式串没有匹配时状态设为S0态，匹配了1个数位时设为S1态，连续匹配了n个数位时设为Sn态。 如果进入S8态，模式串就检测到了。因此可定义S0、S1、S2、S3、S4、S5、S6、S7、S8共9种状态。
初始时S0态，当输入串到来时，按次序一位一位地检测是否与模式串匹配。如果输入串的第1个数位与模式串的第1数位(j=1) 匹配，则进入S1次态。如果不匹配，就重新与模式串中第next［j］个数位相比较，因为此时next［j］=next［1］=0，比较结果会进入S0次态。 依此类推，当j=3时，说明比较前已匹配两个数位，初态S2态，如果现在输入是“0”， 与该位（“0”）匹配，则进入S3次态；如果输入的是“1”，则与该位不匹配，因为此时next［3］=2，所以重新与模式串的第2位比较，此时结果一定相等（原因是KMP算法已修正，而二进制值只有0和1），所以进入S2次态。由此可得表2。
结论：初态为Sj-1态时，输入序列的数位与当前模式串的j位比较，如果匹配，进入Sj态；如果不匹配，进入Snext［j］态。然后再比较输入序列的下一个数位，以此类推。
对于检测非重叠匹配串，S8状态与S0状态等价。但对于需要检测出重叠匹配串的情况，S8的次态分两种情况：一是输入串数位为‘1’， 可在模式串末尾加‘0’（与‘1’表2模式串“11010011”的next函数值与状态的关系j12345678模式串11010011修正的next［j］00202100初态S0S1S2S3S4S5S6S7匹配时进入次态S1S2S3S4S5S6S7S8不匹配时进入次态S0S0S2S0S2S1S0S0不匹配），求末尾一位next值，就是次态的下标； 二是输入串数位为‘0’，可在模式串末尾加‘1’（与‘0’不匹配），求末尾一位next值，就是次态的下标。例如本例： GetNextVal(“B110100111”) ，求出的next［9］=3，则表示输入串的数位为‘0’时进入S3次态。GetNextVal(“B110100110”) ，求出的next［9］=2，则表示输入串的数位为‘1’时进入S2次态。最后得到完全的状态转换图如图1所示。
3序列检测器的VHDL描述
该状态机属于米勒型有限状态机，它包含状态说明部分、主控时序进程、主控组合进程和辅助进程几个部分，其中说明部分用文字符号定义各状态元素［4］。设电路数据输入信号为din，时钟信号为clk，复位信号为rst，输出信号为sout。电路VHDL实现代码如下。
library ieee; use ieee.std_logic_1164.all;
entity xl is
port(din,rst,clk: in std_logic; sout: out std_logic);
end;
architecture bhv of xl is
type states is (s0,s1,s2,s3,s4,s5,s6,s7,s8);
signal st: states:=s0;
begin
process(clk,rst) begin
if rst='1' then st<=s0;
elsif clk'event and clk='1' then
case st is
when s0 => if din='1' then sout<='0'; st<= s1;
else sout<='0'; st<=s0; end if;
when s1 => if din='1' then sout<='0'; st<= s2; else sout<='0'; st<=s0; end if;
when s2 => if din='0' then sout<='0'; st<= s3; else sout<='0'; st<= s2; end if;
when s3 => if din='1' then sout<='0'; st<= s4; else sout<='0'; st<= s0; end if; 图2序列检测器仿真波形图
when s4 => if din='0' then sout<='0'; st<= s5; else sout<='0'; st<= s2; end if;
when s5 => if din='0' then sout<='0'; st<= s6; else sout<='0'; st<= s1;end if;
when s6 => if din='1' then sout<='0'; st<= s7; else sout<='0'; st<= s0; end if;
when s7 => if din='1' then sout<='1'; st<= s8; else sout<='0'; st<= s0; end if;
--s8态
when s8 => if din='0' then sout<='0'; st<= s3; else sout<='0'; st<= s2; end if;
when others => sout<='0'; st<=s0;
end case;
end if;
end process;end;
电路仿真波形图如图2所示。由图可见信号sout输出3次高电平，说明检测到3个模式串。
4结论
本文将KMP字符串模式匹配算法应用到二进制序列检测器的有限状态机设计。由于采用修正的KMP算法，并且是特定的二进制序列，因此只需一次比较就可知次态。如果将KMP算法也用VHDL描述，电路会更有通用性。
参考文献
［1］ 李瑞,孙显龙,刘宝娟.基于FPGA和VHDL的序列检测器设计［J］.微处理机,2012,33(5)：46.
［2］ Hou Xianfeng, Yan Yubao, Xia Lu. Hybrid patternmatching algorithm based on BMKMP algorithm［J］. International Conference on Advanced Computer Theory & Engineering, 2010, 5(8):310313.
［3］ 严蔚敏,吴伟民.数据结构(C语言版)［M］.北京：清华大学出版社,2011.
［4］ 潘松,黄继业.EDA技术实用教程VHDL版(第五版)［M］.北京:科学出版社, 2013.