吳朝暉
（安徽師范大學(xué) 物理與電子信息學(xué)院,，安徽 蕪湖 241000 )
摘要：基于FPGA設(shè)計一個能夠檢測出重疊匹配串的序列檢測器,。首先從KMP字符串模式匹配算法出發(fā)，推導(dǎo)出next函數(shù)值與序列檢測器狀態(tài)之間的關(guān)系,，并針對匹配串重疊的情況進(jìn)行修改,，得到有限狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖，最后用VHDL語言描述并仿真驗證,。
關(guān)鍵詞：KMP模式匹配算法,；序列檢測器,；FPGA；VHDL
0引言
序列檢測器是將一個指定的序列從數(shù)字流中檢測出來,，在通信系統(tǒng)中是常用的電路［1］,，有傳統(tǒng)設(shè)計方法，也有基于現(xiàn)場可編程門陣列（FPGA）的EDA設(shè)計方法,。EDA設(shè)計方法是以硬件描述語言為主,，它可優(yōu)化設(shè)計，提高設(shè)計效率,，具有在系統(tǒng)編程的特點(diǎn),。序列檢測器可用移位寄存器實(shí)現(xiàn)，也可以有限狀態(tài)機(jī)（FSM）來實(shí)現(xiàn),。用硬件描述語言（如VHDL）設(shè)計的有限狀態(tài)機(jī)具有相對固定的語句和程序表達(dá)方式,，電路構(gòu)建簡單，運(yùn)行速度快,，還可使用各種容錯技術(shù)保證系統(tǒng)性能穩(wěn)定可靠,。
設(shè)計序列檢測器的狀態(tài)轉(zhuǎn)換圖是設(shè)計有限狀態(tài)機(jī)的主要任務(wù)，本文采用KMP字符串模式匹配算法來設(shè)計序列檢測器的狀態(tài)轉(zhuǎn)換圖,，并且很容易實(shí)現(xiàn)一些特殊要求的序列檢測器，比如能夠檢測出匹配串重疊的序列檢測器,。
1KMP串模式匹配算法
KMP串的模式匹配算法是由KNUTH D E與PRATT V R和MORRIS J H同時發(fā)現(xiàn)的,，此算法可以在O(n+m)的時間復(fù)雜度完成串的模式匹配操作。本文首先討論此算法的一般情況［2］,。
假設(shè)主串為 S1S2…Sn ,，模式串為P1P2…Pm［3］。經(jīng)典的BF匹配算法的思想是將主串S的第1個字符與模式串P的第1個字符匹配,，若相等,，則繼續(xù)比較S的第2個字符和P的第2個字符；若不相等,，則回溯指針到S的第2個字符再重新與P的第1個字符進(jìn)行比較,。以此類推，直到全部能夠匹配為止,。但實(shí)際上在“失配”時,，S和P前面部分的字符串已比較過，是相等的,，這種已知信息說明不需要重新開始匹配,。KMP算法在此作了改進(jìn)，即不回溯指針,，此時當(dāng)主串中第i個字符與模式串的第j個字符失配時,，主串中第i個字符應(yīng)重新與模式串中第next［j］個字符相比較,。模式串的next函數(shù)的定義如式（1）所示［3］。
從定義可推導(dǎo)出求next［j］的算法,，在有多個重復(fù)字符的情況下,，還需進(jìn)一步修正。 修正之后求next［j］的C#實(shí)現(xiàn)代碼如下：
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#字符串下標(biāo)是從0開始的,，因此字符串的第0位不使用,。假設(shè)模式串為“11010011”，則通過GetNextVal("B11010011"),，計算出next的函數(shù)值,，如表1所示。
2序列檢測器狀態(tài)轉(zhuǎn)換圖
本文設(shè)計的序列檢測器能夠從連續(xù)接收到的一組串行二進(jìn)制序列中檢測出所需的二進(jìn)制序列（即模式串）“11010011”,，雖是一串二進(jìn)制數(shù),，但可以看成字符串的特例。又假設(shè)待檢測的輸入的二進(jìn)制序列為 11101001101 001101001100000000000……,。對于這樣的輸入串一般只會檢測出2個匹配串,，即串中的陰影部分。但有時卻需要檢測出中間斜體部分的串（與其他匹配串重疊）,，即檢測出3個匹配串,，本文設(shè)計的就是這種特殊的序列檢測器。
設(shè)計狀態(tài)轉(zhuǎn)換圖之前,，先定義狀態(tài),。當(dāng)輸入串的數(shù)位與模式串沒有匹配時狀態(tài)設(shè)為S0態(tài)，匹配了1個數(shù)位時設(shè)為S1態(tài),，連續(xù)匹配了n個數(shù)位時設(shè)為Sn態(tài),。 如果進(jìn)入S8態(tài)，模式串就檢測到了,。因此可定義S0,、S1、S2,、S3,、S4、S5,、S6,、S7、S8共9種狀態(tài),。
初始時S0態(tài),，當(dāng)輸入串到來時，按次序一位一位地檢測是否與模式串匹配。如果輸入串的第1個數(shù)位與模式串的第1數(shù)位(j=1) 匹配,，則進(jìn)入S1次態(tài),。如果不匹配，就重新與模式串中第next［j］個數(shù)位相比較,，因為此時next［j］=next［1］=0,，比較結(jié)果會進(jìn)入S0次態(tài)。 依此類推,，當(dāng)j=3時,，說明比較前已匹配兩個數(shù)位，初態(tài)S2態(tài),，如果現(xiàn)在輸入是“0”,， 與該位（“0”）匹配，則進(jìn)入S3次態(tài),；如果輸入的是“1”,，則與該位不匹配，因為此時next［3］=2,，所以重新與模式串的第2位比較,，此時結(jié)果一定相等（原因是KMP算法已修正，而二進(jìn)制值只有0和1）,，所以進(jìn)入S2次態(tài),。由此可得表2。
結(jié)論：初態(tài)為Sj-1態(tài)時,，輸入序列的數(shù)位與當(dāng)前模式串的j位比較,，如果匹配，進(jìn)入Sj態(tài),；如果不匹配，進(jìn)入Snext［j］態(tài),。然后再比較輸入序列的下一個數(shù)位,，以此類推。
對于檢測非重疊匹配串,，S8狀態(tài)與S0狀態(tài)等價,。但對于需要檢測出重疊匹配串的情況，S8的次態(tài)分兩種情況：一是輸入串?dāng)?shù)位為‘1’,， 可在模式串末尾加‘0’（與‘1’表2模式串“11010011”的next函數(shù)值與狀態(tài)的關(guān)系j12345678模式串11010011修正的next［j］00202100初態(tài)S0S1S2S3S4S5S6S7匹配時進(jìn)入次態(tài)S1S2S3S4S5S6S7S8不匹配時進(jìn)入次態(tài)S0S0S2S0S2S1S0S0不匹配）,，求末尾一位next值，就是次態(tài)的下標(biāo),； 二是輸入串?dāng)?shù)位為‘0’,，可在模式串末尾加‘1’（與‘0’不匹配），求末尾一位next值，就是次態(tài)的下標(biāo),。例如本例： GetNextVal(“B110100111”) ,，求出的next［9］=3，則表示輸入串的數(shù)位為‘0’時進(jìn)入S3次態(tài),。GetNextVal(“B110100110”) ,，求出的next［9］=2，則表示輸入串的數(shù)位為‘1’時進(jìn)入S2次態(tài),。最后得到完全的狀態(tài)轉(zhuǎn)換圖如圖1所示,。
3序列檢測器的VHDL描述
該狀態(tài)機(jī)屬于米勒型有限狀態(tài)機(jī),，它包含狀態(tài)說明部分,、主控時序進(jìn)程、主控組合進(jìn)程和輔助進(jìn)程幾個部分,，其中說明部分用文字符號定義各狀態(tài)元素［4］,。設(shè)電路數(shù)據(jù)輸入信號為din，時鐘信號為clk,，復(fù)位信號為rst,，輸出信號為sout。電路VHDL實(shí)現(xiàn)代碼如下,。
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態(tài)
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結(jié)論
本文將KMP字符串模式匹配算法應(yīng)用到二進(jìn)制序列檢測器的有限狀態(tài)機(jī)設(shè)計,。由于采用修正的KMP算法，并且是特定的二進(jìn)制序列,，因此只需一次比較就可知次態(tài),。如果將KMP算法也用VHDL描述，電路會更有通用性,。
參考文獻(xiàn)
?。?］ 李瑞,孫顯龍,劉寶娟.基于FPGA和VHDL的序列檢測器設(shè)計［J］.微處理機(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.
?。?］ 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)［M］.北京：清華大學(xué)出版社,2011.
?。?］ 潘松,黃繼業(yè).EDA技術(shù)實(shí)用教程VHDL版(第五版)［M］.北京:科學(xué)出版社, 2013.