《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 可編程邏輯 > 設(shè)計(jì)應(yīng)用 > 基于KMP串模式匹配算法的序列檢測器的FPGA設(shè)計(jì)
基于KMP串模式匹配算法的序列檢測器的FPGA設(shè)計(jì)
2016年微型機(jī)與應(yīng)用第06期
吳朝暉
(安徽師范大學(xué) 物理與電子信息學(xué)院,安徽 蕪湖 241000 )
摘要: 基于FPGA設(shè)計(jì)一個(gè)能夠檢測出重疊匹配串的序列檢測器。首先從KMP字符串模式匹配算法出發(fā),推導(dǎo)出next函數(shù)值與序列檢測器狀態(tài)之間的關(guān)系,并針對匹配串重疊的情況進(jìn)行修改,得到有限狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖,最后用VHDL語言描述并仿真驗(yàn)證。
Abstract:
Key words :

  吳朝暉

  (安徽師范大學(xué) 物理與電子信息學(xué)院,安徽 蕪湖 241000 )

      摘要:基于FPGA設(shè)計(jì)一個(gè)能夠檢測出重疊匹配串的序列檢測器。首先從KMP字符串模式匹配算法出發(fā),推導(dǎo)出next函數(shù)值與序列檢測器狀態(tài)之間的關(guān)系,并針對匹配串重疊的情況進(jìn)行修改,得到有限狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖,最后用VHDL語言描述并仿真驗(yàn)證。

  關(guān)鍵詞KMP模式匹配算法;序列檢測器;FPGA;VHDL

0引言

  序列檢測器是將一個(gè)指定的序列從數(shù)字流中檢測出來,在通信系統(tǒng)中是常用的電路[1],有傳統(tǒng)設(shè)計(jì)方法,也有基于現(xiàn)場可編程門陣列(FPGA)的EDA設(shè)計(jì)方法。EDA設(shè)計(jì)方法是以硬件描述語言為主,它可優(yōu)化設(shè)計(jì),提高設(shè)計(jì)效率,具有在系統(tǒng)編程的特點(diǎn)。序列檢測器可用移位寄存器實(shí)現(xiàn),也可以有限狀態(tài)機(jī)(FSM)來實(shí)現(xiàn)。用硬件描述語言(如VHDL)設(shè)計(jì)的有限狀態(tài)機(jī)具有相對固定的語句和程序表達(dá)方式,電路構(gòu)建簡單,運(yùn)行速度快,還可使用各種容錯(cuò)技術(shù)保證系統(tǒng)性能穩(wěn)定可靠。

  設(shè)計(jì)序列檢測器的狀態(tài)轉(zhuǎn)換圖是設(shè)計(jì)有限狀態(tài)機(jī)的主要任務(wù),本文采用KMP字符串模式匹配算法來設(shè)計(jì)序列檢測器的狀態(tài)轉(zhuǎn)換圖,并且很容易實(shí)現(xiàn)一些特殊要求的序列檢測器,比如能夠檢測出匹配串重疊的序列檢測器。

1KMP串模式匹配算法

  KMP串的模式匹配算法是由KNUTH D E與PRATT V R和MORRIS J H同時(shí)發(fā)現(xiàn)的,此算法可以在O(n+m)的時(shí)間復(fù)雜度完成串的模式匹配操作。本文首先討論此算法的一般情況[2]。

  假設(shè)主串為 S1S2…Sn ,模式串為P1P2…Pm[3]。經(jīng)典的BF匹配算法的思想是將主串S的第1個(gè)字符與模式串P的第1個(gè)字符匹配,若相等,則繼續(xù)比較S的第2個(gè)字符和P的第2個(gè)字符;若不相等,則回溯指針到S的第2個(gè)字符再重新與P的第1個(gè)字符進(jìn)行比較。以此類推,直到全部能夠匹配為止。但實(shí)際上在“失配”時(shí),S和P前面部分的字符串已比較過,是相等的,這種已知信息說明不需要重新開始匹配。KMP算法在此作了改進(jìn),即不回溯指針,此時(shí)當(dāng)主串中第i個(gè)字符與模式串的第j個(gè)字符失配時(shí),主串中第i個(gè)字符應(yīng)重新與模式串中第next[j]個(gè)字符相比較。模式串的next函數(shù)的定義如式(1)所示[3]。

  E519DB)%DBL32WEXROX(~3A.jpg

  從定義可推導(dǎo)出求next[j]的算法,在有多個(gè)重復(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])//修正時(shí)所加的代碼行

  nextVal[j]=k;

  else//修正時(shí)所加的代碼行

  nextVal[j] = nextVal[k];//修正時(shí)所加的代碼行

  }

  else

  k = nextVal[k];

  }

  return nextVal;

  }

  由于C#字符串下標(biāo)是從0開始的,因此字符串的第0位不使用。假設(shè)模式串為“11010011”,則通過GetNextVal("B11010011"),計(jì)算出next的函數(shù)值,如表1所示。

