吳朝暉

　?。ò不諑煼洞髮W 物理與電子信息學院，安徽 蕪湖 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所示?！?/p>

　　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描述，電路會更有通用性。

參考文獻

　?。?］ 李瑞,孫顯龍,劉寶娟.基于FPGA和VHDL的序列檢測器設計［J］.微處理機,2012,33(5)：46.

　?。?］ Hou Xianfeng, Yan Yubao, Xia Lu. Hybrid patternmatching algorithm based on BMKMP algorithm［J］. International Conference on Advanced Computer Theory & Engineering, 2010, 5(8):310313.

　?。?］ 嚴蔚敏,吳偉民.數據結構(C語言版)［M］.北京：清華大學出版社,2011.

　?。?］ 潘松,黃繼業.EDA技術實用教程VHDL版(第五版)［M］.北京:科學出版社, 2013.