003.jpg

2序列檢測器狀態(tài)轉(zhuǎn)換圖

  本文設(shè)計(jì)的序列檢測器能夠從連續(xù)接收到的一組串行二進(jìn)制序列中檢測出所需的二進(jìn)制序列(即模式串)“11010011”,雖是一串二進(jìn)制數(shù),但可以看成字符串的特例。又假設(shè)待檢測的輸入的二進(jìn)制序列為 11101001101 001101001100000000000……。對于這樣的輸入串一般只會(huì)檢測出2個(gè)匹配串,即串中的陰影部分。但有時(shí)卻需要檢測出中間斜體部分的串(與其他匹配串重疊),即檢測出3個(gè)匹配串,本文設(shè)計(jì)的就是這種特殊的序列檢測器。

  設(shè)計(jì)狀態(tài)轉(zhuǎn)換圖之前,先定義狀態(tài)。當(dāng)輸入串的數(shù)位與模式串沒有匹配時(shí)狀態(tài)設(shè)為S0態(tài),匹配了1個(gè)數(shù)位時(shí)設(shè)為S1態(tài),連續(xù)匹配了n個(gè)數(shù)位時(shí)設(shè)為Sn態(tài)。 如果進(jìn)入S8態(tài),模式串就檢測到了。因此可定義S0、S1、S2、S3、S4、S5、S6、S7、S8共9種狀態(tài)。

  初始時(shí)S0態(tài),當(dāng)輸入串到來時(shí),按次序一位一位地檢測是否與模式串匹配。如果輸入串的第1個(gè)數(shù)位與模式串的第1數(shù)位(j=1) 匹配,則進(jìn)入S1次態(tài)。如果不匹配,就重新與模式串中第next[j]個(gè)數(shù)位相比較,因?yàn)榇藭r(shí)next[j]=next[1]=0,比較結(jié)果會(huì)進(jìn)入S0次態(tài)。 依此類推,當(dāng)j=3時(shí),說明比較前已匹配兩個(gè)數(shù)位,初態(tài)S2態(tài),如果現(xiàn)在輸入是“0”, 與該位(“0”)匹配,則進(jìn)入S3次態(tài);如果輸入的是“1”,則與該位不匹配,因?yàn)榇藭r(shí)next[3]=2,所以重新與模式串的第2位比較,此時(shí)結(jié)果一定相等(原因是KMP算法已修正,而二進(jìn)制值只有0和1),所以進(jìn)入S2次態(tài)。由此可得表2。

004.jpg

  結(jié)論:初態(tài)為Sj-1態(tài)時(shí),輸入序列的數(shù)位與當(dāng)前模式串的j位比較,如果匹配,進(jìn)入Sj態(tài);如果不匹配,進(jìn)入Snext[j]態(tài)。然后再比較輸入序列的下一個(gè)數(shù)位,以此類推。

  對于檢測非重疊匹配串,S8狀態(tài)與S0狀態(tài)等價(jià)。但對于需要檢測出重疊匹配串的情況,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匹配時(shí)進(jìn)入次態(tài)S1S2S3S4S5S6S7S8不匹配時(shí)進(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’時(shí)進(jìn)入S3次態(tài)。GetNextVal(“B110100110”) ,求出的next[9]=2,則表示輸入串的數(shù)位為‘1’時(shí)進(jìn)入S2次態(tài)。最后得到完全的狀態(tài)轉(zhuǎn)換圖如圖1所示?!?/p>

001.jpg

  3序列檢測器的VHDL描述

  該狀態(tài)機(jī)屬于米勒型有限狀態(tài)機(jī),它包含狀態(tài)說明部分、主控時(shí)序進(jìn)程、主控組合進(jìn)程和輔助進(jìn)程幾個(gè)部分,其中說明部分用文字符號定義各狀態(tài)元素[4]。設(shè)電路數(shù)據(jù)輸入信號為din,時(shí)鐘信號為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個(gè)模式串。

002.jpg

4結(jié)論

  本文將KMP字符串模式匹配算法應(yīng)用到二進(jìn)制序列檢測器的有限狀態(tài)機(jī)設(shè)計(jì)。由于采用修正的KMP算法,并且是特定的二進(jìn)制序列,因此只需一次比較就可知次態(tài)。如果將KMP算法也用VHDL描述,電路會(huì)更有通用性。

參考文獻(xiàn)

 ?。?] 李瑞,孫顯龍,劉寶娟.基于FPGA和VHDL的序列檢測器設(shè)計(jì)[J].微處理機(jī),2012,33(5):46.

  [2] 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.

  [3] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版)[M].北京:清華大學(xué)出版社,2011.

 ?。?] 潘松,黃繼業(yè).EDA技術(shù)實(shí)用教程VHDL版(第五版)[M].北京:科學(xué)出版社, 2013.


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。